\chapter{The Simplex Algorithm}\label{C:Simplex_Algorithm}
\section{The Simplex Algorithm}\label{S:Simplex}\index{simplex algorithm}
\setcounter{progress_ck_counter}{0}

\noi Considered to be the classical approach for solving LPs, the simplex algorithm was developed in 1947 by George Dantzig\index{Dantzig, G.}, who used it to solve "programming" problems for the Air Force. Such logistics problems addressed a variety of issues including, for example, the scheduling
of troop deployments and the delivery of supplies.

\subsection{An Overview of the Algorithm}

\noi We begin by revisiting the standard form of the \LP LP:

\begin{align}\label{E:simplex_FuelPro_standard_form}
 \mbox{maximize } z &=4x_1+3x_2  \\
	\mbox{  subject to} \notag \\
   x_1 \phantom{+ 2x_2} + s_1 \ph \ph &= 8  \notag \\
    2x_1 + 2x_2 \ph +s_2 \ph &= 28  \notag \\
    3x_1 + 2x_2 \ph \ph +s_3 &= 32  \notag \\
	x_1,x_2, s_1, s_2, s_3  &\geq 0.  \notag
	\end{align}

\newpar
We will rewrite the LP as an ``augmented matrix,'' so to speak. That is, we will write the system
of equations given by the constraints as an augmented matrix, and we will add a top row that records
the value of our objective function. The result is shown in Table \ref{Ta:petroleum_initial_tableau}.


\begin{table}[h]

\caption{Initial tableau for \LP Petroleum problem}\label{Ta:petroleum_initial_tableau}
\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 & 8 \\ \hline
0 &  2 & 2 & 0 & 1 & 0 & 28 \\ \hline
0 &  3 & 2 & 0 & 0 & 1 & 32 \\
\hline
\end{tabular}
%\caption{Initial tableau for \LP Petroleum problem.}\label{Ta:petroleum_initial_tableau}
\end{table}
\noi Sometimes Table \ref{Ta:petroleum_initial_tableau}\index{simplex tableau|see{simplex algorithm!tableau}} is referred to as the ``simplex tableau.''

\newpar
In a nutshell, the simplex algorithm works as follows:\index{simplex algorithm!overview}
	\be
	\item We begin by finding an initial basic feasible solution (BFS). For many of the initial
	problems we shall encounter, this task is readily
	accomplished by setting all decision variables equal to zero.
	\item We use the top row of the tableau to determine which nonbasic variable should then
	become positive in order to increase the objective function most rapidly. Because this variable
	will switch from nonbasic to basic, we call it the \emph{entering variable}.\index{entering variable|see{simplex algorithm!entering variable}}
	\item We then find the basic variable that swaps places with the entering
	variable and becomes nonbasic.
	\item Once we determine which variables trade roles, we perform elementary row operations, whose purpose
    is to yield a new tableau containing updated values for all variables, as well as the objective
    function.
	\item We repeat the previous steps until the objective function can no longer be increased. The basic
	feasible solution at that stage is the optimal solution.
	\ee

\subsection{A Step-By-Step Analysis of the Process}	

\noi We now break down the algorithm into greater detail by using it to solve the LP
\ref{E:simplex_FuelPro_standard_form}.
	\be
	\item We start by finding an initial BFS. In the \LP example, this is easily
	accomplished by setting $x_1=x_2=0$, in which case the slack variables are given by $s_1=8$, $s_2=28$, and
	$s_3=32$. This BFS corresponds to the origin in
	the feasible region. We have $\ds \BV=\left\{s_1,s_2,s_3 \right\}$ and
	$\ds \NBV=\left\{x_1,x_2 \right\}$. (Note, we do not
	consider $z$ as being either BV or NBV in this process.) Later, we will discuss how to handle situations
	when the origin does not correspond to a BFS.
	\item Our objective function is given by $z=f(x_1,x_2)=4x_1+3x_2$. We see that increasing the nonbasic
	variable $x_1$ by a
	set amount will increase $z$ more than will increasing the other nonbasic variable
	$x_2$ by the same amount.
	We thus choose $x_1$ as the entering variable and focus on its corresponding column.
	Note that in general, selecting the entering variable
	in a maximization problem comes down to determining the nonbasic variable whose coefficient
    in the top row is  {\underbar{most negative}}.
	\item We now determine the extent to which $x_1$ may increase by focusing on the constraint
	equation corresponding to each row. Each such equation involves $x_1$ and a basic variable. We have the following
	three equations:
		\begin{align*}
		x_1 + s_1 &= 8 \\
		2x_1 + s_2 &= 28 \\
		3x_1 +s_3 &= 32.
		\end{align*}
	Currently, $s_1=8$, $s_2=28$, and
	$s_3=32$. Since, the values of these variables must remain nonnegative, $x_1$ can only increase by so much before at least one of these values becomes zero. In general, each equation allows $x_1$ to increase
	up to a value of
    \begin{equation*}
     \mbox{(RHS in Equation)/(Coeff of $x_1$ in Equation)}.
     \end{equation*}
    In this case, the three
	equations permit $x_1$ to increase up to values of 8, 14, and $\ds \frac{32}{3}$, respectively. Since 8 is the smallest of these three values, $x_1$ will replace $s_1$ as a basic variable. We sometimes call this process
	of computing ratios to determine which variable becomes nonbasic, performing the \emph{ratio test}.\index{ratio test|see{simplex algorithm!ratio test}}
	\item We now pivot on the entry in the column corresponding to $x_1$ and the row corresponding
