Linear Programming Exercise 4.19 Let P = {x R I Ax = b, x2 0} be...

 

Transcribed Image Text:

Linear Programming Exercise 4.19 Let P = {x €R" I Ax = b, x2 0} be a nonempty polyhedron, and let m be the dimension of the vector b. We call xj a null variable if xj = 0 whenever æ € P. ONLY PART B AND C (a) Suppose that there exists some p E Rm for which p' A20', p'b = 0, and such that the jth component of p'A is positive. Prove that x; is a null variable. (b) Prove the converse of (a) : if xj is a null variable, then there exists some pE RM with the properties stated in part (a). (c) If xj is not a null variable, then by definition, there exists some y E P for which yj > 0. Use the results in parts (a) and (b) to prove that there exist x EP and ERM such that: p'A20', p'b = 0, x+A'p> 0. Linear Programming Exercise 4.19 Let P = {x €R" I Ax = b, x2 0} be a nonempty polyhedron, and let m be the dimension of the vector b. We call xj a null variable if xj = 0 whenever æ € P. ONLY PART B AND C (a) Suppose that there exists some p E Rm for which p' A20', p'b = 0, and such that the jth component of p'A is positive. Prove that x; is a null variable. (b) Prove the converse of (a) : if xj is a null variable, then there exists some pE RM with the properties stated in part (a). (c) If xj is not a null variable, then by definition, there exists some y E P for which yj > 0. Use the results in parts (a) and (b) to prove that there exist x EP and ERM such that: p'A20', p'b = 0, x+A'p> 0.

Answer rating: 100% (QA)

For a and b the proof is similar to that of Farkas lemma Hint Conside... View the full answer