%  Problem set 2: solutions
%  Combinatorial Optimization, SUAMI, summer 2015
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=9truein
\pdfhorigin=1.5truein \pdfvorigin=1truein

% AMSFonts
\input amssym.tex

\font\titlefont=cmbx12  \font\smfont=cmr8

\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
	\medbreak\noindent{\llap{\bf\the\pno.\enspace}}\ignorespaces}
\def\solution{\medskip\noindent{\bf Solution.}\enspace\ignorespaces}

% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}
\def\subqed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\raise2pt\hbox{\vrule height4pt width4pt depth0pt}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}

\newdimen\pivotwidth  \newdimen\pivotdepth
\def\pivot#1{%
	\setbox0=\hbox{$#1$}
	\pivotdepth=\dp0
	\setbox0=\hbox{\vbox{\vskip2pt\hbox{\hskip2pt\box0\hskip2pt}\vskip2pt}}%
	\pivotwidth=\wd0  \advance\pivotwidth by0.8pt
	\lower\pivotdepth\hbox{\vbox{%
		\vskip-2.4pt
		\hrule width\pivotwidth height0.4pt depth0.0pt
		\hbox{%
			\vrule height\ht0 depth\dp0 width0.4pt
			\copy0
			\vrule height\ht0 depth\dp0 width0.4pt
		}%
		\hrule width\pivotwidth height0.4pt depth0.0pt
		\vskip-2.4pt
	}\hskip-2.4pt}%
}

\def\R{{\mathord{\Bbb R}}}
\def\transpose{{\rm T}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~2: solutions}

\medskip

\problem Consider the following two linear programs in standard form:
$$\eqalign{
	{\rm maximize}\quad c^\transpose x&\cr
	{\rm subject\ to}\quad\phantom{c^\transpose}\llap{$A$}x&=b\cr
	x&\ge0\cr
}\qquad\qquad\qquad\qquad\eqalign{
	{\rm maximize}\quad{-}c^\transpose x&\cr
	{\rm subject\ to}\quad\phantom{-c^\transpose}\llap{$A$}x&=b\cr
	x&\ge0\cr
}$$
Can both of these linear programs have feasible solutions with arbitrarily
large objective value? If yes, give an example; if not, prove so.

\solution Yes. For example,
$$\eqalign{
	{\rm maximize}\quad x_1-x_2&\cr
	x_1\ge0,\quad x_2\ge0&\cr
}\qquad\qquad\qquad\qquad\eqalign{
	{\rm maximize}\quad{-}x_1+x_2&\cr
	x_1\ge0,\quad x_2\ge0&\cr
}$$
[Note that the set of constraints for these linear programs is empty, so the
feasible region is the entire first quadrant. If you don't like $0\times n$
matrices, you can accomplish the same thing by taking, say, $A$~to be a zero
matrix and $b$~to be a zero vector. Or throw in the constraint
$x_1-2x_2-s_1=0$, with $s_1\ge0$; both linear programs are still
unbounded (exercise: justify this claim).] \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem In class we saw an example that served as a sketch of a proof of the
following theorem:

{\medskip\narrower\proclaim Theorem. Let $x$ be a feasible solution to a
maximizing linear program (in standard form). Then either there exists a basic
feasible solution whose objective value is at least as large as that of~$x$, or
else the linear program is unbounded.\par}

\noindent Using the example as a guide, prove this theorem.

\solution Let the linear program be
$$\eqalign{
	{\rm maximize}\quad c^\transpose x&\cr
	{\rm subject\ to}\quad\phantom{c^\transpose}\llap{$A$}x&=b\cr
	x&\ge0,\cr
}$$
where $c$~and~$x$ are $n\times1$ column vectors, $A$~is an $m\times n$ matrix,
and $b$ is an $m\times1$ column vector.

Let $x$ be a feasible solution to this linear program. By reordering the
components of~$x$ (and the components of~$c$, and the columns of~$A$), we may
assume without loss of generality that the first $r$~components of~$x$ are
nonzero and the remaining $n-r$ components are zero:
$$\eqalign{
	x_i&\not=0\quad\hbox{for $1\le i\le r$};\cr
	x_i&=0\quad\hbox{for $r+1\le i\le n$}.\cr
}$$
We proceed by induction on~$r$.

