最新最小费用最大流问题课件

1、 第五节 最小费用最大流问题 网络网络d=（v，a，c）,每一弧（每一弧（vi，vj）a，给，给出（出（vi，vj）上单位流的费用）上单位流的费用b(vi，vj)0，（简记，（简记bij）。）。 最小费用最大流问题：最小费用最大流问题： 求一个最大流求一个最大流 f，使流的总费用，使流的总费用 a),( )( jivvijijf bfb取最小值。取最小值。一、求解原理一、求解原理 设对可行流设对可行流 f 存在增广链存在增广链 ，当沿，当沿 以以 =1调整调整f，得新的可行流得新的可行流 f 时，时，(显然显然 v(f )=v(f )+1)，两流的费，两流的费用之差用之差 b( f )-b(

2、f) ) () ( ijijijijijijffbffb称为增广链称为增广链 的费用。的费用。最小费用最大流的原理的主要依据：最小费用最大流的原理的主要依据： 若若f 是流值为是流值为v（f ）的所有可行流中费用最小者）的所有可行流中费用最小者,而而 是关于是关于f 的所有增广链中费用最小的增广链的所有增广链中费用最小的增广链,则沿则沿 以以 去调整去调整 f ,得可行流得可行流 f ，f 就是流量为就是流量为v(f )+ 的所有可行流中费用最小的可行流。这样，当的所有可行流中费用最小的可行流。这样，当 f 是是最大流时，最大流时， f 就是所求的最小费用最大流。就是所求的最小费用最大流。b(

3、 f ) -b( f ) ijijbb+1-1 构造赋权有向图构造赋权有向图w( f ),它的顶点是它的顶点是d的顶点的顶点,w(f )中中弧及其权弧及其权wij 按弧（按弧（vi，vj）在在d中的情形分为：中的情形分为：则（则（vi，vj）w（f ）,且且wij= bij则（则（ vj ， vi ）w（f ）,且且wji= - bijvjvi4vj4vi3.0vjvi5.53vivj-3 如果已知如果已知 f 是流量为是流量为v（f ）的最小费用流，）的最小费用流， 求求出关于出关于f 的最小费用增广链。的最小费用增广链。若（若（vi，vj）a，且，且fij=0(零弧），零弧），若若(vi，

4、vj )a，且，且fij=cij(饱和弧饱和弧),费用费用若（若（vi，vj）a，且，且0fijcij vj4vi3.2则（则（vi，vj）w（f ），且），且wij= bij 及（及（ vj ， vi ）w（f ），且），且wji= - bijvjvi4vivj-4新网络新网络w（f ）成为流）成为流f 的的(费用费用)长度网络。长度网络。由增广链费用的概念及网络由增广链费用的概念及网络w（f ）的定义，知）的定义，知 在网络在网络d中寻求关于可行流中寻求关于可行流f 的最小费用增广链，的最小费用增广链，等价于在网络等价于在网络w（f ）中寻求从）中寻求从vs到到vt的最短路。的最短路。二、

5、最小费用最大流算法二、最小费用最大流算法算法步骤：算法步骤：第第1步：确定初始可行流步：确定初始可行流f 0 =0，令，令k=0；第第2步：记经步：记经 k 次调整得到的最小费用流为次调整得到的最小费用流为f k，构造，构造 增量网络增量网络w（f k）；）；第第3步：在步：在w（f k）中，寻找）中，寻找vs到到vt的最短路。若不存的最短路。若不存 在最短路（即最短路路长是在最短路（即最短路路长是），则），则f k 就是就是 最小费用最大流，若存在最短路，则此最短最小费用最大流，若存在最短路，则此最短 路即为原网络路即为原网络d中相应的可增广链中相应的可增广链，转入第，转入第 4步。步。 第

6、第4步：在增广链步：在增广链上对上对f k 按下式进行调整，调整量按下式进行调整，调整量 为为 = minkijkijij fmin) , -f(cmin -令令 uvv fuvvf u v,v ffjikijjikijjikijkij ),( ),( )( -1得新的可行流得新的可行流f k+1 , 返回第返回第2步。步。 vsv2v34v1vt621132(a) w(f0)例例 求下图所示网络的最小费用最大流。弧旁数字为求下图所示网络的最小费用最大流。弧旁数字为 （bij，cij）。）。v2v3（4，10）v1vsvt（6，2）（2，5）(1，8)（1，7）（3，10）(2，4)解：（解：

7、（1）取初始）取初始可行流可行流f 0 = 0； （2）按算法要求构造）按算法要求构造长度网络长度网络w（f 0 ），），求出从求出从vs到到vt的最短路。的最短路。（3）在原网络）在原网络d中，与中，与这条最短路对应的增广这条最短路对应的增广链为链为 =（vs，v2，v1，vt）。）。 （3）在原网络）在原网络d中，中， 与这条最短路对应与这条最短路对应 的增广链为的增广链为 : （4）在）在上进行调整，上进行调整， = 5，得，得f 1 ， 如图（如图（b）所示。）所示。v2v3（10，0）v1vsvt（2，0）（5，0）(8，0)（7，0）（10，0）(4，0) =（vs，v2，v1，v

8、t）v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)（7，5）（10，0）(4，0)(b) f 1 按照上述算法依次得按照上述算法依次得f 1 ，f 2 ，f 3 ，f 4 ，流量依次，流量依次为为v(f 1)=5，v(f 2)=7，v(f 3)=10，v( f 4)=11， 构造相应构造相应的增量网络为的增量网络为w(f 1)，w(f 2)，w(f 3)，w( f 4), 如图如图(a), (e), (g), (i)所示。所示。vsv2v34v1vt621132(a) w(f0)v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)（7，5）（10，0）(4，0)(b)

