最小费用最大流的扩流问题

当网络的某些边（弧）容量可以在一定范围内增大时，它的最小费用最大流即发生改变．生产实践中（比如交通运输）常常是给定一个最大流的增流目标，而讨论如何确定边（弧）的最小变动上限以使新网络中的最大流为最小费用者．文献1]提出一个算法，但它只能在极特殊的情形下才适用，而且文中并没指出使用条件．这里我们给出一个适用于一般情况的算法．

The Augmenting Flow Problem of Maximal Flows For Minimal Cost

When capacity of some sides (arcs) in networks increase within a definite scope, its maximal flows for Min-cost will change. During the process of production and practice, one of problems is often that how to define minimal changing upper limit of sides (arcs) to produce maximal flows for Min-cost in new network, when the augmenting flow objective of a maximal now has been given. Literature 1] raised a kind of algorithms, but it only fit for very special case, and using condition didn' t be pointed out. In this paper we raise a kind of algorithms to fit for ordinary circumstances.