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}