Explore BrainMass

Linear Programming : Proof using Duality and the Farkas Lemma

This question is from linear programming.

I want to use duality (it's so obvious), farkas lemma (alternative solution) and all.

(See attached file for full problem description with equations)

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

(b) Prove or disprove the following claim:

Assume that both the linear program

and its dual

are feasible. Then at least one of them has an unbounded feasible region.


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 ...

Solution Summary

Duality and the Farkas Lemma are investigated. The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.