最小费用最大流问题

最小费用最大流问题最大流问题最小费用最大流问题最大流问题引例基本概念最大流算法算例Back1v2v3v5v6v4v)2,17()1,5()6,11()3,3()1,4()2,5()2,3()3,8()3,6()5,10(continuedBack引例假设某个公路网的每条公路只允许单向行驶，这样的公路网称为单行公路网．为了保证畅通，交通部门对每条公路在单位时间内通过的车辆数目要作一个限制．问单位时间内最多能有多少辆车从甲地出发经过该公路网到达乙地？网络与流增广链是一条增广链后向弧集合前向弧集合中在链是饱和弧流量容量)},{()},(),,(),,(),,{(),,,,,(),(1,3,2,55,8,3,1045654332216543215445341324123413241254vvvvvvvvvvvvvvvvcfvvffffcccc一、网络与流一个有向图称为一个网络．其中，为图的所有顶点集；为弧集；为各弧上容量集在中指定了两点，分别称为发点和收点，其余的点叫中间点．定义弧集合上的一个函数为网络的一个流,并称为弧上的流量，简记为continued),,(CAVDVAC)}.,({jiijvvccVtsvv,A)},,({),(:jijivvfvvf),(jivvf),(jivv.ijf二、可行流与最大流一个流称为一个可行流,如果满足以下条件:(1)容量限制条件:对(2)平衡条件:对中间点:流出量=流入量,即对于发点对于收点式中称为这个可行流的流量,即发点的净输出量(或收点的净输入量);0),(ijijjiijcfAvva;0),(),(),(AvvjiAvvijijjifftsii记,sv);(),(),(fvffAvvjsAvvsjsjjs记,tv).(),(),(fvffAvvjtAvvtjtjjt)(fv最大流问题:)(),(),(,0)(),(),(),(tifvtsisifvffAvvjiAvvijijjiAvvcfjiijij),(,0)(maxfvf..ts三、增广链1、给定一个可行流称2、若是网络中联结发点和收点的一条链,定义链的方向是从到,则链上的弧被分为两类:一类是弧的方向与链的方向一致,称为前向弧,前向弧的全体记为另一类弧与链的方向相反,称为后向弧,后向弧的全体记为3、设f是一个可行流,是从到的一条链,称为一条增广链,如果.0;;0;的弧为非零流弧的弧为非饱和弧的弧为零流弧的弧为饱和弧ijijijijijijfcffcfsvtv,svtv..,0),(;,0),(是非零流弧即反向弧集中每一条弧是非饱和弧即正向弧集中每一条弧ijijjiijijjicfvvcfvv四、截集1、设把始点在,终点在中的所有弧构成的集合,记为2、给定网络若点集被剖分为两个非空集合使则弧集称为分离和的截集.3、截集中所有弧的容量之和称为此截集的容量,记为即),,(CAVDST).,(TS,,,TSVTSV,1V__1V,,__11VvVvts),(__11VVsvtv),(__11VV),,(__11VVc),(),(__11_11),(VVvvijjicVVc定理1可行流f是最大流不存在关于f的增广链.定理2任一个网络中,从到的最大流的流量等于分离的最小截集的容量.),,(CAVDtsvv,tvsvBack求最大流的标号法(Ford,Fulkerson)1、标号过程开始:先给标上此时是标号而未检查的点,其余都是未标号点.一般地,取一个标号而未检查的点,对一切未标号点:(1)若在弧上则给标号,这里.此时,点成为标号而未检查的点.(2)若在弧上则给标号这里.此时,点成为标号而未检查的点.于是成为标号且已检查过的点.重复上述步骤,一旦被标上号,表明得到一条从到的增广链,转入调整过程.若所有标号都已经检查过,而标号过程进行不下去时,则算法结束,此时的可行流就是最大流.svsv),,0(ivjv),(jivv,,ijijcfjv))(,(jivlv]),(min[)(ijijijfcvlvljv),(ijvv,0,ijfjv))(,(jivlv]),(min[)(jiijfvlvljvivtvsvtv2、调整过程(1)寻找以为终点的增广链----(反向追踪法):(2)调整量(3)流的调整令去掉所有的标号,对新的可行流重新进入标号过程.。。v，，。vvvv，vv，v。vvvvvvvsikkiiikkttkkkt增广链此时被找的弧就构成了为止直到依此下去再检查的第一个标号相应地出则找或若为的第一个标号接下来检查上的弧链是相应地则弧或的第一个标号为若)),()(,()()),()(,(),(。vvltt的第二个标号即),(,.),(,),(,),(,jiijjiijjiijvvfvvfvvf若若若},'{'ijfftvBacksv2v1v4vtv3v)1,2()3,5()0,3()1,1()3,4()1,1()1,5()2,2()3,3(continuedBack算例用标号法求右下图所示网络的最大流.弧旁的数是解:(一)标号过程1、首先给标上2、检查在弧上不满足标号条件;在弧上则的标号为.其中,).,(ijijfctv3v)1,2()3,5()0,3()1,1()3,4()1,1()1,5()2,2()3,3(svsv).,0(),0(sv),(2vvs,3,22sscf),(1vvs,,11sscf))(,(1vlvs4]15,min[)](),(min[)(111sssfcvlvl)4,(1svv1vsv2v1v4vtv3v)1,2()3,5()0,3()1,1()3,4()1,1()1,5()2,2()3,3(continuedBack3、检查在弧上不满足标号条件;在弧上则的标号为其中,4、检查在弧上则的标号为.其中,在弧上则的标号为.其中,tv3v)1,2()3,5()0,3()1,1()3,4()1,1()1,5()2,2()3,3(sv),(31vv,2,1313cf),(12vv,0,21f)).(,(21vlv1]34,1min[)](),(min[)(242424fcvlvl),(42vv,,2424cf)).(,(42vlv1]1,4min[]),(min[)(2112fvlvl),(23vv,0,32f)).(,(32vlv1]1,1min[]),(min[)(3223fvlvl1v2v2v4v)1,(12vv)4,(1svv)1,(24vv3v),0(sv2v1v4vtv3v)1,2()3,5()0,3()1,1()3,4()1,1()1,5()2,2()3,3(continuedBack5、在中任选一个进行检查.例如在弧上则的标号为其中,因有了标号,故转入调整过程.)1,2()3,5()0,3()1,1()3,4()1,1()1,5()2,2()3,3(sv),(3tvv)).(,(3tvlv,,33ttcf1]12,1min[)](),(min[)(333tttfcvlvl43,vvtvtv)1,(12vv)4,(1svv)1,(24vv)1,(23vv)1,(3vvt),0(sv2v1v4vtv3v)1,2()3,5()0,3()1,1()3,4()1,1()1,5()2,2()3,3(continuedBack(二)调整过程(1)寻找以为终点的增广链----(反向追踪法)(2)调整量)1,2()3,5()0,3()1,1()3,4()1,1()1,5()2,2()3,3(sv)1,(12vv)4,(1svv)1,(24vv)1,(23vv)1,(3vvt),0(。vvvvvvvvv，。vv，v，v。vvvvtsstt),,,(.),(),(),(),(,321112232333此时所求的增广链上的弧是链和同理上的弧是链则找出为的第一个标号接下来检查上的弧是链则弧的第一个标号为若。vvltt的第二个标号即,1)(sv2v1v4vtv3v)2,2()3,5()0,3()0,1()3,4()0,1()2,5()2,2()3,3(continuedBack(3)流的调整去掉所有的标号,对新的可行流重新进入标号过程.)1,2()3,5()0,3()1,1()3,4()1,1()1,5()2,2()3,3(sv)1,(12vv)4,(1svv)1,(24vv)1,(23vv)1,(3vvt),0(，vvvvvts中增广链),,,(321.;01',01')},(),,{(;21',21')},(),,{(323221212312331131不变其余ijttsstsfffffvvvvffffvvvv)2,2()3,5()0,3()0,1()3,4()0,1()2,5()2,2()3,3(sv2v)3,(1svv4v3vtv),0(continuedBack标号过程无法继续下去,算法结束.此时的可行流即为所求的最大流.最大流量为最小截集:其中,为标号点集合,为未标号集合.).,(__11VV)2,2()3,5()0,3()0,1()3,4()0,1()2,5()2,2()3,3(sv)3,(1svv3vtv),0(2v4v.5)(4321ttssfffffv__1V1V5)},(),,{(),(},,,,{},,{312__11432__111其容量为最小截集本例中，vvvvVVvvvvVvvVsts最小费用最大流问题给定网络每一弧上,除了已给容量外,还给了一个单位流量的费用(简记为).所谓最小费用最大流问题就是要求一个最大流,使流的总输送费用最小,即求,使怎么求解这个问题?),,(CAVD),(jivvijc0),(jivvbijbfAvvijijfjifbfb),(*min)(*f1、定义增广链的费用为结论:若是流量为的所有可行流中费用最小者,而是关于的所有增广链中费用最小的增广链,则沿去调整,得到的可行流,就是流量为的所有可行流中的最小费用流.这样,当是最大流时,它即为所求的最小费用最大流.2、定义网络D的一个可行流为,构造其赋权有向图,记为如下：1)的顶点集是D的顶点集;2)把D中的每一条弧变成两个相反方向的弧和.定义中弧的权为:ijijbbf)(fvff'f)'(fv'ff)(fW)(fW),(jivv),(jivv),(ijvvijijijijijijcfcfbw,,0,0,,ijijijjiffbw)(fW在网络D中求关于f的最小费用增广链等价于在中求从到的最短路.最小费用最大流算法开始:取为初始可行流.(1)在第K-1步:最小费用流为,构造赋权有向图并在中,寻求从到的最短路.1)若不存在最短路,则就是最小费用最大流.2)若存在最短路,则在原网络D中得相应的增广链,在增广链上对进行调整.调整量为令则得到新的可行流.转(1).)(fWsvtv0)0(f)1(kf),()1(kfW)()1(kfWsvtv)1(kf)1(kf)]min),(minmin[)1()1(kijkijijffc,),(,),(,),(,)1()1()1()(jikijjikijjikijkijvvfvvfvvff若若若)1(kf算例以下图为例,求最小费用最大流.弧旁数字为(1)取为初始可行流.(2)构造赋权有向图,并求出从到的最短路,如图1所示(双箭头).(3)在原网络中,与这条最短路相应的增广链(4)在