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

%\title{C and O 350}
%\author{(27 October, 1994)}
%\date{}
%\maketitle

\pagestyle{headings}
\begin{center}
C \& O 350 \hspace{1in} {\bf MATRIX FORMULAS} \hspace{1in} 
\end{center}

Consider an LP in standard form:
\[
\begin{array}{lrclcl}
\mbox{Maximize}   & \sum_{j=1}^{n}c_{j}x_{j} &     &     &  & \\
\mbox{subject to} & \sum_{j=1}^{n}a_{ij}x_{j}&\leq &b_{i}&  &(i=1,2,\cdots,m)\\
                  &                     x_{j}&\geq &0    &
&(j=1,2,\cdots,n)
\end{array}
\]
After the introduction of slack variables, the LP becomes:
\[
\begin{array}{llcclcl}
\mbox{Maximize}   & \sum_{j=1}^{n}c_{j}x_{j} &&     &     &  & \\
\mbox{subject to} & \sum_{j=1}^{n}a_{ij}x_{j}&+x_{n+i}&=&b_{i}&
&(i=1,2,\cdots,m)\\
                  & &                    x_{j}&\geq &0    &
&(i=1,2,\cdots,n+m)
\end{array}\]
In this form, all constraints of the LP (apart from non-negativity of the
variables) are equations, and the LP can be expressed 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}
\]
Here $\A$ is an  $m$ by $n+m$ matrix, the vector ${\bf c}$
is a $1$ by $n+m$ row vector, ${\bf b}$ is an $m$ by $1$ column vector, and
${\bf x}$
is an $n+m$ by $1$ column vector, as shown below:
\[\A=\left(\begin{array}{cccccccc}
a_{11} &a_{12} &...&a_{1n}~~&1~~~&0~&...&0\\
a_{21} &a_{22} &...&a_{2n}&0~~&1~&...&0\\
.&&&.&&&&\\
.&&&.&&&&\\
.&&&.&&&&\\
a_{m1} &a_{m2} &...&a_{mn}&0~~&0~&...&1
\end{array}\right)~\mbox{and }~b~=\left( \begin{array}{c}
b_{1}\\
b_{2}\\
.\\
.\\
.\\
b_{m}
\end{array}\right)\]
\[\begin{array}{llllllcccccc}
{\bf c}
&=&(c_{1},&~~c_{2},&...&~c_{n},&0      &&...&0)\hspace{1.5in}\\
{\bf x}^{t}
&=&(x_{1},&~~x_{2},&...&~x_{n},&x_{n+1}&&...&x_{n+m})\hspace{1.5in}
\end{array}
\]
(Note that ${\bf x}$ is a column vector; the vector ${\bf x}^{t}$ displayed
above
is its transpose.)

There are matrix formulas by means of which we can express any dictionary
in terms
of the given data ($\A$, ${\bf b}$, and ${\bf c}$). The following notation and
definitions are important for describing those formulas.


\noindent
\underline{NOTATION:} Let ${\A}_{j}$ denote the $jth$ column of the matrix
${\A}$.
For any subset
$J$ of the column index set $\{1,2,...,n+m\}$, we shall let ${\A}_{J}$
denote the
submatrix of consisting of the columns with their indices in $J$.


