\section{The Revised Simplex Algorithm}\label{S:Revised_Simplex}\index{revised simplex algorithm|see{{simplex algorithm!revised version}}}
\setcounter{progress_ck_counter}{0}

\noi When executed by hand, the simplex algorithm requires writing numerous
tableaus, many of whose values
remain unchanged from one iteration to the next. The purpose of this
section is to address this shortcoming of the algorithm.

\subsection{Notation}\label{S:Int_Prog_relaxation}

\noi Throughout this section we shall again refer to the standard maximization problem
\begin{align*}
 \mbox{maximize } z &=\vecc \cdot \vecx  \\
	\mbox{ subject to} \notag\\
	A \vecx &\leq \vecb \notag \\
	\vecx &\geq \zerovec, \notag
	\end{align*}
where $A$ is an $m$-by-$n$ matrix, $\vecc$ and $\vecx$ belong to $\R^n$, and $\vecb$ belongs to $\R^m$.
We will assume that all entries of $\vecb$ are positive.
The revised simplex algorithm builds upon the result of
Theorem \ref{Th:Paritioned_Matrix_View_Simplex}
from Section \ref{S:Partitioned_Matrix_View_Simplex}. Namely,
the tableau matrix after the $k$th iteration,
in partitioned matrix multiplication form, is given by
\begin{equation}\label{E:Revised_fundamental_insight}
\begin{bmatrix} 1 & \vecy \\  \zerovec & M \end{bmatrix}
\cdot \begin{bmatrix}
1 & -\vecc & \zerovec & 0 \\
\zerovec & A & I_m & \vecb
\end{bmatrix} =
\begin{bmatrix}
1 & -\vecc +\vecy A & \vecy & \vecy \vecb \\
\zerovec & M A & M & M\vecb
\end{bmatrix},
\end{equation}
where $\vecy$ is a row vector in $\R^m$ and $M$ is an $m$-by-$m$ matrix.
The vector $\vecy$ and matrix $M$ record all row operations used to obtain the $k$th tableau matrix. To underscore the fact that these quantities correspond to the $k$th iteration, we modify our notation and
relabel $\vecy$ and $M$ from Theorem \ref{Th:Paritioned_Matrix_View_Simplex} and
(\ref{E:Revised_fundamental_insight})
as $\vecy_k$ and $M_k$, respectively. We also
define the $(m+1)$-by-$(m+1)$ matrix
\begin{equation}\label{E:Revised_Simplex_Sk}
 S_k = \begin{bmatrix} 1 & \vecy_k \\  \zerovec & M_k \end{bmatrix} \qquad k=0,1,2,\ldots
\end{equation}
With this notation, the tableau matrix after the $k$th iteration is the product of $S_k$ and the initial
tableau matrix:
\begin{equation}\label{E:Revised_Simplex_Sk_Product}
S_k \cdot \begin{bmatrix}
1 & -\vecc & \zerovec & 0 \\
\zerovec & A & I_m & \vecb
\end{bmatrix}.
\end{equation}
\noi
Note that when $k=0$, $\ds \vecy_0 = \zerovec_{1 \times m}$, in which case $\ds S_0=I_{m+1}$, the $(m+1)$-by-$(m+1)$ identity matrix. Hence, when $k=0$,
(\ref{E:Revised_Simplex_Sk_Product}) is merely the original tableau matrix.

\subsection{Observations about the Simplex Algorithm}\label{S:Revised_SimplexObservations}

\noi The route to the revised algorithm begins with the following observations.
	\be
	\item After the $k$th iteration of the simplex algorithm, we identify the entering nonbasic variable by focusing on
	the nonbasic variable coefficients in the top row of the tableau. One means
    of identifying the nonbasic variable whose coefficient is most negative is to
    multiply the matrix $S_k$ by each column vector of the initial tableau matrix that corresponds to
    a nonbasic variable.  However, only the first entry in each matrix-vector product is needed to identity
    the entering nonbasic variable.
	\item The entering nonbasic variable and the basic variable it replaces
 determine a pivot entry in the column corresponding to the entering variable. The other entries in this column vector alone dictate the elementary operations
	required to update the tableau. Furthermore, in columns of the tableau corresponding to variables
that remain basic, all entries below row 0 remain unchanged after the iteration is complete.
    \item The tableau matrix after the $(k+1)^{\mbox{st}}$ iteration is obtained by applying to
    (\ref{E:Revised_Simplex_Sk_Product}) the previously described row operations. The matrix
    $S_{k+1}$ is therefore the result of applying these row operations to $S_k$.
	\ee

