最小费用最大流问题ppt课件.ppt

《最小费用最大流问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5-5最小费用最大流问题2、最小费用流对一费用容量网络，具有相同流量f的可行流中，总费用最小的可行流称为该费用容量网络关于流量f的最小费用流，简称流量为f的最小费用流。3、增广链的费用当沿着一条关于可行流X的增广链（流量修正路线）μ，以修正量ε=1进行调整，得到新的可行流，则称C（）-C（X）为增广链μ的费用。②增广链μ的费用就是以单位调整量调整可行流时所付出的费用；③当修正量ε=1时，此时，①的流量f()=f(X)+1；C()-C(X)=二、求解最小费用最大流问题的对偶法1、求解途径：（1）始终保

2、持网络中的可行流是最小费用流，然后不断调整，使流量逐步增大，最终成为最小费用的最大流；（2）始终保持可行流是最大流，通过不断调整使费用逐步减小，最终成为最大流量的最小费用流。2、算法原理（1）定理若X是流量为f(X)的最小费用流，μ是关于X的所有增广链中费用最小的增广链，那麽沿着μ去调整X得到的新的可行流就是流量为f()的最小费用流。（2）实现思路基于第一种求解途径，根据上述定理，只要找到最小费用增广链，在该链上调整流量，得到增加流量后的最小费用流。循环往复直至求出最小费用最大流。＃实施中的关键构造

3、增广费用网络图（即扩展费用网络图），借助最短路算法寻找最小费用增广链。增广费用网络图的构造方法将网络中的每一条弧（vi,vj）都变成一对方向相反的弧，以形成四通八达的“路”，权数定义如下：零流弧上Wij=cij原有弧（流量可以增加）∞后加弧（流量不能再减少）饱和弧上wij=∞原有弧（流量不能再增加）-cij后加弧（流量可以减少）非饱和且非零流(0

4、用网络图：零流弧上，保持原弧不变，将单位费用作为权数，即wij=cij:ViVj(bij,cij)非饱和弧上，原有弧以单位费用作权数，后加弧（虚线弧）以单位费用的负数作权数：ViVj（bij,cij）(bij,-cij)ViVj(bij,-cij)饱和弧上,去掉原有弧,添上后加弧(虚线弧),权数为单位费用的负数：于是，在容量网络中寻找最小费用增广链就相当于在增广费用网络图（扩展费用网络图）中寻找从发点到收点的最短路。注意将找到的最短路还原到原网络图中（虚线弧改成原图中的反向弧）。3、步骤：第一步--

5、-用Ford-Fukerson算法求出该容量网络的最大流量fmax；（本步骤的作用是什麽？）第二步---取初始可行流为零流，其必为流量为0的最小费用流第三步---一般为第k-1次迭代，得一最小费用流X(k-1)，对当前可行流构造增广费用网络图W(X(k-1))，用最短路算法求出从发点到收点的最短路。（若不存在最短路，则X(k-1)即最小费用最大流，停止迭代。否则，转下一步。）第四步---将最短路还原成原网络图中的最小费用增广链μ，在μ上对可行流X(k-1)进行调整，得到新的可行流图，若其流量等于fm

6、ax,迭代结束。否则转入第一步，进入下一次迭代过程。