\noindent
\underline{Definition:} An $m$-element subset  $B$ of the column index set
$\{1,2,...,n+m\}$ is called a {\em 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.


If $B$ is a basis, the variables with subscripts in the set are {\em basic
variables} with respect $B$, and the remaining  variables, i.e. those  with
subscripts not in $B$ are the {\em non-basic variables}.  For convenience,
we shall denote the complement
of $B$, i.e. the set of subscripts of non-basic variables, by $N$.

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 columns with
subscripts in $N$.

By grouping variables according to whether or not they are basic, we rewrite the
system $\A{\bf x}={\bf b}$ as follows:
$$\A_{B}{\bf x}_{B}+\A_{N}{\bf x}_{N}={\bf b}$$
Now since $\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*}
Now by rearranging terms in the above equation, we can express the basic
variables (${\bf x}_{B}$) in terms of the non-basic variables (${\bf x}_{N}$):
\begin{eqnarray}
{\bf x}_{B}&=&\A^{-1}_{B}{\bf b}-\A^{-1}_{B}\A_{N}{\bf x}_{N}
\end{eqnarray}
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 formulas. Before giving
examples, let us restate the  formulas in simpler notation. First of all, if
$B$ is a basis, we shall refer to the matrix $\A^{-1}_{B}$ as the {\em basis
matrix}\footnote{Note that the basis matrix depends on the basis under
consideration, but it is a submatrix of  $\A$.} corresponding to the basis
$B$, and denote it simply by
${\bf B}$ (in bold face). Also, since the product
${\bf c}_{B}{\bf B}^{-1}={\bf c}_{B}\A^{-1}_{B}$ appears repeatedly in the
formulas
let us simply write ${\bf y}$ for the expression  ${\bf c}_{B}{\bf
B}^{-1}$. (The
reason for the choice of the letter ${\bf y}$ is because of the relavance to the
dual. See exercise 4.) With this notation, the above
information can be summarized as below: Firstly, the dictionary corresponding to
the basis $B$ is as follows:

\[
\left.\begin{array}{rcrcl}
{\bf x}_{B}&=&{\bf B}^{-1}{\bf b}&-&{\bf B}^{-1}\A_{N}{\bf x}_{N}\\
\hline
z&=&{\bf y}{\bf b}&+&({\bf c}_{N}-{\bf y}\A_{N}){\bf x}_{N}
\end{array}\right\}
\]
(where, to repeat, ${\bf B}$ is the basis matrix $\A^{-1}_{B}$, and ${\bf
y}={\bf c}_{B}{\bf B}^{-1}$.)

We previously denoted the dictionary corresponding to a basis $B$ as follows:

