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

---

https://brainmass.com/math/linear-programming/linear-programming-proof-duality-farkas-lemma-52941

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