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

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