REVISED

M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 130

Transportation and Assignment Models

10
C H A P T E R

TEACHING SUGGESTIONS shipping network. It is an application that has intuitive appeal.

Both QM for Windows and Excel QM software are easy to run on
Teaching Suggestion 10.1: Transportation Models in the Chapter.
these problems.
This is a long chapter, in part, because of the four transportation
algorithms that are discussed. If time is an issue in your course, se- Teaching Suggestion 10.7: Sensitivity Analysis on the
lect one of the two initial solution methods and one of the two Assignment Problem.
final solution methods to cover in class. The easiest, but not most This algorithm is easy to use and understand. Tell about solving a
efficient, are the northwest corner and stepping-stone rules. large staffing problem, then discuss the cost implications if one
worker is not available or insists on doing a particular task. It is
Teaching Suggestion 10.2: Using the Northwest Corner Rule.
easy, with the software, to recompute the answers and conduct a
This approach is easily understood by students and is appealing to
sensitivity analysis. This is the basis of Problem 10-37.
teach for that very reason. Make sure the students understand the
weakness of the algorithm (that is, it ignores costs totally). Ask Teaching Suggestion 10.8: Maximizing Assignment Problems.
them to come up with their own approaches that could improve on This section is needed if students are to solve maximization prob-
this. Invariably, a good student will present an approach that lems by hand, but QM for Windows and Excel QM software
comes very close to VAM. Name the student’s approach after him negate the need by handling both types of problems. The section
(or her) and tell him he could have been famous if he had devised can be skipped if the software is being used.
it 50 years earlier. Teaching Suggestion 10.9: Problem 10-37.
Teaching Suggestion 10.3: Using the Stepping-Stone Method. In assigning this challenging aggregate planning problem, you
Students usually pick up the concept of a closed path and learn to may wish to first provide some background information on how to
trace the pluses and minuses fairly quickly. But they run into prob- structure the plan. Remind students that back ordering is not per-
lems when they have to cross over an empty cell. Stress that the cities mitted, so very large costs must be inserted in many cells. Note
in the tableau are just in random order, so crossing an unoccupied that Problem 10-23 (Mehta Company) is a warm-up exercise for
box is fine. The big test is Table 10.5. Once students comprehend this data set problem.
this tracing, they are usually ready to move on. Remind students that
there is only one closed path that can be traced for each unused cell. ALTERNATIVE EXAMPLES
Teaching Suggestion 10.4: Dummy Rows and Columns. Alternative Example 10.1: Let us presume that a product is
Another confusing issue to students is whether to add a dummy made at two of our factories which we wish to ship to three of our
row (source) or dummy column (destination) in a transportation warehouses. We produce 18 at factory A and 22 at factory B; we
problem. A slow and careful explanation is valuable so that stu- want 10 in warehouse 1, 20 in warehouse 2, and 10 in warehouse
dents can reach an intuitive understanding as to the correct choice. 3. Per unit transportation costs are A to 1, $4; A to 2, $2; A to 3,
Also note that the software adds these dummies automatically. $3; B to 1, $3; B to 2, $2; B to 3, $1. The corresponding trans-
Teaching Suggestion 10.5: Handling Degeneracy in portation table is
Transportation Problems.
Just as a warning, be aware that students are often confused by the TO Warehouses
concept of where to place the zero so that the closed paths can be FROM 1 2 3 Total
traced. Carefully explain why you chose or didn’t choose a certain 4 2 3
cell. The choice of cell can affect the number of iterations that fol- Factory A 18
low.
3 2 1
Teaching Suggestion 10.6: Facility Location Problems. Factory B 22
These are an important application of the transportation model and
Total 10 20 10 40
make it easy to compare how a new city will fit into an existing

130
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 131

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 131

The northwest corner approach follows: PERIOD

Feb. Mar. Apr.
TO Warehouses
Demand 55 70 75
FROM 1 2 3 Total
Capacity
4 2 3 Regular 50 50 50
Factory A 10 8 18 Overtime 5 5 5
3 2 1 Subcontract 12 12 10
Factory B 12 10 22 Beginning inventory 10
Costs
Total 10 20 10 40 Regular time $60 per unit
Overtime 80 per unit
Subcontract 90 per unit
Let us determine the total cost of transportation with this initial Inventory carrying cost $1 per unit per month
northwest corner solution. For each filled cell, simply multiply the
number of units being shipped by the unit shipping cost and then
See the bottom of the next page for the solution.
add those transhipment costs. Thus, in the order in which the cells
were filled, we have 10($4) ⫹ 8($2) ⫹ 12($2) ⫹ 10($1) ⫽ $90. Alternative Example 10.4: As an example of an assignment
Using stepping-stone or MODI, we can find the optimal problem, let us assume that Susan is a sorority pledge coordinator
solution: with four jobs and only three pledges. Susan decides that the as-
signment problem is appropriate except that she will attempt to
SOLUTION:
minimize total time instead of money (since the pledges aren’t
paid). Susan also realizes that she will have to create a fictitious
TO Warehouses fourth pledge and she knows that whatever job gets assigned to
FROM 1 2 3 Total that pledge will not be done (this semester, anyhow). She creates
4 2 3 estimates for the respective times and places them in the following
Factory A 18 18 table:
3 2 1
Factory B 10 2 10 22 Job 1 Job 2 Job 3 Job 4
Total 10 20 10 40 Barb 4 9 3 8
Cindy 7 8 2 6
Donna 3 4 5 7
Cost ⫽ 18($2) ⫹ 10($3) ⫹ 2($2) ⫹ 10($1) ⫽ $80. Zingo 0 0 0 0
Alternative Example 10.2: There is often an imbalance be-
tween the amounts produced and the amounts desired in the ware- Zingo is, of course, a fictitious pledge, so her times are all zero.
houses. In Alternative Example 10.1, there were 40 units produced
(a) The first step in this algorithm is to develop the opportu-
and forty units demanded for warehousing. Let us presume that an
nity cost table. This is done by subtracting the smallest num-
additional 4 units are desired at each warehouse, increasing the
ber in each row from every other value in that row, then,
total demand to 14 ⫹ 24 ⫹ 14 ⫽ 52. The supply shortage of 12
using these newly created figures, by subtracting the smallest
units prevents a solution of this problem until we create a dummy
number in each column from every other value in that col-
factory that produces a fake 12 units. The cost to ship a false unit
umn. Whenever these smallest values are zero, the subtrac-
from a dummy factory or to a dummy warehouse is zero. After the
tion results in no change. Susan’s resulting matrix is
final optimal solution is computed, the false units and dummy fa-
cilities are ignored. Our new example with a dummy factory and a
Job 1 Job 2 Job 3 Job 4
northwest corner initial solution would look like this:
Barb 1 6 0 5
Cindy 5 6 0 4
TO Warehouses Donna 0 1 2 4
FROM 1 2 3 Total Zingo 0 0 0 0
4 2 3
Factory A 14 4 18 No change was produced when dealing with the columns
3 2 1 since the smallest values were always the zeros from row four.
Factory B 20 2 22 (b) The next step is to draw lines through all of the zeros.
Dummy 0 0 0 The lines are to be straight and either horizontal or vertical.
Factory C 12 12 Furthermore, you are to use as few lines as possible. If it re-
quires four of these lines (four because it is a 4 ⫻ 4 matrix),
Total 14 24 14 52
an optimal assignment is already possible. If it requires fewer
than four lines, another step is required before optimal as-
Alternative Example 10.3: Here is a production application of signments may be made. In our example, draw a line through:
the transportation problem. Set up the following problem in a row four, column three, either column one or row three. One
transportation format and solve for the minimum-cost plan: version of the matrix is
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 132

132 CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS

Job 1 Job 2 Job 3 Job 4 (d) Since all of the zeros can be lined out with three lines,
this is still not optimal. Hence, we repeat the step of finding
Barb 1 6 0 5
the smallest uncovered number and both subtracting that
Cindy 5 6 0 4
quantity from uncovered numbers and adding it to those
Donna 0 1 2 4
Zingo 0 0 0 0 numbers at line intersections. The resultant matrix, after
being lined again, is
(c) Since the number of lines required was less than the
Job 1 Job 2 Job 3 Job 4
number of assignees, a third step is required (as is normally
the case). Looking at the version of the matrix with the lines Barb 0 4 0 3
through it, determine the smallest number. Subtract this Cindy 4 4 0 2
smallest number from every number not covered by a line Donna 0 0 3 3
Zingo 1 0 2 0
and add it to every number at the intersection of two lines.
Repeat the lining out process, with the following result:
Since this matrix requires four lines to cover all zeros, we
Job 1 Job 2 Job 3 Job 4 have now reached an optimal solution stage.
(e) Although there is more than one sequence in which to
Barb 0 5 0 4
make the assignments, in our example the assignments must
Cindy 4 5 0 3
Donna 0 1 3 4
be: Cindy, job 3; Barb, job 1; Donna, job 2; Zingo, job 4.
Zingo 0 0 1 0 Since Zingo is a dummy row, the job labeled job 4 does not
get completed. The total time is 10.
Which is still not an optimum solution.

Table for Alternative

Example 10-3:
Transportation Solution
Demand for:
Total
Unused Capacity
Capacity Available
Supply from: Feb. Mar. Apr. (Dummy) (Supply)
Period

Beginning 0 1 2 0
inventory 10 10
60 61 62 0
Regular time 45 5 50
February

80 81 82 0
Overtime 5 5
90 91 92 0
Subcontract 3 9 12
999 60 61 0
Regular time 50 50
March

999 80 81 0
Overtime 5 5
999 90 91 0
Subcontract 2 10 12
999 999 60 0
Regular time 50 50
999 999 80 0
April

Overtime 5 5
999 999 90 0
Subcontract 10 10
Demand 55 70 75 9 209
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 133

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 133

SOLUTIONS TO DISCUSSION QUESTIONS TO Project Project Project Personnel

AND PROBLEMS FROM 1 2 3 Available

10-1. The transportation model is an example of decision mak- $11 $14 $6

