\documentstyle[fullpage,12pt]{article}
\reversemarginpar
\input{mssymb}
\renewcommand{\textheight}{12in}
\renewcommand{\topmargin}{-.5in}
\addtolength{\oddsidemargin}{.2in}

%\underline{\hspace{60mm}}}}

\begin{document}

\thispagestyle{empty}

\vspace*{2in}

\begin{center}
{\Large\bf C\&O 350 -- LINEAR PROGRAMMING}\\[5mm]
{\Large\bf Midterm Examination - Winter 1995}\\[8mm]
Wednesday, 1 March, 1995, 7.00 -- 9.00pm {\bf (2 hours)} \\[5mm]
This examination consists of 4 questions and 9 pages.  \\[5mm]
{\bf ANSWER ALL QUESTIONS.}  \\[5mm]
Calculators permitted. \\ \medskip \medskip \medskip
Tick off your section: \\ \medskip
\begin{tabular}{|l|l|l|} \hline
01 & \fbox{\phantom{x}}  Wolkowicz & TR 11:30  \\ \hline
02 & \fbox{\phantom{x}}  Lewis & MWF 8:30  \\ \hline
03 & \fbox{\phantom{x}}  Lewis & MWF 10:30  \\ \hline
\end{tabular}
\end{center}



\vspace{20mm}
\begin{center}
\begin{tabular}{ll}

{\bf NAME:} & {\bf \underline{\hspace{74mm}}} \bigskip \\

{\bf ID:} & {\underline{\hspace{74mm}}} \bigskip \\

{\bf SIGNATURE:} & {\underline{\hspace{74mm}}}

\end{tabular}
\end{center}

\vspace{16mm}


\begin{center}
\begin{tabular}[t]{|c|@{\hspace{20mm}/}r|}
\hline
\multicolumn{2}{|c|}{For Marker Only}\\
\hline\hline
\rule{0mm}{9mm}1&\\
\hline
\rule{0mm}{9mm}2&\\
\hline
\rule{0mm}{9mm}3&\\
\hline
\rule{0mm}{9mm}4&\\
\hline\hline
\rule{0mm}{10mm}Total&\\ \hline
\end{tabular}
\end{center}

\newpage

