Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

• Forgot your password?
• Apply for membership

1. • CommentRowNumber1.
   • CommentAuthorMurat_Aygen
   • CommentTimeSep 21st 2018
   • (edited Sep 22nd 2018)
   • PermaLink
   Author: Murat_Aygen
   Format: MarkdownItexCycling 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}

   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}

2. • CommentRowNumber2.
   • CommentAuthorTodd_Trimble
   • CommentTimeSep 21st 2018
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexFunny, I don't think we have anything on the simplex algorithm (in the sense pioneered by George Dantzig) in the nLab, and it's not really in the direction of our principal interests. So why write here?

   Funny, I don’t think we have anything on the simplex algorithm (in the sense pioneered by George Dantzig) in the nLab, and it’s not really in the direction of our principal interests. So why write here?

3. • CommentRowNumber3.
   • CommentAuthorRichard Williamson
   • CommentTimeSep 21st 2018
   • (edited Sep 21st 2018)
   • PermaLink
   Author: Richard Williamson
   Format: MarkdownItexMurat's [previous contributions](https://nforum.ncatlab.org/search/?PostBackAction=Search&Type=Discussions&Advanced=1&Keywords=&Categories%5B%5D=&AuthUsername=Murat_Aygen&btnSubmit=Search) are a bit suspicious. I am enormously sorry if this is unfounded, but could you confirm, Murat, that you are an actual person writing this with the purposes of finding out something, and let us know a bit about what you had in mind in #1?

   Murat’s previous contributions are a bit suspicious. I am enormously sorry if this is unfounded, but could you confirm, Murat, that you are an actual person writing this with the purposes of finding out something, and let us know a bit about what you had in mind in #1?

4. • CommentRowNumber4.
   • CommentAuthorDavidRoberts
   • CommentTimeSep 22nd 2018
   • (edited Sep 22nd 2018)
   • PermaLink
   Author: DavidRoberts
   Format: MarkdownItexThe comments here work using markdown, not LaTeX. I'm particular, that means that using the TeX commands for opening quotes messes things up. If this is a serious question/comment, why not edit it to make it less like source code? Otherwise it looks like cut and paste from some .tex file...

   The comments here work using markdown, not LaTeX. I’m particular, that means that using the TeX commands for opening quotes messes things up. If this is a serious question/comment, why not edit it to make it less like source code? Otherwise it looks like cut and paste from some .tex file…

5. • CommentRowNumber5.
   • CommentAuthorMurat_Aygen
   • CommentTimeSep 22nd 2018
   • PermaLink
   Author: Murat_Aygen
   Format: TextDear Mr. Williamson, my “previous” and present remarks are both topics/findings of my Ph.D. dissertation accepted by Ankara University (Turkey) on May 2018. I have not yet enough time to translate it to English in full. Sincerely Yours.

   Dear Mr. Williamson, my “previous” and present remarks are both topics/findings of my Ph.D. dissertation accepted by Ankara University (Turkey) on May 2018. I have not yet enough time to translate it to English in full. Sincerely Yours.
6. • CommentRowNumber6.
   • CommentAuthorRichard Williamson
   • CommentTimeSep 22nd 2018
   • (edited Sep 22nd 2018)
   • PermaLink
   Author: Richard Williamson
   Format: MarkdownItexDear Dr.Aygen, thank you for joining in, much appreciated! It may be due to language difficulties, but it is a little difficult to understand the purpose of these posts. Is it that you are looking for feedback? That would be absolutely fine if the topic is loosely to do with things typically discussed here (which many things are, and in particular the topic of your post here may well be). In such a case, may I suggest that rather than just copy and paste bits of your thesis, that you add some kind of informal introductory sentence or two, and that you edit the content so that it displays correctly (if you use the 'Markdown + Itex' option, a good deal of LaTeX is supported, but not everything)?

   Dear Dr.Aygen, thank you for joining in, much appreciated! It may be due to language difficulties, but it is a little difficult to understand the purpose of these posts. Is it that you are looking for feedback? That would be absolutely fine if the topic is loosely to do with things typically discussed here (which many things are, and in particular the topic of your post here may well be). In such a case, may I suggest that rather than just copy and paste bits of your thesis, that you add some kind of informal introductory sentence or two, and that you edit the content so that it displays correctly (if you use the ’Markdown + Itex’ option, a good deal of LaTeX is supported, but not everything)?

7. • CommentRowNumber7.
   • CommentAuthorTodd_Trimble
   • CommentTimeSep 22nd 2018
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexYeah, we really don't have anything on linear programming here in the nLab, although it's not too far away from some topics we do discuss (convexity, etc.). There may be some nPOV potential though in discussing some of the fundamental results (Farkas's lemma, duality). All that said, I can't help but think that some of the questions from Dr. Aygen would get a better response at Mathematics StackExchange or MathOverflow.

   Yeah, we really don’t have anything on linear programming here in the nLab, although it’s not too far away from some topics we do discuss (convexity, etc.). There may be some nPOV potential though in discussing some of the fundamental results (Farkas’s lemma, duality).

   All that said, I can’t help but think that some of the questions from Dr. Aygen would get a better response at Mathematics StackExchange or MathOverflow.

8. • CommentRowNumber8.
   • CommentAuthorAli Caglayan
   • CommentTimeSep 22nd 2018
   • PermaLink
   Author: Ali Caglayan
   Format: MarkdownItexI can translate Turkish if it is needed.

   I can translate Turkish if it is needed.