Page 322 -

302 CHAPTER 7 TRANSPORTATION, ASSIGNMENT AND TRANSSHIPMENT PROBLEMS

Step 7. Choose as the outgoing cell the minus-sign cell on the stepping-stone path
with the smallest flow. If there is a tie, choose any one of the tied cells.
The tied cells that are not chosen will be artificially occupied with a flow of
zero at the next iteration.
Step 8. Allocate to the incoming cell the amount of flow currently given to the out
going cell; make the appropriate adjustments to all cells on the stepping-
stone path, and continue with step 2.

Problem Variations
The following problem variations can be handled, with slight adaptations, by the
transportation Simplex method:
1 total supply not equal to total demand;
2 maximization objective function;
3 unacceptable routes.
The case where the total supply is not equal to the total demand can be handled
easily by the transportation Simplex method if we first introduce a dummy origin or
a dummy destination. If total supply is greater than total demand, we introduce a
dummy destination with demand equal to the excess of supply over demand.
Similarly, if total demand is greater than total supply, we introduce a dummy origin
with supply equal to the excess of demand over supply. In either case, the use of a
dummy destination or a dummy origin will equalize total supply and total demand so
that we can use the transportation Simplex method. When a dummy destination or
origin is present, we assign cost coefficients of zero to every arc into a dummy
destination and to every arc out of a dummy origin. The reason is that no shipments
will actually be made from a dummy origin or to a dummy destination when the
solution is implemented and thus a zero cost per unit is appropriate.
The transportation Simplex method can also be used to solve maximization
problems. The only modification necessary involves the selection of an incoming
cell. Instead of picking the cell with the smallest or most negative e ij value, we pick
that cell for which e ij is largest. That is, we pick the cell that will cause the largest
increase per unit in the objective function. If e ij 0 for all unoccupied cells, we stop;
the maximization solution has been reached.
To handle unacceptable routes in a minimization problem, infeasible arcs must
carry an extremely high cost, denoted M, to keep them out of the solution. Thus, if
we have a route (arc) from an origin to a destination that for some reason cannot be
used, we simply assign this arc a cost per unit of M, and it will not enter the solution.
Unacceptable arcs would be assigned a profit per unit of M in a maximization
problem.

NOTES AND COMMENTS

1 Research devoted to developing efficient special- simple extension of this method also can be used
purpose solution procedures for network to solve transshipment problems.
problems has shown that the transportation 2 As we previously noted, each cell in the
Simplex method is one of the best. It is used in transportation tableau corresponds to an arc
the transportation and assignment modules of (route) in the network model of the problem and a
The Management Scientist software package. A variable in the linear programming formulation.

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.