Solutions that Simplex algorithm fails to find

[Murat Aygen]

Cycling is not a sort of breakdown that the Simplex algorithm occasionally does, but the sign of the existence of extraordinary solutions that assign positive values to more than $m$ decision-variables, where $m$ is the number of our structural constraints. Simplex, by its very nature, cannot find such solutions but is able to emit a signal of their existence by cycling.

Consider the classical example given by E. M. L. Beale\footnote{The coefficient of $x_{5}$ on the objective function is altered slightly for reasons that will soon be understood.} where $n=7$ and $m=3$ [see Bazaraa et al., p.176]:

\[
\left.
\begin{array}{lrrrrrrrr}
max. &     &     &     & +\frac{3}{4}x_{4} & -15x_{5} & +\frac{1}{2} x_{6} & - 6x_{7} & RHS   \\
\hline
ST: & +x_{1} & & &  +\frac{1}{4} x_{4} &   -8x_{5} &                      -x_{6} & +9x_{7} & = 0 \\
      & & +x_{2} & &  +\frac{1}{2} x_{4} & -12x_{5} &   -\frac{1}{2}x_{6} & +3x_{7} & = 0 \\
      & & & +x_{3} &                                  &                 &                     +x_{6} &               & = 1 \\
\hline
\multicolumn{6}{l}{and \quad nonnegativity \quad constraints.} \\
\end{array}
\right. \qquad
\]

As we all know, Simplex algorithm can assign positive values to at most three (basic) decision variables out of seven of this problem. Now let $\eta$ be a positive number. Then $x_{4}=\frac{2}{5}+\frac{112}{5}\eta$, $x_{5}=0+\eta$, $x_{6}=1$ and $x_{7}= \frac{1}{10}+\frac{4}{15} \eta$ is such an extraordinary solution that assigns positive values to four variables! The objective function accordingly assumes the unbounded value $(1+ \eta)/5$. Even if the third scarce resource is not tapped (i.e. $x_{3}=1$), it assumes the value $(0+\eta)/5$ which is again as big as we wish.  Hadn't we modified the objective function coefficient of $x_{5}$, it would come out as $-\infty$ in which case cycling must really be avoided. \\

This outcome is categorically different from the ``unbounded solutions'' we are familiar with. Let's define a ``sub-basis'' as the set of current basis' column vectors but the ``departing'' one. We already know something about such bases. For instance each row of the current basis' multiplicative inverse (discernible as a specific part of a specific row of the current Tableau) is the outward-normal (gradient) of the subspace spanned by such a sub-basis. In every cycling example given by Gass et al., and notably in the non-trivial one due to Nering and Tucker (p.310), there is a subspace spanned by such a sub-basis and perpendicular to the RHS vector! Moreover, if such a sub-basis can be extended to a basis that spans the associated subspace positively, then, in the case of a Product Mix Problem for instance, the manufacturer has attained some self-sufficiency to produce at least one product whose production is restrained by intangible constraints only. In the Portfolio Management Problem, the investor's ``credibility''..\\

\textbf{References}

\renewcommand*\labelenumi{[\theenumi]}

\begin{enumerate}
\item Bazaraa, M. S., Jarvis, J. J. \& Sherali, H. D., Linear Programming and Network Flows, Copyright \copyright 2010 by John Wiley \& Sons Inc. 
\item Beale, E. M. L., Cycling in the Dual Simplex Algorithm, Naval Research Logistics Quarterly 2(4), pp.269-276 December 1955
\item Gass, S. I. \& Vinjamuri, S., Cycling in linear programming problems, Computers \& Operations Research 31 (2004) 303-311
\end{enumerate}