\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}


\begin{center}
{\bf C\&O 350} \footnote{If you find any mistakes or misprints,
please
bring them to the attention of one of: 
whcunnin@math, usrmurty@math, hwolkowicz@orion. }
\end{center}
\section{LPs in Equality Form}

A maximization LP in which all the variables are required to be non-negative,
and all the constraints, except the non-negativity restrictions, are  equalities
is said to be in {\bf standard  equality form} or simply in
{\bf equality form}\footnote{This concept is not used in
Chv\'{a}tal.}. Thus, an LP in  equality form is one of the following type:
\begin{equation}
\left.\begin{array}{lrclcl}
\mbox{Maximize}   & \displaystyle\sum_{j=1}^{n}c_{j}x_{j} &     &     &  & \\
\mbox{subject to} & \displaystyle\sum_{j=1}^{n}a_{ij}x_{j}&= &b_{i}&
&(i=1,2,\cdots,m)\\
                  &                     x_{j}&\geq &0    &
&(j=1,2,\cdots,n)
\end{array}
\right\}
\label{eqLP}
\end{equation}
The above LP may also be stated in matrix notation as follows:
\[\begin{array}{rrcr}
\mbox{maximize} &{\bf cx}& & \\
\mbox{subject to}&{\bf Ax}&=&{\bf b}\\
&{\bf x}&\geq & {\bf 0}
\end{array}
\]
where $\A$ is an  $m$ by $n$ matrix, the vector ${\bf c}$
is a $1$ by $n$ row vector\footnote{For compatibility of matrix
multiplication, we should make sure that two matrices being multiplied have
compatible
orders. Thus if we want to multiply a vector ${\bf c}$ in $\R ^n$ by
another vector
${\bf x}$ in $\R ^n$, in that order, then ${\bf c}$ must be a row vector
and ${\bf x}$ a
column vector. Some authors regard all vectors as column vectors. In that
case, we must
transpose appropriately to ensure compatibility. For example, if ${\bf c}$
and ${\bf
x}$ are both taken as column vectors, then we must write
${\bf c}^{t}{\bf x}$, where ${\bf c}^{t}$ is the transpose of ${\bf c}$.},
${\bf b}$ is
an
$m$ by $1$ column vector, and ${\bf x}$ is an $n$ by $1$ column vector, as
shown below:
\[\A=\left(\begin{array}{cccc}
a_{11} &a_{12} &...&a_{1n}\\
a_{21} &a_{22} &...&a_{2n}\\
.&&&.\\
.&&&.\\
.&&&.\\
a_{m1} &a_{m2} &...&a_{mn}
\end{array}\right)~\mbox{and }~b~=\left( \begin{array}{c}
b_{1}\\
b_{2}\\
.\\
.\\
.\\
b_{m}
\end{array}\right)\]
\[\begin{array}{llllllcc}
{\bf c}
&=&(c_{1},&~~c_{2},&...&~c_{n})\hspace{1.5in}\\
{\bf x}^{t}
&=&(x_{1},&~~x_{2},&...&~x_{n})\hspace{1.5in}
\end{array}
\]
Note that ${\bf x}$ is a column vector;
the vector
${\bf x}^{t}$ displayed above is its transpose. We refer to $A$ as the {\bf
matrix of the
LP},
${\bf c}$ as the {\bf cost vector}, and ${\bf b}$ as the {\bf constant  vector}.

The following is an example of an LP in equality form.
\[\begin{array}{lrcrcrcrcr}
\mbox{max } & 4x_{1}&-& 4x_{2} &+& 3x_{3}&+& 3x_{4}&      &   \\
\mbox{s.t. }&  x_{1}&-& 3x_{2} &+&  x_{3}&+& 9x_{4}& = & 4  \\
            & 4x_{1}&+&  x_{2} &+& 2x_{3}&+& 3x_{4}& = & 3 \\
            &3x_{1} &+& 4x_{2} &+& 2x_{3}&+& 6x_{4}& = & 1  \\
            &x_{1}  &,&  x_{2} &,& x_{3} &,&  x_{4}& \geq & 0
\end{array}
\]
An LP in  standard (inequality) form\footnote{In the early chapters of the
textbook,
only LPs in inequality form are considered.} may be converted to one in
equality form by
adding slack variables. In fact, for solving an LP in  inequality form by
the simplex
method, we first convert it to an LP in equality form by adding slack
variables, and
apply the simplex method to the   LP in equality form. Consider for example, the
following LP in standard (inequality) form

\begin{equation}
\left.\begin{array}{lrcrcrcr}
\mbox{max }~z=& 6x_{1}&+& 4x_{2} &+& 2x_{3}&      &   \\
\mbox{s.t. }& 2x_{1}&+&  x_{2} &+&  x_{3}& \leq & 4  \\
            & 4x_{1}&+& 2x_{2} &+& 2x_{3}& \leq & 12 \\
            &3x_{1} &+& \frac{5}{2}x_{2} &+& 2x_{3}& \leq & 8  \\
            &x_{1}  &,&   x_{2}&,&  x_{3}& \geq & 0
\end{array}\right\}\label{ex.ineqLP}
\end{equation}
 We may convert this LP to
the following equality LP by introducing the slack variables $x_{4}$,
$x_{5}$, and
$x_{6}$:
\begin{equation}\left.
\begin{array}{lrcrcrcrcrcrcr}
\mbox{max }~z= & 6x_{1}&+& 4x_{2} &+& 2x_{3}&      &&&&&&&   \\
\mbox{s.t. }& 2x_{1}&+&  x_{2} &+&  x_{3}&+&x_{4}& &     & &     & = & 4  \\
            & 4x_{1}&+& 2x_{2} &+& 2x_{3}& &     &+&x_{5}& &     & = & 12 \\
            &3x_{1} &+& \frac{5}{2}x_{2} &+& 2x_{3}& &     & &
&+&x_{6}& = & 8  \\
            &x_{1}  &,&   x_{2}&,&  x_{3}&,&x_{4}&,&x_{5}&,&x_{6}&\geq& 0
\end{array}\right\}\label{exconverted}
\end{equation}
For this LP:
\[
~~~~\A=\left(\begin{array}{cccccc}
2~~& 1~~ & 1~~ & 1~~ & 0~~ & 0\\
4~~ & 2~~ & 2~~ & 0 ~~& 1~~ & 0\\
3~~&\frac{5}{2}~~&2~~&0~~&0~~&1
\end{array}\right)~~~~~
{\bf b}~=\left( \begin{array}{c}
4\\
12\\
8
\end{array}\right)\]
\[\begin{array}{llllllllr}
{\bf c}&=&(6,&4,&2,&0,&0,&0~~)&\hspace{1in}\\
{\bf x}^t&=&(x_{1},&x_{2},&x_{3},&x_{4},&x_{5},&x_{6})&\hspace{1in}
\end{array}
\]

