—19

Linear Programming

If one would take statistics about which mathematical

problem is using up most of the computer
time in the world, then (not counting database
handling problems like sorting and searching) the
answer would probably be linear programming.
—L. Lovdsz (1980)

Linear programming is the name used for problems in which the objective is to
maximize or minimize a linear function subject to linear inequality constraints.
As the opening quotation from Lovasz indicates, linear programming is a
mathematical technique of immense practical importance. Since its ongins in the
1940s, there have been important theoretical and computational developments, and
its methods are now used every day in many parts of the world.
Because of its extensive use in economic decision problems, all economists
should have some basic knowledge of this theory. However, its importance extends
even beyond its practical applications. In particular, the duality theory of linear
programming is a basis for understanding more complicated opumization problems
with even more interesting economic applications.
In pnnciple, any linear programming problem (often called an LP problem)
can be solved, if a solution exists. The simplex method introduced in 1947 by
G. B. Dantzig is a very efficient numerical procedure that finds the solution in a
finite number of operations. This method will not be discussed in this book. In
fact, for economists. it is probably more important to understand the duality theory
of LP than the details of the simplex method. After all, faced with a nontrivial
LP problem, it is natural to use one of the great number of available LP computer
programs to find the solution.

722
 Sec. 19.1 / Preliminaries 723

19.1 Preliminaries
A general linear programming problem with only two decision variables involves
maximizing or minimizing a linear function

T= CX) + OX (criterion function)

subject to m constraints

Qy)X) +42x2 < dD

2X) + a22X2 < by
(inequality constraints)

Am1X} + Am2X2 < Dm

Usually, we also impose explicit nonnegativity constraints on x; and x2:

x; >0, » >0 (nonnegativity constraints)

Note that the direction of the inequalities in the inequality constraints is a conven-
tion in the sense that any inequality of the form ax; + bx2 > c is equivalent to the
inequality —ax; — bx2 < —c.

A Graphical Approach to Simple LP Problems

LP problems with only two decision variables can be solved by a simple geometric
method.
Example 19.1
A baker has 150 kilograms of flour, 22 kilos of sugar, and 27.5 kilos of butter
with which to make two types of cake. Suppose that making one dozen A
cakes requires 3 kilos of flour, 1 kilo of sugar, and 1 kilo of butter, whereas
making one dozen B cakes requires 6 kilos of flour, 0.5 kilo of sugar. and
1 kilo of butter. Suppose that the profit from one dozen A cakes is 20 and
from one dozen B cakes is 30. How many dozen A cakes (x,) and how
many dozen B cakes (x2) will maximize the baker’s profit?
Solution An output of x; dozen A cakes and x2 dozen B cakes would
need 3x; + 6x2 kilos of flour. Because there are only 150 kilos of flour. the
inequality

3x; + 6x2 < 150 (flour constraint) (1)

must hold. Similanly, for sugar,

x; + 0.5x2 < 22 (sugar constraint) [2]

724 Chapter 19 / Linear Programming

and for butter,

xX} +x. < 27.5 (butter constraint) (3)

Of course, x; > 0 and x2 > 0. The profit obtained from producing x; dozen
A cakes and x2 dozen B cakes is

z = 20x; + 30x [4]

In short, the problem is to

3x; + 6x. < 150

max Zz= 20x; + 30x. s.t. M4 0515-5 2 Xp > 00 oe
oe) SF 5G SIS

This problem will now be solved graphically.

The output pair (x;,x2) is called feasible (or admissible) for prob-
lem [5] if all the five constraints are satisfied. Look at the flour constraint,
which is 3x; + 6x2 < 150. If we use all the flour, then 3x, + 6x. = 150,
and we call this the flour border. We can find similar “borders” for the other
inputs. Figure 19.1 shows the straight lines that represent the flour border,
the sugar border, and the butter border. In order for (x), x2) to be feasible,
it has to be on or below (to the “southwest” of) each of the three borders
simultaneously. Because constraints x; > 0 and x> > 0 restrict (x), x2) to
the nonnegative quadrant, the set of feasible pairs for problem [5], called the
feasible (or admissible) region, is the shaded set S shown in Fig. 19.2. (This
set S is a so-called convex polyhedron, and the five corner points O, A, B,
C, and D are called extreme points of the set S.)

FIGURE 19.1

Flour Border 3x; +6x2=150

Jose Border x; +0.5x.=22

20- . Be Butter Border x} +x2=27.5

 Sec. 19.1 / Preliminaries 725

FIGURE 19.2

In principle, the baker can find the point in the feasible region that
maximizes profit by calculating 20x; + 30x2 at each point of S and picking
the highest value. In practice, this is impossible because there are infinitely
many feasible points. Let us argue this way instead. Can the baker obtain a
profit of 600? If so, the straight line 20x; + 30x. = 600 must have points
in common with S. This line is represented in Fig. 19.2 by dashed line L).
It does have points in common with S. (One of them is (x;. x2) = (0, 20),
where no A cakes are produced, but 20 dozen B cakes are, and the profit
is 20-0+ 30-20 = 600.) Can the baker do better? Yes. For instance, the
straight line 20x; + 30x2 = 601 also has points in common with S and the
profit is 601. In fact, the straight lines

20x; + 30x. =c (c 1S a constant) [6]

are all parallel to 20x; + 30x. = 600. As c increases, the line given by [6]
moves out farther and farther to the northeast. It is clear that the straight line
(6] that has the highest value of c and still has a point in common with S
is dashed line L> in the figure. It touches set $ at point B. Note that B is
at the intersection of the flour border and the butter border. Its coordinates,
therefore, satisfy the two equations:

3x; + 6x. = 150 and xX; +x. = 27.5

Solving these two simultaneous equations yields x; = 5 and x2 = 22.5. So

the baker maximizes profit by baking 5 dozen A cakes and 22.5 dozen B
cakes. This uses all the available flour and butter, but 22—5—0.5-22.5 = 5.75
kilos of sugar are left over. The profit earned is 20x; + 30x2 = 775.

