# Linear Programming: Degeneracy in Simplex Method

• November 9th 2010, 05:18 PM
scherz0
Linear Programming: Degeneracy in Simplex Method
Hello everyone,

I am having trouble understanding one line of the proof for a claim that involves degeneracy in the simplex method, all of which are posted below. Idicated by the red arrow is the step that troubles me: "also $a_{ij}^{-1} = 0$".

I have also written my thoughts below.

Thank you very much!

---

Thoughts:

I know the following from the given fact that the objective value doesn't change after one application of the simplex method:

$\displaystyle q = \frac{-p_j}{a_{ij}} \times b_i + q \Rightarrow$

$\displaystyle \frac{-p_j}{a_{ij}} \times b_i = 0 \Rightarrow \frac{b_i}{a_{ij}} = 0$, since $\displaystyle p_j \neq 0$. However, how does the step in red follow from this?

Actual Question and Proof:

http://img219.imageshack.us/img219/1047/linprogis.jpg