9、 f 1v(f 1 ) = 5v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)（7，5）（10，0）(4，0)(b) f 1v2v3（10，2）v1vsvt（2，0）（5，5）(8，5)（7，7）（10，0）(4，0)(d) f 2 v( f 2)=7vt2v2v3v1vs6-2-1-13w（f （1） （c）411v2v3（10，2）v1vsvt（2，0）（5，5）(8，5)（7，7）（10，0）(4，0)(d) f 2 v( f 2)=7 w(f 2 ) (e)v1vs-1v2v3-46-2-1341vt2v2v3（10，2）v1vsvt（2，0）（5，5）(8，8)（7，7

10、）（10，3）(4，3)(f) f 3 v( f 3)=10v2v3（10，2）v1vsvt（2，0）（5，5）(8，8)（7，7）（10，3）(4，3)(f) f 3 v( f 3)=3vt2v2v3-4v1vs6-2-1-13(g) w( f 3) 4-3-2v2v3（10，3）v1vsvt（2，0）（5，4）(8，8)（7，7）（10，4）(4，4)(h) f 4 v( f 4)=11 图（图（i）中，不存在从）中，不存在从vs到到vt的最短路，所以的最短路，所以f 4为为最小费用最大流。最小费用最大流。问题：（问题：（1）如何求网络）如何求网络w（f k）中的）中的vs到到vt最短路？

11、最短路？ （2）如何判断无）如何判断无vs到到vt的最短路？的最短路？v2v3（10，3）v1vsvt（2，0）（5，4）(8，8)（7，7）（10，4）(4，4)(h) f 4 v( f 4)=11vt-2v2v3-4v1vs6-2-1-13（i） w（f 4） 4-32作业：作业：1. 用标号法求下网络中从点用标号法求下网络中从点v1到到v7的最大流。的最大流。v1 v2v3v4v5v6v7693742513476每条弧旁的数字为该段弧的容量。每条弧旁的数字为该段弧的容量。上面网络中弧表示单行道，试确定上面网络中弧表示单行道，试确定v2v3段道路的方向。段道路的方向。2. 求下图所示网络的

12、最小费用最大流求下图所示网络的最小费用最大流,每弧旁的数每弧旁的数字是字是( bij . cij ) 。(1,4)vsvt(3.5)(2.1)(4,2)(2.1)3.3)(2.5)(1.3)(4.2) 3.下表给出某运输问题的产销平衡表与单位运价下表给出某运输问题的产销平衡表与单位运价表。将此问题转化为最小费用最大流问题，画出网表。将此问题转化为最小费用最大流问题，画出网络图并求数值解。络图并求数值解。产地 销地123产量ab2030242252087销量456不受容量限制，最小总费用为不受容量限制，最小总费用为240 。sba321t(22,7)(24,8)(5,8)(30,7)(0,5)(0,6)(20,8)(0,7)(0,4)(20,8)(0,8)弧旁数字为弧旁数