Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Degeneracy in Linear Programming

  1. Nov 14, 2011 #1


    User Avatar

    1. The problem statement, all variables and given/known data

    Consider the standard form polyhedron {x | Ax = b, x>=0} , and assume that the rows of the
    matrix A are linearly independent.

    (a) Suppose that two different bases lead to the same basic solution. Show that the basic solution is degenerate (has less than m non-zero entries).
    (b) Consider a degenerate basic solution. Is it true that it corresponds to two or more distinct bases? Prove or give a counterexample.
    (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 conterexample.

    2. Relevant equations

    3. The attempt at a solution

    (a) I think it's obvious but how build the proof, the two different bases lead to the same basic solution, when the last entering variable cannot be increased at all because it's b value equals 0 therefore as result we have the same basic solution. But how to prove that?

    (b) no, degenerate basic solution can correspond to one basis only as well. But how to prove that?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?