to $s_1$. This entry is highlighted in Table \ref {Ta:petroleum_initial_tableau}. The purpose of this pivot is to update values of all variables and the objective function when $x_1$ and $s_1$ switch roles. The result is
the new tableau in Table \ref{Ta:petroleum_second_tableau}.
	
\begin{table}[h]
\caption{Tableau after first iteration}\label{Ta:petroleum_second_tableau}
\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 & 2 & -2 & 1 & 0 & 12 \\ \hline
0 &  0 & \fbox{2} & -3 & 0 & 1 & 8 \\
\hline
\end{tabular}
\end{table}

\newpar
We have now completed one iteration of the simplex algorithm. The new BFS corresponds to the
extreme point at $(8,0)$. At this stage, \newline
$\BV=\left\{x_1=8,s_2=12,s_3=8\right\}$,
$\NBV=\left\{x_2,s_1 \right\}$, and
$z=32$.

\item We now repeat this process. The only negative nonbasic variable coefficient in the top row of Table \ref{Ta:petroleum_second_tableau}
corresponds to $x_2$, so $x_2$ becomes the entering variable. Since
$x_1$ is now basic, the constraints are given by
		\begin{align*}
		x_1 + 0x_2 &= 8 \\
		2x_2 + s_2 &= 12 \\
		2x_2 +s_3 &= 8.
		\end{align*}
We again apply the ratio test.
Note that the first equation places no restriction on the growth of $x_2$.
The remaining two equations
limit the increase in $x_2$ to 6 and 4, respectively. We thus focus on the third equation,
which tells us that $x_2$ replaces $s_3$ as a basic variable, and we pivot
on the entry highlighted in Table \ref{Ta:petroleum_second_tableau}. The new tableau is given in Table
\ref{Ta:petroleum_third_tableau}.

\begin{table}[h]
\caption{Tableau after second iteration}\label{Ta:petroleum_third_tableau}
\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 & $-\frac{1}{2}$ & 0 & $\frac{3}{2}$ & 44 \\ \hline
0 &  1 & 0 & 1 & 0 & 0 & 8 \\ \hline
0 &  0 & 0 & \fbox{1} & 1 & -1 & 4 \\ \hline
0 &  0 & 1 & $-\frac{3}{2}$ & 0 & $\frac{1}{2}$ & 4 \\
\hline
\end{tabular}
\end{table}

The new BFS corresponds to the
extreme point at $\ds \left(8,4 \right)$. We have
$\ds \BV=\left\{x_1=8,x_2=4,s_2=4\right\}$, $\NBV=\left\{s_1,s_3 \right\}$ and
$\ds z=44$.

\item The process is repeated one last time. The variable $s_1$ becomes basic. The
corresponding ratios are given by 8, 4, and $\ds -\frac{8}{3}$. Since the negative
ratio corresponds to unlimited growth in $s_1$,  the value of 4 ``wins'' the ratio test. Thus
$s_1$ replaces
$s_2$ as a basic variable and we pivot on the highlighted entry in Table
\ref{Ta:petroleum_third_tableau}. The resulting tableau appears in Table \ref{Ta:petroleum_fourth_tableau}.

