Page 321 -

TRANSPORTATION SIMPLEX METHOD: A SPECIAL-PURPOSE SOLUTION PROCEDURE 301

Table 7.21 Optimal Solution to a Problem with a Degenerate Initial Feasible
Solution

v j
u i 3 6 7 Supply
3 6 7
0 5 25 30 60

8 5 7
–1 6 30 1 30

4 9 11
1 30 2 3 30

Demand 35 55 30

programming that takes advantage of the special mathematical structure of the
transportation problem; but because of the special structure, the transportation
Simplex method is hundreds of times faster than the general Simplex method.
Try part (b) of Problem To apply the transportation Simplex method, you must have a transportation
15 for practise using the problem with total supply equal to total demand; so, for some problems you may
transportation simplex
method. need to add a dummy origin or dummy destination to put the problem in this form.
The transportation Simplex method takes the problem in this form and applies a
two-phase solution procedure. In phase I, apply the minimum cost method to find
an initial feasible solution. In phase II, begin with the initial feasible solution and
iterate until you reach an optimal solution. The steps of the transportation Simplex
method for a minimization problem are summarized as follows.

Phase I Find an initial feasible solution using the minimum cost method.

Phase II
Step 1. If the initial feasible solution is degenerate with less than m + n 1
occupied cells, add an artificially occupied cell or cells so that m + n 1
occupied cells exist in locations that enable use of the MODI method.
Step 2. Use the MODI method to calculate row indexes, u i , and column
indexes, v j .
Step 3. Calculate the net evaluation index e ij ¼ c ij u i v j for each
unoccupied cell.
Step 4. If e ij 0 for all unoccupied cells, stop; you have reached the minimum
cost solution. Otherwise, proceed to step 5.
Step 5. Identify the unoccupied cell with the smallest (most negative) net
evaluation index and select it as the incoming cell.
Step 6. Find the stepping-stone path associated with the incoming cell. Label each
cell on the stepping-stone path whose flow will increase with a plus sign
and each cell whose flow will decrease with a minus sign.

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.