\section{The Dual Simplex Method}
\label{S:Dual_Simplex}
\setcounter{progress_ck_counter}{0}

\noi Theorem \ref{Th:Paritioned_Matrix_View_Simplex} dictates that
when we use the simplex algorithm to solve the standard maximization problem,
(\ref{E:Duality_primal}), the tableau matrix at each iteration takes the general
form
\begin{equation}\label{E:Dual_Simplex_tableau_matrix}
\begin{bmatrix}
1 & -\vecc +\vecy A & \vecy & \vecy \vecb \\
\zerovec & MA & M & M\vecb
\end{bmatrix}.
\end{equation}

\newpar
At each iteration, the primal LP has a basic feasible solution, whose values are
recorded by the entries of $M\vecb$. Unless the LP is degenerate, all such values are
positive. During this process but prior to the
termination of the algorithm, at least one entry of
$\vecy$ or $-\vecc+\vecy A$ is negative, implying $\vecy$ is not dual-feasible.
At the completion of the algorithm, both $\ds \vecy A \geq \vecc$ and
$\vecy \geq \zerovec$, whereby we simultaneously obtain
optimal solutions to both the primal LP and its dual.

\newpar
Unfortunately, if $\vecb$ has one or more negative entries, then so too can
$M\vecb$. In this case the primal has a solution that is basic, but not basic feasible.
The \emph{dual simplex method}\index{dual simplex method}, which uses the
same tableau as the original method, is well suited for addressing such a situation. At each stage
of the algorithm, all entries of $\vecy$ and $-\vecc+\vecy A$ are nonnegative, implying $\vecy$ is
dual-feasible. At the same time, at least one entry of the rightmost tableau column, $M\vecb$, is negative, so that the
basic variable values for the primal at that stage constitute merely a basic, but not basic feasible,
solution. The goal of the algorithm then becomes one of making all entries of $M\vecb$ nonnegative. For when we achieve this outcome, we obtain a basic feasible solution of the primal, whose values are recorded by $M\vecb$, along with a basic feasible solution, $\vecy$, of the dual. Since their objective values are both recorded by $\vecy \vecb$, both solutions are optimal, and our tableau is identical to that obtained using the regular simplex algorithm.


\subsection{Overview of the Method}\label{S:Dual_Simplex_Method_Overview}

\noi Here is a brief outline of the algorithm.
	\be
	\item We start with a standard maximization problem (\ref{E:Duality_primal})
	whose initial tableau matrix is given by
    \begin{equation}\label{E:Dual_Simplex_Algorithm_StartingMatrix}
    \begin{bmatrix}
    1 & -\vecc  & \zerovec & 0 \\
    \zerovec & A & I_m & \vecb
    \end{bmatrix}.
    \end{equation}
    \item The process begins by finding an initial basic feasible solution, $\vecy$, of the dual LP.
    In other words, we need to find $\vecy \geq \zerovec$ that satisfies $\vecy A \geq \vecc$. In general, finding $\vecy$ can prove difficult. However, one situation in which it is always easy to do so
    occurs when $\vecc \leq \zerovec$. For in this situation, $\vecy = \zerovec$ is automatically
    dual-feasible since $\vecy A \geq \vecc$. It is for this reason that the dual simplex is well suited for an LP whose goal is to maximize an objective function whose decision variable coefficients are nonpositive, or, equivalently, to minimize an objective function whose decision variable coefficients are all nonnegative.	
	\item Unlike the usual simplex algorithm, where we first decide which nonbasic variable is to become
	basic, i.e., we determined the ``entering variable,'' in the dual simplex algorithm, our first step is to decide which negative
	basic variable is to become nonbasic, i.e., we determine the ``departing basic variable.''
	At the first iteration of the new algorithm, this is accomplished by determining the most negative entry of $\vecb$.
	\item We perform the ratio test in a manner analogous to the usual simplex algorithm in order to determine
	which nonbasic variable replaces the departing variable in the set of basic variables. The tableau is
	updated. The process is repeated until all values on the right-hand side of the tableau are nonnegative. That
	is, the process terminates when we obtain a basic feasible solution to the primal LP.
	\ee
	
