\section{The Simplex Algorithm}\label{S:ExerciseSolutions_Simplex}
\setcounter{progress_ck_counter}{0}

\be
\item For each LP, we indicate the tableau after each iteration and highlight the pivot
entry used to perform the next iteration.

\be
\item
\newpar

\begin{table}[h]
\caption{Initial tableau}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline
1 & -3 & -2 & 0 & 0 & 0 & 0 \\ \hline
0 & \fbox{1} & 0 & 1 & 0 & 0 & 4 \\ \hline
0 & 1 & 3 & 0 & 1 & 0 & 15 \\ \hline
0 & 2 & 1 & 0 & 0 & 1 & 10  \\
\hline
\end{tabular}
\end{table}

\noi
\begin{table}[h]
\caption{Tableau after first iteration}%\label{Ta:Initial tableau 1a}
\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 & -2 & 3 & 0 & 0 & 12 \\ \hline
0 & 1 & 0 & 1 & 0 & 0 & 4 \\ \hline
0 & 0 & 3 & -1 & 1 & 0 & 11 \\ \hline
0 & 0 & \fbox{1} & -2 & 0 & 1 & 2 \\ \hline
\end{tabular}
\end{table}

\noi
\begin{table}[h]
\caption{Tableau after second iteration}%\label{Ta:Initial tableau 1a}
\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 & 0 & -1 & 0 & 2 & 16 \\ \hline
0 & 1 & 0 & 1 & 0 & 0 & 4 \\ \hline
0 & 0 & 0 & \fbox{5} & 1 & -3 & 5 \\ \hline
0 & 0 & 1 & -2 & 0 & 1 & 2 \\ \hline
\end{tabular}
\end{table}

\noi
\begin{table}[h]
\caption{Final tableau}%\label{Ta:Initial tableau 1a}
\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 & 0 & 0 & 1/5 & 7/5 & 17 \\ \hline
0 & 1 & 0 & 0 & -1/5 & 3/5 & 3 \\ \hline
0 & 0 & 0 & 1 & 1/5 & -3/5 & 1 \\ \hline
0 & 0 & 1 & 0 & 2/5 & -1/5 & 4 \\ \hline
\end{tabular}
\end{table}

\newpar
The solution is $x_1=3$ and $x_2=4$, with $z=17$.



\item
\newpar

\begin{table}[h]
\caption{Initial tableau}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline
1 & -4 & -3 & 0 & 0 & 0 & 0 \\ \hline
0 & \fbox{1} & 0 & 1 & 0 & 0 & 4 \\ \hline
0 & -2 & 1 & 0 & 1 & 0 & 12 \\ \hline
0 & 1 & 2 & 0 & 0 & 1 & 14  \\
\hline
\end{tabular}
\end{table}

\noi
\begin{table}[h]
\caption{Tableau after first iteration}%\label{Ta:Initial tableau 1a}
\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 & 16 \\ \hline
0 & 1 & 0 & 1 & 0 & 0 & 4 \\ \hline
0 & 0 & 1 & 2 & 1 & 0 & 20 \\ \hline
0 & 0 & \fbox{2} & -1 & 0 & 1 & 10 \\ \hline
\end{tabular}
\end{table}


\noi
\begin{table}[h]
\caption{Final tableau}%\label{Ta:Initial tableau 1a}
\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 & 0 & 5/2 & 0 & 3/2 & 31 \\ \hline
0 & 1 & 0 & 1 & 0 & 0 & 4 \\ \hline
0 & 0 & 0 & 5/2 & 1 & -1/2 & 15 \\ \hline
0 & 0 & 1 & -1/2 & 0 & 1/2 & 5 \\ \hline
\end{tabular}
\end{table}

\newpar
The solution is $x_1=4$ and $x_2=5$, with $z=31$.


\item
\newpar

\begin{table}[h]
\caption{Initial tableau}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $x_3$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline
1 & -4 & -1 & -5 & 0 & 0 & 0 & 0 \\ \hline
0 & 2 & 1 & \fbox{3} & 1 & 0 & 0 & 14 \\ \hline
0 & 6 & 3 & 3 & 0 & 1 & 0 & 22 \\ \hline
0 & 2 & 3 & 0 & 0 & 0 & 1 & 14  \\
\hline
\end{tabular}
\end{table}

\noi
\begin{table}[h]
\caption{Tableau after first iteration}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $x_3$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline
1 & -2/3 & 2/3 & 0 & 5/3 & 0 & 0 & 70/3 \\ \hline
0 & 2/3 & 1/3 & 1 & 1/3 & 0 & 0 & 14/3 \\ \hline
0 & \fbox{4} & 2 & 0 & -1 & 1 & 0 & 8 \\ \hline
0 & 2 & 3 & 0 & 0 & 0 & 1 & 14  \\
\hline
\end{tabular}
\end{table}