Our next example is a minimization problem.

726 Chapter 19 / Linear Programming

Example 19.2
A firm is producing two goods, A and B. It has two factories that jointly
produce the two goods in the following quantities (per hour):

Factory 1 Factory 2

Good A 10 20
Good B 25 25

The firm receives an order for 300 units of A and 500 units of B. The costs of
operating the two factories are 10,000 and 8000 per hour. Formulate the linear
programming problem of minimizing the total cost of meeting this order.

Solution Let u, and u> be the number of hours that the two factories
operate to produce the order. Then 10u;+20u2 units of good A are produced,
and 25u; + 25u2 units of good B. Because 300 units of A and 500 units of
B are required,
10u; + 20u2 > 300
[1]
25u; + 25u2 > 500

In addition, of course, u; > 0 and uz > 0. The total costs of operating the
two factones for u; and u2 hours, respectively, are 10.000u,;+ 8000 u2. The
problem is, therefore,

10u; + 20u2 > 300

min 10,000u; +8000u2 subject to {
55u, +. Sun > 500. t=O =O
The feasible set S is shown in Fig. 19.3. Because the inequalities in [1]
are of the > type, the feasible set lies to the northeast. We show some of

FIGURE 19.3

30.
25u; + 25u2 = 500

uy
10u, + 20u2 = 300
 Sec. 19.1 / Preliminaries 727

the level curves 10,000u,; + 8000u2 = c, marked L;, Lz, and L;. These
three correspond to the values 100,000; 160,000; and 240,000 of the cost
level c. As c increases, the level curve moves farther and farther to the
northeast.
The solution to the minimization problem is clearly the level curve that
touches the feasible set S at point A with coordinates (0,20). Hence, the
optimal solution is to operate factory 2 for 20 hours and not to use factory
1 at all. The minimum cost of producing the order is 160,000.

The graphical method of solving linear programming problems works well

when there are only two decision variables. It is possible in principle to extend the
method to the case with three decision variables. Then the feasible set is a convex
polyhedron in 3-space, and the level surfaces of the criterion function are planes
in 3-space. However, it is not easy to visualize the solution in such cases. For
more than three decision vanables, no geometric method is available. (By using
duality theory, however, one can solve LP problems geometrically when either the
number of unknowns or the number of constraints is less than or equal to 3; see
Section 19.5.)
Both the previous examples had optimal solutions. If the feasible region 1s
unbounded, however, a (finite) optimal solution might not exist, as is the case in
Problem 2.

The General LP Problem

The general LP problem is that of maximizing or minimizing

2 CyXy te Cahn (criterion, or objective, function) {19.1}

with c)},...,C, aS given constants, subject to m constraints

aS) Gr 2s + Ginn < by

edhe + Ganka Sb (inequality constraints) [19.2]

QmiX) + + aAmnXn < Da

where elements a;; and b; are given constants. Usually, we assume explicitly that

Yi Ose kano. (nonnegativity constraints) {19.3]

There is no essential difference between a minimization problem and a maxi-

_ mization problem, because the optimal solution (xj, ..., x7) that minimizes [19.1]
subject to [19.2] and [19.3] also maximizes —z, and minz = —max(—z). An
n-vector (x;,..., Xn) that satisfies [19.2] and [19.3] is called feasible.
728 Chapter 19 / Linear Programming

FIGURE 19.4

The set of feasible points is a convex polyhedron in the nonnegative orthant

of n-space. An example in 3-space is shown in Fig. 19.4. The flat portions of the
boundary are called faces and the points O, P, Q. R. S, T, U, and V are called
extreme points. In n-space, a convex polyhedron also has faces and extreme points.
If n and m are large, the number of extreme points can be astronomical.!
If an LP problem has a solution, then it must have a solution at an extreme
point. The simplex method is a procedure that allows us to move from one ex-
treme point to another in such a way that the value of the criterion function never
decreases, until] we come to a point such that by moving to another extreme point it
is impossible to increase the value of the cnterion function. We have then reached
the opumal solunon.

Problems

1. Use the graphical method to solve the following LP problems:

a. max 3x, +4 s.t.
3x}
{
+ 2m < 6
te a a a
:
b. min 10u; +27u2
5
s.t. {Pete
uy + 3u2
a > 1]
0 uy > 0. uw >0
>
—2x, + 3x <0
c. max 2x, +5x2 S.t. Tx; — 2x. < 14 xp =0, x2 >'0
x) ee SS 5

My ae Xo
dad. max 8x; + 9x2 s.t. 2X oxo ls tp 0s 0
Xi ct | xan 0
€. max —2x|
+ X92 St. OS x) — 397 SS eS 2. xX)
=] 0 SS 0
x

'Because an extreme point typically involves n of the n +m inequality constraints holding with
equality. there can be as many as (n + m)!/n!m! extreme points. For example. if n = 50 and m = 60
(which is quite small by the standards of the problems that can be solved numerically). then there can
be as many as 110!/50!60! or more than 6- 10°! extreme points.
 Sec. 19.2 / Introduction to Duality Theory 729

2. a. Is there a solution to the following problem?

—xX; + 0 < -l
max x; + 2X2 S.t. a x, >0, x >0
rer 3 Eis as

b. Is there a solution if the criterion function is z = —x) — x?

3. Set A consists of all (x). x2) satisfying

—2x,+ x<2
XO 91> 0
x; + 2x.
<8

Solve the following problems with A as the feasible set:

a. max x2 b. max x, c. max 3x,
+ 2x2
d. min 2x;
— 2x2 e. max 2x,
+ 4x2 f. min — 3x; — 2x2
4. A firm produces two types of television sets, an inexpensive type (A) and an
expensive type (B). The firm earns a profit of 700 from each TV of type A,
and 1000 for each TV of type B. There are three stages of the production
process. Stage I requires 3 hours of labor on each set of type A and 5 hours
of labor on each set of type B. The total available number of hours is 3900.
Stage II requires 1 hour of labor on each set of type A and 3 hours on each
set of type B. The total labor they have is 2100 hours. At stage III. 2 hours
of labor are needed for both types, and 2200 hours of labor are available.
How many TV sets of each type should the firm produce to maximize its
profit?
5. Replace the criterion function in Example 19.1 by 20x; + tx2. For what
values of ¢ will the maximum profit still be at x; = 5 and x. = 22.5?

19.2 Introduction to Duality Theory

Confronted with an optimization problem involving scarce resources. an economist
will often ask: What happens to the optimal solution if the availability of the
resources changes? For linear programs, answers to questions of this type are
intimately related to the so-called duality theory of LP. As a point of departure, let
us again consider the baker’s problem in Example 19.1.
Example 193
Suppose the baker were to receive (free of charge) one extra kilo of flour.
How much would this extra kilo add to his maximum profit? How much
would an extra kilo of sugar contribute to profit? Or an extra kilo of butter?
Solution If the baker receives one extra kilo of flour. his flour border
would become 3x; + 6x2 = 151. It is clear from Fig. 19.2 that the feasible
730 Chapter 19 / Linear Programming

set S will expand slightly and point B will move up to the left a little along
the butter border. The new optimal point B’ will be at the intersection of the
lines 3x, + 6x2 = 151 and x; + x2 = 27.5. Solving these equations gives
x; = 14/3 and x. = 137/6. Then the criterion function becomes equal to
20(14/3) + 30(137/6) = 2335/3 = 775 + 10/3. So profit rises by 10/3.
If the baker receives an extra kilo of sugar, the feasible set will expand,
but the optimal point is still at B. Recall that at the optimum in the onginal
problem, the baker had 5.75 kilos of unused sugar. There is no extra profit.
An extra kilo of butter would give a new optimal point at the intersec-
tion of the lines 3x; +6x2 = 150 and x; +x = 28.5. Solving these equations
gives x; = 7 and x2 = 21.5 with 20x, + 30x2 = 775+ 10. Profit mses by 10.
These results can be summarized as follows:

a. An extra kilo of flour would increase the optimal z by 10/3.

b. An extra kilo of sugar would increase the optmal z by 0.
c. An extra kilo of butter would increase the opumal z by 10.

The three numbers u} = 10/3, uj = 0 and uz = 10 are related to the flour,

sugar, and butter constraints, respectively. They are the marginal profits
from an extra kilo of each ingredient. Actually, these numbers have many
interesting properties.
Suppose (x), x2) is a feasible pair in the problem, so that constraints
{1}, [2], and {3] in Example 19.1 are satisfied. Muluply [1] by 10/3, [2] by
0, and [3] by 10. Because the multipliers are all > 0, the inequalities are
preserved. That is,

(10/3)(3x; + 6x2) < (10/3) - 150

O(x; + 0.5x2) < 0-22

10(x; + x2) < 10-27.5

Now add all these inequalities, using the obvious fact that if A < B, C < D,
and E< F,thnA+C+£E<B+D+4+F. Theresultis

10
10x; + 20x. + 10x; + 10x. < 3 - 150+ 10- 27.5

which reduces to

20x; + 30x2 < 775

Thus, using the “magic” numbers uj, u3, and u3 defined before, we have
proved that if (x;, x2) is any feasible pair, then the criterion function has to
be less than or equal to 775. Because x, = 5 and x2 = 22.5 give z the value
775, we have in this way proved algebraically that (5, 22.5) is the solution.
 Sec. 19.2 / Introduction to Duality Theory 731

The pattern revealed in this example tums up in all linear programming

problems. In fact, the numbers uf, u3, and u} are solutions to a new LP problem
called the dual of the original problem.

The Dual Problem

Consider once again the baker’s problem, which is

3x; + 6x. < 150

max 20x; + 30x2 subject to xy Oxy eee oaage.eucel an AB
x) + boy SDS)

Suppose the baker gets tired of running the business. (After all, there must be
many complaints about the rather plain cakes.) Somebody else wants to take over
and buy all the baker’s ingredients. The baker intends to charge a price u, for each
kilo of flour, u. for each kilo of sugar, and u3 for each kilo of butter.
Because one dozen A cakes requires 3 kilos of flour and 1 kilo each of sugar
and butter, the baker will charge 3u; +u2+u3 for the ingredients needed to produce
a dozen A cakes. The baker originally had a profit of 20 for each dozen A cakes,
and he wants to earn at least as much from these ingredients if he quits. Hence,
the baker insists that the prices (u;. U2, u3) must satisfy

3u; tur +u3 > 20

Otherwise, it would be more profitable to use the ingredients himself to produce A

cakes. If the baker also wants to earn at least as much as before for the ingredients
needed to produce a dozen B cakes, the requirement is

6u, + 0.5u2 + u3 > 30

Presumably, the entrant wants to buy the baker’s resources as inexpensively

as possible. The total cost of 150 kilos of flour, 22 kilos of sugar, and 27.5 kilos of
butter is 150u; + 22u2 + 27.5u3. In order to pay as little as possible while having
the baker accept the offer, the entrant should suggest prices u,; > 0, uz > 0, and
u3 > 0, which solve

3u, + ur+tu; > 20

min 150u; + 22u.+27.5u3 subject to {
6u, +0.5u2+u3 > 30 [7]

withu; > 0, uz > 0, and u3 > 0.

An interesting question is this: If the baker lets the entrant take over the
business and solve problem [2], will the baker earn as much as before? It turns out
that the answer is yes. The solution to (2] is uj = 10/3, and u3 = 0, and uj = 10,
and the amount the baker gets for selling the resources is 150u} +22u3 + 27.5u3 =
775, which is precisely the maximum value of the criterion function in problem [1].
732 Chapter 19 / Linear Programming