\subsection{A Simple Example}\label{S:Dual_Simplex_SimpleExample}

\noi To illustrate all details of the algorithm, we consider the following two-variable minimization problem:
\begin{align}\label{E:dual_simplex_example}
 \mbox{minimize } w &=3x_1+2x_2 \\
	\mbox{  subject to} \notag \\
   2x_1+3x_2 &\geq 30  \notag \\
    -x_1 + 2x_2 &\leq 6 \notag \\
    x_1 + 3x_2 &\geq 20, \notag
	\end{align}
whose feasible region is shown in Figure \ref{Fi:Sensitivity_LPC}.

\begin{figure}[h]
\centering
\psfrag{x1axislabel}[Bc][Bc]{$x_1$}
\psfrag{x2axislabel}[Bc][Bc]{$x_2$}
\includegraphics[width=.7\linewidth]{images/f05x03x01.eps}
\caption{Feasible region for LP (\ref{E:dual_simplex_example}).}\label{Fi:Sensitivity_LPC}
\end{figure}

\newpar
If we change the objective to that of maximizing $z=-w=-3x_1-2x_2$, express all constraints in $\leq$ form, and introduce slack variables, $s_1$, $s_2$, and $s_3$,
we obtain the tableau shown in Table \ref{Ta:dual_simplex_initial_tableau}.
\begin{table}[h]
\caption{$\mbox{BV}=\left\{s_1,s_2,s_3 \right\} $ }
	\label{Ta:dual_simplex_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 & 3 & 2 & 0 & 0 & 0 & 0  \\
	0 & -2 & \fbox{-3} & 1 & 0 & 0 & -30  \\
	0 & -1 & 2 & 0 & 1 & 0 & 6  \\
    0 & -1 & -3 & 0 & 0 & 1 & -20  \\
	\hline
	\end{tabular}
	\end{table}

\newpar
Initially, we choose $s_1=-30$, $s_2=6$, and $s_3=-20$ as our basic variables. Together, with
$x_1=x_2=0$, they constitute a basic, but not basic feasible solution, of (\ref{E:dual_simplex_example}). In terms of Figure \ref{Fi:Sensitivity_LPC}, this initial
basic solution corresponds to the origin. In terms of the dual LP, $\vecy=[0,0,0]$, the slack variable coefficients in the top row of
Table \ref{Ta:dual_simplex_initial_tableau}, which is dual-feasible.

\newpar
The tableau shows that $s_1=-30$ is the most negative basic variable, so it becomes
the departing variable. Thus we focus on its corresponding row
and must decide which nonbasic variable, $x_1$ or $x_2$, replaces $s_1$.
The two equations,
$\ds -2x_1+s_1=-30$ and $\ds -3x_2+s_1=-30$, indicate that we may let $s_1$ increase to
zero by allowing either $x_1$ to increase to 15 or $x_2$ to increase to 10. The first of these choices
results in $z=-3\cdot15=-45$, the latter in $z=2\cdot10=-20$. Because our goal is to maximize $z$, we let $x_2$ replace $s_1$ as a basic variable and thus pivot on
the highlighted entry in Table \ref{Ta:dual_simplex_initial_tableau}. From this analysis, we conclude that the dual simplex ratio test\index{dual simplex method!ratio test} works as follows: Once we have determined a row corresponding to the departing basic variable, i.e., a pivot row, we determine the column of the entering basic variable as follows. For each negative entry in the pivot row, we compute the ratio of the corresponding entry in the top row (which is necessarily nonnegative by dual-feasibility) divided by the pivot row entry. The smallest of all such ratios, in absolute value, determines the pivot column.

\newpar
We thus pivot on the highlighted entry in Table
\ref{Ta:dual_simplex_initial_tableau}. The resulting tableau is given in Table \ref{Ta:dual_simplex_2}.
Observe that $x_1=0$ and $x_2=10$, which corresponds to another basic solution in Figure
\ref{Fi:Sensitivity_LPC}.


\begin{table}[h]
\caption{$\mbox{BV}=\left\{x_2,s_2,s_3 \right\} $ }
	\label{Ta:dual_simplex_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 & $\frac{5}{3}$ & 0 & $\frac{2}{3}$ & 0 & 0 & -20  \\
	0 & $\frac{2}{3}$ & 1 & $-\frac{1}{3}$ & 0 & 0 & 10  \\
	0 & $-\frac{7}{3}$ & 0 & $\frac{2}{3}$ & 1 & 0 & -14   \\
   0 & 1 & 0 & -1 & 0 & 1 & 10   \\
	\hline
	\end{tabular}
	\end{table}


\newpar
At this stage, $s_2$ is the only negative basic variable. By the ratio test applied to
the row corresponding to $s$, we see that $x_1$ replaces $s_2$ as a basic variable. The resulting pivot leads to the final tableau in Table \ref{E:dual_simplex_4}.

\begin{table}[h]
\caption{$\mbox{BV}=\left\{x_1,x_2,s_3 \right\} $ }
	\label{E:dual_simplex_4}
	\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{8}{7}$ & $\frac{5}{7}$ & 0 & -30  \\
	0 & 0 & 1 & $-\frac{1}{7}$ & $\frac{2}{7}$ & 0 & 6  \\
	0 & 1 & 0 & $-\frac{2}{7}$ & $-\frac{3}{7}$ & 0 & 6   \\
   0 & 0 & 0 & $-\frac{5}{7}$1 & $\frac{3}{7}$ & 1 & 4   \\
	\hline
	\end{tabular}
	\end{table}
	
\newpar
The dual simplex algorithm terminates at this stage because all entries in the right-hand side of the tableau, below the top row, are nonnegative. In other words, a basic feasible solution to the primal LP has been obtained. The primal solution is given by $\ds \left(x_1,x_2\right)=(6,6)$ with
$z=-30$, which corresponds to $w=30$ in the original LP (\ref{E:dual_simplex_example}).

\newpar
If we compare this method with the Big M Method for solving the LP, we see that it provides an elegant and efficient method that completely eliminates the need for introducing artificial variables.

\newpar
Another setting in which the dual simplex method proves extremely useful is in sensitivity analysis, specifically when one desires to know the effect of adding a constraint to an LP.\index{dual simplex method!used for sensitivity analysis} For example, suppose that \LP must add a third stock, call it stock C, to each fuel type in order to reduce emissions. Assume that production of each gallon of premium requires 5 gallons
of stock C and that production of each gallon of regular unleaded requires 6 gallons of stock C. Furthermore, at most 75 gallons of stock C are
available for production. It follows then that we must
add the constraint $5x_1+6x_2 \leq 75$ to the original \LP LP.
Instead of completely resolving a new LP, we may begin with
the final tableau for the original \LP LP, given by Table \ref{Ta:petroleum_fourth_tableau} from
Section \ref{S:Simplex}, and add a row and column, together with a slack variable $s_4$ corresponding to the new constraint. The result is shown in Table \ref{Ta:Other_Algorithms_LinPro_added_constraint}.

\begin{table}[h]
\caption{\LP tableau after addition of new constraint}\label{Ta:Other_Algorithms_LinPro_added_constraint}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & $s_4$ & RHS \\
\hline \hline
1 & 0 & 0 & 0 & $\frac{1}{2}$ & 1 & 0 & 46 \\ \hline
0 &  1 & 0 & 0 & -1 & 1 & 0 & 4 \\ \hline
0 &  0 & 0 & 1 & 1 & -1 & 0 &4 \\ \hline
0 &  0 & 1 & 0 & $\frac{3}{2}$ & -1 & 0 & 10 \\ \hline
0 &  5 & 6 & 0 & 0 & 0 & 1 & 75 \\ \hline
\end{tabular}
\end{table}

\newpar
To update the values of the basic variables $x_1$ and $x_2$ in the tableau, we must perform
two pivots. The resulting tableau is given in Table \ref{Ta:Other_Algorithms_LinPro_added_constraint2}.

\begin{table}[h]
\caption{Updated tableau after pivots are performed}
\label{Ta:Other_Algorithms_LinPro_added_constraint2}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & $s_4$ & RHS \\
\hline \hline
1 & 0 & 0 & 0 & $\frac{1}{2}$ & 1 & 0 & 46 \\ \hline
0 &  1 & 0 & 0 & -1 & 1 & 0 & 4 \\ \hline
0 &  0 & 0 & 1 & 1 & -1 & 0 &4 \\ \hline
0 &  0 & 1 & 0 & $\frac{3}{2}$ & -1 & 0 & 10 \\ \hline
0 &  0 & 0 & 0 & \fbox{-4} & 1 & 1 & -5 \\ \hline
\end{tabular}
\end{table}

\newpar
At this stage, $\ds \vecy= \begin{bmatrix} 0 & \frac{1}{2} & 1 & 0 \end{bmatrix}$
is dual-feasible so that we may apply the dual simplex algorithm directly.
Only one iteration is required, in which case we replace a negative
basic variable, $s_4$, with the nonbasic variable $s_2$. Pivoting on the highlighted
entry in Table \ref{Ta:Other_Algorithms_LinPro_added_constraint2} yields the final tableau
in Table \ref{Ta:Other_Algorithms_LinPro_added_constraint3}.

\begin{table}[h]
\caption{Updated tableau after one dual-simplex iteration}\label{Ta:Other_Algorithms_LinPro_added_constraint3}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & $s_4$ & RHS \\
\hline \hline
1& 0 & 0 & 0 & 0 &  $\frac{9}{8}$   & $\frac{1}{8}$ & $\frac{363}{8}$ \\ \hline
0 &1 &  0 & 0 & 0 & $\frac{3}{4}$   & $-\frac{1}{4}$  & $\frac{21}{4}$ \\ \hline
0 &0 &  0 & 1 & 0 & $-\frac{3}{4}$  & $\frac{1}{4}$  & $\frac{11}{4}$ \\ \hline
0 &0 &  1 & 0 & 0 & $-\frac{5}{8}$  & $\frac{3}{8}$  & $\frac{65}{8}$ \\ \hline
0 &0 &  0 & 0 & 1 & $-\frac{1}{4}$  & $-\frac{1}{4}$  & $\frac{5}{4}$ \\ \hline
\end{tabular}
\end{table}

\newpar
From this final tableau, we observe that the addition of the new constraint leads to an updated
solution of $\d (x_1,x_2)=\left(\frac{21}{4},\frac{65}{8} \right)$ with a corresponding profit of
$\ds z= \frac{363}{8} =45.375$. Observe how the added constraint has decreased \LPC's profit from the original model.


\newpar
As the steps involved in applying the dual simplex algorithm are quite similar to those
of its regular counterpart, we should not be surprised that the Maple worksheet,
\textbf{Simplex Algorithm.mw}, from Section
\ref{S:Simplex} is easily modified to execute the dual simplex method\index{dual simplex method!Maple implementation}. Specifically,
we substitute for the \mf{RowRatios} procedure in the original worksheet, a procedure
that computes ``column ratios'' instead. Syntax for doing so is given as follows:

\begin{maplelist}
\item \mf{ColumnRatios:=proc(M,r) local k:
\newline for k from 2 to nops(convert(Row(M,r),list))-1 do
\newline if M[r+1,k]=0 then print(cat(``Column'', convert(k-1,string), ``Ratio Undefined''))
\newline else print(cat(``Column'',convert(k-1,string), ``Ratio= '',
\newline convert(evalf(M[1,k]/M[r+1,k]),string))) end if; end do; end:
}
\end{maplelist}

\newpar
Here we follow our numbering convention that column 0 and row 0 denote the leftmost column and top row, respectively, of
the tableau matrix.

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

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_DualSimplex}	
	
\endinput
	
	