\section{Alternative Optimal/Unbounded Solutions and Degeneracy}\label{S:Special_cases}\index{special cases}
\setcounter{progress_ck_counter}{0}


\noi
When applying the simplex algorithm, how can we determine from the tableau whether an LP has alternative optimal
solutions or is unbounded? The purpose of this section is to address these special cases.


\subsection{Alternative Optimal Solutions}\index{linear programming problem!alternative optimal solutions}


\noi Consider first the LP given by the following:
\begin{align}\label{E:Special_cases_alternative_solutions_example}
\mbox{maximize } z & =12x_1+3x_2 \\
	\mbox{  subject to} \notag \\
	4x_1 + x_2 &\leq 8 \notag \\
	5x_1+2x_2  &\leq 12  \notag \\
	x_1,x_2 &\geq 0.\notag
\end{align}

\newpar
The feasible region for the LP is shown in Figure \ref{Fi:Special_cases_alternative_solutions_example}. Superimposed on the feasible region is the contour $z=12$ of the objective function. The fact that the contour $z=12$ and all others are parallel to one edge of the feasible region can be immediately seen by observing that the objective function is a scalar multiple of the left-hand side of the first constraint.
\begin{figure}[h]
\centering
\includegraphics[width=.7\linewidth]{images/f03x04x01.eps}
\caption{Feasible region for LP \ref{E:Special_cases_alternative_solutions_example}. }\label{Fi:Special_cases_alternative_solutions_example}
\end{figure}

\newpar
After introducing two slack variables $s_1$ and $s_2$ and performing one iteration of the
simplex algorithm, we arrive at the tableau given in Table
\ref{Ta:Special_cases_alternative_solutions_example}.

\begin{table}[h]\caption{LP
(\ref{E:Special_cases_alternative_solutions_example}) after
one iteration}\label{Ta:Special_cases_alternative_solutions_example}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$  & RHS \\
\hline
1 & 0 & 0 & 3 & 0 & 24 \\ \hline
0 &  1 & $\frac{1}{4}$ & $\frac{1}{4}$ & 0 & 2  \\ \hline
0 &  0 & $\frac{3}{4}$ &  $-\frac{5}{4}$ & 1 & 2 \\ \hline
\end{tabular}
\end{table}

\noi We have $\ds \BV=\left\{x_1=2,s_2=2\right\}$, which corresponds to the
extreme point at $\ds \vecx=\begin{bmatrix} 2 \\ 0 \end{bmatrix}$.

\newpar
The nonbasic variables are given by $\ds \NBV=\left\{x_2,s_1\right\}$ and neither
has a negative coefficient in the top row, thereby indicating
 that the current solution is optimal. But let's take a closer look.
The top row of the tableau dictates that increasing $s_1$ will decrease the value of $z$. (In
fact, it will return us to the initial basic feasible solution at the origin!) On the other
hand, \emph{increasing the other nonbasic variable $x_2$ from its current value of
zero will not change the current $z$ value because $x_2$ currently has a coefficient of zero in the top row}.
An additional iteration of the simplex algorithm in which $x_2$ becomes basic
leads to $\ds x_1=\frac{4}{3}$,
$\ds x_2=\frac{8}{3}$, and $s_1=s_2=0$.  Thus, each of the vectors
$\ds \vecx=\begin{bmatrix} 2 \\ 0  \end{bmatrix} $
and
$\ds \vecx= \begin{bmatrix} \frac{4}{3} \\ \frac{8}{3} \end{bmatrix} $
are solutions to the LP. By exercise 5, of Section \ref{S:LP_BFS}, so is every point
on the line segment connecting the two vectors:
	\[\vecx
		=(1-t) \begin{bmatrix} 2 \\ 0 \\ 0 \\ 2 \end{bmatrix}+ t \begin{bmatrix} \frac{4}{3} \\ \frac{8}{3} \\ 0 \\ 0 \end{bmatrix}, \]
where $t \in [0,1]$. This infinite set of vectors corresponds to points along the edge of feasible region connecting
$\ds (2,0)$ and $\ds \left(\frac{4}{3},\frac{8}{3}\right)$.


\subsection{Unbounded Solutions}\index{linear programming problem!unbounded solutions}


\noi How do we determine whether an LP is unbounded from its tableau? (Recall that for a maximization problem, an unbounded
LP is one in which the objective function can be made arbitrarily large.) To answer this question,
we consider an LP
whose tableau at some stage of the simplex algorithm is almost identical to that from Table \ref{Ta:petroleum_second_tableau} of Section \ref{S:Simplex}, such as the one shown in
Table \ref{Ta:Special_cases_unbounded_solutions_example}.

