Quantitative Methods (Linear Programming Model) : Optimizing a Teaching Schedule

Extracted Content from Question Files:

(See Attached Sample Problem)

The Department of Management Science and
Information Technology at Tech
The management science and information technology department at tech offers between
36 and 40 three-hour course sections each semester. Some of the courses are taught by
graduate student instructors, whereas 20 of the course sections are taught by the 10
regular tenured, faculty in the department. Before the beginning of each year the
department head sends the faculty a questionnaire asking them to rate their preference for
each course using a scale from 1 to 5, where 1 is “strongly preferred, 2 is “preferred but
not as strongly as 1”, 3 is “neutral,” 4 is “prefer but not to teach but not strongly,” and 5
is “strongly prefer not to teach this course.” The faculty have returned their preferences
as follows.

Course
______________________________________________________

Faculty Member 3424 3434 3444 3454 4434 4444 4454 4464

Clayton 2 4 1 3 2 5 5 5
Houck 3 3 4 1 2 5 5 4
Huang 2 3 2 1 3 4 4 4
Major 1 4 2 5 1 3 2 2
Moore 1 1 4 4 2 3 3 5
Ragsdale 1 3 1 5 4 1 1 2
Rakes 3 1 2 5 3 1 1 1
Rees 3 4 3 5 5 1 1 3
Russell 4 1 3 2 2 5 5 5
Sumichrast 4 3 1 5 2 3 3 1

For the fall semester the department will offer two sections each of 3424 and 4464; three
sections of 3434, 3444, 4434, 4444, and 4454; and one section of 3454.

The normal semester teaching load for a regular faculty member is two sections. (Once
the department head determines the courses, he will assign the faculty he schedules the
course times so they will not conflict.) Help the department head determine a
teach schedule that will satisfy faculty teach preferences to the greatest
degree possible.

Quantitative Methods

MAT 540
Transportation, Transshipment, and
Assignment Problems
Objectives
• When you complete this lesson, you will be
able to solve:
• Transportation problems
• Transshipment problems
• Assignment problems
Overview
• Network flow problems
• Transportation models
• Transshipment models
• Assignment models
The Transportation Model
• Characteristics
• A product is transported from a number of
sources to a number of destinations at the
minimum cost
• Each source is able to supply a fixed amount of
the product, and each destination has a fixed
amount of demand for the product
The Transportation Model,
continued
Grain Elevator Supply Mill Demand
1. Kansas City 150 A. Chicago 200
2. Omaha 175 B. St. Louis 100
3. Des Moines 275 C. Cincinnati 300
Total 600 tons Total 600 tons

Transport Cost from Grain Elevator to Mill ($/ton)
Grain Elevator A. Chicago B. St. Louis C. Cincinnati
1. Kansas City $6 $8 $10
2. Omaha 7 11 11
3. Des Moines 4 5 12
The Transportation Model,
continued
• Linear programming model
minimize Z = 6 x1A + 8 x1B + 10 x1C + 7 x2 A + 11x2 B + 11x2 C + 4 x3A + 5 x3B + 12 x3C
subject to
x1A + x1B + x1C = 150
x2 A + x2 B + x2C = 175
x3A + x3B + x3C = 275
x1A + x2 A + x3A = 200
x1B + x2 B + x3B = 100
x1C + x2C + x3C = 300
xij ≥ 0
Computer Solution of a
Transportation Problem
• Excel solution
Computer Solution of a
Transportation Problem, continued
• Excel QM solution
Computer Solution of a
Transportation Problem, continued
• Excel QM solution
Computer Solution of a
Transportation Problem, continued
• QM for Windows solution
The Transshipment Model
• Transshipment points
• Transportation may take place from
• Sources through transshipment points to
destinations
• One source to another
• One transshipment point to another
• One destination to another
• Sources to destinations
The Transshipment Model,
continued
• Nebraska, Colorado each harvest 300 tons
• Kansas City, Omaha, and Des Moines are
transshipment points

G ra in E le va to r
F a rm 3 . K a n s a s C ity 4. O m aha 5 . D e s M o in e s
1 . N e b ra s k a $16 10 12
2 . C o lo ra d o 15 14 17
The Transshipment Model,
continued
• Supply constraints for the farms
x13 + x14 + x15 = 300
x23 + x24 + x25 = 300
• Demand constraints at mills
x36 + x46 + x56 = 200
x37 + x47 + x57 = 100
x38 + x48 + x58 = 300
The Transshipment Model,
continued
• Grain shipped into Kansas City: x13 + x23
• Grain shipped out of Kansas City: x36 + x37 + x38
• The two amounts must equal one another
x13 + x23 = x36 + x37 + x38
x13 + x23 − x36 − x37 − x38 = 0

• Constraints for Omaha and Des Moines
x14 + x24 − x46 − x47 − x48 = 0
x15 + x25 − x56 − x57 − x58 = 0
The Transshipment Model,
continued
• Linear programming model
minimize Z = 16 x13 + 10 x14 + 12 x15 + 15 x23 + 14 x24 + 17 x25 + 6 x36 + 8 x37 + 10 x38
+ 7 x46 + 11x47 + 11x48 + 4 x56 + 5 x57 + 12 x58
subject to x13 + x14 + x15 = 300
x23 + x24 + x25 = 300
x36 + x46 + x56 = 200
x37 + x47 + x57 = 100
x38 + x48 + x58 = 300
x13 + x23 − x36 − x37 − x38 = 0
x14 + x24 − x46 − x47 − x48 = 0
x15 + x25 − x35 − x35 − x35 = 0
xij ≥ 0
The Transshipment Model,
continued
• Excel solution
The Assignment Problem
• All supply and demand values equal 1
• The supply at each source and the demand
at each destination are each limited to one
unit
The Assignment Problem,
continued
• Four teams of officials to four games
• Minimize distance traveled
• Supply and demand is one team of officials
per game
The Assignment Problem,
continued
• Linear programming model
minimize Z = 210 xAR + 90 xAA + 180 xAD + 160 xAC + 100 xBR + 70 xBA + 130 xBD
+ 200 xBC + 175 xCR + 105 xCA + 140 xCD + 170 xCC + 80 xDR + 65 xDA
+ 105 xDD + 120 xDC
subject to xAR + xAA + xAD + xAC = 1
xBR + xBA + xBD + xBC = 1
xCR + xCA + xCD + xCC = 1
xDR + xDA + xDD + xDC = 1
xAR + xBR + xCR + xDR = 1
xAA + xBA + xCA + xDA = 1
xAD + xBD + xCD + xDD = 1
xAC + xBC + xCC + xDC = 1
xij ≥ 0
The Assignment Problem,
continued
• Excel solution
The Assignment Problem,
continued
• Excel QM solution
The Assignment Problem,
continued
• QM for Windows Solution