The purpose of this handout is to provide definitions of the concepts such
as bases,
basic solutions, dictionaries, etc., used in the development of the simplex
method.
These definitions are given for equality LPs.


A  knowledge of the fundamental notions of linear algebra is necessary for
understanding the theory of linear programming, in particular, the
development of
the simplex method. Students should be familiar with the  concepts of linear
independence of vectors, bases and dimension of  a vector space,  ranks of
matrices,
and the relationship of  these notions with solution sets of systems of linear
equations.

\section{Equivalence}
In the simplex method, we start with a system of linear equations. In each
iteration,
this system is transformed to a new system by means of elementary row
operations.
Although, in each iteration, we deal with a different looking system of
equations,
they all ``carry the same information". To make this precise, we need the
following
important notion.

\noindent
\begin{thm}\underline{Definition:} Two systems of linear equations are said
to be {\bf
equivalent}\footnote{The dictionaries encountered during the course of an
application
of the simplex method are all equivalent.} if they have the same set of
solutions.
\end{thm}

\section{Notation}
Consider a system $${\bf Ax}={\bf b}$$
of linear equations where $\A$ is an $m\times n$ matrix.
This system may also be rewritten as
$$x_{1}A_{1} + x_{2}A_{2} + \ldots + x_{n}A_{n} = b$$
where $A_{j}$ is the $j$th column of the matrix $A$. (This shows the
correspondence between the columns of $\A$ and the $n$ variables.)


In studying linear equations, it is often convenient to group terms
involving subsets
of variables. To express such grouping, the following matrix notation is
convenient.

 For any subset $J$ of the column index set $\{1,2,...,n\}$, we shall let
${\A}_{J}$
denote the submatrix of $\A$   consisting of the columns with their indices
in $J$.
(If  $J=(j_{1},j_{2},...,j_{k})$ is an ordered subset, then
${\A}_{J}$ denotes the matrix $(A_{j_{1}},A_{j_{2}},...,A_{j_{k}})$. If
there is no
specified ordering of the elements of $J$, then then the columns of
${\A}_{J}$ may be
listed in any order.)

\begin{thm}\label{example1}
\underline{Example:} Consider the LP
\end{thm}
$$\max ~z={\bf cx},~\mbox{s.t.}~{\bf Ax}={\bf
b},~{\bf x}\geq{\bf 0},$$ where
\[\A=\left(\begin{array}{rrrr}
3&-6&3&6\\
4&1 &5&10\end{array}\right)~~~~
{\bf b}=\left(\begin{array}{c}
12\\25\end{array}\right)
\]
and
$${\bf c}=(-7,5,-10,-19).$$
If $B=(1,2)$  and $N=(3,4)$, then
\[
{\A}_{B}=\left(\begin{array}{rr}
3&-6\\
4&1 \end{array}\right) ,~~~~
{\bf x}_{B}=\left(\begin{array}{c}
x_{1}\\x_{2}\end{array}\right),~~~~
{\A}_{N}=\left(\begin{array}{rr}
3&6\\
5&10 \end{array}\right) ,~~~~
{\bf x}_{N}=\left(\begin{array}{c}
x_{3}\\x_{4}\end{array}\right)
\]
and
$${\bf c}_{B}=(-7,5)~~\mbox{and}~~ {\bf c}_{N}=(-10,-19).$$
Now the system ${\bf Ax}={\bf b}$may be rewritten as
$${\A}_{B}{\bf x}_{B}+{\A}_{N}{\bf x}_{N}={\bf b}.$$
This amounts to grouping, in each equation, the terms involving the
variables $x_{1}$
and $x_{2}$ together, and the terms involving the  variables $x_{3}$
and $x_{4}$ together. Similarly,
$$z={\bf c}{\bf x}={\bf c}_{B}{\bf x}_{B}+{\bf c}_{N}{\bf x}_{N}.$$
\section{Bases}
 Clearly, a system $\A{\bf x} = {\bf b}$
is consistent if, and only if, ${\bf b}$ is in the column space of the
matrix $\A$. In
fact,  every solution ${\bf s}$ corresponds to an expression (${\bf
b}=\sum_{i=1}^{n}s_{j}A_{j}$) of ${\bf b}$ as a linear combination of the
columns of
$\A$.  In particular, $\A{\bf x} = {\bf b}$ has a solution if, and only if,
${\bf
b}$ can be expressed as a linear combination of any basis of the column
space of $\A$.
This observation leads to the central notion of this subject, namely, the
notion of a
basis.

\vspace{.1in}
Consider a system $\A{\bf x} = {\bf b}$ of linear equations with rank($\A$)=
$m$. (See footnote\footnote{Although the systems of equations associated
with  LPs may
be either inconsistent or redundant, the systems that we use in the
computational
procedures are both consistent and  not redundant. 
(For example, when we add slack
variables to an inequality LP,  or, when we add artificial
variables in Phase 1, we obtain such a system.) For this reason, in
studying properties
of linear equations relevant to the development of the simplex method, we
shall assume
that we have a system
$\A{\bf x} = {\bf b}$ which is both consistent and irredundant.  This amounts to
assuming that the matrix $\A$ is of full rank (i.e. rank($\A$)= $m$ = the
number of rows
of $\A$).})

\begin{thm}
\underline{Definition:} An $m$-element subset  $B$ of the column index set
$\{1,2,...,n\}$ is called a {\bf basis} if the $m$ columns of the submatrix
${\A}_{B}$ are linearly independent (equivalently, if ${\A}_{B}$ is invertible).
Note that when $B$ is a basis, the $m$ columns of $\A_{B}$ constitute a
basis for
the column space ($\R^{m}$) of $\A$; this is the reason for calling $B$ a basis.
\end{thm}

\begin{thm}
\underline{Definition:} An {\bf ordered basis} is a basis with a specified
ordering of
its elements. If $B$ is an ordered basis, the matrix ${\A}_{B}$ is called
the {\bf basis
matrix} corresponding to $B$.
\end{thm}


\begin{thm}
\underline{Definition:} If $B$ is a basis, the variables with subscripts in
the set are
{\bf basic variables} with respect $B$, and the remaining  variables, i.e.
those  with
subscripts not in $B$ are the {\bf non-basic variables}.
\end{thm}

For convenience, we shall denote the complement
of $B$, i.e. the set of the subscripts of non-basic variables, by $N$.

\vspace{.1in}