ing under certainty where a decision maker knows beforehand Adams 1 1
exactly what state of nature will occur (see Chapter 2). In trans- 8 10 11
portation problems, this means that the costs of each shipping Brown 1 1
route, the demand at each destination, and the supply at each 9 12 7
source are all known with certainty. Cooper 1 1
10-2. Vogel’s approximation method gives a good initial solu- Project Needs 1 1 1 3
tion because it makes each allocation on the basis of the opportu-
nity cost, or penalty, that would be incurred if that allocation is not
chosen (see Section 10.6). The northwest corner rule does not take The northwest corner initial assignment above yields a degenerate
into account the shipping costs associated with each route alterna- solution (only three squares are filled instead of the required five).
tive as does VAM. Nevertheless, the northwest corner rule could This will always be a problem when applying the transportation
provide as low-cost an initial solution—but only if, by chance, it method to assignment problems. The problem will be degenerate
turned out that the lowest-cost routes happened to be on the ini- because there will be only one assignment in a given row or
tially assigned squares. column.
10-3. A balanced transportation problem is one in which total 10-9. It is not necessary to rework the assignment solution.
demand (from all destinations) is exactly equal to total supply Changing each entry in the cost table will not result in different
(from all sources). If a problem is unbalanced, it is necessary to total opportunity cost tables. The optimal cost will, however, be
establish either a dummy source (if demand is greater than supply) increased by $25 from $492 to $517 because of the extra $5
or a dummy destination (if demand is less than supply). Refer to charge for each of the five workers.
Section 10.7. 10-10. To exclude any unwanted or unacceptable assignment
10-4. This would cause two filled cells to become empty simul- from occurring, it is necessary only to place a very high artificial
taneously. This means that the solution in the next table will be de- cost in the row and column representing that particular assign-
generate. Placing a 0 in one of these two cells and treating this as a ment. If, for example, all of the relocation costs for Simmons’s
filled cell can resolve this difficulty. firm were in the range $1,000 to $3,000, an artificial cost of
$20,000 could be placed on the unwanted assignment. Conversely,
10-5. The total cost will decrease $2 for each unit that is placed
if we were dealing with a maximization problem, a very low rating
in this empty cell. Since the maximum that can be placed in this
would be given to the unacceptable assignment.
cell is 80 units, the total cost will decrease by 2(80)  $160. This
means the total cost for the solution in the next table will be 10-11. a. Initial solution to modify Executive Furniture Corpo-
$900  $160  $740. In general, when moving from one trans- ration problem using the northwest corner rule:
portation table to the next, the total cost will decrease by the im-
provement index for the cell to be filled times the minimum num- TO Albu- Factory
ber of units in any of the “negative” cells in the steppingstone path. FROM querque Boston Cleveland Capacity
10-6. When m ⫹ n ⫺ 1 squares (where m ⫽ number of rows 5 4 3
and n ⫽ number of columns) are not occupied, the solution is de- Des Moines 200 100 300
generate. Not enough squares are occupied to allow us to draw a 8 4 3
closed path for all unused squares. Hence we would not be able to Evansville 100 50 150
evaluate all of the unused routes. To handle this problem, we se- Fort 9 7 5
lect one empty square, place a zero in it, pretend as if it is occu- Lauderdale 250 250
pied, and proceed as in a normal, nondegenerate case. (To bring
Warehouse
the number of allocations to m ⫹ n ⫺ 1, it may be necessary to
Requirements 200 200 300 700
place a zero in more than one empty square.)
10-7. The enumeration method is not a practical means of solv-
ing 5 ⫻ 5 or 7 ⫻ 7 problems because of the number of possible as- Total cost of this initial solution
signments to be considered. In the 5 ⫻ 5 case, 5! (⫽ 5 ⫻ 4 ⫻ 3 ⫻ ⫽ 200($5) ⫹ 100($4) ⫹ 100($4) ⫹ 50($3)
2 ⫻ 1) ⫽ 120 alternatives need to be evaluated. In the 7 ⫻ 7 case, ⫹ 250($5)
there are 7! ⫽ 5,040 alternatives.
⫽ 1,000 ⫹ 400 ⫹ 400 ⫹ 150 ⫹ 1,250
10-8. The assignment problem is a special case of the trans-
⫽ $3,200
portation problem and hence can be solved with the approach
shown earlier in this chapter. This is illustrated for the Fix-It Shop b. To see if this initial solution is optimal, we compute im-
problem. Notice that the column and row requirements will always provement indices for each unused square, namely, D–C,
be equal to 1. E–A, F–A, and F–B:
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 134

134 CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS

D–C index path ⫽ D–C to E–C to E–B to D–B 0 0

⫽ $3 ⫺ 3 ⫹ 4 ⫺ 4 ⫽ $0 TO Albu- Factory
FROM querque Boston Cleveland Capacity
E–A index path ⫽ E–A to E–B to D–B to D–A
⫽ $8 ⫺ 4 ⫹ 4 ⫺ 5 ⫽ ⫹$3 5 4 3
Des Moines 200 300 1
F–A index path ⫽ F–A to F–C to E–C to E–B to D–B to D–A
8 4 3
⫽ ⫹$9 ⫺ 5 ⫹ 3 ⫺ 4 ⫹ 4 ⫺ 5 ⫽ ⫹$2 Evansville 150 1
F–B index path ⫽ F–B to F–C to E–C to E–B Fort 9 7 5
⫽ ⫹$7 ⫺ 5 ⫹ 3 ⫺ 4 ⫽ ⫹$1 Lauderdale 250 250 2
This solution is optimal, so further stepping–stone computations Warehouse
are not necessary. Requirements 200 200 300
c. The improvement index for square D–C is zero. This im-
plies the presence of multiple optimal solutions. Practically When the Ft. Lauderdale row is eliminated from further considera-
speaking, management could close the E–C shipping route and tion, we have the opportunity costs shown below. We assign
send 50 units on the D–C route instead. The table below illus- 50 units from Des Moines to Cleveland. Then the only remaining
trates the overall changes in this alternative optimal solution. column is Boston, so the assignments are made where possible.
Evaluating the empty cells indicates that this is the optimal solution
with a cost of $3,200.
TO Albu- Factory
FROM querque Boston Cleveland Capacity 0 0

5 4 3 TO Albu- Factory
Des Moines 200 50 50 300 FROM querque Boston Cleveland Capacity

8 4 3 5 4 3
Evansville 150 0 150 Des Moines 200 50 50 300 1

Fort 9 7 5 8 4 3
Lauderdale 250 250 Evansville 150 150 1

Warehouse Fort 9 7 5
Requirements 200 200 300 700 Lauderdale 250 250 -
Warehouse
Requirements 200 200 300
Total cost of alternative optimal solution
10-13. a. Hardrock’s initial solution using the northwest corner
⫽ 200($5) ⫹ 50($4) ⫹ 50($3) ⫹ 150($4) ⫹ 250($5) rule is shown below.
⫽ $3,200
TO Plant
10-12. Using VAM, we find the opportunity costs by compar- FROM A B C Capacity
ing the lowest cost cell in each row (and column) with the second
10 4 11
lowest cost cell in that row (or column). The results are given in 1 40 30 70
the table below. We avoid the high opportunity cost by putting as
many units as possible in the lowest cost cell for the row or col- 12 5 8
2 20 30 50
umn with the highest opportunity cost.
9 7 6
3 30 30
3 0 0
TO Albu- Factory Project
FROM querque Boston Cleveland Capacity Requirements 40 50 60 150

5 4 3 Cost ⫽ 40($10) ⫹ 30($4) ⫹ 20($5) ⫹ 30($8) ⫹ 30($6)

Des Moines 200 300 1
⫽ $1,040
8 4 3
Using the stepping-stone method, the following improvement in-
Evansville 150 1
dices are computed:
Fort 9 7 5
plant 1–project C ⫽ $11 ⫺ $4 ⫹ $5 ⫺ $8 ⫽ ⫹$4
Lauderdale 250 2
(closed path: 1-C to 1-B to 2-B to 2-C)
Warehouse plant 2–project A ⫽ ⫹$12 ⫺ $5 ⫹ $4 ⫺ $10 ⫽ $1
Requirements 200 200 300 (closed path: 2-A to 2-B to 1-B to 1-A)
plant 3–project A ⫽ ⫹$9 ⫺ $6 ⫹ $8 ⫺ $5 ⫹ $4 ⫺ $10 ⫽ $0
We eliminate the Albuquerque column from consideration be- (closed path: 3-A to 3-C to 2-C to 2-B to 1-B to 1-A)
cause all 200 units in this column have been allocated. We find plant 3–project B ⫽ ⫹$7 ⫺ $6 ⫹ $8 ⫺ $5 ⫽ ⫹$4
new opportunity costs based on the remaining rows and columns. (closed path: 3-B to 3-C to 2-C to 2-B)
In the next iteration of this process, the opportunity costs are the Since all indices are greater than or equal to zero, this initial solu-
same as in the original table. tion provides the optimal transportation schedule, namely, 40 units
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 135

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 135

from 1 to A, 30 units from 1 to B, 20 units from 2 to B, 30 units

from 2 to C, and 30 units from 3 to C.
b. There is an alternative optimal solution to this problem.
This fact is seen by the index for plant 3–project A being
equal to zero. The other optimal solution, should you wish for
students to pursue it, is as follows:
plant 1–project A ⫽ 20 units
plant 1–project B ⫽ 50 units
plant 2–project C ⫽ 50 units
plant 3–project A ⫽ 20 units
plant 3–project C ⫽ 10 units
Total cost remains unchanged at $1,040.
10-14. Hardrock’s problem now requires the addition of a
dummy project (destination) because supply exceeds demand. The
northwest corner initial solution is as follows:

TO
FROM A B C Dummy Capacity
10 4 11 0
1 40 30 70
12 5 8 0
2 20 30 50
9 7 6 0
3 30 30 60
Requirements 40 50 60 30 180

Cost of initial solution ⫽ 40($10) ⫹ 30($4) ⫹ 20($5)