\newpar	
In the subsequent discussions, we will use the following notation. We let $\bv_k$, where
$0 \leq k \leq m$, be an
$m+1$ by 1 column vector of
``labels,'' whose top entry is $z$ and whose $j$th entry is the basic variable associated with row $j$ of the tableau
after the $k$th iteration.
For example, in the \LP LP, $\ds \bv_1=\begin{bmatrix} z \\ x_1 \\ s_2 \\ s_3 \end{bmatrix}$ since
the basic variables after the first iteration are given by $x_1$ (row 1), $s_2$ (row 2), and
$s_3$ (row 3).

\subsection{An Outline of the Method}\label{S:Revised_MethodOutline}

\noi Using this notation, our algorithm can be outlined in the following steps.
	\be
	\item At the start, $\bv_0$ is made up of the initial basic variables in the order corresponding to their
	rows (the slack variables in our discussion), and $S_0=I_{m+1}$.
	\item At the $k$th stage, we first compute
	$\ds S_k \begin{bmatrix} 0 \\ \vecb \end{bmatrix} $ and then
 multiply $S_k$ times the column vector corresponding to each
	nonbasic variable in the initial tableau matrix. After computing only the top entry in each matrix-vector product, we can identify the entering variable, if one exists, as the one corresponding to the most negative top entry. (If all such top entries are nonnegative, then the algorithm terminates and the final tableau matrix is given by
(\ref{E:Revised_Simplex_Sk_Product}).) We then compute the remaining
	entries in the vector corresponding to only the entering variable. Call this vector $\vecv$.
	\item We apply the ratio test, just as in the usual simplex algorithm,
	using entries in $\ds S_k \begin{bmatrix} 0 \\ \vecb \end{bmatrix} $ and the vector $\vecv$ computed in
	the previous step. (We ignore, however, the ratio in the top entry, which corresponds
	to row 0 of the tableau matrix.) The result identifies the pivot entry in $\vecv$. Knowing
	the pivot entry in $\vecv$, we have identified the variable that will become nonbasic.
	This allows us to compute
	$\bv_{k+1}$.
	\item Because $\vecv$ corresponds to the column of the entering basic variable, we must pivot on the entry identified in the previous step. The entries of $\vecv$ alone dictate the row operations
	required to carry out this process. These row operations are performed on $S_k$ to create
	$S_{k+1}$.
	\item We now return to step (2).
	\ee

\subsection{Application to the \LP LP}\label{S:Revised_FuelproApplication}

\noi To illustrate an application of this algorithm, we return to the \LP LP.

\begin{table}[h]
\caption{Initial tableau for \LP Petroleum problem}\label{Ta:Revised_LinPro_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 & -4 & -3 & 0 & 0 & 0 & 0 \\ \hline
0 &  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}
\end{table}

\noi
Recall that our convention is to number the top row of the tableau
matrix, excluding labels, as row 0 and the leftmost column as column 0.

\be
\item Initially,
	$\ds \bv_0= \begin{bmatrix} z \\ s_1 \\ s_2 \\ s_3 \end{bmatrix}$ and $\ds S_0=I_4$.
\item We have that
		\begin{equation}\label{E:Revised_step1_1}
	\bv_0=S_0 \begin{bmatrix} 0 \\ \vecb \end{bmatrix}
		= \begin{bmatrix} 0 \\ 8 \\ 28 \\ 32  \end{bmatrix}.
	\end{equation}
Since the nonbasic variables are $x_1$ and $x_2$, we compute the top entries in the matrix-vector products of $S_0$ and the corresponding initial tableau matrix column vectors:
	\[ S_0 \begin{bmatrix} -4 \\ 1 \\ 2 \\ 3 \end{bmatrix} = \begin{bmatrix} -4 \\ \bs \\ \bs \\ \bs \end{bmatrix}
\quad \mbox{and} \quad
		S_0 \begin{bmatrix} -3 \\ 0 \\ 2 \\ 2 \end{bmatrix}=\begin{bmatrix} -3 \\ \bs \\ \bs \\ \bs \end{bmatrix},\]
so that $x_1$ is the entering variable and
	\begin{equation}\label{E:Revised_step1_2}
	\vecv=S_0 \begin{bmatrix} -4 \\ 1 \\ 2 \\ 3 \end{bmatrix}=\begin{bmatrix} -4 \\ 1 \\ 2 \\ 3 \end{bmatrix}.
	\end{equation}
\item Using the results of (\ref{E:Revised_step1_1}) and (\ref{E:Revised_step1_2}), we compute the respective
ratios as 8, 14, and $\frac{32}{3}$. The result tells us that $x_1$ replaces $s_1$ in the second entry (i.e.,
row 1 entry) of $\ds \bv_0$ so that $\ds \bv_1= \begin{bmatrix} z \\ x_1 \\ s_2 \\ s_3 \end{bmatrix}$.

\item
We now pivot on the second entry of
$\vecv = \ds \begin{bmatrix} -4 \\ 1 \\ 2 \\ 3 \end{bmatrix}$. This process requires
the following
three elementary row operations:
	\be
	\item Add 4 times row 1 to row 0;
	\item Add -2 times row 1 to row 2;
	\item Add -3 times row 1 to row 3.
	\ee
