\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\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 2,	Due Tuesday, January 30, 1996}
\bigskip
\begin{enumerate}
\item
Solve the following problem by the simplex method, identifying
the basis matrix $A_B$ and the basis inverse $A_B^{-1}$ at each iteration.
Is the optimal solution unique? Explain. You may use LPmovie to check your
calculations, but do not  submit the output.
\begin{eqnarray*}
\mbox{maximize } z=-x_1+2x_2+5x_3+x_4&&\\
\mbox{subject to}&&\\
x_1+2x_2+2x_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{eqnarray*}
\item For the system of equations
$$
\begin{array}{rrrrrrc}
x_1&+x_2&+x_3&+x_4&&=&4\\
x_1&-x_2&&x_4&+x_5&=&1\\
x_1&+x_2&+x_3&&+x_5&=&4
\end{array}
$$
which of the following is a basic solution? Justify your answers.
\begin{enumerate}
\item[(a)] $(0,1,2,1,1)^T;$
\item[(b)] $(2,1,1,0,0)^T;$
\item[(c)] $(0,-1,5,0,0)^T;$
\item[(d)] $(0,0,\frac{7}{2},\frac{1}{2},\frac{1}{2}))^T.$
\end{enumerate}
\item Give an example to show that the variable that becomes basic on
one iteration of the simplex method, can become nonbasic on the next iteration.
\item Give a formula for the reduced cost $\bar c_j$ of a nonbasic variable
in a simplex tableau (or dictionary) in terms of the coefficients in the
previous tableau. Use this formula to prove that the variable that becomes
nonbasic on an iteration of the simplex method cannot become basic on
the next iteration.
\item \begin{enumerate}
\item[(a)] Formulate a Phase 1	(auxiliary) problem for finding a nonnegative
solution of the system of equations in problem 2. (Note that the method
used in Chapter 3 of the text will not work for this. Use the method
given in class.)
\item [(b)] Use LPmovie, with the largest coefficient rule for choosing
the entering variable, to solve the problem in (a), and submit the output.
\item [(c)] Using the solution to (b) find a feasible tableau or dictionary for
the problem maximize $z=x_1+x_2+2x_3+x_5$ subject to $x_1,\ldots, x_5\geq 0$
and the equations of problem 2.
\end{enumerate}
\item
Let $\bar x$ be an element of a convex set $S$.
Show that $\bar{x}$ is an
extreme point of $S$ if and only if the set $S-\{\bar{x}\}$ is a
convex set.

\end{enumerate}
\end{document}