⫹ 30($8) ⫹ 30($6) ⫹ 30($0)
⫽ $1,040
This is the same initial assignment and cost as that found in Prob-
lem 10-13. This coincidence occurs because the change in plant
capacity is at the lower right-hand corner of the table and is unaf-
fected by the northwest corner rule.
Testing the unused routes:
plant 1–project C index ⫽ $11 ⫺ 8 ⫹ 5 ⫺ 4 ⫽ ⫹$4
plant 1–dummy index ⫽ ⫹$0 ⫺ 0 ⫹ 6 ⫺ 8 ⫹ 5 ⫺ 4 ⫽ ⫺$1
best plant 2–project A index ⫽ ⫹$12 ⫺ 5 ⫹ 4 ⫺ 10 ⫽ ⫹$1
improvement plant 2–dummy index ⫽ ⫹$0 ⫺ 0 ⫹ 6 ⫺ 8 ⫽ ⫺$2
index plant 3–project A index ⫽ ⫹$9 ⫺ 6 ⫹ 8 ⫺ 5 ⫹ 4 ⫺ 10 ⫽ $0
plant 3–project B index ⫽ ⫹$7 ⫺ 6 ⫹ 8 ⫺ 5 ⫽ ⫹$4
The second table involves bringing the plant 2–dummy route
into the solution as follows:

TO
FROM A B C Dummy Capacity
10 4 11 0
1 40 30 70
12 5 8 0
2 20 0 30 50
9 7 6 0
3 60 60
Requirements 40 50 60 30 180

Cost of this iteration ⫽ $980.

 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 136

136 CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS

Because two squares became zero by opening the plant 2–dummy

route, the current solution is degenerate (fewer than 3 rows ⫹ 4
columns ⫺ 1 square are occupied). We will need to place an artifi-
cial zero in an unused square (such as plant 2–project C) to be able
to trace all of the closed paths and evaluate where this solution is
optimal.
We now trace the closed paths for the six unused squares (we
assume that the plant 2–project C square has a zero in it). The in-
dices are:
plant 1–project C ⫽ ⫹$11 ⫺ 8 ⫹ 5 ⫺ 4 ⫽ ⫹$4
plant 1–dummy ⫽ ⫹$0 ⫺ 0 ⫹ 5 ⫺ 4 ⫽ ⫹$1
plant 2–project A ⫽ ⫹$12 ⫺ 5 ⫹ 4 ⫺ 10 ⫽ ⫹$1
plant 3–project A ⫽ ⫹$9 ⫺ 6 ⫹ 8 ⫺ 5 ⫹ 4 ⫺ 10 ⫽ $0
plant 3–project B ⫽ ⫹$7 ⫺ 6 ⫹ 8 ⫺ 5 ⫽ ⫹$4
plant 3–dummy ⫽ ⫹$0 ⫺ 0 ⫹ 8 ⫺ 6 ⫽ ⫹$2
Since all indices are zero or positive, an optimal solution has been
reached. Again, note that the plant 3–project A route has an im-
provement index of $0, implying that an alternative optimal solu-
tion exists. The alternative optimal solution, whose total cost is
also $980, is shown in the following table.

TO
FROM A B C Dummy Capacity
10 4 11 0
1 20 50 70
12 5 8 0
2 20 30 50
9 7 6 0
3 20 40 60
Requirements 40 50 60 30 180

10-15. a. Using the northwest corner rule for the Saussy Lum- The improved solution is shown in the following table. Its
ber Company data, the following initial solution is cost is $255.
reached:
TO Customer Customer Customer
TO Customer Customer Customer FROM 1 2 3 Capacity
FROM 1 2 3 Capacity
3 3 2
3 3 2 Pineville 25 25
Pineville 25 25
4 2 3
4 2 3 Oak Ridge 30 10 40
Oak Ridge 5 30 5 40
3 2 3
3 2 3 Mapletown 5 25 30
Mapletown 30 30
Demand 30 30 35 95
Demand 30 30 35 95

Initial cost ⫽ 25($3) ⫹ 5($4) ⫹ 30($2) ⫹ 5($3) ⫹ 30($3)

⫽ $260
b. Applying the stepping-stone method, the improvement
indices are computed:
Pineville–customer 2 ⫽ ⫹$3 ⫺ 2 ⫹ 4 ⫺ 3 ⫽ ⫹$2
best Pineville–customer 3 ⫽ ⫹$2 ⫺ 3 ⫹ 4 ⫺ 3 ⫽ $0
improve-
Mapletown–customer 1 ⫽ ⫹$3 ⫺ 3 ⫹ 3 ⫺ 4
ment
⫽ ⫺$1
index
Mapletown–customer 2 ⫽ ⫹$2 ⫺ 3 ⫹ 3 ⫺ 2 ⫽ $0
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 137

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 137

Checking improvement indices again, we find that this improved Calculations of the Ri’s, Kj’s, and improvement indices are
solution is still not optimal. The improvement index for the R1 ⫹ K1 ⫽ C11 ⇒ 0 ⫹ K1 ⫽ 3 or K1 ⫽ 3
Pineville–customer 3 route ⫽ ⫹$2 ⫺ 3 ⫹ 3 ⫺ 3 ⫽ ⫺$1. Hence
R3 ⫹ K1 ⫽ C31 ⇒ R3 ⫹ 3 ⫽ 3 or R3 ⫽ 0
another shift is necessary. The third iteration is shown in the fol-
lowing table: R1 ⫹ K3 ⫽ C13 ⇒ 0 ⫹ K3 ⫽ 2 or K3 ⫽ 2
R2 ⫹ K3 ⫽ C23 ⇒ R2 ⫹ 2 ⫽ 3 or R2 ⫽ 1
TO Customer Customer Customer
R2 ⫹ K2 ⫽ C22 ⇒ 1 ⫹ K2 ⫽ 2 or K2 ⫽ 1
FROM 1 2 3 Capacity
Improvement indices:
3 3 2
Pineville 0 25 25 Pineville–customer 2 ⫽ I12
⫽ C12 ⫺ R1 ⫺ K2 ⫽ 3 ⫺ 0 ⫺ 1 ⫽ ⫹2
4 2 3
Oak Ridge 30 10 40 Oak Ridge–customer 1 ⫽ I21
⫽ C21 ⫺ R2 ⫺ K1 ⫽ 4 ⫺ 1 ⫺ 3 ⫽ 0
3 2 3
Mapletown 30 0 30 Mapletown–customer 2 ⫽ I32
⫽ C32 ⫺ R3 ⫺ K2 ⫽ 2 ⫺ 0 ⫺ 1 ⫽ ⫹1
Demand 30 30 35 95
Mapletown–customer 3 ⫽ I33
The cost of this solution is $230. Since two squares went to zero ⫽ C33 ⫺ R3 ⫺ K3 ⫽ 3 ⫺ 0 ⫺ 2 ⫽ ⫹1
simultaneously in this last table, the solution has become degener- Final solution with Ri and Kj values:
ate. However, an examination of improvement indices reveals that
K1 ⫽ 3 K2 ⫽ 1 K3 ⫽ 2
this current solution is optimal.
TO Customer Customer Customer
10-16. Solving the Saussy Lumber Company problem with
FROM 1 2 3 Capacity
MODI, we begin with the same initial solution as found in Prob-
lem 10-15: 3 3 2
R1 ⫽ 0 Pineville 0 25 25
K1 K2 K3
4 2 3
TO Customer Customer Customer R2 ⫽ 1 Oak Ridge 30 10 40
FROM 1 2 3 Capacity
3 2 3
3 3 2 R3 ⫽ 0 Mapletown 30 30
R1 Pineville 25 25
Demand 30 30 35 95
4 2 3
R2 Oak Ridge 5 30 5 40
3 2 3
R3 Mapletown 30 30
Demand 30 30 35 95

R1 ⫽ 0
R1 ⫹ K1 ⫽ C11 ⇒ 0 ⫹ K1 ⫽ 3 or K1 ⫽ 3
R2 ⫹ K1 ⫽ C21 ⇒ R2 ⫹ 3 ⫽ 4 or R2 ⫽ 1
R2 ⫹ K2 ⫽ C22 ⇒ 1 ⫹ K2 ⫽ 2 or K2 ⫽ 1
R2 ⫹ K3 ⫽ C23 ⇒ 1 ⫹ K3 ⫽ 3 or K3 ⫽ 2
R3 ⫹ K3 ⫽ C33 ⇒ R3 ⫹ 2 ⫽ 3 or R3 ⫽ 1
Improvement indices are as follows:
Pineville–customer 2 ⫽ I12
⫽ C12 ⫺ R1 ⫺ K2 ⫽ 3 ⫺ 0 ⫺ 1 ⫽ ⫹2
Pineville–customer 3 ⫽ I13
best ⫽ C13 ⫺ R1 ⫺ K3 ⫽ 2 ⫺ 0 ⫺ 2 ⫽ 0
improvement Mapletown–customer 1 ⫽ I31
index ⫽ C31 ⫺ R3 ⫺ K1 ⫽ 3 ⫺ 1 ⫺ 3 ⫽ ⫺1
Mapletown–customer 2 ⫽ I32
⫽ C32 ⫺ R3 ⫺ K2 ⫽ 2 ⫺ 1 ⫺ 1 ⫽ 0
The final solution is also evaluated using MODI below and to the
right.
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 138

138 CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS

10-17. Krampf Lines Railway Company’s initial northwest cor-

ner solution is shown below.
K1 ⫽ 50 K2 ⫽ 30 K3 ⫽ ⫺40 K4 ⫽ ⫺90
TO Coal Coal
FROM Valley Coaltown Junction Coalsburg Supply
50 30 60 70
R1 ⫽ 0 Morgantown 30 5 35
20 80 10 90
R2 ⫽ 50 Youngstown 40 20 60
100 40 80 30
R3 ⫽ 120 Pittsburgh 5 20 25
Demand 30 45 25 20 120

Initial solution’s total cost

