最大流最小费用的一种简洁算法

一、引言 对于一个输运网络,已知发点的数目、位置和发量,收点的数目、位置和需求量,及网络中各边的容量,求使总运费最省的调度方案,这是线性规划解决的典型问题,Busacker与Gowen也就该问题将可行流与迭代、反圈法结合起来求解。 本文拟将图论中的求最短路径及求最大流的两种算法结合起来,提出该问题的一种简洁实用的解法。 本文的算法较线性规划解法与Busacker和Gowen的算法而言的优点在于:物理意义明确;可与图形显示系统结合起来进行流过程的动态模拟,形式更加简洁有效。

An Algrothm of Maximum Flow with Least-Cost

The problem is for a traffic network, given the numbers, positions and the amount of supply or re-quirment of original and terminal points, and given the capacity limit of each network line, how to find the optimal traffic plan with least traffic cost. The paper links two algrothms of shortest route and maximum flow to solve the problem. The algrothm consists of three continuous procedures: 1. Finding the shortest route between original and terminal points with the Dijkstra algrothm; 2. Labelling along the shortest route; and 3. Increasing the folw along the labelled shortest route. The three steps are to be repeated until the terminal point can not be labelled. The graphic algrothm can be related with dynamic chisplay system to simulate and analyse the transport flow and transport scheme.