\documentstyle[11pt]{article}
\oddsidemargin 0.0in
\evensidemargin 0.0in
\textwidth 6.75in
\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}
\underline{{\bf C \& O 350 \hspace{1.6in} Assignment 3 \hspace{1.6in} Due
Tuesday, 24th October}}
\end{center}

\section{\underline{Phases I,II}}
 Solve the following linear programs using the two phase approach.
\begin{enumerate}
\item
\[  (LP)  \begin{array}{ccccccrcl}
 \max  & 8x_1 &+& 10x_2   \\
 \mbox{subject to} &   x_1 &-&x_2   & = & 1\\
                   &   x_1 &+&x_2   & \leq & 9\\
                   &   x_1 &+&\frac 12 x_2   & \geq & 4\\
       &  &&  x_j & \geq & 0,& \forall j \\
  \end{array}
\]
\item
\[  (LP)  \begin{array}{ccccccrcl}
 \max  & 5x_1 &+& x_2   \\
 \mbox{subject to} &   2x_1 &+&x_2   & \geq  & 5\\
                   &    &&x_2   & \geq & 1\\
                   &   2x_1 &+&3 x_2   & \leq & 6\\
       &  &&  x_j & \geq & 0,& \forall j \\
  \end{array}
\]
\end{enumerate}

\section{\underline{BFS}}
Suppose that $x^*$ is the only optimal solution of a linear programming
problem in standard form. Prove that $x^*$ is a basic solution.

\section{\underline{Duality}}
 Solve the linear program
\[  (LP)  \begin{array}{ccccrcl}
 \min  & 3y_1 &+& 6y_2  \\
 \mbox{subject to} &   3y_1 &&  & \geq & 3\\
       & -y_1 &+& y_2  & \geq & 1 \\
       & 2y_1 &-& y_2  & \geq & -2 \\
       & -2y_1 &+& y_2  & \geq & 1 \\
       & y_1 &+& 2y_2  & \geq & -2 \\
       & -y_1 &+& y_2  & \geq & 1 \\
       & -3y_1 &+& 2y_2  & \geq & -3 \\
       & y_1 &&   & \geq & 0 \\
       &  &&  y_2 & \geq & 0 \\
  \end{array}
\]
(HINT: Do not be undually upset by the number of constraints.)


\section{\underline{Complementary Slackness}}
Using complementary slackness, check optimality of:
\begin{enumerate}
\item
\[  x = \left( 10 \frac 13,6 \frac 13,0 \right)^t  \]
\item
\[  x = \left( 7,9,0 \right)^t  \]
\item
\[  x = \left( 6,7,4 \right)^t  \]
\end{enumerate}
for the following linear program.
\[  (LP)  \begin{array}{ccccccrcl}
 \max  & 16x_1 &+& 21x_2 &+& 10x_3  \\
 \mbox{subject to} &   3x_1 &+&4x_2 &+& 2x_3  & \leq & 57\\
                   &   2x_1 &+&x_2 &+& 2x_3  & \leq & 27\\
                   &   4x_1 &+&5x_2 &+& 4x_3  & \leq & 73\\
       &  &&  x_j & \geq & 0,& \forall j \\
  \end{array}
\]


\section{\underline{Duality}}
Suppose that you have no knowledge of how to solve linear programs.
But you do understand the duality theorem, as well as weak duality. Suppose
further that you have access to a ``black box'' which, given a real $m
\times n$ matrix $A$ and $m$-vector $b$, solves the system of linear
inqualities
\[  (L)  ~~~ Aw \leq b.    \]
That is, it either gives an explicit vector  $w$ which solves (L), or says
``(L) has no solution'', if that is the case.\\
Explain how you would use this black box to solve the linear program
\[  (LP)  \begin{array}{ccccccrcl}
 \max  & x_1 &+& x_2   \\
 \mbox{subject to} &   2x_1 &-&x_2   & \leq & 3\\
                   &   3x_1 &+&x_2   & \leq & 6\\
       &  &&  x_j & \geq & 0,& \forall j \\
  \end{array}
\]
Specifically, determine the $A$ and $b$ which you would give the black
box, and explain how to find a solution to (P) from a solution to (L).
Generalize your result to any linear program.


\end{document}


