On the simplex algorithm for networks and generalized networks
On the simplex algorithm for networks and generalized networks
复制标题
关于网络和广义网络的单纯形算法
DOI：
10.1007/bfb0121050
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
J. Orlin
中科院分区：
文献类型：
--
作者：
J. Orlin
我们考虑单纯形算法应用于有向图G=(V，E)上的最小费用网络流。首先，我们考虑Elam，Goverer和Klingman的强收敛枢轴规则应用于广义网络。我们证明了这个枢轴规则与Dantzig的词典编纂规则在离开基变量的选择上是等价的。我们还证明了广义网络流问题的每个基B所满足的单调性。如果b‘≤b≤b*，如果L≤B−1b’，B−1b*≤u，则L≤B−1b≤u；即如果b‘和b*的基是可行的，那么b也是可行的。接下来，我们考虑丹齐格的枢轴法则，即选择折合成本最小的进入变量，并使用词典编纂来避免循环。我们证明了Dantzig枢轴规则应用于指派问题或最短路径问题时，最大枢轴个数为O(|V|2|E|log|V|)。此外，最小费用网络流问题的最大连续退化支点个数为O(|V|2|E|log|V|)。
We consider the simplex algorithm as applied to minimum cost network flows on a directed graph, G=(V, E). First we consider the strongly convergent pivot rule of Elam, Glover, and Klingman as applied to generalized networks. We show that this pivot rule is equivalent to Dantzig’s lexicographical rule in its choice of the variable to leave the basis. We also show the following monotonicity property that is satisfied by each basis B of a generalized network flow problem. If b′≤b≤b * and if l≤B −1 b′, B −1 b *≤u, then l≤B −1 b≤u; i.e., if a basis is feasible for b′ and b * then it is feasible for b. Next we consider Dantzig’s pivot rule of selecting the entering variable whose reduced cost is minimum and using lexicography to avoid cycling. We show that the maximum number of pivots using Dantzig’s pivot rule is O(|V|2|E| log |V|) when applied to either the assignment problem or the shortest path problem. Moreover, the maximum number of consecutive degenerate pivots for the minimum cost network flow problem is O(|V|2|E|log|V|).