The entrant pays for each ingredient exactly the marginal profit for that ingredient
which was calculated previously. In particular, the price of sugar is zero, because
the baker has more than he can use optimally.
Problem [2] is called the dual of problem [1]. The two problems turn out to
be closely related. Let us explain in general how to construct the dual of an LP
problem.

The General Case

Consider the general LP problem

QyjX1) + -os + AinXn < D

MAX Cy)Xj be ++ + CpXp_ SUBJECT IO ¢ .---- +e - eee eee eee eee eee eee [19.4]
Am1X} ar its AmnXn < bm

with nonnegativity constraints x; > 0,...,x, = 0.

The dual of [19.4] is the LP problem

min b)u; +---+Bntm Subject to ¢ ....--.-.---

20s eeee eee eee eees [19.5]

with nonnegativity constraints u; > 0, ..., um = 0. Note that problem [19.5]

is constructed using exactly the same coefficients c),.... Cpl aie ceer ae and
b),...,bm as in [19.4].
In problem [19.4], which we now refer to as the primal problem, there are n
variables x;,...,x, and m constraints (disregarding the nonnegativity constraints).
In the dual [19.5], there are m vanables u,,....u,, and m constraints. Whereas
the primal is a maximization problem, the dual is a minimization problem. In both
problems, all variables are nonnegative. The m constraints in the primal problem
are of the “less than or equal to” type, whereas the n constraints in the dual are
of the “greater than or equal to” type. The coefficients of the criterion function
in either problem are the right-hand side elements of the constraints in the other
problem. Finally, the two matrices formed by the coefficients of the variables in the
constraints in the primal and dual problems are transposes of each other, because
they take the form

Qi; @)}2 jn a); 42) am)

Qar\ (ey esas aye ; Qj2 G22 205 Gy?
A= . ; ‘ and A’ = é : : [19.6]

Am) G@m2 --- Amn Qin Ax» amn

Check carefully that problem [2] is the dual of problem [1] in the sense we have
just explained. Due to the symmetry between the two problems, we call either the
dual of the other.
 Sec. 19.3 / The Duality Theorem 733

Matrix Formulation
Let us introduce the following column vectors (matrices):

x) C} by uy
a eke se bee (19.7)
Ses Gr loys un

Then the primal can be written as follows (with A and A’ given by [19.6]):

max c’x subjectto Ax <b, x>0 [19.8]

And the dual can be wnitten as min b’u subject to A’u>c, u> 0. It is more
convenient, however, to write the dual in a slightly different way. Transposing
A’u > ¢ using the rules in [12.44] of Section 12.9 yields u’A > c’, and moreover
b’u = w’b. So the dual can be written as

min u’b subjectto WA>c’, u>0 [19.9]

Problems

1. Consider Problem 1(a) in Section 19.1.

a. Replace the constraint 3x; + 2x2 < 6 by 3x; + 2x2 < 7. Find the new
optimal solution and compute the increase uj} in the criterion function.
b. Replace the constraint x; + 4x2 < 4 by x; + 4x. < 5. Find the new
optimal solution and compute the increase u> in the criterion function.
c. By the same argument as in Example 19.3, prove that if (x), x2) is feasible
in the onginal problem, then the cniterion function can never be larger
than 36/5.
2. Write down the dual to Problems 1(a) and (b) in Section 19.1.
3. Write down the dual to Problem 1(d) in Section 19.1.

19.3 The Duality Theorem

This section presents the main results relating the two solutions to an LP problem
and its dual. We begin by considering the baker’s problem yet again.
Example 19.4
Consider problems [1] and [2] in Section 19.2. Suppose that (x), x2) is an
arbitrary feasible pair in [1], which means that x, > 0, x2 > 0, and the three
< inequalities in [1] are satisfied. Let (u;, uz, u3) be an arbitrary feasible
triple in [2]. Multiply the < inequalites in [1] by the nonnegative numbers
uj, U2, and u3, respectively, and then add the inequalities. The result is the
734 Chapter 19 / Linear Programming

new inequality

(3x; + 6x2)uy + (x) + 0.5x2)ur + (x) + X2)Uu3 < 150U, + 22u2 + 27.5u3

Rearranging the terms on the left-hand side yields

(Bu, tur +u3)x; + (64; + 0.5u2 + u3)xX2 < 150u; +22u2+27.5u3 [*]

In a corresponding way, we multiply the > inequalities in (2) by the non-

negative numbers x; and x2, respectively, and add the results. This gives

(3u; + ur + u3)x; + (6u; + 0.5u2 + u3)x2 > 20x; + 30x [**]

From [*] and [x] together, it follows that

150u; + 22u. + 27.5u3 > 20x; + 30x2 [*%x]

for all feasible (x;, x2) in problem [1] and for all feasible (u;.u2.u3) in
problem [2]. We conclude that in this example. the criterion function in
the dual problem is always greater than or equal to the criterion func-
tion of the primal problem, whatever feasible (x). x2) and (u;,u2,.u3) are
chosen.
The inequality [x**] is valid for the feasible pair (x). x2) = (5, 22.5)
in particular. For each feasible tiple (u;. u2.u3), we therefore obtain

150u; + 22u2 + 27.5u3 > 20-5 +30-22.5 =775

It follows that if we can find a feasible triple (u}.u3.u3) for prob-

lem [2] such that 150uy} + 22u3 + 27.5u3 = 775, then (uj. u3. uz) must
solve problem [2], because no lower value of the criterion function is ob-
tainable. In Section 19.2, we saw that for (uj. u3,u3) = (10/3. 0, 10). the
criterion function in the dual did have the value 775. Hence, (10/3. 0. 10)
solves the dual problem.

The first general result we prove is the following:

Theorem 19.1 If (x; Xn) 1S feasible in the primal problem [19.4]

uy) 1s feasible in the dual problem [19.5], then

buy tes td & CyX) Hee + CpXn [19.10]

