《6.-5最小费用最大流问题》由会员分享，可在线阅读，更多相关《6.-5最小费用最大流问题（34页珍藏版）》请在金锄头文库上搜索。
1、 第五节第五节 最小费用最大流问题最小费用最大流问题一、基本概念一、基本概念1 1、什么是最小费用最大流问题？、什么是最小费用最大流问题？对每一条弧都给出单位流量费用单位流量费用的容量网络 D=（V，A，B）（称为费用容量网络）中， 求取最大流X，使输送流量的总费用 C（X）=cijxij为最小的一类优化问题。其中，bij表示弧（vi，vj）上的容量，xij表示弧 （vi，vj）上的流量，cij表示弧（vi，vj）上通过单位流量所花费的费用。2 2、最小费用流、最小费用流对一费用容量网络，具有相同流对一费用容量网络，具有相同流 量量 f f 的可行流中，总费用最小的可行的可行流中，总费用最小的
2、可行流称为该费用容量网络关于流量流称为该费用容量网络关于流量 f f 的的最小费用流，简称最小费用流，简称流量为流量为 f f 的最小费的最小费用流。用流。从上节可知，寻求最大流的方法是从某个可行流出 发，找到关于这个流的一条增广链 。沿着调整f ，对新的可行流试图寻求关于它的增广链，如此反 复直至最大流。现在，要寻求最小费用的最大流， 我们首先考察一下，当沿着一条关于可行流f的增广 链 ，以=1调整f，得到新的可行流f（显然v（f ）=v（f）+1）时，C（f）比C（f）增加多少(输送 流量的总费用 )？3 3、增广链的费用、增广链的费用当沿着一条关于可行流 X 的增广链（流量修正路线），以
3、修正量=1进 行调整，得到新的可行流 ，则称C（ ）- C（X）为增广链增广链 的费用的费用。增广链的费用就是以单位调整量调整可行流时所付出的费用；当修正量=1时，此时， 的流量 f( ) = f(X)+1；C( )-C( X )=二、求解最小费用最大流问题的对偶法二、求解最小费用最大流问题的对偶法1 1、求解途径：、求解途径：（1 1）始终保持网络中的可行流是最小费用流， 然后不断调整，使流量逐步增大流量逐步增大，最终成为最 小费用的最大流；（2 2）始终保持可行流是最大流，通过不断调整 使费用逐步减小费用逐步减小，最终成为最大流量的最小费 用流。2 2、算法原理、算法原理（1 1）定理）定
4、理 若X 是流量为f(X)的最小费用流，是关于X 的所有增广链中费用最小的增广链，那么沿着去 调整X得到的新的可行流 就是流量为 f ( )的最小费用流。（2 2）实现思路）实现思路基于第一种求解途径，根据上述定理，只要找到最小费用增广链，在找到最小费用增广链，在该链上调整流量，得到增加流量后的该链上调整流量，得到增加流量后的最小费用流最小费用流。循环往复直至求出最小费用最大流。对偶法原理和步骤求最大流Ford算法找从vs到 vt的最短增广链调整流量得费用最小的可行流将0流作为初始可行流Yes绘制扩展 费用网络No流量等于 最大流?得最小费用最大流确保流 量最大确保费用最小实施中的关键实施中的
5、关键 构造增广费用网络图增广费用网络图（即扩展费用网络图），借助最短路算法最短路算法寻找最小费用增广链最小费用增广链。为什么?理由: 正向饱和弧不标记,反向零流弧不标记。不构造增广费用网络,就无法调整流量(1)饱和弧,流量无法减小;(2)非饱和弧,流量只能增加,不能减小;增广链流量调整：正向弧增加流量增广链流量调整：正向弧增加流量 ，反向弧减少流量，反向弧减少流量 。零流弧上零流弧上 WWij ij = =cij 原有弧（流量可以增加） 后加弧（流量不能再减少） 饱和弧上饱和弧上w wij ij = = 原有弧（流量不能再增加 ） -cij 后加弧（流量可以减少） 非饱和且非零流非饱和且非零流
6、 (0(0x xij ij b bij ij) )弧上弧上cij 原有弧（流量可以增加 ） -cij 后加弧（流量可以减少） WWij ij= =增广费用网络图增广费用网络图的构造方法构造方法将网络中的每一条弧（vi, vj）都变成一对方向相反的弧，以形成四通八达的四通八达的“ “路路” ”，权数定义如下： 将上述思想加以简化，出现将上述思想加以简化，出现 处相应的弧处相应的弧不画，按下面的方法具体构造增广费用网不画，按下面的方法具体构造增广费用网 络图络图： 零流弧上零流弧上，保持原弧不变，将单位费用 作为权数，即wij= cij:Vi Vj原网络Vi Vj增广费用网络非饱和弧上非饱和弧上
7、，原有弧以单位 费用作权数，后加弧（虚线弧）以单位 费用的负数作权数：ViVj原网络ViVj增广费用网络饱和弧上饱和弧上 ,去掉原有弧,添上后加弧(虚线弧),权数为单位费用的负数： ViVj原网络ViVj(bij, -cij)增广费用网络于是，在容量网络中寻找最小费用增广链就相当于在增广费用网络图（在增广费用网络图（ 扩展费用网络图）中寻找从发点到收扩展费用网络图）中寻找从发点到收 点的最短路点的最短路。注意注意 将找到的最短路还原到原网络图将找到的最短路还原到原网络图 中中（虚线弧改成原图中的反向弧）（虚线弧改成原图中的反向弧）。3 3、步骤：、步骤：第一步第一步-用Ford-Fukerso
8、n算法求出该容量网络的最大流量fmax；（本步骤的作用是什么？）本步骤的作用是什么？）第二步第二步- - 取初始可行流为零流，其必取初始可行流为零流，其必为流量为为流量为0 0的最小费用流（为什么？）的最小费用流（为什么？）第三步第三步 - - 一般为第一般为第k-1k-1次迭代，得次迭代，得 一最小费用流一最小费用流X X(k-1)(k-1) ，对当前可行流构对当前可行流构造增广费用网络图造增广费用网络图W(W(X X(k-1)(k-1) )，用用最短路最短路算法算法求出从发点到收点的最短路。求出从发点到收点的最短路。若不存在最短路，则若不存在最短路，则X X(k-1)(k-1)即最小费即最
9、小费用最大流，停止迭代；用最大流，停止迭代；否则，转下一步。否则，转下一步。 第四步第四步-将最短路还原成原网将最短路还原成原网络图中的最小费用增广链络图中的最小费用增广链 ，在，在 上上 对可行流对可行流X X(k-1)(k-1)进行调整，得到新的可进行调整，得到新的可行流图，若其流量等于行流图，若其流量等于f fmaxmax, ,迭代结束迭代结束。否则转入第一步，进入下一次迭。否则转入第一步，进入下一次迭代过程。代过程。 4 4、举例、举例 增广费用网络图(容量费用图(bij,cij) 可 行 流 图(流量网络(bij,cij,xij)vsvtv2v3v1(10,7)(7,7)(8,4)(
10、10,4)(4,4)(5,0)(2,0)最大流图fmax=11 (未标费用) 第 0 次 迭 代vsvtv2v3v1(10,4)(7,1)(8,1)(10,3)(4,2)(5,2)(2,6)(5,2,5)(7,1,5)vsvtv2v3v1(10,4,0)(8,1,5)(10,3,0)(4,2,0)(2,6,0)第 1 次 迭 代原图全部是零流弧,保持原 边不变,单位费用为权；所有的权均大于零，可用D 氏标号法求出最短路：恰也是最小费用增广链最小费用增广链。 流量调整量1=min8-0,5-0,7-0=5总流量f1=5最小费用增广链的费用 cij=1+2+1=4总费用C1=45=20 第 2 次
11、 迭 代(3,1)v1vt(5,-2)(2,6)v2v3(10,4)(5,-1)(10,3)(4,2)（2,1）vs（5，-1）(7,1,7) vsvtv2v3v1(10,4,2)(8,1,5)(10,3,0)(4,2,0)(2,6,0)(5,2,5)零流弧保持原边,非饱和非 零流弧(vs,v2)和(v1,vt)增添后 加弧,饱和弧(v2,v1)去掉原弧 增添后加弧；用列表法求出最短路:恰也是最小费用增广链。 流量调整量 2=min10-0,2-0(7-5)=2， 总流量=原流量+新增流量 =5+2=7； 最小费用增广链的费用 cij=4+1=5总费用C2=原费用+新增费用 =20+52=30
12、 vsvtv2v3v1(8,4)（2,-4）(5,-1)(7,-1)(10,3)(4,2)(2,6)(5,-2)(3,1)零流弧保持原边，此外的非 饱和弧增添后加弧，饱和弧去 掉原边增添反向虚线弧用列表法求得最短路恰也是最小费用增广链。流量调整量3=min3，10,4=3， 总流量=原流量+新增流量=7+3=10； 最小费用增广链的费用cij=1+3+2=6总费用C2=原费用+新增费 用=30+63=48 第 3 次 迭 代(7,1,7) vsvtv2v3v1(10,4,2)(8,1,8)(10,3,3)(4,2,3)(2,6,0)(5,2,5)(2,6)(7,3)(8,4)vsvtv2v3v
13、1(3,-3)(7,-1,)(8,-1) (3,-2)（1,2）(2,-4)（5,-2）零流弧保持原边，此外的非饱 和弧增添后加弧，饱和弧去掉原 边增添反向虚线弧；用列表法求得最短路对应的最小费用增广链是流量调整量4=min8,5,7,1=1， 总流量=原流量+新增流量=10+1=11； 最小费用增广链的费用cij=4-2+3+2=7 总费用C2=原费用+新增费用=48+71=55。由于总流量11已达到最大流量，故停 止迭代，当前的可行流图即最大流图 。第 4 次 迭 代(7,1,7)vsvtv2v3v1(10,4,3)(8,1,8)(10,3,4)(4,2,4)(2,6,0) (5,2,4)
14、举例 求最小费用-最大流问题求下图中网络从 到 的最小费用最大流，图中弧上 的数字为 。vsv2v3v4v5vtvsv2v3v4v5vt(0)求网络的最大流量由前面计算知， 。 将0流作为初始可行流。扩展费用网络与原网络相同(1)第一次迭代：用Ford算法求最短增广链，路线是vsv3v5vtvsv2v3v4v5vt调整流量：在增广链上有：在初始可行 流的基础上 调整流量得到新的可行流，刷新网络图（bij, cij, xij）(2)第二次迭代扩展费用网络vsv2v3v4v5vt饱和弧只能 减小流量，单 位费用减少3（1）流量还可增加3，单 位费用6；（2）流量也可 减小，当前流量为6，每减 单位
15、流量，费用节省6。（1）流量还可增加4，单 位费用1；（2）流量也可 减小，当前流量为6，每减 单位流量，费用节省1。用Ford算法求最短增广链，路线是vsv2v5vtvsv2v3v4v5vt在原可行 流基础上 调整流量 得到新的可行流，刷新网络图(3)第三次迭代扩展费用网络vsv2v3v4v5vt用Ford算法求最短增广链，路线是vsv2v4vt调整流量：在增广链上有：在初始可行 流的基础上 调整流量得到新的可行流，刷新网络图vsv2v3v4v5vt(3)第四次迭代扩展费用网络用Ford算法求最短增广链，路线是vsv3v4vtvsv2v3v4v5vtvsv2v3v4v5vt调整流量：在增广链上有：在初始可行 流的基础上 调整流量得到新的可行流，刷新网络图OVER!
