\section{Excess and Artificial Variables: The Big M Method}\label{S:Big_M}
\setcounter{progress_ck_counter}{0}

\noi In this section we describe a technique by which we can modify the simplex algorithm to
solve LPs whose initial basic feasible solutions are not readily apparent. An example of
such an LP is given by the
\emph{Foraging Herbivore Model}\index{Foraging Herbivore Model}, from Exercise 4 of Section
\ref{S:LP_Prototype_Standard_Form}. For the sake of completeness, we reconstruct this model here.

\newpar
	In certain parts of the U.S., studies have shown that the
	vole, or common field mouse, is an herbivore whose diet consists
	predominantly of grass and a type of broad-leafed herb known as forb. Empirical studies
	suggest that the vole forages in a way that minimizes its
    total foraging time, subject to a set of two constraints \cite{Belovsky_herbivores}.
	
    \newpar
	Table \ref{Ta:Big_M_Foraging_Data} provides relevant information
	concerning digestive capacity and 	
	energy content. Food bulk records the extent to which the mass
    of a substance increases after it enters the digestive system and becomes
    liquid-saturated. For example,
    two grams of grass, when consumed, expands to $2 \times 1.64=3.28$ grams
    within the digestive system. To distinguish
    the mass of food prior to consumption from that in the digestive system,
    we use units of gm-dry and gm-wet, respectively.

	\begin{table}[h]
    \caption{Data for \emph{Foraging Herbivore} model}
    \label{Ta:Big_M_Foraging_Data}
	\begin{tabular}{|l|c|c|c|} \hline
	&
	{\scriptsize{Food bulk (gm-wet/gm-dry)}}
	&  {\scriptsize{Energy content (kcal/gm)}} \\ \hline
	Grass & 1.64 &  2.11 \\ \hline
	Forb & 2.67 &  2.30 \\ \hline
	\end{tabular}
	\end{table}
	
	\newpar
	The digestive capacity of the vole is 31.2 gm-wet per day, and the vole must consume enough food to meet an energy requirement of at least 13.9 kcal per day. Assume that the vole's foraging rate is 45.55 minutes per gram of grass and 21.87 minutes per gram of forb.

	\newpar
	Let $x_1$ and $x_2$ denote the quantity of grass and forb,
	respectively, consumed by the vole on a given day. Units of both $x_1$ and $x_2$ are gm-dry, and consumption results in a total mass of $1.64x_1+2.67x_2$ gm-wet within the digestive system. Food bulk
limitations then lead to the constraint
\begin{equation*} 1.64x_1+2.67x_2 \leq 31.2.
\end{equation*}

\noi Similar reasoning, based upon
the daily energy requirement, yields \newline
$2.11x_1+2.3x_2 \geq 13.9$. Finally, the total foraging time, the quantity we seek to minimize, is given by $z=45.55x_1+21.87x_2$. Combining these results,
we arrive at the LP given in (\ref{E:BigMForagingModel}).

\begin{align}
 \mbox{minimize } z &=45.55x_1+21.87x_2 \label{E:BigMForagingModel}  \\
	\mbox{ subject to} \notag\\
    1.64x_1+2.67x_2 &\leq 31.2  \notag\\
    2.11x_1+2.3x_2 &\geq 13.9 \notag\\
	x_1,x_2 &\geq 0. \notag
	\end{align}	

\begin{progress_ck}
Express LP (\ref{E:BigMForagingModel}) in the standard matrix form,
\begin{align}
 \mbox{maximize } z &=\vecc \cdot \vecx   \label{E:BigMForagingModelMatrixForm} \\
	\mbox{ subject to} \notag\\
	\left[A | I_2 \right] \begin{bmatrix}  \vecx \\ \vecs  \end{bmatrix} &= \vecb \notag \\
	\vecx, \vecs  &\geq \zerovec.  \notag
	\end{align}
Clearly specify the quantities, $\vecc$, $A$, and $\vecb$. The vector $\vecb$ should have one negative entry.
\end{progress_ck}

\newpar
In previously encountered LPs, an initial basic
solution has been found by choosing decision variables as nonbasic and slack variables as basic. In the case of (\ref{E:BigMForagingModelMatrixForm}), this approach does not work. Specifically, if all decision variables are set to zero, entries of $\vecs$ are uniquely determined but at least one is negative due to the negative entry in $\vecb$. Hence, setting the decision variables equal to zero leads to a basic, but not basic feasible, solution. From a graphical perspective, as shown in Figure \ref{Fi:Big_M_Foraging_Feasible}, the difficulty stems from the fact the origin lies outside
the feasible region.

\begin{figure}[h]
\centering
\psfrag{x1_axis_label}[Bc][Bc]{$x_1$}
\psfrag{x2_axis_label}[Bc][Bc]{$x_2$}
\includegraphics[width=.7\linewidth]{images/f03x05x01.eps}
\caption{Feasible region for the foraging herbivore LP, (\ref{E:BigMForagingModel}).}
\label{Fi:Big_M_Foraging_Feasible}
\end{figure}