\[
\begin{array}{rcrcl}
x_{i}&=&\overline{b}_{i}&-&\displaystyle\sum_{j\in N}
\overline{a}_{ij}x_{j},~~\mbox{for}~i\in B\\
\hline
z&=&\overline{z}&+&\displaystyle\sum_{j\in N} \overline{c}_{j}x_{j}
\end{array}
\]
where $\overline{b}_{i}$ is the value of the  basic variable $x_{i}~$,
$\overline{z}$
is the value of the objective function at the basic solution associated
with the basis
(obtained by setting the values of the non-basic variables equal to zero),
$\overline{c}_{j}$ is the coefficient of $x_{j}$ (referred to as the
`reduced cost'
coefficient of $x_{j}$). (In general, the entries of the dictionary
corresponding
to a basis $B$ are indicated by an overline; those without the overline indicate
the original data.)
In view of the above derivation of the dictionary corresponding to $B$, we
have the
following relationships:
\[
\begin{array}{lcl}
\overline{b}&=&{\bf B}^{-1}{\bf b}\\
\overline{\A}&=&{\bf B}^{-1}{\A}~~~(\overline{\A}_{j}={\bf B}^{-1}{\A}_{j})\\
\overline{z}&=&{\bf y}{\bf b}~~~\mbox{and,}\\
\overline{{\bf c}}&=&{\bf c}-{\bf y}\A~~(\overline{c}_{j}=c_{j}-{\bf
y}{\A}_{j})
\end{array}
\]

Dictionaries are convenient for understanding the way the simplex method
works. But to visualize the above relationships, tableaux are more convenient.
Note that a tableau simply consists of the constraint equations written without
rearranging terms, followed by the equation representing the objective
function:
(The tableau to the left is the initial tableau, and the tableau to the
right is a
subsequent tableau. Note that the number in the lower right-hand corner
represents
the negative of the value of the objective function at the corresponding basic
solution.)
\[
\left.\begin{array}{cccc}
&\sum a_{ij}x_{j}&=&b_{i}\\
\hline
-z+&\sum c_{j}x_{j}&=&0
\end{array}\right\}
~~~\Rightarrow~~~
\begin{array}{cccc}
&\sum \overline{a}_{ij}x_{j}&=&\overline{b}_{i}\\
\hline
-z+&\sum \overline{c}_{j}x_{j}&=&-\overline{z}
\end{array}
\]
The relationships stated above can be displayed in tableau format (just
using the
coefficients) as follows:

\vspace{2in}

Let us emphasise that there is a one-to-one correpondence between bases  and
dictionaries. We shall call a basis {\em feasible}, if the  the
correponding basic
solution is feasible (i.e. non-negative), and we shall refer to the basis
corresponding to an optimal basic feasible solution as an {\em 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).}.


Whenever a basis is specified, we can derive the
corresponding dictionary using the above formulas\footnote{Important
Remark: All the above defintions and formulas are valid for any LP
of the form $\max {\bf cx}:~\mbox{s.t.}~{\bf Ax}={\bf b},~{\bf x}\geq {\bf 0}$,
provided that the rank of the matrix ${\bf A}$ is $m$. It is not necessary
for the
LP to have been obtained from  an LP in standard form by adding slack
variables.}.
There are situations when  we might wish to compute the dictionary
corresponding to a specified basis directly from the given data. For example, we
might, for verification purposes,  wish to reconstruct the final dictionary
(corresponding to the optimal solution) without going through all the
intermediate
dictionaries. Another situation involves sensitivity analysis: after an LP
has been
solved, we are told that some numbers in the data need to be modified
slightly. In
order to decide if the basis which is optimal with the old data remains
optimal after
changes, it is not necessary to solve the revised problem from scratch: we
can use
the matrix formulas.

\vspace{.1in}
\noindent
\underline{EXERCISES:}

\begin{enumerate}
\item
Consider the following LP (obtained from an LP in standard form by adding
the slack
variables $x_{4}$, and $x_{5}$):
\[\begin{array}{lrcrcrcrcrcrcr}
\mbox{max } &x_{1}&+& 4x_{2} &+&3x_{3}& &&&&     &   \\
\mbox{s.t. }&  x_{1}&+&  x_{2} &+& 2x_{3}&+&x_{4}& & &= & 5  \\
            & 2x_{1}&+&  x_{2} &+&  4x_{3}& &&+&x_{5}&= & 7 \\
            & x_{1} &,&  x_{2} &,&  x_{3}&,&x_{4}&,&x_{5}& \geq & 0
\end{array}\]

(a)  For the basis $\{1,2\}$, using the matrix formulas, compute  the
following:

\begin{enumerate}
\item [(i)]
The values of the basic variables in the corresponding basic
solution (i.e $\overline{b}$),
\item [(ii)]
${\bf y}$,
\item [(iii)]
the value of the objective function at the corresponding basic solution, and
\item [(iv)]
the corresponding reduced costs.
\end{enumerate}
Using the above information, decide whether or not $\{1,2\}$ is an optimal
basis.

(b) Do the same for the basis $\{2,3\}$.

\item
For the LP on page 98 ( also  102) of the text, verify, using matrix formulas
that $\{1,3,4\}$ is an optimal basis. Then show that the same basis remains
optimal
if the number of hours of labour available is increased by ten.

\item
Given a basis $B$, we can compute ${\bf B}^{-1}$, the inverse of the basis
matrix,
and ${\bf y}$, and then, using the matrix formulas we can construct the
dictionary
corresponding to the basis $B$. Conversely, given the dictionary
corresponding to
the basis $B$, we can find ${\bf B}^{-1}$ and ${\bf y}$. (${\bf B}^{-1}$ appears
`under' the slack variables, and $y_{i}$ is the negative of the reduced
cost of the
ith slack variable, (more precise explanation will be given in class).)

Consider the final dictionary for example 1 (page 17 of the text). Recover
${\bf B}^{-1}$ and ${\bf y}$.
\item
(a) Write, in matrix notation, the dual of an LP in standard form. (b) Let ${\bf
y}^{\ast}$ denote the ${\bf y}$-vector corresponding to an optimal basis.
Show that
${\bf y}^{\ast}$ is an optimal solution to the dual. (This would be proof of the
duality theorem, stated in matrix notation.)

\end{enumerate}
















\end{document}




