Degeneracy in Simplex

Degeneracy occurs when a BFS has a zero basic variable. In simplex, it can cause zero-length pivots.

Definition

A BFS is degenerate if at least one basic variable satisfies $x_{B(i)}=0$.

Zero Step

The ratio test can give $\theta^*=0$, so the basis changes but the point does not move.

Stalling

Repeated zero steps are called stalling.

Cycling

Rarely, simplex can revisit an old basis. Smallest-index pivot rules avoid cycling.

Checklist

Recognize zero basic variables and explain stalling.

See Also

• Degenerate Basic Feasible Solutions
• Minimum Ratio Test

Exam checkpoint

For simplex questions in minimization form, negative reduced costs indicate possible improvement. Use $u=B^{-1}A_j$, apply the ratio test only to positive components of $u$, then update the basis.