\documentstyle[12pt]{article}
\oddsidemargin 0.0in
\evensidemargin 0.0in
\textwidth 6.5in
\addtolength{\topmargin}{-.5in}
\addtolength{\textheight}{1in}
\newtheorem{thm}{\mbox{}}

\newcommand{\A}{\mbox{\bf A}}
\newcommand{\B}{\mbox{\bf B}}
\newcommand{\C}{\mbox{\bf C}}
\newcommand{\Q}{\mbox{\bf Q}}
\newcommand{\R}{\mbox{\bf R}}
\newcommand{\Z}{\mbox{\bf Z}}
\newcommand{\qed}{\hfill\rule{2.5mm}{2.5mm}}

\begin{document}
\oddsidemargin 0.0in
\evensidemargin 0.0in
\textwidth 6.5in
\addtolength{\topmargin}{-.5in}
\addtolength{\textheight}{1in}
\pagestyle{headings}

\begin{center}
\underline{{\bf FEASIBILITY}}
\end{center}

Consider an LP in equality form:
\[\begin{array}{rrrl}
\max &&{cx}&\\
\mbox{s.t.}&&{Ax}&={b}\\
&&{x}&\geq 0
\end{array}\]
If  an initial feasible basis is available, then, we have
seen that such an LP can be solved by the revised simplex method. If an initial
feasible basis is not available, we must first decide if the LP is
feasible, and if it
is feasible, we must find a feasible basis for it. This can be achieved by the
following procedure (referred to as the phase 1):

\begin{enumerate}
\item
Ensure that all the right-hand sides of the equality constraints are
non-negative (if
an equation has a negative right-hand side, multiply the equation through
by $-1$).
\item
Add an artificial variable to each constraint, and require that all of them be
non-negative.

\item
Maximize the sum of the negatives of the artificial variables subject to
the resulting
equality constraints, and non-negativity of all variables.

\item
If the maximum is negative, then the LP has no feasible solution. If the
maximum is
zero, then it is possible to obtain a basic feasible solution to the given LP.
\end{enumerate}


\underline{EXAMPLE 1:}
\[
\begin{array}{rrrrrrrrrr}
\max       &z&=&x_{1} &+&x_{2}&-&2x_{3}&    &\\
\mbox{s.t.}& & &2x_{1}&-&x_{2}&-&x_{3} &=   &2\\
           & & &2x_{1}&+&x_{2}&-&2x_{3}&=   &4\\
           & & &x_{1} &,&x_{2}&,&x_{3} &\geq&0
\end{array}
\]

The auxiliary LP (Phase 1 LP) is shown below: (Here $x_{4}$ and $x_{5}$ are the
  artificial variables.)
\[
\begin{array}{rrrrrrrrrrrrrr}
\max       &w&=&      & &     & &      &-&x_{5}&-&x_{6}&    &\\
\mbox{s.t.}& & &2x_{1}&-&x_{2}&-&x_{3} &+&x_{4}& &     &=   &2\\
           & & &2x_{1}&+&x_{2}&-&2x_{3}& &     &+&x_{5}&=   &4\\
           & & &x_{1} &,&x_{2}&,&x_{3} &,&x_{4}&,&x_{5} &\geq&0
\end{array}
\]

Starting with the basis $\{4,5\}$, we may apply the simplex method to solve
this LP.
(To set up the initial ditionary, we need to express $w$ in terms of the
non-basic
variables $x_{1},x_{2}$, and $x_{3}$.) The final dictionary obtained is
shown below:

\[
\begin{array}{rcrcrcrcr}

x_{1} &=&\frac{3}{2} &+&\frac{3}{4}x_{3}&- &\frac{1}{4}x_{4}
&-&\frac{1}{4}x_{5}\\
x_{2} &=&1           &+&\frac{1}{2}x_{3}&+ &\frac{1}{2}x_{4}
&-&\frac{1}{2}x_{5}  \\
\hline w     &=&0           & &         &- &           x_{4}  &-&  x_{5}
\end{array}
\]
By dropping the artificial variables, we obtain:
$x_{1}=\frac{3}{2}+\frac{3}{4}x_{3}$,
and $x_{2}=1+\frac{1}{2}x_{3}$ (see footnote\footnote{This shows that
$(\frac{3}{2},1,0)$ is a basic feasible solution to the given LP.}).  By
substtuting in
the given objective function, we have:
\begin{eqnarray*}
z&=&x_{1}+x_{2}-2x_{3}\\
 &=&(\frac{3}{2}+\frac{3}{4}x_{3})+(1+\frac{1}{2}x_{3})-2x_{3}\\
 &=&\frac{5}{2}-\frac{3}{4}x_{3}
\end{eqnarray*}

Thus we have the following feasible dictionary for the given LP:

