Recognizing Multiple Optimal Solutions

In the final simplex tableau of a maximization LP, the optimality condition is that every entry in the objective row (the $z$-row) is $\ge 0$. Basic variables always have a $z$-row entry of $0$ — the informative entries are those of the non-basic variables.

If every non-basic variable has a strictly positive reduced cost, pivoting any of them into the basis would strictly decrease $z$, so the current basic feasible solution (BFS) is the unique optimum.

If some non-basic variable has reduced cost exactly $0$, pivoting it into the basis would leave $z$ unchanged. The LP has multiple optimal solutions — also called alternative optima.

$$\textbf{Multiple optimal solutions} \iff \text{some non-basic variable has reduced cost } 0 \text{ in the final } z\text{-row.}$$

For example, consider the final tableau

$$\begin{array}{c|cccc|c} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline z & 0 & 0 & 2 & 0 & 24 \\ x_1 & 1 & 2/3 & 1/3 & 0 & 4 \\ s_2 & 0 & 1/3 & -1/3 & 1 & 1 \end{array}$$

All $z$-row entries are $\ge 0$, so the tableau is optimal with $z^* = 24$ at the BFS $x_1=4,\ x_2=0,\ s_1=0,\ s_2=1$. The non-basic variables are $x_2$ and $s_1$, with reduced costs $0$ and $2$. Since $x_2$ is non-basic with reduced cost $0$, this LP has alternative optima — bringing $x_2$ into the basis would produce a different BFS achieving the same objective value $24$.