The vector of
variables restricted to $B$ is ${\bf x}_{B}$, and vector of variables
restricted to
$N$ is ${\bf x}_{N}$. Analogously, $\A_{B}$ and ${\bf c}_{B}$ are the
restrictions of $\A$ and ${\bf c}$, respectively, to columns with subscripts in
$B$, and $\A_{N}$ and ${\bf c}_{N}$ are the
restrictions of $\A$ and ${\bf c}$, respectively, to the columns with
subscripts in $N$.

By grouping variables according to whether or not they are basic, we may
rewrite the
system $\A{\bf x}={\bf b}$ as follows:
$$\A_{B}{\bf x}_{B}+\A_{N}{\bf x}_{N}={\bf b}$$
Note that given any basis $B$, ${\bf b}$ can be expressed as a unique linear
combination of the columns of ${\A}_{B}$. Thus, there is a unique solution to
$\A{\bf x}={\bf b}$ with ${\bf x}_{N}={\bf 0}$, namely, ${\bf
x}_{B}={\A}_{B}^{-1}{\bf
b}$. This solution is called the {\bf basic solution} corresponding to the
basis $B$.

\vspace{.2in}
\noindent
Exercise:
Determine, by inspection,  all the bases of  the following two systems.
\[ \begin{array}{lrcrcrcrcr}
(i) ~~~~~& x_{1}  & + & x_{2}  & + & 2x_{3} & + & x_{3} & = & 1 \\
         & 2x_{1} & + & 2x_{2} & + & 4x_{3} & + & x_{3} & = & 2
\end{array} \]
\[ \begin{array}{lrcrcrcrcrcr}
(ii)     & x_{1}  & + & x_{2}  & + & x_{3}  & + & x_{4}  & + & x_{5}  & = & 7 \\
         & x_{1}  & + & 2x_{2} & + & 2x_{3} & + & 3x_{4} & - & 2x_{5} & = & 3 \\
         & 2x_{1}& + & 3x_{2} & + & 3x_{3} & + & 4x_{4} & - & x_{5}  & = & 10
\end{array} \]



\section{The system of equations representing an LP}
Suppose that we have an equality LP of the form:
$$\max ~z={\bf cx},~\mbox{s.t.}~{\bf Ax}={\bf b},~{\bf x}\geq{\bf 0}$$
where $\A$ is an $m\times n$ matrix. By treating $z$ as a variable, we may
associate
with this LP, the system
\[\left.\begin{array}{lcrcc}\label{systemforLP}
&&{\bf Ax}&=&{\bf b}\\ \hline
z&-&{\bf cx}&=&0
\end{array}\right\}
\]
of $m+1$ equations in $n+1$ variables. (The first $m$ equations of the
system represent
the equality constraints. The last equation represents the objective
function; it is
separated from the other equations by a horizontal line because the objective
function has a special status.) We may in fact view this system as
representing the
statement of the LP with the understanding that $z$ is to be maximized, and
that
the variables $x_{1}$, $x_{2}$,...,$x_{n}$ are required to be non-negative.

The augmented coefficient matrix of the system (\ref{systemforLP})
associated with
the LP is
\[\left(\begin{array}{c|c|c}
{\bf 0}&\A&{\bf b}\\
\hline
1&-{\bf c}&0
\end{array}\right) .
\]
If there is a partition of the index set $\{1,2,...,n\}$ into two sets $B$ and
$N$, the grouping of terms involving variables with subscripts depending on
whether
or not they belong to $B$ or $N$ may be indicated by grouping the columns in the
augmented coefficient matrix as follows:

\begin{equation}
\left(\begin{array}{c|c|c|c}
{\bf 0}&{\A}_{B}&{\A}_{N}&{\bf b}\\
\hline
1&-{\bf c}_{B}&-{\bf c}_{N}&0
\end{array}\right)\label{syseq}
\end{equation}

\begin{thm}
\underline{Example:} Consider the following system of equations:
\end{thm}
\[
\begin{array}{cccccccc}
&x_{4}&&     &+&2x_{1}&-&4x_{3}=5\\
     &&&x_{2}&+&3x_{1}&+&2x_{3}=3\\
\hline
z&&&&-&4x_{1}&+&5x_{3}=6
\end{array}
\]

We may represent this system in matrix notation as follows:
\[
\begin{array}{cccccc}
  &{\bf I}_{2}{\bf x}_{B}&+&\overline{\A}_{N}{\bf x}_{N}
&=&\overline{{\bf b}}\\
\hline
z&                       &-&\overline{\bf c}_{N}{\bf x}_{N}&=&\overline{v}
\end{array}
\]
where $B=(4,2)$, and $N=(1,3)$,
\[
{\bf I}_{2}=\left(\begin{array}{rr}
1&0\\
0&1 \end{array}\right) ,~~~
{\bf x}_{B}=\left(\begin{array}{c}
x_{4}\\x_{2}\end{array}\right),~~~
\overline{\A}_{N}=\left(\begin{array}{rr}
2&-4\\
3&2 \end{array}\right) ,~~~
{\bf x}_{N}=\left(\begin{array}{c}
x_{1}\\x_{3}\end{array}\right),~~~
\overline{\bf b}=\left(\begin{array}{r}
5\\3\end{array}\right)
\]
and
$$\overline{\bf c}_{N}=(4,-5),~~~\overline{v}=6$$
Because ${\bf I}_{2}{\bf x}_{B}={\bf x}_{B}$, this system may be
represented simply, as
\[\begin{array}{cccccc}
  &{\bf x}_{B}&+&\overline{\A}_{N}{\bf x}_{N}   &=&\overline{\bf b}\\
\hline
z&                       &-&\overline{\bf c}_{N}{\bf x}_{N}&=&\overline{v}
\end{array}
\]
By rearranging terms, we may also represent the system as
\[\begin{array}{ccccc}
  {\bf x}_{B}&=&\overline{\bf b}&-&\overline{\A}_{N}{\bf x}_{N}\\
\hline
            z&=& \overline{v}              &+&\overline{\bf c}_{N}{\bf x}_{N}
\end{array}
\]