If $r=0$, then $x$ is the zero vector, which certainly is a basic solution:
Since $x$ is feasible, it satisfies $Ax=b$, so $b$ must be the zero vector. So
we may choose any basis of~$A$ and the corresponding basic solution will be
the zero vector. Therefore, if $r=0$, then we are done, because $x$ itself is a
basic feasible solution. This establishes the base case.

For the inductive step, suppose that $r\ge1$. If the first $r$~columns of~$A$
are linearly independent, then we are done, because $x$~itself is a basic
solution: we can extend the first $r$~columns of~$A$ to a basis, and the
corresponding basic solution will be~$x$.

Otherwise, the first $r$~columns $\{A_1,\ldots,A_r\}$ of~$A$ are linearly
dependent. Therefore there exist coefficients $h_1$,~\dots,~$h_r$, not all
zero, such that $A_1h_1+\cdots+A_rh_r=0$. Let $h$ be the $n\times1$ column
vector $[h_1,\ldots,h_r,0,\ldots,0]^\transpose$, so that $Ah=0$. Note that
$h\not=0$ because not all of the coefficients $h_1$,~\dots,~$h_r$ are zero.
Also observe that $A(x+th)=Ax+tAh=b+0=b$ for all $t\in\R$, so $x+th$ will
satisfy the constraints of the linear program for any scalar~$t$, which means
that $x+th$ will be a feasible solution as long as all of its components are
nonnegative.

Without loss of generality, we may assume that $c^\transpose h\ge0$; if not,
then take $-h$ instead of~$h$.

We now consider two cases, depending on whether $h$ has any negative
components. In the first case, $h$ has no negative components. If
$c^\transpose h=0$, then $-h$ must have at least one negative component
(because $h\not=0$), so take $-h$ instead of~$h$ and go to the second case.
Otherwise $c^\transpose h>0$. Since $h$ has no negative components, we have
$x+th\ge x\ge0$ for all $t\ge0$, so $x+th$ is feasible for all $t\ge0$.
Furthermore, the objective value of $x+th$ is
$c^\transpose(x+th)=c^\transpose x+t(c^\transpose h)$, which can be made
arbitrarily large because $c^\transpose h>0$. So the linear program is
unbounded.

In the second case, $h$ has at least one negative component. Let
$$t=\min\left\{\,-{x_i\over h_i}:h_i<0\,\right\}.$$
Let $k$ be a coordinate at which this minimum is attained, that~is,
$-x_k/h_k=t$. Since $x_i>0$ for all $1\le i\le r$, and $h_i=0$ for all
$r+1\le i\le n$, we see that $t>0$ and $1\le k\le r$. Let $y=x+th$. For
$1\le i\le r$, if $h_i\ge0$ then $y_i=x_i+th_i\ge x_i\ge0$; otherwise, by the
definition of~$t$, we have $y_i=x_i+th_i\ge x_i+(-x_i/h_i)h_i=0$. For
$r+1\le i\le n$, we have $y_i=x_i+th_i=0+t\cdot0=0$. So $y$ is feasible,
because all of its components are nonnegative. Moreover,
$y_k=x_k+th_k=x_k+(-x_k/h_k)h_k=0$, so $y$ has strictly fewer than $r$~nonzero
components (because $y_i=0$ for $i=k$ and for all $r+1\le i\le n$). Finally,
$c^\transpose y=c^\transpose(x+th)=c^\transpose x+t(c^\transpose h)\ge
c^\transpose x$ because $t>0$ and $c^\transpose x\ge0$, so the objective value
of~$y$ is at least as large as that of~$x$. By the inductive hypothesis, either
there exists a basic feasible solution whose objective value is at least as
large as that of~$y$ (and hence at least as large as that of~$x$), or else the
linear program is unbounded. This completes the inductive step, and hence the
proof. \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vskip0pt plus30pt

\problem Convert the following linear program to standard form. Write the
initial simplex tableau and give the initial basic feasible solution. Do a
pivot to bring $x_2$ into the basis and give the resulting basic feasible
solution.
$$\eqalign{
	{\rm maximize}\quad5x_1+3x_2-2x_3&\cr
	{\rm subject\ to}\quad\phantom1x_1+2x_2+\phantom1x_3&\le10\cr
	4x_1+5x_2\phantom{{}+0x_3}&\le20\cr
	2x_1-3x_2+2x_3&\le\phantom06\cr
	&\phantom{{}=00}\llap{$x_1\ge0$,\quad$x_2\ge0$,\quad$x_3\ge0$}.\cr
}$$

