Share
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
min
s.t.

and its dual
max
s.t.

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

Attachments

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.

$2.19