\section{Dictionaries}
\begin{thm}
\underline{Definition}: Let $B=(j_{1}, j_{2},..., j_{m})$ be an ordered
index set. Then,
a system of equations of the form
\[D:\left\{\begin{array}{rcl}
x_{i}&=&\overline{b}_{i}-\sum_{j\not\in
B}\overline{a}_{ij}x_{j}~~\mbox{for}~~~j_{1}\leq i\leq j_{m}\\
\hline
z&=&\overline{v}+\sum_{j\not\in B}\overline{c}_{j}x_{j}
\end{array}\right.
\]
is called a {\bf dictionary} with respect to $B$.
\end{thm}

(In matrix notation, $D$ may be represented as
\[\begin{array}{ccccc}
  {\bf x}_{B}&=&\overline{\bf b}&-&\overline{\A}_{N}{\bf x}_{N}\\
\hline
            z&=& \overline{v}              &+&\overline{\bf c}_{N}{\bf x}_{N}
\end{array}
\]
The system
\[\begin{array}{cccccc}
  &{\bf x}_{B}&+&\overline{\A}_{N}{\bf x}_{N}   &=&\overline{\bf b}\\
\hline
z&                       &-&\overline{\bf c}_{N}{\bf x}_{N}&=&\overline{v}
\end{array}\label{diceq}
\]
obtained by rearranging the terms in $D$ is a {\bf tableau} with respect to
$B$.)

The variables
$x_{i},~i\in B$ are referred to as the basic variables, and the variables
$x_{j},~j\not\in B$ as the non-basic variables. The reason for this
nomenclature is the
following:

\begin{thm} \underline{Theorem}: If a dictionary $D$ with respect to $B$ is
equivalent
to  the system of linear equations representing an LP
$$\max {\bf cx}~~{\bf Ax}={\bf b},~{\bf x}\geq{\bf 0},$$
then $B$ must be a basis of ${\bf Ax}={\bf b}$.
\end{thm}

\noindent
{\bf Proof:} When we set ${\bf x}_{N}={\bf 0}$ in $D$, we obtain the unique
solution
${\bf x}_{B}=\overline{\bf b}$, ${\bf x}_{N}={\bf 0}$, and $z=\overline{v}$.
Thus, if $D$ is equivalent to
the system of equations representing the LP,  ${\bf x}_{B}=\overline{\bf
b}$, ${\bf
x}_{N}={\bf 0}$ must be the unique solution to the system ${\bf Ax}={\bf
b}$ when we set
${\bf x}_{N}={\bf 0}$. This, in turn, means that ${\bf x}_{B}=\overline{\bf
b}$ must be
the unique solution to the system
${\A}_{B}{\bf x}_{B}={\bf b}$. But this is possible only if $B$ is a basis
of ${\bf
Ax}={\bf b}$.\qed

\begin{thm} \underline{Definitions}:
In view of the above theorem, we refer to the index set  $B$ as a basis,
and  the
variables  $x_{i},~i\in B$ as the {\bf basic variables}, and the variables
$x_{j},~j\not\in B$ as the {\bf non-basic variables} in  $D$, and the
solution  ${\bf x}_{B}=\overline{\bf b}$, ${\bf x}_{N}={\bf 0}$ as the {\bf
basic
solution} associated with $D$.

A dictionary $D$ is  {\bf feasible}\footnote{In order
to apply the simplex method to solve an LP, we must have a feasible
dictionary equivalent
to the given LP as the input. In fact, all the dictionaries encountered
during the
course of an application of  the simplex method are feasible; the pivot
rules are
designed to maintain feasibility.  (Note that, if a feasible dictionary is
available, the
question of infeasibility does not arise.)} if
$\overline{\bf b}\geq{\bf 0}$.

A dictionary $D$ satisfies the optimality condition if
 $\overline{\bf c}_{N}\leq{\bf 0}$.

A feasible dictionary $D$ which satisfies the optimality condition is an {\bf
optimal} dictionary. (In this case, the basic feasible solution associated with
the dictionary is an optimal solution for the LP.)
\end{thm}



The converse of the above theorem is also true. That is, given any ordered
basis $B$ of
$\A$,  there is a dictionary $D$ with respect to $B$ that is equivalent to
the system of
equations representing the LP. Such a dictionary can be obtained using algebraic
operations. This derivation will be discussed in the next section. We
conclude this
section with the following important theorem.

\begin{thm} \underline{Theorem}: If $D$ and $D'$ are two equivalent
dictionaries with
respect to the same ordered basis $B$, then  $D$ and $D'$ are
identical.\label{uniqueness}
\end{thm}
(A proof of this theorem appears on page 33 of the textbook.)




\section{The dictionary corresponding to an ordered basis}

\begin{thm} \underline{Theorem:}
Consider an LP of the form:
$$\max~{\bf cx},~\mbox{s.t.}~{\bf Ax}={\bf b}, {\bf x}\geq 0.$$
in which the  rank of $\A$ is $m$, and let $B$ be an ordered basis of ${\bf
Ax}={\bf
b}$. Then there is a unique
dictionary with respect to  $B$ which is equivalent to the system of equations
associated with the LP.
\end{thm}

The required dictionary can be obtained by performing elementary row
operations on the
system of equations corresponding to the LP, or equivalently, by suitable matrix
operations. First, we shall illustrate the former method by considering the
LP in
example (\ref{example1}). We shall then establish the validity of the theorem in
general by describing the algebraic procedure in terms of matrices.

\begin{thm}\underline{Example:} Consider the following system of equations
associated
with the LP in example (\ref{example1}):
\end{thm}
\[\begin{array}{crcrcrcrcr}
&3x_{1}&-&6x_{2}&+&3x_{3}&+&6x_{4}&=&12\\
&4x_{1}&+& x_{2}&+&5x_{3}&+&10x_{4}&=&25\\
\hline
z+&7x_{1}&-&5x_{2}&+&10x_{3}&+&19x_{4}&=&0\\
\end{array}
\]
To obtain the tableau with respect to the basis $(1,2)$, we must transform the
equations so that $x_{1}$ appears with coefficient $1$ in the first equation, and with
coefficient $0$ in the other equations, and $x_{2}$ appears with
coefficient $1$ in the
second equation, and with coefficient $0$ in the other equations. To
achieve this,
first let us divide the first equation by $3$, the coefficient of $x_{1}$
in the first
equation, and then subtract suitable multiples of the first equation from
the other
equations to eliminate $x_{1}$ from them. (We say that we are {\bf
pivoting} on the
coefficient of
$x_{1}$ in equation 1.) This gives us the following system:

\[\begin{array}{crcrcrcrcr}
&x_{1}&-&2x_{2}&+& x_{3}&+&2x_{4}&=&4\\
&     & &9x_{2}&+& x_{3}&+&2x_{4}&=&9\\
\hline
z &   & &9x_{2}&+&3x_{3}&+&5x_{4}&=&-28\\
\end{array}
\]
Now devide the second equation by $9$, the coefficient of $x_{2}$ in the second
equation, and then subtract suitable multiples of the first equation from
the other
equations to eliminate $x_{2}$ from them. (That is, pivot on the coefficient of
$x_{2}$ in the second equation.)  This gives us the following system:

\[\begin{array}{crcrcrcrcr}
&x_{1}& &      &+&\frac{11}{9}x_{3}&+&\frac{22}{9}x_{4}&=&6\\
&     & & x_{2}&+&\frac{1 }{9}x_{3}&+&\frac{2}{9}x_{4}&=&1\\
\hline
z &   & &      &+&2x_{3}&+&3x_{4}&=&-37\\
\end{array}
\]
To obtain the dictionary, it is a simply a matter of rearranging terms:

\[\begin{array}{crcrcrc}
x_{1}      &=&6   &-&\frac{11}{9}x_{3}&-&\frac{22}{9}x_{4}\\
x_{2}      &=&1   &-&\frac{1 }{9}x_{3}&-&\frac{2}{9}x_{4}\\
\hline
z          &=&-37 &-&2x_{3}&-&3x_{4}\\
\end{array}
\]\qed

This procedure can be described in general, using matrix algebra. (Remember that
performing any sequence of elementary row operations on a matrix amounts to
premultiplying the matrix by a suitable non-singular matrix.)

By grouping variables according to whether
or not they are basic, we may rewrite the system $\A{\bf x}={\bf b}$ as follows:
$$\A_{B}{\bf x}_{B}+\A_{N}{\bf x}_{N}={\bf b}$$
Now since the basis matrix $\A_{B}$ is invertible, $\A^{-1}_{B}$ exists.
Multiplying
both sides of the above equation by $\A^{-1}_{B}$, we obtain:
\begin{eqnarray*}
\A^{-1}_{B}\A_{B}{\bf x}_{B}+\A^{-1}_{B}\A_{N}{\bf x}_{N}&=&\A^{-1}_{B}{\bf
b}~~\mbox{or,}\nonumber \\
{\bf x}_{B}+\A^{-1}_{B}\A_{N}{\bf x}_{N}&=&\A^{-1}_{B}{\bf b}
\end{eqnarray*}
Note that in the  above system, which is equivalent to the given system
${\bf Ax}={\bf
b}$, each basic variable appears  precisely in one equation, and where it
does, it
appears with coefficient $1$. Thus, we may solve for  each of the $m$ basic
variables in
terms of the $n-m$ non-basic variables.  In matrix notation, the
relationship between
the basic variables (${\bf x}_{B}$) and non-basic variables (${\bf x}_{N}$)
is obtained
by rearranging the terms in the above matrix equation:
\begin{eqnarray*}
{\bf x}_{B}&=&\A^{-1}_{B}{\bf b}-\A^{-1}_{B}\A_{N}{\bf x}_{N}
\end{eqnarray*}
This equation describes, in matrix notation, the set of solutions of the system
${\bf Ax}={\bf b}$ in terms of ${\bf x}_{N}$.

The above equation represents, in matrix notation, the first $m$ rows of the
dictionary corresponding to the basis $B$. To obtain the last row, we must
express
the objective function $z={\bf cx}$ in terms of the non-basic variables. This is
simply a matter of substitution:
\begin{eqnarray}
z&=&{\bf cx}\nonumber\\
 &=&{\bf c}_{B}{\bf x}_{B}+{\bf c}_{N}{\bf x}_{N}\nonumber\\
 &=&{\bf c}_{B}(\A^{-1}_{B}{\bf b}-\A^{-1}_{B}\A_{N}{\bf x}_{N})+{\bf c}_{N}{\bf
x}_{N}\nonumber\\
 &=& {\bf c}_{B}\A^{-1}_{B}{\bf b}+({\bf c}_{N}-{\bf
c}_{B}\A^{-1}_{B}\A_{N}){\bf x}_{N}
\end{eqnarray}
By writing equation (2)  underneath equation (1), we obtain the dictionary
corresponding to the basis $B$:
\[
\left.\begin{array}{rcrcl}
{\bf x}_{B}&=&\A^{-1}_{B}{\bf b}&-&\A^{-1}_{B}\A_{N}{\bf x}_{N}\\
\hline
z&=&{\bf c}_{B}\A^{-1}_{B}{\bf b}&+&({\bf c}_{N}-{\bf
c}_{B}\A^{-1}_{B}\A_{N}){\bf x}_{N}
\end{array}\right\}
\]

