\documentclass[11pt]{article}
\usepackage{amsmath,amsfonts,colortbl,amsthm,html}
\usepackage[all]{xy}
\usepackage[bottomafter]{draftcopy}

\newcommand{\x}{\boldsymbol{x}}
\newcommand{\y}{\boldsymbol{y}}
\newcommand{\0}{\boldsymbol{0}}
\renewcommand{\a}{\boldsymbol{a}}
\renewcommand{\b}{\boldsymbol{b}}
\renewcommand{\c}{\boldsymbol{c}}
\renewcommand{\r}{\boldsymbol{r}}
\renewcommand{\v}{\boldsymbol{v}}
\renewcommand{\u}{\boldsymbol{u}}

\newcommand{\R}{\mathbb{R}}
\setlength{\extrarowheight}{2pt}

\renewcommand{\theenumi}{\roman{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}

\begin{document}
\title{Practical Guide to the \\
Simplex Method of Linear Programming}
\author{Marcel Oliver}
\date{Revised: September 28, 2020}
\maketitle

\newtheorem{theorem}{Theorem}

\section{The basic steps of the simplex algorithm}

\subsection*{Step 1: Write the linear programming problem in
\emph{standard form}}

Linear programming (the name is historical, a more descriptive term
would be \emph{linear optimization}) refers to the problem of
optimizing a linear \emph{objective function} of several variables
subject to a set of linear equality or inequality constraints.

Every linear programming problem can be written in the following
\emph{standard form}.  
\begin{subequations}
\begin{gather}
  \text{Minimize } \zeta = \c^T \x
\intertext{subject to}
  A\x = \b \,, \\
  \x \geq \0 \,.
\end{gather}
\end{subequations}
Here $\x \in \R^n$ is a vector of $n$ unknowns, $A \in M(m \times n)$
with $n$ typically much larger than $m$, $\c\in \R^n$ the coefficient
vector of the objective function, and the expression $\x \geq \0$
signifies $x_i \geq 0$ for $i=1,\dots,n$.  For simplicity, we assume
that $\operatorname{rank}A=m$, i.e., that the rows of $A$ are linearly
independent.

Turning a problem into standard form involves the following steps.
\begin{enumerate}

\item Turn Maximization into minimization and write inequalities in
standard order.

This step is obvious.  Multiply expressions, where appropriate, by
$-1$.

\item Introduce \emph{slack variables} to turn inequality constraints
into equality constraints with nonnegative unknowns.

Any inequality of the form $a_1 \, x_1 + \dots + a_n \, x_n \leq c$
can be replaced by $a_1 \, x_1 + \dots + a_n \, x_n + s = c$ with $s
\geq 0$.

\item Replace variables which are not sign-constrained by differences.

Any real number $x$ can be written as the difference of nonnegative
numbers $x=u-v$ with $u,v\geq 0$.
\end{enumerate}

Consider the following example.
\begin{subequations}
\begin{equation}
  \text{Maximize } z = x_1 + 2 \, x_2 +3 \, x_3
\end{equation}
subject to 
\begin{gather}
  x_1 + x_2 - x_3 = 1 \,, \label{1b} \\ 
  -2 \, x_1 + x_2 + 2 \, x_3 \geq -5 \,, \label{1c} \\
  x_1 - x_2 \leq 4 \,, \label{1d} \\
  x_2 + x_3 \leq 5 \,, \label{1e} \\
  x_1 \geq 0 \,, \\
  x_2 \geq 0 \,.
\end{gather}
\end{subequations}
Written in standard form, the problem becomes
\begin{subequations}
\begin{equation}
  \text{minimize } \zeta = - x_1 - 2 \, x_2 - 3 \, u + 3 \, v
\end{equation}
subject to 
\begin{gather}
  x_1 + x_2 - u + v = 1 \,, \label{3b} \\
  2 \, x_1 - x_2 - 2 \, u + 2 \, v  + s_1 = 5 \,, \label{3c} \\
  x_1 - x_2 + s_2 = 4 \,, \label{3d} \\
  x_2 + u - v + s_3 = 5 \,, \label{3e} \\
  x_1, x_2, u, v, s_1, s_2, s_3 \geq 0 \,.
\end{gather}
\end{subequations}

\subsection*{Step 2: Write the coefficients of the problem into a
\emph{simplex tableau}}

The coefficients of the linear system are collected in an augmented
matrix as known from Gaussian elimination for systems of linear
equations; the coefficients of the objective function are written in a
separate bottom row with a zero in the right hand column.

For our example, the initial tableau reads:
\newcolumntype{B}{%
  >{\columncolor[gray]{.8}[.5\tabcolsep]}c}
\begin{center}
\begin{tabular}{BcccBBB|c}
  $x_1$ & $x_2$ & $u$ & $v$ & $s_1$ & $s_2$ & $s_3$ \\
  \hline
  $1$ & $1$ & $-1$ & $1$ & $0$ & $0$ & $0$ & $1$ \\
  $2$ & $-1$ & $-2$ & $2$ & $1$ & $0$ & $0$ & $5$ \\
  $1$ & $-1$ & $0$ & $0$ & $0$ & $1$ & $0$ & $4$ \\
  $0$ & $1$ & $1$ & $-1$ & $0$ & $0$ & $1$ & $5$ \\
  \hline
  $-1$ & $-2$ & $-3$ & $3$ & $0$ & $0$ & $0$ & $0$ 
\end{tabular}
\end{center}

In the following steps, the variables will be divided into $m$
\emph{basic variables} and $n-m$ \emph{non-basic variables}.  We will
act on the tableau by the rules of Gaussian elimination, where the
pivots are always chosen from the columns corresponding to the basic
variables.

Before proceeding, we need to choose an initial set of basic variables
which corresponds to a point in the feasible region of the linear
programming problem.  Such a choice may be non-obvious, but we shall
defer this discussion for now.  In our example, $x_1$ and $s_1, \dots,
s_3$ shall be chosen as the initial basic variables, indicated by gray
columns in the tableau above.


\subsection*{Step 3: Gaussian elimination}

For a given set of basic variables, we use Gaussian elimination to
reduce the corresponding columns to a permutation of the identity
matrix.  This amounts to solving $A\x=\b$ in such a way that the
values of the nonbasic variables are zero and the values for the basic
variables are explicitly given by the entries in the right hand column
of the fully reduced matrix.  In addition, we eliminate the
coefficients of the objective function below each pivot.

Our initial tableau is thus reduced to
\begin{center}
\begin{tabular}{BcccBBB|c}
  $x_1$ & $x_2$ & $\boldsymbol{u}$ & $v$ & $s_1$ & $s_2$ & $s_3$ \\
  \hline
  $1$ & $1$ & $\boldsymbol{-1}$ & $1$ & $0$ & $0$ & $0$ & $1$ \\
  $0$ & $-3$ & $\boldsymbol{0}$ & $0$ & $1$ & $0$ & $0$ & $3$ \\
  $\mathit 0$ & $\mathit{-2}$ & $\boldsymbol{\mathit{1}}$ & 
    $\mathit{-1}$ & $\mathit 0$ & $\mathit 1$ & $\mathit 0$ & 
    $\mathit{3}$ \\
  $0$ & $1$ & $\boldsymbol{1}$ & $-1$ & $0$ & $0$ & $1$ & $5$ \\
  \hline
  $0$ & $-1$ & $\boldsymbol{-4}$ & $4$ & $0$ & $0$ & $0$ & $1$ 
\end{tabular}
\end{center}
The solution expressed by the tableau is only admissible if all basic
variables are non-negative, i.e., if the right hand column of the
reduced tableau is free of negative entries.  This is the case in this
example.  At the initial stage, however, negative entries may come up;
this indicates that different initial basic variables should have been
chosen.  At later stages in the process, the selection rules for the
basic variables will guarantee that an initially feasible tableau will
remain feasible throughout the process.

\subsection*{Step 4: Choose new basic variables}

If, at this stage, the objective function row has at least one
negative entry, the cost can be lowered by making the corresponding
variable basic.  This new basic variable is called the \emph{entering
variable}.  Correspondingly, one formerly basic variable has then to
become nonbasic, this variable is called the \emph{leaving variable}.
We use the following standard selection rules.

\begin{enumerate}
\item The \emph{entering variable} shall correspond to the column
which has the most negative entry in the cost function row.  If all
cost function coefficients are non-negative, the cost cannot be
lowered and we have reached an optimum.  The algorithm then
terminates.

\item Once the entering variable is determined, the \emph{leaving
variable} shall be chosen as follows.  Compute for each row the ratio
of its right hand coefficient to the corresponding coefficient in the
entering variable column.  Select the row with the smallest finite
positive ratio.  The leaving variable is then determined by the column
which currently owns the pivot in this row.  If all coefficients in
the entering variable column are non-positive, the cost can be lowered
indefinitely, i.e., the linear programming problem does not have a
finite solution.  The algorithm then also terminates.

\end{enumerate}
If entering and leaving variable can be found, go to Step~3 and
iterate.

Note that choosing the most negative coefficient in rule (i) is only a
heuristic for choosing a direction of fast decrease of the objective
function.  Rule (ii) ensures that the new set of basic variables
remains feasible.  

Let us see how this applies to our problem.  The previous tableau
holds the most negative cost function coefficient in column $3$,
thus $u$ shall be the entering variable (marked in boldface).  The
smallest positive ratio of right hand column to entering variable
column is in row $3$, as $\tfrac31<\tfrac51$.  The pivot in this row
points to $s_2$ as the leaving variable.  Thus, after going through
the Gaussian elimination once more, we arrive at
\begin{center}
\begin{tabular}{BcBcBcB|c}
  $x_1$ & $\boldsymbol{x_2}$ & $u$ & $v$ & $s_1$ & $s_2$ & $s_3$ \\
  \hline
  $1$ & $\boldsymbol{-1}$ & $0$ & $0$ & $0$ & $1$ & $0$ & $4$ \\
  $0$ & $\boldsymbol{-3}$ & $0$ & $0$ & $1$ & $0$ & $0$ & $3$ \\
  $0$ & $\boldsymbol{-2}$ & $1$ & $-1$ & $0$ & $1$ & $0$ & $3$ \\
  $\mathit{0}$ & $\boldsymbol{\mathit{3}}$ & $\mathit 0$ & $\mathit 0$ 
      & $\mathit 0$ & $\mathit{-1}$ & $\mathit{1}$ & $\mathit 2$ \\
  \hline
  $0$ & $\boldsymbol{-9}$ & $0$ & $0$ & $0$ & $4$ & $0$ & $13$ 
\end{tabular}
\end{center}
At this point, the new entering variable is $x_2$ corresponding to the
only negative entry in the last row, the leaving variable is $s_3$.
After Gaussian elimination, we find
\begin{center}
\begin{tabular}{BBBcBcc|c}
  $x_1$ & $x_2$ & $u$ & $v$ & $s_1$ & $s_2$ & $s_3$ \\
  \hline
  $1$ & $0$ & $0$ & $0$ & $0$ & $\tfrac23$ & $\tfrac13$ & $\tfrac{14}3$ \\
  $0$ & $0$ & $0$ & $0$ & $1$ & $-1$ & $1$ & $5$ \\
  $0$ & $0$ & $1$ & $-1$ & $0$ & $\tfrac13$ & $\tfrac23$ & $\tfrac{13}3$ \\
  $0$ & $1$ & $0$ & $0$ & $0$ & $-\tfrac13$ & $\tfrac13$ & $\tfrac23$ \\
  \hline
  $0$ & $0$ & $0$ & $0$ & $0$ & $1$ & $3$ & $19$ 
\end{tabular}
\end{center}
Since there is no more negative entry in the last row, the cost cannot
be lowered by choosing a different set of basic variables; the
termination condition applies.

\subsection*{Step 4: Read off the solution}

The solution represented by the final tableau has all nonbasic
variables set to zero, while the values for the basic variables can be
can be read off the right hand column.  The bottom right corner gives
the negative of the objective function.

In our example, the solution reads $x_1=\tfrac{14}3$, $x_2=\tfrac23$,
$x_3=u=\tfrac{13}3$, $s_1=5$, $v=s_2=s_3=0$, which corresponds to
$\zeta=-19$, which can be independently checked by plugging the
solution back into the objective function.

As a further check, we note that the solution must satisfy \eqref{1b},
\eqref{1d}, and \eqref{1e} with equality and \eqref{1c} with a slack
of $5$.  This can also be checked by direct computation.


\section{Initialization}

For some problem it is not obvious which set of variables form a
\emph{feasible} initial set of basic variables.  For large problems, a
trial-and-error approach is prohibitively expensive due the rapid
growth of $\binom{n}{m}$, the number of possibilities to choose $m$
basic variables out of a total of $n$ variables, as $m$ and $n$ become
large.  This problem can be overcome by adding a set of $m$ artificial
variables which form a trivial set of basic variables and which are
penalized by a large coefficients $\omega$ in the objective function.
This penalty will cause the artificial variables to become nonbasic as
the algorithm proceeds.

We explain the method by example.  For the problem
\begin{subequations}
\begin{gather}
  \text{minimize } z = x_1 + 2 \, x_2 + 2 \, x_3
\intertext{subject to}
  x_1 + x_2 + 2 \, x_3 + x_4 = 5 \,, \\
  x_1 + x_2 + x_3 - x_4 = 5 \,, \\
  x_1 + 2 \, x_2 + 2 \, x_3 - x_4 = 6 \,, \\
  \x \geq \0 \,,
\end{gather}
\end{subequations}
we set up a simplex tableau with three artificial variables which are
initially basic:
\begin{center}
\begin{tabular}{BBBcccc|c}
  $a_1$ & $a_2$ & $a_3$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ \\
  \hline
  $1$ & $0$ & $0$ & $1$ & $1$ & $2$ & $1$ & $5$ \\
  $0$ & $1$ & $0$ & $1$ & $1$ & $1$ & $-1$ & $5$ \\
  $0$ & $0$ & $1$ & $1$ & $2$ & $2$ & $-1$ & $6$ \\
  \hline
  $\omega$ & $\omega$ & $\omega$ & $1$ & $2$ & $2$ & $0$ & $0$ 
\end{tabular}
\end{center}
We proceed as before by first eliminating the nonzero entries below
the pivots:
\begin{center}
\begin{tabular}{BBBcccc|c}
  $a_1$ & $a_2$ & $a_3$ & $x_1$ & $x_2$ & $\boldsymbol{x_3}$ & $x_4$ \\
  \hline
  $\mathit 1$ & $\mathit 0$ & $\mathit 0$ & $\mathit 1$ & $\mathit 1$
  & 
    $\boldsymbol{\mathit{2}}$ & $\mathit 1$ & $\mathit 5$ \\
  $0$ & $1$ & $0$ & $1$ & $1$ & $\boldsymbol{1}$ & $-1$ & $5$ \\
  $0$ & $0$ & $1$ & $1$ & $2$ & $\boldsymbol{2}$ & $-1$ & $6$ \\
  \hline
  $0$ & $0$ & $0$ & $1-3\omega$ & $2-4\omega$ & $\boldsymbol{2-5\omega}$ & 
    $\omega$ & $-16\omega$ 
\end{tabular}
\end{center}
Since, for $\omega$ large, $2-5\omega$ is the most negative
coefficient in the objective function row, $x_3$ will be entering and,
since $\tfrac52<\tfrac62<\tfrac51$, $a_1$ will be leaving.
The Gaussian elimination step then yields
\begin{center}
\begin{tabular}{cBBccBc|c}
  $a_1$ & $a_2$ & $a_3$ & $x_1$ & $\boldsymbol{x_2}$ & $x_3$ & $x_4$ \\
  \hline
  $\tfrac12$ & $0$ & $0$ & $\tfrac12$ & $\boldsymbol{\tfrac12}$ & $1$ 
    & $\tfrac12$ & $\tfrac52$ \\
  $-\tfrac12$ & $1$ & $0$ & $\tfrac12$ & $\boldsymbol{\tfrac12}$ & $0$ 
    & $-\tfrac32$ & $\tfrac52$ \\
  $\mathit{-1}$ & $\mathit0$ & $\mathit1$ & $\mathit0$ 
    & $\boldsymbol{\mathit{1}}$ & $\mathit0$ & $\mathit{-2}$ & $\mathit1$ \\
  \hline
  $-1+\tfrac52\omega$ & $0$ & $0$ & $-\tfrac12\omega$ 
    & $\boldsymbol{1-\tfrac32\omega}$ & $0$ & 
    $-1+\tfrac72\omega$ & $-5-\tfrac72\omega$ 
\end{tabular}
\end{center}
Now $x_2$ is entering, $a_3$ is leaving, and we obtain
\begin{center}
\begin{tabular}{cBccBBc|c}
  $a_1$ & $a_2$ & $a_3$ & $\boldsymbol{x_1}$ & $x_2$ & $x_3$ & $x_4$ \\
  \hline
  $1$ & $0$ & ${-\tfrac12}$ 
    & $\boldsymbol{{\tfrac12}}$ & $0$ & $1$ 
    & ${\tfrac32}$ & $2$ \\
  $\mathit0$ & $\mathit1$ & $\mathit{-\tfrac12}$ & $\boldsymbol{\mathit{\tfrac12}}$ & $\mathit0$ & $\mathit0$ 
    & $\mathit{-\tfrac12}$ & $\mathit2$ \\
  $-1$ & $0$ & $1$ & $\boldsymbol{0}$ & $1$ & $0$ & $-2$ & $1$ \\
  \hline
  $\omega$ & $0$ & $-1+\tfrac32\omega$ & $\boldsymbol{-\tfrac12\omega}$ 
    & $0$ & $0$ & $1+\tfrac12\omega$ & $-6-2\omega$ 
\end{tabular}
\end{center}
The new entering variable is $x_1$ while the criterion for the leaving
variable is tied between $a_2$ and $x_3$.  Since we want the
artificial variable to become nonbasic, we take $a_2$ to be leaving.
(Choosing $x_3$ as the leaving variable would lead us to the same
solution, albeit after a few extra steps.)  We obtain
\begin{center}
\begin{tabular}{cccBBBc|c}
  $a_1$ & $a_2$ & $a_3$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ \\
  \hline
  $1$ & $-1$ & $0$ & $0$ & $0$ & $1$ 
    & $2$ & $0$ \\
  $0$ & $2$ & $-1$ & $1$ & $0$ & $0$ 
    & $-1$ & $4$ \\
  $-1$ & $0$ & $1$ & $0$ & $1$ & $0$ & $-2$ & $1$ \\
  \hline
  $\omega$ & $\omega$ & $-1+\omega$ & $0$ 
    & $0$ & $0$ & $1$ & $-6$ 
\end{tabular}
\end{center}
The termination condition is now satisfied, and we see that the
solution is $z=6$ with $x_1=4$, $x_2=1$, $x_3=0$, $x_4=0$.

We close with two remarks.
\begin{itemize}
\item When using a computer to perform the simplex algorithm
numerically, $\omega$ should be chosen large (one or two orders of
magnitude larger than any of the other coefficients in the problem)
but not too large (to avoid loss of significant digits in floating
point arithmetic).

\item If not all artificial variables become nonbasic, $\omega$ must
be increased.  If this happens for any value of $\omega$, the feasible
region is empty.

\item In the final tableau, the penalty parameter $\omega$ can only
appear in artificial variable columns.
\end{itemize}


\section{Duality}

The concept of duality is best motivated by an example.  Consider the
following transportation problem.  Some good is available at location
$A$ at no cost and may be transported to locations $B$, $C$, and $D$
according to the following directed graph:
\[
\xymatrix  {
  && *+<10pt>[o][F-]{B} \ar@/^/[drr]_4 \ar[dd]_3 \\
     *+<10pt>[o][F-]{A} \ar@/_/[drr]_2 \ar@/^/[urr]^1 &&&&
     *+<10pt>[o][F-]{D} \\
  &&  *+<10pt>[o][F-]{C} \ar@/_/[urr]^5 }
\]
On each of the unidirectional channels, the unit cost of
transportation is $c_j$ for $j=1,\dots,5$.  At each of the vertices
$b_\alpha$ units of the good are sold, where $\alpha = B,C,D$.  How
can the transport be done most efficiently?

A first, and arguably most obvious way of quantifying efficiency would
be to state the question as a minimization problem for the total cost
of transportation.  If $x_j$ denotes the amount of good transported
through channel $j$, we arrive at the following linear programming
problem:
\begin{subequations}
  \label{e.primal}
\begin{gather}
  \text{minimize } c_1 \, x_1 + \dots + c_5 \, x_5 \\
\intertext{subject to}
  x_1 - x_3 - x_4 = b_B \,, \\
  x_2 + x_3 - x_5 = b_C \,, \\
  x_4 + x_5 = b_D \,.
\end{gather}
\end{subequations}
The three equality constraints state that nothing gets lost at nodes
$B$, $C$, and $D$ except what is sold.

There is, however, a second, seemingly equivalent way of
characterizing efficiency of transportation.  Instead of looking at
minimizing the cost of transportation, we seek to maximize the income
from selling the good.  Letting $y_\alpha$ denote the unit price of
the good at node $\alpha = A, \dots, D$ with $y_A=0$ by assumption,
the associated linear programming problem is the following:
\begin{subequations}
  \label{e.dual}
\begin{gather}
  \text{maximize } y_B \, b_B + y_C \, b_C + y_D \, b_D \\
\intertext{subject to}
  y_B - y_A \leq c_1 \,, \\
  y_C - y_A \leq c_2 \,, \\
  y_C - y_B \leq c_3 \,, \\
  y_D - y_B \leq c_4 \,, \\
  y_D - y_C \leq c_5 \,.
\end{gather}
\end{subequations}
The inequality constraints encode that, in a free market, we can only
maintain a price difference that does not exceed the cost of
transportation.  If we charged a higher price, then ``some local guy''
would immediately be able to undercut our price by buying from us at
one end of the channel, using the channel at the same fixed channel
cost, then selling at a price lower than ours at the high-price end of
the channel.

Setting 
\begin{gather}
  \x =
  \begin{pmatrix}
    x_1 \\ \vdots \\ x_5
  \end{pmatrix} \,, \qquad 
  \y =
  \begin{pmatrix}
    y_B \\ y_C \\ y_D
  \end{pmatrix} \,, 
  \qquad \text{and }
  A =
  \begin{pmatrix}
    1 & 0 & -1 & -1 & 0 \\
    0 & 1 & 1 & 0 & -1 \\
    0 & 0 & 0 & 1 & 1
  \end{pmatrix} \,,
\end{gather}
we can write \eqref{e.primal} as the abstract \emph{primal problem}
\begin{subequations}
  \label{e.p}
\begin{gather}
  \text{minimize } \c^T \x \\
  \text{subject to } A\x = \b, \x \geq \0 \,.
\end{gather}
\end{subequations}
Likewise, \eqref{e.dual} can be written as the \emph{dual problem}
\begin{subequations}
  \label{e.d}
\begin{gather}
  \text{maximize } \y^T \b \\
  \text{subject to } \y^T A \leq \c^T \,.
\end{gather}
\end{subequations}
We shall prove in the following that the minimal cost and the maximal
income coincide, i.e., that the two problems are equivalent.

Let us first remark this problem is easily solved without the simplex
algorithm: clearly, we should transport all goods sold at a particular
location through the cheapest channel to that location.  Thus, we
might perform a simple search for the cheapest channel, something
which can be done efficiently by combinatorial algorithms such as
Dijkstra's algorithm \cite{D}.  The advantage of the linear
programming perspective is that additional constraints such as channel
capacity limits can be easily added.  For the purpose of understanding
the relationship between the primal and the dual problem, and for
understanding the significance of the dual formulation, the simple
present setting is entirely adequate.

The unknowns $\x$ in the primal formulation of the problem not only
identify the vertex of the feasible region at which the optimum is
reached, but they also act as sensitivity parameters with regard to
small changes in the cost coefficients $\c$.  Indeed, when the linear
programming problem is nondegenerate, i.e.\ has a unique optimal
solution, changing the cost coefficients from $\c$ to $\c + \Delta\c$
with $\lvert \Delta \c \rvert$ sufficiently small will not make the
optimal vertex jump to another corner of the feasible region, as the
cost depends continuously on $\c$.  Thus, the corresponding change in
cost is $\Delta \c^T \x$.  If $x_i$ is nonbasic, the cost will not
react at all to small changes in $c_i$, whereas if $x_i$ is large,
then the cost will be sensitive to changes in $c_i$.  This information
is often important because it gives an indication where to best spend
resources if the parameters of the problem---in the example above, the
cost of transportation---are to be improved.

Likewise, the solution vector $\y$ to the dual problem provides the
sensitivity of the total income to small changes in $\b$.  Here, $\b$
is representing the number of sales at the various vertices of the
network; if the channels were capacity constrained, the channel limits
were also represented as components of $\b$.  Thus, the dual problem
is providing the answer to the question ``if I were to invest in
raising sales, where should I direct this investment to achieve the
maximum increase in income?''

The following theorems provide a mathematically precise statement on
the equivalence of primal and dual problem.

\begin{theorem}[Weak duality]
Assume that $\x$ is a feasible vector for the primal problem
\eqref{e.p} and $\y$ is a feasible vector for the dual problem
\eqref{e.d}.  Then
\begin{enumerate}
\item $\y^T \b \leq \c^T \x$; \label{i.weak}
\item if (\ref{i.weak}) holds with equality, then $\x$ and $\y$ are
optimal for their respective linear programming problems;
\item the primal problem does not have a finite minimum if and only if the
feasible region of the dual problem is empty; vice versa, the dual
problem does not have a finite maximum if and only if the feasible
region of the primal problem is empty.
\end{enumerate}
\end{theorem}

The proof is simple and shall be left as an exercise.  

To proceed, we say that $\x$ is a \emph{basic feasible solution} of
$A\x = \b$, $\x \geq 0$ if it has at most $m$ nonzero components.  We
say that it is \emph{nondegenerate} if it has exactly $m$ nonzero
components.  If, in the course of performing the simplex algorithm,
we hit a degenerate basic feasible solution, it is possible that the
objective function row in the simplex tableau contains negative
coefficients, yet the cost cannot be lowered because the corresponding
basic variable is already zero.  This can lead to cycling and thus
non-termination of the algorithm.  We shall not consider the
degenerate case further.  

When $\x$ is a nondegenerate solution to the primal problem
\eqref{e.p}, i.e., $\x$ is nondegenerate basic feasible and also
optimal, then we can be assured that the simplex method terminates
with all coefficients in the objective function row nonnegative.  (If
they were not, we could immediately perform at least one more step of
the algorithm with strict decrease in the cost.)  In this situation,
we can use the simplex algorithm as described to prove the following
stronger form of the duality theorem.

\begin{theorem}[Strong duality]
The primal problem \eqref{e.p} has an optimal solution $\x$ if and
only if the dual problem \eqref{e.d} has an optimal solution $\y$; in
this case $\y^T \b = \c^T \x$.
\end{theorem}

\begin{proof}
We only give a proof in the case when the solution to the primal
problem is non-degenerate.  It is based on a careful examination of
the termination condition of the simplex algorithm.  Assume that $\x$
solves the primal problem.  Without loss of generality, we can reorder
the variables such that the first $m$ variables are basic, i.e.\
\begin{equation}
  \x =
  \begin{pmatrix}
    \x_B \\ \boldsymbol{0}
  \end{pmatrix}
\end{equation}
and that the final simplex tableau reads
\begin{equation}
  \label{e.final}
  \left(
  \begin{matrix}
    I & R \\
    \boldsymbol{0}^T & \r^T
  \end{matrix} \right.\left|\left.
  \begin{matrix}
    \x_B \\ -z
  \end{matrix}
  \right)\right. \,.
\end{equation}  
The last row represents the objective function coefficients and $z$
denotes the optimal value of the objective function.  We note that the
termination condition of the simplex algorithm reads $\r \geq \0$.  We
now partition the initial matrix $A$ and the coefficients of the
objective function $\c$ into their basic and nonbasic components,
writing
\begin{equation}
  A =
  \begin{pmatrix}
  B & N
  \end{pmatrix}
  \qquad \text{and} \qquad
  \c =
  \begin{pmatrix}
    \c_B \\ \c_N
  \end{pmatrix} \,.
\end{equation}
Finally, it can be shown that the elementary row operations used in
the Gaussian elimination steps of the simplex algorithm can be written
as multiplication by a matrix from the left, which we also partition
into components compatible with the block matrix structure of
\eqref{e.final}, so that the transformation from the initial to the
final tableau can be written as
\begin{equation}
  \label{e.final2}
  \begin{pmatrix}
    M & \v \\
    \u^T & \alpha
  \end{pmatrix}
  \left(
  \begin{matrix}
    B & N \\
    \c_B^T & \c_N^T
  \end{matrix} \right.\left|\left.
  \begin{matrix}
    \b \\ 0
  \end{matrix}
  \right)\right. 
  = \left(
  \begin{matrix}
    MB + \v \c_B^T & MN + \v \c_N^T \\
    \u^TB + \alpha \c_B^T & \u^TN + \alpha \c_N^T
  \end{matrix} \right.\left|\left.
  \begin{matrix}
    M\b \\ \u^T\b
  \end{matrix}
  \right)\right. \,.
\end{equation}  
We now compare the right hand side of \eqref{e.final2} with
\eqref{e.final} to determine the coefficients of the left hand matrix.
First, we note that in the simplex algorithm, none of the Gaussian
elimination steps on the equality constraints depend on the objective
function coefficients (other than the path taken from initial to final
tableau, which is not at issue here).  This immediately implies that
$\v=\0$.  Second, we observe that nowhere in the simplex algorithm do
we ever rescale the objective function row.  This immediately implies
that $\alpha=1$.  This leaves us with the following set of matrix
equalities:
\begin{subequations}
\begin{gather}
  MB=I \,, \\
  M\b = \x_B \,, \\
  \u^T B + \c_B^T = \0^T \,, \\
  \u^T N + \c_N^T = \r^T \,.
\end{gather}
\end{subequations}
so that $M = B^{-1}$ and $\u^T = -\c_B^T B^{-1}$.  We now claim that
\begin{gather}
  \y^T = \c_B^T B^{-1}
\end{gather}
solves the dual problem.  We compute
\begin{align}
  \y^T A 
  & = \c_B^T B^{-1}
      \begin{pmatrix}
        B & N
      \end{pmatrix} \notag \\
  & = \begin{pmatrix}
        \c_B^T & \c_B^T B^{-1}N
      \end{pmatrix} \notag \\
  & = \begin{pmatrix}
        \c_B^T & \c_N^T - \r^T
      \end{pmatrix} \notag \\
  & \leq \begin{pmatrix}
           \c_B^T & \c_N^T 
         \end{pmatrix} = \c^T \,.
\end{align}
This shows that $\y$ is feasible for the dual problem.  Moreover,
\begin{equation}
  \y^T \b = \c_B^T B^{-1} \b = \c_B^T \x_B = \c^T \x \,.
\end{equation}
Thus, by weak duality, $\y$ is also optimal for the dual problem.

The reverse implication of the theorem follows from the above by
noting that the bi-dual is identical with the primal problem.
\end{proof}



\begin{thebibliography}{9}

\bibitem{DT}
  G.B. Dantzig, M.N. Thapa,
  ``Linear Programming,''
  Springer, New York, 1997.

\bibitem{D}
  ``Dijkstra's algorithm.'' Wikipedia, The Free Encyclopedia. April 4,
  2012, 06:13 UTC. \\
  {\tiny\url{http://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algorithm&oldid=485462965}}

\bibitem{G}
  D. Gale,
  \textit{Linear Programming and the simplex method},
  Notices of the AMS \textbf{54} (2007), 364--369. \\
  {\tiny\url{http://www.ams.org/notices/200703/fea-gale.pdf}}

\bibitem{P}
  P. Pedregal, ``Introduction to optimization,'' Springer, New York,
  2004. 


\end{thebibliography}

\end{document}