\newpar
To investigate how the simplex algorithm can be modified to address this type of situation, we first consider the numerically simpler LP given by

\begin{align}\label{E:BigM_LP}
 \mbox{minimize } z &=3x_1+x_2   \\
	\mbox{ subject to} \notag\\
	x_1 +x_2 &\leq 6 \notag\\
	x_1\phantom{+3x_2} &\geq 1  \notag\\
	2x_1+x_2 &= 10  \notag\\
	x_1,x_2 &\geq 0. \notag
	\end{align}

\noi
Note that LP (\ref{E:BigM_LP}) has an equality constraint; thus, its feasible region consists of
a segment in $\R^2$.

\newpar
Certainly we can introduce a slack variable, $s_1$ in the first constraint so
that it becomes $x_1+x_2+s_1=6.$
But rewriting the second constraint in $\leq$ form and adding a slack variable will only
lead to the same problem of finding an initial basic feasible solution, so we instead
{\underbar{subtract}} from $x_1$ a
nonnegative \emph{excess variable}\index{excess variable}, $e_2$, and rewrite
the second constraint as $x_1-e_2=1$. Clearly we can find nonnegative values of $x_1$ and $e_2$
that satisfy this equation, but determining nonnegative values of $x_2$ and $s_1$ that satisfy the other two constraint equations may still prove quite difficult.

\newpar
To address this challenge, we introduce even more variables, called \emph{artificial variables}\index{artificial variable}, which
are added to those constraints in which a $\geq$ or $=$ is present. To the second and third constraints, we introduce the nonnegative artificial variables $a_2$ and $a_3$, respectively, so that
(\ref{E:BigM_LP}) becomes

\begin{align}
 \mbox{minimize } z &=3x_1+x_2 \label{E:BigM_LP2} \\
 \mbox{ subject to} \notag \\
	x_1 +x_2 + s_1 \phantom{-e_2} \phantom{+a_2} \phantom{+a_3} &= 6 \notag\\
	x_1 \phantom{+x_2} \phantom{+s_1} -e_2 + a_2  \phantom{+a_3}  &= 1  \notag\\
	2x_1+x_2 \phantom{+s_1} \phantom{-e_2} \phantom{+a_2}  +a_3& = 10  \notag\\
	x_1,x_2, s_1, e_2, a_2, a_3 &\geq 0.\notag
	\end{align}

\newpar
Clearly this system yields a basic
feasible solution in which the basic variables are given
by $s_1=6$, $a_2=1$, and $a_3=10$.

\newpar
The introduction of artificial variables therefore eliminates the difficulty
of finding an initial basic feasible solution. However, these additional variables may yield an LP whose solution differs from that of the original LP. We therefore modify the objective function of the original LP
so that all artificial variables in the new LP's final solution
are ensured to equal zero. For if this outcome occurs and all artificial variables
are zero, then the values of all remaining variables (decision, slack, and excess)
are exactly the same as those in the optimal solution to the original LP.

\newpar
The simplest way to modify the original objective function is to rewrite it as
\[ z= 3x_1 + x_2 + Ma_2 + Ma_3,\]
where $M$ is chosen to be a very large number.
While there is no definitive rule as to how large $M$ should be,
it is important that $M$ be significantly
larger than any of the coefficients in the objective function, large enough so that any
nonzero artificial variable value in the final solution results in a significantly larger
$z$ value. Put another way, the objective function incurs a substantial penalty of $M$ units for every one unit
increase in any artificial variable. Thus, we call this approach for solving the LP the
\emph{Big M Method}.\index{Big M Method}
For the particular example under discussion, we set $M=20$. The initial tableau
for the LP is given in Table \ref{Ta:Big_M_example1}.
\begin{table}[h]
\caption{$\mbox{BV}=\left\{s_1,a_2,a_3 \right\} $ }
	\label{Ta:Big_M_example1}
	\begin{tabular}{|c|c|c|c|c|c|c|c|}
	\hline
	$z$ & $x_1$ & $x_2$ & $s_1$ & $e_2$ & $a_2$ & $a_3$ &  RHS \\ \hline
	1 & -3 & -1 & 0 & 0 & -20 & -20 & 0  \\ \hline
	0 & 1 & 1 & 1 & 0 & 0 & 0 & 6  \\ \hline
	0 & 1 & 0 & 0 & -1 & 1 & 0 & 1  \\ \hline
	0 & 2 & 1 & 0 & 0 & 0 & 1 & 10  \\
	\hline
\end{tabular}
	\end{table}
	
\newpar
Since $a_2$ and $a_3$ are basic variables at the outset, pivots in
 their columns are necessary to record the initial objective function value. Performing two pivots
yields the tableau in Table \ref{Ta:Big_M_example2}.	