So the dual cnterion function has a value that is always at least as large as
that of the pnmal.
 Sec. 19.3 / The Duality Theorem 735

Proof Multiply the m inequalities in [19.4] by the nonnegative numbers

uj,....Um, then add. Also, multiply the n inequalities in [19.5] by the non-
negative numbers x},....X,, then add. These two operations yield the two
inequalities

(QyjX1 H-+-
+ AynXn Uy +--+ + (m1X1 +--+
+ AmnXn)um < buy +---
+ Dmum

(211Uy +--+
Am Um)X] ++ 2+ + (Gin) +--+ Omnllm)Xn > CX] +++
+ CnXn

By rearranging the terms on the left-hand side of each inequality, we see that
each is equal to the double sum )°"_, )0"_, ajjuixj. Then [19.10] follows
immediately.

From Theorem 19.1 another interesting result is obtained:

Theorem 19.2 Suppose that (xf.....x*) and (uj,...,u*,) are feasible

in problems [19.4] and [19.5], respectively, and that

Cyxp bees benx% = Duy +--- + bnu*m [19.11]

Then (xj, ...,x7) solves problem [19.4] and (uj,...,u*,) solves problem
{19.5}.

Proof Let (x},....X,) be an arbitrary feasible n-vector for problem [19.4].

Using [19.10] with uj =uy..... Um = uy, as well as [19.11], we obtain

CyX] H++ Cnn S dyuy +--+ + bmuy,

= CX) Ho+ Cnx,

This proves that (x}, ....x;) solves [19.4].

Suppose that (u;..... Um) is feasible for problem [19.5]. Then [19.10]
and [19.11] together imply that

byuy +--+
+ Omtim = CX} He Henx,

= byuy +--- + bmuy,

This proves that (uy,.... u*) solves [19.5].

Theorem 19.2 shows that if we are able to find feasible solutions for prob-
Jems [19.4] and [19.5] that give the same value to the criterion function in each of
the two problems, then these feasible solutions are, in fact, optimal solutions.
736 = Chapter 19 / Linear Programming

The most important result in duality theory is the following:

Theorem 19.3 (The Duality Theorem) Suppose the primal prob-

lem [19.4] has a (finite) optimal solution. Then the dual problem [19.5]
also has a (finite) optimal solution, and the corresponding values of the cri-
terion functions are equal. If the primal has no bounded opumum, then the
dual has no feasible solution.

The proofs of Theorems 19.1 and 19.2 were very simple. It is much more difficult
to prove the first statement in Theorem 19.3 concerning the existence of a solution
to the dual, and so we shall not attempt to provide a proof here. The last state-
ment in Theorem 19.3, however, follows readily from inequality [19.10]. For if
(u;,...,U,) is any feasible solution to the dual problem, then b)u; +--- + d,_um
is a finite number greater than or equal to any number c)x; + --- +¢,X, when
(x}....,%Xn,) iS feasible in the pnmal. This puts an upper bound on the possible
values of c)x) +--+ + CpXp-
Note: It is a useful exercise to formulate and prove Theorems 19.] and 19.2 using
matrix algebra. Let us do so for Theorem 19.1. Suppose x is feasible in [19.8]
and u is feasible in [19.9]. Then

ub > u (Ax) = (uwA)x > cx

You should note carefully how these inequalities correspond to those we established
in the earlier proof of Theorem 19.1.

Problems

1. Consider the problem

4x + Sy < 20
max 2x + 7y subject to {
ae de ty al xz0.y=0
. Solve it by a geometric argument.
&
ao. Wmitedown the dual and solve it by a geometric argument.
c. Are the values of the criterion functions equal? (If not, then according
to Theorem 19.3, you have made a mistake.)
2. Wnte down the dual to the problem in Example 19.2 and solve it. Check
that the optimal values of the cniterion functions are equal.
3. A firm produces small and medium television sets. The profit is 400 for
each small and 500 for each medium television set. Each television has
to be processed in three different divisions. Each small television requires
respectively 2, 1, and 1 hour in divisions 1. 2, and 3. The corresponding
numbers for the medium television sets are 1, 4, and 2. Suppose divisions 1
 Sec. 19.4 / A General Economic Interpretation 737

and 2 both have a capacity of at most 16 hours per day, and division 3 has
a capacity of at most 11] hours per day. Let x, and x2 denote the number of
small and medium television sets that are produced per day.
a. Show that in order to maximize profits per day, one must solve the
following problem:

2x; + Xx. < 16

max 400x; + 500x2 subject to bape cS ie Ko lameee thee Ole pie f
x} + 2m < 11

b. Solve this problem graphically.

c. If the firm could increase its capacity by 1 hour a day in just one of the
three divisions,- which should be the first to have its capacity increased?

19.4 A General Economic Interpretation

This section gives a general economic interpretation of the LP problem [19.4] and
its dual [19.5]. Think of a firm that produces one or several outputs using m differ-
ent resources as inputs. There are n different activities (or processes) involved in
the production process. A typical activity is characterized by the fact that running
it at unit level requires a certain amount of each resource. If a;; is the number of
units of resource i that are needed to min activity j at unit level, the vector with
components @1;,@2;...-,@mj expresses the m different total resource requirements
for running activity j at unit level. If we run the activities at levels x;,...,x,, the
total resource requirement can be expressed as the column vector

aj\ Qin
xy{ ot |te--t+2n
am} amn

If the available resources are b;....,b,, then the feasible activity levels are those
that satisfy the m constraints in [19.4]. The nonnegativity constraints reflect the
fact that we cannot run the activities at negative levels.
Each activity brings a certain “reward.” Let c; be a measure of the reward
(or value) created by running activity j at unit level. The total reward obtained by
running the activities at levels x,,..., x, is then c)x; +---+c,x,. The problem of
the firm is therefore to solve the following LP problem: Find those levels for the n
activities that maximize the total reward, subject to the given resource constraints .
The problem in Example 19.1 can be interpreted in this way. There are two
activities of making each of the two types of cake, and there are three resources—
flour, sugar, and butter.
Let us turn to the dual problem [19.5]. In order to be in business, the firm
has to use some resources. Each resource, therefore, has a value or price. Let u;
738 Chapter 19 / Linear Programming

