\section{Excess and Artificial Variables: The Big M Method}\label{S:ExerciseSolutions_BigM}

\setcounter{progress_ck_counter}{0}

\be
\item 
\be
%  EXERCISE 1A
\item We let $e_1$ and $a_1$ denote the excess and artificial variables, respectively, that correspond
to the first constraint. Similarly, we let $e_2$ and $a_2$ correspond to the second constraint. Using $M=100$, our objective becomes one of minimizing $z=-x_1+4 x_2 + 100a_1 + 100a_2$. If $s_3$ is the slack variable corresponding
to the third constraint our initial tableau is as follows:

\begin{table}[h]
\caption{Initial tableau}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $e_1$ & $a_1$ & $e_2$ & $a_2$ & $s_3$ & RHS \\
\hline
1 & 1 & -4 & 0 & -100 & 0 & -100 & 0 & 0 \\ \hline
0 & 1 & 3 & -1 & \fbox{1} & 0 & 0 & 0 & 8 \\ \hline
0 & 1 & 1 & 0 & 0 & -1 & \fbox{1} & 0 & 4 \\ \hline
0 & 1 & -1 & 0 & 0 & 0 & 0 & 1 & 2 \\
\hline
\end{tabular}
\end{table}

\noi To obtain an initial basic feasible solution, we pivot on each of the highlighted entries in this tableau. The result is the following:

\begin{table}[h]
\caption{Tableau indicting initial basic feasible solution}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $e_1$ & $a_1$ & $e_2$ & $a_2$ & $s_3$ & RHS \\
\hline
1 & 201 & 396 & -100 & 0 & -100 & 0 & 0 & 1200 \\
0 & 1 & 3 & -1 & 1 & 0 & 0 & 0 & 8 \\
0 & 1 & 1 & 0 & 0 & -1 & 1 & 0 & 4 \\
0 & 1 & -1 & 0 & 0 & 0 & 0 & 1 & 2 \\
\hline
\end{tabular}
\end{table}

\noi Three iterations of the simplex algorithm are required before all coefficients in the top row
of the tableau that correspond to nonbasic variables are nonpositive. The final tableau is given by

\begin{table}[h]
\caption{Final tableau}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $e_1$ & $a_1$ & $e_2$ & $a_2$ & $s_3$ & RHS \\
\hline
1 & 0 & 0 -3/4 & -397/4 & 0 & -100 & -7/4 & 5/2 \\ \hline
0 & 0 & 1 & -1/4 & 1/4 & 0 & 0 & -1/4 & 3/2 \\ \hline
0 & 1 & 0 & -1/4 & 1/4 & 0 & 0 & 3/4 & 7/2 \\ \hline
0 & 0 & 0 & -1/2 & 1/2 & 1 & -1 & 1/2 & 1 \\
\hline
\end{tabular}
\end{table}

\newpar
The solution is $\ds x_1=\frac{7}{2}$ and $\ds x_2=\frac{3}{2}$, with $\ds x_2=\frac{5}{2}$.

%  EXERCISE 1B

\item We let $e_1$ and $a_1$ denote the excess and artificial variables, respectively, that correspond
to the first constraint. Similarly, we let $e_3$ and $a_3$ correspond to the third constraint. Using $M=100$, our objective becomes one of minimizing $z=x_1+x_2 + 100a_1 + 100a_3$. If $s_2$ is the slack variable corresponding
to the second constraint our initial tableau is as follows:

\begin{table}[h]
\caption{Initial tableau}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $e_1$ & $a_1$ & $s_2$ & $e_3$ & $a_3$ & RHS \\
\hline
1 & -1 & -1 & 0 & -100 & 0 & 0 & -100 & 0 \\ \hline
0 & 2 & 3 & -1 & \fbox{1} & 0 & 0 & 0 & 30 \\ \hline
0 & -1 & 2 & 0 & 0 & 1 & 0 & 0 & 6 \\ \hline
0 & 1 & 3 & 0 & 0 & 0 & -1 & \fbox{1} & 18 \\
\hline
\end{tabular}
\end{table}

\noi To obtain an initial basic feasible solution, we pivot on each of the highlighted entries in this tableau. The result is the following:

\begin{table}[h]
\caption{Tableau indicting initial basic feasible solution}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $e_1$ & $a_1$ & $s_2$ & $e_3$ & $a_3$ & RHS  \\
\hline
1 & 299 & 599 & -100 & 0 & 0 & -100 & 0 & 4800 \\ \hline
0 & 2 & 3 & -1 & 1 & 0 & 0 & 0 & 30 \\ \hline
0 & -1 & 2 & 0 & 0 & 1 & 0 & 0 & 6 \\ \hline
0 & 1 & 3 & 0 & 0 & 0 & -1 & 1 & 18 \\
\hline
\end{tabular}
\end{table}

\noi Three iterations of the simplex algorithm lead to a final tableau given by

\begin{table}[h]
\caption{Final tableau}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $e_1$ & $a_1$ & $s_2$ & $e_3$ & $a_3$ & RHS \\
\hline
1 & 0 & 0 & -3/7 & -697/7 & -1/7 & 0 & -100 & 12 \\ \hline
0 & 0 & 0 & -5/7 & 5/7 & 3/7 & 1 & -1 & 6 \\ \hline
0 & 0 & 1 & -1/7 & 1/7 & 2/7 & 0 & 0 & 6 \\ \hline
0 & 1 & 0 & -2/7 & 2/7 & -3/7 & 0 & 0 & 6 \\
\hline
\end{tabular}
\end{table}