\begin{table}[h]
\caption{Tableau after third iteration}\label{Ta:petroleum_fourth_tableau}
\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 & $\frac{1}{2}$ & 1 & 46 \\ \hline
0 &  1 & 0 & 0 & -1 & 1 & 4 \\ \hline
0 &  0 & 0 & 1 & 1 & -1 & 4 \\ \hline
0 &  0 & 1 & 0 & $\frac{3}{2}$ & -1 & 10 \\ \hline
\end{tabular}
\end{table}
The new BFS corresponds to the
extreme point at $\ds \left(4,10 \right)$. We have
$\ds \BV=\left\{x_1=4,x_2=10,s_1=4\right\}$,
$\NBV=\left\{s_2,s_3 \right\}$ and
$\ds z=46$. Note that all coefficients in the top row of the
tableau are nonnegative, so we have obtained the optimal solution, and \LP maximizes
its profit if $x_1=4$, $x_2=10$, in which case $z=46$, i.e., a profit of \$4.60 per hour. These results agree with those obtained using Maple's \mf{LPSolve} command and graphical tools from Section \ref{S:LP_Graphical}.
\ee

\newpar
Here are points to keep in mind regarding this process.
\bi
\item Performing elementary row operations is a tedious task. Consequently, one's focus should be on global aspects of the algorithm
such as keeping track of the basic and nonbasic variables and understanding the rationale behind the ratio test. Doing so will prove beneficial during later discussions of special cases, duality, and sensitivity analysis. A Maple worksheet found at the end of this section can facilitate this process.

\item The preceding example was fairly straightforward. As such, it raises a variety of questions.
For example, ``What happens in the process if the LP is unbounded? What happens if the LP has alternative optimal solutions? What happens if the LP has equality constraints?'' We address all these questions in the next section.
\ei

\subsection{Solving Minimization Problems}\index{minimization LPs|see{simplex algorithm!minimization LPs}}

\noi The simplex algorithm is easily modified to solve
minimization problems in which $\vecx=\zerovec$ corresponds to a basic feasible solution.
Suppose, for example, that we consider the following minimization LP from Section \ref{S:LP_BFS}:

\begin{align}\label{E:simplex_minimization_LP}
\mbox{minimize } 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}
	
There are two different approaches to solving (\ref{E:simplex_minimization_LP}):
	\be
	\item Rephrase the problem as a maximization problem. That is, keep each constraint
	above as is, but replace the objective with
		\[ \mbox{maximize } \tilde{z}=-\left(-5x_1+2x_2 \right)=5x_1-2x_2.\]
	Now solve the LP using the algorithm exactly as before.
	\item Maintain the objective goal of minimizing $z$ and modify the simplex algorithm slightly
	as follows.
	At each stage, instead of choosing the entering variable on the basis of the most negative
	coefficient in the top row of the tableau, select the entering variable on the basis
	of the {\underbar{most positive}} coefficient. (Think about why this works!) Then terminate
    the algorithm when entries in the top row of the tableau corresponding to nonbasic variables are all
nonpositive.
	\ee
Either of these methods works; our convention will be to use the latter. For example, let us use this approach to solve LP (\ref{E:simplex_minimization_LP}). The initial tableau is given in Table \ref{Ta:LP_BFS_minimization_LP_initial}, in which
case $\ds \BV=\left\{s_1=2,s_2=6,s_3=12\right\}$, and
$\NBV=\left\{x_1,x_2 \right\}$.

\begin{table}[h]
\caption{Initial tableau for minimization LP (\ref{E:simplex_minimization_LP})} \label{Ta:LP_BFS_minimization_LP_initial}
\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}	

\newpar
Since 5 is the most positive nonbasic variable coefficient in the top row, $x_1$ is the entering
variable. The third constraint row yields the smallest ratio of $\ds \frac{3}{2}$, so $s_3$ becomes nonbasic and is
replaced by $x_1$. The new tableau is shown in Table \ref{Ta:LP_BFS_minimization_LP_second}.

\begin{table}[h]
\caption{Tableau after first iteration for minimization LP (\ref{E:simplex_minimization_LP})
}\label{Ta:LP_BFS_minimization_LP_second}
\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 & $-\frac{31}{8}$ & 0 & 0 & $-\frac{5}{8}$ & $-\frac{15}{2}$ \\ \hline
0 &  0 & $-\frac{3}{8}$ & 1 & 0 & $-\frac{1}{8}$ & $\frac{1}{2}$ \\ \hline
0 &  0 & $\frac{7}{8}$ & 0 & 1 & $-\frac{3}{8}$ & $\frac{3}{2}$ \\ \hline
0 &  1 & $\frac{3}{8}$ & 0 & 0 & $\frac{1}{8}$ & $\frac{3}{2}$ \\ \hline
\end{tabular}
\end{table}	

