有上下界网络最大流与最小截问题

Problem of Maximum Flow & Minimum Cut Set of Network with Lower & Upper Arc Capacities

为了便于建立与有上下界网络最大流与最小截问题有关的决策支持系统,本文给出一个求有上下界网络最大流与最小截的数值算法,证明了算法的理论依据,并举例说明了算法在堵塞流理论中的应用。该算法能判定问题是否有可行解,在问题有可行解的情况下能求得问题的最优解。该算法具有易于编程实现、收敛性好等优点。数值实验表明该算法有较高的计算效率,可用于求解最小饱和流问题。

For convenience to build decision support system relative to the problem of maximum flow ＆ minimum cut set of network with lower ＆ upper arc capacities, a numerical algorithm for finding maximum flow ＆ minimum cut set in network with lower ＆ upper arc capacities, is proposed in this paper. The theory, on which the algorithm is based, is strictly proved. And the application of the algorithm to blocking flow theory is illustrated with an exampie. The algorithm can judge whether the problem has a feasible solution or not, which can find the optimal solution to the problem while a feasible solution exists, and has good performance in the sense of being implemented on computer, convergence, etc. Numerical experiments demonstrate that the algorithm is an efficient and robust method to solve the problem, which can still be used to solve the minimum saturated flow problem.