Degeneracy and Cycling in Simplex

Each simplex tableau represents a basic feasible solution (BFS) of the linear program: the basic variables read their values directly from the RHS column, and the nonbasic variables equal zero.

A BFS is degenerate if at least one basic variable equals zero. In tableau form, this is exactly the case when the RHS column contains a zero in some constraint row.

For example, consider the tableau

$$\begin{array}{c|cccccc|c} \text{Basis} & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & \text{RHS} \\ \hline s_1 & 0 & 2 & 1 & 1 & 0 & 0 & 5 \\ x_1 & 1 & -1 & 3 & 0 & 1 & 0 & 0 \\ s_3 & 0 & 4 & 0 & 0 & -2 & 1 & 7 \\ \hline z & 0 & -3 & 1 & 0 & 4 & 0 & 12 \end{array}$$

The basic variables take the values $s_1 = 5,$ $x_1 = 0,$ and $s_3 = 7.$ Since the basic variable $x_1$ equals zero, this BFS is degenerate.

Geometrically, a degenerate BFS corresponds to a vertex of the feasible region at which more than $n$ of the defining inequalities are tight — i.e. the vertex is over-determined. Algebraically, it is a warning sign: the simplex method may stall at such a point.