求解最小费用最大流问题：例题分析

上一节讨论了寻求网络中的最大流问题，然而在实际生活中，涉及“流”的问题时，人们考虑的还不只是流量，还有“费用”的因素，本节介绍的最小费用最大流问题就是这类问题之一。

给定网络D=（V，A，C），在每一条弧（vi，vj）∈A上，除了已给容量 cij外，还给了一个单位流量的费用 b（vi，vj）≥0（简记为bij）。所谓最小费用最大流问题就是要求一个最大流f，使流的总输送费用

取极小值。

下面介绍解决这个问题的一种方法。

由上节可知，寻求最大流的方法就是从某个可行流出发，找到关于这个流的一条增广链μ 。沿着μ 调整f，对新的可行流试图寻求关于它的增广链，如此反复直至最大流。现在要寻求最小费用的最大流。首先考查一下，当沿着一条关于可行流f的增广链μ，以θ=1调整f，得到新的可行流f′时（显然，v（f′）　=v（f）+1），b（f′）比 b（f）增加多少？不难看出

我们称为这条增广链μ的“费用”。

可以证明，若f 是流量为v（f）的所有可行流中的费用最小者，而μ 是关于f的所有增广链中费用最小的增广链，那么沿μ 去调整f，得到的可行流f′，就是流量为v（f′）的所有可行流中的最小费用流。这样，当f′是最大流时，它也就是所要求的最小费用最大流了。

注意到，由于bij≥0，所以f=0必是流量为0的最小费用流，这样，总可以从f=0开始。一般地，设已知f 是流量 v（f）的最小费用流，余下的问题就是如何去寻求关于f的最小费用增广链。为此，可构造一个赋权有向图 W（f），它的顶点是原网络D的顶点，而把D中的每一条弧（vi，vj）变成两个相反方向的弧（vi，vj）和（vj，vi）。定义 W（f）中弧的权 wij为：

于是在网络D中寻求关于f的最小费用增广链就等价于在赋权有向图 W（f）中，寻求从 vs到vt的最短路。因此有如下算法：

开始取f（0）=0，一般情况下，若在第k-1步得到最小费用流f（k-1），则构造赋权有向图W（f（k-1）），并在W（f（k-1））中，寻求从 vs到 vt的最短路。若不存在最短路（即最短路权是+∞），则f（k-1）就是最小费用最大流；若存在最短路，则在原网络D中得到相应的增广链μ，在增广链μ 上对f（k-1）进行调整。调整量为：

(www.xing528.com)

得到新的可行流 f（k），再对 f（k）重复上述步骤。

例6-14　以图6-28 为例，求最小费用最大流，弧旁数字为（bij，cij）。

图6-28

（1）取 f（0）=0为初始可行流。

（2）构造赋权有向图W（f（0）），并求出从 vs到 vt的最短路（vs，v2，v1，vt），如图6-29（a）（双箭头为最短路）。

（3）在原网络D中，与这条最短路相应的增广链为μ=（vs，v2，v1，vt）。

（4）在μ 上进行调整，θ=5，得f（1）（图6-29（b））。

按照上述算法依次得 f（1），f（2），f（3），f（4），流量依次为5，7，10，11；构造相应的赋权有向图为W（f（1）），W（f（2）），W（f（3）），W（f（4）），如图6-29 所示。

图6-29

注意到W（f（4））中已不存在从 vs到 vt的最短路，所以 f（4）为最小费用最大流。