Page 305 -

TRANSPORTATION PROBLEM: A NETWORK MODEL AND A LINEAR PROGRAMMING FORMULATION 285

Whenever total supply is programming model will have a feasible solution. A zero cost per unit is assigned to
less than total demand, each arc leaving the dummy origin so that the value of the optimal solution for the
the model does not
determine how the revised problem will represent the shipping cost for the units actually shipped (no
unsatisfied demand is shipments actually will be made from the dummy origin). When the optimal
handled (e.g., solution is implemented, the destinations showing shipments being received from
backorders). The
manager must handle the dummy origin will be the destinations experiencing a shortfall or unsatisfied
this aspect of the demand.
problem.

Try Problem 7 to test Maximization Objective Function In some transportation problems, the objective
your ability to handle a is to find a solution that maximizes profit or revenue. Using the values for profit or
case where demand is
greater than supply with revenue per unit as coefficients in the objective function, we simply solve a
a maximization objective. maximization rather than a minimization linear programme. This change does not
affect the constraints.

Route Capacities and/or Route Minimums The linear programming formulation
of the transportation problem can also accommodate capacities and/or minimum
quantities for one or more of the routes. For example, suppose that in the Foster
Electronics problem the China–Boston route (origin 3 to destination 1) had a
capacity of 1000 units because of limited space availability on its normal mode of
transportation. With x 31 denoting the amount shipped from China to Boston, the
route capacity constraint for the China–Boston route would be:

x 31 1000
Similarly, route minimums can be specified. For example,
x 22 2000

would guarantee that a previously committed order for a Brazil–Dubai delivery of at
least 2000 units would be maintained in the optimal solution.

Unacceptable Routes Finally, establishing a route from every origin to every
destination may not be possible. This may happen, for example, because of safety or
security concerns or because of physical barriers preventing certain routes from being
used. To handle this situation, we simply drop the corresponding arc from the network
and remove the corresponding variable from the linear programming formulation. For
example, if the Czech Republic–Singapore route were unacceptable or unusable, the
arc from Czech Republic to Singapore could be dropped in Figure 7.1, and x 13 could be
removed from the linear programming formulation. Solving the resulting 11-variable,
seven-constraint model would provide the optimal solution while guaranteeing that the
Czech Republic–Singapore route is not used.

A General Linear Programming Model of the Transportation Problem
To show the general linear programming model of the transportation problem, we
1950 saw the first use the notation:
computer solution of a
transportation problem. i ¼ index for origins; i ¼ 1; 2; .. . ; m
j ¼ index for destinations; j ¼ 1; 2; ... ; n
x ij ¼ number of units shipped from origin i to destination j
c ij ¼ cost per unit of shipping from origin i to destination j
s i ¼ supply or capacity in units at origin i
d j ¼ demand in units at destination j

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.