\begin{table}[h]
\caption{Example tableau similar to \ref{Ta:petroleum_second_tableau} }\label{Ta:Special_cases_unbounded_solutions_example}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline
1 & 0 & -3 & 4 & 0 & 0 & 32 \\ \hline
0 &  1 & 0 & 1 & 0 & 0 & 8 \\ \hline
0 &  0 & $\bs$ & -2 & 1 & 0 & 12 \\ \hline
0 &  0 & $\bs$ & -3 & 0 & 1 & 8 \\ \hline
\end{tabular}
\end{table}.

\newpar
Assume that $x_1$, $s_2$, and $s_3$ are basic. The variable $x_2$ is the entering variable, and
clearly any strict increase in its value will lead to a strict increase in $z$.
The row of the tableau corresponding to the first constraint places no limit on the increase of
$x_2$ due to the coefficient of zero in the $x_2$ column. Thus, if either of the entries marked
$\bs$ were also zero, then the corresponding constraints would also place no limit on the increase of
$x_2$. But the same conclusion can be made if either of the entries marked $\bs$ were less than zero. The
variable $x_2$ could increase as large as desired, and slack variables could increase
in a positive manner ensuring
that all constraint equations were still satisfied. \emph{Thus, if a variable in the top row of an LP maximum problem has a negative coefficient and all the entries below the top row are less
than or equal to zero, then the LP is unbounded.}

\begin{progress_ck}%\label{Th:Special_cases_progress_ck_1}
The tableau shown in
Table \ref{Ta:Exercises_Special_cases_problem1} results when the simplex
    algorithm is used to solve a standard maximization LP. Assume that $a \geq 0$ and that $\ds \BV=\left\{x_1,s_1 \right\}$.
		\be
		\item For which values of $a$ does the LP have alternative optimal solutions?
		\item For which values of $a$ is the LP unbounded?
		\ee
\end{progress_ck}
	\begin{table}[h]
   \caption{Tableau for a standard maximization problem}
    \label{Ta:Exercises_Special_cases_problem1}
    \begin{tabular}{|c|c|c|c|c|c|} \hline
	$z$ & $x_1$ & $x_2$ &$s_1$ & $s_2$ & RHS \\ \hline
	1 & 0 & $1-a$ & 0 & $2-a$ & 1 \\ \hline
	0 & 1 & 0 & 0 & -1 & $a$ \\ \hline
	0 & 0 & $a-3$ & 1 & $a-4$ & 2 \\ \hline
	\end{tabular}
	\end{table}


\subsection{Degeneracy}\index{linear programming problem!degenerate}


\noi Recall that Definition \ref{Th:BFS} states the basic variables in any basic feasible solution must be nonnegative. For the examples we have considered thus far, basic variables have always been positive.
A \emph{degenerate}\index{degenerate|see{linear programming problem!degenerate}} LP is one that possesses a basic feasible solution in which at least one basic variable equals zero. Degenerate LPs are important from the standpoint
of convergence of the simplex algorithm.

\newpar
An important observation regarding the simplex algorithm is that from one iteration to the next, the objective
function increases by an amount equal to the value of the entering variable
multiplied by the negative of that variable's coefficient in the top row of the tableau. Thus, if an LP is nondegenerate, then the new value of each entering variable must be nonzero so that the objective function must strictly increase at each iteration. In particular, the simplex algorithm cannot encounter the same basic feasible solution, so the algorithm must terminate due to the finite number of such solutions.

\newpar
For a degenerate LP, the objective function can remain unchanged over successive iterations. One of the simplest examples illustrating this possibility is given by the LP

\begin{align}
 \mbox{maximize } z &=5x_1+2x_2  \label{E:Special_cases_degenerate_LP} \\
	\mbox{ subject to} \notag\\
	x_1 +x_2 &\leq 6 \notag\\
	x_1-x_2 &\leq 0  \notag\\
	x_1,x_2 &\geq 0,\notag
	\end{align}	
whose feasible region is shown in Figure \ref{Fi:Special_cases_degenerate_feasible_region}.

\begin{figure}[h]
\centering
  \includegraphics[width=.7\linewidth]{images/f03x04x02.eps}
\caption{Feasible region for a degenerate LP \ref{E:Special_cases_degenerate_LP}.} \label{Fi:Special_cases_degenerate_feasible_region}
\end{figure}

\newpar
The initial tableau for the LP is given in Table \ref{Ta:Special_cases_degenerate_LP}.