⫽ 30(50 miles) ⫹ 5(30 miles) ⫹ 40(80 miles) ⫹ 20(10 miles) ⫹ 5(80 miles) ⫹ 20(30 miles)
⫽ 6,050 car-miles
To test for improvement with MODI, we set up an equation for
each occupied square:
R1 ⫽ 0
R1 ⫹ K1 ⫽ 50 0 ⫹ K1 ⫽ 50 or K1 ⫽ 50
R1 ⫹ K2 ⫽ 30 0 ⫹ K2 ⫽ 30 or K2 ⫽ 30
R2 ⫹ K2 ⫽ 80 R2 ⫹ 30 ⫽ 80 or R2 ⫽ 50
R2 ⫹ K3 ⫽ 10 50 ⫹ K3 ⫽ 10 or K3 ⫽ ⫺40
R3 ⫹ K3 ⫽ 80 R3 ⫺ 40 ⫽ 80 or R3 ⫽ 120
R3 ⫹ K4 ⫽ 30 120 ⫹ K4 ⫽ 30 or K4 ⫽ ⫺90
index13 ⫽ C13 ⫺ R1 ⫺ K3 ⫽ 60 ⫺ 0 ⫺ (⫺40)
⫽ ⫹100
index14 ⫽ C14 ⫺ R1 ⫺ K4 ⫽ 70 ⫺ 0 ⫺ (⫺90)
⫽ ⫹160
index21 ⫽ C21 ⫺ R2 ⫺ K1 ⫽ 20 ⫺ 50 ⫺ 50
⫽ ⫺80
index24 ⫽ C24 ⫺ R2 ⫺ K4 ⫽ 90 ⫺ 50 ⫺ (⫺90)
best ⫽ ⫹130
improvement index31 ⫽ C31 ⫺ R3 ⫺ K1 ⫽ 100 ⫺ 120 ⫺ 50
index ⫽ ⫺70
index32 ⫽ C32 ⫺ R3 ⫺ K2 ⫽ 40 ⫺ 120 ⫺ 30
⫽ ⫺110
Second Krampf solution—cost ⫽ 5,500 miles:

K1 ⫽ 50 K2 ⫽ 30 K3 ⫽ ⫺40 K4 ⫽ 20
TO Coal Coal
FROM Valley Coaltown Junction Coalsburg Supply
50 30 60 70
R1 ⫽ 0 Morgantown 30 5 35
20 80 10 90
R2 ⫽ 50 Youngstown 35 25 60
100 40 80 30
R3 ⫽ 10 Pittsburgh 5 20 25
Demand 30 45 25 20 120
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 139

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 139

R1 ⫽ 0 index13 ⫽ C13 ⫺ R1 ⫺ K3 ⫽ 60 ⫺ 0 ⫺ (⫺40)

R1 ⫹ K1 ⫽ 50 ⇒ K1 ⫽ 50 ⫽ ⫹100
R1 ⫹ K2 ⫽ 30 ⇒ K2 ⫽ 30 index14 ⫽ C14 ⫺ R1 ⫺ K4 ⫽ 70 ⫺ 0 ⫺ 20
⫽ ⫹50
R2 ⫹ K2 ⫽ 80 ⇒ R2 ⫽ 50 best
improvement index21 ⫽ C21 ⫺ R2 ⫺ K1 ⫽ 20 ⫺ 50 ⫺ 50
R2 ⫹ K3 ⫽ 10 ⇒ K3 ⫽ ⫺40
index ⫽ ⫺80
R3 ⫹ K2 ⫽ 40 ⇒ R3 ⫽ 10
index24 ⫽ C24 ⫺ R2 ⫺ K4 ⫽ 90 ⫺ 50 ⫺ 20
R3 ⫹ K4 ⫽ 30 ⇒ K4 ⫽ 20 ⫽ ⫹20
index31 ⫽ C31 ⫺ R3 ⫺ K1 ⫽ 100 ⫺ 10 ⫺ 50
⫽ ⫹40
index33 ⫽ C33 ⫺ R3 ⫺ K3 ⫽ 80 ⫺ 10 ⫺ (⫺40)
⫽ ⫹110
Third and optimal Krampf solution ⫽ 3,100 miles:

TO Coal Coal
FROM Valley Coaltown Junction Coalsburg Supply
50 30 60 70
Morgantown 35 35
20 80 10 90
Youngstown 30 5 25 60
100 40 80 30
Pittsburgh 5 20 25
Demand 30 45 25 20 120

10-18. A dummy destination (column) is added. Using VAM,

the initial solution is the optimal solution.

TO Factory
FROM Dallas Atlanta Denver Dummy Capacity
8 12 10
Houston 800 50 850
10 14 9
Phoenix 250 200 200 650
11 8 12
Memphis 300 300
Warehouse 800 600 200 200
Requirements

In the optimal solution we ship 800 from Houston to Dallas, 50 Cleveland, and 130 from Denver to Chicago. There will be 30
from Houston to Atlanta, 250 from Phoenix to Atlanta, 200 from units left in Denver that are not needed. The total cost is $5,310.
Phoenix to Denver, and 300 from Memphis to Atlanta. The total
10-21. a. VAM steps are as follows:
cost is $14,700.
1. Assign 30 units to C–W (the W column has the
10-19. If Vogel’s Approximation is used, the initial solution is
greatest difference, 7) and place X’s in all other
the optimal solution. This is to ship 120 from Reno to Phoenix, 20
row C squares.
from Denver to Phoenix, 160 from Pittsburgh to Cleveland, and
180 from Denver to Chicago. The total cost is $5,700. 2. Assign 20 units to B–X.
10-20. The problem is unbalanced and a dummy destination 3. Assign 10 units to B–W.
must be added. The optimal solution is to ship 120 from Reno to 4. Assign 20 units to A–Z.
Phoenix, 20 from Denver to Phoenix, 160 from Pittsburgh to 5. Assign 35 units to A–Y and 15 units to B–Y.
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 140

140 CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS

TO Excess
FROM W X Y Z Supply
12 4 9 5
A X X 35 20 55 4
8 1 6 6
B 10 20 15 X 45 0
1 12 4 7
C 30 X X X 30
Power Demand 40 20 50 20 130

Total VAM cost ⫽ 35(9) ⫹ 20(5) ⫹ 10(8) ⫹ 20(1)

⫹ 15(6) ⫹ 30(1)
⫽ 635

b. MODI technique to test for optimality:

K1 ⫽ 11 K2 ⫽ 4 K3 ⫽ 9 K4 ⫽ 5
TO Excess
FROM W X Y Z Supply
12 4 9 5
R1 ⫽ 0 A 35 20 55
8 1 6 6
R2 ⫽ ⫺3 B 10 20 15 45
1 12 4 7
R3 ⫽ ⫺10 C 30 30
Power Demand 40 20 50 20 130

R1 ⫽ 0
R1 ⫹ K3 ⫽ 9 K3 ⫽ 9
R1 ⫹ K4 ⫽ 5 K4 ⫽ 5
R2 ⫹ K3 ⫽ 6 R2 ⫽ ⫺3
R2 ⫹ K1 ⫽ 8 K1 ⫽ 11
R2 ⫹ K2 ⫽ 1 K2 ⫽ 4
R3 ⫹ K1 ⫽ 1 R3 ⫽ ⫺10
index11 ⫽ C11 ⫺ R1 ⫺ K1 ⫽ 12 ⫺ 0 ⫺ 11 ⫽ ⫹1
index12 ⫽ C12 ⫺ R1 ⫺ K2 ⫽ 4 ⫺ 0 ⫺ 4 ⫽ 0
index24 ⫽ C24 ⫺ R2 ⫺ K4 ⫽ 6 ⫺ (⫺3) ⫺ 5 ⫽ ⫹4
index32 ⫽ C32 ⫺ R3 ⫺ K2 ⫽ 12 ⫺ (⫺10) ⫺ 4 ⫽ ⫹18
index33 ⫽ C33 ⫺ R3 ⫺ K3 ⫽ 4 ⫺ (⫺10) ⫺ 9 ⫽ ⫹5
index34 ⫽ C34 ⫺ R3 ⫺ K4 ⫽ 7 ⫺ (⫺10) ⫺ 5 ⫽ ⫹12
Since all improvement indices are zero or positive, this solution
is optimal. An alternative optimal solution, however, is A–X ⫽ 20,
A–Y ⫽ 15, A–Z ⫽ 20, B–W ⫽ 10, B–Y ⫽ 35, C–W ⫽ 30, cost ⫽
$635.
10-22. The initial solution using the northwest corner rule shows
that degeneracy exists. The number of rows plus the number of
columns minus 1 ⫽ 4 ⫹ 3 ⫺ 1 ⫽ 6. But the number of occupied
squares is only 5. Refer to the numbers not circled. To solve the
problem a zero will have to be placed in a square (such as 2–C).
This will enable all unused paths to be closed.
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 141

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 141

The optimal solution to Problem 10-22, through the use of

our computer program, is circled. Cost ⫽ $1,036.

TO
FROM A B C Supply
72 8 9 4
1 26 15 31 72
38 5 6 8
2 38 38
7 9 6
3 46 34 12 46
5 3 7
4 19 19 19
Demand 110 34 31 175

10-23. Using VAM to find an initial solution, we make the fol-

lowing assignment:

TO Hospital Hospital Hospital Hospital

FROM 1 2 3 4 Supply
8 9 11 16
Bank 1 50 X X X 50 1
12 7 5 8
Bank 2 X 70 10 X 80
14 10 6 7
Bank 3 40 X 30 50 120 1
Demand 90 70 40 50 250

Cost of VAM ⫽ 50($8) ⫹ 70($7) ⫹ 10($5)

assignment ⫹ 40($14) ⫹ 30($6) ⫹ 50($7)
⫽ $2,030
Application of the MODI or stepping-stone methods will
yield the following solution in one more iteration. The optimal
cost is $2,020.

TO Hospital Hospital Hospital Hospital

FROM 1 2 3 4 Supply
8 9 11 16
Bank 1 50 50
12 7 5 8
Bank 2 10 70 80
14 10 6 7
Bank 3 30 40 50 120
Demand 90 70 40 50 250
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 142

142 CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS

10-24. The optimal solution to the Hall Real Estate decision is

shown in the table below.

TO Drury Max.
FROM Hill St. Banks St. Park Ave. Lane Avail.
8% 8% 10% 11%
First Homestead $40,000 $40,000 $ 80,000
9% 10% 12% 10%
Commonwealth $60,000 $40,000 $100,000
9% 11% 10% 9%
Washington Federal $90,000 $30,000 $120,000
Loan Needed $60,000 $40,000 $130,000 $70,000 $300,000