\solution First we insert slack variables to convert the linear program to
standard form:
$$\eqalign{
	{\rm maximize}\quad5x_1+3x_2-2x_3\phantom{{}+s_1+s_2+s_3}&\cr
	{\rm subject\ to}\quad\phantom1x_1+2x_2+\phantom1x_3+s_1\phantom{{}+s_2+s_3}
		&=10\cr
	4x_1+5x_2\phantom{{}+0x_3+s_1}+s_2\phantom{{}+s_3}&=20\cr
	2x_1-3x_2+2x_3\phantom{{}+s_1+s_2}+s_3&=\phantom06\cr
	&\phantom{{}=00}\llap{$x_1\ge0$,\quad$x_2\ge0$,\quad$x_3\ge0$,\quad
		$s_1\ge0$,\quad$s_2\ge0$,\quad$s_3\ge0$}.\cr
}$$

\goodbreak

\noindent Now we can write the initial simplex tableau:
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x_1&x_2&x_3&s_1&s_2&s_3&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
-5&-3&2&0&0&0&1&&0\cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
1&2&1&1&0&0&0&&10\cr
4&5&0&0&1&0&0&&20\cr
2&-3&2&0&0&1&0&&6\cr}}$$

\noindent The initial basic feasible solution is
$$x_1=0,\quad x_2=0,\quad x_3=0,\quad s_1=10,\quad s_2=20,\quad s_3=6.$$

\noindent We are asked to do a pivot to bring $x_2$ into the basis, so we need
to pivot on an entry in the $x_2$~column. There are two positive entries in
this column, which are the candidates to be the pivot entry. The test ratio for
the entry~2 in the first row of the body of the tableau is $10/2=5$, and the
test ratio for the entry~5 in the second row is $20/5=4$. So we pivot on the~5,
because it has the minimum test ratio. After this pivot, the tableau becomes
the following:
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x_1&x_2&x_3&s_1&s_2&s_3&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
-13/5&0&2&0&3/5&0&1&&12\cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
-3/5&0&1&1&-2/5&0&0&&2\cr
4/5&1&0&0&1/5&0&0&&4\cr
22/5&0&2&0&3/5&1&0&&18\cr}}$$
The corresponding basic feasible solution is
$$x_1=0,\quad x_2=4,\quad x_3=0,\quad s_1=2,\quad s_2=0,\quad s_3=18.\eqno\hbox{\qed}$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Answer yes or no and prove your answer: Can a pivot move the
corresponding basic feasible solution a positive distance in~$\R^n$ while
leaving the objective value unchanged?

\solution Yes. For example:
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x&s_1&s_2&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0&0&0&1&&0\cr
\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&height2pt\cr
2&1&0&0&&5\cr
\pivot1&0&1&0&&1\cr}}$$
The corresponding basic feasible solution is $x=0$, $s_1=5$, $s_2=1$, with an
objective value of~0. Pivoting on the indicated entry produces the following
tableau:
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x&s_1&s_2&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0&0&0&1&&0\cr
\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&height2pt\cr
0&1&-2&0&&3\cr
1&0&1&0&&1\cr}}$$
The basic feasible solution corresponding to this tableau is $x=1$, $s_1=3$,
$s_2=0$, also having an objective value of~0. So the pivot moved the basic
feasible solution a positive distance in~$\R^n$ (i.e., the two basic solutions
are not identical), but the objective value is unchanged.

In general, this will happen whenever a pivot is performed in a column having a
zero in the objective row (in a non-degenerate tableau). \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Solve the following linear program by hand, using the simplex
algorithm.
$$\eqalign{
	{\rm maximize}\quad20x_1+6x_2+8x_3&\cr
	{\rm subject\ to}\quad\phantom06x_1+2x_2+3x_3&\le420\cr
	4x_1+3x_2\phantom{{}+0x_3}&\le200\cr
	x_3&\le\phantom050\cr
	&\phantom{{}=000}\llap{$x_1\ge0$,\quad$x_2\ge0$,\quad$x_3\ge0$}.\cr
}$$

