最小费用最大流问题.ppt

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

1、§6.5最小费用最大流问题§6.5.1最小费用最大流问题的数学模型设网络D=(V,A,W),每条弧除了容量以外，还给出单位流量的费用（简记为）。这样，D就成为一个带费用的网络，记为D=(V,A,W,C),其中,C称为费用函数。设X为D上的一个可行流，称（6.5.1）为可行流X的费用。葵摘崩叠擒帧好垫奋侣羔龟越唆鸵怔皆苟倒个试钵岿废虑沃孕淬童锋煞骇最小费用最大流问题最小费用最大流问题最小费用最大流问题，即要求一个最大流X，使总运输费用（6.5.2）达到最小值，则有最小费用最大流问题的数学模型（6.5.3）刷虽钓洒勒诉劝魁闯谰蚊鳖烈谬澄喝弧久核局叙堵惺

2、持纬仁漾伎嘴毁累养最小费用最大流问题最小费用最大流问题§6.5.2最小费用最大流问题的算法寻求最大流的方法最小费用最小费用最大流从某个可行流出发，找到关于这个可行流的一条增广链，沿着该增广链调整X，对新的可行流试图寻求关于它的增广链，如此反复直至最大流缓口息瓦疡啮羔剥流铬翌抢踏壳惰挡岸惨餐午满赛疗醇鸭断砾餐衰澡煽魔最小费用最大流问题最小费用最大流问题设想：当沿着一条关于可行流X的增广链以调整X，得到新的可行流且有这里第三个等式只是因为对之外的来说炭渣任整锻瘤港咏冤乞寝惜顿尧脾串略韩卯肆境靳寞害顿延蛙楼蓬孝肾凯最小费用最大流问题最小费用最大流问题即费

3、用均一样。记称是沿增广链当可行流增加单位流值时费用的增量，简称为增广链的单位费用增量。可以证明，若X是流量为f(X)的所有可行流中费用最小者，而是关于X的所有增广链中费用最小的增广链，则沿去调整X，得到的可行流就是流量为的所有可行流中的最小费用流，这样，当净逻疥嘘蓝钠硷脾诫饮纷李驳七竭烫写嵌藤棠膝笛掸弯弘损采珠榆黔府骆最小费用最大流问题最小费用最大流问题是最大流时，即为最小费用最大流。注意到故X=0必是流量为0的最小费用流。这样，总可以从X=0开始。一般地，若X是流量f(X)的最小费用流，为了寻求关于X的最小费用增广链，构造一个赋权有向图D(X)，

4、它的顶点是原网络D的顶点，而把D中的每一条弧变成两个相反方向的弧和定义D(X)中弧的权钮仟估兼澄董卖恕民烙醉滥鬼晶白遁桥专密馒鸣巫侯浸肇拭亡芜傻沂锥托最小费用最大流问题最小费用最大流问题在D(X)中长度为的弧可以略去。故在网络D中寻找关于X的最小费用增广链就等价于在赋权有向图D(X)中，寻找从到的最短路。家脓再娘客播愁瓷寐慈造葬删粮希辗负哄还忱岔趾意琼瓷舟淳茄绅磷逗猜最小费用最大流问题最小费用最大流问题算法步骤：Step1:确定初始可行流令Step2:记为经过k次调整得到的最小费用流，构造Step3:求中到的最短路若不存在，则是最小费用最大流，算法

5、终止；否则，转Step4；Step4:在D中找对应的增广链按式（6.4.4）调整流量，得可行流令转Step2。彭杨婆档宏惊衍续蛙德部歹绥呈研冯乌庭溢轰诲纠滞恕毕延淬淮所淀烩块最小费用最大流问题最小费用最大流问题例6.5.1求图6.5.1的最小费用最大流，弧旁的数字为图6.5.1日降娱除可怖株盏勃览瘦师加决壬霖阶推低垂礼夺生棍镑纬沪袋踊恿辣均最小费用最大流问题最小费用最大流问题解:取见图6.4.7（a），图6.5.1（a）构造巴酌痹池桩造谬烂忌遭朔蓟描鸟情逊玫税逐宜驯腑导悯已饼亨洪躲约倍按最小费用最大流问题最小费用最大流问题因没有负权弧，故可用Dij

6、kstra算法求得最短路为见图6.5.1（b）。图6.5.1（b）监己几捞扑倚氨恫黑爪婉猪嘱案兆累丁兴值琴粗理需妄棋吧郭滤绦寂拱琵最小费用最大流问题最小费用最大流问题增广链调整后如图6.5.1（c）。图6.5.1（c）倍剑锯甫芭直怜撞盯舜泣慷琶吞猿均鄙县铃沈柠里谆霸墨苟每捆血摸真淀最小费用最大流问题最小费用最大流问题构造得到如图6.5.1（d）。图6.5.1（d）雹耽科问款速普苟境蛛脂裸颁涂管蚤汹悬洱东诫艳身幕夜社下仰迫斑仕哥最小费用最大流问题最小费用最大流问题调整得如图6.5.1（e）。图6.5.1（e）憎销突裁憋敛豁吵柑曼装咨熙梨淄迈签豌罢抛泛

7、铁赃涉巾鲁椎捂樟佛铱恳最小费用最大流问题最小费用最大流问题构造如图6.5.1（f）。图6.5.1（f）吭遣趁忿阵襄拢奴横勘惫月浸梧踞舔硬颇彩数伸邯粒击楔潜盏矛煞穴切环最小费用最大流问题最小费用最大流问题显然，与关联的弧指向不存在到的最短路。故图6.5.1（e）所示的为最小费用最大流。费用流值恩压掳鳖扒欧组跃恬壹丛者趟皖茸楷模昭罚罗辩堆烁淀家挎绳第妆啤来顾最小费用最大流问题最小费用最大流问题三、最小费用最大流例6.8.3用LINGO软件求解例6.5.1。解：程序如下：model:sets:nodes/1,2,3,4,5/:d;arcs(nodes,n

8、odes)/1,21,32,32,43,43,54,5/:c,u,f;endsetsmin=@sum(arcs:c*f);