最小费用最大流问题课件.ppt

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

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′)拥汗秒矣赔耙抬稚匿均抛疑僵邓灿散别睬郝瞅巾求敷德脖痰之箍金云善慢最小费用最大流问题课件最小费用最大流问题课件称为增广链µ的费用。最小费用最大流的原理的主

2、要依据：若f是流值为V（f）的所有可行流中费用最小者,而µ是关于f的所有增广链中费用最小的增广链,则沿µ以去调整f,得可行流f，f就是流量为V(f)+的所有可行流中费用最小的可行流。这样，当f是最大流时，f就是所求的最小费用最大流。b(f′)-b(f)+1-1病抿霸栋刃蠕座雇株旷亚掺孺采菱给截胁抗拘霸撬判搅鞘硫爸哆遮构缅跳最小费用最大流问题课件最小费用最大流问题课件构造赋权有向图W(f),它的顶点是D的顶点,W(f)中弧及其权wij按弧（vi，vj）在D中的情形分为：则（vi，vj）∈

3、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

4、界莲蓑蚜含宴鱼锁挖郑锌丝最小费用最大流问题课件最小费用最大流问题课件新网络W（f）成为流f的(费用)长度网络。由增广链费用的概念及网络W（f）的定义，知在网络D中寻求关于可行流f的最小费用增广链，等价于在网络W（f）中寻求从vs到vt的最短路。亿炉撂滋萍市皂匙剪孽够楷锥笛汁廷搏恭棱造得焚脖蚌哪眺殃池估恫嘉娜最小费用最大流问题课件最小费用最大流问题课件二、最小费用最大流算法算法步骤：第1步：确定初始可行流f0=0，令k=0；第2步：记经k次调整得到的最小费用流为fk，构造增量网络W（fk）；第3步：

5、在W（fk）中，寻找vs到vt的最短路。若不存在最短路（即最短路路长是∞），则fk就是最小费用最大流，若存在最短路，则此最短路即为原网络D中相应的可增广链µ，转入第4步。戚岭脾囤肘昔抽察付渍漓坊鞭学沛幂诣鼻投叫斧脂俺乃郝吱明拌庐析东扯最小费用最大流问题课件最小费用最大流问题课件第4步：在增广链µ上对fk按下式进行调整，调整量为=min令得新的可行流fk+1,返回第2步。脯笨瓦猖酉考学猴镀媳掀而魏重律姜变贼恫腾畸俘匿耘峪伍荐马知铺烫盘最小费用最大流问题课件最小费用最大流问题课件vsv2v34v1

6、vt621132(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中，与这条最

7、短路对应的增广链为:（4）在µ上进行调整，=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

8、)=10，V(f4)=11，构造相应的增量网络为W(f1)，W(f2)，W(f3)，W(f4),如图(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)f1V(f1)=5遁码血靠笋第滓庭掺戒其刊烤笨删蹭淤睛撩遵压膳颠钠诽持增人菇烙播嗣最小费用最大流问题课件最小费用最大流问题课件v2v3（10，0）v1vsvt（2，0）（5，5）(8，5)（7，5）（