\solution First we insert slack variables in order to convert the linear
program to standard form:
$$\eqalign{
	{\rm maximize}\quad20x_1+6x_2+8x_3\phantom{{}+s_1+s_2+s_3}&\cr
	{\rm subject\ to}\quad\phantom06x_1+2x_2+3x_3+s_1\phantom{{}+s_2+s_3}&=420\cr
	4x_1+3x_2\phantom{{}+0x_3+s_1}+s_2\phantom{{}+s_3}&=200\cr
	x_3\phantom{{}+s_1+s_2}+s_3&=\phantom050\cr
	&\phantom{{}=000}\llap{$x_1\ge0$,\quad$x_2\ge0$,\quad$x_3\ge0$,\quad
		$s_1\ge0$,\quad$s_2\ge0$,\quad$s_3\ge0$}.\cr
}$$
Now we write the initial simplex tableau:
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x_1&x_2&x_3&s_1&s_2&s_3&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
-20&-6&-8&0&0&0&1&&0\cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
6&2&3&1&0&0&0&&420\cr
4&3&0&0&1&0&0&&200\cr
0&0&1&0&0&1&0&&50\cr}}$$
We will pivot in the $x_1$~column, because it has the most negative entry in
the objective row. The test ratio for the entry~6 in that column is $420/6=70$,
the test ratio for the entry~4 in that column is $200/4=50$, and we cannot
pivot on the entry~0. So we pivot on the entry~4, because it has the minimum
test ratio. After that pivot, we obtain the following tableau:
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x_1&x_2&x_3&s_1&s_2&s_3&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0&9&-8&0&5&0&1&&1000\cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
0&-5/2&3&1&-3/2&0&0&&120\cr
1&3/4&0&0&1/4&0&0&&50\cr
0&0&1&0&0&1&0&&50\cr}}$$
Now we pivot in the $x_3$~column, because it is the only column with a negative
entry in the objective row. The test ratio for the entry~3 in that column is
$120/3=40$, we cannot pivot on the entry~0, and the test ratio for the entry~1
in that column is $50/1=50$. So we pivot on the entry~3, because it has the
minimum test ratio. After that pivot, we get this tableau:
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x_1&x_2&x_3&s_1&s_2&s_3&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0&7/3&0&8/3&1&0&1&&1320\cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
0&-5/6&1&1/3&-1/2&0&0&&40\cr
1&3/4&0&0&1/4&0&0&&50\cr
0&5/6&0&-1/3&1/2&1&0&&10\cr}}$$
Now there are no negative entries in the objective row, so this tableau is
optimal. The optimal solution to the linear program is $x_1=50$, $x_2=0$,
$x_3=40$, $s_1=0$, $s_2=0$, $s_3=10$, having the optimal objective value~1320.
\qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Consider the following simplex tableau (for the maximizing simplex
algorithm).
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$&\quad\hfil\strut$#$\quad&\vrule#%
	&\quad\hfil\strut$#$\quad\cr
x_1&x_2&x_3&s_1&s_2&s_3&s_4&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
a_1&0&0&0&40&0&25&1&&700\cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
a_2&0&0&1&1/2&0&-2&0&&84\cr
a_3&1&0&0&-2&0&5/2&0&&225\cr
a_4&0&1&0&3/2&0&1/2&0&&125\cr
a_5&0&0&0&-5/2&1&-3/2&0&&65\cr}}$$
For each part below, describe conditions on the entries $a_1$,~\dots,~$a_5$ in
the first column so that the tableau satisfies the stated condition. Try to
make your answers as general as possible.

\smallskip

\item{(a)} The corresponding basic feasible solution is optimal and unique.

\smallskip

\item{(b)} The corresponding basic feasible solution is optimal but not
unique, and $x_1=13$ in the alternative optimal basic feasible solution.

\smallskip

\item{(c)} The corresponding basic feasible solution is not optimal, and in the
next basic feasible solution (that~is, the basic feasible solution
corresponding to the tableau after the next pivot in the simplex algorithm),
$s_1=0$ and the value of the objective function is~742.

\smallskip

\item{(d)} The corresponding basic feasible solution is not optimal, and in the
next basic feasible solution $x_3=0$ and $s_3=40$.

