最小费用最大流问题xfj.ppt

《最小费用最大流问题xfj.ppt》由会员分享，可在线阅读，更多相关《最小费用最大流问题xfj.ppt（23页珍藏版）》请在三一办公上搜索。

1、10-5 最小费用最大流问题,一、基本概念1、什么是最小费用最大流问题？对每一条弧都给出单位流量费用的容量网络D=(V,A,C)(称为费用容量网络)中，求取最大流f，使输送流量的总费用 b(f)=bijfij 为最小的一类优化问题。其中，cij表示弧(vi,vj)上的容量，bij表示弧(vi,vj)上通过单位流量所花费的费用，fij表示弧(vi,vj)上的流量。,2、最小费用流 对于一个费用容量网络，具有相同流量 v(f)的可行流中，总费用b(f)最小的可行流称为该费用容量网络关于流量 v(f)的最小费用流，简称流量为 v(f)的最小费用流。,3、增广链的费用 当沿着一条关于可行流 f 的增广

2、链（流量修正路线），以修正量=1进行调整，得到新的可行流，则称 为增广链的费用。,增广链的费用定义为：以单位调整量调整可行流时所付出的费用；当修正量=1时，,此时，的流量v()=v(f)+1；,二、求解最小费用最大流问题的对偶法,1、求解途径：（1）始终保持网络中的可行流是最小费用 流，然后不断调整，使流量逐步增大，最终成为最小费用的最大流；（2）始终保持可行流是最大流，通过不断 调整使费用逐步减小，最终成为最大流 量的最小费用流。,主要学习按思路(1)的求解方法始终保持网络中的可行流是最小费用流，然后不断调整，使流量逐步增大，最终成为最小费用的最大流。,v(f),b(f),应该如何实现“始终

3、保持网络中的可行流是最小费用流”呢？,（2）实现思路 基于第一种求解途径，根据上述定理，从流量为v(f)的最小费用流f 开始，只要找到其上的最小费用增广链，在该链上调整流量，就得到增加流量后的最小费用流。循环往复就可以求出最小费用最大流。,实施中的关键寻找最小费用增广链具体方法：构造增广费用网络图，借助最短路算法寻找最小费用增广链。,增广费用网络图的构造方法 将流量网络中的每一条弧（vi,vj）都看作一对方向相反的弧，并定义弧的权数如下：,对于零流弧(fij=0),在其对应位置构造与其方向相同且权数为bij的弧；,对于非饱和且非零流弧(cijfij0)，在其对应位置构造与其方向相同且边权为bi

4、j的弧，以及与其方向相反且边权为-bij的弧。处理完所有的弧，即形成增广费用网络图。,对于饱和弧(fij=cij)，在其对应位置构造与其方向相反且权数为-bij的弧；,零流弧上(fij=0)，保持原弧不变，将单位费用作为权数，即wij=bij:,bij,饱和弧上(fij=cij)：去掉原有弧，添加以单位费用的负数作为权数后向弧（虚线弧）：,非饱和且非零流弧上(cijfij0)，原有弧以单位费用作权数，并添加以单位费用的负数作为权数后向弧（虚线弧）：,3、整个过程的求解步骤：第一步-取初始可行流为零流，它必为流量=0的最小费用流。,第二步-对该可行流f(0)构造增广费用网络图W(f(0)，用最短

5、路算法求出从发点到收点的最短路。(寻找f(0)的最小费用增广链)若不存在最短路，则该可行流即为最小费用最大流，停止迭代；否则，转下一步。,第三步-将最短路还原成流量网络图（cij,fij）中的最小费用增广链，在上对可行流f(0)进行调整(采用最大流问题中的增广链流量调整方法)，得到新的可行流图。返回第二步，将f(0)替换为新的可行流即可。,4、举例：以下图为例，求最小费用最大流，弧旁的数字为(cij,bij)。,解：（1）以零流弧为初始可行流f(0)，则初始可行流的流量v(f(0)=0。,4,1,1,3,2,2,6,第 1 次 迭 代,f(0)中全部是零流弧,则保持原边不变,单位费用为权；所有

6、的权均大于零，可用D氏标号法求出最短路：即是f(0)的最小费用增广链。,流量调整量1=min8-0,5-0,7-0=5 总流量v(f(1)=5最小费用增广链的费用bij=1+2+1=4新的可行流为f(1),总费用b1=45=20,第 2 次 迭 代,1,-2,6,4,-1,3,2,1,-1,零流弧保持原边,非饱和非零流弧(vs,v2)和(v1,vt)增添后向弧,饱和弧(v2,v1)去掉原弧增添后向弧；用列表法求出最短路:即是f(1)的最小费用增广链。,流量调整量2=min10-0,7-5=2，总流量v(f(2)=原流量+新增 流量=5+2=7；最小费用增广链的费用 bij=4+1=5新的可行流

7、为f(2),总费用b2=原费用+新增费用=20+52=30,4,-4,-1,-1,3,2,6,-2,1,零流弧保持原边，非饱和非零流弧增添后向弧，饱和弧去掉原边增添后向弧用列表法求得最短路 即是f(2)的最小费用增广链。,流量调整量3=min8-5,10-0,4-0=3，总流量v(f(3)=原流量+新 增流量=7+3=10；最小费用增广链的费用 bij=1+3+2=6新的可行流为f(3),总费用b3=原费用+新增费用=30+63=48,第 3 次 迭 代,添加弧；用列表法求得最短路 对应最小费用增广链,调整流量 4=min10-2,5,10-3,4-3=1，总流量v(f(4)=10+1=11；

8、最小费用增广链的费用 bij=4-2+3+2=7新的可行流为f(4),总费用b4=原费用+新增费用=48+71=55。,第 4 次 迭 代,6,3,4,-3,-1,-1,-2,-4,-2,添加弧；用列表法计算发现Vs和Vt之间不存在一条最短路，计算结束。当前的可行流f(4)即为所求的最小费用最大流。,第 5次 迭 代,2,6,3,4,-3,-1,-1,-2,-4,-2,2,总 结,最短路算法与最大流算法的结合运用 1）构造初始可行流的增广费用网络，用最短路算法求出最小费用增广链。2）将最小费用增广链还原到容量流量网络图中的增广链，调整流量得到新的可行流，继续进行，直到用最短路算法找不到最小费用增广链。,