A note on cycling in the simplex method
作者:
K. T. Marshall,
J. W. Suurballe,
期刊:
Naval Research Logistics Quarterly
(WILEY Available online 1969)
卷期:
Volume 16,
issue 1
页码: 121-137
ISSN:0028-1441
年代: 1969
DOI:10.1002/nav.3800160110
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractAlthough 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 sh
点击下载:
PDF
(641KB)
返 回