《最小费用最大流问题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、增广链的费用 当沿着
2、一条关于可行流 f 的增广链（流量修正路线），以修正量=1进行调整，得到新的可行流 ，则称 为增广链的费用。,增广链的费用定义为：以单位调整量调整可行流时所付出的费用； 当修正量=1时，,此时， 的流量v( ) = v(f)+1；,二、求解最小费用最大流问题的对偶法,1、求解途径： （1）始终保持网络中的可行流是最小费用 流，然后不断调整，使流量逐步增大， 最终成为最小费用的最大流； （2）始终保持可行流是最大流，通过不断 调整使费用逐步减小，最终成为最大流 量的最小费用流。,主要学习按思路(1)的求解方法 始终保持网络中的可行流是最小费用流，然后不断调整，使流量逐步增大，最终成为最小费用的最
3、大流。,v(f),b(f),应该如何实现“始终保持网络中的可行流是最小费用流” 呢？,（2）实现思路 基于第一种求解途径，根据上述定理，从流量为v(f) 的最小费用流f 开始，只要找到其上的最小费用增广链，在该链上调整流量，就得到增加流量后的最小费用流。循环往复就可以求出最小费用最大流。,实施中的关键寻找最小费用增广链 具体方法：构造增广费用网络图，借助最短路算法寻找最小费用增广链。,增广费用网络图的构造方法 将流量网络中的每一条弧（vi,vj）都看作一对方向相反的弧，并定义弧的权数如下：,对于零流弧(fij=0),在其对应位置构造与其方向相同且权数为bij的弧；,对于非饱和且非零流弧( ci
4、jfij0)，在其对应位置构造与其方向相同且边权为bij的弧，以及与其方向相反且边权为-bij的弧。 处理完所有的弧，即形成增广费用网络图。,对于饱和弧(fij=cij)，在其对应位置构造与其方向相反且权数为-bij的弧；,零流弧上(fij=0) ，保持原弧不变，将单位费用作为权数，即wij= bij:,bij,饱和弧上(fij=cij)：去掉原有弧，添加以单位费用的负数作为权数后向弧（虚线弧）：,非饱和且非零流弧上( cijfij0) ，原有弧以单位费用作权数，并添加以单位费用的负数作为权数后向弧（虚线弧）：,3、整个过程的求解步骤： 第一步-取初始可行流为零流 ，它必为流量=0的最小费用流
5、。,第二步 - 对该可行流f(0)构造增广费用网络图W(f(0)，用最短路算法求出从发点到收点的最短路。(寻找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,第
6、 1 次 迭 代, f(0)中全部是零流弧,则保持原边不变,单位费用为权； 所有的权均大于零，可用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， 总流量
7、v(f(2)=原流量+新增 流量=5+2=7； 最小费用增广链的费用 bij=4+1=5 新的可行流为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 次 迭 代,添加弧； 用列表法求得最短路
8、对应最小费用增广链,调整流量 4=min10-2,5,10-3,4-3=1， 总流量v(f(4) =10+1=11； 最小费用增广链的费用 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）将最小费用增广链还原到容量流量网络图中的增广链，调整流量得到新的可行流，继续进行，直到用最短路算法找不到最小费用增广链。,