\solution

\smallskip

\item{(a)} A non-degenerate simplex tableau represents a unique optimal bfs if
and only~if all nonbasic columns have positive entries in the objective row.
For this to be true of this tableau, the $x_1$~column must be a nonbasic column
with a positive entry in the objective row; so $a_1>0$. There are no conditions
on the entries $a_2$,~\dots,~$a_5$.

\smallbreak

\item{(b)} A non-degenerate simplex tableau represents a non-unique optimal bfs
if and only~if all entries in the objective row are nonnegative and at least
one nonbasic column has a zero in the objective row. So we need $a_1=0$. From
such a tableau, an alternative optimal bfs can be obtained by pivoting in that
nonbasic column on a positive entry having the minimum test ratio. In order to
make $x_1=13$ in the alternative optimal bfs, we need that minimum test ratio
to be~13. So we additionally need $a_2\le84/13$, $a_3\le225/13$,
$a_4\le125/13$, and $a_5\le5$ with at least one of these inequalities satisfied
by equality.

\smallbreak

\item{(c)} In order for the corresponding bfs to be non-optimal, we need a
negative entry in the objective row, so $a_1<0$. In order to make $s_1=0$ in
the next bfs, we need one of the following to be true:

\smallskip

\itemitem{$\bullet$} We can pivot on~$a_2$, thereby making $s_1=0$ because it
will fall out of the basis. To make the value of the objective function be~742
in the next bfs, we need $a_2=-2a_1$, and to ensure that $a_2$ has the minimum
test ratio, we need $a_3\le225a_2/84$, $a_4\le125a_2/84$, and $a_5\le65a_2/84$.

\smallskip

\itemitem{$\bullet$} We can pivot on~$a_3$. To make the value of the objective
function be~742 in the next bfs, we need $a_3=-225a_1/42$. To make $s_1=0$ in
the next bfs, we need $a_2=84a_3/225$. To ensure that $a_3$ has the minimum
test ratio, we need $a_4\le125a_3/225$ and $a_5\le65a_3/225$.

\smallskip

\itemitem{$\bullet$} We can pivot on~$a_4$. To make the value of the objective
function be~742 in the next bfs, we need $a_4=-125a_1/42$. To make $s_1=0$ in
the next bfs, we need $a_2=84a_4/125$. To ensure that $a_4$ has the minimum
test ratio, we need $a_3\le225a_4/125$ and $a_5\le65a_4/125$.

\smallskip

\itemitem{$\bullet$} We can pivot on~$a_5$. To make the value of the objective
function be~742 in the next bfs, we need $a_5=-65a_1/42$. To make $s_1=0$ in
the next bfs, we need $a_2=84a_5/65$. To ensure that $a_5$ has the minimum
test ratio, we need $a_3\le225a_5/65$ and $a_4\le125a_5/65$.

\smallbreak

\item{(d)} In order for the corresponding bfs to be non-optimal, we need a
negative entry in the objective row, so $a_1<0$. In order to make $x_3=0$ in
the next bfs, we need one of the following to be true:

\smallskip

\itemitem{$\bullet$} We can pivot on~$a_4$, thereby making $x_3=0$ because it
will fall out of the basis. To make $s_3=40$ in the next bfs, we need
$a_5=25a_4/125$. To ensure that $a_4$ has the minimum test ratio, we need
$a_2\le84a_4/125$ and $a_3\le225a_4/125$.

\smallskip

\itemitem{$\bullet$} We can pivot on~$a_2$. To make $x_3=0$ in the next bfs, we
need $a_4=125a_2/84$. To make $s_3=40$ in the next bfs, we need $a_5=25a_2/84$.
To ensure that $a_2$ has the minimum test ratio, we need $a_3\le225a_2/84$.

\smallskip

\itemitem{$\bullet$} We can pivot on~$a_3$. To make $x_3=0$ in the next bfs, we
need $a_4=125a_3/225$. To make $s_3=40$ in the next bfs, we need
$a_5=25a_3/225$. To ensure that $a_3$ has the minimum test ratio, we need
$a_2\le84a_3/225$.

\smallskip

\item{} Note that we cannot pivot on~$a_5$, because that would cause $s_3$ to
fall out of the basis, which would make it impossible to have $s_3=40$. \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
