Summary Report of Attached Pages
Please read homework 4 assignment, and write a summary for numbers 1-7. Ask me questions please
IE413
♣ ♣ ♣ ♣ ♣ ♣ ♣♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣
Homework #4
♣ ♣ ♣ ♣ ♣ ♣♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣
1. Read Chapter 6.1 (The Essence of Duality Theory) of the attached, and write a one-page
summary report (1 point).
2. Read Chapter 6.2 (Economic Interpretation of Duality) of the attached, and write a one-
page summary report (1 point).
3. Read Chapter 6.3 (Primal-Dual Relationships) of the attached, and write a one-page
summary report (1 point).
4. Read Chapter 6.4 (Adapting to Other Primal Forms) of the attached, and write a one-
page summary report (1 point).
5. Read Chapter 9.1 (The Transportation Problem) or Chapter 8.1 of the attached, and write
a one-page summary report (2 points).
6. Read Chapter 9.3 (The Assignment Problem) or Chapter 8.3 of the attached, and write a
one-page summary report (2 points).
7. Read Chapter 9.4 (A Special Algorithm for the Assignment Problem) or Chapter 8.4 of
the attached, and write a one-page summary report (2 points).
Instructions for homework submission:
You have to submit a scanned copy of your work (or a word document file) through
the class Canvas system. Do not email me your work!
The summary report should be prepared on a word processor (e.g., MS Word). Be
concise in your writing and consult technical writing references as needed. The body
of the summary report should include the sections outlined as follows:
a. Summary of the Chapters’ main points
b. Your opinion of the Chapters including the most important information you learned.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Editio
n
6. Duality Theory and
Sensitivity Analysis
Text 203© The McGraw−Hill
Companies, 201
0
195
6C H A P T E R
Duality Theory and
Sensitivity Analysis
One of the most important discoveries in the early development of linear programmingwas the concept of duality and its many important ramifications. This discovery re-
vealed that every linear programming problem has associated with it another linear pro-
gramming problem called the dual. The relationships between the dual problem and th
e
original problem (called the primal) prove to be extremely useful in a variety of ways.
For example, you soon will see that the shadow prices described in Sec. 4.7 actually are
provided by the optimal solution for the dual problem. We shall describe many other valu-
able applications of duality theory in this chapter as well.
One of the key uses of duality theory lies in the interpretation and implementation of
sensitivity analysis. As we already mentioned in Secs. 2.3, 3.3, and 4.7, sensitivity analy-
sis is a very important part of almost every linear programming study. Because most of
the parameter values used in the original model are just estimates of future conditions,
the effect on the optimal solution if other conditions prevail instead needs to be investi-
gated. Furthermore, certain parameter values (such as resource amounts) may represent
managerial decisions, in which case the choice of the parameter values may be the main
issue to be studied, which can be done through sensitivity analysis.
For greater clarity, the first three sections discuss duality theory under the assump-
tion that the primal linear programming problem is in our standard form (but with no re-
striction that the bi values need to be positive). Other forms are then discussed in Sec. 6.4.
We begin the chapter by introducing the essence of duality theory and its applications.
We then describe the economic interpretation of the dual problem (Sec. 6.2) and delve
deeper into the relationships between the primal and dual problems (Sec. 6.3). Section 6.5
focuses on the role of duality theory in sensitivity analysis. The basic procedure for sen-
sitivity analysis (which is based on the fundamental insight of Sec. 5.3) is summarized in
Sec. 6.6 and illustrated in Sec. 6.7. Section 6.8 focuses on how to use spreadsheets to per-
form sensitivity analysis in a straightforward way. (If you don’t have much time to de-
vote to this chapter, it is feasible to read only Sec. 6.8 by itself to obtain a relatively brief
introduction to sensitivity analysis.)
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text204 © The McGraw−Hill
Companies, 2010
Thus, with the primal problem in maximization form, the dual problem is in minimization
form instead. Furthermore, the dual problem uses exactly the same parameters as the pri-
mal problem, but in different locations, as summarized below.
1. The coefficients in the objective function of the primal problem are the right-hand sides
of the functional constraints in the dual problem.
2. The right-hand sides of the functional constraints in the primal problem are the coef-
ficients in the objective function of the dual problem.
3. The coefficients of a variable in the functional constraints of the primal problem are
the coefficients in a functional constraint of the dual problem.
To highlight the comparison, now look at these same two problems in matrix notation (as
introduced at the beginning of Sec. 5.2), where c and y � [y1, y2, . . . , ym] are row vec-
tors but b and x are column vectors.
Primal Problem Dual Proble
m
196 CHAPTER 6 DUALITY THEORY AND SENSITIVITY ANALYSIS
Maximize Z �
�
n
j�
1
cjxj,
subject to
�
n
j�1
aijxj � bi, for i � 1, 2, . . . , m
and
xj � 0, for j � 1, 2, . . . , n.
Minimize W �
�
m
i�1
bi yi,
subject to
�
m
i�1
aij yi � cj, for j � 1, 2, . . . , n
and
yi � 0, for i � 1, 2, . . . , m.
Maximize Z � cx,
subject to
Ax � b
and
x � 0.
Minimize W � yb,
subject to
yA � c
and
y � 0.
Primal Problem Dual Problem
To illustrate, the primal and dual problems for the Wyndor Glass Co. example of Sec. 3.1
are shown in Table 6.1 in both algebraic and matrix form.
The primal-dual table for linear programming (Table 6.2) also helps to highlight
the correspondence between the two problems. It shows all the linear programming pa-
rameters (the aij, bi, and cj) and how they are used to construct the two problems. All the
headings for the primal problem are horizontal, whereas the headings for the dual prob-
lem are read by turning the book sideways. For the primal problem, each column (ex-
cept the Right Side column) gives the coefficients of a single variable in the respective
constraints and then in the objective function, whereas each row (except the bottom one)
gives the parameters for a single contraint. For the dual problem, each row (except the
Right Side row) gives the coefficients of a single variable in the respective constraints
and then in the objective function, whereas each column (except the rightmost one) gives
■ 6.1 THE ESSENCE OF DUALITY THEORY
Given our standard form for the primal problem at the left (perhaps after conversion from
another form), its dual problem has the form shown to the right.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text 205© The McGraw−Hill
Companies, 2010
6.1 THE ESSENCE OF DUALITY THEORY 197
■ TABLE 6.2 Primal-dual table for linear programming, illustrated by the Wyndor
Glass Co. example
(a) General Case
Primal Problem
Coefficient of:
Right
x1 x2 … xn Side
y1 a11 a12 … a1n � b1
y2 a21 a22 … a2n � b
2
� �
ym am1 am2 … amn � bm
VI VI … VI
c1 c2 … cnRi
g
h
t
S
id
e
D
u
a
l
P
ro
b
le
m
C
o
e
ff
ic
ie
n
t
o
f:
C
o
ef
fic
ie
n
ts
fo
r
O
b
je
ct
iv
e
Fu
n
ct
io
n
(M
in
im
iz
e)
Coefficients for
Objective Function
(Maximize)
(b) Wyndor Glass Co. Example
x1 x2
y1 1 0 �
4
y2 0 2 �
12
y3 3 2 �
18
VI VI
3 5
■ TABLE 6.1 Primal and dual problems for the Wyndor Glass Co. example
Maximize Z � 3×1 � 5×2,
subject to
3×1 � 2×2 � 4
3×1 � 2×2 � 12
3×1 � 2×2 � 18
and x1 � 0, x2 � 0.
Minimize W � 4y1 � 12y2 � 18y3,
subject to
y12y2 � 3y3 �
3
2y2 � 2y3 � 5
and
y1 � 0, y2 � 0, y3 � 0.
Maximize Z � [3, 5]
,
subject to
�
and
�
.
0
0
x1
x2
⎤
⎥
⎥
⎦
4
12
18
⎡
⎢
⎢
⎣
x1
x2
⎤
⎥
⎥
⎦
0
2
2
1
0
3
⎡
⎢
⎢
⎣
x1
x2 Minimize W � [y1, y2, y3]
subject to
[y1, y2, y3] � [3, 5]
and
[y1, y2, y3] � [0, 0, 0].
⎤
⎥
⎥
⎦
0
2
2
1
0
3
⎡
⎢
⎢
⎣
⎤
⎥
⎥
⎦
4
12
18
⎡
⎢
⎢
⎣
Primal Problem Dual Problem
in Algebraic Form in Algebraic Form
Primal Problem Dual Problem
in Matrix Form in Matrix Form
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text206 © The McGraw−Hill
Companies, 2010
the parameters for a single constraint. In addition, the Right Side column gives the right-
hand sides for the primal problem and the objective function coefficients for the dual
problem, whereas the bottom row gives the objective function coefficients for the primal
problem and the right-hand sides for the dual problem.
Consequently, we now have the following general relationships between the primal
and dual problems.
1. The parameters for a (functional) constraint in either problem are the coefficients of a
variable in the other problem.
2. The coefficients in the objective function of either problem are the right-hand sides for
the other problem.
Thus, there is a direct correspondence between these entities in the two problems, as sum-
marized in Table 6.3. These correspondences are a key to some of the applications of du-
ality theory, including sensitivity analysis.
The Worked Examples section of the book’s website provides another example of
using the primal-dual table to construct the dual problem for a linear programming model.
Origin of the Dual Problem
Duality theory is based directly on the fundamental insight (particularly with regard to
row 0) presented in Sec. 5.3. To see why, we continue to use the notation introduced in
Table 5.9 for row 0 of the final tableau, except for replacing Z* by W* and dropping the
asterisks from z* and y* when referring to any tableau. Thus, at any given iteration of the
simplex method for the primal problem, the current numbers in row 0 are denoted as
shown in the (partial) tableau given in Table 6.4. For the coefficients of x1, x2, . . . , xn,
recall that z � (z1, z2, . . . , zn) denotes the vector that the simplex method added to the
vector of initial coefficients, �c, in the process of reaching the current tableau. (Do not
confuse z with the value of the objective function Z.) Similarly, since the initial coeffi-
cients of xn�1, xn�2, . . . , xn�m in row 0 all are 0, y � ( y1, y2, . . . , ym) denotes the vec-
tor that the simplex method has added to these coefficients. Also recall [see Eq. (1) in the
statement of the fundamental insight in Sec. 5.3] that the fundamental insight led to the
following relationships between these quantities and the parameters of the original model:
W � yb � �
m
i�1
bi yi ,
z � yA, so zj � �
m
i�1
aijyi , for j � 1, 2, . . . , n.
198 CHAPTER 6 DUALITY THEORY AND SENSITIVITY ANALYSIS
■ TABLE 6.3 Correspondence between
entities in primal and
dual problems
One Problem Other Problem
Constraint i ←⎯⎯→ Variable i
Objective function ←⎯⎯→ Right-hand sides
■ TABLE 6.4 Notation for entries in row 0 of a simplex tableau
Coefficient of:
Basic Right
Iteration Variable Eq. Z x1 x2 … xn xn�1 xn�2 … xn�m Side
Any Z (0) 1 z1 � c1 z2 � c2 … zn � cn y1 y2 … ym W
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text 207© The McGraw−Hill
Companies, 2010
To illustrate these relationships with the Wyndor example, the first equation gives
W � 4y1 � 12y2 � 18y3, which is just the objective function for the dual problem shown
in the upper right-hand box of Table 6.1. The second set of equations give z1 � y1 � 3y3
and z2 � 2y2 � 2y3, which are the left-hand sides of the functional constraints for this
dual problem. Thus, by subtracting the right-hand sides of these � constraints (c1 � 3 and
c2 � 5), (z1 � c1) and (z2 � c2) can be interpreted as being the surplus variables for these
functional constraints.
The remaining key is to express what the simplex method tries to accomplish (accord-
ing to the optimality test) in terms of these symbols. Specifically, it seeks a set of basic
variables, and the corresponding BF solution, such that all coefficients in row 0 are non-
negative. It then stops with this optimal solution. Using the notation in Table 6.4, this goal
is expressed symbolically as follows:
Condition for Optimality:
zj � cj � 0 for j � 1, 2, . . . , n,
yi � 0 for i � 1, 2, . . . , m.
After we substitute the preceding expression for zj, the condition for optimality says that
the simplex method can be interpreted as seeking values for y1, y2, . . . , ym such that
6.1 THE ESSENCE OF DUALITY THEORY 199
W � �
m
i�1
biyi,
subject to
�
m
i�1
aijyi � cj, for j � 1, 2, . . . , n
and
yi � 0, for i � 1, 2, . . . , m.
But, except for lacking an objective for W, this problem is precisely the dual problem! To
complete the formulation, let us now explore what the missing objective should be.
Since W is just the current value of Z, and since the objective for the primal problem
is to maximize Z, a natural first reaction is that W should be maximized also. However,
this is not correct for the following rather subtle reason: The only feasible solutions for this
new problem are those that satisfy the condition for optimality for the primal problem.
Therefore, it is only the optimal solution for the primal problem that corresponds to a
feasible solution for this new problem. As a consequence, the optimal value of Z in the
primal problem is the minimum feasible value of W in the new problem, so W should be
minimized. (The full justification for this conclusion is provided by the relationships we de-
velop in Sec. 6.3.) Adding this objective of minimizing W gives the complete dual problem.
Consequently, the dual problem may be viewed as a restatement in linear program-
ming terms of the goal of the simplex method, namely, to reach a solution for the primal
problem that satisfies the optimality test. Before this goal has been reached, the corre-
sponding y in row 0 (coefficients of slack variables) of the current tableau must be in-
feasible for the dual problem. However, after the goal is reached, the corresponding y must
be an optimal solution (labeled y*) for the dual problem, because it is a feasible solution
that attains the minimum feasible value of W. This optimal solution ( y1*, y2*, . . . , ym*)
provides for the primal problem the shadow prices that were described in Sec. 4.7. Fur-
thermore, this optimal W is just the optimal value of Z, so the optimal objective function
values are equal for the two problems. This fact also implies that cx � yb for any x and
y that are feasible for the primal and dual problems, respectively.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text208 © The McGraw−Hill
Companies, 2010
To illustrate, the left-hand side of Table 6.5 shows row 0 for the respective itera-
tions when the simplex method is applied to the Wyndor Glass Co. example. In each
case, row 0 is partitioned into three parts: the coefficients of the decision variables (x1, x2),
the coefficients of the slack variables (x3, x4, x5), and the right-hand side (value of Z ). Since
the coefficients of the slack variables give the corresponding values of the dual variables
( y1, y2, y3), each row 0 identifies a corresponding solution for the dual problem, as shown
in the y1, y2, and y3 columns of Table 6.5. To interpret the next two columns, recall that
(z1 � c1) and (z2 � c2) are the surplus variables for the functional constraints in the dual
problem, so the full dual problem after augmenting with these surplus variables is
Minimize W � 4y1 � 12y2 � 18y3,
subject to
y1 � 3y3 � (z1 � c1) � 3
2y2 � 2y3 � (z2 � c2) � 5
and
y1 � 0, y2 � 0, y3 � 0.
Therefore, by using the numbers in the y1, y2, and y3 columns, the values of these surplus
variables can be calculated as
z1 � c1 � y1 � 3y3 � 3,
z2 � c2 � 2y2 � 2y3 � 5.
Thus, a negative value for either surplus variable indicates that the corresponding con-
straint is violated. Also included in the rightmost column of the table is the calculated
value of the dual objective function W � 4y1 � 12y2 � 18y3.
As displayed in Table 6.4, all these quantities to the right of row 0 in Table 6.5 al-
ready are identified by row 0 without requiring any new calculations. In particular, note
in Table 6.5 how each number obtained for the dual problem already appears in row 0 in
the spot indicated by Table 6.4.
For the initial row 0, Table 6.5 shows that the corresponding dual solution
(y1, y2, y3) � (0, 0, 0) is infeasible because both surplus variables are negative. The first it-
eration succeeds in eliminating one of these negative values, but not the other. After two it-
erations, the optimality test is satisfied for the primal problem because all the dual variables
and surplus variables are nonnegative. This dual solution (y1*, y2*, y3*) � (0, �
3
2
�, 1) is optimal
(as could be verified by applying the simplex method directly to the dual problem), so the
optimal value of Z and W is Z * � 36 � W *.
200 CHAPTER 6 DUALITY THEORY AND SENSITIVITY ANALYSIS
■ TABLE 6.5 Row 0 and corresponding dual solution for each iteration
for the Wyndor Glass Co. example
Primal Problem Dual Problem
Iteration Row 0 y1 y2 y3 z1 � c1 z2 � c2 W
0 [�3, �5 0, 0, 0 0] 0 0 0 �3 �5 0
1 [�3, �0 0, �
5
2
�, 0 30] 0 �
5
2
� 0 �3 �0 30
2 [�0, �0 0,
�
3
2
�, 1 36] 0 �
3
2
� 1 �0 �0 36
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text 209© The McGraw−Hill
Companies, 2010
Summary of Primal-Dual Relationships
Now let us summarize the newly discovered key relationships between the primal and dual
problems.
Weak duality property: If x is a feasible solution for the primal problem and y
is a feasible solution for the dual problem, then
cx � yb.
For example, for the Wyndor Glass Co. problem, one feasible solution is x1 � 3, x2 � 3,
which yields Z � cx � 24, and one feasible solution for the dual problem is y1 � 1,
y2 � 1, y3 � 2, which yields a larger objective function value W � yb � 52. These are just
sample feasible solutions for the two problems. For any such pair of feasible solutions, this
inequality must hold because the maximum feasible value of Z � cx (36) equals the min-
imum feasible value of the dual objective function W � yb, which is our next property.
Strong duality property: If x* is an optimal solution for the primal problem
and y* is an optimal solution for the dual problem, then
cx* � y*b.
Thus, these two properties imply that cx
yb for feasible solutions if one or both of them
are not optimal for their respective problems, whereas equality holds when both are optimal.
The weak duality property describes the relationship between any pair of solutions
for the primal and dual problems where both solutions are feasible for their respective
problems. At each iteration, the simplex method finds a specific pair of solutions for the
two problems, where the primal solution is feasible but the dual solution is not feasible
(except at the final iteration). Our next property describes this situation and the relation-
ship between this pair of solutions.
Complementary solutions property: At each iteration, the simplex method si-
multaneously identifies a CPF solution x for the primal problem and a comple-
mentary solution y for the dual problem (found in row 0, the coefficients of the
slack variables), where
cx � yb.
If x is not optimal for the primal problem, then y is not feasible for the dual
problem.
To illustrate, after one iteration for the Wyndor Glass Co. problem, x1 � 0, x2 � 6, and
y1 � 0, y2 � �
5
2
�, y3 � 0, with cx � 30 � yb. This x is feasible for the primal problem, but
this y is not feasible for the dual problem (since it violates the constraint, y1 � 3y3 � 3).
The complementary solutions property also holds at the final iteration of the simplex
method, where an optimal solution is found for the primal problem. However, more can
be said about the complementary solution y in this case, as presented in the next property.
Complementary optimal solutions property: At the final iteration, the simplex
method simultaneously identifies an optimal solution x* for the primal problem
and a complementary optimal solution y* for the dual problem (found in row
0, the coefficients of the slack variables), where
cx* � y*b.
The yi* are the shadow prices for the primal problem.
For the example, the final iteration yields x1* � 2, x2* � 6, and y1* � 0, y2* � �
3
2
�, y3* � 1,
with cx* � 36 � y*b.
6.1 THE ESSENCE OF DUALITY THEORY 201
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text210 © The McGraw−Hill
Companies, 2010
We shall take a closer look at some of these properties in Sec. 6.3. There you will see
that the complementary solutions property can be extended considerably further. In partic-
ular, after slack and surplus variables are introduced to augment the respective problems,
every basic solution in the primal problem has a complementary basic solution in the dual
problem. We already have noted that the simplex method identifies the values of the sur-
plus variables for the dual problem as zj � cj in Table 6.4. This result then leads to an ad-
ditional complementary slackness property that relates the basic variables in one problem
to the nonbasic variables in the other (Tables 6.7 and 6.8), but more about that later.
In Sec. 6.4, after describing how to construct the dual problem when the primal prob-
lem is not in our standard form, we discuss another very useful property, which is sum-
marized as follows:
Symmetry property: For any primal problem and its dual problem, all relation-
ships between them must be symmetric because the dual of this dual problem is
this primal problem.
Therefore, all the preceding properties hold regardless of which of the two problems is
labeled as the primal problem. (The direction of the inequality for the weak duality prop-
erty does require that the primal problem be expressed or reexpressed in maximization
form and the dual problem in minimization form.) Consequently, the simplex method can
be applied to either problem, and it simultaneously will identify complementary solutions
(ultimately a complementary optimal solution) for the other problem.
So far, we have focused on the relationships between feasible or optimal solutions in
the primal problem and corresponding solutions in the dual problem. However, it is pos-
sible that the primal (or dual) problem either has no feasible solutions or has feasible so-
lutions but no optimal solution (because the objective function is unbounded). Our final
property summarizes the primal-dual relationships under all these possibilities.
Duality theorem: The following are the only possible relationships between the
primal and dual problems.
1. If one problem has feasible solutions and a bounded objective function (and
so has an optimal solution), then so does the other problem, so both the weak
and strong duality properties are applicable.
2. If one problem has feasible solutions and an unbounded objective function
(and so no optimal solution), then the other problem has no feasible solutions.
3. If one problem has no feasible solutions, then the other problem has either no
feasible solutions or an unbounded objective function.
Applications
As we have just implied, one important application of duality theory is that the dual prob-
lem can be solved directly by the simplex method in order to identify an optimal solution
for the primal problem. We discussed in Sec. 4.8 that the number of functional constraints
affects the computational effort of the simplex method far more than the number of vari-
ables does. If m � n, so that the dual problem has fewer functional constraints (n) than
the primal problem (m), then applying the simplex method directly to the dual problem
instead of the primal problem probably will achieve a substantial reduction in computa-
tional effort.
The weak and strong duality properties describe key relationships between the primal
and dual problems. One useful application is for evaluating a proposed solution for the pri-
mal problem. For example, suppose that x is a feasible solution that has been proposed for
implementation and that a feasible solution y has been found by inspection for the dual
202 CHAPTER 6 DUALITY THEORY AND SENSITIVITY ANALYSIS
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text 211© The McGraw−Hill
Companies, 2010
problem such that cx � yb. In this case, x must be optimal without the simplex method
even being applied! Even if cx
yb, then yb still provides an upper bound on the optimal
value of Z, so if yb � cx is small, intangible factors favoring x may lead to its selection
without further ado.
One of the key applications of the complementary solutions property is its use in
the dual simplex method presented in Sec. 7.1. This algorithm operates on the primal
problem exactly as if the simplex method were being applied simultaneously to the dual
problem, which can be done because of this property. Because the roles of row 0 and
the right side in the simplex tableau have been reversed, the dual simplex method re-
quires that row 0 begin and remain nonnegative while the right side begins with some
negative values (subsequent iterations strive to reach a nonnegative right side). Conse-
quently, this algorithm occasionally is used because it is more convenient to set up the
initial tableau in this form than in the form required by the simplex method. Further-
more, it frequently is used for reoptimization (discussed in Sec. 4.7), because changes
in the original model lead to the revised final tableau fitting this form. This situation is
common for certain types of sensitivity analysis, as you will see later in the chapter.
In general terms, duality theory plays a central role in sensitivity analysis. This role
is the topic of Sec. 6.5.
Another important application is its use in the economic interpretation of the dual prob-
lem and the resulting insights for analyzing the primal problem. You already have seen one
example when we discussed shadow prices in Sec. 4.7. Section 6.2 describes how this in-
terpretation extends to the entire dual problem and then to the simplex method.
6.2 ECONOMIC INTERPRETATION OF DUALITY 203
1Actually, several slightly different interpretations have been proposed. The one presented here seems to us to
be the most useful because it also directly interprets what the simplex method does in the primal problem.
■ 6.2 ECONOMIC INTERPRETATION OF DUALITY
The economic interpretation of duality is based directly upon the typical interpretation for
the primal problem (linear programming problem in our standard form) presented in Sec. 3.2.
To refresh your memory, we have summarized this interpretation of the primal problem in
Table 6.6.
Interpretation of the Dual Problem
To see how this interpretation of the primal problem leads to an economic interpretation
for the dual problem,1 note in Table 6.4 that W is the value of Z (total profit) at the cur-
rent iteration. Because
W � b1y1 � b2 y2 � . . . � bm ym ,
■ TABLE 6.6 Economic interpretation of the primal problem
Quantity Interpretation
xj Level of activity j ( j � 1, 2, . . . , n)
cj Unit profit from activity j
Z Total profit from all activities
bi Amount of resource i available (i � 1, 2, . . . , m)
aij Amount of resource i consumed by each unit of activity j
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text212 © The McGraw−Hill
Companies, 2010
each bi yi can thereby be interpreted as the current contribution to profit by having bi units
of resource i available for the primal problem. Thus,
The dual variable yi is interpreted as the contribution to profit per unit of resource
i (i � 1, 2, . . . , m), when the current set of basic variables is used to obtain the
primal solution.
In other words, the yi values (or yi* values in the optimal solution) are just the shadow
prices discussed in Sec. 4.7.
For example, when iteration 2 of the simplex method finds the optimal solution for
the Wyndor problem, it also finds the optimal values of the dual variables (as shown in
the bottom row of Table 6.5) to be y1* � 0, y2* � �
3
2
�, and y3* � 1. These are precisely the
shadow prices found in Sec. 4.7 for this problem through graphical analysis. Recall that
the resources for the Wyndor problem are the production capacities of the three plants
being made available to the two new products under consideration, so that bi is the num-
ber of hours of production time per week being made available in Plant i for these
new products, where i � 1, 2, 3. As discussed in Sec. 4.7, the shadow prices indicate
that individually increasing any bi by 1 would increase the optimal value of the ob-
jective function (total weekly profit in units of thousands of dollars) by yi*. Thus, yi*
can be interpreted as the contribution to profit per unit of resource i when using the
optimal solution.
This interpretation of the dual variables leads to our interpretation of the overall dual
problem. Specifically, since each unit of activity j in the primal problem consumes aij
units of resource i,
�mi�1 ai jyi is interpreted as the current contribution to profit of the mix of resources
that would be consumed if 1 unit of activity j were used ( j � 1, 2, . . . , n).
For the Wyndor problem, 1 unit of activity j corresponds to producing 1 batch of product
j per week, where j � 1, 2. The mix of resources consumed by producing 1 batch of prod-
uct 1 is 1 hour of production time in Plant 1 and 3 hours in Plant 3. The corresponding
mix per batch of product 2 is 2 hours each in Plants 2 and 3. Thus, y1 � 3y3 and 2y2 � 2y3
are interpreted as the current contributions to profit (in thousands of dollars per week) of
these respective mixes of resources per batch produced per week of the respective products.
For each activity j, this same mix of resources (and more) probably can be used in
other ways as well, but no alternative use should be considered if it is less profitable than
1 unit of activity j. Since cj is interpreted as the unit profit from activity j, each functional
constraint in the dual problem is interpreted as follows:
�mi�1 aij yi � cj says that the actual contribution to profit of the above mix of re-
sources must be at least as much as if they were used by 1 unit of activity j; oth-
erwise, we would not be making the best possible use of these resources.
For the Wyndor problem, the unit profits (in thousands of dollars per week) are c1 � 3
and c2 � 5, so the dual functional constraints with this interpretation are y1 � 3y3 � 3
and 2y2 � 2y3 � 5. Similarly, the interpretation of the nonnegativity constraints is the
following:
yi � 0 says that the contribution to profit of resource i (i � 1, 2, . . . , m) must
be nonnegative: otherwise, it would be better not to use this resource at all.
The objective
Minimize W � �
m
i�1
bi yi
204 CHAPTER 6 DUALITY THEORY AND SENSITIVITY ANALYSIS
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text 213© The McGraw−Hill
Companies, 2010
can be viewed as minimizing the total implicit value of the resources consumed by the
activities. For the Wyndor problem, the total implicit value (in thousands of dollars per
week) of the resources consumed by the two products is W � 4y1 � 12y2 � 18y3.
This interpretation can be sharpened somewhat by differentiating between basic and
nonbasic variables in the primal problem for any given BF solution (x1, x2, . . . , xn�m).
Recall that the basic variables (the only variables whose values can be nonzero) always
have a coefficient of zero in row 0. Therefore, referring again to Table 6.4 and the ac-
companying equation for zj, we see that
�
m
i�1
aij yi � cj, if xj � 0 ( j � 1, 2, . . . , n),
yi � 0, if xn�i � 0 (i � 1, 2, . . . , m).
(This is one version of the complementary slackness property discussed in Sec. 6.3.) The
economic interpretation of the first statement is that whenever an activity j operates at a
strictly positive level (xj � 0), the marginal value of the resources it consumes must equal
(as opposed to exceeding) the unit profit from this activity. The second statement implies
that the marginal value of resource i is zero ( yi � 0) whenever the supply of this resource
is not exhausted by the activities (xn�i � 0). In economic terminology, such a resource is
a “free good”; the price of goods that are oversupplied must drop to zero by the law of
supply and demand. This fact is what justifies interpreting the objective for the dual prob-
lem as minimizing the total implicit value of the resources consumed, rather than the re-
sources allocated.
To illustrate these two statements, consider the optimal BF solution (2, 6, 2, 0, 0) for
the Wyndor problem. The basic variables are x1, x2, and x3, so their coefficients in row 0
are zero, as shown in the bottom row of Table 6.5. This bottom row also gives the corre-
sponding dual solution: y1* � 0, y2* � �
3
2
�, y3* � 1, with surplus variables (z1* � c1) � 0 and
(z2* � c2) � 0. Since x1 � 0 and x2 � 0, both these surplus variables and direct calcula-
tions indicate that y1* � 3y3* � c1 � 3 and 2y2* � 2y3* � c2 � 5. Therefore, the value of
the resources consumed per batch of the respective products produced does indeed equal
the respective unit profits. The slack variable for the constraint on the amount of Plant 1
capacity used is x3 � 0, so the marginal value of adding any Plant 1 capacity would be
zero ( y1* � 0).
Interpretation of the Simplex Method
The interpretation of the dual problem also provides an economic interpretation of what
the simplex method does in the primal problem. The goal of the simplex method is to
find how to use the available resources in the most profitable feasible way. To attain
this goal, we must reach a BF solution that satisfies all the requirements on profitable
use of the resources (the constraints of the dual problem). These requirements com-
prise the condition for optimality for the algorithm. For any given BF solution, the
requirements (dual constraints) associated with the basic variables are automatically
satisfied (with equality). However, those associated with nonbasic variables may or
may not be satisfied.
In particular, if an original variable xj is nonbasic so that activity j is not used, then
the current contribution to profit of the resources that would be required to undertake each
unit of activity j
�
m
i�1
aijyi
6.2 ECONOMIC INTERPRETATION OF DUALITY 205
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text214 © The McGraw−Hill
Companies, 2010
206 CHAPTER 6 DUALITY THEORY AND SENSITIVITY ANALYSIS
may be smaller than, larger than, or equal to the unit profit cj obtainable from the activ-
ity. If it is smaller, so that zj � cj
0 in row 0 of the simplex tableau, then these resources
can be used more profitably by initiating this activity. If it is larger (zj � cj � 0), then
these resources already are being assigned elsewhere in a more profitable way, so they
should not be diverted to activity j. If zj � cj � 0, there would be no change in profitability
by initiating activity j.
Similarly, if a slack variable xn�i is nonbasic so that the total allocation bi of resource
i is being used, then yi is the current contribution to profit of this resource on a marginal
basis. Hence, if yi
0, profit can be increased by cutting back on the use of this resource
(i.e., increasing xn�i). If yi � 0, it is worthwhile to continue fully using this resource,
whereas this decision does not affect profitability if yi � 0.
Therefore, what the simplex method does is to examine all the nonbasic variables in
the current BF solution to see which ones can provide a more profitable use of the re-
sources by being increased. If none can, so that no feasible shifts or reductions in the
current proposed use of the resources can increase profit, then the current solution must
be optimal. If one or more can, the simplex method selects the variable that, if increased
by 1, would improve the profitability of the use of the resources the most. It then actu-
ally increases this variable (the entering basic variable) as much as it can until the mar-
ginal values of the resources change. This increase results in a new BF solution with a
new row 0 (dual solution), and the whole process is repeated.
The economic interpretation of the dual problem considerably expands our ability to
analyze the primal problem. However, you already have seen in Sec. 6.1 that this inter-
pretation is just one ramification of the relationships between the two problems. In Sec 6.3,
we delve into these relationships more deeply.
2You might wonder why we do not also introduce artificial variables into these constraints as discussed in
Sec. 4.6. The reason is that these variables have no purpose other than to change the feasible region tem-
porarily as a convenience in starting the simplex method. We are not interested now in applying the simplex
method to the dual problem, and we do not want to change its feasible region.
■ 6.3 PRIMAL–DUAL RELATIONSHIPS
Because the dual problem is a linear programming problem, it also has corner-point so-
lutions. Furthermore, by using the augmented form of the problem, we can express these
corner-point solutions as basic solutions. Because the functional constraints have the
� form, this augmented form is obtained by subtracting the surplus (rather than adding
the slack) from the left-hand side of each constraint j ( j � 1, 2, . . . , n).2 This surplus is
zj � cj � �
m
i�1
aijyi � cj , for j � 1, 2, . . . , n.
Thus, zj�cj plays the role of the surplus variable for constraint j (or its slack variable if
the constraint is multiplied through by �1). Therefore, augmenting each corner-point so-
lution ( y1, y2, . . . , ym) yields a basic solution ( y1, y2, . . . , ym , z1 � c1, z2 � c2, . . . ,
zn � cn) by using this expression for zj � cj. Since the augmented form of the dual
problem has n functional constraints and n � m variables, each basic solution has n basic
variables and m nonbasic variables. (Note how m and n reverse their previous roles
here because, as Table 6.3 indicates, dual constraints correspond to primal variables and
dual variables correspond to primal constraints.)
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text 215© The McGraw−Hill
Companies, 2010
Complementary Basic Solutions
One of the important relationships between the primal and dual problems is a direct cor-
respondence between their basic solutions. The key to this correspondence is row 0 of the
simplex tableau for the primal basic solution, such as shown in Table 6.4 or 6.5. Such a
row 0 can be obtained for any primal basic solution, feasible or not, by using the formu-
las given in the bottom part of Table 5.8.
Note again in Tables 6.4 and 6.5 how a complete solution for the dual problem (includ-
ing the surplus variables) can be read directly from row 0. Thus, because of its coefficient in
row 0, each variable in the primal problem has an associated variable in the dual problem,
as summarized in Table 6.7, first for any problem and then for the Wyndor problem.
A key insight here is that the dual solution read from row 0 must also be a basic so-
lution! The reason is that the m basic variables for the primal problem are required to have
a coefficient of zero in row 0, which thereby requires the m associated dual variables to
be zero, i.e., nonbasic variables for the dual problem. The values of the remaining n (ba-
sic) variables then will be the simultaneous solution to the system of equations given at
the beginning of this section. In matrix form, this system of equations is z � c � yA � c,
and the fundamental insight of Sec. 5.3 actually identifies its solution for z � c and y as
being the corresponding entries in row 0.
Because of the symmetry property quoted in Sec. 6.1 (and the direct association be-
tween variables shown in Table 6.7), the correspondence between basic solutions in the
primal and dual problems is a symmetric one. Furthermore, a pair of complementary ba-
sic solutions has the same objective function value, shown as W in Table 6.4.
Let us now summarize our conclusions about the correspondence between primal and
dual basic solutions, where the first property extends the complementary solutions prop-
erty of Sec. 6.1 to the augmented forms of the two problems and then to any basic solu-
tion (feasible or not) in the primal problem.
Complementary basic solutions property: Each basic solution in the primal
problem has a complementary basic solution in the dual problem, where their
respective objective function values (Z and W ) are equal. Given row 0 of the sim-
plex tableau for the primal basic solution, the complementary dual basic solution
(y, z � c) is found as shown in Table 6.4.
The next property shows how to identify the basic and nonbasic variables in this com-
plementary basic solution.
Complementary slackness property: Given the association between variables
in Table 6.7, the variables in the primal basic solution and the complementary
dual basic solution satisfy the complementary slackness relationship shown in
Table 6.8. Furthermore, this relationship is a symmetric one, so that these two
basic solutions are complementary to each other.
6.3 PRIMAL-DUAL RELATIONSHIPS 207
■ TABLE 6.7 Association between variables in primal and dual problems
Primal Variable Associated Dual Variable
Any problem
(Decision variable) xj zj � cj (surplus variable) j � 1, 2, . . . , n
(Slack variable) xn�i yi (decision variable) i � 1, 2, . . . , m
Decision variables: x1 z1 � c1 (surplus variables)
Decision variables: x2 z2 � c2
Wyndor problem Slack variables: x3 y1 (decision variables)
Decision variables: x4 y2
Decision variables: x5 y3
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text216 © The McGraw−Hill
Companies, 2010
208 CHAPTER 6 DUALITY THEORY AND SENSITIVITY ANALYSIS
■ TABLE 6.8 Complementary slackness
relationship for complementary
basic solutions
Primal Associated
Variable Dual Variable
Basic Nonbasic (m variables)
Nonbasic Basic (n variables)
■ TABLE 6.9 Complementary basic solutions for the Wyndor Glass Co. example
Primal Problem Dual Problem
No. Basic Solution Feasible? Z � W Feasible? Basic Solution
1 (0, 0, 4, 12, 18) Yes 0 No (0, 0, 0, �3, �5)
2 (4, 0, 0, 12, 6) Yes 12 No (3, 0, 0, 0, �5)
3 (6, 0, �2, 12, 0) No 18 No (0, 0, 1, 0, �3)
4 (4, 3, 0, 6, 0) Yes 27 No ���92�, 0, �
5
2
�, 0, 0�
5 (0, 6, 4, 0, 6) Yes 30 No �0, �52�, 0, �3, 0�
6 (2, 6, 2, 0, 0) Yes 36 Yes �0, �32�, 1, 0, 0�
7 (4, 6, 0, 0, �6) No 42 Yes �3, �52�, 0, 0, 0�
8 (0, 9, 4, �6, 0) No 45 Yes �0, 0, �52�, �
9
2
�, 0�
The reason for using the name complementary slackness for this latter property is that
it says (in part) that for each pair of associated variables, if one of them has slack in its
nonnegativity constraint (a basic variable � 0), then the other one must have no slack (a
nonbasic variable � 0). We mentioned in Sec. 6.2 that this property has a useful economic
interpretation for linear programming problems.
Example. To illustrate these two properties, again consider the Wyndor Glass Co. prob-
lem of Sec. 3.1. All eight of its basic solutions (five feasible and three infeasible) are
shown in Table 6.9. Thus, its dual problem (see Table 6.1) also must have eight basic so-
lutions, each complementary to one of these primal solutions, as shown in Table 6.9.
The three BF solutions obtained by the simplex method for the primal problem are the
first, fifth, and sixth primal solutions shown in Table 6.9. You already saw in Table 6.5 how
the complementary basic solutions for the dual problem can be read directly from row 0,
starting with the coefficients of the slack variables and then the original variables. The other
dual basic solutions also could be identified in this way by constructing row 0 for each of
the other primal basic solutions, using the formulas given in the bottom part of Table 5.8.
Alternatively, for each primal basic solution, the complementary slackness property
can be used to identify the basic and nonbasic variables for the complementary dual ba-
sic solution, so that the system of equations given at the beginning of the section can be
solved directly to obtain this complementary solution. For example, consider the next-to-
last primal basic solution in Table 6.9, (4, 6, 0, 0, �6). Note that x1, x2, and x5 are basic
variables, since these variables are not equal to 0. Table 6.7 indicates that the associated
dual variables are (z1 � c1), (z2 � c2), and y3. Table 6.8 specifies that these associated dual
variables are nonbasic variables in the complementary basic solution, so
z1 � c1 � 0, z2 � c2 � 0, y3 � 0.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text 217© The McGraw−Hill
Companies, 2010
6.3 PRIMAL-DUAL RELATIONSHIPS 209
Consequently, the augmented form of the functional constraints in the dual problem,
y1 � 3y3 � (z1 � c1) � 3
2y2 � 2y3 � (z2 � c2) � 5,
reduce to
y1 � 0 � 0 � 3
2y2 � 0 � 0 � 5,
so that y1 � 3 and y2 � �
5
2
�. Combining these values with the values of 0 for the nonbasic
variables gives the basic solution (3, �52�, 0, 0, 0), shown in the rightmost column and next-
to-last row of Table 6.9. Note that this dual solution is feasible for the dual problem be-
cause all five variables satisfy the nonnegativity constraints.
Finally, notice that Table 6.9 demonstrates that (0, �32�, 1, 0, 0) is the optimal solution
for the dual problem, because it is the basic feasible solution with minimal W (36).
Relationships between Complementary Basic Solutions
We now turn our attention to the relationships between complementary basic solutions,
beginning with their feasibility relationships. The middle columns in Table 6.9 provide
some valuable clues. For the pairs of complementary solutions, notice how the yes or no
answers on feasibility also satisfy a complementary relationship in most cases. In partic-
ular, with one exception, whenever one solution is feasible, the other is not. (It also is
possible for neither solution to be feasible, as happened with the third pair.) The one ex-
ception is the sixth pair, where the primal solution is known to be optimal. The explana-
tion is suggested by the Z � W column. Because the sixth dual solution also is optimal
(by the complementary optimal solutions property), with W � 36, the first five dual so-
lutions cannot be feasible because W
36 (remember that the dual problem objective is
to minimize W ). By the same token, the last two primal solutions cannot be feasible be-
cause Z � 36.
This explanation is further supported by the strong duality property that optimal pri-
mal and dual solutions have Z � W.
Next, let us state the extension of the complementary optimal solutions property of
Sec. 6.1 for the augmented forms of the two problems.
Complementary optimal basic solutions property: An optimal basic solution
in the primal problem has a complementary optimal basic solution in the dual
problem, where their respective objective function values (Z and W ) are equal.
Given row 0 of the simplex tableau for the optimal primal solution, the comple-
mentary optimal dual solution (y*, z* � c) is found as shown in Table 6.4.
To review the reasoning behind this property, note that the dual solution (y*, z* � c)
must be feasible for the dual problem because the condition for optimality for the pri-
mal problem requires that all these dual variables (including surplus variables) be non-
negative. Since this solution is feasible, it must be optimal for the dual problem by the
weak duality property (since W � Z, so y*b � cx* where x* is optimal for the primal
problem).
Basic solutions can be classified according to whether they satisfy each of two con-
ditions. One is the condition for feasibility, namely, whether all the variables (including
slack variables) in the augmented solution are nonnegative. The other is the condition
for optimality, namely, whether all the coefficients in row 0 (i.e., all the variables in the
complementary basic solution) are nonnegative. Our names for the different types of
basic solutions are summarized in Table 6.10. For example, in Table 6.9, primal basic
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text218 © The McGraw−Hill
Companies, 2010
210 CHAPTER 6 DUALITY THEORY AND SENSITIVITY ANALYSIS
solutions 1, 2, 4, and 5 are suboptimal, 6 is optimal, 7 and 8 are superoptimal, and 3 is
neither feasible nor superoptimal.
Given these definitions, the general relationships between complementary basic so-
lutions are summarized in Table 6.11. The resulting range of possible (common) values
for the objective functions (Z � W ) for the first three pairs given in Table 6.11 (the last
pair can have any value) is shown in Fig. 6.1. Thus, while the simplex method is dealing
■ TABLE 6.11 Relationships between complementary basic solutions
Both Basic Solutions
Primal Basic Complementary
Solution Dual Basic Solution Primal Feasible? Dual Feasible?
Suboptimal Superoptimal
Yes No
Optimal Optimal Yes Yes
Superoptimal Suboptimal No Yes
Neither feasible Neither feasible No No
nor superoptimal nor superoptimal
■ TABLE 6.10 Classification of basic solutions
Satisfies Condition
for Optimality?
Yes No
Yes Optimal Suboptimal
Feasible?
No Superoptimal Neither feasible nor superoptimal
Primal problem Dual problem
n
�
j�1
cj xj � Z
m
�
i �1
bi yiW �
Superoptimal Suboptimal
Suboptimal Superoptimal
(optimal) Z* (optimal)W*
■ FIGURE 6.1
Range of possible values of
Z � W for certain types of
complementary basic
solutions.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text 219© The McGraw−Hill
Companies, 2010
6.4 ADAPTING TO OTHER PRIMAL FORMS 211
■ TABLE 6.12 Conversions to standard form for linear programming models
Nonstandard Form Equivalent Standard Form
Minimize Z Maximize (�Z )
�
n
j�1
aijxj � bi ��
n
j�1
aijxj � �bi
�
n
j�1
aijxj � bi �
n
j�1
aijxj � bi and ��
n
j�1
aijxj � �bi
xj unconstrained in sign xj
� � xj
�, xj
� � 0, xj
� � 0
■ 6.4 ADAPTING TO OTHER PRIMAL FORMS
Thus far it has been assumed that the model for the primal problem is in our standard
form. However, we indicated at the beginning of the chapter that any linear programming
problem, whether in our standard form or not, possesses a dual problem. Therefore, this
section focuses on how the dual problem changes for other primal forms.
Each nonstandard form was discussed in Sec. 4.6, and we pointed out how it is pos-
sible to convert each one to an equivalent standard form if so desired. These conversions
are summarized in Table 6.12. Hence, you always have the option of converting any model
to our standard form and then constructing its dual problem in the usual way. To illus-
trate, we do this for our standard dual problem (it must have a dual also) in Table 6.13.
Note that what we end up with is just our standard primal problem! Since any pair of pri-
mal and dual problems can be converted to these forms, this fact implies that the dual of
the dual problem always is the primal problem. Therefore, for any primal problem and its
dual problem, all relationships between them must be symmetric. This is just the sym-
metry property already stated in Sec. 6.1 (without proof ), but now Table 6.13 demon-
strates why it holds.
One consequence of the symmetry property is that all the statements made earlier in
the chapter about the relationships of the dual problem to the primal problem also hold
in reverse.
directly with suboptimal basic solutions and working toward optimality in the primal prob-
lem, it is simultaneously dealing indirectly with complementary superoptimal solutions
and working toward feasibility in the dual problem. Conversely, it sometimes is more con-
venient (or necessary) to work directly with superoptimal basic solutions and to move to-
ward feasibility in the primal problem, which is the purpose of the dual simplex method
described in Sec. 7.1.
The third and fourth columns of Table 6.11 introduce two other common terms that
are used to describe a pair of complementary basic solutions. The two solutions are said
to be primal feasible if the primal basic solution is feasible, whereas they are called dual
feasible if the complementary dual basic solution is feasible for the dual problem. Using
this terminology, the simplex method deals with primal feasible solutions and strives to-
ward achieving dual feasibility as well. When this is achieved, the two complementary
basic solutions are optimal for their respective problems.
These relationships prove very useful, particularly in sensitivity analysis, as you will
see later in the chapter.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text220 © The McGraw−Hill
Companies, 2010
Another consequence is that it is immaterial which problem is called the primal and
which is called the dual. In practice, you might see a linear programming problem fit-
ting our standard form being referred to as the dual problem. The convention is that the
model formulated to fit the actual problem is called the primal problem, regardless of
its form.
Our illustration of how to construct the dual problem for a nonstandard primal prob-
lem did not involve either equality constraints or variables unconstrained in sign. Actu-
ally, for these two forms, a shortcut is available. It is possible to show (see Probs. 6.4-7
and 6.4-2a) that an equality constraint in the primal problem should be treated just like
a � constraint in constructing the dual problem except that the nonnegativity constraint
for the corresponding dual variable should be deleted (i.e., this variable is unconstrained
in sign). By the symmetry property, deleting a nonnegativity constraint in the primal prob-
lem affects the dual problem only by changing the corresponding inequality constraint to
an equality constraint.
Another shortcut involves functional constraints in � form for a maximization prob-
lem. The straightforward (but longer) approach would begin by converting each such con-
straint to � form
�
n
j�1
aij xj � bi ⎯→ � �
n
j�1
aij xj � �bi.
Constructing the dual problem in the usual way then gives �ai j as the coefficient of
yi in functional constraint j (which has � form) and a coefficient of �bi in the objec-
tive function (which is to be minimized), where yi also has a nonnegativity constraint
yi � 0. Now suppose we define a new variable yi� � �yi. The changes caused by ex-
pressing the dual problem in terms of yi� instead of yi are that (1) the coefficients of
the variable become ai j for functional constraint j and bi for the objective function and
(2) the constraint on the variable becomes yi� � 0 (a nonpositivity constraint). The
shortcut is to use yi� instead of yi as a dual variable so that the parameters in the orig-
inal constraint (ai j and bi) immediately become the coefficients of this variable in the
dual problem.
212 CHAPTER 6 DUALITY THEORY AND SENSITIVITY ANALYSIS
■ TABLE 6.13 Constructing the dual of the
dual problem
Minimize W � yb,
subject to
yA � c
and
y � 0.
Maximize (�W ) � �yb,
subject to
�yA � �c
and
y � 0.
Dual Problem Converted to Standard Form
Maximize Z � cx,
subject to
Ax � b
and
x � 0.
Minimize (�Z ) � �cx,
subject to
�Ax � �b
and
x � 0.
Converted to
Standard Form Its Dual Problem
⎯→
⎯→
⎯
→
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text 221© The McGraw−Hill
Companies, 2010
Here is a useful mnemonic device for remembering what the forms of dual constraints
should be. With a maximization problem, it might seem sensible for a functional constraint
to be in � form, slightly odd to be in � form, and somewhat bizarre to be in � form.
Similarly, for a minimization problem, it might seem sensible to be in � form, slightly odd
to be in � form, and somewhat bizarre to be in � form. For the constraint on an individ-
ual variable in either kind of problem, it might seem sensible to have a nonnegativity con-
straint, somewhat odd to have no constraint (so the variable is unconstrained in sign), and
quite bizarre for the variable to be restricted to be less than or equal to zero. Now recall
the correspondence between entities in the primal and dual problems indicated in Table 6.3;
namely, functional constraint i in one problem corresponds to variable i in the other prob-
lem, and vice versa. The sensible-odd-bizarre method, or SOB method for short, says
that the form of a functional constraint or the constraint on a variable in the dual problem
should be sensible, odd, or bizarre, depending on whether the form for the corresponding
entity in the primal problem is sensible, odd, or bizarre. Here is a summary.
The SOB Method for Determining the Form of Constraints in the Dual.3
1. Formulate the primal problem in either maximization form or minimization form, and
then the dual problem automatically will be in the other form.
2. Label the different forms of functional constraints and of constraints on individual vari-
ables in the primal problem as being sensible, odd, or bizarre according to Table 6.14. The
labeling of the functional constraints depends on whether the problem is a maximization
problem (use the second column) or a minimization problem (use the third column).
3. For each constraint on an individual variable in the dual problem, use the form that
has the same label as for the functional constraint in the primal problem that corre-
sponds to this dual variable (as indicated by Table 6.3).
4. For each functional constraint in the dual problem, use the form that has the same la-
bel as for the constraint on the corresponding individual variable in the primal prob-
lem (as indicated by Table 6.3).
The arrows between the second and third columns of Table 6.14 spell out the corre-
spondence between the forms of constraints in the primal and dual. Note that the corre-
spondence always is between a functional constraint in one problem and a constraint on
an individual variable in the other problem. Since the primal problem can be either a max-
imization or minimization problem, where the dual then will be of the opposite type, the
second column of the table gives the form for whichever is the maximization problem and
the third column gives the form for the other problem (a minimization problem).
To illustrate, consider the radiation therapy example presented at the beginning of
Sec. 3.4. To show the conversion in both directions in Table 6.14, we begin with the max-
imization form of this model as the primal problem, before using the (original) mini-
mization form.
The primal problem in maximization form is shown on the left side of Table 6.15. By
using the second column of Table 6.14 to represent this problem, the arrows in this table
indicate the form of the dual problem in the third column. These same arrows are used in
Table 6.15 to show the resulting dual problem. (Because of these arrows, we have placed
the functional constraints last in the dual problem rather than in their usual top position.)
6.4 ADAPTING TO OTHER PRIMAL FORMS 213
3This particular mnemonic device (and a related one) for remembering what the forms of the dual constraints
should be has been suggested by Arthur T. Benjamin, a mathematics professor at Harvey Mudd College. An in-
teresting and wonderfully bizarre fact about Professor Benjamin himself is that he is one of the world’s great
human calculators who can perform such feats as quickly multiplying six-digit numbers in his head. For a
further discussion and derivation of the SOB method, see A. T. Benjamin: “Sensible Rules for Remembering
Duals — The S-O-B Method,” SIAM Review, 37(1): 85–87, 1995.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text222 © The McGraw−Hill
Companies, 2010
Beside each constraint in both problems, we have inserted (in parentheses) an S, O, or B to
label the form as sensible, odd, or bizarre. As prescribed by the SOB method, the label for
each dual constraint always is the same as for the corresponding primal constraint.
However, there was no need (other than for illustrative purposes) to convert the pri-
mal problem to maximization form. Using the original minimization form, the equivalent
primal problem is shown on the left side of Table 6.16. Now we use the third column of
Table 6.14 to represent this primal problem, where the arrows indicate the form of the
dual problem in the second column. These same arrows in Table 6.16 show the resulting
dual problem on the right side. Again, the labels on the constraints show the application
of the SOB method.
Just as the primal problems in Tables 6.15 and 6.16 are equivalent, the two dual prob-
lems also are completely equivalent. The key to recognizing this equivalency lies in the
fact that the variables in each version of the dual problem are the negative of those in the
other version (y1� � �y1, y2� � �y2, y3 � �y3�). Therefore, for each version, if the vari-
ables in the other version are used instead, and if both the objective function and the con-
straints are multiplied through by �1, then the other version is obtained. (Problem 6.4-5
asks you to verify this.)
If you would like to see another example of using the SOB method to construct a
dual problem, one is given in the Worked Examples section of the book’s website.
If the simplex method is to be applied to either a primal or a dual problem that has
any variables constrained to be nonpositive (for example, y3� � 0 in the dual problem of
Table 6.15), this variable may be replaced by its nonnegative counterpart (for example,
y3 � �y3�).
214 CHAPTER 6 DUALITY THEORY AND SENSITIVITY ANALYSIS
■ TABLE 6.14 Corresponding primal-dual forms
Primal Problem Dual Problem
Label (or Dual Problem) (or Primal Problem)
Maximize Z (or W ) Minimize W (or Z )
Constraint i: Variable yi (or xi):
Sensible � form yi � 0
Odd � form Unconstrained
Bizarre � form yi� � 0
Variable xj (or yj): Constraint j:
Sensible xj � 0 � form
Odd Unconstrained � form
Bizarre xj� � 0 � form
←⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯→
←⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯→
←⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯→
←⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯→
←⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯→
←⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯→
■ TABLE 6.15 One primal-dual form for the radiation therapy example
Maximize �Z � �0.4×1 � 0.5×2,
subject to
(S) 0.3×1 � 0.1×2 � 2.7
(O) 0.5×1 � 0.5×2 � 6
(B) 0.6×1 � 0.4×2 � 6
and
(S) x1 � 0
(S) x2 � 0
Minimize W � 2.7y1 � 6y2 � 6y3�,
subject to
y1 � 0 (S)
y2 unconstrained in sign (O)
y3� � 0 (B)
and
0.3y1 � 0.5y2 � 0.6y3� � �0.4 (S)
0.1y1 � 0.5y2 � 0.4y3� � �0.5 (S)
Primal Problem Dual Problem
←⎯⎯⎯⎯→
←⎯⎯⎯⎯→
←⎯⎯⎯⎯→
←⎯⎯⎯⎯→
←⎯⎯⎯⎯→
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
6. Duality Theory and
Sensitivity Analysis
Text 223© The McGraw−Hill
Companies, 2010
6.5 THE ROLE OF DUALITY THEORY IN SENSITIVITY ANALYSIS 215
When artificial variables are used to help the simplex method solve a primal prob-
lem, the duality interpretation of row 0 of the simplex tableau is the following: Since ar-
tificial variables play the role of slack variables, their coefficients in row 0 now provide
the values of the corresponding dual variables in the complementary basic solution for the
dual problem. Since artificial variables are used to replace the real problem with a more
convenient artificial problem, this dual problem actually is the dual of the artificial prob-
lem. However, after all the artificial variables become nonbasic, we are back to the real
primal and dual problems. With the two-phase method, the artificial variables would need
to be retained in phase 2 in order to read off the complete dual solution from row 0. With
the Big M method, since M has been added initially to the coefficient of each artificial
variable in row 0, the current value of each corresponding dual variable is the current co-
efficient of this artificial variable minus M.
For example, look at row 0 in the final simplex tableau for the radiation therapy
example, given at the bottom of Table 4.12. After M is subtracted from the coefficients
of the artificial variables x�4 and x�6, the optimal solution for the corresponding dual prob-
lem given in Table 6.15 is read from the coefficients of x3, x�4, and x�6 as (y1, y2, y3�)
� (0.5, �1.1, 0). As usual, the surplus variables for the two functional constraints are
read from the coefficients of x1 and x2 as z1 � c1 � 0 and z2 � c2 � 0.
■ TABLE 6.16 The other primal-dual form for the radiation therapy example
Minimize Z � 0.4×1 � 0.5×2,
subject to
(B) 0.3×1 � 0.1×2 � 2.7
(O) 0.5×1 � 0.5×2 � 6
(S) 0.6×1 � 0.4×2 � 6
and
(S) x1 � 0
(S) x2 � 0
Maximize W � 2.7y1� � 6y2� � 6y3,
subject to
y1� � 0 (B)
y2� unconstrained in sign (O)
y3 � 0 (S)
and
0.3y1� � 0.5y2� � 0.6y3 � 0.4 (S)
0.1y1� � 0.5y2� � 0.4y3 � 0.6 (S)
Primal Problem Dual Problem
←⎯⎯⎯⎯→
←⎯⎯⎯⎯→
←⎯⎯⎯⎯→
←⎯⎯⎯⎯→
←⎯⎯⎯⎯→
■ 6.5 THE ROLE OF DUALITY THEORY IN SENSITIVITY ANALYSIS
As described further in the next three sections, sensitivity analysis basically involves in-
vestigating the effect on the optimal solution of making changes in the values of the
model parameters aij, bi, and cj. However, changing parameter values in the primal prob-
lem also changes the corresponding values in the dual problem. Therefore, you have your
choice of which problem to use to investigate each change. Because of the primal-dual
relationships presented in Secs. 6.1 and 6.3 (especially the complementary basic solu-
tions property), it is easy to move back and forth between the two problems as desired.
In some cases, it is more convenient to analyze the dual problem directly in order to de-
termine the complementary effect on the primal problem. We begin by considering two
such cases.
Changes in the Coefficients of a Nonbasic Variable
Suppose that the changes made in the original model occur in the coefficients of a vari-
able that was nonbasic in the original optimal solution. What is the effect of these changes
on this solution? Is it still feasible? Is it still optimal?
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text312 © The McGraw−Hill
Companies, 2010
8C H A P T E R
The Transportation
and Assignment Problems
304
Chapter 3 emphasized the wide applicability of linear programming. We continue tobroaden our horizons in this chapter by discussing two particularly important (and re-
lated) types of linear programming problems. One type, called the transportation problem,
received this name because many of its applications involve determining how to optimally
transport goods. However, some of its important applications (e.g., production scheduling)
actually have nothing to do with transportation.
The second type, called the assignment problem, involves such applications as as-
signing people to tasks. Although its applications appear to be quite different from those
for the transportation problem, we shall see that the assignment problem can be viewed
as a special type of transportation problem.
The next chapter will introduce additional special types of linear programming prob-
lems involving networks, including the minimum cost flow problem (Sec. 9.6). There we
shall see that both the transportation and assignment problems actually are special cases
of the minimum cost flow problem. We introduce the network representation of the trans-
portation and assignment problems in this chapter.
Applications of the transportation and assignment problems tend to require a very
large number of constraints and variables, so a straightforward computer application of
the simplex method may require an exorbitant computational effort. Fortunately, a key
characteristic of these problems is that most of the aij coefficients in the constraints are
zeros, and the relatively few nonzero coefficients appear in a distinctive pattern. As a re-
sult, it has been possible to develop special streamlined algorithms that achieve dramatic
computational savings by exploiting this special structure of the problem. Therefore, it is
important to become sufficiently familiar with these special types of problems that you
can recognize them when they arise and apply the proper computational procedure.
To describe special structures, we shall introduce the table (matrix) of constraint coeffi-
cients shown in Table 8.1, where aij is the coefficient of the jth variable in the ith functional
constraint. Later, portions of the table containing only coefficients equal to zero will be in-
dicated by leaving them blank, whereas blocks containing nonzero coefficients will be shaded.
After presenting a prototype example for the transportation problem, we describe the
special structure in its model and give additional examples of its applications. Section 8.2
presents the transportation simplex method, a special streamlined version of the simplex
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 313© The McGraw−Hill
Companies, 2010
8.1 THE TRANSPORTATION PROBLEM 305
method for efficiently solving transportation problems. (You will see in Sec. 9.7 that this
algorithm is related to the network simplex method, another streamlined version of the
simplex method for efficiently solving any minimum cost flow problem, including both
transportation and assignment problems.) Section 8.3 focuses on the assignment problem.
Section 8.4 then presents a specialized algorithm, called the Hungarian algorithm, for
solving only assignment problems very efficiently.
The book’s website also provides a supplement to this chapter. It is a complete case
study (including the analysis) that illustrates how a corporate decision regarding where to
locate a new facility (an oil refinery in this case) may require solving many transporta-
tion problems. (One of the cases for this chapter asks you to continue the analysis for an
extension of this case study.)
■ 8.1 THE TRANSPORTATION PROBLEM
Prototype Example
One of the main products of the P & T COMPANY is canned peas. The peas are pre-
pared at three canneries (near Bellingham, Washington; Eugene, Oregon; and Albert Lea,
Minnesota) and then shipped by truck to four distributing warehouses in the western
United States (Sacramento, California; Salt Lake City, Utah; Rapid City, South Dakota;
and Albuquerque, New Mexico), as shown in Fig. 8.1. Because the shipping costs are a
major expense, management is initiating a study to reduce them as much as possible. For
the upcoming season, an estimate has been made of the output from each cannery, and
each warehouse has been allocated a certain amount from the total supply of peas. This
information (in units of truckloads), along with the shipping cost per truckload for each
cannery-warehouse combination, is given in Table 8.2. Thus, there are a total of 300
truckloads to be shipped. The problem now is to determine which plan for assigning these
shipments to the various cannery-warehouse combinations would minimize the total ship-
ping cost.
By ignoring the geographical layout of the canneries and warehouses, we can pro-
vide a network representation of this problem in a simple way by lining up all the can-
neries in one column on the left and all the warehouses in one column on the right. This
representation is shown in Fig. 8.2. The arrows show the possible routes for the truck-
loads, where the number next to each arrow is the shipping cost per truckload for that
route. A square bracket next to each location gives the number of truckloads to be shipped
out of that location (so that the allocation into each warehouse is given as a negative
number).
The problem depicted in Fig. 8.2 is actually a linear programming problem of the
transportation problem type. To formulate the model, let Z denote total shipping cost, and
let xij (i � 1, 2, 3; j � 1, 2, 3, 4) be the number of truckloads to be shipped from cannery
■ TABLE 8.1 Table of
constraint coefficients
for linear programming
A �
⎤
⎥
⎥
⎥
⎦
a1n
a2n
amn
…
…
…
a12
a22
am2
a11
a21
am1
⎡
⎢
⎢
⎢
⎣
………………………
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text314 © The McGraw−Hill
Companies, 2010
CANNERY 1
Bellingham
CANNERY 2
Eugene CANNERY 3
Albert Lea
WAREHOUSE 4
Albuquerque
WAREHOUSE 3
Rapid City
WAREHOUSE 2
Salt Lake City
WAREHOUSE 1
Sacramento
■ FIGURE 8.1
Location of canneries and warehouses for the P & T Co. problem.
Procter & Gamble (P & G) makes and markets over
300 brands of consumer goods worldwide. The company
has grown continuously over its long history tracing back
to the 1830s. To maintain and accelerate that growth, a
major OR study was undertaken to strengthen P & G’s
global effectiveness. Prior to the study, the company’s
supply chain consisted of hundreds of suppliers, over
50 product categories, over 60 plants, 15 distribution
centers, and over 1,000 customer zones. However, as
the company moved toward global brands, management
realized that it needed to consolidate plants to reduce
manufacturing expenses, improve speed to market, and
reduce capital investment. Therefore, the study focused
on redesigning the company’s production and distribu-
tion system for its North American operations. The re-
sult was a reduction in the number of North American
plants by almost 20 percent, saving over $200 million in
pretax costs per year.
A major part of the study revolved around formulat-
ing and solving transportation problems for individual
product categories. For each option regarding the plants
to keep open, and so forth, solving the corresponding
transportation problem for a product category showed
what the distribution cost would be for shipping the prod-
uct category from those plants to the distribution centers
and customer zones.
Source: J. D. Camm, T. E. Chorman, F. A. Dill, J. R. Evans,
D. J. Sweeney, and G. W. Wegryn: “Blending OR/MS, Judg-
ment, and GIS: Restructuring P & G’s Supply Chain,” Inter-
faces, 27(1): 128–142, Jan.–Feb. 1997. (A link to this article is
provided on our website, www.mhhe.com/hillier.)
An Application Vignette
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 315© The McGraw−Hill
Companies, 2010
8.1 THE TRANSPORTATION PROBLEM 307
i to warehouse j. Thus, the objective is to choose the values of these 12 decision variables
(the xij) so as to
Minimize Z � 464×11 � 513×12 � 654×13 � 867×14 � 352×21 � 416×22
� 690×23 � 791×24 � 995×31 � 682×32 � 388×33 � 685×34,
subject to the constraints
x11 � x12 � x13 � x14 � x21 � x21 � x21 � x21 � x21 � x21 � x21 � x21 � 75
� x21 � x21 � x21 � x21x21 � x22 � x23 � x24 � x21 � x21 � x21 � x21 � 125
� x21 � x21 � x21 � x21 � x21 � x21 � x21 � x21x31 � x32 � x33 � x34 � 100
x11 � x21 � x21 � x21 � x21 � x21 � x21 � x21 � x31 � x21 � x21 � x21 � 80
x11 � x12 � x21 � x21 � x21 � x22 � x21 � x21 � x21 � x32 � x21 � x21 � 65
x11 � x12 � x13 � x21 � x21 � x21 � x23 � x21 � x21 � x21 � x33 � x21 � 70
x11 � x12 � x13 � x14 � x21 � x21 � x21 � x24 � x21 � x21 � x21 � x34 � 85
and
xij � 0 (i � 1, 2, 3; j � 1, 2, 3, 4).
■ TABLE 8.2 Shipping data for P & T Co.
Shipping Cost ($) per Truckload
Warehouse
1 2 3 4 Output
1 464 513 654 867 75
Cannery 2 352 416 690 791 125
3 995 682 388 685 100
Allocation 80 65 70 85
[75]
[125]
[100]
[�80]
[�65]
[�70]
[�85]
C1
C2
C3
W1
W2
W3
W4
464
352
995
867
654
513
416
690
791
682
388
685
■ FIGURE 8.2
Network representation of
the P & T Co. problem.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text316 © The McGraw−Hill
Companies, 2010
308 CHAPTER 8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
Table 8.3 shows the constraint coefficients. As you will see later in this section, it is the
special structure in the pattern of these coefficients that distinguishes this problem as a
transportation problem, not its context. However, we first will describe the various other
characteristics of the transportation problem model.
The Transportation Problem Model
To describe the general model for the transportation problem, we need to use terms that
are considerably less specific than those for the components of the prototype example. In
particular, the general transportation problem is concerned (literally or figuratively) with
distributing any commodity from any group of supply centers, called sources, to any group
of receiving centers, called destinations, in such a way as to minimize the total distribu-
tion cost. The correspondence in terminology between the prototype example and the gen-
eral problem is summarized in Table 8.4.
As indicated by the fourth and fifth rows of the table, each source has a certain sup-
ply of units to distribute to the destinations, and each destination has a certain demand
for units to be received from the sources. The model for a transportation problem makes
the following assumption about these supplies and demands.
The requirements assumption: Each source has a fixed supply of units, where
this entire supply must be distributed to the destinations. (We let si denote the
number of units being supplied by source i, for i � 1, 2, . . . , m.) Similarly, each
destination has a fixed demand for units, where this entire demand must be re-
ceived from the sources. (We let dj denote the number of units being received by
destination j, for j � 1, 2, . . . , n.)
This assumption holds for the P & T Co. problem since each cannery (source) has a fixed
output and each warehouse (destination) has a fixed allocation.
■ TABLE 8.4 Terminology for the transportation problem
Prototype Example General Problem
Truckloads of canned peas Units of a commodity
Three canneries m sources
Four warehouses n destinations
Output from cannery i Supply si from source i
Allocation to warehouse j Demand dj at destination j
Shipping cost per truckload from cannery Cost cij per unit distributed from source
i to warehouse j i to destination j
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎧
⎪
⎨
⎪
⎩
⎧
⎨
⎩
■ TABLE 8.3 Constraint coefficients for P & T Co.
Coefficient of:
x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34
1
1 1 1
Cannery
1 1 1 1
constraints
1 1 1 1
A � 1 1 1
1 1 1 Warehouse
1 1 1 constraints
1 1 1
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 317© The McGraw−Hill
Companies, 2010
8.1 THE TRANSPORTATION PROBLEM 309
This assumption that there is no leeway in the amounts to be sent or received means
that there needs to be a balance between the total supply from all sources and the total
demand at all destinations.
The feasible solutions property: A transportation problem will have feasible
solutions if and only if
�
m
i�1
si � �
n
j�1
dj.
Fortunately, these sums are equal for the P & T Co. since Table 8.2 indicates that the sup-
plies (outputs) sum to 300 truckloads and so do the demands (allocations).
In some real problems, the supplies actually represent maximum amounts (rather than
fixed amounts) to be distributed. Similarly, in other cases, the demands represent maxi-
mum amounts (rather than fixed amounts) to be received. Such problems do not quite fit
the model for a transportation problem because they violate the requirements assumption.
However, it is possible to reformulate the problem so that they then fit this model by in-
troducing a dummy destination or a dummy source to take up the slack between the ac-
tual amounts and maximum amounts being distributed. We will illustrate how this is done
with two examples at the end of this section.
The last row of Table 8.4 refers to a cost per unit distributed. This reference to a unit
cost implies the following basic assumption for any transportation problem.
The cost assumption: The cost of distributing units from any particular source to
any particular destination is directly proportional to the number of units distrib-
uted. Therefore, this cost is just the unit cost of distribution times the number of
units distributed. (We let cij denote this unit cost for source i and destination j.)
This assumption holds for the P & T Co. problem since the cost of shipping peas from
any cannery to any warehouse is directly proportional to the number of truckloads being
shipped.
The only data needed for a transportation problem model are the supplies, demands,
and unit costs. These are the parameters of the model. All these parameters can be sum-
marized conveniently in a single parameter table as shown in Table 8.5.
The model: Any problem (whether involving transportation or not) fits the
model for a transportation problem if it can be described completely in terms
of a parameter table like Table 8.5 and it satisfies both the requirements assump-
tion and the cost assumption. The objective is to minimize the total cost of distrib-
uting the units. All the parameters of the model are included in this parameter table.
■ TABLE 8.5 Parameter table for the transportation problem
Cost per Unit Distributed
Destination
1 2 … n Supply
1 c11 c12 … c1n s1
2 c21 c22 … c2n s2Source
� �
m cm1 cm2 … cmn sm
Demand d1 d2 … dn
…………………………………………………………………
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text318 © The McGraw−Hill
Companies, 2010
310 CHAPTER 8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
Therefore, formulating a problem as a transportation problem only requires filling
out a parameter table in the format of Table 8.5. (The parameter table for the P & T Co.
problem is shown in Table 8.2.) Alternatively, the same information can be provided by
using the network representation of the problem shown in Fig. 8.3 (as was done in
Fig. 8.2 for the P & T Co. problem). Some problems that have nothing to do with trans-
portation also can be formulated as a transportation problem in either of these two ways.
The Worked Examples section of the book’s website includes another example of such
a problem.
Since a transportation problem can be formulated simply by either filling out a para-
meter table or drawing its network representation, it is not necessary to write out a for-
mal mathematical model for the problem. However, we will go ahead and show you this
model once for the general transportation problem just to emphasize that it is indeed a
special type of linear programming problem.
Letting Z be the total distribution cost and xij (i � 1, 2, . . . , m; j � 1, 2, . . . , n) be
the number of units to be distributed from source i to destination j, the linear program-
ming formulation of this problem is
Minimize Z � �
m
i�1
�
n
j�1
cijxij,
subject to
�
n
j�1
xij � si for i � 1, 2, . . . , m,
D1S1[s1] [�d1]
S2 D2[s2] [�d2]
Sm Dn[sm] [�dn]
c11
c22
c m
1
c m2
cmn
c
2n
c12
c
1n
c21
■ FIGURE 8.3
Network representation of
the transportation problem.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 319© The McGraw−Hill
Companies, 2010
8.1 THE TRANSPORTATION PROBLEM 311
�
m
i�1
xij � dj for j � 1, 2, . . . , n,
and
xij � 0, for all i and j.
Note that the resulting table of constraint coefficients has the special structure shown in
Table 8.6. Any linear programming problem that fits this special formulation is of the trans-
portation problem type, regardless of its physical context. In fact, there have been numerous
applications unrelated to transportation that have been fitted to this special structure, as we
shall illustrate in the next example later in this section. (The assignment problem described
in Sec. 8.3 is an additional example.) This is one of the reasons why the transportation prob-
lem is considered such an important special type of linear programming problem.
For many applications, the supply and demand quantities in the model (the si and dj)
have integer values, and implementation will require that the distribution quantities (the xij)
also have integer values. Fortunately, because of the special structure shown in Table 8.6,
all such problems have the following property.
Integer solutions property: For transportation problems where every si and dj
have an integer value, all the basic variables (allocations) in every basic feasible
(BF) solution (including an optimal one) also have integer values.
The solution procedure described in Sec. 8.2 deals only with BF solutions, so it auto-
matically will obtain an integer optimal solution for this case. (You will be able to see why
this solution procedure actually gives a proof of the integer solutions property after you
learn the procedure; Prob. 8.2-20 guides you through the reasoning involved.) Therefore,
it is unnecessary to add a constraint to the model that the xij must have integer values.
As with other linear programming problems, the usual software options (Excel,
LINGO/LINDO, MPL/CPLEX) are available to you for setting up and solving trans-
portation problems (and assignment problems), as demonstrated in the files for this
chapter in your OR Courseware. However, because the Excel approach now is some-
what different from what you have seen previously, we next describe this approach.
Using Excel to Formulate and Solve Transportation Problems
As described in Sec. 3.6, the process of using a spreadsheet to formulate a linear program-
ming model for a problem begins by developing answers to three questions. What are the
decisions to be made? What are the constraints on these decisions? What is the overall mea-
sure of performance for these decisions? Since a transportation problem is a special type of
■ TABLE 8.6 Constraint coefficients for the transportation problem
Coefficient of:
x11 x12 … x1n x21 x22 … x2n … xm1 xm2 … xmn
1 1 … 1
1 1 … 1 Supply
constraints
1 1 … 1
A �
1 1 1
1 1 … 1 Demand
constraints
1 1 1
………
…
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎧
⎪
⎨
⎪
⎩
⎧
⎪
⎨
⎪
⎩
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text320 © The McGraw−Hill
Companies, 2010
312 CHAPTER 8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
linear programming problem, addressing these questions also is a suitable starting point for
formulating this kind of problem on a spreadsheet. The design of the spreadsheet then re-
volves around laying out this information and the associated data in a logical way.
To illustrate, consider the P & T Co. problem again. The decisions to be made are
the number of truckloads of peas to ship from each cannery to each warehouse. The con-
straints on these decisions are that the total amount shipped from each cannery must equal
its output (the supply) and the total amount received at each warehouse must equal its al-
location (the demand). The overall measure of performance is the total shipping cost, so
the objective is to minimize this quantity.
This information leads to the spreadsheet model shown in Fig. 8.4. All the data pro-
vided in Table 8.2 are displayed in the following data cells: UnitCost (D5:G7), Supply
(J12:J14), and Demand (D17:G17). The decisions on shipping quantities are given by the
changing cells, ShipmentQuantity (D12:G14). The output cells are TotalShipped (H12:H14)
and TotalReceived (D15:G15), where the SUM functions entered into these cells are shown
near the bottom of Fig. 8.4. The constraints, TotalShipped (H12:H14) = Supply (J12:J14)
and TotalReceived (D15:G15) = Demand (D17:G17), have been specified on the spread-
sheet and entered into the Solver dialogue box. The target cell is TotalCost (J17), where
its SUMPRODUCT function is shown in the lower right-hand corner of Fig. 8.4. The
Solver dialogue box specifies that the objective is to minimize this target cell. One of the
selected Solver options (Assume Non-Negative) specifies that all shipment quantities must
be nonnegative. The other one (Assume Linear Model) indicates that this transportation
problem is also a linear programming problem.
To begin the process of solving the problem, any value (such as 0) can be entered in
each of the changing cells. After clicking on the Solve button, the Solver will use the sim-
plex method to solve the transportation problem and determine the best value for each of
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
A B C D E F G H I J
P&T Co. Distribution Problem
Uni t Cost Destination (Warehouse)
Sacramento Salt Lake City Rapid City Albuquerque
Source Bellingham $464 $513 $654 $867
(Cannery) Eugene $352 $416 $690 $791
Albert Lea $995 $682 $388 $685
Shi pm ent Qu anti ty Destination (Warehouse)
(Truckl oa ds) Sacramento Salt Lake City Rapid City Albuquerque Total Shipped Supply
Source Bellingham 0 20 0 55 75 = 75
(Cannery) Eugene 80 45 0 0 125 = 125
Albert Lea 0 0 70 30 100 = 100
Total Received 80 65 70 85
= = = = Total Cost
Demand 80 65 70 85 152,535$
■ FIGURE 8.4
A spreadsheet formulation of
the P & T Co. problem as a
transportation problem,
including the target cell
TotalCost (J17) and the other
output cells TotalShipped
(H12:H14) and TotalReceived
(D15:G15), as well as the
specifications needed to set
up the model. The changing
cells ShipmentQuantity
(D12:G14) show the optimal
shipping plan obtained by
the Solver.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 321© The McGraw−Hill
Companies, 2010
8.1 THE TRANSPORTATION PROBLEM 313
the decision variables. This optimal solution is shown in ShipmentQuantity (D12:G14) in
Fig. 8.4, along with the resulting value $152,535 in the target cell TotalCost (J17).
Note that the Solver simply uses the general simplex method to solve a transporta-
tion problem rather than a streamlined version that is specially designed for solving trans-
portation problems very efficiently, such as the transportation simplex method presented
in the next section. Therefore, a software package that includes such a streamlined ver-
sion should solve a large transportation problem much faster than the Excel Solver.
We mentioned earlier that some problems do not quite fit the model for a transportation
problem because they violate the requirements assumption, but that it is possible to re-
formulate such a problem to fit this model by introducing a dummy destination or a dummy
source. When using the Excel Solver, it is not necessary to do this reformulation since the
simplex method can solve the original model where the supply constraints are in � form
or the demand constraints are in � form. (The Excel files for the next two examples in
your OR Courseware illustrate spreadsheet formulations that retain either the supply con-
straints or the demand constraints in their original inequality form.) However, the larger
the problem, the more worthwhile it becomes to do the reformulation and use the trans-
portation simplex method (or equivalent) instead with another software package.
The next two examples illustrate how to do this kind of reformulation.
An Example with a Dummy Destination
The NORTHERN AIRPLANE COMPANY builds commercial airplanes for various airline
companies around the world. The last stage in the production process is to produce the jet
engines and then to install them (a very fast operation) in the completed airplane frame.
The company has been working under some contracts to deliver a considerable number of
airplanes in the near future, and the production of the jet engines for these planes must
now be scheduled for the next four months.
To meet the contracted dates for delivery, the company must supply engines for in-
stallation in the quantities indicated in the second column of Table 8.7. Thus, the cumu-
lative number of engines produced by the end of months 1, 2, 3, and 4 must be at least
10, 25, 50, and 70, respectively.
The facilities that will be available for producing the engines vary according to other
production, maintenance, and renovation work scheduled during this period. The result-
ing monthly differences in the maximum number that can be produced and the cost
(in millions of dollars) of producing each one are given in the third and fourth columns
of Table 8.7.
Because of the variations in production costs, it may well be worthwhile to produce
some of the engines a month or more before they are scheduled for installation, and this
possibility is being considered. The drawback is that such engines must be stored until
the scheduled installation (the airplane frames will not be ready early) at a storage cost
of $15,000 per month (including interest on expended capital) for each engine,1 as shown
in the rightmost column of Table 8.7.
The production manager wants a schedule developed for the number of engines to be
produced in each of the four months so that the total of the production and storage costs
will be minimized.
Formulation. One way to formulate a mathematical model for this problem is to let xj
be the number of jet engines to be produced in month j, for j � 1, 2, 3, 4. By using only
1For modeling purposes, assume that this storage cost is incurred at the end of the month for just those engines
that are being held over into the next month. Thus, engines that are produced in a given month for installation
in the same month are assumed to incur no storage cost.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text322 © The McGraw−Hill
Companies, 2010
314 CHAPTER 8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
these four decision variables, the problem can be formulated as a linear programming
problem that does not fit the transportation problem type. (See Prob. 8.2-18.)
On the other hand, by adopting a different viewpoint, we can instead formulate the
problem as a transportation problem that requires much less effort to solve. This view-
point will describe the problem in terms of sources and destinations and then identify the
corresponding xij, cij, si, and dj. (See if you can do this before reading further.)
Because the units being distributed are jet engines, each of which is to be scheduled
for production in a particular month and then installed in a particular (perhaps different)
month,
Source i � production of jet engines in month i (i � 1, 2, 3, 4)
Destination j � installation of jet engines in month j ( j � 1, 2, 3, 4)
xij � number of engines produced in month i for installation in month j
cij � cost associated with each unit of xij
� �
si � ?
dj � number of scheduled installations in month j.
The corresponding (incomplete) parameter table is given in Table 8.8. Thus, it remains to
identify the missing costs and the supplies.
Since it is impossible to produce engines in one month for installation in an earlier
month, xij must be zero if i � j. Therefore, there is no real cost that can be associated with
such xij. Nevertheless, in order to have a well-defined transportation problem to which the
solution procedure of Sec. 8.2 can be applied, it is necessary to assign some value for the
unidentified costs. Fortunately, we can use the Big M method introduced in Sec. 4.6 to
if i � j
if i � j
cost per unit for production and any storage
?
■ TABLE 8.8 Incomplete parameter table for Northern Airplane Co.
Cost per Unit Distributed
Destination
1 2 3 4 Supply
1 1.080 1.095 1.110 1.125 ?
2 ? 1.110 1.125 1.140 ?
Source
3 ? ? 1.100 1.115 ?
4 ? ? ? 1.130 ?
Demand 10 15 25 20
■ TABLE 8.7 Production scheduling data for Northern Airplane Co.
Scheduled Maximum Unit Cost* Unit Cost*
Month Installations Production of Production of Storage
1 10 25 1.08 0.015
2 15 35 1.11 0.015
3 25 30 1.10 0.015
4 20 10 1.13
*Cost is expressed in millions of dollars.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 323© The McGraw−Hill
Companies, 2010
8.1 THE TRANSPORTATION PROBLEM 315
assign this value. Thus, we assign a very large number (denoted by M for convenience)
to the unidentified cost entries in Table 8.8 to force the corresponding values of xij to be
zero in the final solution.
The numbers that need to be inserted into the supply column of Table 8.8 are not ob-
vious because the “supplies,” the amounts produced in the respective months, are not fixed
quantities. In fact, the objective is to solve for the most desirable values of these production
quantities. Nevertheless, it is necessary to assign some fixed number to every entry in the
table, including those in the supply column, to have a transportation problem. A clue is pro-
vided by the fact that although the supply constraints are not present in the usual form, these
constraints do exist in the form of upper bounds on the amount that can be supplied, namely,
x11 � x12 � x13 � x14 � 25,
x21 � x22 � x23 � x24 � 35,
x31 � x32 � x33 � x34 � 30,
x41 � x42 � x43 � x44 � 10.
The only change from the standard model for the transportation problem is that these con-
straints are in the form of inequalities instead of equalities.
To convert these inequalities to equations in order to fit the transportation problem
model, we use the familiar device of slack variables, introduced in Sec. 4.2. In this con-
text, the slack variables are allocations to a single dummy destination that represent the
unused production capacity in the respective months. This change permits the supply in
the transportation problem formulation to be the total production capacity in the given
month. Furthermore, because the demand for the dummy destination is the total unused
capacity, this demand is
(25 � 35 � 30 � 10) � (10 � 15 � 25 � 20) � 30.
With this demand included, the sum of the supplies now equals the sum of the demands,
which is the condition given by the feasible solutions property for having feasible solutions.
The cost entries associated with the dummy destination should be zero because there
is no cost incurred by a fictional allocation. (Cost entries of M would be inappropriate
for this column because we do not want to force the corresponding values of xij to be
zero. In fact, these values need to sum to 30.)
The resulting final parameter table is given in Table 8.9, with the dummy destination
labeled as destination 5(D). By using this formulation, it is quite easy to find the optimal
production schedule by the solution procedure described in Sec. 8.2. (See Prob. 8.2-10
and its answer in the back of the book.)
■ TABLE 8.9 Complete parameter table for Northern Airplane Co.
Cost per Unit Distributed
Destination
1 2 3 4 5(D) Supply
1 1.080 1.095 1.110 1.125 0 25
2 M 1.110 1.125 1.140 0 35
Source
3 M M 1.100 1.115 0 30
4 M M M 1.130 0 10
Demand 10 15 25 20 30
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text324 © The McGraw−Hill
Companies, 2010
316 CHAPTER 8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
An Example with a Dummy Source
METRO WATER DISTRICT is an agency that administers water distribution in a large ge-
ographic region. The region is fairly arid, so the district must purchase and bring in water
from outside the region. The sources of this imported water are the Colombo, Sacron, and
Calorie rivers. The district then resells the water to users in the region. Its main customers
are the water departments of the cities of Berdoo, Los Devils, San Go, and Hollyglass.
It is possible to supply any of these cities with water brought in from any of the three
rivers, with the exception that no provision has been made to supply Hollyglass with Calo-
rie River water. However, because of the geographic layouts of the aqueducts and the cities
in the region, the cost to the district of supplying water depends upon both the source of
the water and the city being supplied. The variable cost per acre foot of water (in tens of
dollars) for each combination of river and city is given in Table 8.10. Despite these vari-
ations, the price per acre foot charged by the district is independent of the source of the
water and is the same for all cities.
The management of the district is now faced with the problem of how to allocate the
available water during the upcoming summer season. In units of 1 million acre feet, the
amounts available from the three rivers are given in the rightmost column of Table 8.10.
The district is committed to providing a certain minimum amount to meet the essential
needs of each city (with the exception of San Go, which has an independent source of
water), as shown in the minimum needed row of the table. The requested row indicates
that Los Devils desires no more than the minimum amount, but that Berdoo would like
to buy as much as 20 more, San Go would buy up to 30 more, and Hollyglass will take
as much as it can get.
Management wishes to allocate all the available water from the three rivers to the
four cities in such a way as to at least meet the essential needs of each city while mini-
mizing the total cost to the district.
Formulation. Table 8.10 already is close to the proper form for a parameter table, with
the rivers being the sources and the cities being the destinations. However, the one basic
difficulty is that it is not clear what the demands at the destinations should be. The amount
to be received at each destination (except Los Devils) actually is a decision variable, with
both a lower bound and an upper bound. This upper bound is the amount requested un-
less the request exceeds the total supply remaining after the minimum needs of the other
cities are met, in which case this remaining supply becomes the upper bound. Thus, in-
satiably thirsty Hollyglass has an upper bound of
(50 � 60 � 50) � (30 � 70 � 0) � 60.
Unfortunately, just like the other numbers in the parameter table of a transportation
problem, the demand quantities must be constants, not bounded decision variables. To
■ TABLE 8.10 Water resources data for Metro Water District
Cost (Tens of Dollars) per Acre Foot
Berdoo Los Devils San Go Hollyglass Supply
Colombo River 16 13 22 17 50
Sacron River 14 13 19 15 60
Calorie River 19 20 23 — 50
Minimum needed 30 70 0 10 (in units of 1
Requested 50 70 30 � million acre feet)
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 325© The McGraw−Hill
Companies, 2010
8.1 THE TRANSPORTATION PROBLEM 317
begin resolving this difficulty, temporarily suppose that it is not necessary to satisfy the
minimum needs, so that the upper bounds are the only constraints on amounts to be al-
located to the cities. In this circumstance, can the requested allocations be viewed as the
demand quantities for a transportation problem formulation? After one adjustment, yes!
(Do you see already what the needed adjustment is?)
The situation is analogous to Northern Airplane Co.’s production scheduling prob-
lem, where there was excess supply capacity. Now there is excess demand capacity. Con-
sequently, rather than introducing a dummy destination to “receive” the unused supply
capacity, the adjustment needed here is to introduce a dummy source to “send” the un-
used demand capacity. The imaginary supply quantity for this dummy source would be
the amount by which the sum of the demands exceeds the sum of the real supplies:
(50 � 70 � 30 � 60) � (50 � 60 � 50) � 50.
This formulation yields the parameter table shown in Table 8.11, which uses units of
million acre feet and tens of millions of dollars. The cost entries in the dummy row are
zero because there is no cost incurred by the fictional allocations from this dummy source.
On the other hand, a huge unit cost of M is assigned to the Calorie River–Hollyglass spot.
The reason is that Calorie River water cannot be used to supply Hollyglass, and assign-
ing a cost of M will prevent any such allocation.
Now let us see how we can take each city’s minimum needs into account in this kind
of formulation. Because San Go has no minimum need, it is all set. Similarly, the for-
mulation for Hollyglass does not require any adjustments because its demand (60) ex-
ceeds the dummy source’s supply (50) by 10, so the amount supplied to Hollyglass from
the real sources will be at least 10 in any feasible solution. Consequently, its minimum
need of 10 from the rivers is guaranteed. (If this coincidence had not occurred, Hollyglass
would need the same adjustments that we shall have to make for Berdoo.)
Los Devils’ minimum need equals its requested allocation, so its entire demand of 70
must be filled from the real sources rather than the dummy source. This requirement calls
for the Big M method! Assigning a huge unit cost of M to the allocation from the dummy
source to Los Devils ensures that this allocation will be zero in an optimal solution.
Finally, consider Berdoo. In contrast to Hollyglass, the dummy source has an ade-
quate (fictional) supply to “provide” at least some of Berdoo’s minimum need in addition
to its extra requested amount. Therefore, since Berdoo’s minimum need is 30, adjustments
must be made to prevent the dummy source from contributing more than 20 to Berdoo’s
total demand of 50. This adjustment is accomplished by splitting Berdoo into two desti-
nations, one having a demand of 30 with a unit cost of M for any allocation from the
dummy source and the other having a demand of 20 with a unit cost of zero for the dummy
source allocation. This formulation gives the final parameter table shown in Table 8.12.
■ TABLE 8.11 Parameter table without minimum needs for Metro Water District
Cost (Tens of Millions of Dollars) per Unit Distributed
Destination
Berdoo Los Devils San Go Hollyglass Supply
Colombo River 16 13 22 17 50
Sacron River 14 13 19 15 60
Source
Calorie River 19 20 23 M 50
Dummy 0 0 0 0 50
Demand 50 70 30 60
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text326 © The McGraw−Hill
Companies, 2010
318 CHAPTER 8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
2For example, see K. Holmberg and H. Tuy: “A Production-Transportation Problem with Stochastic Demand
and Concave Production Costs,” Mathematical Programming Series A, 85: 157–179, 1999.
This problem will be solved in Sec. 8.2 to illustrate the solution procedure pre-
sented there.
Generalizations of the Transportation Problem
Even after the kinds of reformulations illustrated by the two preceding examples, some
problems involving the distribution of units from sources to destinations fail to satisfy the
model for the transportation problem. One reason may be that the distribution does not
go directly from the sources to the destinations but instead passes through transfer points
along the way. The Distribution Unlimited Co example in Sec. 3.4 (See Fig. 3.13) illus-
trates such a problem. In this case, the sources are the two factories and the destinations
are the two warehouses. However, a shipment from a particular factory to a particular
warehouse may first get transferred at a distribution center, or even at the other factory or
the other warehouse, before reaching its destination. The unit shipping costs differ for
these different shipping lanes. Furthermore, there are upper limits on how much can be
shipped through some of the shipping lanes. Although it is not a transportation problem,
this kind of problem still is a special type of linear programming problem, called the min-
imum cost flow problem, that will be discussed in Sec. 9.6. The network simplex method
described in Sec. 9.7 provides an efficient way of solving minimum cost flow problems.
A minimum cost flow problem that does not impose any upper limits on how much can be
shipped through the shipping lanes is referred to as a transshipment problem. Section 23.1
on the book’s website is devoted to discussing transshipment problems.
In other cases, the distribution may go directly from sources to destinations, but other
assumptions of the transportation problem may be violated. The cost assumption will be
violated if the cost of distributing units from any particular source to any particular des-
tination is a nonlinear function of the number of units distributed. The requirements as-
sumption will be violated if either the supplies from the sources or the demands at the
destinations are not fixed. For example, the final demand at a destination may not become
known until after the units have arrived and then a nonlinear cost is incurred if the amount
received deviates from the final demand. If the supply at a source is not fixed, the cost of
producing the amount supplied may be a nonlinear function of this amount. For example,
a fixed cost may be part of the cost associated with a decision to open up a new source.
Considerable research has been done to generalize the transportation problem and its so-
lution procedure in these kinds of directions.2
■ TABLE 8.12 Parameter table for Metro Water District
Cost (Tens of Millions of Dollars) per Unit Distributed
Destination
Berdoo (min.) Berdoo (extra) Los Devils San Go Hollyglass
1 2 3 4 5 Supply
Source Colombo River 1(D) 16 16 13 22 17 50
Source
Sacron River 2(D) 14 14 13 19 15 60
Source
Calorie River 3(D) 19 19 20 23 M 50
Source Dummy 4(D) M 0 M 0 0 50
Demand 30 20 70 30 60
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text342 © The McGraw−Hill
Companies, 2010
334 CHAPTER 8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
10For example, see L. J. LeBlanc, D. Randels, Jr., and T. K. Swann: “Heery International’s Spreadsheet Opti-
mization Model for Assigning Managers to Construction Projects,” Interfaces, 30(6): 95–106, Nov.–Dec. 2000.
Page 98 of this article also cites seven other applications of the assignment problem.
The assignment problem is a special type of linear programming problem where as-
signees are being assigned to perform tasks. For example, the assignees might be em-
ployees who need to be given work assignments. Assigning people to jobs is a common
application of the assignment problem.10 However, the assignees need not be people. They
also could be machines, or vehicles, or plants, or even time slots to be assigned tasks. The
first example below involves machines being assigned to locations, so the tasks in this
case simply involve holding a machine. A subsequent example involves plants being as-
signed products to be produced.
To fit the definition of an assignment problem, these kinds of applications need to be
formulated in a way that satisfies the following assumptions.
1. The number of assignees and the number of tasks are the same. (This number is de-
noted by n.)
2. Each assignee is to be assigned to exactly one task.
3. Each task is to be performed by exactly one assignee.
4. There is a cost cij associated with assignee i (i � 1, 2, . . . , n) performing task j
( j � 1, 2, . . . , n).
5. The objective is to determine how all n assignments should be made to minimize the
total cost.
Any problem satisfying all these assumptions can be solved extremely efficiently by al-
gorithms designed specifically for assignment problems.
The first three assumptions are fairly restrictive. Many potential applications do not
quite satisfy these assumptions. However, it often is possible to reformulate the problem
to make it fit. For example, dummy assignees or dummy tasks frequently can be used for
this purpose. We illustrate these formulation techniques in the examples.
Prototype Example
The JOB SHOP COMPANY has purchased three new machines of different types. There
are four available locations in the shop where a machine could be installed. Some of these
locations are more desirable than others for particular machines because of their proxim-
ity to work centers that will have a heavy work flow to and from these machines. (There
will be no work flow between the new machines.) Therefore, the objective is to assign the
new machines to the available locations to minimize the total cost of materials handling.
The estimated cost in dollars per hour of materials handling involving each of the ma-
chines is given in Table 8.24 for the respective locations. Location 2 is not considered
suitable for machine 2, so no cost is given for this case.
To formulate this problem as an assignment problem, we must introduce a dummy
machine for the extra location. Also, an extremely large cost M should be attached to the
assignment of machine 2 to location 2 to prevent this assignment in the optimal solution.
The resulting assignment problem cost table is shown in Table 8.25. This cost table con-
tains all the necessary data for solving the problem. The optimal solution is to assign ma-
chine 1 to location 4, machine 2 to location 3, and machine 3 to location 1, for a total
cost of $29 per hour. The dummy machine is assigned to location 2, so this location is
available for some future real machine.
■ 8.3 THE ASSIGNMENT PROBLEM
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 343© The McGraw−Hill
Companies, 2010
8.3 THE ASSIGNMENT PROBLEM 335
We shall discuss how this solution is obtained after we formulate the mathematical
model for the general assignment problem.
The Assignment Problem Model
The mathematical model for the assignment problem uses the following decision variables:
xij � �
for i � 1, 2, . . . , n and j � 1, 2, . . . , n. Thus, each xij is a binary variable (it has value
0 or 1). As discussed at length in the chapter on integer programming (Chap. 11), binary
variables are important in OR for representing yes/no decisions. In this case, the yes/no
decision is: Should assignee i perform task j?
By letting Z denote the total cost, the assignment problem model is
Minimize Z � �
n
i�1
�
n
j�1
cijxij,
subject to
�
n
j�1
xij � 1 for i � 1, 2, . . . , n,
�
n
i�1
xij � 1 for j � 1, 2, . . . , n,
and
xij � 0, for all i and j
(xij binary, for all i and j).
if assignee i performs task j,
if not,
1
0
■ TABLE 8.24 Materials-handling cost data
($) for Job Shop Co.
Location
1 2 3 4
1 13 16 12 11
Machine 2 15 — 13 20
3 5 7 10 6
■ TABLE 8.25 Cost table for the Job Shop Co.
assignment problem
Task
(Location)
1 2 3 4
1 13 16 12 11
Assignee
2 15 M 13 20
(Machine) 3 5 7 10 6
4(D) 0 0 0 0
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text344 © The McGraw−Hill
Companies, 2010
336 CHAPTER 8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
The first set of functional constraints specifies that each assignee is to perform exactly
one task, whereas the second set requires each task to be performed by exactly one as-
signee. If we delete the parenthetical restriction that the xij be binary, the model clearly
is a special type of linear programming problem and so can be readily solved. Fortu-
nately, for reasons about to unfold, we can delete this restriction. (This deletion is the
reason that the assignment problem appears in this chapter rather than in the integer pro-
gramming chapter.)
Now compare this model (without the binary restriction) with the transportation prob-
lem model presented in the third subsection of Sec. 8.1 (including Table 8.6). Note how
similar their structures are. In fact, the assignment problem is just a special type of trans-
portation problem where the sources now are assignees and the destinations now are tasks
and where
Number of sources m � number of destinations n,
Every supply si � 1,
Every demand dj � 1.
Now focus on the integer solutions property in the subsection on the transporta-
tion problem model. Because si and dj are integers (� 1) now, this property implies
that every BF solution (including an optimal one) is an integer solution for an assign-
ment problem. The functional constraints of the assignment problem model prevent any
variable from being greater than 1, and the nonnegativity constraints prevent values less
than 0. Therefore, by deleting the binary restriction to enable us to solve an assign-
ment problem as a linear programming problem, the resulting BF solutions obtained
(including the final optimal solution) automatically will satisfy the binary restriction
anyway.
Just as the transportation problem has a network representation (see Fig. 8.3), the as-
signment problem can be depicted in a very similar way, as shown in Fig. 8.5. The first
column now lists the n assignees and the second column the n tasks. Each number in a
square bracket indicates the number of assignees being provided at that location in the
network, so the values are automatically 1 on the left, whereas the values of �1 on the
right indicate that each task is using up one assignee.
For any particular assignment problem, practitioners normally do not bother writing
out the full mathematical model. It is simpler to formulate the problem by filling out a
cost table (e.g., Table 8.25), including identifying the assignees and tasks, since this table
contains all the essential data in a far more compact form.
Problems occasionally arise that do not quite fit the model for an assignment prob-
lem because certain assignees will be assigned to more than one task. In this case, the
problem can be reformulated to fit the model by splitting each such assignee into sepa-
rate (but identical) new assignees where each new assignee will be assigned to exactly
one task. (Table 8.29 will illustrate this for a subsequent example.) Similarly, if a task is
to be performed by multiple assignees, that task can be split into separate (but identical)
new tasks where each new task is to be performed by exactly one assignee according to
the reformulated model. The Worked Examples section of the book’s website provides
another example that illustrates both cases and the resulting reformulation to fit the model
for an assignment problem. An alternative formulation as a transportation problem also
is shown.
Solution Procedures for Assignment Problems
Alternative solution procedures are available for solving assignment problems. Problems
that aren’t much larger than the Job Shop Co. example can be solved very quickly by the
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 345© The McGraw−Hill
Companies, 2010
8.3 THE ASSIGNMENT PROBLEM 337
general simplex method, so it may be convenient to simply use a basic software package
(such as Excel and its Solver) that only employs this method. If this were done for the
Job Shop Co. problem, it would not have been necessary to add the dummy machine to
Table 8.25 to make it fit the assignment problem model. The constraints on the number
of machines assigned to each location would be expressed instead as
�
3
i�1
xij � 1 for j � 1, 2, 3, 4.
As shown in the Excel files for this chapter, a spreadsheet formulation for this example
would be very similar to the formulation for a transportation problem displayed in
Fig. 8.4 except now all the supplies and demands would be 1 and the demand constraints
would be �1 instead of � 1.
However, large assignment problems can be solved much faster by using more spe-
cialized solution procedures, so we recommend using such a procedure instead of the gen-
eral simplex method for big problems.
Because the assignment problem is a special type of transportation problem, one con-
venient and relatively fast way to solve any particular assignment problem is to apply the
transportation simplex method described in Sec. 8.2. This approach requires converting
the cost table to a parameter table for the equivalent transportation problem, as shown in
Table 8.26a.
For example, Table 8.26b shows the parameter table for the Job Shop Co. problem
that is obtained from the cost table of Table 8.25. When the transportation simplex method
is applied to this transportation problem formulation, the resulting optimal solution has
c11
c12
c21
c22
c
2n
c n1
cnn
c n2
c
1n
A1
[1] [�1]
[1] [�1]
An[1] [�1]
T1
A2 T2
Tn
■ FIGURE 8.5
Network representation of
the assignment problem.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text346 © The McGraw−Hill
Companies, 2010
338 CHAPTER 8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
basic variables x13 � 0, x14 � 1, x23 � 1, x31 � 1, x41 � 0, x42 � 1, x43 � 0. (You are
asked to verify this solution in Prob. 8.3-6.). The degenerate basic variables (xi j � 0)
and the assignment for the dummy machine (x42 � 1) do not mean anything for the orig-
inal problem, so the real assignments are machine 1 to location 4, machine 2 to loca-
tion 3, and machine 3 to location 1.
It is no coincidence that this optimal solution provided by the transportation simplex
method has so many degenerate basic variables. For any assignment problem with n as-
signments to be made, the transportation problem formulation shown in Table 8.26a has
m � n, that is, both the number of sources (m) and the number of destinations (n) in this
formulation equal the number of assignments (n). Transportation problems in general have
m � n � 1 basic variables (allocations), so every BF solution for this particular kind of
transportation problem has 2n � 1 basic variables, but exactly n of these xij equal 1 (cor-
responding to the n assignments being made). Therefore, since all the variables are binary
variables, there always are n � 1 degenerate basic variables (xij � 0). As discussed at the
end of Sec. 8.2, degenerate basic variables do not cause any major complication in the
execution of the algorithm. However, they do frequently cause wasted iterations, where
nothing changes (same allocations) except for the labeling of which allocations of zero
correspond to degenerate basic variables rather than nonbasic variables. These wasted it-
erations are a major drawback to applying the transportation simplex method in this kind
of situation, where there always are so many degenerate basic variables.
Another drawback of the transportation simplex method here is that it is purely a
general-purpose algorithm for solving all transportation problems. Therefore, it does noth-
ing to exploit the additional special structure in this special type of transportation problem
(m � n, every si � 1, and every dj � 1). Fortunately, specialized algorithms have been de-
veloped to fully streamline the procedure for solving just assignment problems. These algo-
rithms operate directly on the cost table and do not bother with degenerate basic variables.
When a computer code is available for one of these algorithms, it generally should be used
in preference to the transportation simplex method, especially for really big problems.11
Section 8.4 describes one of these specialized algorithms (called the Hungarian al-
gorithm) for solving only assignment problems very efficiently.
11For an article comparing various algorithms for the assignment problem, see J. L. Kennington and Z. Wang:“An
Empirical Analysis of the Dense Assignment Problem: Sequential and Parallel Implementations,” ORSA Journal
on Computing, 3: 299–306, 1991.
■ TABLE 8.26 Parameter table for the assignment problem formulated as a transportation problem, illustrated
by the Job Shop Co. example
(a) General Case
Cost per Unit
Distributed
Destination
1 2 … n Supply
1 c11 c12 … c1n 1
2 c21 c22 … c2n 1Source
� … … … … �
m � n cn1 cn2 … cnn 1
Demand 1 1 … 1
(b) Job Shop Co. Example
Cost per Unit
Distributed
Destination (Location)
1 2 3 4 Supply
1 13 16 12 11 1
Source 2 15 M 13 20 1
(Machine) 3 5 7 10 6 1
4(D) 0 0 0 0 1
Demand 1 1 1 1
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 347© The McGraw−Hill
Companies, 2010
8.3 THE ASSIGNMENT PROBLEM 339
Your IOR Tutorial includes both an interactive procedure and an automatic procedure
for applying this algorithm.
Example—Assigning Products to Plants
The BETTER PRODUCTS COMPANY has decided to initiate the production of four
new products, using three plants that currently have excess production capacity. The
products require a comparable production effort per unit, so the available production
capacity of the plants is measured by the number of units of any product that can be
produced per day, as given in the rightmost column of Table 8.27. The bottom row gives
the required production rate per day to meet projected sales. Each plant can produce
any of these products, except that Plant 2 cannot produce product 3. However, the vari-
able costs per unit of each product differ from plant to plant, as shown in the main body
of Table 8.27.
Management now needs to make a decision on how to split up the production of the
products among plants. Two kinds of options are available.
Option 1: Permit product splitting, where the same product is produced in more than one
plant.
Option 2: Prohibit product splitting.
This second option imposes a constraint that can only increase the cost of an optimal
solution based on Table 8.27. On the other hand, the key advantage of Option 2 is
that it eliminates some hidden costs associated with product splitting that are not re-
flected in Table 8.27, including extra setup, distribution, and administration costs.
Therefore, management wants both options analyzed before a final decision is made.
For Option 2, management further specifies that every plant should be assigned at
least one of the products.
We will formulate and solve the model for each option in turn, where Option 1 leads
to a transportation problem and Option 2 leads to an assignment problem.
Formulation of Option 1. With product splitting permitted, Table 8.27 can be con-
verted directly to a parameter table for a transportation problem. The plants become the
sources, and the products become the destinations (or vice versa), so the supplies are
the available production capacities and the demands are the required production rates.
Only two changes need to be made in Table 8.27. First, because Plant 2 cannot produce
product 3, such an allocation is prevented by assigning to it a huge unit cost of M. Sec-
ond, the total capacity (75 � 75 � 45 � 195) exceeds the total required production
(20 � 30 � 30 � 40 � 120), so a dummy destination with a demand of 75 is needed to
balance these two quantities. The resulting parameter table is shown in Table 8.28.
The optimal solution for this transportation problem has basic variables (allocations)
x12 � 30, x13 � 30, x15 � 15, x24 � 15, x25 � 60, x31 � 20, and x34 � 25, so
■ TABLE 8.27 Data for the Better Products Co. problem
Unit Cost ($) for Product
Capacity
1 2 3 4 Available
1 41 27 28 24 75
Plant 2 40 29 — 23 75
3 37 30 27 21 45
Production rate 20 30 30 40
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text348 © The McGraw−Hill
Companies, 2010
340 CHAPTER 8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
Plant 1 produces all of products 2 and 3.
Plant 2 produces 37.5 percent of product 4.
Plant 3 produces 62.5 percent of product 4 and all of product 1.
The total cost is Z � $3,260 per day.
Formulation of Option 2. Without product splitting, each product must be assigned
to just one plant. Therefore, producing the products can be interpreted as the tasks for an
assignment problem, where the plants are the assignees.
Management has specified that every plant should be assigned at least one of the prod-
ucts. There are more products (four) than plants (three), so one of the plants will need to
be assigned two products. Plant 3 has only enough excess capacity to produce one prod-
uct (see Table 8.27), so either Plant 1 or Plant 2 will take the extra product.
To make this assignment of an extra product possible within an assignment problem
formulation, Plants 1 and 2 each are split into two assignees, as shown in Table 8.29.
The number of assignees (now five) must equal the number of tasks (now four), so
a dummy task (product) is introduced into Table 8.29 as 5(D). The role of this dummy
task is to provide the fictional second product to either Plant 1 or Plant 2, whichever one
receives only one real product. There is no cost for producing a fictional product so, as
usual, the cost entries for the dummy task are zero. The one exception is the entry of M
in the last row of Table 8.29. The reason for M here is that Plant 3 must be assigned a
real product (a choice of product 1, 2, 3, or 4), so the Big M method is needed to prevent
the assignment of the fictional product to Plant 3 instead. (As in Table 8.28, M also is
used to prevent the infeasible assignment of product 3 to Plant 2.)
The remaining cost entries in Table 8.29 are not the unit costs shown in Tables 8.27
or 8.28. Table 8.28 gives a transportation problem formulation (for Option 1), so unit costs
■ TABLE 8.28 Parameter table for the transportation problem formulation of
Option 1 for the Better Products Co. problem
Cost per Unit Distributed
Destination (Product)
1 2 3 4 5(D) Supply
1 41 27 28 24 0 75
Source
2 40 29 M 23 0 75
(Plant)
3 37 30 27 21 0 45
Demand 20 30 30 40 75
■ TABLE 8.29 Cost table for the assignment problem formulation of Option 2 for
the Better Products Co. problem
Task (Product)
1 2 3 4 5(D)
1a 820 810 840 960 0
1b 820 810 840 960 0
Assignee
2a 800 870 M 920 0
(Plant)
2b 800 870 M 920 0
3 740 900 810 840 M
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 349© The McGraw−Hill
Companies, 2010
8.3 THE ASSIGNMENT PROBLEM 341
are appropriate there, but now we are formulating an assignment problem (for Option 2).
For an assignment problem, the cost cij is the total cost associated with assignee i per-
forming task j. For Table 8.29, the total cost (per day) for Plant i to produce product j is
the unit cost of production times the number of units produced (per day), where these two
quantities for the multiplication are given separately in Table 8.27. For example, consider
the assignment of Plant 1 to product 1. By using the corresponding unit cost in Table 8.28
($41) and the corresponding demand (number of units produced per day) in Table 8.28
(20), we obtain
Cost of Plant 1 producing one unit of product 1 � $41
Required (daily) production of product 1 � 20 units
Total (daily) cost of assigning plant 1 to product 1 � 20 ($41)
� $820
so 820 is entered into Table 8.29 for the cost of either Assignee 1a or 1b performing Task 1.
The optimal solution for this assignment problem is as follows:
Plant 1 produces products 2 and 3.
Plant 2 produces product 1.
Plant 3 produces product 4.
Here the dummy assignment is given to Plant 2. The total cost is Z � $3,290 per day.
As usual, one way to obtain this optimal solution is to convert the cost table of Table
8.29 to a parameter table for the equivalent transportation problem (see Table 8.26) and
then apply the transportation simplex method. Because of the identical rows in Table
8.29, this approach can be streamlined by combining the five assignees into three sources
with supplies 2, 2, and 1, respectively. (See Prob. 8.3-5.) This streamlining also decreases
by two the number of degenerate basic variables in every BF solution. Therefore, even
though this streamlined formulation no longer fits the format presented in Table 8.26a
for an assignment problem, it is a more efficient formulation for applying the trans-
portation simplex method.
Figure 8.6 shows how Excel and its Solver can be used to obtain this optimal solu-
tion, which is displayed in the changing cells Assignment (C19:F21) of the spreadsheet.
Since the general simplex method is being used, there is no need to fit this formulation
into the format for either the assignment problem or transportation problem model. There-
fore, the formulation does not bother to split Plants 1 and 2 into two assignees each, or
to add a dummy task. Instead, Plants 1 and 2 are given a supply of 2 each, and then �
signs are entered into cells H19 and H20 as well as into the corresponding constraints in
the Solver dialogue box. There also is no need to include the Big M method to prohibit
assigning product 3 to Plant 2 in cell E20, since this dialogue box includes the constraint
that E20 � 0. The target cell TotalCost (I24) shows the total cost of $3,290 per day.
Now look back and compare this solution to the one obtained for Option 1, which
included the splitting of product 4 between Plants 2 and 3. The allocations are somewhat
different for the two solutions, but the total daily costs are virtually the same ($3,260 for
Option 1 versus $3,290 for Option 2). However, there are hidden costs associated with
product splitting (including the cost of extra setup, distribution, and administration) that
are not included in the objective function for Option 1. As with any application of OR,
the mathematical model used can provide only an approximate representation of the total
problem, so management needs to consider factors that cannot be incorporated into the
model before it makes a final decision. In this case, after evaluating the disadvantages of
product splitting, management decided to adopt the Option 2 solution.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text350 © The McGraw−Hill
Companies, 2010
In Sec. 8.3, we pointed out that the transportation simplex method can be used to solve
assignment problems but that a specialized algorithm designed for such problems should
be more efficient. We now will describe a classic algorithm of this type. It is called the
Hungarian algorithm (or Hungarian method) because it was developed by Hungarian
mathematicians. We will focus just on the key ideas without filling in all the details needed
for a complete computer implementation.
The Role of Equivalent Cost Tables
The algorithm operates directly on the cost table for the problem. More precisely, it converts
the original cost table into a series of equivalent cost tables until it reaches one where an op-
timal solution is obvious. This final equivalent cost table is one consisting of only positive or
342 CHAPTER 8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
■ 8.4 A SPECIAL ALGORITHM FOR THE ASSIGNMENT PROBLEM
11
12
13
14
B C D E F
Cost ($/day) Product 1 Product 2 Product 3 Product 4
Plant 1 =C4*C$8 =D4*D$8 =E4*E$8 =F4*F$8
Plant 2 =C5*C$8 =D5*D$8 – =F5*F$8
Plant 3 =C6*C$8 =D6*D$8 =E6*E$8 =F6*F$8
17
18
19
20
21
G
Total
Assignments
=SUM(C19:F19)
=SUM(C20:F20)
=SUM(C21:F21)
Range Name Cells
Assignment C19:F21
Cost C12:F14
Demand C24:F24
RequiredProduction C8:F 8
Supply I19:I21
TotalAssigned C22:F22
TotalAssignments G19:G21
TotalCost I24
UnitCost C4:F 6
23
24
I
Total Cost
=SUMPRODUCT(Cost,Assignment)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
A B C D E F G H I
Better Products Co. Production Planning Problem (Option 2)
Unit Cost Product 1 Product 2 Product 3 Product 4
Plant 1 $41 $27 $28 $24
Plant 2 $40 $29 – $23
Plant 3 $37 $30 $27 $21
Required Production 20 30 30 40
Cost ($/day) Product 1 Product 2 Product 3 Product 4
Plant 1 $820 $810 $840 $960
Plant 2 $800 $870 – $920
Plant 3 $740 $900 $810 $840
Total
Assignment Product 1 Product 2 Product 3 Product 4 Assignments Supply
Plant 1 0 1 1 0 2 <= 2 Plant 2 1 0 0 0 1 <= 2 Plant 3 0 0 0 1 1 = 1
Total Assigned 1 1 1 1
= = = = Total Cost
Demand 1 1 1 1 $3,290
22
B C D E F
Total Assigned =SUM(C19:C21) =SUM(D19:D21) =SUM(E19:E21) =SUM(F19:F21)
■ FIGURE 8.6
A spreadsheet formulation of
Option 2 for the Better
Products Co. problem as a
variant of an assignment
problem. The target cell is
TotalCost (I24) and the other
output cells are Cost
(C12:F14), TotalAssignments
(G19:G21), and
TotalAssigned (C22:F22),
where the equations entered
into these cells are shown
below the spreadsheet. The
values of 1 in the changing
cells Assignment (C19:F21)
display the optimal
production plan obtained by
the Solver.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 351© The McGraw−Hill
Companies, 2010
8.4 A SPECIAL ALGORITHM FOR THE ASSIGNMENT PROBLEM 343
1 2 3 4
1 2 5 1 0
2 15 M 13 20
3 5 7 10 6
4(D) 0 0 0 0
Since any feasible solution must have exactly one assignment in row 1, the total cost for
the new table must always be exactly 11 less than for the old table. Hence, the solution
which minimizes total cost for one table must also minimize total cost for the other.
Notice that, whereas the original cost table had only strictly positive elements in the
first three rows, the new table has a zero element in row 1. Since the objective is to
obtain enough strategically located zero elements to yield a complete set of assignments,
this process should be continued on the other rows and columns. Negative elements are
to be avoided, so the constant to be subtracted should be the minimum element in the row
or column. Doing this for rows 2 and 3 yields the following equivalent cost table:
12The individual rows and columns actually can be reduced in any order, but starting with all the rows and then
doing all the columns provides one systematic way of executing the algorithm.
zero elements where all the assignments can be made to the zero element positions. Since
the total cost cannot be negative, this set of assignments with a zero total cost is clearly op-
timal. The question remaining is how to convert the original cost table into this form.
The key to this conversion is the fact that one can add or subtract any constant from every
element of a row or column of the cost table without really changing the problem. That is, an
optimal solution for the new cost table must also be optimal for the old one, and conversely.
Therefore, the algorithm begins by subtracting the smallest number in each row from
every number in the row. This row reduction process will create an equivalent cost table
that has a zero element in every row. If this cost table has any columns without a zero
element, the next step is to perform a column reduction process by subtracting the small-
est number in each such column from every number in the column.12 The new equivalent
cost table will have a zero element in every row and every column. If these zero elements
provide a complete set of assignments, these assignments constitute an optimal solution
and the algorithm if finished.
To illustrate, consider the cost table for the Job Shop Co. problem given in Table 8.25.
To convert this cost table into an equivalent cost table, suppose that we begin the row re-
duction process by subtracting 11 from every element in row 1, which yields:
1 2 3 4
1 2 5 1 0
2 2 M 0 7
3 0 2 5 1
4(D) 0 0 0 0
This cost table has all the zero elements required for a complete set of assignments,
as shown by the four boxes, so these four assignments constitute an optimal solution (as
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text352 © The McGraw−Hill
Companies, 2010
344 CHAPTER 8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
1 2 3 4 5(D)
1a 80 0 30 120 0
1b 80 0 30 120 0
2a 60 60 M 80 0
2b 60 60 M 80 0
3 0 90 0 0 M
claimed in Sec. 8.3 for this problem). The total cost for this optimal solution is seen in
Table 8.25 to be Z � 29, which is just the sum of the numbers that have been subtracted
from rows 1, 2, and 3.
Unfortunately, an optimal solution is not always obtained quite so easily, as we now
illustrate with the assignment problem formulation of Option 2 for the Better Products
Co. problem shown in Table 8.29.
Because this problem’s cost table already has zero elements in every row but the last one,
suppose we begin the process of converting to equivalent cost tables by subtracting the mini-
mum element in each column from every entry in that column. The result is shown below.
1 2 3 4 5(D)
1a 80 0 30 120 0
1b 80 0 30 120 0
2a 60 60 M 80 0
2b 60 60 M 80 0
3 0 90 0 0 M
Now every row and column has at least one zero element, but a complete set of assign-
ments with zero elements is not possible this time. In fact, the maximum number of as-
signments that can be made in zero element positions in only 3. (Try it.) Therefore, one
more idea must be implemented to finish solving this problem that was not needed for
the first example.
The Creation of Additional Zero Elements
This idea involves a new way of creating additional positions with zero elements with-
out creating any negative elements. Rather than subtracting a constant from a single row
or column, we now add or subtract a constant from a combination of rows and columns.
This procedure begins by drawing a set of lines through some of the rows and columns
in such a way as to cover all the zeros. This is done with a minimum number of lines, as
shown in the next cost table.
Notice that the minimum element not crossed out is 30 in the two top positions in col-
umn 3. Therefore, subtracting 30 from every element in the entire table, i.e., from every
row or from every column, will create a new zero element in these two positions. Then,
in order to restore the previous zero elements and eliminate negative elements, we add 30
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 353© The McGraw−Hill
Companies, 2010
8.4 A SPECIAL ALGORITHM FOR THE ASSIGNMENT PROBLEM 345
to each row or column with a line covering it—row 3 and columns 2 and 5(D). This yields
the following equivalent cost table.
1 2 3 4 5(D)
1a 50 0 0 90 0
1b 50 0 0 90 0
2a 30 60 M 50 0
2b 30 60 M 50 0
3 0 120 0 0 M
1 2 3 4 5(D)
1a 50 0 0 90 0
1b 50 0 0 90 0
2a 30 60 M 50 0
2b 30 60 M 50 0
3 0 120 0 0 M
A shortcut for obtaining this cost table from the preceding one is to subtract 30 from
just the elements without a line through them and then add 30 to every element that lies
at the intersection of two lines.
Note that columns 1 and 4 in this new cost table have only a single zero element and
they both are in the same row (row 3). Consequently, it now is possible to make four as-
signments to zero element positions, but still not five. (Try it.) In general, the minimum num-
ber of lines needed to cover all zeros equals the maximum number of assignments that can
be made to zero element positions. Therefore, we repeat the above procedure, where four
lines (the same number as the maximum number of assignments) now are the minimum
needed to cover all zeros. One way of doing this is shown below.
The minimum element not covered by a line is again 30, where this number now appears
in the first position in both rows 2a and 2b. Therefore, we subtract 30 from every uncov-
ered element and add 30 to every doubly covered element (except for ignoring elements
of M), which gives the following equivalent cost table.
1 2 3 4 5(D)
1a 50 0 0 90 30
1b 50 0 0 90 30
2a 0 30 M 20 0
2b 0 30 M 20 0
3 0 120 0 0 M
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text354 © The McGraw−Hill
Companies, 2010
The linear programming model encompasses a wide variety of specific types of problems.
The general simplex method is a powerful algorithm that can solve surprisingly large ver-
sions of any of these problems. However, some of these problem types have such simple
formulations that they can be solved much more efficiently by streamlined algorithms that
exploit their special structure. These streamlined algorithms can cut down tremendously
on the computer time required for large problems, and they sometimes make it computa-
tionally feasible to solve huge problems. This is particularly true for the two types of lin-
ear programming problems studied in this chapter, namely, the transportation problem and
the assignment problem. Both types have a number of common applications, so it is im-
portant to recognize them when they arise and to use the best available algorithms. These
special-purpose algorithms are included in some linear programming software packages.
346 CHAPTER 8 THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
■ 8.5 CONCLUSIONS
This table actually has several ways of making a complete set of assignments to zero
element positions (several optimal solutions), including the one shown by the five boxes.
The resulting total cost is seen in Table 8.29 to be
Z � 810 � 840 � 800 � 0 � 840 � 3,290.
We now have illustrated the entire algorithm, as summarized below.
Summary of the Hungarian Algorithm
1. Subtract the smallest number in each row from every number in the row. (This is called
row reduction.) Enter the results in a new table.
2. Subtract the smallest number in each column of the new table from every number in
the column. (This is called column reduction.) Enter the results in another table.
3. Test whether an optimal set of assignments can be made. You do this by determining
the minimum number of lines needed to cover (i.e., cross out) all zeros. Since this min-
imum number of lines equals the maximum number of assignments that can be made
to zero element positions, if the minimum number of lines equals the number of rows,
an optimal set of assignments is possible. (If you find that a complete set of assign-
ments to zero element positions is not possible, this means that you did not reduce the
number of lines covering all zeros down to the minimum number.) In that case, go to
step 6. Otherwise go on to step 4.
4. If the number of lines is less than the number of rows, modify the table in the fol-
lowing way:
a. Subtract the smallest uncovered number from every uncovered number in the table.
b. Add the smallest uncovered number to the numbers at intersections of covering lines.
c. Numbers crossed out but not at the intersections of cross-out lines carry over un-
changed to the next table.
5. Repeat steps 3 and 4 until an optimal set of assignments is possible.
6. Make the assignments one at a time in positions that have zero elements. Begin with
rows or columns that have only one zero. Since each row and each column needs to
receive exactly one assignment, cross out both the row and the column involved after
each assignment is made. Then move on to the rows and columns that are not yet
crossed out to select the next assignment, with preference again given to any such row
or column that has only one zero that is not crossed out. Continue until every row and
every column has exactly one assignment and so has been crossed out. The complete
set of assignments made in this way is an optimal solution for the problem.
Your IOR Tutorial provides an interactive procedure for applying this algorithm ef-
ficiently. An automatic procedure in included as well.
Hillier−Lieberman:
Introduction to Operations
Research, Ninth Edition
8. The Transportation and
Assignment Problems
Text 355© The McGraw−Hill
Companies, 2010
LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE 347
■ SELECTED REFERENCES
1. Dantzig, G. B., and M. N. Thapa: Linear Programming 1: Introduction, Springer, New York,
1997, chap. 8.
2. Hall, R. W.: Handbook of Transportation Science, 2nd ed., Kluwer Academic Publishers (now
Springer), Boston, 2003.
3. Hillier, F. S., and M. S. Hillier: Introduction to Management Science: A Modeling and Case
Studies Approach with Spreadsheets, 3rd ed., McGraw-Hill/Irwin, Burr Ridge, IL, 2008,
chap. 15.
We shall reexamine the special structure of the transportation and assignment prob-
lems in Sec. 9.6. There we shall see that these problems are special cases of an important
class of linear programming problems known as the minimum cost flow problem. This
problem has the interpretation of minimizing the cost for the flow of goods through a net-
work. A streamlined version of the simplex method called the network simplex method
(described in Sec. 9.7) is widely used for solving this type of problem, including its var-
ious special cases.
A supplementary chapter (Chap. 23) on the book’s website describes various addi-
tional special types of linear programming problems. One of these, called the transship-
ment problem, is a generalization of the transportation problem which allows shipments
from any source to any destination to first go through intermediate transfer points. Since
the transshipment problem also is a special case of the minimum cost flow problem, we
will describe it further in Sec. 9.6.
Much research continues to be devoted to developing streamlined algorithms for spe-
cial types of linear programming problems, including some not discussed here. At the
same time, there is widespread interest in applying linear programming to optimize the
operation of complicated large-scale systems. The resulting formulations usually have spe-
cial structures that can be exploited. Being able to recognize and exploit special structures
is an important factor in the successful application of linear programming.
■ LEARNING AIDS FOR THIS CHAPTER ON OUR WEBSITE (www.mhhe.com/hillier)
Worked Examples:
Examples for Chapter 8
A Demonstration Example in OR Tutor:
The Transportation Problem
Interactive Procedures in IOR Tutorial:
Enter or Revise a Transportation Problem
Find Initial Basic Feasible Solution—for Interactive Method
Solve Interactively by the Transportation Simplex Method
Solve an Assignment Problem Interactively
Automatic Procedures in IOR Tutorial:
Solve Automatically by the Transportation Simplex Method
Solve an Assignment Problem Automatically