The total interest cost would be $28,300, or an average rate of Table for Problem 10-26
9.43%. An alternative optimal solution exists. It is
First Homestead–Hill Street 30,000
TO Production
First Homestead–Banks Street 40,000 FROM Los Angeles New York Capacity
First Homestead–Park Avenue 10,000
Commonwealth–Hill Street 30,000 $14 $11
Atlanta 600 600
Commonwealth–Drury Lane 70,000
Washington Federal–Park Avenue 120,000 $9 $12
Tulsa 200 700 900
$9 $10
10-25. Mehta’s production smoothing problem is a good exer- New Orleans 500 500
cise in the formulation of transportation problems and applying
Demand 800 1,200 2,000
them to real-world issues. The problem may be set up as in the
table on the top of the next page. All squares with X’s represent
nonfeasible (backorder) solutions. In applying a computer pro-
gram to solve such a problem, a very large cost (say about $5,000) Total cost ⫽ (600 units ⫻ $14) ⫹ (200 units ⫻ $9)
would be assigned to each of these squares. This would assure that ⫹ (700 units ⫻ $12) ⫹ (500 units ⫻ $10)
they would not appear in the final solution. The dummy destina- ⫽ $8,400 ⫹ $1,800 ⫹ $8,400 ⫹ $5,000
tion (month) is added to balance the problem. ⫽ $23,600
The initial solution has a cost of $65,700.
The costs for the beginning inventory in months 1, 2, 3, and 4 Is this initial solution optimal? We once again employ the step-
could be 0, 10, 20, and 30 respectively if the carrying cost for the ping-stone method to test it and to compute improvement indices
beginning inventory has already been considered. The solution is for unused routes.
the same but the cost would be $65,300. Improvement index for Atlanta to New York route:

10-26. To determine which new plant will yield the lowest cost ⫹$11 (Atlanta to New York)
for Ashley in combination with the existing plants, we need to ⫺$14 (Atlanta to Los Angeles)
solve two transportation problems. We begin by setting up a trans- ⫹$9 (Tulsa to Los Angeles)
portation table that represents the opening of the third plant in
⫺$12 (Tulsa to New York)
New Orleans (see the table). The northwest corner method is used
to provide an initial solution. The total cost of this first solution is ⫽ ⫺$6
seen to be $23,600. You should note that the cost of each individ-
ual “plant to distribution center” route is found by adding the
distribution costs to the respective unit production costs. Thus
the total production plus shipping cost of one auto top carrier
from Atlanta to Los Angeles is $14 ($8 for shipping plus $6 for
production).
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 143

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 143

Table for Problem 10-25

Destination (Month)
Sources 1 2 3 4 Dummy Capacity
10 20 30 40 0
Beginning inventory 40 40
100 110 120 130 0
Regular prod. (month 1) 80 20 100
130 140 150 160 0
Overtime (month 1) 50 50
100 110 120 0
Regular prod. (month 2) 90 10 100
130 140 150 0
Overtime (month 2) 50 50
100 110 0
Regular prod. (month 3) 100 100
130 140 0
Overtime (month 3) 50 50
100 0
Regular prod. (month 4) 100 100
130 0
Overtime (month 4) 50 50
150 150 150 150 0
Outside purchases 30 420 450
Demand 120 160 240 100 470 1,090

10-26 (continued)
Improvement index for New Orleans to Los Angeles route: index for Atlanta to Los Angeles
⫹$9 (New Orleans to Los Angeles) ⫽ ⫹$14 ⫺ $11 ⫹ $12 ⫺ $9 ⫽ ⫹$6
index for New Orleans to Los Angeles
⫺$10 (New Orleans to New York) ⫽ ⫹$9 ⫺ $10 ⫹ $12 ⫺ $9 ⫽ ⫹$2
⫹$12 (Tulsa to New York) Since both indices are greater than zero, we have reached an opti-
⫺$9 (Tulsa to Los Angeles) mal solution. If Ashley selects to open the New Orleans plant, the
⫽ ⫹$2 firm’s total distribution system cost will be $20,000. If the Houston
plant site is chosen, the initial solution is as follows:
Since the firm can save $6 for every unit it ships from Atlanta to
New York, it will want to improve the initial solution and send as
many as possible (600 in this case) on this currently unused route. TO Production
FROM Los Angeles New York Capacity
$14 $11
TO Production
Atlanta 600 600
FROM Los Angeles New York Capacity
$9 $12
$14 $11
Tulsa 200 700 900
Atlanta 600 600
$7 $9
$9 $12
Houston 500 500
Tulsa 800 100 900
Demand 800 1,200 2,000
$9 $10
New Orleans 500 500
Total cost of initial solution
Demand 800 1,200 2,000
⫽ $8,400 ⫹ $1,800 ⫹ $8,400 ⫹ $4,500
⫽ $23,100
You may want to confirm that the total cost is now $20,000, a
savings of $3,600 over the initial solution. Improvement index for Atlanta to New York
Again, we must test the two unused routes to see if their im- ⫽ ⫹$11 ⫺ $14 ⫹ $9 ⫺ $12
provement indices are negative numbers. ⫽ ⫺$6
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 144

144 CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS

Improvement index for Houston to Los Angeles

⫽ ⫹$7 ⫺ $9 ⫹ $12 ⫺ $9
⫽ ⫹$1
The improved solution by opening Atlanta to New York
route is shown below.

TO Production
FROM Los Angeles New York Capacity
$14 $11
Atlanta 600 600
$9 $12
Tulsa 800 100 900
$7 $9
Houston 500 500
Demand 800 1,200 2,000

Total cost of improved solution ⫽ $19,500.

Improvement indices for Atlanta to New York and Houston
to Los Angeles routes are both positive at this point. Hence an op-
timal solution has been reached. Upon comparing total costs for
the Houston option ($19,500) to those for the New Orleans option
($20,000), we would recommend to Ashley that all factors being
equal, the Houston site should be selected.
10-27. Considering Fontainebleau, we have

South Pacific
Canada America Rim Europe Capacity
60 70 75 75
Waterloo 4,000 4,000 8,000
55 55 40 70
Pusan 2,000 2,000
60 50 65 70
Bogota 5,000 5,000
75 80 90 60
Fontainebleau 4,000 5,000 9,000
Market Demand 4,000 5,000 10,000 5,000 24,000

Optimal cost ⫽ $1,530,000.

Considering Dublin, we have the following initial northwest corner
solution:

South Pacific
Canada America Rim Europe Capacity
60 70 75 75
Waterloo 4,000 4,000 8,000
55 55 40 70
Pusan 1,000 1,000 2,000
60 50 65 70
Bogota 5,000 5,000
70 75 85 65
Dublin 4,000 5,000 9,000
Market Demand 4,000 5,000 10,000 5,000 24,000
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 145

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 145

Final solution
South Pacific
Canada America Rim Europe Capacity
60 70 75 75
Waterloo 4,000 4,000 8,000
55 55 40 70
Pusan 2,000 2,000
60 50 65 70
Bogota 5,000 5,000
70 75 85 65
Dublin 4,000 5,000 9,000
Market Demand 4,000 5,000 10,000 5,000 24,000

Optimal cost ⫽ $1,535,000.

There is no difference in the routing of shipments, but the
Fontainebleau location is $5,000 less expensive than the Dublin
location. As a practical matter, changes in exchange rates, subjec-
tive factors, or evaluation of future intangibles may overwhelm
such a small difference in cost.
10-28. Considering East St. Louis, we have:
Initial solution—northwest corner rule:

Decatur Minn. C’dale E. St. L. Demand

20 17 21 29
Blue Earth 250 250
25 27 20 30
Ciro 50 150 200
22 25 22 30
Des Moines 50 150 150 350
Capacity 300 200 150 150 800

Optimal solution:

Decatur Minn. C’dale E. St. L. Demand

20 17 21 29
Blue Earth 50 200 250
25 27 20 30
Ciro 150 50 200
22 25 22 30
Des Moines 250 100 350
Capacity 300 200 150 150 800

Optimal cost using East St. Louis: $17,400.

Considering St. Louis, we have:
Initial solution—northwest corner rule:

Decatur Minn. C’dale St. Louis Demand

20 17 21 27
Blue Earth 250 250
25 27 20 28
Ciro 50 150 200
22 25 22 31
Des Moines 50 150 150 350
Capacity 300 200 150 150 800
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 146

146 CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS

Optimal solution:

Decatur Minn. C’dale St. Louis Demand

20 17 21 27
Blue Earth 200 50 250
25 27 20 28
Ciro 100 100 200
22 25 22 31
Des Moines 300 50 350
Capacity 300 200 150 150

Optimal cost using St. Louis: $17,250.

Therefore, St. Louis is $150 per week less expensive than East St.
Louis.
10-29. Considering East St. Louis, we have:
Initial solution—northwest corner rule:

Decatur Minn. C’dale E. St. L. Demand

70 77 91 69
Blue Earth 250 250
75 87 90 70
Ciro 50 150 200
72 85 92 70
Des Moines 50 150 150 350
Capacity 300 200 150 150

Optimal solution:

Decatur Minn. C’dale E. St. L. Demand

70 77 91 69
Blue Earth 50 200 250
75 87 90 70
Ciro 150 50 200
72 85 92 70
Des Moines 250 100 350
Capacity 300 200 150 150

Optimal cost using East St. Louis: $60,900.

Considering St. Louis, we have:
Initial solution—northwest corner rule:

Decatur Minn. C’dale St. Louis Demand

70 77 91 77
Blue Earth 250 250
75 87 90 78
Ciro 50 150 200
72 85 92 81
Des Moines 50 150 150 350
Capacity 300 200 150 150
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 147

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 147

Optimal solution:

Decatur Minn. C’dale St. Louis Demand

70 77 91 77
Blue Earth 200 50 250
75 87 90 78
Ciro 100 100 200
72 85 92 81
Des Moines 300 50 350
Capacity 300 200 150 150

Optimal cost using St. Louis: $62,250. Return to step 2—cover all zeros:
Therefore, East St. Louis is $1,350 per week less expensive than
St. Louis. MACHINE
JOB W X Y Z
10-30. Step 1—row subtraction:
A12 0 2 3 2

