Page 306 -

286 CHAPTER 7 TRANSPORTATION, ASSIGNMENT AND TRANSSHIPMENT PROBLEMS

The general linear programming model of the m-origin, n-destination transportation
problem is:
X X
m
n
Min c ij x ij
i¼1 j¼1
s:t:
X
n
i ¼ 1; 2; ... ; m Supply
x ij s i
j¼1
m
X
x ij ¼ d j j ¼ 1; 2; .. . ; n Demand
i¼1
x ij 0 for all i and j
As mentioned previously, we can add constraints of the form x ij L ij if the route
from origin i to destination j has capacity L ij . A transportation problem that includes
constraints of this type is called a capacitated transportation problem. Similarly, we
can add route minimum constraints of the form x ij M ij if the route from origin i to
destination j must handle at least M ij units.

NOTES AND COMMENTS

1 Transportation problems encountered in practice constraint to the formulation that sets the variable
usually lead to large linear programmes. you want to remove equal to zero.
Transportation problems with 100 origins and 100 3 The optimal solution to a transportation model will
destinations are not unusual. Such a problem consist of integer values for the decision variables
would involve (100)(100) ¼ 10 000 variables. as long as all supply and demand values are
2 To handle a situation in which some routes may integers. The reason is the special mathematical
be unacceptable, we stated that you could drop structure of the linear programming model. Each
the corresponding arc from the network and variable appears in exactly one supply and one
remove the corresponding variable from the demand constraint, and all coefficients in the
linear programming formulation. Another constraint equations are 1s and 0s.
approach often used is to assign an extremely 4 Although many transportation problems involve
large objective function cost coefficient to any minimizing the cost of transporting goods
unacceptable arc. If the problem has already between locations, many other applications of the
been formulated, another option is to add a transportation model exist.

Transportation Simplex Method: A Special-Purpose Solution
7.2
Procedure

Solving transportation problems with a general-purpose linear programming code is
fine for small to medium-sized problems. However, these problems often grow very
large (a problem with 100 origins and 1000 destinations would have 100 000 varia-
bles), and more efficient solution procedures may be needed. The network structure
of the transportation problem has enabled management scientists to develop special-
purpose solution procedures that greatly simplify the calculations.

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.