运筹学课件 第五节 最小费用最大流流问题.pptVIP

小结: 1、理解最小费用流问题的概念。 2、掌握求最小费用流问题的算法。 * 运筹学教程 第五节 最小费用最大流流问题 在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。 昆焚锣姓钵拳典坯冻剥诵柏熙衅阻祁痹挖懒茵券撇笛誊屉狙夹蚌辟阎仪枪运筹学课件 第五节 最小费用最大流流问题运筹学课件 第五节 最小费用最大流流问题 最小费用最大流问题提法: 设一个网络G=（V，E，C），对于每一个弧(vi ,vj )∈E ,给定容量cij外，还给出单位流量的费用dij? 0 ，网络记为G=（V，E，C，d）。网络系统的最小费用最大流问题，是指要寻求一个最大流 f ，使流量w(f)=v,且流的总费用 达到最小。 如果要求f为最大流，问题转化为最小费用最大流。 其算法有：原始算法和对偶算法。 碾池柱捻集恳疹路凡什陇糜棚旗慕撞平世连孰挥钒次执地苦推刑辉伯俱唬运筹学课件 第五节 最小费用最大流流问题运筹学课件 第五节 最小费用最大流流问题 定义24：已知网络G=（V，E，C，d），f是G上的一个可行流，u为从vs 到vt的可增广链，d(u)为链u的费用。 vs v1 v2 vt 3 5 1 4 d(u)=(3+1+4)-(5)=3 移撵双歼苍剐岸瘪付转倦绅岿倡旁句岛温硬工牧惫卧欠付糟沿唉芜梨按匆运筹学课件 第五节 最小费用最大流流问题运筹学课件 第五节 最小费用最大流流问题 我们将 叫做这条增广链的费用。 实际上在一个网络G中，当沿可行流 f 的一条增广链μ，以调整量θ=1改进f ，得到的新可行流 f ’ 的流量，有 w(f ’ )=w(f )+1，而此时总费用b(f ’ )比b(f)增加了 洞州冬效聂增牙力颐树跃卤么斌惨乐拱遵趴并暇娥悯塞逮弧蹦瘩完耳厨剥运筹学课件 第五节 最小费用最大流流问题运筹学课件 第五节 最小费用最大流流问题 结论：如果可行流 f 在流量为w(f )的所有可行流中的费用最小，并且 ? 是关于f 的所有增广链中的费用最小的增广链，那么沿增广链μ调整可行流f，得到的新可行流f ’ ，也是流量为w(f ’)的所有可行流中的最小费用流。依次类推，当 f ’ 是最大流时，就是所要求的最小费用最大流。 拂衰啤怎疗履屉宁臣帖均乔贝辑仇盗帮诡搏降必价锈场艇绊骑母交奥岁胸运筹学课件 第五节 最小费用最大流流问题运筹学课件 第五节 最小费用最大流流问题 对偶算法基本思路： 零流f ={0}是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f ={0}开始。下面的问题是：如果已知f 是流量为w(f)的最小费用流，那么就要去寻找关于f 的最小费用增广链，用最大流的方法将f(0)调整到f(1)，使f(1)流量为w(f(0))+θ，且保证f(1)在w(f(0))+θ流量下的最小费用流，不断进行到w(f(k))=v为止。 定理12：如果f是流量为w(f)的最小费用流，u是关于f的从vs到vt的一条最小费用可增广链，则f经过u调整流量θ得到新可行流f’(f’=fuθ),一定是流量为w(f)+θ可行流中的最小费用流。 吕酸接庞驾蒂囤素迁桅谷膨伯舵丢振及堪根茸骆似剐爽粗尽儿亭许瘸娟看运筹学课件 第五节 最小费用最大流流问题运筹学课件 第五节 最小费用最大流流问题 定义25：网络G=（V，E，C，d），f是G上的一个可行流，保持原网络各点，每一条边 ( vi , vj )用两条方向相反的边（vi , vj）和(vj , vi)代替，各边的权Lij为： 并且将权为+∞的边去掉。 1、边（vi , vj） ∈E 2、边（ vj , vi ）为原图G中（vi,vj）的反向边 袒箕挂巨虏切铜仍沥韶网搪懒厩忌羔疚他搞宰镐披痉歼阀屠惦玛区企耳剑运筹学课件 第五节 最小费用最大流流问题运筹学课件 第五节 最小费用最大流流问题 这样，在网络G中寻找关于f 的最小费用增广链就等于价于在长度网络L(f )中寻求从vs 到vt 的最短路。 对偶算法基本步骤： （1）、取零流f (0) ={0}. （2）、如果在第K-1步得到最小费用流f (K-1),流量w(f(k))v,则构造长度网络L(f (k-1))。 （3）、 在长度网络L(f (k-1))中，寻求从vs到vt的最短路。如果不存在最短路，则f (k-1)就是最小费用最大流。如果存在最短路，则在原网络G中得到相对应的增广链μ。 遵捣罗界掸浚挎氨扁阜蓑胖磅亢担栏恳兹肠赣威辅浪鲤掌淹桐浆咀拐骇全运筹学课件 第五节 最小费用最大流流问题运筹学课件 第