8.5 Farkas' Lemma 113

&yTB cTB^yT cTBB~x & yTb = cTBB~xb = cTx\

Furthermore, this choice of y is optimal, and the strong duality theorem has

been proven. This is a constructive proof, x* and y* were actually computed,

which is convenient since we know that the simplex method finds the optimal

values. D

8.5 Farkas' Lemma

Coll

rt £<i H 1

mnl

Column2

o \J// / / -•—

>/// Column3

Column4

i) Ax=b has s i nonnegative solution

b

H

* J

-«e

f-

Coli

i J]\ 1

mnl

^/^Column2

-»•_

i^(// Column?"

Column4

(ii) Else

Fig. 8.2. Farkas' Lemma

By the fundamental theorem of Linear Algebra,

either b G U(A) or 3y e M(AT) By JLb,

that is, there is a component of b in the left null space. Here, we immediately

have the following theorem of alternatives.

Proposition 8.5.1 Either Ax — b has a solution, or else there is a y 3

ATy = 9,yTb^0.

If b € Cone(a^1 , a^2 , a^3 ,...) then Ax — b is solvable. If 6 0 Cone(columns
of A), then there is a separating hyperplane which goes through the origin
defined by y that has b on the negative side. The inner product of y and b is
negative (yTb < 0) since they make a wide angle (> 90°) whereas the inner
product of y and every column of A is positive (ATy > 0). Thus, we have the
following theorem.

Proposition 8.5.2 Either Ax = b,x > 9 has a solution, or else there is a y
such that ATy > 6, yTb < 0.

Corollary 8.5.3 Either Ax > b,x > 9 has a solution, or else there is a y
such that ATy > 9, yTb < 0, y < 9.