MACHINE A15 1 0 1 0
JOB W X Y Z B2 0 1 0 1
A12 0 4 6 3 B9 0 0 1 1
A15 0 1 3 0
Assignment can be made:
B2 0 3 3 2
Job A12 to machine W
B9 0 2 4 2
Job A15 to machine Z
Job B2 to machine Y
Column subtraction: Job B9 to machine X
Time ⫽ 10 ⫹ 12 ⫹ 12 ⫹ 16 ⫽ 50 hours
MACHINE
JOB W X Y Z 10-31. The initial table used for the assignment problem is:

A12 0 3 3 3 Job 1 Job 2 Job 3 Job 4

A15 0 0 0 0 Billy 400 90 60 120

Taylor 650 120 90 180
B2 0 2 0 2 Mark 480 120 80 180
B9 0 1 1 2 John 500 110 90 150

Solving this using the assignment module in QM for Windows,

Step 2—minimum straight lines to cover zeros: the following assignments are made:
Billy–Job 1; Taylor–Job 2; Mark–Job 3; John–Job 4
The total time is 750 minutes.
MACHINE
JOB W X Y Z 10-32. For the prohibited route where no assignment may be
A12 0 3 3 3 made, a very high cost (10,000 miles) used to prevent anything
from being assigned here. The initial assignment table is:
A15 0 0 0 0
Kansas City Chicago Detroit Toronto
B2 0 2 0 2
Seattle 1500 1730 1940 2070
B9 0 1 1 2
Arlington 460 810 1020 1270
Oakland 1500 1850 2080 10000
Step 3—subtract the smallest uncovered number from all the un- Baltimore 960 610 400 330
covered numbers—add it to numbers at intersections of two lines: The optimal solution found using the QM for Windows assign-
ment module is:
MACHINE The Seattle crew will go to Detroit.
JOB W X Y Z The Arlington crew will go to Kansas City.
A12 0 2 3 2 The Oakland crew will go to Chicago.
The Baltimore crew will go to Toronto.
A15 1 0 1 0
The total distance is 4,580 miles.
B2 0 1 0 1
B9 0 0 1 1
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 148

148 CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS

10-33. If the total distance is maximized, we assign a very low 10-38. The following optimal assignments can be made:
cost (miles) to the prohibited route to prevent this assignment. A
cost of 0 is used. The initial table is: Assignment Cost
Component C53 to plant 6 0.06
Kansas City Chicago Detroit Toronto Component C81 to plant 3 0.04
Seattle 1500 1730 1940 2070 Component D5 to plant 4 0.30
Arlington 460 810 1020 1270 Component D44 to plant 5 0.10
Oakland 1500 1850 2080 0 Component E2 to plant 2 0.07
Baltimore 960 610 400 330 Component E35 to plant 8 0.06
Component G99 to plant 1 0.55
Total cost $1.18
With the solution found using QM for Windows, the Seattle crew
will go to Chicago; the Arlington crew will go to Toronto; the
Oakland crew will go to Detroit; the Baltimore crew will go to 10-39. Students should note the large numbers used to block in-
Kansas City; and the total distance is 6,040 miles. This maximum feasible production plans (see Printout 1 on the next
distance is 1,460 miles more than the minimum distance (4,580). page).
a. The solution yields a cost of $2,591,200. The plan is
10-34. Because this is a maximization problem, each number is
shown in Printout 2. There are multiple optimal solutions.
subtracted from 95. The problem is then solved using the mini-
b. Yes, the solution now costs $2,640,500 with 275 per
mization algorithm.
month in regular time.
c. If overtime rises by $100 per unit to $1,400 per unit,
Assignment Rating
the cost increases, from part a, to $2,610,100. The pro-
Anderson—finance 95 duction plan remains the same as in Printout 2.
Sweeney—economics 75 If overtime cost is $1,200 per unit, the total cost is
Williams—statistics 85
$2,572,100.
McKinney—management 380
Total rating 335

10-35. Assignment Rating

Hawkins to cardiology 18
Condriac to urology 32
Bardot to orthopedics 24
Hoolihan to obstetrics 12
Total “cost scale” 86

10-36. Each rating is subtracted from 27.1 because this is a max-

imization problem.

Assignment Rating
1–2 P.M. on A 27.1
2–3 P.M. on C 17.1
3–4 P.M. on B 18.5
4–5 P.M. on independent 12.8
Overall rating 75.5

10-37. Assignment Rating

Adams to project 3 $ 6
Brown to project 2 10
Cooper to project 1 9
Davis to dummy $00
$25

Thus, the optimal solution does not change by adding a fourth

member. Davis is assigned to the dummy (nonexistent project).
This is because Davis is not the relatively least-cost assignment to
any of the first three projects.
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 149

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 149

Printout 1 for Problem 10-39 (Computer Data Entry. The costs are in $1,000s.)

JAN FEB MARCH APR MAY JUNE JULY AUG Supply

REG 1. 1.1 1.2 1.3 1.4 1.5 1.6 1.7 235
OT 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2. 20
SUB 1.5 1.6 1.7 1.8 1.9 2. 2.1 2.2 12
REG 10. 1. 1.1 1.2 1.3 1.4 1.5 1.6 255
OT 10. 1.3 1.4 1.5 1.6 1.7 1.8 1.9 24
SUB 10. 1.5 1.6 1.7 1.8 1.9 2. 2.1 15
REG 10. 10. 1. 1.1 1.2 1.3 1.4 1.5 290
OT 10. 10. 1.3 1.4 1.5 1.6 1.7 1.8 26
SUB 10. 10. 1.5 1.6 1.7 1.8 1.9 2. 15
REG 10. 10. 10. 1. 1.1 1.2 1.3 1.4 300
OT 10. 10. 10. 1.3 1.4 1.5 1.6 1.7 24
SUB 10. 10. 10. 1.5 1.6 1.7 1.8 1.9 17
REG 10. 10. 10. 10. 1. 1.1 1.2 1.3 300
OT 10. 10. 10. 10. 1.3 1.4 1.5 1.6 30
SUB 10. 10. 10. 10. 1.5 1.6 1.7 1.8 17
REG 10. 10. 10. 10. 10. 1. 1.1 1.2 290
OT 10. 10. 10. 10. 10. 1.3 1.4 1.5 28
SUB 10. 10. 10. 10. 10. 1.5 1.6 1.7 19
REG 10. 10. 10. 10. 10. 10. 1. 1.1 300
OT 10. 10. 10. 10. 10. 10. 1.3 1.4 30
SUB 10. 10. 10. 10. 10. 10. 1.5 1.6 19
REG 10. 10. 10. 10. 10. 10. 10. 1. 290
OT 10. 10. 10. 10. 10. 10. 10. 1.3 30
SUB 10. 10. 10. 10. 10. 10. 10. 1.5 20
Demand 255. 294. 321. 301. 330. 320. 345. 340.
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 150

150 CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS

Printout 2 for Problem 10-39 (Computer Solution to HAIFA. Multiple Optimal Solutions)

Optimal cost  JAN FEB MARCH APR MAY JUNE JULY AUG Dummy
$2,591,200
REG 235.
OT 20.
SUB 0. 0. 12.
REG 255.
OT 24.
SUB 15.
REG 290.
OT 26.
SUB 5. 10.
REG 300.
OT 1. 0. 23.
SUB 17.
REG 300.
OT 30.
SUB 17.
REG 290.
OT 28.
SUB 2. 17.
REG 300.
OT 30.
SUB 15. 0. 4.
REG 290.
OT 30.
SUB 20.

RT ⫽ regular time; OT ⫽ overtime; SUB ⫽ subcontracting

10-40. a. Here is the first schedule using our software. b. The revised schedule is

Optimal Solution: 96.0 Optimal Solution: 92.0

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0
2 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0
3 0 0 0 1 0 0 0 0 0 0 3 0 0 0 0 0 0 1 0 0 0
4 0 0 1 0 0 0 0 0 0 0 4 0 0 1 0 0 0 0 0 0 0
5 1 0 0 0 0 0 0 0 0 0 5 1 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 1 0 0 6 0 0 0 0 0 0 0 1 0 0
7 0 0 0 0 0 0 0 0 0 1 7 0 0 0 1 0 0 0 0 0 0
8 0 0 0 0 0 0 1 0 0 0 8 0 0 0 0 0 0 0 0 0 1
9 0 0 0 0 0 0 0 0 1 0 9 0 0 0 0 0 0 0 0 1 0
10 0 1 0 0 0 0 0 0 0 0 10 0 1 0 0 0 0 0 0 0 0
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 151

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 151

c. Yes, there is a new schedule: Third VAM assignment with W’s requirement satisfied:
2 4 3
Optimum Solution: 93.0 TO
FROM A B C Available
1 2 3 4 5 6 7 8 9 10
4 3 3
1 0 0 0 0 1 0 0 0 0 0
W X 15 20 35 1
2 0 0 0 0 0 1 0 0 0 0
3 0 0 0 0 0 0 1 0 0 0 6 7 6
4 0 0 1 0 0 0 0 0 0 0 Y X 50 0
5 0 0 0 1 0 0 0 0 0 0 8 2 5
6 0 0 0 0 0 0 0 1 0 0 Z X 50 X 50 3
7 1 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 1 Demand 30 65 40 135
9 0 0 0 0 0 0 0 0 1 0
10 0 1 0 0 0 0 0 0 0 0 The third VAM table involves assigning 20 units to the W–C
route. This is done because column C has the highest difference
and square W–C the lowest cost in that column.
SOLUTIONS TO INTERNET HOMEWORK PROBLEMS Final assignment for Cohen Clothing Group:
10-41. Jessie Cohen Clothing Group’s first VAM assignment 2 4 3
table:
TO
2 1 2 FROM A B C Available

TO Factory 4 3 3
FROM A B C Availability W X 15 20 35 0

4 3 3 6 7 6
W 35 0 Y 30 X 20 50 0

6 7 6 8 2 5
Y 50 0 Z X 50 X 50 3

