\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