最小费用最大流问题课件

《最小费用最大流问题课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五节最小费用最大流问题网络D=（V，A，C）,每一弧（vi，vj）∈A，给出（vi，vj）上单位流的费用b(vi，vj)≥0，（简记bij）。最小费用最大流问题：求一个最大流f，使流的总费用取最小值。一、求解原理设对可行流f存在增广链µ，当沿µ以=1调整f，得新的可行流f'时，(显然V(f')=V(f)+1)，两流的费用之差b(f)-b(f′)称为增广链µ的费用。最小费用最大流的原理的主要依据：若f是流值为V（f）的所有可行流中费用最小者,而µ是关于f的所有增广链中费用最小的增广链,则沿µ以去调整f,得可行流f，f就是流量为V(f)+的所有可行流中费用

2、最小的可行流。这样，当f是最大流时，f就是所求的最小费用最大流。b(f′)-b(f)+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，vj)∈A，且fij=cij(饱和弧),费用若（vi，vj）∈A，且0＜fij

3、（vi，vj）∈W（f），且wij=bij及（vj，vi）∈W（f），且wji=-bijvjvi4vivj-4新网络W（f）成为流f的(费用)长度网络。由增广链费用的概念及网络W（f）的定义，知在网络D中寻求关于可行流f的最小费用增广链，等价于在网络W（f）中寻求从vs到vt的最短路。二、最小费用最大流算法算法步骤：第1步：确定初始可行流f0=0，令k=0；第2步：记经k次调整得到的最小费用流为fk，构造增量网络W（fk）；第3步：在W（fk）中，寻找vs到vt的最短路。若不存在最短路（即最短路路长是∞），则fk就是最小费用最大流，若存在最短路，则此最短路即为原网

4、络D中相应的可增广链µ，转入第4步。第4步：在增广链µ上对fk按下式进行调整，调整量为=min令得新的可行流fk+1,返回第2步。vsv2v34v1vt621132(a)w(f0)例求下图所示网络的最小费用最大流。弧旁数字为（bij，cij）。v2v3（4，10）v1vsvt（6，2）（2，5）(1，8)（1，7）（3，10）(2，4)解：（1）取初始可行流f0=0；（2）按算法要求构造长度网络W（f0），求出从vs到vt的最短路。（3）在原网络D中，与这条最短路对应的增广链为µ=（vs，v2，v1，vt）。（3）在原网络D中，与这条最短路对应的增广链为:（4

5、）在µ上进行调整，=5，得f1，如图（b）所示。v2v3（10，0）v1vsvt（2，0）（5，0）(8，0)（7，0）（10，0）(4，0)µ=（vs，v2，v1，vt）v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)（7，5）（10，0）(4，0)(b)f1按照上述算法依次得f1，f2，f3，f4，流量依次为V(f1)=5，V(f2)=7，V(f3)=10，V(f4)=11，构造相应的增量网络为W(f1)，W(f2)，W(f3)，W(f4),如图(a),(e),(g),(i)所示。vsv2v34v1vt621132(a)w(f0)v2v3（10

6、，0）v1vsvt（2，0）（5，5）(8，5)（7，5）（10，0）(4，0)(b)f1V(f1)=5v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)（7，5）（10，0）(4，0)(b)f1v2v3（10，2）v1vsvt（2，0）（5，5）(8，5)（7，7）（10，0）(4，0)(d)f2V(f2)=7vt2v2v3v1vs6-2-1-13W（f（1））（c）411v2v3（10，2）v1vsvt（2，0）（5，5）(8，5)（7，7）（10，0）(4，0)(d)f2V(f2)=7w(f2)(e)v1vs-1v2v3-46-2-1341vt2

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

8、t的最短路