8 2 5 Demand 30 65 40 135
Z X 50 X 50 3
Store Demand 30 65 40 135 The final assignment (above) is made by completing the row and
column requirements. This means that 30 units must be assigned
to Y–A and 20 units to Y–C.
In the initial assignment table above, we see that the Z row has the The total cost of this VAM assignment ⫽ (15 units ⫻ $3) ⫹
greatest difference (3). We assign the minimum possible number (20 units ⫻ $3) ⫹ (30 units ⫻ $6) ⫹ (20 units ⫻ $6) ⫹ (50
of units (50) to the least-cost route (Z–B) in that row. units ⫻ $2) ⫽ $505. A quick check using the stepping-stone index
Second VAM assignment with B’s requirement satisfied: method indicates that this VAM solution is optimal.
2 4 3 10-42.
TO OFFICE
FROM A B C Available MAN Omaha Miami Dallas
4 3 3 Jones 800 1,100 1,200 Row subtraction
W 15 35 0 is done next.
Smith 500 1,600 1,300
6 7 6
Y X 50 0 Wilson 500 1,000 2,300

8 2 5
Z X 50 X 50 3 OFFICE
Demand 30 65 40 135 MAN Omaha Miami Dallas
Jones 0 300 400 Column
This second VAM table (above) indicates that the greatest differ- subtraction
Smith 0 1,100 800
ence is now in the B column (4). We may assign up to 15 units to is done next.
Wilson 0 500 1,800
the W–B square without exceeding the demand at store B.
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 152

152 CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS

OFFICE CUSTOMER
MAN Omaha Miami Dallas SITE A B C D
Jones 0 0 0 Cover zeros 1 4 0 0 5 Cover zeros
with lines next. with lines.
Smith 0 800 400 2 1 0 1 1
Wilson 0 200 1,400 3 0 1 2 0
4 4 2 2 0
OFFICE
MAN Omaha Miami Dallas
CUSTOMER
Jones 0 0 0 Subtract SITE A B C D
smallest
Smith 0 800 400 1 4 0 0 5
number next.
Wilson 0 200 1,400 2 1 0 0 1
3 0 1 2 0

OFFICE 4 4 2 2 0
MAN Omaha Miami Dallas
Optimal assignment:
Jones 200 0 0 Cover zeros
with lines next. taxi at post 1 to customer C
Smith 0 600 200 taxi at post 2 to customer B
Wilson 0 0 1,200 taxi at post 3 to customer A
taxi at post 4 to customer D
OFFICE Total distance traveled ⫽ 4 ⫹ 4 ⫹ 6 ⫹ 4 ⫽ 18 miles.
MAN Omaha Miami Dallas 10-44. Original problem:
Jones 200 0 0
CASE
Smith 0 600 200 SQUAD A B C D E
Wilson 0 0 1,200 1 14 7 3 7 27 Row sub-
traction
2 20 7 12 6 30
Optimal assignment: is
3 10 3 4 5 21 done
Jones to Dallas
4 8 12 7 12 21 next.
Smith to Omaha
Wilson to Miami 5 13 25 24 26 8
Cost ⫽ $1,200 ⫹ $500 ⫹ $1,000
⫽ $2,700
CASE
10-43. Original problem: SQUAD A B C D E
CUSTOMER 1 11 4 0 4 24 Column
SITE A B C D subtrac-
2 14 1 6 0 24
tion is
1 7 3 4 8 Row 3 7 0 1 2 18 done
subtraction
2 5 4 6 5 4 1 5 0 5 14 next.
is done
3 6 7 9 6 next. 5 5 17 16 18 0
4 8 6 7 4

CASE
CUSTOMER SQUAD A B C D E
SITE A B C D 1 10 4 0 4 24 Cover
1 4 0 1 5 Column zeros
2 13 1 6 0 24
subtraction with
2 1 0 2 1 3 6 0 1 2 18 lines.
is done next.
3 0 1 3 0 4 0 5 0 5 14
4 4 2 3 0 5 4 17 16 18 0
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 153

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 153

CASE SOLUTION TO ANDREW–CARTER, INC., CASE

SQUAD A B C D E This case presents some of the basic concepts of aggregate plan-
1 10 4 0 4 24 ning by the transportation method. The case involves solving a
rather complex set of transportation problems. Four different con-
2 13 1 6 0 24
figurations of operating plants have to be tested. The solutions, al-
3 6 0 1 2 18 though requiring relatively few iterations to optimality, involve
4 0 5 0 5 14 degeneracy if solved manually. The costs are:
5 4 17 16 18 0
Total Total
Optimal assignment: Variable Fixed Total
Configuration Cost Cost Cost
squad 1 to case C
squad 2 to case D All plants operating $179,730 $41,000 $220,730
squad 3 to case B 1 and 2 operating, 3 closed 188,930 33,500 222,430
squad 4 to case A 1 and 3 operating, 2 closed 183,430 34,000 217,430
squad 5 to case E 2 and 3 operating, 1 closed 188,360 33,000 221,360

Total person-days projected using this assignment ⫽ 3 ⫹ 6 ⫹ 3 ⫹

The lowest weekly total cost, operating plants 1 and 3 with 2
8 ⫹ 8 ⫽ 28 days.
closed, is $217,430. This is $3,300 per week ($171,600 per year)
10-45. Assignment Rating or 1.5% less than the next most economical solution, operating all
C53 at plant 1 10 cents
three plants. Closing a plant without expanding the capacity of the
C81 at plant 3 4 cents remaining plants means unemployment. The optimum solution,
D5 at plant 4 30 cents using plants 1 and 3, indicates overtime production of 4,000 units
D44 at plant 2 14 cents at plant 1 and 0 overtime at plant 3. The all-plant optima have no
Total manufacturing cost 58 cents use of overtime and include substantial idle regular time capacity:
11,000 units (55%) in plant 2 and either 5,000 units in plant 1
(19% of capacity) or 5,000 in plant 3 (20% of capacity). The idled
10-46. The major difference between the MODI and stepping-
capacity versus unemployment question is an interesting, non-
stone methods is in the procedure used to test for optimality. In the
quantitative aspect of the case and could lead to a discussion of the
stepping-stone method, we first draw a closed path for each of the
forecasts for the housing market and thus the plant’s product.
empty squares to calculate its improvement index. Then, the most
The optimum producing and shipping pattern is
favorable square (i.e., the one with the largest negative index) is
identified. In MODI, however, we first identify the most favorable From To (Amount)
square (by using row and column numbers) and then draw a closed
Plant 1 (R.T.) W2 (13,000); W4 (14,000)
path (only for that path) to direct us in improving the solution.
Plant 3 (R.T.) W1 (5,000); W3 (11,000);
10-47. A “northeast corner” rule would be directly analogous W4 (1,000); W5 (8,000)
to the northwest corner rule, but it would simply begin in the Plant 3 (O.T.) W1 (4,000)
upper right-hand corner instead of the upper left-hand corner. We
see in the table that this initial solution is degenerate because only There are three alternative optimal producing and shipping pat-
four squares (instead of the expected five) are occupied. The de- terns, where R.T. ⫽ regular time, O.T. ⫽ overtime, and W ⫽
generacy condition, by the way, is just a peculiarity of the Execu- warehouse.
tive Furniture Corporation data. Getting the solution manually should not be attempted using
the northwest corner rule. It will take eight tableaux to do the “all
TO Albu- Factory plants” configuration, with degeneracy appearing in the seventh
FROM querque Boston Cleveland Capacity tableau; the “1 and 2” configuration takes five tableaux; and so on.
5 4 3 It is strongly suggested that software be used.
Des Moines 100 100
8 4 3 SOLUTION TO OLD OREGON WOOD STORE CASE
Evansville 200 100 300 1. The assignment algorithm can be utilized to yield the fastest
Fort 9 7 5 time to complete a table with each person assigned one task.
Lauderdale 300 300
Warehouse Time
Requirements 300 200 200 700 Person Job (Minutes)
Tom Preparation 100
Cathy Assembly 70
George Finishing 60
Leon Packaging 210
Total time 240
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 154

154 CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS

2. If Randy is used, the assignment problem becomes unbal- INTERNET CASE STUDY
anced and a dummy job must be added. The optimum assignment
Northwest General Hospital
would be
Optimal Solution
Time
Person Job (Minutes) Source Destination Number of Trays

George Preparation 80 From: Station 5A To: Wing 5 60

Tom Assembly 60 5A 6 80
Leon Finishing 80 5A 3 60
Randy Packaging 210 3G 1 80
Total time 230 3G 3 90
3G 4 55
1S 4 155
This is a savings of 10 minutes with Cathy becoming the backup.
1S 2 120
3. If Cathy is given the preparation task, the solution of the as-
signment with the remaining three workers assigned to the remain- Optimal Cost: 4,825 minutes
ing three tasks is
SOLUTION TO CUSTOM VANS, INC. CASE
Time
To determine whether the shipping pattern can be improved and
Person Job (Minutes)
where the two new plants should be located, the total costs for the
Cathy Preparation 120 entire transportation system for each combination of plants, as
Tom Assembly 60 well as the existing shipping pattern costs, will have to be deter-
George Finishing 60 mined. In the headings identifying the combination being dis-
Leon Packaging 210
cussed, Gary and Fort Wayne will be omitted since they appear in
Total time 250
every possible combination.
Total costs and optimal solutions for each combination are
If Cathy is assigned to the finishing task, the optimum assign-
given on succeeding pages. A summary of the total costs and the
ment is
respective systems is listed below:
Time Detroit–Madison ⫽ $10,200
Person Job (Minutes) Madison–Rockford ⫽ $10,550
Detroit–Rockford ⫽ $11,400
George Preparation 80
Tom Assembly 60 Since the total cost is lowest in the Gary–Fort Wayne–
Cathy Finishing 100 Detroit–Madison combination ($10,200), the new plants should be
Leon Packaging 210 located in Detroit and Madison. This system is also an improve-
Total time 250 ment over the existing pattern, which costs $9,000, on a cost-per-
unit basis.
4. One possibility would be to combine the packaging operation Status quo: $9,000/450 units ⫽ $20/unit
with finishing. Then, George could build an entire table by himself Proposed: $10,200/750 units ⫽ $13.60/unit
(in 230 minutes) and Tom could do preparation (100 minutes),
Randy the assembly (80 minutes), and Leon the finishing and Thus the two new plants would definitely be advantageous,
packaging (90 minutes). This crew could build 4.8 tables in a 480- both in satisfying demand and in minimizing transportation costs.
minute workday, while George himself could build 2.09 tables—a
total of almost 7 tables per day.
To utilize all five workers, George and Tom could each build
entire tables, 2.09 and 1.75 per day, respectively. Letting Randy
do preparation (110 minutes), Cathy the assembly (70 minutes),
and Leon the finishing and packaging (90 minutes) allows an addi-
tional 4.36 tables per day for a total of 8.2 per day.
Nine tables per day could be achieved by having Tom pre-
pare and assemble 3 tables, George prepare and finish 3 tables,
Cathy assemble 6 tables, Leon finish 6 tables, and Randy prepare
3 tables and package all 9. George, Cathy, and Randy would each
have 60 minutes per day unutilized and could build 0.6 table hav-
ing George do preparation (80 minutes), Cathy assembly and
packaging (95 minutes), and Randy the finishing (100 minutes).
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 155

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 155

