Multiple optimal solutions / LP

Question

In the optimal primal simplex tableau, if we have a non-basic variable with a reduced cost of zero, can we say for sure the primal has multiple optimal solutions? Or can the same thing also happen when we have a degenerate unique solution? Thanks.

Answer 1

I use "BV" as an abbreviation of "basic variable". In the following optimal simplex tableau, suppose that we are going to replace the basic variable $x_r$ by a non-basic variable $x_j$ to obtain an alternate optimal basic feasible solution to the LPP. Suppose that in the tableau, there're $m$ constraints and $n$ columns (excluding "BV" and "RHS").

• Let $y_{00}$ be the value of the current optimal value.
• Let $y_{0j} = 0$ be the value of the current reduced cost coefficient of $x_j$.
• Let $y_{r0}$ be the value of $x_r$.

\begin{align*} \begin{array}{c|ccc|c} \mbox{BV} & * & x_j & * & \mbox{RHS} \\ \hline * & * & * & * & * \\ x_r & * & y_{rj} & * & y_{r0} \\ * & * & * & * & * \\ \hline * & * & y_{0j} & * & y_{00} \end{array} \end{align*}

If $y_{r0} = 0$, then we are just replacing $x_r = 0$ by $x_j = 0$ on the LHS of the tableau, but the current optimal solution is not changed. Therefore, to find an alternate basic optimal feasible solution, we need to assume that $y_{r0} \ne 0$.

To perform a pivot operation on $y_{rj}$, we first need the condition that $y_{rj} > 0$. This gives us another (feasibility) condition: there exists $j \in \left\{ 1,\dots,n \right\}$ such that \begin{equation*} \begin{cases} x_j \mbox{ is a non-basic variable,} \\ y_{0j} = 0 \mbox{ and} \\ \exists r \in \left\{ 1,\dots m \right\} \mbox{ s.t. } y_{rj} > 0 \end{cases} \end{equation*}

After a pivot operation on $y_{rj}$, the objective function value $y_{00}$ will become $y_{00} - \dfrac{y_{r0} y_{0j}}{y_{rj}}$. If we want $y_{00}$ to be unchanged, we need $\dfrac{y_{r0} y_{0j}}{y_{rj}} = 0$. Since $y_{rj} > 0$ (feasibility) and $y_{r0} \ne 0$ (to get another solution), we have $y_{0j} = 0$. Therefore, the only way to determine whether there is an alternate basic optimal feasible solution from the optimal simplex tableau is to search for the zeros in the reduced cost coefficient of the non-basic variables.