\newpar The new BFS corresponds to the
extreme point at $\ds \left(\frac{3}{2},0 \right)$, where
$\ds \BV=\left\{x_1=\frac{3}{2},s_1=\frac{1}{2},s_2=\frac{3}{2}\right\}$,
$\NBV=\left\{x_2,s_3 \right\}$ and
$\ds z=-\frac{15}{2}$. Since all nonbasic variable coefficients in the top row of the
tableau are {\underbar{nonpositive}}, this solution is optimal.

\begin{progress_ck} Now solve the minimization LP (\ref{E:simplex_minimization_LP}) by
converting it to a maximization problem.
\end{progress_ck}

\subsection{A Step-by-Step Maple Implementation of the \mbox{Simplex} \mbox{Algorithm}}\label{SS:Maple_Implementation_Simplex}\index{simplex algorithm!Maple implementation}

\noi
What follows is a worksheet, entitled \textbf{Simplex Algorithm.mw},
 which facilitates using the simplex
algorithm to solve an LP stated in matrix inequality form as
\begin{align}
 \mbox{maximize } z &=\vecc \cdot \vecx  \label{E:Simplex_LP_matrix_form}  \\
	\mbox{ subject to} \notag\\
	A \vecx &\leq \vecb \notag \\
	\vecx &\geq \zerovec. \notag
	\end{align}
\noi
In this case, the worksheet is implemented to solve the \LP LP. The user enters the quantities $\vecc$, $A$, and $\vecb$, as well as the
number of constraints and number of decision variables. (The \mf{Vector} command is used to enter $\vecc$ as a row vector.) A
\mf{for-do} loop structure then
creates arrays of decision variables and slack variables
of appropriate respective sizes. These quantities are used to create a matrix
 labeled \mf{LPMatrix}. Note that the task of keeping track of basic versus nonbasic variables is still left to the user.

\newpar
Three Maple \emph{procedures}
are then created to facilitate implementation of the simplex algorithm. A procedure
is a small ``program'' within a worksheet that accepts certain arguments and performs specified
tasks. The first procedure, \mf{Tableau}, merely prints the tableau matrix with a top row of
variable labels. The second procedure,  \mf{RowRatios(\emph{M,c})} performs the ratio test
on a matrix \mf{\emph{M}} using column number \mf{\emph{c}}, where column 0 corresponds
to the \underbar{leftmost} column of the tableau. Once this procedure determines the
ratio test results, the third procedure,
\mf{Iterate(\emph{M,c,r})}, pivots on the entry (\mf{\emph{c},\emph{r}}) of the matrix \mf{\emph{M}}, where column 0 corresponds to the leftmost column and row 0 to the \underbar{top} row of the tableau, not
including the variable labels. The term \mf{local} within each procedure refers to one or more variables that are used locally to the procedure only and whose values are not accessible outside of the procedure.

