\documentstyle[11pt]{article}
\oddsidemargin 0.0in
\evensidemargin 0.0in
\textwidth 6.5in
\addtolength{\topmargin}{-1in}
\addtolength{\textheight}{2in}
\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}
\pagestyle{headings}
\underline{{\bf C\& O 350\hspace{1.35in} Assignment 4\hspace{1.35in}Due:
November
14}}

\vspace{.1in}
\noindent
(1) Interpret the complementary slackness conditions in economic terms.

\vspace{.1in}
\noindent
(2) Consider the LP in equality form:
\[\begin{array}{rrcr}
\mbox{maximize} &{\bf cx}& & \\
\mbox{subject to}&{\bf Ax}&=&{\bf b}\\
&{\bf x}&\geq & {\bf 0}
\end{array}
\]
where
\[\A=\left(\begin{array}{rrrrr}
1&2&1&1&0\\
1&4 &1&0&1\end{array}\right)~~~~
{\bf b}=\left(\begin{array}{c}
3\\5\end{array}\right)~~~\mbox{and}
~~{\bf c}=(2,1,1,1,1)\]
\underline{Using matrix formulas}, compute the dictionary corresponding to the
basis $B=(1,2)$.

\vspace{.1in}
\noindent
(3) Consider the inequality 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}
\]

The final dictionary obtained by applying the simplex method to solve this LP is
presented below:  ($x_{4}$, $x_{5}$, and $x_{6}$ represent the slack variables.)

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

For the basis $B=(1,5,2)$, what is the basis matrix $A_{B}~$?
>From the above given dictionary, find

\vspace{.1in}
\noindent
$$(i)~~{\bf A}_{B}^{-1},~~
(ii)~~{\bf y}={\bf c}_{B}{\bf A}_{B}^{-1},~~
(iii)~~\overline{{\bf b}}, ~~ \mbox{and}
~~(iv)~~\overline{v}.$$

\vspace{.1in}
\noindent
(4) Do problem 7.1 on page 116 of the textbook.


\vspace{.1in}
\noindent
(5) Do problem 8.1 (b) on page 135 of the textbook. (In this problem, $x_{1}$,
and $x_{2}$ are free variables. They can be eliminated as in the example
given in
the text on page 132.)

\vspace{.1in}
\noindent
(6) Do problem 8.1 (e) on page 135 of the textbook. (Use matlab.)

\vspace{.1in}
\noindent
(7) Consider the LP:
$$(P):~~\max z={\bf cx},~~\mbox{s.t.}~~{\bf Ax}={\bf b},$$
where no variable is required to be non-negative. Show that if $(P)$ has an
optimal solution, then,
for all feasible solutions ${\bf x}$ of $(P)$, ${\bf cx}$ is the same.

(HINT: If ${\bf x}_{1}$, and ${\bf x}_{2}$ are any two feasible solutions to
$(P)$,  then, for any $\lambda$, $\lambda{\bf x}_{1}+(1-\lambda ){\bf x}_{2}$
is also a feasible solution to $(P)$, and if the value of $z$ at
${\bf x}_{1}$ is $v_{1}$, and the value of $z$ at
${\bf x}_{2}$ is $v_{2}$, then the value of $z$ at
$\lambda{\bf x}_{1}+(1-\lambda ){\bf x}_{2}$ is
$\lambda{v}_{1}+(1-\lambda ){v}_{2}=v_{2}+\lambda (v_{1}-v_{2})$. If there
are two
different feasible solutions
${\bf x}_{1}$, and ${\bf x}_{2}$ at which the objective function values are
different, show that $(P)$ is unbounded.

Alternatively, note that the dual of $(P)$ is
$(D):~~\min w={\bf yb},~~\mbox{s.t.}~~{\bf yA}={\bf c}.$ Show that if both the
primal and dual are feasible, then, $z$ has the same value at all primal
feasible
solutions.

Can you guess the condition on ${\bf c}$ under which the objective function
value is the same for all feasible solutions?)


\end{document}

