\section{Alternative Optimal/Unbounded Solutions and Degeneracy}\label{S:ExerciseSolutions_Special_cases}
\setcounter{progress_ck_counter}{0}

\be
\item Exercise 1
\newpar

The initial tableau is shown in Table

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

After performing two iterations of the simplex algorithm, we obtain
the following:

\begin{table}[h]
\caption{Tableau after second iteration for Exercise 1}
\label{Ta:ExercisesSpecialCasesProblem1}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ &  RHS \\
\hline
1 & 0 & 0 & 2 & 0 & 12  \\ \hline
0 & 1 & 0 & 1 & -3  & 3 \\ \hline
0 & 0 & 1 & 0 & \fbox{1} &  1 \\ \hline
\end{tabular}
\end{table}

\noi
At this stage, the basic variables are $x_1=3$ and $x_2=1$, with a corresponding objective
value $z=12$. The nonbasic variable, $s_2$, has a coefficient of zero in the top row. Thus, letting
$s_2$ become basic will not change the value of $z$. In fact, if we pivot on the highlighted
entry in Table \ref{Ta:ExercisesSpecialCasesProblem1}, $x_2$ replaces $s_2$ as a nonbasic variable,
$x_1=6$, and the objective value is unchanged.

\item Exercise 2
\newpar
For an LP minimization problem to be unbounded, there must exist, at some stage of the simplex algorithm, a basic feasible solution in which a nonbasic variable has a negative coefficient in the top row and nonpositive coefficients in the remaining rows.

\item Exercise 3
\newpar
\be
\item For the current basic solution to not be optimal, it must be the case that $a<0$. However,
if the LP is bounded, then the ratio test forces $b>0$. Thus, we may pivot on row and column containing
$b$, in which case, we obtain the following tableau:

\begin{table}[h]
\caption{Tableau obtained after pivoting on row and column containing $b$}\label{Ta:ExercisesSpecialCasesProblem2}
\begin{tabular}{|c|c|c|c|c|c|} \hline
$z$ & $x_1$ & $x_2$ &$s_1$ & $s_2$ & RHS \\ \hline
1 & 0 & $-\frac{a}{b}$ & 0 & $3-\frac{a}{b}$ & $10-2\frac{a}{b}$ \\ \hline
0 & 1 & $\frac{1}{b}$ & 0 & $\frac{1}{b}-1$ & $3+\frac{2}{b}$ \\ \hline
0 & 0 & $\frac{1}{b}$ & 1 & $\frac{1}{b}$ & $\frac{2}{b}$ \\ \hline
\end{tabular}
\end{table}

\noi
Thus, $\ds x_1=3+\frac{2}{b}$, $\ds x_2=0$, and $\ds z=10-2\frac{a}{b}$.

\item If the given basic solution was optimal, then $a \geq 0$. However, if the LP
has alternative optimal solutions, then $a=0$. In this case, pivoting on the same entry
in the original tableau as we did in (b), we would obtain the result
in Table \ref{Ta:ExercisesSpecialCasesProblem2}, but with $a=0$. Thus, $\ds x_1=3+\frac{2}{b}$, $\ds x_2=0$, and $\ds z=10$.

\item If the LP is unbounded, then $a <0$ and $b\leq 0$.
\ee

\item Exercise 4
\newpar
\be
\item The coefficient of the nonbasic variable, $s_1$, in the top row of the tableau
is negative. Since the coefficient of $s_1$ in the remaining two rows is also negative, we see that the LP is unbounded.
\item So long as $s_2$ remains non basic, the equations relating $s_1$ to each of $x_1$ and $x_2$
are given by $x_1-2s_1=4$ and $x_2-s_1=5$. Thus, for each unit of increase in $s_1$, $x_1$ increases by
2 units; for each unit of increase in $s_1$, $x_2$ increases by 1 unit.
\item Eliminating $s_1$ from the equations $x_1-2s_1=4$ and $x_2-s_1=5$, we obtain $\ds x_2=\frac{1}{2}x_1+3$.
\item When $s_1=0$, $x_1=4$ and $x_2=5$. Since $s_1 \geq 0$, $x_1 \geq 4$ and $x_2 \geq 5$. Thus,we sketch  that portion of the line $\ds x_2=\frac{1}{2}x_1+3$ for which $x_1 \geq 4$ and $x_2 \geq 5$.
\item Since $z=1,000$, $z=x_1+3x_2$, and $\ds x_2=\frac{1}{2}x_1+3$, we have a system of equations whose
solution is given by $\ds x_1=\frac{1982}{5}$ and $\ds x_2=\frac{1006}{5}$.
\ee

