《最小费用最大流问题xfj》由会员分享，可在线阅读，更多相关《最小费用最大流问题xfj（23页珍藏版）》请在金锄头文库上搜索。
1、10-5 最小费用最大流问题最小费用最大流问题一、基本概念一、基本概念1、什么是最小费用最大流问题？、什么是最小费用最大流问题？对每一条弧都给出对每一条弧都给出单位流量费用单位流量费用的的容量网络容量网络D=(V, A, C)(称为费用容量网络称为费用容量网络)中，求取中，求取最大最大流流f，使输送流量的，使输送流量的总费用总费用 b(f)=bijfij为最小为最小的一类优化问题。的一类优化问题。 其中，其中，cij表示弧表示弧(vi, vj)上的容量，上的容量，bij表示弧表示弧(vi, vj)上通过单位流量所花费的费用，上通过单位流量所花费的费用，fij表示弧表示弧(vi, vj)上的流量
2、。上的流量。vivj(cij,bij,fij)2、最小费用流、最小费用流对于一个费用容量网络，具有相同对于一个费用容量网络，具有相同流量流量 v(f) 的可行流中，总费用的可行流中，总费用b(f)最小的最小的可行流称为该费用容量网络关于流量可行流称为该费用容量网络关于流量 v(f) 的最小费用流，简称的最小费用流，简称流量为流量为 v(f) 的最小的最小费用流。费用流。3、增广链的费用、增广链的费用当沿着一条关于可行流当沿着一条关于可行流f 的增广链的增广链（流量修正路线）（流量修正路线），以修正量，以修正量=1进进行调整行调整，得到新的可行流，得到新的可行流 ，则称，则称 为为增广链增广链的
3、费用。的费用。增广链增广链的费用定义为：以的费用定义为：以单位调整量单位调整量调整可行流时所付出的费用；调整可行流时所付出的费用；当修正量当修正量=1时，时，此时，此时， 的流量的流量v()=v(f)+1；二、求解最小费用最大流问题的对偶法二、求解最小费用最大流问题的对偶法1、求解途径：、求解途径：（1）始终保持始终保持网络中的可行流是网络中的可行流是最小费用最小费用 流流，然后不断调整，使，然后不断调整，使流量逐步增大流量逐步增大， 最终成为最小费用的最大流；最终成为最小费用的最大流；（2）始终保持始终保持可行流是可行流是最大流最大流，通过不断，通过不断 调整使调整使费用逐步减小费用逐步减小
4、，最终成为最大流，最终成为最大流 量的最小费用流。量的最小费用流。主要学习按思路主要学习按思路(1)(1)的求解方法的求解方法始终保持始终保持网络中的可行流是网络中的可行流是最小费用流最小费用流，然后，然后不断调整，使不断调整，使流量逐步增大流量逐步增大，最终成为最小费，最终成为最小费用的最大流。用的最大流。v(f)b(f)(1)(2)应该如何实现应该如何实现“始终保持网络中的可始终保持网络中的可行流是最小费用流行流是最小费用流” 呢？呢？2、算法原理、算法原理（1）定理）定理若若f 是流量为是流量为v(f)的最的最小费用流，小费用流，是关于是关于 f 的所有增广的所有增广链中链中费用最小的增
5、广链费用最小的增广链，那么沿着，那么沿着去去调整调整 f 得到的新的可行流得到的新的可行流 就就是流量为是流量为 的最小费用流。的最小费用流。（2）实现思路）实现思路基于第一种求解途径，根据上述定理，基于第一种求解途径，根据上述定理，从流量为从流量为v(f) 的最小费用流的最小费用流f 开始，只要找开始，只要找到其上的到其上的最小费用增广链，在该链上调整流最小费用增广链，在该链上调整流量，就得到量，就得到增加流量增加流量后的最小费用流后的最小费用流。循环。循环往复就可以求出最小费用最大流。往复就可以求出最小费用最大流。 实施中的关键实施中的关键寻找最小费用增广链寻找最小费用增广链具体方法具体方
6、法：构造增广费用网络图，借助最短路构造增广费用网络图，借助最短路算法寻找最小费用增广链。算法寻找最小费用增广链。 增广费用网络图增广费用网络图的的构造方法构造方法 将流量网络中的每一条弧（将流量网络中的每一条弧（vi,vj）都看作）都看作一对方向相反的弧，并定义弧的权数如下：一对方向相反的弧，并定义弧的权数如下： vivj(cij,fij)w wij ij = =bij若若fij0+ 若若fij=0 对于零流弧对于零流弧(fij=0),在其对应位置构造在其对应位置构造与其方向相同且权数为与其方向相同且权数为bij的弧；的弧；w wij ij = =bij若若fij0+ 若若fij=0对于非饱和
7、且非零流弧对于非饱和且非零流弧( cijfij0)，在其对应位，在其对应位置构造与其方向相同且边权为置构造与其方向相同且边权为bij的弧，以及与的弧，以及与其方向相反且边权为其方向相反且边权为-bij的弧。的弧。 处理完所有的弧，即形成增广费用网络图。处理完所有的弧，即形成增广费用网络图。对于饱和弧对于饱和弧(fij=cij)，在其对应位置构造与其方，在其对应位置构造与其方向相反且权数为向相反且权数为-bij的弧；的弧；零流弧上零流弧上(fij=0) ，保持原弧不变，将，保持原弧不变，将单位费用作为权数，即单位费用作为权数，即wij= bij:ViVjbijViVj-bij饱和弧上饱和弧上(f
8、ij=cij)：去掉原有弧，添加去掉原有弧，添加以单位费用的以单位费用的负数负数作为权数作为权数后向弧后向弧（虚线弧）：（虚线弧）：非饱和且非零流弧上非饱和且非零流弧上( cijfij0) ，原有，原有弧以单位费用作权数，并添加以单位费弧以单位费用作权数，并添加以单位费用的用的负数负数作为权数作为权数后向弧后向弧（虚线弧）：（虚线弧）：ViVj bij-bij3、整个过程的求解步骤：、整个过程的求解步骤：第一步第一步-取初始可行流为零流取初始可行流为零流 ，它必为，它必为流量流量=0的最小费用流。的最小费用流。第二步第二步-对该可行流对该可行流f(0)构造增广费用构造增广费用网络图网络图W(f
9、(0)，用，用最短路算法最短路算法求出从发点到求出从发点到收点的最短路。收点的最短路。(寻找寻找f(0)的最小费用增广链的最小费用增广链)若不存在最短路，则该可行流即为最小费若不存在最短路，则该可行流即为最小费用最大流，停止迭代；否则，转下一步。用最大流，停止迭代；否则，转下一步。第三步第三步-将最短路还原成流量网将最短路还原成流量网络图（络图（cij,fij）中的最小费用增广链）中的最小费用增广链，在，在上对可行流上对可行流f(0)进行调整进行调整(采用采用最大流问题中的增广链流量调整方最大流问题中的增广链流量调整方法法)，得到新的可行流图。返回第二，得到新的可行流图。返回第二步，将步，将f
10、(0)替换为新的可行流即可。替换为新的可行流即可。4、举例：、举例：以下图为例，求最小费用最大以下图为例，求最小费用最大流，弧旁的数字为流，弧旁的数字为(cij,bij)。 vsvtv2v3v1(10,4)(7,1)(8,1)(10,3)(4,2)(5,2)(2,6)解：（解：（1）以零流弧为初始可行流）以零流弧为初始可行流f(0)，则初始可行，则初始可行流的流量流的流量v(f(0)=0。vsvtv2v3v14113226(5,5)(7,5)vsvtv2v3v1(10,0)(8,5)(10,0)(4,0)(2,0)第第1次次迭迭代代 f f(0)(0)中全部是零流弧中全部是零流弧, ,则保则保
11、持原边不变持原边不变, ,单位费用为权；单位费用为权；所有的权均大于零，可用所有的权均大于零，可用D D氏标号法求出最短路：氏标号法求出最短路：即是即是f f(0)(0)的的最小费用增广链最小费用增广链最小费用增广链最小费用增广链。 流量调整量流量调整量1 1=min8-0,5-0,7-0=5=min8-0,5-0,7-0=5 总流量总流量v(fv(f(1)(1)=5)=5最小费用增广链的费用最小费用增广链的费用b bijij=1+2+1=4=1+2+1=4新的可行流为新的可行流为f f(1)(1), ,总费总费用用b b1 1=4=45=205=20 第第2次次迭迭代代1v1vt-26v2v
12、34-132 1vs-1(7,7)vsvtv2v3v1(10,2)(8,5)(10,0)(4,0)(2,0)(5,5)零流弧保持原边零流弧保持原边, ,非饱和非非饱和非零流弧零流弧(v(vs s,v,v2 2) )和和(v(v1 1,v,vt t) )增添后增添后向弧向弧, ,饱和弧饱和弧(v(v2 2,v,v1 1) )去掉原弧去掉原弧增添后向弧；增添后向弧；用列表法求出最短路用列表法求出最短路: : 即是即是f f(1)(1)的最小费用增广链的最小费用增广链。 流量调整量流量调整量2 2=min10-0,7-5=2=min10-0,7-5=2，总流量总流量v(fv(f(2)(2)=)=原流
13、量原流量+ +新增新增 流量流量=5+2=7=5+2=7；最小费用增广链的费用最小费用增广链的费用 b bijij=4+1=5=4+1=5新的可行流为新的可行流为f f(2)(2), ,总费用总费用b b2 2= =原费用原费用+ +新增费用新增费用=20+5=20+52=30 2=30 vsvtv2v3v14-4-1-1326-21零流弧保持原边，非饱和非零流弧保持原边，非饱和非零流弧增添后向弧，饱和弧去零流弧增添后向弧，饱和弧去掉原边增添后向弧掉原边增添后向弧用列表法求得最短路用列表法求得最短路 即是即是f(2)的最小费用增广链。的最小费用增广链。流量调整量流量调整量3 3=min8-=m
14、in8-5,10-0,4-0=35,10-0,4-0=3，总流量总流量v(fv(f(3)(3) ) = =原流量原流量+ +新新 增流量增流量=7+3=10=7+3=10；最小费用增广链的费用最小费用增广链的费用 b bijij=1+3+2=6=1+3+2=6新的可行流为新的可行流为f f(3)(3), ,总费用总费用b b3 3= =原费用原费用+ +新增费用新增费用=30+6=30+63=48 3=48 第第3次次迭迭代代(7,7)vsvtv2v3v1(10,2)(8,8)(10,3)(4,3)(2,0)(5,5)634vsvtv2v3v1-3-1-1-22-4 -2添加弧；添加弧；用列表
15、法求得最短路用列表法求得最短路 对应最小费用增广链对应最小费用增广链调整流量调整流量 4 4=min10-2,5,10-3,4-3=1=min10-2,5,10-3,4-3=1，总流量总流量v(fv(f(4)(4) ) =10+1=11=10+1=11；最小费用增广链的费用最小费用增广链的费用 b bijij=4-2+3+2=7=4-2+3+2=7新的可行流为新的可行流为f f(4)(4), ,总费用总费用b b4 4= =原费用原费用+ +新增费用新增费用 =48+7=48+71=551=55。第第4次次迭迭代代(7,7)vsvtv2v3v1(10,3)(8,8)(10,4)(4,4)(2,
16、0)(5,4)634vsvtv2v3v1-3-1-1-2-4 -2添加弧；添加弧；用列表法计算发现用列表法计算发现VsVs和和VtVt之间不存在一条最之间不存在一条最短路，计算结束。当前短路，计算结束。当前的可行流的可行流f f(4)(4)即为所求的即为所求的最小费用最大流。最小费用最大流。第第5次次迭迭代代2vsv1v2v3vtd(1)d(2)d(3)d(4)vs040000v1-40-264444v2-1203222v3-301055vt-1-20634vsvtv2v3v1-3-1-1-2-4 -22总总 结结 最短路算法与最大流算法的结合运用最短路算法与最大流算法的结合运用 1 1）构造初始可行流的增广费用网络，用最）构造初始可行流的增广费用网络，用最短路算法求出最小费用增广链。短路算法求出最小费用增广链。 2 2）将最小费用增广链还原到容量流量网络）将最小费用增广链还原到容量流量网络图中的增广链，调整流量得到新的可行流，继图中的增广链，调整流量得到新的可行流，继续进行，直到用最短路算法找不到最小费用增续进行，直到用最短路算法找不到最小费用增广链。广链。
