\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 3, Due Tuesday Feb. 13, 1996}
\bigskip
\begin{enumerate}
\item
Solve the following problems by the two phase simplex method.
You may use lpmovie to do the calculations, but do not submit output
from it.
\begin{enumerate}
\item
\[
\begin{array}{cccc}
\mbox{minimize} & z=3x_1-4x_2-x_3-2x_4-3x_5&&\\
\mbox{subject to}&&&\\
&x_1+x_2+x_3-x_4+2x_5&\leq&12\\
&x_1-2x_2-x_3-x_4-x_5&\geq&-30\\
&x_j\geq 0,~\forall j
\end{array}
\]
\item
\[
\begin{array}{cccc}
\mbox{maximize} & z=3x_1-x_2-3x_3+x_4&&\\
\mbox{subject to}&&&\\
&x_1+2x_2-x_3+x_4& = &0\\
&2x_1-2x_2+3x_3+3x_4& = &9\\
&x_1-x_2+2x_3-x_4& = &6\\
&x_j\geq 0,~\forall j
\end{array}
\]
\end{enumerate}
%\item
%Solve the following problem by the simplex method algorithm, identifying
%the basis matrix $A_B$ and its inverse at each iteration. Is the optimal
%solution unique? Explain.
%\[
%\begin{array}{cccc}
%\mbox{maximize} & z=x_1+2x_2+5x_3+x_4&&\\
%\mbox{subject to}&&&\\
%&x_1+2x_2+x_3-x_4&\leq&20\\
%&x_1+x_2+x_3+x_4&\leq&12\\
%&2x_1+x_2+x_3-x_4&\leq&30\\
%&x_j\geq 0,~\forall j
%\end{array}
%\]
\item
Consider the following problem.
\[
\begin{array}{cccc}
\mbox{maximize} & z=2x_1+x_2&&\\
\mbox{subject to}&&&\\
&x_1-x_2&\geq&8\\
&2x_1+3x_2&\leq&24\\
&2x_1+x_2&\leq&12\\
&x_j\geq 0,~\forall j
\end{array}
\]
\begin{enumerate}
\item
Verify graphically that this problem is infeasible.
\item
Use phase I of the two-phase method to show that the problem is
infeasible.
\end{enumerate}
\item
\begin{enumerate}
\item[(a)]
Suppose that we have a feasible dictionary or tableau for an l.p. problem,
corresponding to basis $B$ and basic feasible solution $x^*$. Show that 
if $\bar c_j<0$ for every $j\in N$, then $x^*$ is the unique optimal 
solution of the l.p. problem. 
\item[(b)] Give an example to show that the converse of the statement in 
part (a) is not true, that is, that it is possible for $x^*$ to be the 
unique optimal solution even though some $\bar c_j\geq 0$.
\end{enumerate}
\item Arrange the following vectors in lexicographical order, from smallest
to largest.\\ 
$(0,0,1),\ (0,-1,9),\ (1,-5,-6),\ (0,0,0),\ (0,-1,8),\ (-1,2,8)$

\item Choose the entering and leaving variables in this example, assuming 
that we are using:
\begin{enumerate}
\item[(a)] The smallest subscript rules. (In this case the $\eps$ columns
should be ignored.)
\item[(b)] The largest coefficient rule to choose the entering
variable and the lexicographical rule for choosing 
the leaving variable (using the $\eps$ columns).
\item[(c)] The smallest subscript rule is used for choosing the entering 
variable and the lexicographic rule for choosing the leaving variable.
$$
\begin{array}{rrrrrrrrrrr}
&&2x_2&+x_3&&-x_5&+x_6&=4&+2\eps_1&-2\eps_2&\\
&&x_2&-x_3& +x_4&+2x_5&&=2&+2\eps_1&+\eps_2&+3\eps_3\\
&x_1&+2x_2 &+2x_3&&+3x_5&&=6&+3\eps_1&&\\
z&&-2x_2 &+2x_3&& -3x_5&&=5 & &&
\end{array}
$$
\end{enumerate}
\item Suppose that, when solving a problem with the simplex method, there is 
never a tie for the choice of the leaving variable, that is, at each iteration
if $x_k$ is the entering variable, there is exactly one basic variable 
$x_r$ with $\bar a_{rk}>0$ and $\bar b_r/\bar a_{rk} =\min (\bar b_i/\bar a_{ik}
:\bar a_{ik}>0)$. 
\begin{enumerate}
\item [(a)] Can such a problem be degenerate? Explain.
\item [(b)] Can such a problem cycle? Explain.
\end{enumerate}
\end{enumerate}
\end{document}



