最小费用最大流问题解析PPT幻灯片课件.ppt

5-5 最小费用最大流问题最小费用最大流问题1一、基本概念一、基本概念1、什么是最小费用最大流问题？、什么是最小费用最大流问题？ 对每一条弧都给出对每一条弧都给出单位流量费用单位流量费用的的容量网络容量网络D=（（V，，A，，B）（称为费用容量网络）中，求取）（称为费用容量网络）中，求取最大流最大流X，使输送流量的，使输送流量的总费用总费用 C（（X））=∑cijxij为最小为最小的一类优化问题的一类优化问题 其中，其中，bij表示弧（表示弧（vi，，vj）上的容量，）上的容量，xij表示表示弧（弧（vi，，vj）上的流量，）上的流量，cij表示弧（表示弧（vi，，vj）上）上通过单位流量所花费的费用通过单位流量所花费的费用22、最小费用流、最小费用流 对一费用容量网络，具有相同流对一费用容量网络，具有相同流量量 f 的可行流中，总费用最小的可行的可行流中，总费用最小的可行流称为该费用容量网络关于流量流称为该费用容量网络关于流量 f 的的最小费用流，简称最小费用流，简称流量为流量为 f 的最小费的最小费用流33、增广链的费用、增广链的费用 当沿着一条关于可行流当沿着一条关于可行流 X 的增广链的增广链（流量修正路线）（流量修正路线）μ，以修正量，以修正量ε=1进进行调整行调整，得到新的可行流，得到新的可行流 ，则称，则称C（（ ））- C（（X）为）为 增广链增广链μ的费用的费用。

4②②增广链增广链μ的费用就是以单位调整量调整的费用就是以单位调整量调整可行流时所付出的费用；可行流时所付出的费用；③③当修正量当修正量ε=1时，时，此时，此时， ①① 的流量的流量 f( ) = f(X)+1；；C( )-C( X )=5二、求解最小费用最大流问题的对偶法二、求解最小费用最大流问题的对偶法1、求解途径：、求解途径：（（（（1 1））））始终保持始终保持网络中的可行流是网络中的可行流是最小费用流最小费用流，，然后不断调整，使然后不断调整，使流量逐步增大流量逐步增大流量逐步增大流量逐步增大，最终成为最，最终成为最小费用的最大流；小费用的最大流；（（（（2 2））））始终保持始终保持可行流是可行流是最大流最大流，通过不断调整，通过不断调整使使费用逐步减小费用逐步减小费用逐步减小费用逐步减小，最终成为最大流量的最小费，最终成为最大流量的最小费用流62、算法原理、算法原理（（1）定理）定理 若若X 是流量为是流量为f(X)的最的最小费用流，小费用流，μ是关于是关于X 的所有增广的所有增广链中费用最小的增广链，那麽沿着链中费用最小的增广链，那麽沿着μ去调整去调整X得到的新的可行流得到的新的可行流 就就是流量为是流量为 f ( )的最小费用流。