\begin{table}[h]
\caption{$\mbox{BV}=\left\{s_1,a_2,a_3 \right\} $ }
	\label{Ta:Big_M_example2}
	\begin{tabular}{|c|c|c|c|c|c|c|c|}
	\hline
	$z$ & $x_1$ & $x_2$ & $s_1$ & $e_2$ & $a_2$ & $a_3$ &  RHS \\ \hline
	1 & 57 & 19 & 0 & -20 & 0 & 0 & 220  \\ \hline
	0 & 1 & 1 & 1 & 0 & 0 & 0 & 6  \\ \hline
	0 & \fbox{1} & 0 & 0 & -1 & 1 & 0 & 1  \\ \hline
	0 & 2 & 1 & 0 & 0 & 0 & 1 & 10  \\
	\hline
\end{tabular}
	\end{table}

\newpar
As this is a minimization LP, we focus on the column corresponding to the nonbasic variable
whose coefficient in the top row of the tableau is most positive. This variable is $x_1$. By the
ratio test, $x_1$ replaces $a_2$ as a basic variable, and we pivot on the indicated
entry in Table \ref{Ta:Big_M_example2}. The resulting tableau is given in Table \ref{Ta:Big_M_example3}.

\begin{table}[h]
\caption{$\mbox{BV}=\left\{x_1,s_1,a_3 \right\} $}
	\label{Ta:Big_M_example3}
	\begin{tabular}{|c|c|c|c|c|c|c|c|}
	\hline
	$z$ & $x_1$ & $x_2$ & $s_1$ & $e_2$ & $a_2$ & $a_3$ &  RHS \\ \hline
	1 & 0 & 19 & 0 & 37 & -57& 0 & 163  \\ \hline
	0 & 0 & 1 & 1 & 1 & -1 & 0 & 5  \\ \hline
	0 & 1 & 0 & 0 & -1 & 1 & 0 & 1 \\ \hline
    0 & 0 & 1 & 0 & 2 & -2 & 1 & 8 \\
	\hline
	\end{tabular}
	\end{table}	

\newpar
Two more iterations of the simplex algorithm are then necessary to achieve the optimal solution. The intermediate and final tableaus are given in Tables \ref{E:Big_M_example4} and \ref{E:Big_M_example5}.

\begin{table}[h]
\caption{$\mbox{BV}=\left\{x_1,s_1,e_2 \right\} $ }
	\label{E:Big_M_example4}
	\begin{tabular}{|c|c|c|c|c|c|c|c|}
	\hline
	$z$ & $x_1$ & $x_2$ & $s_1$ & $e_2$ & $a_2$ & $a_3$ &  RHS \\ \hline
	1 & 0 & $\frac{1}{2}$ & 0 & 0 & -20 & $-\frac{37}{2}$ & 15 \\ \hline
    0 & 0 & $\frac{1}{2}$ & 1 & 0 & 0 & $-\frac{1}{2}$ & 1 \\ \hline
    0 & 1 & $\frac{1}{2}$ & 0 & 0 & 0 & $\frac{1}{2}$ & 5 \\ \hline
    0 & 0 & $\frac{1}{2}$ & 0 & 1 & -1& $\frac{1}{2}$ & 4 \\
	\hline
	\end{tabular}
	\end{table}	

\begin{table}[h]
\caption{$\mbox{BV}=\left\{x_1,x_2,e_2 \right\} $}
	\label{E:Big_M_example5}
	\begin{tabular}{|c|c|c|c|c|c|c|c|}
	\hline
	$z$ & $x_1$ & $x_2$ & $s_1$ & $e_2$ & $a_2$ & $a_3$ &  RHS \\ \hline
	1 & 0 & 0 & -1  & 0 & -20 & -18 & 14  \\ \hline
    0 & 0 & 1 & 2 & 0 & 0 & -1 & 2 \\ \hline
    0 & 1 & 0 & -1 & 0 & 0 & 1 & 4 \\ \hline
    0 & 0 & 0 & -1 & 1 & -1 & 1 & 3 \\
	\hline
	\end{tabular}
	\end{table}	
\newpar
Recall that because this is a standard minimization problem, we terminate the algorithm when
entries in the top row of the tableau corresponding to nonbasic variables are all
nonpositive. Thus the optimal solution is given by $\ds \left(x_1,x_2\right)=\left(4,2\right)$
and an objective value of $\ds z=14$. It is extremely important to
observe that in this solution, both artificial variables are nonbasic!

\newpar
To summarize, the Big M Method is a means of adapting the simplex algorithm to LPs involving a wider variety of constraints. We start with an LP written in a way that the right-hand side of each constraint is nonnegative. To each constraint involving a $\geq$, we subtract a positive excess variable and add an artificial variable. To
each equality constraint, we simply add an artificial variable.

\begin{progress_ck}
Now use the Big M Method to solve the Foraging Herbivore Model (\ref{E:BigMForagingModel}).
\end{progress_ck}

\section*{Exercises Section \protect\ref{S:Big_M} }

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_Big_M}
	
\endinput 