\[\begin{array}{ccc}
x_{1}&=&\frac{3}{2}+\frac{3}{4}x_{3}\\
x_{2}&=&1+\frac{1}{2}x_{3}\\ \hline
z&=&\frac{5}{2}-\frac{3}{4}x_{3}
\end{array}\]

\vspace{.1in}
\noindent
REMARKS
\begin{enumerate}
\item
As in the phase 1 procedure in chapter 3, if an artificial variable is a
candidate for
the leaving variable in any iteration, it should be given preference.
\item
If the original system of equations has redundancies, inspite of using the
above rule,
one or more artificial varibles will remain basic at the end of phase 1.
Rows in which
artificial variables remain basic are redundant. (Further explanation in class.)
\end{enumerate}

\vspace{.2in}
\noindent
EXAMPLE 2: Determine whether or not the following system of equations has a
{\em non-negative} solution.
\[
\begin{array}{rrrrrrrrr}
3x_{1}&+&3x_{2}&-&3x_{3} &-&x_{4} &=   &2\\
-6x_{1}&+&3x_{2}&+&3x_{3} &+&4x_{4}&=   &4\\
4x_{1}&-&8x_{2}&-& x_{3} &-&4x_{4}&=   &6
\end{array}
\]

\vspace{.2in}
\noindent
SOLUTION: Add artificial variables $x_{5}$, $x_{6}$, and $x_{7}$ to the
first, second, and the third equations, respectively.  The auxiliary LP has the
following

\[
\begin{array}{rrrrrrrrrrrrrrrl}
\max&&&&&&&&-&x_{5}&-&x_{6}&-&x_{7}&\\
&3x_{1}&+&3x_{2}&-&3x_{3} &-&x_{4}&+&x_{5}& &  & &  &=   &2\\
&-6x_{1}&+&3x_{2}&+&3x_{3} &+&4x_{4}& &&+&x_{6} & & &=   &4\\
&4x_{1}&-&8x_{2}&-& x_{3} &-&4x_{4}& & & &  &+&x_{7}&=   &6\\
&&&&&&&&&&&&&x_{j}&\geq&0~~\mbox{forall}~ j
\end{array}
\]
The maximum of $w$ turns out to be $-34/3$. Since the maximum of $w$ is
negative, we
conclude that the given system of equations has no non-negative solution.

(We may apply the revised simplex method starting with the
input\footnote{Note that
the coefficient matrix is the $3$ by $7$ matrix obtained by adjoining a $3$
by $3$
identity matrix to  the coefficient matrix $A$ of the system of equations.}:
\[
{\B}=I~~~\mbox{and}~~
\left(\begin{array}{c}
x^{\ast}_{5}\\
x^{\ast}_{6}\\
x^{\ast}_{7}
\end{array}\right)=
\left(\begin{array}{c}
2\\4\\6\end{array}\right)\]

\noindent
Step 1: Solve the equation $yB=c_{B}$ to obtain $y$. Here $y=c_{B}=(-1,-1,-1)$.

\noindent
Step 2: Compute $\overline{c}_{N}=c_{N}-y\A_{N}=(1,-2,-1,-1).$ (Note that
$c_{N}=0$.)
Since, $\overline{c}_{1}$ is the only positive reduced cost, the entering
variable is
$x_{1}$  (and, $a$ is the first column of $\A$).

\noindent
Step 3: Solve the equation $Bd=a$ to obtain $d$. In this case, since $B$ is the
identity matrix, $d=a$ is the first column of $\A$.

\noindent
Step 4: The maximum value that can be given to $x_{1}$ is $2/3$, and when
$x_{1}$ is
given this value, $x_{5}$ becomes zero. Therefore, the leaving variable is
$x_{5}$.

\noindent
Input for the second iteration:

\[
{\B}=\left(\begin{array}{rrr}
3~&0~&0\\
-6~&1~&0\\
4~&0~&1
\end{array}\right)~~~\mbox{and}~~
\left(\begin{array}{c}
x^{\ast}_{1}\\
x^{\ast}_{6}\\
x^{\ast}_{7}
\end{array}\right)=
\left(\begin{array}{c}
2/3\\8\\10/3\end{array}\right)\]

\noindent
Step 1: Solve the equation $yB=c_{B}$ to obtain $y$. Here
$y=c_{B}=(-2/3,-1,-1)$.

\noindent
Step 2: Compute $\overline{c}_{N}=c_{N}-y\A_{N}=(-3,0,-2/3,-1/3).$ Since all the
reduced costs are less than or equal to zero, we have optimality.)


\vspace{.1in}
\noindent
CERTIFYING INFEASIBILITY:

The fact that the maximum of $w$ in the auxiliary problem is negative does
imply that
the system has no non-negative solution. But there is a more succinct way of
demonstrating this fact. For example, if we consider the linear combination
of the
three equations with  $(-2/3)$ times  the first equation,
$(-1)$ the second equation, and $(-1)$ times  the third equation, we obtain the
following equation:
$$3x_{2}+(2/3)x_{4}=-34/3 $$
Since the above equation is a linear combination of the given equations, any
solution to the given system is also a solution to this equation. However, it is
patently clear that this equation has no non-negative solution because all the
coefficients on the left are $\geq 0$, but the right-hand side constant term is
negative! The content of an important  theorem, known as Farkas Lemma is
that such
a demonstration is always possible.  Before stating this theorem, let us
note that if
$\A$ is an $m$ by $n$ matrix, and $y=(y_{1}, y_{2},...,y_{m})$ is a $1$ by $m$
row-vector, then the product
$y\A$ simply represents the linear combination of the rows of $\A$ with
coefficients
$y_{1}$, $y_{2}$,...,$y_{m}$ for the $m$ rows, respectively. If $\A x=b$ is
any system
of equations, and $y$ is any row vector, the every solution to the system
$\A x=b$ is
also a solution to the equation $y\A x=yb$.

If $\A$ represents the
coefficient matrix of the system in example 2, and $y=(-2/3,-1,-1),$ then
$$y\A=
(0,3,0,2/3)~~~\mbox{but}~~~yb=-34/3.$$


\noindent
\underline{{\bf Farkas Lemma:}} Let $\A$ be an $m$ by $n$ matrix, and let
$b$ be any $m$
by $1$ vector. Then, the system
                  $$(i)~~\A x=b~~x\geq {0}$$
has a solution if and only if the system
                   $$(ii)~~y\A\geq {0},~~yb<0$$
has no solution\footnote{Another way of stating the theorem is as follows:
{\em either} $\A x=b$ has a solution $x$ with $x\geq 0$,
{\em or}, there exists a vector $y$ such that $y\A\geq 0$, but $yb<0$, {\em
but not
both}. It is an example of a class of theorems known as the theorems of the
alternatives. Exercise 16.10, page 248 has several examples of such theorems.}.


\vspace{.1in}
\noindent
Proof: Firstly suppose that  $\overline{x}$ is a  solution to $(i)$. Then,
for any $y$,
$\overline{x}$ is also a solution to the equation $y\A x=yb$, which is   a
linear
combination of the equations in $(i)$. Thus,
         $$y\A \overline{x}=yb,~~\mbox{for any }~y$$
If $y$ is such that $y\A\geq 0$, then,  since $\overline{x}\geq 0$, $yb=y\A
\overline{x}$ is non-negative. It follows that $(ii)$ cannot have a solution.

\vspace{.2in}
To prove the converse, assume that $(i)$ has no solution, and consider the
following linear program and its dual:
\[
\begin{array}{rrc}
\mbox{Primal:}~~\max &0x&\\
\mbox{s.t.}&\A x&=b\\
&x&\geq 0
\end{array}
~~~
~~\begin{array}{rlc}
\mbox{Dual:}~~\min &yb&\\
\mbox{s.t.}&y\A&\geq 0\\&&
\end{array}
\]
Our assumption amounts to saying that the primal is infeasible. Thus, by
the duality theorem (see the chart on page 60):
\begin{itemize}
\item
either the dual is infeasible,
\item
or is feasible but unbounded.
\end{itemize}

But, clearly the dual is feasible ($y=0$ is a feasible solution).
Therefore, the dual
must be  unbounded. In particular, there must exist a feasible solution
$\overline{y}$ at which the value of the objective function is negative. Such a
$\overline{y}$ is a solution to $(ii)$. \qed


\vspace{.1in}
An alternative, constructive proof of the above theorem may be obtained
using phase 1.

Suppose that we are given a system of equations of the type $\A x=b$, and
are asked to
determine if it has a feasible solution. We can add artificial variables,
set up the
auxiliary LP, and apply the simplex method (or the revised simplex method)
to solve
it. If, in  the auxiliary LP, the maximum is zero, then by restricting the
optimal
solution  to the given (non-artificial) variables, we have a non-negative
solution to the given system.

 On the other hand, if the maximum in the auxiliary LP
is negative, then the $y$-vector corresponding to the final basis is such that
$y\A\geq 0$, but $yb<0$. (Sketch of proof: Suppose that the max of $w$ is
negative.
Consider the
$y$-vector corresponding to the final iteration. Then, by the optimality
criterion,
applied just to the non-artificial variables,
$c-y\A\leq 0$. Since, $c=0$, this amounts to saying the $-y\A \leq 0$, or,
equivalently, $y\A\geq 0$. On the other hand, $yb$ is the optimal value of the
objective function which is negative.)
\end{document}



