\documentstyle[12pt,fullpage]{article}
\begin{document}

\begin{center}
{\large\bf C\&O 350 \\ 
Assignment 4 
}
\end{center}

\begin{flushleft}
{\large  Due: Friday March 17 (\S 2, \S 3),
          Thursday March 16 (\S 1 )
}
\end{flushleft}

\begin{enumerate}
\item
Consider the following two systems, where $A$ is a given $m \times n$
matrix, and $b$ is a given column $m$-vector:
\begin{enumerate}
\item[(i)] $Ax=b,~x \geq 0,~x \in \Re^n$.
\item[(ii)] $yA \geq 0,~yb<0,~y \in \Re^m$.
\end{enumerate}
\begin{enumerate}
\item[(a)]  Prove that it is not possible for both systems to 
have solutions.
\item[(b)]  Prove that if system (i) does not have a solution
then system (ii) must have a solution.  (Hint:  consider the
linear program:  maximize $0x$ subject to $Ax=b$ and $x \geq 0$.)
\end{enumerate}
\item 
Use complementary slackness to determine whether or not
$(y_1,y_2) = (4,5)$ is an optimal solution of the dual
problem for the linear program
\[ \left\{  \begin{array}{lrcrcrcrcrcl}
\mbox{maximize}   &10x_1&+&24x_2&+&20x_3&+&20x_4&+&25x_5&    &      \\
\mbox{subject to} &  x_1&+& x_2 &+&2x_3 &+&3x_4 &+&5x_5 &\leq& 19,  \\
                  &2x_1 &+&4x_2 &+&3x_3 &+&2x_4 &+& x_5 &\leq& 57,  \\
                  & x_1 &,& x_2 &,& x_3 &,& x_4 &,& x_5 &\geq& 0.
            \end{array} \right.  \]

\item
Use the Revised Simplex Method to solve the problem
\[ \left\{  \begin{array}{lrcrcrcrcrcrcrcrcl} 
\mbox{maximize}   &7x_1 &-&3x_2 & &     &-&4x_4 &+&3x_5 & &     &+& x_7 &+&2x_8 &    &      \\
\mbox{subject to} &     & & x_2 &+&2x_3 &-& x_4 &-&3x_5 & &     &-& x_7 & &     &\leq& 24,  \\
                  & x_1 &+& x_2 &-& x_3 & &     &+&2x_5 &+& x_6 & &     &-& x_8 &\leq& 18,  \\
                  & x_1 &,& x_2 &,& x_3 &,& x_4 &,& x_5 &,& x_6 &,& x_7 &,& x_8 &\geq& 0.
            \end{array} \right.  \]
\item
Consider the linear program
\[ \left\{  \begin{array}{lrcrcrcl}
\mbox{maximize}   &5x_1 &+& 4x_2&+& 3x_3&    &      \\
\mbox{subject to} &2x_1 &+&3x_2 &+& x_3 &\leq&  5,  \\
                  &4x_1 &+& x_2 &+&2x_3 &\leq& 11,  \\
                  &3x_1 &+&4x_2 &+&2x_3 &\leq&  8,  \\
                  & x_1 &,& x_2 &,& x_3 &\geq& 0.
            \end{array} \right.  \]
\begin{enumerate}
\item[(i)]
After introducing slack variables $x_4,x_5,x_6$, verify that the
optimal basis for this problem is $\{x_1,x_3,x_5\}$ by calculating
the corresponding dictionary directly: {\bf do not perform any
pivots}.
\item[(ii)]
Suppose the right-hand-side is changed to $(5,11,7)^T$.  Use
your answer to part (i) to derive an optimal dictionary for the
new problem. (Use the dual simplex method if needed.)
\end{enumerate}

\item
{\bf BONUS QUESTION}\\
Suppose that the following standard form linear program is
feasible and bounded. 
\[  (P)~~~~~\left\{ \begin{array}{lrcl}
\mbox{maximize}   & cx &      &     \\
\mbox{subject to} & Ax & \leq & b,  \\
                  &  x & \geq & 0.
                    \end{array} \right.  \]
Prove that there exists an $x,$ an optimal solution for
$(P)$, and a $y,$ an optimal solution for the dual of (P), for which
{\em strict} complementary slackness holds, i.e. 
\[  \begin{array}{rclcrclcr}
\sum_{i=1}^n a_{ij} x_j &=& b_i & \mbox{or} & y_i &=& 0, &
\mbox{but not both} & (i=1,2,\ldots,m),  \\
\mbox{and}              & &     &            &     & &    &  \\
\sum_{j=1}^m a_{ij} y_i &=& c_j & \mbox{or} & x_j &=& 0, &
\mbox{but not both} & (j=1,2,\ldots,n).
    \end{array}  \]
(Hint: Try to do this for one $i$ and then for one $j$. Then use
convex combinations.)

\end{enumerate}
\end{document}