be the price associated with one unit of resource j. Rather than think of u; as
a market price for resource j. we should think of it as (Somehow) measuring the
relative contribution that one unit of resource j makes to the total economic result.
These prices are not real prices, so they are often called shadow prices.
Because aj ;.@2;,....@mj are the numbers of units of each of the m resources
needed to run activity j at unit level, a);u; + a2j;u2 + --- + Qmjum is the total
(shadow) cost of running activity j at unit level. Because c; is the reward (value)
of running activity j at unit level,

Cj — (ay jy + anjuz +--- + AmjUm)

can be regarded as the (shadow) profit of running activity j at unit level. Note
that the jth constraint in the dual problem [19.5] says that the (shadow) profit from
running activity j at unit level is < 0.
The criterion function Z = bu; +--- + bmu, in the dual LP problem
measures the (shadow) value of the initial stock of all the resources. The dual
problem is, therefore, the following: Among all choices of nonnegative shadow
DIICES Ug. > sx Um such that the profit of running each activity at unit level is < 0,
find one that minimizes the (shadow) value of the initial resources.

The Optimal Dual Variables as Shadow Prices

Consider again the primal problem

Qy\X; + FAX = i
max €)xX; +--+ +CpXn subject TO.) Cc dae ks bepertbaes Sedo rendiece ER 258 [x]
QmiX, + + @mnXn S bm

withix; 2.0.5. .3 X, > 0. What happens to the optimal value of the criterion
function if the numbers })..... b,, change? If the changes Ab,..... Ab, are
positive, then the feasible set increases and the new optimal value of the criterion
function cannot be smaller. (Usually it increases.) The following analysis also
applies when some or all the changes Ab), .... Ab, are negative.
How big is the change in the optimal value? Suppose (xf,...,x*) and
(ey ACen x; + Ax,) are optimal solutions to the primal when the nght-hand
side is respectively (b). ..., bm) and (b} + Ad), ..-.bm + Abm). If Ab,...., Abn
are all sufficiently small, the duals of the two problems often have the same optimal
solution uj..... u*. Then, according to Theorem 19.3, one has

CiXy Hee HCpxT = yu +--- + bn ur

Ci (xy + AX) +++ ten (XZ + Axq) = (b) + Abi )uy +--+ (bm + Adm)
ur,

Hence, by subtraction,

CA, +--+
+ CpAX, = UpAb, + +--+
u* Abp,
 Sec. 19.5 / Complementary Slackness 739

Here the left-hand side is the change we obtain in the criterion function in [*] when
b,...., bm are changed by Ab),..., Abm, respectively. Denoting this change in
z by Az*, we obtain

Az* = ulAby +--+

+ u" Adm [19.12]

Note: The assumption underlying [19.12] is that the changes in the b’s do not
cause the optimal dual vanables to change.

Problems

1. Consider Problem | in Section 19.3,

4x+ Sy a 20
max 2x
+ 7y subject to {es Ge im x=
00 = 0
21

We found that the optimal solution of this problem was x* = 0, and y* = 3,

with z* = 2x* + 7y* = 21. The optimal solution of the dual was uj = 0
and u5 = 1. Suppose we change 20 to 20.1 and 21 to 20.8. What is the
corresponding change in the cnitenon function?

19.5 Complementary Siackness

Consider again the baker’s problem [1] in Section 19.2 and its dual (2]. The solution
to [1] was xf = 5 and x} = 22.5, with the first and the third inequalities both
satisfied with equality. The solution to the dual was uj = 10/3, u; =0, and u3 =
10, with both inequalities in the dual satisfied with equality. Thus, in this example,

the first and second inequalities

x; > 0, Boom | {1}
in the dual are satisfied with equality

the first and third inequalities

uy >0.u;>O0=—> {
in the.primal are satisfied with equality [2]

We interpret [2] this way: Because the shadow prices of flour and butter are posi-
tive, in the optimal solution, all the available flour and butter are used. We do not
use all the available sugar, so its shadow price is zero—it is not a scarce resource.
These results hold more generally.
Indeed, first, consider the problem

QjX1 + Qy2X2
max €;X; +C2x2 subject to ¢ @2)x; + a72Xx2 = v oO y V oO ¥
€31X| + 32X2 IA epee
INIA
740 = Chapter 19 / Linear Programming

and its dual

Q))Uy + 42\)U2
+ a3;uU3 2 Cy
min bju; + bou2 + b3u3 subject to {
Q\2U, + 472U2
+ 432U3— = C2
(4)

with uv}, u2, and u3; > 0. Suppose (xf. x3) solves (3] whereas (u7.u}. U3) solves
[4]. Then

QyjX} +aj2x5 < Dy Z 2 af

P Qj\U; + AU,
+ A3;U3; = C|
(a) Qax{ +axx,7 Sb2 ~~ (b) . ‘ [5]
* *
Qj2U, + A22U>= + A32U3 = C2

Multiply the three inequalities in [5](a) by the three nonnegative numbers uj, u3,
and u3, respectively. Then add the results. This yields the inequality

(Ay, Xf +Qy2X5) Ul + (a2) X7 +422X5 U5 + (43) X} +4323) UZ < Diu} +b2u,+b3u; [6]

Muluply the two inequalities in [5](b) by xf and x}. respectively, and then add.
This gives

(@yyUy + a21)Uz + G3)U5)xT + (ai2Uy + QxU5 + a32U3)x5 > Cx +c2x, = [7]

