\documentstyle[12pt]{article}
%
\def\baselinestretch {1.3}
\oddsidemargin 0.5cm
\textwidth 6in
\topmargin -0.5cm
\textheight 8.5in
\pagestyle{empty}
%
\pagestyle{empty}
\newtheorem{prop}{Proposition}[section]
\newtheorem{theorem}[prop]{Theorem}
\newtheorem{cor}[prop]{Corollary}
\newtheorem{lemma}[prop]{Lemma}
\newcommand{\myline}{\noindent \rule{\textwidth}{.02in} \medskip}
\newcommand{\matchings}{\noindent {\bf Matching Polyhedra} \medskip}
%
\newcommand\blackslug{\hbox{\hskip 1pt \vrule width 4pt height 8pt depth 1.5pt
        \hskip 1pt}}
  
\newenvironment{proof}{{\bf Proof:\ }}{{\quad\blackslug\medbreak}}
\newcommand{\oofx}{{\quad\blackslug\medbreak}}
\newcounter{ex}[section]
\newcommand{\ex}[1]{\refstepcounter{ex}\item[\thesection.\theex.]\label{#1}}
%
\def\eps{\varepsilon}
\def\minimize{\rm minimize}
\def\maximize{\rm maximize}
\def\R{{\bf R}}
\def\Z{{\bf Z}}
\def\bs{\backslash}
\newcommand{\ssp}{\renewcommand{\baselinestretch}{1}\large\normalsize}
\newcommand{\dsp}{\renewcommand{\baselinestretch}{1.5}\large\normalsize}
\begin{document}
                                                           
\centerline{\bf C\&O 350 Assignment 4, Due Thursday March 7, 1996}
\bigskip
\begin{enumerate}
\item
For each of the following problems, write the dual problem, and use 
the final tableau of the primal problem to obtain optimal solutions to
both problems. Check that the optimal primal and dual values are equal.
\begin{itemize}
\item[(a)] Problem 1 from Assignment 2.
\item[(b)] Problem 1(a) from Assignment 3. (First convert to standard 
inequality form.)
\item[(c)] Problem 1 from the midterm. 
\end{itemize}
\item Does the dual problem of 1(c) above have more than one optimal solution?
Explain. What property of the primal problem is this related to? 
\item Consider the l.p. problem $(P)$ below:
$$
\begin{array}{rrrrrr}
\mbox{maximize }-2x_1&+5x_2&+5x_3&+4x_4&&\\
\mbox{subject to }&&&&&\\
x_1&+3x_2&-x_3&+x_4&\leq &3\\
-x_1&+x_2&+2x_3& +x_4&\leq &4\\
x_1&+x_2 &+x_3&-x_4&\leq &1\\
x_1,&x_2,&x_3,&x_4&\geq & 0
\end{array}
$$
For each of the following, use complementary slackness to determine whether
it is an optimal solution of $(P)$:
\begin{itemize}
\item[(a)] $x=(1,1,1,0)^t$;
\item[(b)] $x=(0,1,1,1)^t$;
\item[(c)] $x=(2,0,0,1)^t$;
\item[(d)] $x=(1,0,1,3)^t$.
\end{itemize}
\item For the l.p. of Problem 1(b) of Assignment 3, 
write the dual problem, and use the optimal basis to 
find an optimal solution of the dual problem.
\item Chv\'atal problem 5.2. (Use duality.)
\item Chv\'atal problem 9.1.
\end{enumerate}
\end{document}