的最小费用流7（（2）实现思路）实现思路 基于第一种求解途径，根据上述基于第一种求解途径，根据上述定理，只要定理，只要找到最小费用增广链，在找到最小费用增广链，在该链上调整流量，得到增加流量后的该链上调整流量，得到增加流量后的最小费用流最小费用流循环往复直至求出最小循环往复直至求出最小费用最大流费用最大流8 实施中的关键实施中的关键 构造构造增广费用网络图增广费用网络图（即扩展费用网络图），（即扩展费用网络图），借助借助最短路算法最短路算法寻找寻找最小费用增广链最小费用增广链增广费用网络图增广费用网络图的的构造方法构造方法将网络中的每一条弧（将网络中的每一条弧（vi,vj）都变成一对）都变成一对方向相反的弧，以形成方向相反的弧，以形成四通八达的四通八达的“路路”，权数定义如下：，权数定义如下： 9零流弧上零流弧上零流弧上零流弧上 WWij ij = =cij 原有弧（流量可以增加）原有弧（流量可以增加）∞ 后加弧（流量不能再减少）后加弧（流量不能再减少） 饱和弧上饱和弧上饱和弧上饱和弧上wij =∞ 原有弧（流量不能再增加）原有弧（流量不能再增加） -cij 后加弧（流量可以减少）后加弧（流量可以减少） 非饱和且非零流非饱和且非零流非饱和且非零流非饱和且非零流 (0

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

否则转入第一步，进入下一次束否则转入第一步，进入下一次迭代过程迭代过程 174、举例、举例增广费用网络图增广费用网络图(容量费用图容量费用图(bij,cij)) 可可 行行 流流 图图 (流量网络流量网络(bij,cij,xij))vsvtv2v3v1(10,7)(7,7)(8,4)(10,4)(4,4)(5,0)(2,0)最大流图最大流图fmax=11 (未标费用未标费用) 第第 0 次次 迭迭 代代18vsvtv2v3v1(10,4)(7,1)(8,1)(10,3)(4,2)(5,2)(2,6)(5,2,5)(7,1,5)vsvtv2v3v1(10,4,0)(8,1,5)(10,3,0)(4,2,0)(2,6,0)第第 1 次次 迭迭 代代①①原图全部是零流弧原图全部是零流弧, ,保持原保持原边不变边不变, ,单位费用为权；单位费用为权；②②所有的权均大于零，可用所有的权均大于零，可用D D氏标号法求出最短路：氏标号法求出最短路：恰也是恰也是最小费用增广链最小费用增广链最小费用增广链最小费用增广链 ①①流量调整量流量调整量εε1 1=min{8-0,5-0,7-0}=5=min{8-0,5-0,7-0}=5 总流量总流量f f1 1=5=5②②最小费用增广链的费用最小费用增广链的费用∑∑c cijij=1+2+1=4=1+2+1=4③③总费用总费用C C1 1=4=4××5=205=20 19第第 2 次次 迭迭 代代(3,1)v1vt(5,-2)(2,6)v2v3(10,4)(5,-1)(10,3)(4,2)（（2,1））vs（（5，，-1））(7,1,7)vsvtv2v3v1(10,4,2)(8,1,5)(10,3,0)(4,2,0)(2,6,0)(5,2,5)①①零流弧保持原边零流弧保持原边, ,非饱和非非饱和非零流弧零流弧(v(vs s,v,v2 2) )和和(v(v1 1,v,vt t) )增添后增添后加弧加弧, ,饱和弧饱和弧(v(v2 2,v,v1 1) )去掉原弧去掉原弧增添后加弧；增添后加弧；②②用列表法求出最短路用列表法求出最短路: :恰也是最小费用增广链恰也是最小费用增广链。

①①流量调整量流量调整量εε2 2=min{10-0,2-0}=2=min{10-0,2-0}=2，，总流量总流量= =原流量原流量+ +新增流量新增流量 =5+2=7=5+2=7；；②②最小费用增广链的费用最小费用增广链的费用 ∑ ∑c cijij=4+1=5=4+1=5③③总费用总费用C C2 2= =原费用原费用+ +新增费用新增费用=20+5=20+5××2=30 2=30 20vsvtv2v3v1(8,4)（（2,-4））(5,-1)(7,-1)(10,3)(4,2)(2,6)(5,-2)(3,1)①①零流弧保持原边，此外的非零流弧保持原边，此外的非饱和弧增添后加弧，饱和弧去饱和弧增添后加弧，饱和弧去掉原边增添反向虚线弧掉原边增添反向虚线弧②②用列表法求得最短路用列表法求得最短路恰也是最小费用增广链恰也是最小费用增广链①①流量调整量流量调整量εε3 3=min{3=min{3，，10,4}=310,4}=3，，总流量总流量= =原流量原流量+ +新增流量新增流量 =7+3=10=7+3=10；；②②最小费用增广链的费用最小费用增广链的费用 ∑ ∑c cijij=1+3+2=6=1+3+2=6③③总费用总费用C C2 2= =原费用原费用+ +新增费新增费用用=30+6=30+6××3=48 3=48 第第 3 次次 迭迭 代代(7,1,7)vsvtv2v3v1(10,4,2)(8,1,8)(10,3,3)(4,2,3)(2,6,0)(5,2,5)21(2,6)(7,3)(8,4)vsvtv2v3v1(3,-3)(7,-1,)(8,-1)(3,-2)（（1,2））(2,-4)（（5,-2））①①零流弧保持原边，此外的非饱零流弧保持原边，此外的非饱和弧增添后加弧，饱和弧去掉原和弧增添后加弧，饱和弧去掉原边增添反向虚线弧；边增添反向虚线弧；②②用列表法求得最短路用列表法求得最短路 ③③对应的最小费用增广链是对应的最小费用增广链是①①流量调整量流量调整量εε4 4=min{8,5,7,1}=1=min{8,5,7,1}=1，，总流量总流量= =原流量原流量+ +新增流量新增流量=10+1=11=10+1=11；；②②最小费用增广链的费用最小费用增广链的费用 ∑ ∑c cijij=4-2+3+2=7=4-2+3+2=7③③总费用总费用C C2 2= =原费用原费用+ +新增费用新增费用 =48+7=48+7××1=551=55。

由于总流量由于总流量1111已达到最大流量，故停已达到最大流量，故停止迭代，止迭代，当前的可行流图即最大流图当前的可行流图即最大流图第第 4 次次 迭迭 代代(7,1,7)vsvtv2v3v1(10,4,3)(8,1,8)(10,3,4)(4,2,4)(2,6,0)(5,2,4)22 第十三次作业第十三次作业 P162：：7；； P163：：8；；23。