Question

I have some optimization questions if anyone's up for it, thanks.

12. (Exercise 2.9) Consider the standard form polyhedron P = {Z ER” | Az = b, x>0}, where the rows of A are linearly independent. (a) Suppose that two differnt bases lead to the same basic solution. Show that the basic solution is degenerate. (b) Consider a degenerate basic solution. Is it true that it corresponds to two distinct bases? Prove or give a counterexample. 16 (c) Suppose that a basic solution is degenerate. Is it true that there exists an adjacent basic solution which is degenerate? Prove or give a counterexample.

Answer 1

Answer:

Here, we are considering the standard form polyhedron is {x / Ax = b, x > o}

Assuming the two distinct bases Bland B2 that each yield the same basic of solution x. so, here we have to do it by contradiction, then we have to assume that se is nendegenerate That means every one of the invariables in eis nonzero. Thus every one of the invariables in Bl is nonzero, and every one of the n variables in BW is nonzero. since, The Bland Bro are distinct, so there is at least one variable in Bl not in B2. But, this yields at least mtl.nonzero variables inx, So it is contradiction, Then x must be degenerate, The degenerate basic solution is not corresponds to to two distinct bases. The counter exanipte isi Xitx2 + 33 =1 -X: +82 + x3 = this system xi, X2,23 Z here, Those are there potential bases in i.e., B = {x, ; X2} B₂ = {Xq X3} Bz = {X2, X3}

however By cannot actually be a basis because the corresponding matrix, [i:] It is not invertible, Bi yields the basic solution (0,1,0), while, B2 yields the basic solution (ool) Bl and B2 are degenerate, but there is only one basis Cororesponding to each. The basi degenerate basic solution is not true. Bo Taking the given gystem; sitR2=1 22 +22=1 X1, X2, X3 20. The basic solution is Co, 1,o) it corresponds to bases (xx,&2) and (&2 , 83) and the only other basis is (xi,&z), The other basis solution is (1, 0, 1) Then, .. The degerat e basic solution is co, lo] is not adjacent to other denerate basic solution.