A note on cycling in the simplex method

K. T. Marshall and J. W. Suurballe

Naval Research Logistics Quarterly, 1969, vol. 16, issue 1, 121-137

Abstract: Although cycling in the simplex method has long been known, a number of theoretical questions concerning cycling have not been fully answered. One of these, stated in [3], is to find the smallest example of cycling, and Beale's example with three equations and seven variables is conjectured to be the smallest one. The exact bounds on dimensions of cycling examples are established in this paper. We show that Beale's example is the smallest one which cycles at a non‐optimal solution, that a smaller one can cycle at the optimum, and that, in general (including the completely degenerate case), a cycling example must have at least two equations, at least six variables, and at least three non‐basic variables. Examples and geometries are given for the extreme cases, showing that the bounds are sharp.

Date: 1969
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800160110

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:16:y:1969:i:1:p:121-137

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().