\begin{table}[h]
\caption{Initial tableau for \ref{E:Special_cases_degenerate_LP}}\label{Ta:Special_cases_degenerate_LP}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & RHS \\
\hline
1 & -5 & -2 & 0 & 0 & 0  \\ \hline
0 & 1 & 1 & 1 & 0 & 6 \\ \hline
0 & 1 & -1 & 0 & 1 & 0 \\ \hline
\end{tabular}
\end{table}

\newpar
If we start with our usual initial basic feasible solution $x_1=x_2=0$, we
see that $s_2=0$, so this LP is degenerate. From a graphical perspective, if we
temporarily view the sign conditions as constraints, then we can see that the LP is degenerate by observing there is an extreme point where equality holds for three, as opposed
to just two, of the four constraints.

\newpar
Following our ``usual rules,'' we allow $x_1$ to become basic, but we observe that, due to degeneracy,
the ratio corresponding to the bottom row is zero. To determine which of $s_1$ or $s_2$ becomes nonbasic, we consider
the equations corresponding to rows 1 and 2. Since $x_2$ remains nonbasic, the equation in row 1 corresponds to $x_2+s_1=6$, whereas that in row 2 yields $x_1+s_2=0$. The first equation permits $x_1$ to increase by 6. However, in the second equation, the basic variable $s_2=0$ so that $x_1$ cannot increase without $s_2$ becoming negative. If we treat the ratio in the bottom row as the smallest ``positive'' ratio and pivot in a way that $x_1$ replaces $s_2$ as a nonbasic variable, we obtain the new tableau in Table \ref{Ta:Special_cases_degenerate_LP2}.

\begin{table}[h]
\caption{Tableau after first iteration for \ref{E:Special_cases_degenerate_LP}}
\label{Ta:Special_cases_degenerate_LP2}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & RHS \\
\hline
1 & 0 & -7 & 0 & 5 & 0  \\ \hline
0 & 0 & 2 & 1 & -1 & 6 \\ \hline
0 & 1 & -1 & 0 & 1 & 0 \\ \hline
\end{tabular}
\end{table}

\newpar
Note that the objective function value has not changed from zero nor has the extreme point in
the feasible region. Only have the roles of $x_1$ and $s_2$ as basic versus nonbasic changed; their
values after the first iteration remain equal to zero.

\newpar
At the next iteration, $x_2$ becomes basic, and we are once again faced with a ratio of 0. In this case, the equations corresponding to the bottom two rows are given by $2x_2+s_1=6$ and $x_1-x_2=0$. The first permits $x_1$ to increase by 3. The second permits $x_2$ to increase without bound, provided $x_1$ does so as well in a manner that their difference remains equal to 0. Thus, we now let $x_2$ replace $s_1$ as a basic variable, and the final tableau becomes that shown in Table \ref{Ta:Special_cases_degenerate_LP2_SecondIteration}

\begin{table}[h]
\caption{Tableau after second iteration for \ref{E:Special_cases_degenerate_LP}}
\label{Ta:Special_cases_degenerate_LP2_SecondIteration}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & RHS \\
\hline
1 & 0 & 0 & $\frac{7}{2}$ & $\frac{3}{2}$ & 21  \\ \hline
0 & 0 & 1 & $\frac{1}{2}$ & $-\frac{1}{2}$ & 3 \\ \hline
0 & 1 & 0 & $\frac{1}{2}$ & $\frac{1}{2}$ & 3 \\ \hline
\end{tabular}
\end{table}

\noi We see that the optimal solution
corresponds to the extreme point, $\ds \begin{bmatrix} 3 \\ 3 \end{bmatrix}$ with an objective value of $z=21$.

\newpar
In this example, degeneracy led to ratios of zero, a situation we have not encountered thus far when performing the ratio test. But degeneracy can also result in ties when we perform the ratio test, implying there exists more than one choice for the departing basic variable. Endless
cycling\index{simplex algorithm!cycling}
between basic feasible solutions is possible depending upon how such ties are resolved. In real-life applications of linear
programming, this problem rarely occurs. In fact, any degenerate LP in which cycling occurs
must contain at least six decision variables \cite{Marshall_Cycling}. Moreover,
\emph{Bland's Rule}\index{Bland's Rule}
is an advanced linear programming tool
that overcomes the theoretical difficulty of cycling. Simply put, if the variables of the LP are
listed as a single variable with an increasing subscript, it dictates a ``smallest subscript rule.''
At any stage of the simplex algorithm, given a choice of two variables to enter the set of basic variables
or to leave the set of basic variables, always choose the variable with the smaller subscript.

\section*{Exercises Section \protect\ref{S:Special_cases}}
\addcontentsline{toc}{subsection}{Exercises}
\input{Exercises/Exercises_Special_Cases}

\endinput

	
	