Explore BrainMass

Explore BrainMass

    Linear Programming : Proof using Duality and the Farkas Lemma

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com March 4, 2021, 6:37 pm ad1c9bdddf


    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.