\documentstyle[12pt,fullpage]{article}
% \documentstyle[12pt]{siam}
\input{mssymb}
\pagestyle{empty}
\setlength{\textheight}{9.20in}
\setlength{\oddsidemargin}{-0.50in}
\setlength{\evensidemargin}{-0.50in}

\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 The Two-Phase Method for Solving General LP Problems}}
\end{center}

\begin{enumerate}

\item
Write down the (condensed) Phase-1 LP problem as follows:

\begin{itemize}
\item[{\it (i)}]
Convert all inequality constraints to equality constraints by
introducing slack variables $x_{n+1},\ldots,x_{n+\ell}$
($\ell$ is the number of slack variables).
\\
Now {\it all} constraints (except nonnegativity constraints)
in the LP problem are equality constraints.

\item[{\it (ii)}]
For each constraint with a negative RHS (i.e., {\bf b}$_i < 0$),
multiply it by $(-1)$.
\\
Now the LP problem has {\it nonnegative} RHS.

\item[{\it (iii)}]
Introduce the artificial variables $x_{n+\ell+1},\ldots,x_{n+\ell+m}$,
one per constraint.
\\
The (initial) Phase-1 LP is:
\[
	\mbox{maximize~~} w= -\sum_{i=1}^{m} x_{n+\ell+i}, \quad\quad
	\mbox{subject to~~} {\bf Ax}={\bf b},\;\; {\bf x}\ge 0,
\]
where {\bf A} now has a column for each $x_j$, $j=1,\ldots,n+\ell+m$.
\\
The initial basis consists of the artificial variables, and
is feasible.

\item[{\it (iv)}]
Repeat the following for each artificial variable $x_{n+\ell+i}$,
$i=1,\ldots,m$:
\\
If the column of $x_{n+\ell+i}$ in the matrix {\bf A}
is exactly the same as the column
of a {\it nonartificial} variable $x_k$,
then eliminate $x_{n+\ell+i}$ from the Phase-1 LP problem,
and in the initial basis
replace $x_{n+\ell+i}$ by $x_k$.

\end{itemize}

\item
Solve the (condensed) Phase-1 LP problem by the
revised (or standard) simplex method.
\\
Whenever there is a tie for the leaving variable and
an artificial variable is a candidate,
then choose an artificial variable.
\\
An artificial variable must be eliminated as soon as
it becomes nonbasic, that is,
the entry of that artificial variable in {\bf x}$_N$,
its column in {\bf A}$_N$ and its entry in {\bf c}$_N$
must all be eliminated.

\item
If the optimal value $w^{\star}$ of the (condensed) Phase-1 LP problem is nonzero,
then {\sc stop},
because the original LP problem is infeasible,
otherwise start Phase~2 and solve the {\it original} LP problem
using the simplex method as follows:

\begin{itemize}
\item[(I)]
Replace the Phase-1 objective function $w$ by the
original objective function $z$.

\item[(II)]
Take the initial Phase-2 basis heading $B$ to be the final
Phase-1 basis heading.
Each artificial variable present in
the final Phase-1 basis
must be kept in the initial Phase-2 basis.
The initial Phase-2 basis will be feasible.

\item[(III)]
Modify the leaving variable rule:
\\
After solving for {\bf d} in the system {\bf A$_B$d $\,=\,$ a},
if there is an artificial variable $x_{n+\ell+i}$
whose component in {\bf d} is nonzero,
then choose $x_{n+\ell+i}$ to be the leaving variable,
otherwise use the normal rule (i.e., the leaving variable
$x_r$ is a variable whose component $\mbox{\bf d}_{ir}$ in {\bf d}
is positive and whose ratio $\mbox{\bf x}^*_r/\mbox{\bf d}_{ir}$ equals
$\min_{\mbox{\scriptsize\bf d}_i >0} (\mbox{\bf x}_B^*)_i/{\bf d}_i$).

\item[(IV)]
An artificial variable must be eliminated as soon as
it becomes nonbasic;
see Step~2 above.

\end{itemize}

\end{enumerate}

%% \bigskip
%% \bigskip
%% \begin{center}
%% {{\large\bf The Revised Simplex Method modified to handle
%% 	artificial variables and free variables}}
%% \end{center}
%% 
%% The modifications are as follows:
%% \\
%% {\bf Artificial variables}:
%% Choose a leaving variable to be an artificial variable
%% whenever possible.
%% \\
%% An artificial variable must be eliminated as soon as
%% it becomes nonbasic, that is,
%% the entry of that artificial variable in $x_N$,
%% its column in $A_N$ and its entry in $c_N$
%% must all be eliminated.
%% 
%% \medskip
%% \noindent
%% {\bf Free variables}:
%% A free variable $x_j$ {\it not in} the basis
%% may be the entering variable if its
%% reduced cost $\ov{c}_j = c_j - y \cdot A^{(j)}$
%% (here $A^{(j)}$ means the column of $x_j$ in the matrix $A$)
%% is positive or {\it negative}.
%% Suppose that a free variable $x_j$ enters with $\ov{c}_j < 0$,
%% then the value of $x_j$ {\it decreases} to the {\it maximum} $t$
%% ($t < 0$) such that the new basic solution stays feasible.
%% \\
%% Further, if a free variable is {\it in} the basis,
%% then it {\it never} leaves.

\end{document}