\begin{enumerate}
\item
\begin{enumerate}
\item[(i)]
Solve
\[ (P)~~~~\left\{ \begin{array}{lrcrcrcl}
\mbox{maximize}   & 2x_1 &+& 3x_2 &-& 4x_3 &      &    \\
\mbox{subject to} &  x_1 &+&  x_2 &-&  x_3 & \leq & 2, \\
                  &  x_1 &+& 2x_2 &+&  x_3 & \leq & 3, \\
                  &  x_1 &,&  x_2 &,&  x_3 & \geq & 0,
                  \end{array} \right. \]
by the simplex method.
\end{enumerate}
\newpage
\item[1.]
\begin{enumerate}
\item[(ii)]
State the (strong) duality theorem for linear programs in standard form.
\vspace{3cm}
\item[(iii)]
Write down the dual problem $(D)$ for $(P)$, and deduce an optimal solution
for $(D)$ from
your answer to part (i).
\vspace{10cm}
\item[(iv)]
Use your answer to part (iii) to verify the duality theorem for $(P)$.
\end{enumerate}
\newpage
\item
\begin{enumerate}
\item[(i)]
Use Phase I of the simplex method to find an initial feasible dictionary
for
\[ (Q)~~~~\left\{ \begin{array}{lrcrcl}
\mbox{maximize}   &   x_1 &+&  x_2 &      &     \\
\mbox{subject to} & -2x_1 &-&  x_2 & \leq & -4, \\
                  &   x_1 &-&  x_2 & \leq & -1, \\
                  & -2x_1 &+&  x_2 & \leq &  2, \\
                  &   x_1 &,&  x_2 & \geq & 0.
                  \end{array} \right. \]
{\bf Do not solve the problem.}
\end{enumerate}
\newpage
\item[2.]
\begin{enumerate}
\item[(ii)]
Find a NEW objective function (in terms of $x_1$ and $x_2$)
for the problem $(Q)$ for which the feasible
solution you found in part (i) is the unique optimal solution.  Explain
your answer.
\end{enumerate}
\newpage
\item
\begin{enumerate}
\item[(a)]
Let $F$ be the set of $x$ in ${\Bbb R}^k$ satisfying
\[  (S)~~~~\left\{ \begin{array}{rcll}
\sum_{j=1}^k a_{ij} x_j &  = & b_i & (i=1,2,\ldots,m),  \\
                    x_j &\geq&   0 & (j=1,2,\ldots,k).
                   \end{array} \right.  \]
\begin{enumerate}
\item[(i)]
Define `$x^*$ is a basic feasible solution for $(S)$'.
\vspace{5cm}
\item[(ii)]
Define `$x^*$ is an extreme point of $F$'.
\vspace{3cm}
\end{enumerate}

\item[(b)]
Now let $F$ be the set of $x$ in ${\Bbb R}^5$ satisfying
\[ \left\{ \begin{array}{rcrcrcrcrcr}
 x_1 &-& 2x_2 &-&  x_3 &+& x_4 & &     &  = & -2,  \\
2x_1 &+& 3x_2 &+& 5x_3 & &     &+& x_5 &  = & 10,  \\
 x_1 &,&  x_2 &,&  x_3 &,& x_4 &,& x_5 &\geq&  0,
           \end{array} \right. \]
For each of the following points $x^*$, either find a dictionary
corresponding to $x^*$, or find a nonzero $d$ in ${\Bbb R}^5$ with
$x^* + d$ and $x^* - d$ in $F$:
\begin{enumerate}
\item[(i)]
$x^* = (1,1,1,0,0)^T$.
\vspace{8cm}
\end{enumerate}
\newpage
\item[3.]
\begin{enumerate}
\item[(ii)]
$x^* = (0,0,2,0,0)^T$.
\end{enumerate}
\end{enumerate}
\newpage
\item
\begin{enumerate}
\item[(a)]
Suppose that $x$ and $y$ are given such that
\[  \begin{array}{rclcrclr}
\sum_{i=1}^n a_{ij} x_j &\leq& b_i & \mbox{and} & y_i &\geq& 0, &
(i=1,2,\ldots,m),  \\
\mbox{and}              &    &     &            &     &    &    &  \\
\sum_{j=1}^n a_{ij} y_i &\geq& c_j & \mbox{and} & x_j &\geq& 0, &
(j=1,2,\ldots,n).
    \end{array}  \]
Prove from first principles (without using any results) that
$\sum_{j=1}^n c_j x_j \leq \sum_{i=1}^m b_i y_i$, with equality if
and only if
\[  \begin{array}{rclcrclr}
\sum_{i=1}^n a_{ij} x_j &=& b_i & \mbox{or} & y_i &=& 0, &
(i=1,2,\ldots,m),  \\
\mbox{and}              & &     &            &     & &    &  \\
\sum_{j=1}^n a_{ij} y_i &=& c_j & \mbox{or} & x_j &=& 0, &
(j=1,2,\ldots,n).
    \end{array}  \]
\end{enumerate}
\newpage
\item[4.]
\begin{enumerate}
\item[(b)]
Use complementary slackness to determine if $x=(3,0,0,0)^T$
is optimal for the problem
\[ \left\{ \begin{array}{lrcrcrcrcl}
\mbox{maximize}   & 2x_1 &+& 3x_2 &+& 5x_3 &+& 4x_4 &      &    \\
\mbox{subject to} &  x_1 &+& 2x_2 &+& 3x_3 &+&  x_4 & \leq & 5, \\
                  &  x_1 &+&  x_2 &+& 2x_3 &+& 3x_4 & \leq & 3, \\
                  &  x_1 &,&  x_2 &,&  x_3 &,&  x_4 & \geq & 0,
                  \end{array} \right. \]
\end{enumerate}

\end{enumerate}
\end{document}
