\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 5, due Tuesday, November 28, 1995}
\bigskip
\begin{enumerate}
\item Prove that $Ax\leq b$ is unsolvable if and only if there exists a
vector $y$ such that $y\geq 0$, $yA= 0$, and $yb<0$.
\item For the system $Ax=b,\ x\geq 0$, where $b=(3,1,2)^T$ and
\[A=\left(\begin{array}{rrrrr}
4&1&2&0&-1\\
0&1&1&-1&2\\
1&1&1&-1&1
\end{array}\right)\]
try to find a feasible solution by
applying the revised simplex
method using MATLAB to an auxiliary problem. Submit a computer printout of
your work. If there is no feasible solution, find a vector $y$ as in the
Farkas	Lemma.
\item
Consider the linear programming problem (P) $\max cx \mbox{ subject to }Ax=b,\ x\geq 0$,
where $b=(-2,5,-1)^T$, $c=(2,-1,0,-1,1)$, and
\[A=\left(\begin{array}{rrrrr}
-3&1&1&0&2\\
1&1&0&1&1\\
1&-2&0&0&1
\end{array}\right).\]
The feasible basis $B=(1,2,3)$ has corresponding basic feasible solution
$x^*=(3,2,5,0,0)^T$.
\begin{enumerate}
\item
[(a)] Find the solution $y$ of $yA_B=c_B$, and use it to check that $x^*$ is optimal.
\item
[(b)] Suppose that $c_5$ in (P) is changed from $1$ to a real number $R$.
For what values of $R$ is $x^*$ still optimal?
\item
[(c)] Suppose that $R$ of part (b) is slightly too large to satisfy the
conditions there. How would you solve the new problem? Go as far as finding
the entering and leaving variables, and the new primal solution after
one pivot.
\item
[(d)] Suppose that $c_2$ in (P) is changed from $-1$ to a real number $R$.
For what values of $R$ is $x^*$ still optimal?
\item
[(e)] Suppose that a new variable $x_6$ with coefficients $a_{16}=2$,
$a_{26}=-3$, and $a_{36}=4$ and $c_6=R$ is added to the problem (P).
For what values of $R$ will $x^*$ (with $x^*_6$ defined to be zero)
be optimal for the new problem?
\item
[(f)] Suppose that the value of $b_1$ in (P) is changed from $-2$ to $3$.
Solve the resulting problem.
\end{enumerate}
\item
Consider the linear programming problem (Q) $\max cx \mbox{ subject to }Ax\leq b,\ x\geq 0$,
where $b=(1,1,1)^T$, $c=(2,4,2,1)$, and
\[A=\left(\begin{array}{rrrr}
9&-1&2&-3\\
-14&3&-3&5\\
-6&1&-1&2
\end{array}\right).\]
After adding slack variables and solving it is found that $B=(1,3,4)$ is
an optimal basis, with corresponding optimal solution $x^*=(1,0,5,6,0,0,0)^T$.
You are given that
\[A^{-1}_B=\left(\begin{array}{rrr}
1&1&-1\\
2&0&3\\
4&3&-1
\end{array}\right)\]
\begin{enumerate}
\item
[(a)] Give an optimal dictionary for (Q).
\item
[(b)]
Suppose that the value of $b_3$ is changed from 1 to a real number $R$.
For what values of $R$ does the optimal basis remain optimal?
\item
[(c)] Suppose that $R$ of part (b) is slightly too small to satisfy the
conditions there. How should we proceed to solve the new problem? What do
you conclude about the new problem?
\item
[(d)] Suppose that a new constraint $x_1+x_3\leq 4$  is added to (Q). How
should we proceed to solve the new problem? Go as far as identifying the
entering and leaving variables on the first pivot.
\end{enumerate}
\end{enumerate}
\end{document}

