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