\newpar
The solution is $\ds x_1=6$ and $\ds x_2=6$, with $\ds x_2=12$.


%  EXERCISE 1C

\item We let $a_1$ denote the artificial variable corresponding to the first (equality)
constraint, and we let $e_2$ and $a_2$ denote the excess and artificial variables, respectively,
that correspond to the second constraint. Using $M=100$, our objective becomes one of
maximizing $z=x_1+5x_2 + 6x_3- 100a_1 - 100a_2$. The initial tableau is given by 


\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$ & $a_1$ & $e_2$ & $a_2$ & RHS \\
\hline
1 & -1 & -5 & -6 & 100 & 0 & 100 & 0 \\ \hline
0 & 1 & 4 & 2 & \fbox{1} & 0 & 0 & 50 \\ \hline
0 & 1 & -4 & 4 & 0 & -1 & \fbox{1} & 40 \\
\hline
\end{tabular}
\end{table}

\noi To obtain an initial basic feasible solution, we pivot on each of the highlighted entries in this tableau. The result is the following:

\begin{table}[h]
\caption{Tableau indicting initial basic feasible solution}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $x_3$ & $a_1$ & $e_2$ & $a_2$ & RHS \\
\hline
1 & -201 & -5 & -606 & 0 & 100 & -9000 \\ \hline
0 & 1 & 4 & 2 & 1 & 0 & 0 & 50 \\ \hline
0 & 1 & -4 & 4 & 0 & -1 & 1 & 40 \\
\hline
\end{tabular}
\end{table}

\noi Three iterations of the simplex algorithm are required before all coefficients in the top row
of the tableau that correspond to nonbasic variables are nonnegative. The final tableau is given by

\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$ & $a_1$ & $e_2$ & $a_2$ & RHS \\
\hline
1 & 2 & 7 & 0 & 103 & 0 & 100 & 150 \\
0 & 1 & 12 & 0 & 2 & 1 & -1 & 60 \\
0 & 1/2 & 2 & 1 & 1/2 & 0 & 0 & 25 \\
\hline
\end{tabular}
\end{table}

\newpar
The solution is $\ds x_1=x_2=0$ and $\ds x_3=25$, with $\ds z=150$.


\ee
\ee

% WAYPOINT SOLUTIONS

\hrulefill

\newpar
\textbf{Solutions to Waypoints}

\begin{waypoint}
The LP is given by
\begin{align*}
 \mbox{maximize } z &=\vecc \cdot \vecx    \\
	\mbox{ subject to} \\
	\left[A | I_2 \right] \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} &= \vecb  \\
	\vecx, \vecs  &\geq \zerovec,  \notag
	\end{align*}
where $\ds A= \begin{bmatrix} 1.64 & 2.67 \\ -2.11 & -2.3 \end{bmatrix}$,
$\ds  \vecc=\begin{bmatrix} -45.55 & -21.87 \end{bmatrix}$,
$\ds \vecb= \begin{bmatrix} 31.2 \\ -13.0 \end{bmatrix}$,
$\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$, and
$\ds \vecs= \begin{bmatrix} s_1 \\ s_2 \end{bmatrix}$.
\end{waypoint}

\begin{waypoint}
Let $s_1$ denote the slack variable for the first constraint, and let $e_2$ and $a_2$
denote the excess and artificial variables, respectively, for the second constraint. Using $M=100$, our objective becomes one of
minimizing $z=45.55x_1+21.87x_2+100a_2$. The initial tableau is as follows:


\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$ & $e_2$ & $a_2$ & RHS \\
\hline
1 & -45.55 & -21.87 & 0 & 0 & -100 & 0 \\ \hline
0 & 1.64 & 2.67 & 1 & 0 & 0 & 31.2 \\ \hline
0 & 2.11 & 2.3 & 0 & -1 & \fbox{1} & 13.9 \\ \hline
\end{tabular}
\end{table}

\noi To obtain an initial basic feasible solution, we pivot on the highlighted entry in this tableau. The result is the following:

\begin{table}[h]
\caption{Tableau indicting initial basic feasible solution}%\label{Ta:Initial tableau 1a}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $e_2$ & $a_2$ & RHS \\
\hline
1 & 165 & 208 & 0 & -100 & 0 & 1390 \\ \hline
0 & 1.64 & 2.67 & 1 & 0 & 0 & 13.2 \\ \hline
0 & 2.11 & 2.3 & 0 & -1 & 1 & 13.9 \\ 
\hline
\end{tabular}
\end{table}

\noi Two iteration of the simplex algorithm yield the final tableau:

\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$ & $e_2$ & $a_2$ & RHS \\
\hline
1 & -26 & 0 & 0 & -9.5 & -90.5 & 132.17 \\ \hline
0 & -.81 & 0 & 1 & 1.16 & -1.16 & 15 \\ \hline
0 & .918 & 1 & 0 & -.435 & .435 & 6.04 \\
\hline
\end{tabular}
\end{table}

\noi Thus $x_1$ is nonbasic so that the total foraging time is minimized when $x_1 =0$ grams of grass and $x_2 \approx 6.04$ grams of forb, in which case  $z \approx 132.17$ minutes
\end{waypoint}


\endinput 