\pdfpagewidth=8.5truein  \pdfpageheight=11truein
\hsize=6truein  \vsize=9truein
\pdfhorigin=1.25truein  \pdfvorigin=1truein

\def\itemitemitem{\par\indent \hangindent3\parindent \hskip\parindent \textindent}

\headline={\hfil}  \footline={\hfil}

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

\centerline{\bf Analysis of a simplex tableau}
\centerline{(ignoring degeneracy)}

\bigskip

\noindent Is the corresponding solution {\bf optimal?}

\smallskip

\item{$\bullet$} If there is a negative number in the objective row: {\bf No,}
the corresponding solution is not optimal. (Increasing the value of the
corresponding variable will increase the objective value.)

\smallskip

\item{} In this case: Is the problem {\bf unbounded?}

\smallskip

\itemitem{$\circ$} If any negative entry in the objective row has no positive
numbers above it: {\bf Yes,} the problem is unbounded. (The value of the
corresponding variable can be made arbitrarily large in such a way that no
constraints are violated, and this will make the objective value arbitrarily
large as well.)

\smallskip

\itemitem{$\circ$} If all negative entries in the objective row have at least
one positive number above them: {\bf No conclusion.} (The objective value can
be increased by pivoting on a column with a negative entry in the objective
row. This will lead to a new tableau. Then analyze the new tableau.)

\smallskip

\item{$\bullet$} If all numbers in the objective row are nonnegative:
{\bf Yes,} the corresponding solution is optimal. (No variable can be increased
to increase the objective value.)

\smallskip

\item{} In this case: Is this optimal solution {\bf unique?}

\smallskip

\itemitem{$\circ$} If all nonbasic columns have positive entries in the
objective row: {\bf Yes,} the optimal solution is unique. (Bringing any
nonbasic variable into the basis will decrease the objective value.)

\smallskip

\itemitem{$\circ$} If there is a nonbasic column with a zero in the objective
row: {\bf No,} the optimal solution is not unique. (The value of the
corresponding variable can be increased to get a different optimal solution.)

\smallskip

\itemitem{} In this case: Is there {\bf another optimal $\underline{\bf basic}$
solution?}

\smallskip

\itemitemitem{--} If there is a nonbasic column with a zero in the objective
row and at least one positive number above it: {\bf Yes,} there is another
optimal basic solution. (Pivoting on this column will produce it.)

\smallskip

\itemitemitem{--} If none of the nonbasic columns having zero in the objective
row have positive numbers above: {\bf No,} there is no other optimal basic
solution. (But there are still infinitely many optimal solutions---the set of
optimal solutions forms an infinite ray extending from the optimal basic
solution.)

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

\bye
