《最小费用最大流问题解析》由会员分享，可在线阅读，更多相关《最小费用最大流问题解析（23页珍藏版）》请在金锄头文库上搜索。
1、5-5 最小费用最大流问题,一、基本概念 1、什么是最小费用最大流问题？ 对每一条弧都给出单位流量费用的容量网络D=（V，A，B）（称为费用容量网络）中，求取最大流X，使输送流量的总费用 C（X）=cijxij为最小的一类优化问题。 其中，bij表示弧（vi，vj）上的容量，xij表示弧（vi，vj）上的流量，cij表示弧（vi，vj）上通过单位流量所花费的费用。,2、最小费用流 对一费用容量网络，具有相同流量 f 的可行流中，总费用最小的可行流称为该费用容量网络关于流量 f 的最小费用流，简称流量为 f 的最小费用流。,3、增广链的费用 当沿着一条关于可行流 X 的增广链（流量修正路线），以
2、修正量=1进行调整，得到新的可行流 ，则称C（ ）- C（X）为 增广链的费用。,增广链的费用就是以单位调整量调整可行流时所付出的费用； 当修正量=1时，,此时， 的流量 f( ) = f(X)+1；,C( )-C( X )=,二、求解最小费用最大流问题的对偶法,1、求解途径： （1）始终保持网络中的可行流是最小费用流，然后不断调整，使流量逐步增大，最终成为最小费用的最大流； （2）始终保持可行流是最大流，通过不断调整使费用逐步减小，最终成为最大流量的最小费用流。,2、算法原理 （1）定理 若X 是流量为f(X)的最小费用流，是关于X 的所有增广链中费用最小的增广链，那麽沿着去调整X得到的新的
3、可行流 就是流量为 f ( )的最小费用流。,（2）实现思路 基于第一种求解途径，根据上述定理，只要找到最小费用增广链，在该链上调整流量，得到增加流量后的最小费用流。循环往复直至求出最小费用最大流。,实施中的关键 构造增广费用网络图（即扩展费用网络图），借助最短路算法寻找最小费用增广链。,增广费用网络图的构造方法 将网络中的每一条弧（vi,vj）都变成一对方向相反的弧，以形成四通八达的“路”，权数定义如下：,将上述思想加以简化，出现处相应的弧不画，按下面的方法具体构造增广费用网络图：,零流弧上，保持原弧不变，将单位费用作为权数，即wij= cij:,非饱和弧上，原有弧以单位费用作权数，后加弧（
4、虚线弧）以单位费用的负数作权数：,饱和弧上,去掉原有弧,添上后加弧(虚线弧),权数为单位费用的负数：,于是，在容量网络中寻找最小费用增广链就相当于在增广费用网络图（扩展费用网络图）中寻找从发点到收点的最短路。 注意 将找到的最短路还原到原网络图中（虚线弧改成原图中的反向弧）。,3、步骤： 第一步-用Ford-Fukerson算法求出该容量网络的最大流量fmax； （本步骤的作用是什麽？）,第二步- 取初始可行流为零流，其必为流量为0的最小费用流（为什麽？）,第三步 - 一般为第k-1次迭代，得一最小费用流X(k-1) ，对当前可行流构造增广费用网络图W(X(k-1)，用最短路算法求出从发点到收
5、点的最短路。 若不存在最短路，则X(k-1)即最小费用最大流，停止迭代； 否则，转下一步。,第四步-将最短路还原成原网络图中的最小费用增广链，在上对可行流X(k-1)进行调整，得到新的可行流图，若其流量等于fmax,迭代结束。否则转入第一步，进入下一次迭代过程。,4、举例,增广费用网络图 (容量费用图(bij,cij),可 行 流 图 (流量网络(bij,cij,xij),最大流图fmax=11 (未标费用),第 0 次 迭 代,第 1 次 迭 代,原图全部是零流弧,保持原边不变,单位费用为权； 所有的权均大于零，可用D氏标号法求出最短路： 恰也是最小费用增广链。,流量调整量 1=min8-0
6、,5-0,7-0=5 总流量f1=5 最小费用增广链的费用cij=1+2+1=4 总费用C1=45=20,第 2 次 迭 代,零流弧保持原边,非饱和非零流弧(vs,v2)和(v1,vt)增添后加弧,饱和弧(v2,v1)去掉原弧增添后加弧； 用列表法求出最短路: 恰也是最小费用增广链。,流量调整量 2=min10-0,2-0=2， 总流量=原流量+新增流量 =5+2=7； 最小费用增广链的费用 cij=4+1=5 总费用C2=原费用+新增费用=20+52=30,零流弧保持原边，此外的非饱和弧增添后加弧，饱和弧去掉原边增添反向虚线弧 用列表法求得最短路 恰也是最小费用增广链。,流量调整量 3=mi
7、n3，10,4=3， 总流量=原流量+新增流量 =7+3=10； 最小费用增广链的费用 cij=1+3+2=6 总费用C2=原费用+新增费用=30+63=48,第 3 次 迭 代,零流弧保持原边，此外的非饱和弧增添后加弧，饱和弧去掉原边增添反向虚线弧； 用列表法求得最短路 对应的最小费用增广链是,流量调整量4=min8,5,7,1=1， 总流量=原流量+新增流量=10+1=11； 最小费用增广链的费用 cij=4-2+3+2=7 总费用C2=原费用+新增费用 =48+71=55。 由于总流量11已达到最大流量，故停止迭代，当前的可行流图即最大流图。,第 4 次 迭 代,第十三次作业 P162：7； P163：8；,