To compute $S_1$, we perform on $S_0=I_4$ these elementary row operations, in the order they are listed.
The result is as follows:
	\[ S_1 = \begin{bmatrix} 1 & 4 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & -2 & 1 & 0 \\ 0 & -3 & 0 & 1 \end{bmatrix}.\]

This completes the first iteration of the revised method.

\item We begin the second iteration by computing
$\ds S_1 \begin{bmatrix} 0 \\ \vecb \end{bmatrix} $. One means of performing this task is of course to
carry out the matrix-vector multiplication. Another way is to perform on $S_0 \vecb$, the same elementary
row operations that derived $S_1$ from $S_0$. Either approach leads to
\begin{equation}\label{E:Revised_step2_1}
	S_1 \begin{bmatrix} 0 \\ \vecb \end{bmatrix}
= \begin{bmatrix} 32 \\ 8 \\ 12 \\ 8  \end{bmatrix}.
	\end{equation}
The nonbasic variables are $x_2$ and $s_1$. Thus we compute only the top entries in the matrix-vector products of $S_0$ and the corresponding initial tableau matrix column vectors:
	\[ S_1 \begin{bmatrix} -3 \\ 0 \\ 2 \\ 2 \end{bmatrix} = \begin{bmatrix} -3 \\ \bs \\ \bs \\ \bs \end{bmatrix}
\quad \mbox{and} \quad
		S_1 \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix}=\begin{bmatrix} 4 \\ \bs \\ \bs \\ \bs \end{bmatrix},\]
so that $x_2$ is the entering variable and
	\begin{equation}\label{E:Revised_step2_2}
	\vecv=S_1 \begin{bmatrix} -3 \\ 0 \\ 2 \\ 2 \end{bmatrix}=\begin{bmatrix} -3 \\ 0 \\ 2 \\ 2 \end{bmatrix}.
	\end{equation}
\item The results of (\ref{E:Revised_step2_1}), (\ref{E:Revised_step2_2}), and
the ratio test tell us to pivot on the fourth entry (i.e., on the row 3 entry) in the result from
(\ref{E:Revised_step2_2}). Thus $x_2$ replaces $s_3$ as a basic variable and
	\[\bv_2= \begin{bmatrix} z \\ x_1 \\ s_2 \\ x_2 \end{bmatrix}.\]
\item The required row operations to pivot on the row 3 entry of (\ref{E:Revised_step2_2})
are as follows:
	\be
	\item Add the negative of row 3 to row 2.
	\item Add $\frac{3}{2}$ of row 3 to row 0.
	\item Scale row 3 by $\frac{1}{2}$.
	\ee
These row operations, when applied to $S_1$, yield
\[ S_2 = \begin{bmatrix} 1 & -\frac{1}{2} & 0 & \frac{3}{2} \\
0 & 1 & 0 & 0 \\
0 & 1 & 1 & -1 \\
0 & -\frac{3}{2} & 0 & \frac{1}{2} \end{bmatrix},\]

thereby completing the second iteration.
\ee

\newpar
An important observation to make regarding this new notation is that the matrix $S_k$ is a submatrix
of the tableau matrix obtained after the $k$th iteration. It is formed using columns of
the tableau matrix corresponding to the slack variables, augmented on the left with the column vector,
$\ds \begin{bmatrix} 1 \\ 0 \\ 0 \\0 \end{bmatrix}$. Indeed, the matrices $S_1$ and $S_2$ can easily be identified as submatrices
of Tables \ref{Ta:petroleum_second_tableau} and \ref{Ta:petroleum_third_tableau}, respectively,
from Section \ref{S:Simplex}.

\begin{progress_ck}
Execute a third iteration of the revised simplex algorithm for the \LP LP. Your results
should indicate that $\ds \bv_3 = \begin{bmatrix} z \\ x_1 \\ s_1 \\ x_2 \end{bmatrix}$
and $\ds S_3 \vecb = \begin{bmatrix} 46 \\ 4 \\ 4 \\ 10 \end{bmatrix}$. Begin to carry out a fourth
iteration. You should discover that when $S_3$ is multiplied by either column vector of the tableau matrix
corresponding to a nonbasic variable, the top entry of the vector is positive. Hence
 the algorithm terminates with $\bv_3 = S_3 \vecb$ so that $z=46$, $x_1=4$, $s_1=4$
 and $x_2=10$.
\end{progress_ck}

\newpar
In practice, the revised simplex algorithm has a significant advantage over the
original algorithm in that it requires less memory storage, specifically that needed
to record the large number of zeros and
ones in columns corresponding to basic variables.

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

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_Revised_Simplex}		
\endinput
	
	