Linear Programming : Proof using Duality and the Farkas Lemma
Not what you're looking for?
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.
---
Purchase this Solution
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.
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 ...
Purchase this Solution
Free BrainMass Quizzes
Exponential Expressions
In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.
Solving quadratic inequalities
This quiz test you on how well you are familiar with solving quadratic inequalities.
Know Your Linear Equations
Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.
Graphs and Functions
This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.
Multiplying Complex Numbers
This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.