\noi
\begin{table}[h]
\caption{Final tableau}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $x_3$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline
1 & 0 & 1 & 0 & 3/2 & 1/6 & 0 & 74/3 \\ \hline
0 & 0 & 0 & 1 & 1/2 & -1/6 & 0 & 10/3 \\ \hline
0 & 1 & 1/2 & 0 & -1/4 & 1/4 & 0 & 2 \\ \hline
0 & 0 & 2 & 0 & 1/2 & -1/2 & 1 & 10  \\
\hline
\end{tabular}
\end{table}

\newpar
The solution is $x_1=2$, $x_2=0$, and $\ds x_3=\frac{10}{3}$, with $z=\ds \frac{74}{3}$.



\item
\newpar

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

\noi
\begin{table}[h]
\caption{Final tableau}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$  & RHS \\
\hline
1 & -5 & 0 & 0 & -2 & -8 \\ \hline
0 & 3 & 0 & 1 & 2 & 10 \\ \hline
0 & 1 & 1 & 0 & 1 & 4 \\ \hline
\end{tabular}
\end{table}

\newpar
This is a minimization problem, so we terminate the algorithm when all coefficients 
in the top row that correspond to nonbasic variables are nonpositive. The solution is $x_1=0$
and $x_2=4$, with $z=-8$.


\ee

\item If we rewrite the first and second constraints as
$-x_1-3x_2 \leq -8$ and $-x_1-x_2 \leq -4$ and incorporate
slack variables as usual, our initial tableau becomes that shown
in Table \ref{Ta:Initial tableau 2}

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

\noi
The difficulty we face when attempting to perform the simplex algorithm, centers on the fact that 
the origin, $(x_1,x_2)=(0,0)$ yields negative values of $s_1$ and $_2$. In other words,
the origin corresponds to a basic, but not basic feasible, solution. We cannot read off the initial
basic feasible solution as we could for Exercise (1d).


\item We list those constraints that are binding for each LP.
\be
\item Constraints 2 and 3
\item Constraints 1 and 3
\item Constraints 1 and 2
\item Constraint 2
\ee

\ee

% WAYPOINT SOLUTIONS

\hrulefill

\newpar
\textbf{Solutions to Waypoints}

\begin{waypoint}
We first state the LP in terms of maximization. If we set $\tilde{z}=-z$, then
\begin{align}\label{E:waypoint2_1}
\mbox{maximize } \tilde{z} &=5x_1-2x_2 \\
	\mbox{  subject to}   \notag \\
    x_1 \x \x &\leq 2 \notag\\
	3x_1+2x_2  &\leq 6  \notag\\
	8x_1 + 3x_2 &\leq 12 \notag \\
	x_1,x_2 &\geq 0,\notag
	\end{align}
where $\tilde{z}=-z$.

\noi The initial tableau corresponding to LP (\ref{E:waypoint2_1})
is given by
\begin{table}[h]
\caption{Initial tableau}\label{Ta:initialtableau waypoint2_1}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline
1 & -5 & 2 & 0 & 0 & 0 & 0   \\ \hline
0 & 1 & 0 & 1 & 0 & 0 & 2 \\ \hline
0 & 3 & 2 & 0 & 1 & 0 & 6 \\ \hline
0 & \fbox{8} & 3 & 0 & 0 & 1 & 12 \\ \hline
\end{tabular}
\end{table}

\noi
Since we are now solving a maximization problem, we pivot on the
highlighted entry in this tableau, which yields the following: 

\begin{table}[h]
\caption{Final tableau}\label{Ta:finaltableau waypoint2_1}
\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 & 31/8 & 0 & 0 & 5/8 & 15/2   \\ \hline
0 & 0 & -3/8 & 1 & 0 & -1/8 & 1/2 \\ \hline
0 & 0 & 7/8 & 0 & 1 & -3/8 & 3/2 \\ \hline
0 & 1 & 3/8 & 0 & 0 & 1/8 & 3/2 \\ \hline
\end{tabular}
\end{table}

\noi
All entries in the top row corresponding to nonbasic variables
are positive. Hence $x_1=\frac{3}{2}$ and $x_2=0$ is a solution of the LP. However,
the objective value corresponding to this optimal solution, for the original LP,
is given by $z = -\tilde{z}=-\frac{15}{2}$.

\end{waypoint}



\endinput 