\begin{maplelist}
\item \mf{restart;with(LinearAlgebra):}
\item \mf{c:=Vector[row]([4,3]); \newline \# Create row vector with objective coefficients.}
\mo{c:=[4,3]}
\item \mf{A:=Matrix(3,2,[1,0,2,2,3,2]); \newline \# Matrix of constraint coefficients.}
\mo{A:=\begin{bmatrix} 1 & 0 \\ 2 & 2 \\ 3 & 2 \end{bmatrix}}
\item \mf{b:=<8,28,32>; \newline \# Constraint bounds.}
\mo{b:=\begin{bmatrix} 8 \\ 28 \\ 32 \end{bmatrix} }
\item \mf{n:=2:m:=3: \newline \# Enter the number of decision variables and constraints,
\newline   respectively.}
\item \mf{x:=array(1..n):s:=array(1..m): \newline \# Create arrays of decision and slack variables.}
\item \mf{Labels:=
\newline Matrix(1,2+n+m,[z,seq(x[i],i=1..n),seq(s[j],j=1..m),RHS]):
\newline \# Create a top row of variable labels for the tableau}
\item \mf{LPMatrix:=
\newline <UnitVector(1,m+1)\vb <-c,A> \vb <ZeroVector[row](m),
IdentityMatrix(m)> \vb <0,b>>; \newline \# Create matrix corresponding to the tableau.}
\mo{LPMatrix:=\begin{bmatrix}
1 & -4 & -3 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 & 8 \\
0 & 2 & 2 & 0 & 1 & 0 & 28 \\
0 & 3 & 2 & 0 & 0 & 1 & 32
\end{bmatrix}}

\item \mf{Tableau:=proc(M);return(<labels,M>):end: \newline \# Procedure for printing tableau with labels.}
\item \mf{RowRatios:=proc(M,c) local k:
\newline for k from 2 to nops(convert(Column(M,c+1),list)) do
\newline if M[k,c+1]=0 then print(cat(``Row '', convert(k-1,string), `` Undefined''))
\newline else print(cat(``Row '',convert(k-1,string), ``Ratio = '', \newline convert(evalf(M[k,nops(convert(Row(M,k),list))]/M[k,c+1]),
\newline string))) end if; end do;end:
\newline \#The ratio test procedure applied to column c of M.}
\item \mf{Iterate:=proc(M,r,c) RowOperation(M,r+1,(M[r+1,c+1])\^{}(-1),
\newline inplace=true): Pivot(M,r+1,c+1,inplace=true):return(Tableau(M)):end:
\newline \# Iteration of the simplex algorithm applied to row r, 
\newline column c}
\item \mf{Tableau(LPMatrix); \newline \# Display initial tableau.}
\mo{ \begin{bmatrix}
z & x_1 & x_2 & s_1 & s_2 & s_3 & RHS \\
1 & -4 & -3 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 & 8 \\
0 & 2 & 2 & 0 & 1 & 0 & 28 \\
0 & 3 & 2 & 0 & 0 & 1 & 32
\end{bmatrix}}
\item \mf{RowRatios(LPMatrix,1);  \newline \# Determine ratios corresponding to column 1.}
\mo{
\mbox{``Row 1 Ratio = 8.''}}
\mo{
\mbox{``Row 2 Ratio = 14.''}}
\mo{
\mbox{``Row 3 Ratio = 10.66666667.''}}
\item \mf{Iterate(LPMatrix,1,1); \newline \# Pivot on entry in row 1, column 1 of matrix.}

\mo{ \begin{bmatrix}
z & x_1 & x_2 & s_1 & s_2 & s_3 & RHS \\
1 & 0 & -3 & 4 & 0 & 0 & 32 \\
0 & 1 & 0 & 1 & 0 & 0 & 8 \\
0 & 0 & 2 & -2 & 1 & 0 & 12 \\
0 & 0 & 2 & -3 & 0 & 1 & 8
\end{bmatrix}}

\item \mf{RowRatios(LPMatrix,2);  \newline \# Determine ratios corresponding to column 2.}
\mo{
\mbox{``Row 1 Ratio Undefined.''}}
\mo{
\mbox{``Row 2 Ratio = 6.''}}
\mo{\mbox{
``Row 3 Ratio = 4.''}}

\item \mf{Iterate(LPMatrix,3,2); \newline \# Pivot on entry in row 3, column 2 of matrix.}

\mo{ \begin{bmatrix}
z & x_1 & x_2 & s_1 & s_2 & s_3 & RHS \\
1 & 0 & 0 & -\frac{1}{2} & 0 & \frac{3}{2} & 44 \\
0 & 1 & 0 & 1 & 0 & 0 & 8 \\
0 & 0 & 0 & 1 & 1 & -1 & 4 \\
0 & 0 & 1 & -\frac{3}{2} & 0 & \frac{1}{2} & 4
\end{bmatrix}}

\item \mf{RowRatios(LPMatrix,3);  \newline \# Determine ratios corresponding to column 3.}
\mo{
\mbox{``Row 1 Ratio =8.''}}
\mo{
\mbox{``Row 2 Ratio = 4.''}}
\mo{
\mbox{``Row 3 Ratio = -2.666666667.''}}

\item \mf{Iterate(LPMatrix,2,3); \newline \# Pivot on entry in row 2, column 3 of matrix to obtain final tableau.}

\mo{ \begin{bmatrix}
z & x_1 & x_2 & s_1 & s_2 & s_3 & RHS \\
1 & 0 & 0 & 0 & \frac{1}{2} & 1 & 46 \\
0 & 1 & 0 & 0 & -1 & 1 & 4 \\
0 & 0 & 0 & 1 & 1 & -1 & 4 \\
0 & 0 & 1 & 0 & \frac{3}{2} & -1 & 10
\end{bmatrix}}

\end{maplelist}


\section*{Exercises Section \protect\ref{S:Simplex}}
\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_Simplex}
	
\endinput
