Linear Programming : Proof using Duality and the Farkas Lemma

Solution Preview

Please see the attached file for the complete solution.
Thanks for using BrainMass.

(a) Let . Prove that one of the following systems has a solution but not both:

Farkas Lemma.
( , Ax = b) {y, (yTA  0 => yTb  0)}

Proof: Assume that there exists y0 that satisfies y0TA  0, but y0Tb < 0. Now assume that there also exists x0 that satisfies x0  0 and Ax0 = b.

Then we have Ax0 = b
Consequently, y0TAx0 = y0T(b)
 (y0TA)x0 = y0T(b)
But y0TA  0 and x0  0 => (y0TA)x0  0

 (y0TA)x0 = y0T(b)  0
contradiction our assumption that y0T(b) < 0. Therefore no such x0 exists that satisfies the inequality y0TA  0 and y0Tb < 0.

Conversely, if y such that yTA  0 => yTb  0, then we can show that  , for which Ax = b is valid.

[HINT: instead of the yTA  0 as defined in the lemma above, you replace  by  and retrace the steps of Farkas lemma as shown above!]

Another form of Farkas lemma:

Consider this problem:

(x, Ax  b) { , (yTA = 0 => yTb = 0)} (1)
[here we replace the inequality sign by equality and vice ...