(adsbygoogle = window.adsbygoogle || []).push({}); 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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Degeneracy in Linear Programming

Can you offer guidance or do you also need help?

**Physics Forums | Science Articles, Homework Help, Discussion**