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]:

$\begin{array}{lr} max.& & & &+\frac{3}{4}x_{4} & -15x_{5} & +\frac{1}{2} x_{6} & - 6x_{7} & RHS \\ 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 \end{array}$$\qquad \qquad$ and nonnegativity constraints.

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}

]]>