\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\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 2, due Thursday, October 12, 1995}
\bigskip
\begin{enumerate}
\item Solve the following LP using the simplex method, and then find a second
optimal solution. Do not submit a computer printout.
\begin{eqnarray*}
{\rm maximize}\  x_1 +&5x_2 +5x_3 +5x_4&\\
		   &\hbox{\rm subject to}\\
		   x_1 +&4x_2 +3x_3 +3x_4&\leq 17\\
				&x_2 +x_3 +x_4&\leq  4\\
		   x_1 +&2x_2 +2x_3 +3x_4&\leq 10\\
		   &x_1,\ldots,x_4\geq 0.
		   \end{eqnarray*}
		  \item \label{l1}Use LPmovie to exhibit cycling in the simplex method beginning with
this dictionary, and submit a computer printout.
\begin{eqnarray*}
  x_5=& 2x_1 +9x_2 +x_3-9x_4&\\
		x_6=&-\frac{1}{3}x_1 -x_2 +\frac{1}{3}x_3 +2x_4&\\
	   z  =& 2 x_1 +3x_2 -x_3 -12x_4&
		   \end{eqnarray*}

\item Arrange the following vectors in	lexicographical order from
smallest to largest:
$$(3,-1,0,0),\ (3,0,0,0),\ (2,10,0,0),\ (3,-4,1,0),\ (0,0,1,3),\ (3,4,0,3),\
(3,-4,1,1)$$
\item Solve
the problem of~\ref{l1} using the smallest-subscript rule.
 \item	  Prove that the variable that becomes non-basic on one
		  iteration of the simplex method cannot become basic on the next
		   iteration. Show that the variable that becomes basic on one
		  iteration of the simplex method {\it can} become non-basic on
		   the next iteration.

\item Construct a feasible dictionary whose basic feasible solution is optimal,
but having $\bar c_j>0$ for some $j$.
\item Chv\'atal 3.9(b).  Do not submit a computer printout.
%\item Suppose that in solving a problem with the simplex method, we never have
%a tie for the choice of the variable becoming non-basic. Prove that there will
%be no cycle.
\end{enumerate}
\end{document}