Thus, for any given basis $B$, the dictionary corresponding to the basis
$B$ can be
computed directly from the original data using the above
procedure\footnote{There is
a slick way of describing the above computations as follows: We can obtain the
augmented coefficient matrix of the tableau corresponding to $B$,  by
premultiplying
 (\ref{syseq}) by a non-singular matrix as below:

 \[\left(\begin{array}{c|c}
 {\A}_{B}^{-1}&{\bf 0}\\
 \hline
 {\bf c}_{B}{\A}_{B}^{-1}&1
 \end{array}\right)\left(\begin{array}{c|c|c|c}
{\bf 0}&{\A}_{B}&{\A}_{N}&{\bf b}\\
\hline
1&-{\bf c}_{B}&-{\bf c}_{N}&0
\end{array}\right)=\left(\begin{array}{c|c|c|c}
{\bf 0}&{\bf I}&{\A}_{B}^{-1}{\A}_{N}&{\A}_{B}^{-1}{\bf b}\\
\hline
1&{\bf 0}&-{\bf c}_{N}+{\bf c}_{B}{\A}_{B}^{-1}{\A}_{N}&{\bf
c}_{B}{\A}_{B}^{-1}{\bf b}
\end{array}\right)
 \] }.

This material is covered in the seventh chapter of the textbook. We shall
return to the
matrix formulation of dictionaries later on.

As a result of the above discussion, we have:

\begin{thm}\underline{Theorem:} There is a one-to-one
correspondence between ordered bases  and dictionaries.
\end{thm}

However, different orderings of
the same basis give rise to the same basic solution\footnote{The
correspondence between
bases and basic solutions is not one-to-one. Corresponding to each basis,
there is a
unique vector that is its basic solution, but the same vector may be the
basic solution
corresponding to different bases. An example is given in the next section}.




\section{Basic Solutions}

Consider an LP of the form
$$\max z={\bf cx},~~\mbox{s.t.}~~{\bf Ax}={\bf b},~~{\bf x}\geq{\bf 0}$$
with\footnote{This assumption is mainly for the sake of simplifying the
presentation.
With minor adjustments, we can make all the definitions in this section
work for any
equality LP.} rank($\A$)=$m$ = number of rows of
$\A$.

Let $B$ be any basis of the system ${\bf Ax}={\bf b}$.
We have seen that a solution to the system
can be obtained by arbitrarily assigning
values to the non-basic variables $\{ x_{j} : j \not\in B \}$.
In particular we may assign the value zero to each of the non-basic variables.
The values of basic variables are then uniquely determined.
The solution thus obtained is called the  {\bf basic solution} corresponding
to the basis $B$. (Note that the ordering of elements of $B$ is irrelevent
for this
definition.)

