\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 basic feasible solution {\bf optimal?}

\smallskip

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

\smallskip

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

\smallskip

\itemitem{$\circ$} If there exists a negative entry in the objective row having
no positive entries below it: {\bf Yes,} the linear program is unbounded. (The
value of the corresponding nonbasic 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 every negative entry in the objective row has at least
one positive entry below it: {\bf No conclusion.} (The objective value can be
increased by pivoting in a column having a negative entry in the objective row.
This will lead to a new tableau. Then analyze the new tableau.)

\smallskip

\item{$\bullet$} If all entries in the objective row are nonnegative:
{\bf Yes,} the corresponding basic feasible 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 (i.e., nonzero)
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 exists 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 exists a nonbasic column having a zero in the
objective row and at least one positive number below it: {\bf Yes,} there is
another optimal basic solution. (Pivoting in this column will produce it.)

\smallskip

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

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

\bye