Looking closely at the left-hand sides of the two inequalities in [6] and [7] reveals
that they are equal. Moreover, by the duality theorem of LP (Theorem 19.3), the
nght-hand sides of [6] and [7] are equal. Hence, both inequalities in [6] and [7] can
be replaced by equalities. Thus, replacing < by = in (6) and rearranging. we obtain

(ay,
xX}+@12x7 — by uy + (a2)
x} + a22x3 — b2)UZ + (a3)xf+€32x5 —b3)uz = 0 [8]

Each term in the parentheses within [8] is < 0 because (xf.x3) is feasible. So,
because uj}, u5, and u3 are all > 0, the three terms in [8] are < 0. If any were < 0,
their sum would be < 0. Because their sum is 0, each of them must be 0. Thus,

(aj\x} + aj2x3 — bj)uj —) Gg = Leis)

We conclude that

ajix} + aj2X3 < b; (= bj if us > 0) Lj lous) [9]

Using the fact that > in [7] can be replaced by =, and reasoning in exactly the
same way as before, we also get

A\jUS+ aru; + a3u; > c; (= ¢; if x* > 0) (i= 1,2,3) [10]

The results in [9] and [10] are called the complementary slackness conditions.
The arguments used to show that these conditions are necessary extend in a straight-
 Sec. 19.5 / Complementary Slackness 741

forward way to the general case. Furthermore, the same complementary slackness
conditions are also sufficient for optimality. Here is a general statement and proof:

Theorem 19.4 (Complementary Slackness) Suppose that the primal

problem [19.4] of Section 19.2 has an optimal solution x* =
whereas the dual [19.5] has an optimal solution u* = (uj, ...

TH: +amiuX >; (=c; if x* > 0) [19.13]

Aj\X} e+ + Qjnx, <b; (cS bj if uj > 0) [19.14]

Conversely, if x* and u* have all their components nonnegative and satisfy

{19.13] and [19.14], then x* and u® solve the pnmal problem [19.4] and the
dual [19.5], respectively.

Proof Suppose x* solves [19.4] and u* solves [19.5]. Then, in particular

(see [19.8] and [19.9]).

Ax* <b and (u*)’A>c’ (1)

Multiplying the first inequality in [1] on the left by (u*)’ > 0 and the second
inequality on the right by x* > 0 yields

(u*)’Ax* < (u")’b — and (u*)’Ax* > c’x* (2]

According to Theorem 19.3, (u*)’b = c’x*. So both inequalities in [2] must

be equalities. They can be wntten as

(u*)'(Ax* — b) i 0 and = ((u*)’A—c’)x* =0 (3)

But these two equations are equivalent to

Sub ajixt +++ + ajnxt — bj) =0 [4]

j=!
and
n

SS (aiiay +--+ + amis, — ¢j)x7 =0 [5]

i=l

For j=1..... m one has both u* > 0 and ajjxf +---+ajnxq

— 6; <0. So
each term in the sum [4] is < 0. The sum of all the terms is 0. so there can be
no negative term. because there is no positive term to cancel it. Hence, each
742 = Chapter 19 / Linear Programming

term in the sum [4] must be 0. Therefore.

ur (ajjx} +--+ ajnX, — bj) =0 (jr ee m) [6]

Now [19.14] follows immediately. Property [19.13] is proved in the same way
by noting how [5] implies that

x} (aul +--+: + amity, — ci) =0 (P=) a ase n) (7)

Suppose on the other hand that x* and u™ have all their components
nonnegative and satisfy [19.13] and [19.14]. It follows immediately that [6]
and [7] are satisfied. So summing over j and i, respectively. we obtain [4] and
[5]. From these equalities. it follows that 5° , bus = Sor Dias SjixpuF
and also S°7_, cix? = Doj_) Loja ajiM7x7. But the two double sums are
equal. Hence, }°7_, bjut = >) ix? So according to Theorem 19.2, the
vector (xf.---.x;) solves problem [1] and (uj. ---.u™) solves the dual.

Note: Using the general economic interpretations we gave in Section 19.4, condi-
tions [19.13] and [19.14] can be interpreted as follows:
If the optimal solution of the primal problem implies that activity i is in operation
(x > 0), then the (shadow) profit from running that activity at unit level is 0.
If the shadow price of resource j ts positive (u; > 0), then all the available stock
of resource j must be used in any optimum.

How Complementary Slackness Can Help Solve

LP Problems
If the solution to either the pnmal or the dual problem is known, then the com-
plementary slackness conditions can help find the solution to the other problem by
determining which constraints are slack. Let us look at an example.
Example 19.5:
Consider the problem

x2+ x3 <2 a
+ 6x3
+ 4x. subject to 3x) +
max 3x;
; X, + 2x2 + 6x3 <1

with x; > 0, x2 > 0, and x3 > 0. Write down the dual problem and solve it
by a geometric argument. Then use complementary slackness to solve [1].

Solution The dual problem is

3u;+ U2 ma
min 2u; +u2 subject of uy + 2u. >4 uj.u2>0 [2]
uy; + 6u2 >6
 Sec. 19.5 / Complementary Slackness 743

Using the geometric solution technique shown in Example 19.2, we find the
solution uj = 2/5, and u = 9/5. Then 3uj + u3 = 3. uj + 2u3 = 4, and
ui + 6u3 > 6.
What do we know about the solution (xf, x3, xj) to [1]? According
to [19.14], because uj > 0 and u5 > 0, both inequalities in [1] are satisfied
with equality. So

Bxptxp+x3=2 and = xf+2x5+6x3=1 (3]

Now x} cannot be > 0, otherwise [19.13] would imply uj +6u5 = 6. Hence,

x3 = 0. Letting x3 = 0 in [3] and solving for xf and x} gives

=3/f5, x5, xf =0
This is the solution to problem [1]. Note that the optimal values of the
criterion functions in the two problems are indeed equal: 2uj + u3 = 13/5
and 3xf + 4x3 + 6x3 = 13/5, just as they should be according to the duality
theorem.

The Kuhn—Tucker Theorem Applied to Linear

