Principles of Mathematics in Operations Research

112 8 Linear Programming

same: The minimum of cTx equals the maximum ofyTb. Otherwise, if optimal

vectors do not exist, either both feasible sets are empty or else one is empty

and the other problem is unbounded.

Theorem 8.4.2 (Weak Duality) If x andy are feasible vectors in the min-

imum and maximum problems, then yTb < cTx.

Proof. Since they are feasible, Ax > b and ATy < c (<& yTA < cT). They

should be nonnegative as well: x > 8, y > 9. Therefore, we can take inner

products without ruining the inequalities: yTAx > yTb and yTAx < cTx.

Thus, yTb < cTx since left-hand-sides are identical. D

Corollary 8.4.3 // the vectors x and y are feasible, and if cTx = yTb, then

these vectors must be optimal.

Proof. No feasible y can make yTb larger than cTx. Since our particular y

achieves this value it should be optimal. Similarly, x should be optimal. D

Theorem 8.4.4 (Complementary Slackness) Suppose the feasible vectors

x and y satisfy the following complementary slackness conditions:

if (Ax)i > bi, then yt = 0 and if (ATy)j < Cj, then Xj = 0.

Then, x and y are optimal. Conversely, optimal vectors must satisfy comple-

mentary slackness.

Proof. At optimality we have

yTb = yT(Ax) = (yTA)x = cTx.

If y > 0 and Ax > b =4- yTb < yT(Ax). When yTb — yT{Ax) holds, if

bi < (Ax)i, the corresponding factor «/; should be zero. The same is true

for y^1 Ax < cTx. If Cj > (ATy)j then Xj = 0 to have yTAx = cTx. Thus,

complementary slackness guarantees (and is guaranteed by) optimality. •

Proof (Strong Duality). We have to show that yTb = cTx is really possible.

Max cTx, Ax>b, x>8

«• Max [cT\9T]. M-'] = 6, >e.

[A\-I] -¥ [B\N] -» XB

XN

B~lb

0 [cH^] -•[«]•

Optimality condition: NT(BT) XCB < c^.

Since we have finite number of extreme points, the optimality condition is
eventually met. At that moment, the minimum cost is cTx = CQB~^1 XB-

Max by subject to

A

r

-I y<

c

0

->

B^1

y<

CB

CN

<S=> BTy = cB