If we know the dictionary associated with $B$ (with any ordering of $B$),
we may read
the basic solution corresponding to $B$ from the dictionary. For example, if the
dictionary is $D$ is
\[\begin{array}{rcl}
x_{i}&=&\overline{b}_{i}-\sum_{j\not\in
B}\overline{a}_{ij}x_{j}~~\mbox{for}~~~i\in B,\\
\hline
z&=&\overline{v}+\sum_{j\not\in B}\overline{c}_{j}x_{j}.
\end{array}
\]
Then, $x_{i}=\overline{b}_{i}$, for $i\in B$, $x_{j}=0$, for $j\not \in B$
is the basic
solution corresponding to $B$.


A non-negative basic solution is called a {\bf basic feasible solution}.
(This is often
abbreviated as {\bf bfs}.) We shall call a basis {\bf feasible} if the
corresponding basic
solution is feasible, and we shall refer to the basis
corresponding to an optimal basic feasible solution as an {\bf optimal
basis}\footnote{There is a practical meaning of an  optimal basis. In a
manufacturing
problem, we typically have the option to make a number ($n$) of products.
The fact
the the optimal solution obtained by the simplex method is a basic solution
tells us
that, in order to maximize profit, it suffices to produce a selection of
$m$ of the
products (those corresponding to the basic variables).}.



\noindent
{\bf Example:}  Consider the following system of equations
\[ \begin{array}{rrcrcr}
x_{1} &       & - & 3x_{3} & = &-3 \\
      & x_{2} & + & 4x_{3} & = & 5
\end{array} \]
The following list shows various types of solutions:

\begin{itemize}
\item
($1,-\frac{1}{3},\frac{4}{3})$  is  a solution but is not feasible,
\item
$(\frac{1}{4},\frac{2}{3},\frac{13}{12})$ is a feasible solution but not a basic
solution,
\item
$(-3,5,0)$ is a basic solution but is not a bfs,
\item
$(0,1,1)$ is a bfs,
\item
$(\frac{3}{4},0,\frac{5}{4})$ is a bfs.
\end{itemize}


The following theorem is a characterization of basic feasible solutions.
\begin{thm} \underline{Theorem:}
A feasible solution is a basic feasible solution if and only if the columns
of $\A$
corresponding to variables with positive value in the solution constitute a
linearly
independent set.\label{chofbafs}
\end{thm}

\noindent
{\bf Proof.}  Suppose that ${\bf s} = (s_{1}, s_{2}, \ldots , s_{n})$ is a basic
feasible solution
corresponding to a basis $B$.
Then the only $s_{i}$ that can be positive have their subscripts in $B$.
By  definition, any subset of columns whose  subscripts are in $B$ is linearly
independent. This proves the ``only if'' part.

Conversely, suppose that ${\bf s} = (s_{1}, s_{2}, \ldots , s_{n})$ is a
feasible
solution which
satisfies the given condition.
Suppose that $I$ is the index set such that $s_{i} > 0$ for all $i \in I$
and $s_{j} = 0$ for
all $j \not\in I$.
By the hypothesis $\{A_{i} : i \in I \}$ is linearly independent.
This linearly independent set is contained in subset of columns of $\A$
which constitutes
a basis for the column space of $\A$. Let $\{ A_{i}: i \in B \}$ be such a
basis.
Since $B \supseteq I, ~ s_{j} = 0$ for all $j \not\in B$. It follows that
${\bf s}$ is
the basic solution corresponding to $B$.\qed

\begin{thm}
\underline{Example:}  Consider the following system of linear equations
\end{thm}
\[ \begin{array}{rrrcrcrcrcrcr}
x_{1} &       &       & + & x_{4} & + & 2x_{5} & - & 2x_{6} & + & x_{7} & =
& 1 \\
      & x_{2} &       & + & x_{4} & + & 2x_{5} & - & 2x_{6} & + & x_{7} & =
& 1 \\
      &       & x_{3} &   &       & + & x_{5}  & - & 2x_{6} & + & x_{7} & = & 0
\end{array} \]
\begin{itemize}
\item[(a)]
$(0,0,0,0,1,3,5)$ is not a bfs to this system because $\A_{5}, \A_{6}$ and
$\A_{7}$ (the fifth,
sixth and seventh columns of the coefficient matrix) are not linearly
independent.
\item[(b)]
$(1,1,0,0,0,0,0)$ is a bfs because the columns $A_{1}$ and $A_{2}$ are
linearly independent.
$\{A_{1}, A_{2} \}$ can be extended to a basis.
$\{ A_{1}, A_{2}, A_{3} \}$ is one of them.
In fact there are four bases which contain $\{ A_{1}, A_{2} \}$.
\end{itemize}

Two remarks are in order here:
\begin{itemize}
\item[(1)]
The same vector may arise as a bfs corresponding to different bases.
\item[(2)]
A basic variable may assume the value zero in a bfs (if a basic variable
takes the value zero
in a bfs then the solution is a {\bf degenerate} bfs).
\end{itemize}

Both these are exemplified by (b) above.

\vspace{.1in}

The following  theorem brings out the importance of basic feasible
solutions in the theory
of linear programming.

\begin{thm} \underline{Theorem:}
Consider the linear program
\[ \begin{array}{rl}
\mbox{Maximize} & z = {\bf cx} \\
\mbox{subject to} & {\bf Ax} = {\bf b} \\
\mbox{and} & {\bf x} \geq 0. \end{array} \]
(1) If the LP has a feasible solution, then it has a basic feasible solution.

\noindent
(2) If the LP has an optimal  solution then it has an optimal basic
feasible solution.
\end{thm}

These theorems provide a motivation for the simplex method.
It is possible to give simple direct proofs of them, but they do follow
from the fact
that the simplex method works.

\vspace{.2in}
\begin{flushleft}
{\bf  Exercises.}
\end{flushleft}
\begin{enumerate}
 \item[1.]