The optimal solution is:

10 20 40 15
SHOP
PLANT Chicago Milwaukee Minneapolis Detroit Capacity
Gary 300 X X X 300
Fort Wayne X X X 150 150
Dummy X 100 150 50 300
750
Demand 300 100 150 200
750

The total cost is 300($10) ⫹ 100($0) ⫹ 150($0) ⫹ 150($15) ⫹

50($0) ⫽ $5,250. This is also the optimal solution with no addi-
tional plants. The cost of the existing shipping pattern is $9,000
and is shown below. Thus the existing shipping pattern can be
improved.

Existing Shipping Pattern

SHOP
PLANT Chicago Milwaukee Minneapolis Detroit Capacity Ri
10 20 40 25
Gary 200 100 300
20 30 50 15
Fort Wayne 50 100 150
0 0 0 0
Dummy 100 50 50 100 300
Demand 300 100 150 200 750
Kj

Total costs ⫽ 200(10) ⫹ 50(30) ⫹ 100(40) ⫹ 100(15)

⫽ $9,000

The costs for the additional plants are shown below.

Cost Table for Custom Vans, Inc.

SHOP
PLANT Chicago Milwaukee Minneapolis Detroit Capacity
Gary 10 20 40 25 300
Existing
Fort Wayne 20 30 50 15 150

Detroit* 26 36 56 1 150
Proposed Madison** 7 2 22 37 150
Rockford 5 10 30 35 150
Forecast Demand 300 100 150 200

*Since a plant at Detroit could purchase a gallon of fiberglass for $2 less than any other plant, and one Shower-Rific takes 2 gallons
of fiberglass, a systems approach to transportation warrants that $2(2), $4, be deducted from each price quoted in the case for ship-
ments from Detroit.
**Since a plant at Madison could hire labor for $1 less per hour than the other plants, and one Shower-Rific takes 3 labor hours to
build, $1(3) or $3 should be deducted from each price quoted for shipments from Madison.
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 156

156 CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS

Detroit–Madison, Iteration 1 (Vogel’s Approximation Method)

SHOP
PLANT Chicago Milwaukee Minneapolis Detroit Capacity Ri
10 20 40 25
Gary 200 100 300 0 (10)
20 30 50 15 (5)
Fort Wayne 100 50 150 10 (10)
26 36 56 1
Detroit 150 150 ⫺4 (25)
7 2 22 37 (5)
Madison 100 50 150 ⫺18 15
Demand 300 100 150 200 750
Kj 10 20 40 5

(3) (18) (13) (14)

10 10

Improvement indices (MODI method): All solutions are positive; solution is optimal as shown:
G to Milw: 20 ⫺ 20 ⫺ 0 ⫽ 0 G to C: 200 units
G to D: 25 ⫺ 5 ⫺ 0 ⫽ ⫹20 G to Minn: 100 units
FW to Milw: 30 ⫺ 20 ⫺ 10 ⫽ 0 FW to C: 100 units
FW to Minn: 50 ⫺ 40 ⫺ 10 ⫽ 0 FW to D: 50 units
D to C: 26 ⫺ 10 ⫺ (⫺4) ⫽ ⫹20 D to D: 150 units
D to Milw: 36 ⫺ 20 ⫺ (⫺4) ⫽ ⫹20 M to Milw: 100 units
D to Minn: 56 ⫺ 40 ⫺ (⫺4) ⫽ ⫹20 M to Minn: 50 units
M to C: 7 ⫺ 10 ⫺ (⫺18) ⫽ ⫹15 Total cost ⫽ 200(10) ⫹ 100(20) ⫹ 100(2) ⫹ 100(40)
M to D: 37 ⫺ 5 ⫺ (⫺18) ⫽ ⫹50 ⫹ 50(22) ⫹ 50(15) ⫹ 150(1) ⫽ $10,200

Madison–Rockford, Iteration 1 (Vogel’s Approximation Method)

SHOP
PLANT Chicago Milwaukee Minneapolis Detroit Capacity Ri
10 20 40 25
Gary 250 50 300 0 (10)
20 30 50 15
Fort Wayne 150 150 ⫺10 (5)
7 2 22 37 (5)
Madison 50 100 0* 150 ⫺3 (15)
5 10 30 35
Rockford 150 150 5 (1)
Demand 300 100 150 200 750
Kj 10 5 25 25

(2) (8) (8) (10)

(10)
*0 supplied to avoid degeneracy.

Improvement indices (MODI method): M to D: 37 ⫺ 25 ⫺ (⫺3) ⫽ ⫹15

G to Milw: 20 ⫺ 5 ⫺ 0 ⫽ ⫹15 R to C: 5 ⫺ 10 ⫺ 5 ⫽ ⫺10 冑 best improvement
G to Minn: 40 ⫺ 25 ⫺ 0 ⫽ ⫹15 (see iteration 2)
FW to Milw: 30 ⫺ 5 ⫺ (⫺10) ⫽ ⫹35 R to Minn: 10 ⫺ 5 ⫺ 5 ⫽ 0
FW to C: 20 ⫺ 10 ⫺ (⫺10) ⫽ ⫹20 R to D: 35 ⫺ 25 ⫺ 5 ⫽ ⫹5
FW to Minn: 50 ⫺ 25 ⫺ (⫺10) ⫽ ⫹35
 REVISED
M10_REND6289_10_IM_C10.QXD 5/12/08 11:26 AM Page 157

CHAPTER 10 TRANSPORTATION AND ASSIGNMENT MODELS 157

Madison–Rockford, Iteration 2
10 15 35 25
SHOP
PLANT Chicago Milwaukee Minneapolis Detroit Capacity Ri
10 20 40 25
0 Gary 250 50 300 0
20 30 50 15
⫺10 Fort Wayne 150 150 ⫺10
7 2 22 37
⫺13 Madison 100 50 150 ⫺13
5 10 30 35
⫺5 Rockford 50 100 150 ⫺5
Demand 300 100 150 200 750
Kj 10 15 35 25

Improvement indices (MODI method): Optimal solution:

G to Milw: 20 ⫺ 15 ⫺ 0 ⫽ ⫹5 G to C: 250 units
G to Minn: 40 ⫺ 35 ⫺ 0 ⫽ ⫹5 G to D: 50 units
FW to C: 20 ⫺ 10 ⫺ (⫺10) ⫽ ⫹20 FW to D: 150 units
FW to Milw: 30 ⫺ 15 ⫺ (⫺10) ⫽ ⫹25 M to Milw: 100 units
FW to Minn: 50 ⫺ 35 ⫺ (⫺10) ⫽ ⫹25 M to Minn: 50 units
M to C: 7 ⫺ 10 ⫺ (⫺13) ⫽ ⫹10 R to C: 50 units
M to D: 37 ⫺ 25 ⫺ (⫺13) ⫽ ⫹25 R to Minn: 100 units
R to Milw: 10 ⫺ 15 ⫺ (⫺5) ⫽ 0 Total cost ⫽ 250(10) ⫹ 50(5) ⫹ 100(2) ⫹ 50(22) ⫹ 100(30) ⫹
R to D: 35 ⫺ 25 ⫺ (⫺5) ⫽ ⫹15 50(25) ⫹ 150(15)
⫽ $10,550

Detroit–Rockford (Vogel’s Approximation Method)

10 30 40 5
SHOP
PLANT Chicago Milwaukee Minneapolis Detroit Capacity Ri
10 20 40 25 (10)
0 Gary 200 100 300 0 (30)
20 30 50 15 (5)
10 Fort Wayne 100 50 150 10 (10)
26 36 56 1
⫺4 Detroit 150 150 ⫺4 (25)
5 10 30 35
⫺10 Rockford 0* 150 150 ⫺10 (5)
Demand 300 100 150 200 750
Kj 10 20 40 5

(5) (10) (10) (14)

(15) (10)
*0 supplied to avoid degeneracy.

Improvement indices (MODI method) for Detroit-Rockford: Optimal solution:

G to Minn: 40 ⫺ 40 ⫺ 0 ⫽ 0 G to C: 200 units
G to D: 25 ⫺ 5 ⫺ 0 ⫽ ⫹20 G to Milw: 100 units
FW to Milw: 30 ⫺ 20 ⫺ 10 ⫽ 0 FW to C: 100 units
FW to Minn: 50 ⫺ 40 ⫺ 10 ⫽ 0 D to D: 150 units
D to C: 26 ⫺ 10 ⫺ (⫺4) ⫽ ⫹20 FW to D: 50 units
D to Milw: 36 ⫺ 20 ⫺ (⫺4) ⫽ ⫹20 R to Minn: 150 units
D to Minn: 56 ⫺ 40 ⫺ (⫺4) ⫽ ⫹20 Total costs ⫽ 200(10) ⫹ 100(20) ⫹ 100(20) ⫹ 50(15) ⫹ 150(1)
R to C: 5 ⫺ 10 ⫺ (⫺10) ⫽ ⫹5 ⫹ 150(30)
R to D: 35 ⫺ 5 ⫺ (⫺10) ⫽ ⫹40
⫽ $11,400