Programs
Consider the general linear programming problem

QyjX1
= + Anke, = OY
TNAXCCI
A Cake eS Mate Seana ih eae ee Xi Ola kee)
QmiX1 t--> t+ amnXn < bm 1]

1
This problem is obviously a special case of the general nonlinear programming
problem

g(x, Xn) Sc
MAX sii is Mack) GSE XR esd.
36<e ie! Res
ag x, 08 Se}
Qin x jeearent kn) sere

which was studied in Section 18.9. Note that the functions f and g; in [1] are
all linear, so are concave as well as convex. Thus, the Kuhn—Tucker conditions
[18.42] and [18.43] are sufficient for optimality of a vector x = (x), x2..... i)
satisfying the constraints specified in [1]. Let us see what form these conditions
take in the linear case.
If we let A; = uj for j=1..... m, conditions [18.42] and [18.43] become

Ci) — (ayjuy +--+ + Gmitm) <9 (=O

if x; > 0) (i= en) (3)

(Tippee (= 0 if ajjx,y +--- + GjnxX_ < dj) Cit= |xencern) (4]

744 Chapter 19 / Linear Programming

When combined with the requirement that x satisfy the constraints in problem [1],
these conditions are precisely the complementary slackness conditions in Theo-
rem 19.4.

Duality When Some Constraints are Equalities

Suppose that one of the constraints in the primal problem is the equality

jy X] +--+
+ AinXn = 5; [*]

Then we can replace it by the two inequalities

Gj1Xj +--+ Ginx, S 0; and = Qj) Xj — 2 — Ginkn = —O; [**]

in order to put the problem into standard form. Constraint [*] thus gives rise to
two dual variables u‘ and u’’. In the matrix describing the dual constraints, the two
columns associated with uw; and w;’ are equal except for opposite signs everywhere.
Therefore, we can replace the two variables u; and u/ with u; = u; — u7, but
then there is no restriction on the sign of u;. We see that if the ith constraint in
the primal is an equality, then the ith dual variable has an unrestricted sign. This
is consistent with the economic interpretation we have given. If we are forced
to use all of resource i, then it is not surprising that the resource may command
a negative shadow price—it may be something that is harmful in excess. For
instance, if the baker of Example 19.1 was forced to include all the stock of sugar
in the cakes, the best point in Fig. 19.2 would be B, not C. Some profit would
be lost.
From the symmetry between the primal and the dual, we realize now that if
one of the variables in the primal has an unrestricted sign, then the corresponding
constraint in the dual is an equality.

Problems

1. Consider Problem 1 of Section 19.3. The optmal solution of the primal was
x” = 0, and y* = 3, whereas u} = 0, u3 = 1 was the optimal solution of the
dual. Verify that [19.13] and [19.14] are satisfied in this case.
2. a. Solve the following problem geometrically:

pT Be SP Retake
‘
min y; + 2y2 subject to aybs tea ap aS 5 ; :
es yn 20, 2 =0
’ y= 2)3 B20
b. Write down the dual problem and solve it.
c. What happens to the optimal dual variables if the constraint y) +6y2 > 15
is changed to y) + 6y2 > 15.1?
 Sec. 19.5 / Complementary Slackness 745

3. A firm produces two commodities A and B. The firm has three factories
that jointly produce both commodities in the amounts per hour given in the
following table:

Factory 1 Factory 2 Factory 3

Commodity A 10 20 20
Commodity B 20 10 20

The firm receives an order for 300 units of A and 500 units of B. The cost
per hour of running factories 1, 2, and 3 are respectively 10,000: 8000; and
11,000.
a. Let y), y2, and y3, respectively, denote the number of hours for which
the three factories are used. Write down the linear programming problem
of minimizing the costs of fulfilling the order.
b. Show that the dual of the problem in part (a) is

10x, + 20x. < 10.000

max 300x; +500x. s.t.¢ 20x, + 10x. < 8000 36) = ade =U
20x, + 20x. < 11.000

Solve this problem and then find the solution of the problem in part (a).
c. By how much will the minimum cost of production increase if the cost
per hour in factory 1 increases by 100?

Harder Problems

4. The following problem has arisen in production theory:

Elxl 4 gry? 4... ENXN < V,

Elx) 43x? 4---+8Nx" < Vy
x1 ax =
max x! + x7 4+---4x" sit. > Fie3 {1]
xo aXe

bg asd!

where vaniablesx e%75, o-oex. wares all =O; Here, 62) 9Vi. Vaux 252:
x are fixed constants. (Superscripts i = 1]. .... N refer to production
units; V, and V> are available quantities of two resources; each x/ is a
capacity constraint on the output of unit j.) Wnte down the dual to prob-
lem [1], with g; and g2 denoting the dual prices associated with the firsi two
constraints in [1], whereas r', r?, .... r% are the dual variables associated
with the last N constraints. Let the values of the variables that solve the
746 = Chapter 19 / Linear Programming

two problems be those indicated with a hat. Show that if [1] has a finite
optimum, then

#>0 => H4+GQtr'=1 G= IN) li]

ban elgr-er > =x =0 C= Nes N) {ii
Gj OES eee ty, (j = 1,2) (iii)

Eg po + ENE < VV, => Gj =0 (j = 1,2) liv]

fF>0 = = x GaT, =; N) [v]
g<x'
i aH
= 7'=0 (feral N) [vi]

5. Consider the LP problem

X} = xe <
max 3x;+2x2 subject to 2x) Pe Xeo— -xs <1 xp izraOeG >0
X; + 2x. -— 2x3 < 1

a. Suppose x3 is a fixed number. Solve the problem if x3 = 0 and if x; = 3.

b. Solve the problem for any fixed value of x3 in [0.00). The maximal
value of 3x; + 2x2 becomes a function of x3. Find this function and
maximize it.
c. Do the results in part (b) say anything about the solution to the original
problem in which x3 can also be chosen?