\documentstyle[12pt,fullpage]{article}
% \documentstyle[12pt]{siam}
\input{mssymb}
\pagestyle{empty}
\setlength{\textheight}{9.00in}

\def\ov#1{\overline{#1}}
\def\wt#1{\widetilde{\mbox{\bf #1}}}
\newcommand{\alg}[1]{\newline\parbox{#1cm}{\ }}

\begin{document}

\begin{center}
{{\Large\bf C\&O 350~~~~~Linear Programming}}
\end{center}

\vspace{0.10in}
\begin{center}
{{\large\bf Dictionaries, Pivots and the Simplex Method}}
\end{center}

\bigskip
\begin{center}
{{\large Dictionaries }}
\end{center}

\vspace{0.10in}

Let (D) be a given dictionary (an example is given below).
Suppose that the dictionary has $m+1$ rows,
including the last row for $z$,
and suppose that it has $n$ right hand side variables.
The left hand side (LHS) $x$ variables of (D)
are called {\it basic}
(note that the LHS variable of the last row, $z$, is not basic),
and the right hand side (RHS) variables of (D)
are called {\it nonbasic}.
\\
\\
Consider a row of the dictionary
that has $x_h$ as its basic variable.
On the RHS, there is a constant term (not containing any $x_j$)
denoted by $\ov{b}_h$, and
there is a term for each nonbasic variable $x_j$,
denoted by $-\ov{a}_{hj} x_j$
(it is possible that some $x_j$'s have $\ov{a}_{hj} = 0$).
Hence, this row of (D) is denoted
\[ x_h = \ov{b}_h - \sum_{j : j \mbox{\footnotesize ~is nonbasic} }
	\ov{a}_{hj} x_j. \]
Note that
in  the initial dictionary,
for a row with $x_h$ as its basic variable
we have $\ov{b}_h = b_h$ and $\ov{a}_{hj} = a_{hj}$,
hence this row of the initial dictionary is denoted
\[ x_h = {b}_h - \sum_{j : j \mbox{\footnotesize ~is nonbasic} }
	{a}_{hj} x_j. \]
\\
\\
Now consider the last row of the dictionary (D):
the constant term is denoted by $z^*$
and the coefficient of a nonbasic variable $x_j$
is denoted by $\ov{c}_j$;
so the last row is denoted
\[ z = z^* + \sum_{j : j \mbox{\footnotesize ~is nonbasic} }
	\ov{c}_{j} x_j. \]
\\
\\
In the dictionary (D), the set of subscripts of the basic
variables $x_h$ is denoted by $B$;
that is, $B$ is a subset containing
exactly $m$ elements chosen from the numbers
$\{1,2,\ldots,n,\mbox{$n+1$},\dots,\mbox{$n+m$}\}$,
such that for each element $h \in B$
the variable $x_h$ occurs on the left hand side of the dictionary.
The set of subscripts of the nonbasic variables $x_j$
in the dictionary is denoted by $N$.
\\
\\
We can now state the notation for a dictionary:

\bigskip
\begin{tabular}{lccccc}
(D)\quad\quad \\
 & $x_h$ & = & $\ov{b}_h$ & $-$ & $\sum_{j\in N} \ov{a}_{hj} x_j$ \\
 & \multicolumn{5}{c}{\hrulefill} \\
 & $z$ & = & $z^*$ & $+$ & $\sum_{j\in N} \ov{c}_{j} x_j$ \\
\end{tabular}

\bigskip
Associated with every dictionary is a so-called
{\it basic solution};
each dictionary has exactly one basic solution,
and this solution is obtained by setting the nonbasic variables
at zero, and evaluating the basic variables
from the equations of the dictionary.
In terms of the dictionary notation,
the basic solution is
\[ x_h = \ov{b}_h \; (h\in B),\quad\quad
	x_j = 0 \; (j\in N). \]
A dictionary is called {\it feasible}
if its basic solution is feasible,
i.e., if every basic variable $x_h$ has
a nonnegative value for $\ov{b}_h$
(no special conditions are needed on the nonbasic variables
since all of them have value zero).

\bigskip
{\bf An Example}:
Consider the third dictionary (D3)
for the example LP from the first lecture:

\bigskip
\begin{tabular}{lcccccc}
$x_2$ & = & $8$ & $-$ & $x_3$ & $-$ & ${1 \over 5}x_4$ \\
$x_1$ & = & $4$ & $+$ & $x_3$ & & \\
\hline
$z$   & = & 32		& $-$ & $x_3$ & $-$ & ${3 \over 5} x_4$
\end{tabular}
\bigskip

\noindent
Here, $B = \{ 1, 2\}$, and $N = \{ 3, 4\}$;
\\
$z^* = 32$, $\ov{c}_3 = -1$ and $\ov{c}_4 = -{3\over 5}$.
\\
For $h=1 \in B$, $\ov{b}_h = 4$,
$\ov{a}_{h3} = -1$ (in this row,
the coefficient of $x_3$ is $+1$, but
according to the notation for dictionaries
the term for $x_3$ is $-\ov{a}_{h3} x_3$),
and lastly, $\ov{a}_{h4} = 0$.
\\
For $h=2 \in B$, $\ov{b}_h = 8$,
$\ov{a}_{h3} = +1$,
and $\ov{a}_{h4} = +{1\over 5}$.
\\
The basic solution of this dictionary is
\[ x_1 = 4, x_2 = 8,\]
and since this solution is feasible
the dictionary too is called feasible.

\bigskip
\bigskip
\begin{center}
{{\large Pivots }}
\end{center}
\vspace{0.10in}

\noindent
{\bf Pivot}.
The computational process of constructing a new dictionary
from an old dictionary is called a {\it pivot}.
In particular, each iteration of the simplex method
constitutes a pivot.
\\ \\
{\bf Entering variable and pivot column}.
In a pivot, the nonbasic variable of the old dictionary
that becomes a basic variable of the new dictionary
is called the {\it entering variable}.
The column of the dictionary corresponding to the
entering variable is called the {\it pivot column}.
The entering variable is denoted by $x_s$,
i.e., $s$ is the subscript of the pivot column.
\\ \\
{\bf Leaving variable and pivot row}.
In a pivot, the basic variable of the old dictionary
that becomes a nonbasic variable of the new dictionary
is called the {\it leaving variable}.
The row of the dictionary having the leaving
variable on its LHS is called the {\it pivot row}.
The  leaving variable is denoted by $x_r$,
i.e., $r$ is the subscript of the pivot row.
\\ \\
{\bf Description of a pivot}.
Let (D) be a given dictionary.
With (D) as the old dictionary, consider a pivot on $(r,s)$,
where $s\in N$ is the subscript of the entering variable,
$r\in B$ is the subscript of the leaving variable,
and the coefficient $\ov{a}_{rs}$ in the dictionary (D)
is nonzero.
The pivot is the following operation:
\\
Replace the equation
\[ x_r = \ov{b}_r - \sum_{j\in N} \ov{a}_{rj} x_j \]
in the dictionary (D) by
\[ x_s = {1\over \ov{a}_{rs}} ( \ov{b}_r - x_r
	- \sum_{j\in N-\{s\} } \ov{a}_{rj} x_j ), \]
and replace all other equations in the dictionary (D)
by substituting this formula for $x_s$ into them.
The resulting dictionary is the new dictionary of the pivot.

\bigskip
\bigskip
\begin{center}
{{\large The Simplex Method}}
\end{center}
\vspace{0.10in}

We make two simplifying assumptions in this outline:
\begin{itemize}
\item
We restrict attention to LP problems with a feasible origin,
i.e., those with each RHS $b_i$ nonnegative (see page~28 of the text).
\item
We ignore the possibility of cycling (see pages~30--38 of the text).
\end{itemize}
\medskip
Both assumptions will be removed when we come to
the end of Chapter~3 in the text.

\vfill

\noindent
\alg{1.0} To start, construct a feasible dictionary;
\alg{1.0} {\bf while} there is a $j\in N$ with $\ov{c}_j > 0$ {\bf do}
\alg{1.5}    choose $s\in N$ with $\ov{c}_s > 0$;
\alg{1.5}    {\bf if} $\ov{a}_{hs} \le 0$ for all $h\in B$ {\bf then}
\alg{2.0}       {\sc STOP} since the LP problem is unbounded;
\alg{1.5}       {\bf else}
\[ \mbox{choose~} r\in B \mbox{~such that~} \ov{a}_{rs} > 0 \mbox{~and~}
		{\ov{b}_r \over \ov{a}_{rs} } =
		\min_{\ov{a}_{hs} > 0} ({\ov{b}_h \over \ov{a}_{hs}}) ;
\]
\alg{2.0}       pivot on $(r,s)$ to get a new feasible dictionary;
\alg{1.5}    {\bf end~if}
\alg{1.0} {\bf end~while}
\alg{1.0} {\sc STOP};
\\
\alg{1.0} at termination, the basic solution of the final dictionary is feasible;
\alg{1.0} moreover, for all $j\in N$, we have $\ov{c}_j \le 0$,
\alg{1.0} therefore, the basic solution of the final dictionary is optimal.

\end{document}