Theoretical Properties of the Network Simplex Method
Theoretical Properties of the Network Simplex Method
复制标题
网络单纯形法的理论性质
DOI：
--
复制
发表时间：
1979
影响因子：
1.7
通讯作者：
W. Cunningham
中科院分区：
文献类型：
--
作者：
W. Cunningham
给出了网络单纯形法中循环的例子，并证明了其发生的一些限制。还给出了“停顿”的示例（没有循环的连续简并枢轴的指数长序列），并且显示了两种防止循环的方法来承认停顿。描述了防止循环和失速发生的旋转规则，并指出了一些计算优势。还描述了上限和对偶单纯形法的相关结果。
An example of cycling in the network simplex method is given and some restrictions on its occurrence are proved. An example of “stalling” (an exponentially long sequence of consecutive degenerate pivots without cycling) is also given, and two methods which prevent cycling are shown to admit stalling. Pivoting rules which prevent the occurrence of both cycling and stalling are described, and some computational advantages are noted. Related results for the upper-bounded and dual simplex methods are also described.