Show that if $\A$ is an $m\times n$ matrix with rank($\A$)=$m$, then ${\bf
Ax}={\bf b}$
has at most
$n\choose m$ basic feasible solutions.
\item[2.]
Consider the following system
\[ \begin{array}{rcrcrcrcrcrcl}
x_{1}  &   &       &   &       & + & x_{4}  & +  & 2x_{5}  & - & x_{6}  & =
& 1 \\
       & + & x_{2} &   &       & + & 2x_{4} & + & 4x_{5}   & + & 2x_{6} & =
& 2 \\
2x_{1} &   &       & + & x_{3} & + & 3x_{4} & + & 6x_{5}   & + & x_{6}  & = & 3.
\end{array} \]
In each of the following cases verify whether or not the given vector is a
basic feasible
solution to the system
\[ \begin{array}{llcll}
(i) & (1, 2, 1, 0, 0, 0) & ~~~~~~~~~~ & (ii) & (0,0,0, \frac{1}{3},
\frac{1}{3}, 0) \end{array}
\]
\item[3.]
Show that if ${\bf 0}$ is a feasible solution to ${\bf Ax}={\bf b}$ then it
is a basic
feasible solution of ${\bf Ax} = {\bf b},~{\bf x}
\geq {\bf 0}$.
\item[4.]
Show that a non-negative solution ${\bf s}$ to a system ${\bf Ax} = {\bf
b},~{\bf x}
\geq {\bf 0}$ is a bfs if and only if there is a linear function $z={\bf
cx}$ such that
${\bf s}$
 is the unique optimum  solution to the LP
 \[ \begin{array}{rl}
\mbox{Maximize} & z = {\bf cx} \\
\mbox{subject to} & {\bf Ax} = {\bf b} \\
\mbox{and} & {\bf x} \geq {\bf 0}. \end{array} \]
\end{enumerate}

\section{Geometrical Interpretation}
The feasible region of an LP in $n$ variables is a convex polyhedron in $\R
^n$, and the
basic feasible solutions to the LP are the extreme points (corners) of this
polyhedron.
In the simplex method, we start at one extreme point. In each iteration, we
move along
an edge of the polyhedron from the the current extreme point to an  extreme
point adjacent to it.

A subset $K$ of $R^{n}$ is called a {\bf convex set} if for any two points
${\bf x}$ and ${\bf y}$ in $K$,
the whole line segment joining ${\bf x}$ and ${\bf y}$ is entirely in $K$;
that is if
${\bf x},{\bf y} \in K
\Rightarrow \lambda {\bf x} + (1 - \lambda ) {\bf y} \in K$ for all
$\lambda$ such that
$0 \leq \lambda \leq 1$.

\begin{thm}
\underline {Examples:}
\end{thm}
\begin{itemize}
\item[(1)]
The set of all solutions to one linear equation,
$\sum_{j=1}^{n}a_{j}x_{j}=b$, with not all $a_{j}=0$,  is called a {\bf
hyperplane} in
$R^{n}$. (In two-dimensions, hyperplanes are lines, in three-dimensions,
hyperplanes
are planes.) If $\sum_{j=1}^{n}a_{j}x_{j}=b$ is a hyperplane, then the two sets
$$\{ (x_{1}, x_{2}, \ldots , x_{n}) | \displaystyle \sum^{n}_{j=1}
a_{j}x_{j} \geq b \}~~\mbox{and}$$
$$\{ (x_{1}, x_{2}, \ldots , x_{n}) | \displaystyle \sum^{n}_{j=1}
a_{j}x_{j} \leq b \},$$
are called the {\em half-spaces} generated by the hyperplane.

Any hyperplane or a half-space is a convex set.
\item[(2)] The set of points inside a sphere is a convex set.
\end{itemize}
\begin{thm} \underline{Theorem:}
The intersection of a finite number of convex sets is convex.
\end{thm}

\noindent
\begin{thm}
\underline{Definition:} The intersection of a finite number of half-spaces is
called a {\bf convex polyhedron}.
\end{thm}

In an LP, each constraint either defines a hyperplane or a
half-space\footnote{Note
that a hyperplane itself is the intersection of the two half-spaces it
generates.}. Thus, the set of
points satisfying any one constraint is a convex set. The feasible region
of the LP is
the set of all points which satisfy all the constraints. Thus, it is the
intersection
of the convex sets defined by the individual constraints. Hence we have:
\begin{thm} \underline{Theorem:}
The feasible region
of an LP  is a convex polyhedron.
\end{thm}


A point ${\bf x}$ in a convex set $K$ is called an  {\bf extreme point} of
$K$ if
$${\bf x} = \frac{1}{2} {\bf x}_{1} + \frac{1}{2}{\bf x}_{2} ~ \mbox{and} ~
{\bf x}_{1},
{\bf x}_{2} \in K \Longrightarrow {\bf x}_{1}
= {\bf x}_{2} = {\bf x}.$$
In the case of a convex polygon, the extreme points are precisely its
corner points.
Each point on the surface of a closed ball is its extreme points.

\begin{thm} \underline{Theorem:}
A feasible solution to ${\bf Ax}={\bf b},~{\bf x}\geq{\bf 0}$ is an extreme
point of the
feasible region  if, and only if, it is a basic feasible solution.
\end{thm}

\noindent
{\bf Sketch of Proof:}
Let {\bf x} be a basic feasible solution of ${\bf Ax}={\bf b}$.
Assume without loss of generality that {\bf x} corresponds to the ordered
basis $B
= (1, 2, \ldots , m)$.
If ${\bf x}_{1}$ and ${\bf x}_{2}$ are feasible solutions such that ${\bf
x} = \frac{1}{2}
{\bf x}_{1} + \frac{1}{2}
{\bf x}_{2}$ then ${\bf x}_{1}$ and ${\bf x}_{2}$ agree with ${\bf x}$ in
the last $n - m$
co-ordinates. It follows (exercise) that ${\bf x}_{1} = {\bf x}_{2} = {\bf x}$.
Hence ${\bf x}$ is an extreme point of the set of feasible solutions to
${\bf Ax}={\bf
b},~{\bf x}\geq{\bf 0}.$

Conversely suppose that ${\bf s}$ is an extreme point of the set of feasible
solutions to ${\bf Ax}={\bf b}$.
Assume without loss of generality taht the first $p$ co-ordinates of $S$
are positive and the
remaining $n-p$ co-ordinates of ${\bf s}$ are zero.
If ${\bf s}$ is not a basic feasible solution, then, by Theorem (\ref{chofbafs}), the
first $p$ columns of $\A$ are
linearly dependent.
Thus, there exist $\lambda_{1}, \lambda_{2}, \ldots , \lambda_{p}$, not all
zero, such that
$$ \displaystyle \sum^{p}_{j=1} \lambda_{j} A_{j} = 0.$$
Let ${\bf \lambda}$ denote the $n$-vector $(\lambda_{1}, \lambda_{2}, \ldots ,
\lambda_{p}, 0, \ldots , 0)^t$.
Consider the two vectors
$${\bf x} = {\bf s} + t \lambda$$
and
$${\bf y} = {\bf s} - t \lambda.$$
If $t$ is a positive real number such that
$$ t \leq \mbox{min}_{j} \left\{ \frac{s_{j}}{| \lambda_{j}|},
\lambda_{j} \neq 0
\right\}$$
then both ${\bf x}$ and ${\bf y}$ are feasible solutions (exercise), and
$${\bf s} = \frac{1}{2}{\bf x} + \frac{1}{2}{\bf y}.$$
This contradicts the assumption that ${\bf s}$ is an extreme point of the convex
set of feasible solutions.
Hence ${\bf s}$ is a basic feasible solution. \qed