\item Exercise 5
\newpar
\be
\item The LP has 2 decision variables and 4 constraints. Inspection of the graph shows that the constraints
are given by
\begin{align*}
2x_1+x_2 &\leq 10 \\
x_1+x_2 &\leq 6 \\
\frac{1}{2}x_1+x_2 &\leq 4 \\
-\frac{1}{2}x_1+x_2 &\leq 2.
\end{align*}

\noi By introducing slack variables, $s_1$, $s_2$, $s_3$, and $s_4$, we can convert the preceding list of inequalities to a system of equations in six variables, $x_1$, $x_2$, $s_1$, $s_2$, $s_3$, and $s_4$. Basic
feasible solutions are then most easily determined by substituting each of the extreme points into the system of equations and solving for the slack variables. The results are as follows:

\begin{multline*}
\begin{bmatrix} \vecx \\ \vecs \end{bmatrix}
= \begin{bmatrix}   0 \\ 0 \\ 10 \\ 6 \\ 4 \\ 2 \end{bmatrix}
= \begin{bmatrix}  5 \\ 0 \\ 1 \\ 1 \\ 3/2 \\ 9/2 \end{bmatrix} \\
= \begin{bmatrix}  4 \\ 2 \\ 0 \\ 0 \\ 0 \\ 2  \end{bmatrix}
= \begin{bmatrix}  2 \\ 3 \\ 3 \\ 1 \\ 0 \\ 0  \end{bmatrix}
= \begin{bmatrix}  0 \\ 2 \\ 8 \\ 4 \\ 2 \\ 0  \end{bmatrix}
\end{multline*}

\noi Observe that the extreme point $\ds \vecx=\begin{bmatrix} 4 \\ 2 \end{bmatrix}$
yields slack variable values for which $s_1=s_2=s_3=0$. This means that when any two of these
three variables are chosen to be nonbasic, the third variable, which is basic, must be zero. Hence,
the LP is degenerate. From a graphical perspective, the LP is degenerate because the boundaries of three of the constraints intersect at the single extreme point,
$\ds \vecx=\begin{bmatrix} 4 \\ 2 \end{bmatrix}$

\item If the origin is the initial basic feasible solution, at least two simplex algorithm iterations are required before a degenerate basic feasible solution results. This occurs when the objective coefficient of $x_1$ is larger than that of $x_2$. In this case, the intermediate iteration yields
    $\ds \vecx=\begin{bmatrix} 5 \\ 0 \end{bmatrix}$. If the objective coefficient of $x_2$ is positive and
    larger than that of $x_1$, then at most three iterations are required.

\ee





\ee

% WAYPOINT SOLUTIONS

\hrulefill

\newpar
\textbf{Solutions to Waypoints}

\begin{waypoint}
\be
\item The current basic feasible solution consists of $x_1=a$, $s_1=2$, and $x_2=s_2=0$. The LP has
alternative optimal solutions if a nonbasic variable has a coefficient of zero in the top row of the
tableau. This occurs when $a=1$ or $a=2$.
\item The LP is unbounded if both $1-a<0$ and $a-3 <0$, i.e., if $1< a \leq 3$. The LP is also unbounded if both $2-a < 0$ and $a-4 \leq 0$, i.e., if $2 < a \leq 4$.
\ee
\end{waypoint}

\endinput 