\vspace{.2in}

Suppose that we have an  LP $\mbox{max}~z = {\bf cx}$ s.t. ${\bf Ax}={\bf
b},~{\bf
x}\geq{\bf 0}$, with rank $\A$ = $m$ = the number of rows of $\A$. If $B$
is a feasible
basis, the basic feasible solution corresponding to $B$ is the unique
solution to the
system
\begin{equation}
\begin{array}{rcl}
{\A}_{B}{\bf x}_{B}&=&{\bf b},\\
{\bf x}_{N}&=&{\bf 0}
\end{array}\label{edge1}
\end{equation}
of $n$ equations in $n$ variables. Suppose that the current bfs is not optimal
and  suppose that a variable
$x_{s}$ is chosen as the entering variable. To determine the leaving
variable, we
consider  the system of equations
\begin{equation}
\begin{array}{rcl}{\A}_{B}{\bf x}_{B}&=&{\bf b}-x_{s}{\A}_{s},\\
{\bf x}_{N-s}&=&{\bf 0}.
\end{array}\label{edge}
\end{equation}
When $x_{s}=0$, the solution to this system is the current bfs. Let us denote
by $L$ the set of all non-negative solutions to (\ref{edge}). It may be the
case that
$L$ is just a singleton consisting of the current bfs\footnote{This happens in
case of degeneracy.}. For clarity, let us consider the case in
which there are points in
$L$ at which  $x_{s}$ takes positive values. Then $L$  is an `edge' of the
polyhedron (see exercise 4).  Moving along this edge, away from the current
bfs, results in an increase in the value of the objective function. If, for all
non-negative values of
$x_{s}$, (\ref{edge}) has feasible solutions, then the LP is unbounded. If not,
there is a maximum value of $x_{s}$.  A basic variable $x_{r}$ that becomes
zero when $x_{s}$ is given this maximum possible value  is chosen as the leaving
variable. The new basis is $B'=B-\{r\}\cup \{s\}$  (and $N'=N-\{s\}\cup \{r\}$).
We move to the basic feasible solution which is the unique solution to the
system
\begin{equation}
\begin{array}{rcl}
{\A}_{B'}{\bf x}_{B'}&=&{\bf b},\\
{\bf x}_{N'}&=&{\bf 0}
\end{array}\label{edge2}
\end{equation}
In this case $L$ is the edge of the feasible region joining the two extreme
points which are the basic feasible solutions corresponding to $B$ and $B'$,
respectively\footnote{In case of a degenerate pivot, the two systems
(\ref{edge1}) and
(\ref{edge2}) have the same solution.}.


\begin{flushleft}
{\bf  Exercises.}
\end{flushleft}
\begin{enumerate}
\item[1.]
Show that the vectors ${\bf x}$ and ${\bf y}$ defined in the proof of
theorem 6 are
feasible solutions to
${\bf Ax}={\bf b},~{\bf x}\geq{\bf 0}$ if $0 < t \leq \mbox{min}_{j} \left\{
\frac{s_{j}}{|
\lambda_{j}|}, \lambda_{j} \neq
0 \right\}$.
\item[2.]
Consider the LP:
\[
\begin{array}{lrcrcrcr}
\mbox{max }~z=& 6x_{1}&+& 4x_{2} &+& 2x_{3}&      &   \\
\mbox{s.t. }& 2x_{1}&+&  x_{2} &+&  x_{3}& \leq & 4  \\
            & 4x_{1}&+& 2x_{2} &+& 2x_{3}& \leq & 12 \\
            &3x_{1} &+& \frac{5}{2}x_{2} &+& 2x_{3}& \leq & 8  \\
            &x_{1}  &,&   x_{2}&,&  x_{3}& \geq & 0
\end{array}
\]
Determine the polyhedron of feasible solutions to this LP. What are the extreme
points of this polyhedron?

\item[3.]
A hyperplane $H$ defined by $\sum c_{i}x_{i} = c$ is called a {\bf
supporting hyperplane} of a
convex set $K$ if (i) $H \cap K \neq \emptyset$ and (ii) $K$ lies in one
closed half-space
generated by $H$.

Consider the LP $\mbox{max}~z = {\bf cx}$ s.t. ${\bf Ax}={\bf b},~{\bf x}\geq{\bf 0}$.
Let
$v^{\ast}$ be the optimal value of $z$. Show that the hyperplane defined by
${\bf cx} =
v^{\ast}$ is a supporting hyperplane to the convex
set of feasible solutions to the LP.

\item[4.]
(a) Show that, in case of non-degeneracy, the set $L$ of feasible solutions to
(\ref{edge}) is indeed an edge of the polyhedron of feasible solutions.
(Firstly show
that $L$ is $1$-dimensional. Then show that if ${\bf x}$ is on $L$,
 and  ${\bf x}_{1}$ and ${\bf x}_{2}$
are feasible solutions to the LP such that ${\bf x}=\frac{1}{2}{\bf
x}_{1}+\frac{1}{2}{\bf x}_{2}$, then ${\bf x}_{1}$ and ${\bf x}_{2}$ are also
on $L$.

(b) Describe  $L$ parametrically in terms of $x_{s}$.


\item[5$^{\ast}$.]
If ${\bf x}_{1}$, ${\bf x}_{2}$,...,${\bf x}_{k}$,  are $k$ vectors in $\R^n$,
${\lambda}_{1}$, ${\lambda}_{2}$,...,${\lambda}_{k}$ are real numbers such that
$0\leq {\lambda_{i}}\leq 1$, for $1\leq i\leq k$, and
$\sum_{i=1}^{k}\lambda_{i}=1$,
then $\sum_{i=1}^{k}\lambda_{i}{\bf x}_{i}$ is called a {\bf convex linear
combination}  of ${\bf x}_{1}$, ${\bf x}_{2}$,...,${\bf x}_{k}$. Show that
a convex
set is closed under the operation of taking convex linear combinations.
(For example,
show that if $K$ is a convex set, and ${\bf x}_{1}$, ${\bf x}_{2}$,${\bf x}_{3}$
belong to $K$, then $\frac{1}{3}{\bf x}_{1}+\frac{1}{3}{\bf
x}_{2}+\frac{1}{3}{\bf x}_{3}$  also belongs to $K$.)


\end{enumerate}







\end{document}





--========================_24179756==_--


