网络优化ppt课件

《网络优化ppt课件》由会员分享，可在线阅读，更多相关《网络优化ppt课件（76页珍藏版）》请在装配图网上搜索。

1、网络优化ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望 许多实际问题都可以转化为最小费用流问题 S ST T最小费用流问题的例子公路交通网络：车辆路线确定最短路问题 最小费用流问题 1辆车 多辆车:车流 2定义定义7.1 在流网络在流网络N=(V,A，L,U,D)上增加如下的权函数：上增加如下的权函数：C：A R为弧上的权函数，弧（为弧上的权函数，弧（i，j）对应的权）对应的权 C（i，j）记）记为为cij ，称为弧（，称为弧（i，j）的单位流量的成本

2、或）的单位流量的成本或费用费用（cost）;此时网络可称为此时网络可称为容量容量-费用网络费用网络 (一般仍可简称为一般仍可简称为网络网络),),记为记为 N=(V,A,C，L,U,D).7.1.1 7.1.1 最小费用流问题最小费用流问题 di 0:供应点供应点(supply node)(supply node)或源或源(source)(source)、起始点或发货点、起始点或发货点 di 0:需求点需求点(demand node)或汇或汇(sink)、终止点或吸收点终止点或吸收点 di 0:转运点转运点(transshipment node)或平衡点、中间点或平衡点、中间点 可以把可以把L

3、 0的网络转化为的网络转化为L=0的网络进行研究的网络进行研究(思考思考？)除非特别说明除非特别说明,假设假设L=0,网络简记为网络简记为N=(V,A,C，U,D).3定义定义7.2（容量容量-费用网络中的费用网络中的流(flow)的定义同前一章）流x的（总）费用定义为 通常又称为转转运运问问题题(transshipment(transshipment problem)problem)或容容量量受受限限的的转转运问题运问题(capacitated transshipment problem).(capacitated transshipment problem).最小费用流问题就是在网络中寻找

4、总费用最小的可行流.最小费用流问题最小费用流问题引理引理7.17.1 最小费用流问题存在可行流的必要条件 经典的最小费用流问题：单源单汇(起点s，终点t)，寻找从s流到t的给定流量(或最大流量、最小流量等)的最小费用流.线性费用网络线性费用网络思考：思考：经典问题与一般问题有什么关系？是否等价？经典问题与一般问题有什么关系？是否等价？4例 7.1 最短路问题在有向网络中，令所有弧上容量下界为0，容量（上界）为1，并令图中节点s的供需量为1，节点t的供需量为-1，则：从从s到到t的一条有向路正好对应于网络中的一个可行流的一条有向路正好对应于网络中的一个可行流x （弧(i，j)位于s-t路上：xi

5、j=1；弧(i，j)不在s-t路上：xij=0）.如果再令所有弧上的(单位流量)的费用为“弧长”,则此时的最小费用流问题就是第五章讨论过的最短路问题.在第五章我们正是用这样的方式对最短路问题进行建模的 7.1.2 7.1.2 最小费用流模型的特例及扩展最小费用流模型的特例及扩展 P Ps st t5例-最大流问题 设s为起点,t为终点,增加弧(t,s),令7.1.2 7.1.2 最小费用流模型的特例及扩展最小费用流模型的特例及扩展s st t而令所有其他弧上的费用为0,所有顶点上的供需量(外部流量)全为0.6例-运输问题(transportation Problem)又称Hitchcock问题

6、（Hitchcock,1941年）完全二部图只有源和汇没有中间转运点 ST7.1.2 7.1.2 最小费用流模型的特例及扩展最小费用流模型的特例及扩展如果每条弧上还有容量(上下限)的限制,则称为容容量量受受限限的的运运输问题输问题(capacitated transportation problem)(capacitated transportation problem).有解的必要条件可以不失一般性指派问题(assignment problem)77.1.2 7.1.2 最小费用流模型的特例及扩展最小费用流模型的特例及扩展（1）当一定的流量流过一条弧时，该弧上导致的总费用与流量大小成线性正比

7、正比关系，这样的流网络一般称为线性费用网络线性费用网络.如果当一定的流量流过一条弧时，该弧上导致的总费用不一定与流量大小成线性正比关系，而是流量大小的一个凹（或凸）函数，则这样的网络称为凹凹（或或凸凸）费费用用网网络络，相应的最小费用流问题称为凹（凸）费用网络上的最小费用流问题.（2）当流量流过一条弧时，流出该弧的流量（即流入该弧终点的流量）与进入该弧的流量（即流出该弧起点的流量）相等相等.如果当流量流过一条弧时，流出该弧的流量是进入该弧的流量的一个线线性性函函数数，即流出该弧的流量是对进入该弧的流量按一定比例进行放大或缩小的结果，则这样的流网络一般称为带带增增益益(或盈亏或盈亏)的流网络的流

8、网络（flow with gain network）.增益除了可以发生在弧弧上，类似地可以考虑增益发生在节点节点上87.1.2 7.1.2 最小费用流模型的特例及扩展最小费用流模型的特例及扩展 最 小 费 用 流 问 题指 派问 题运 输问 题最大流问题最短路问题带 增 益 的最小费用流问题线性规划问题凹费用网络的最小费用流问题凸费用网络的最小费用流问题狭义模型 广义模型 凸规划 9单源单汇网络单源单汇网络可行流可行流x的的流量流量（或（或流值流值）为）为v=v（x）=ds=-dt如果我们并不给定如果我们并不给定ds 和和dt,则网络一般记为则网络一般记为N=(s,t,V,A,C,U)容量可行

9、且转运点流量守恒的流称为容量可行且转运点流量守恒的流称为s-t可行流可行流，有时为了方，有时为了方便也称为可行流便也称为可行流.最小费用流问题就是在网络最小费用流问题就是在网络N=(s,t,V,A,C,U)中计算流值为中计算流值为v的的最小费用流最小费用流x 或者当不给定流值时或者当不给定流值时,计算流值最大的最小费用流计算流值最大的最小费用流x(此时流此时流x称为称为最小费用最大流最小费用最大流).7.2 消圈算法与最小费用路算法消圈算法与最小费用路算法 最小费用最小流最小费用最小流?107.2 消圈算法与最小费用路算法消圈算法与最小费用路算法 定定义义7.3 对对网网络络N=(s,t,V,

10、A,C,U)中中给给定定的的s-t可可行行流流x，网网络络N关关于于流流x的的残残量量网网络络N(x)=(s,t,V,A(x),C(x),U(x),其其中中A(x),C(x)，U(x)定义如下：定义如下：（residual network，或增量网络或辅助网络，或增量网络或辅助网络）讨论算法复杂度时，假定讨论算法复杂度时，假定:弧（弧（i，j）A时，弧（时，弧（j，i）A；c ij=-cjiA（x）=A(允许容量为允许容量为0的弧仍然保留在网络中就可以了的弧仍然保留在网络中就可以了)其中称其中称,uij(x)为弧为弧(i,j)上的上的残留容量残留容量(residual capacity).11

11、定义W的费用为 对于N(x)中的任何一个有向圈W,它一定对应于原网络N中的一个增广圈(增广弧构成的圈)；通过沿W对当前流x进行增广，可以获得流值相等的s-t可行流y.消圈算法的思想消圈算法的思想则当增广的流量为则当增广的流量为 时时 只要N中存在费用为负数的增广圈W，即C（W）0，则可以通过沿W 对当前流 x 进行增广，获得流值相等但费用更小的s-t可行流y.12 设设x0为不同于的可行流，但费用低于为不同于的可行流，但费用低于x的费用，即的费用，即 7.2.1 7.2.1 消圈算法消圈算法(cycle-canceling algorithm)(cycle-canceling algorith

12、m)定定理理7.1 7.1 可可行行流流x为为最最小小费费用用流流的的充充要要条条件件是是N(x)中中不不存存在在负负费费用增广圈用增广圈.令令 x1=x0-x,则则 ，即令，即令x1为网络为网络N中的循环流中的循环流.一一个个循循环环流流一一定定可可以以表表示示为为至至多多m个个非非零零圈圈流流之之和和，所所以以可可以以将将x1表表示示为为r个个非零圈流之和（非零圈流之和（）。设对应的有向圈为）。设对应的有向圈为Wk，至至少少存存在在一一个个费费用用为为负的增广圈负的增广圈.矛盾矛盾 必要性是显然的必要性是显然的.反证法证明充分性：反证法证明充分性：13N(x)中找负圈可用最短路算法中找负圈

13、可用最短路算法(如如Bellman-Ford算法，算法，O(m n)则该算法的复杂度为则该算法的复杂度为O(n m 2CU),不是多项式时间算法不是多项式时间算法.STEP 2.沿找到的负圈增广流量沿找到的负圈增广流量,转转STEP 1.Step0Step0可借用最大流算法可借用最大流算法，复杂度为复杂度为O(n2m)STEP 0.在网络在网络N=(s,t,V,A,C,U)中计算流值为中计算流值为v的可行流的可行流 x.7.2.1 7.2.1 消圈算法消圈算法:Klein(1967):Klein(1967)等等 STEP 1.在在残残量量网网络络N(x)中中判判别别负负圈圈.若若无无负负圈圈,

14、则则已已经经找找到到了了最小费用流，结束；否则转最小费用流，结束；否则转STEP 2.如按一些特定次序消圈如按一些特定次序消圈,可得到一些多项式时间算法可得到一些多项式时间算法 复杂度？复杂度？v任何可行流的费用不可能超过任何可行流的费用不可能超过mCUv设数据是整数设数据是整数,每次消去一个负圈至少使费用下降一个单位每次消去一个负圈至少使费用下降一个单位v设数据是整数设数据是整数,消去负圈的消去负圈的STEP12最多执行最多执行O(mCU)次次14略略 7.2.1 7.2.1 消圈算法消圈算法,例：例：15能能否否首首先先在在网网络络N=(s,t,V,A,C,U)中中计计算算流流值值为为v且

15、且费费用用最最小小的的s-t可行流可行流(v v)，然后对它沿增广路增广以增加流值呢，然后对它沿增广路增广以增加流值呢?7.2.2 7.2.2 最小最小费费用路算法用路算法 为为了了获获得得最最小小费费用用流流，我我们们希希望望沿沿费费用用最最小小的的增增广广路路对对当当前前流流x进行增广，以最小的费用增加获得流值更大的进行增广，以最小的费用增加获得流值更大的s-t可行流可行流y 对对于于N(x)中中的的一一条条从从s到到t的的有有向向路路P,它它一一定定对对应应于于原原网网络络N中中的的一一条条增增广广路路，即即可可以以通通过过沿沿P对对当当前前流流x进进行行增增广广，获获得得流流值值更更大

16、的大的s-t可行流可行流y.定义定义P的费用为的费用为 则当增广的流量为则当增广的流量为 时时 167.2.2 7.2.2 最小最小费费用路算法用路算法定定理理7.2 设设x为为流流值值为为v的的最最小小费费用用流流，P为为关关于于x的的从从s到到t的的一一条条最最小小费费用用增增广广路路，且且沿沿P所所能能增增广广的的流流量量为为 ，则则增增广广后后得得到到流流值为值为v+的最小费用流的最小费用流y y.只需证明网络中不存在关于只需证明网络中不存在关于y y的负费用增广圈的负费用增广圈.用反证法用反证法 假设增广后存在关于假设增广后存在关于y的负费用增广圈的负费用增广圈W.由于除由于除P以外

17、的弧及其流量在增广前以外的弧及其流量在增广前后没有发生改变后没有发生改变,于是于是P和和W至少有一条公共弧至少有一条公共弧.不妨假设不妨假设P和和W只有一条公只有一条公共弧共弧,记为记为(i,j)如果如果(i,j)在在P中是正向弧中是正向弧,则在则在W中是反向弧中是反向弧;反之反之,如果如果(i,j)在在P中是中是反向弧反向弧,则在则在W中是正向弧中是正向弧 也是网也是网络中关于络中关于x x的增广路的增广路,且且 t tP PW Ws si ij j177.2.2 7.2.2 最小最小费费用路算法用路算法也称为连续最短路算法也称为连续最短路算法,即即Successive Shortest P

18、ath Algorithm),Jewell(1958),Iri(1960),Busacker&Gowen(1961)独立提出的独立提出的STEP 0.取取x为任一为任一s-t可行流、且在同一流值的流中费用最小的可行流、且在同一流值的流中费用最小的流流(如如x=0).STEP 1.若若x的流值达到的流值达到v,结束；否则在残量网络结束；否则在残量网络N(x)中判别最中判别最小费用路小费用路.若无这样的路若无这样的路,则流值不可达到则流值不可达到v,结束；否则结束；否则STEP 2.STEP 2.沿该最小费用增广路增广流量沿该最小费用增广路增广流量(增广后的流值不超过增广后的流值不超过v),转转S

19、TEP 1.STEP1可用最短路算法：记最短路算法的复杂度为可用最短路算法：记最短路算法的复杂度为S(n，m，C)STEP12最多执行最多执行O(v)次次 复杂度？复杂度？最大流流值不超过最大流流值不超过nU，本算法复杂度为，本算法复杂度为 O(nU S(n，m，C)采用特定的变尺度技术采用特定的变尺度技术,可以得到一些多项式时间算法可以得到一些多项式时间算法 18略略 7.2.2 7.2.2 最小最小费费用路算法用路算法,例：例：19 7.3.1 7.3.1对偶问题及互补松弛条件对偶问题及互补松弛条件 仍然考虑传统的单源单汇网络的最小费用流问题仍然考虑传统的单源单汇网络的最小费用流问题 两类

20、约束分别引入对偶变量两类约束分别引入对偶变量 和和z,则这一问题的对偶问题为则这一问题的对偶问题为 7.3 7.3 原始原始-对偶算法对偶算法 20互补松弛条件互补松弛条件 设设x和和(,z)分别为原问题和对偶问题的可行解：分别为原问题和对偶问题的可行解：下面我们说明在一定的下面我们说明在一定的“约定约定”下下,这一条件可以等价地写成这一条件可以等价地写成当当 时时，=0；(7.19)当当 时，时，=；(7.20)当当 时，时，.(7.21)约约定定:存存在在对对偶偶可可行行的的变量变量z z，使得上式成立，使得上式成立.定定理理7.3 设设x为为原原问问题题的的可可行行解解,则则x为为最最小

21、小费费用用流流的的充充要要条条件件是是:存在节点的势（存在节点的势（）,满足条件满足条件(7.19)(7.21).7.3.17.3.1对偶问题及互补松弛条件对偶问题及互补松弛条件记记“相对费用相对费用”（Reduced Reduced CostCost）217.3.17.3.1对偶问题及互补松弛条件对偶问题及互补松弛条件 引引理理7.2 最最优优性性条条件件(7.19)(7.21)等等价价于于，对对于于N(x)中中任任意的意的(i,j)弧弧,0 假设假设(7.19)(7.21)成立成立,则对于原网络中的一条弧则对于原网络中的一条弧(i,j),当当 0,所以所以 =-()=-0,因此因此(j,i

22、)弧不属于残量网络弧不属于残量网络N(x).所以所以 =0.当当 时，即时，即 0 时时，=0；(7.19)当当 0 时时，=；(7.23)当当 0 时时，=；(7.23)当当 0 时，时，=；(7.24)当当 时，时，=0 =0.(7.25)39 -残量网络残量网络7.4瑕疵算法 当当xijuij 时时,则则(j,i)N(x),uji(x)=xij-uij,cji(x)=-cij.瑕疵算法仍然是在残量网络上对弧上的流量进行操作瑕疵算法仍然是在残量网络上对弧上的流量进行操作;由于流不一定满足容量约束由于流不一定满足容量约束,需定义这时残量网络的构造方法需定义这时残量网络的构造方法:把把原原网网

23、络络中中可可能能增增加加流流量量的的弧弧(前前向向弧弧)、减减少少流流量量的的弧弧(反反向向弧弧)纳入残量网络纳入残量网络.具体具体方法如下方法如下:瑕疵算法的思想：瑕疵算法的思想：在算法过程中使弧上的在算法过程中使弧上的Kilter数不断下降数不断下降,最后降为最后降为0.当当 时时:如如果果xijlij,则则(j,i)N(x),uji(x)=xij-lij,cji(x)=-cij.40 -残量网络残量网络7.4瑕疵算法 可以直接定义弧可以直接定义弧(i,j)N(x)的的KilterKilter数，分三种情况讨论数，分三种情况讨论:可可知知:原原网网络络中中的的任任何何一一条条瑕瑕疵疵弧弧一

24、一定定会会在在残残量量网网络络中中得得到到反反映映(即瑕疵弧不以前向弧的形式出现即瑕疵弧不以前向弧的形式出现,就以反向弧的形式出现就以反向弧的形式出现).).当当 时时:如如果果(i,j)是是瑕瑕疵疵弧弧(0),则则其其Kilter数数必必然然等等于于(i,j)的残留容量的残留容量:kij=uij(x)当当xijlij时时:如果如果 0,则则kij=uij(x)=lij-xij;如果如果 uji 时时:如如果果 0(即即 0),则则kij=xji-lji;如如果果 0(即即 0),则则kij=uij(x)=xji-uji.41 -步骤步骤7.4瑕疵算法 STEP 0.STEP 0.给出初始势和

25、初始循环流给出初始势和初始循环流(如如=0,=0,x=0).=0).Yakovleva(1959),Minty(1960),Fulkerson(1961)Yakovleva(1959),Minty(1960),Fulkerson(1961)等提出等提出;AashtianiAashtiani和和Magnanti(1976)Magnanti(1976)给出一种高效率的实现方法给出一种高效率的实现方法.STEP 1.计计算算弧弧上上的的Kilter数数.若若网网络络中中不不存存在在瑕瑕疵疵弧弧,则则已已经经得得到到最最优优解解,计计算算结结束束；否否则则在在残残量量网网络络N(x)中中，选选择择一一

26、条条瑕瑕疵疵弧弧（p,q）,继续下一步继续下一步.STEP 3.若若（p,q）仍仍为为瑕瑕疵疵弧弧,则则沿沿 P (p,q)确确定定的的增增广广圈圈增增广广流流量量(增增广广的的流流值值为为该该增增广广圈圈的的容容量量),转转STEP 1;否否则则直直接接转转STEP 1.STEP 2.在在N(x)(q,p)中中,以以max0,为为（i,j）弧弧的的弧弧长长，计计算算从从节节点点q到到所所有有节节点点 i 的的最最短短路路路路长长d(i)，并并记记从从节节点点q到到节节点点p的最短路为的最短路为P.令令 i =i -d(i),继续继续STEP 3.主要过程主要过程:一是对节点上势的修改一是对节

27、点上势的修改;一是沿增广圈增广一是沿增广圈增广42 -正确性正确性7.4瑕疵算法 证明证明 引引理理7.6 7.6 在在瑕瑕疵疵算算法法中中,对对节节点点上上势势的的修修改改不不会会增增加加任任何何弧弧上上的的KilterKilter数数.=-+=-(i-d(i)+(j-d(j)=+(d(i)-d(j)-max0,当当 0:-max0,=0 (6.26)当当 0,)0,所以所以 =-+=-(i-d(i)+(j-d(j)=+(d(i)-d(j)(6.28)43 -正确性正确性7.4瑕疵算法 从从KilterKilter数数的的定定义义知知:当当弧弧上上流流量量保保持持不不变变时时,只只有有的的符

28、符号号改改变时变时,弧上的弧上的KilterKilter数才可能改变数才可能改变.下面分别对几种情况讨论下面分别对几种情况讨论:节点上势的修改不会增加任何弧上的节点上势的修改不会增加任何弧上的KilterKilter数数.沿增广圈增广呢沿增广圈增广呢?当当 时时:如如果果(i,j)关关于于 是是无无瑕瑕弧弧,则则关关于于 也也是是无无瑕瑕弧弧;如如果果(i,j)关关于于 是是瑕瑕疵疵弧弧(uji 时时:此时在节点上势的修改前后此时在节点上势的修改前后(i,j)一定都是瑕疵弧一定都是瑕疵弧.与与xijlij类似可证类似可证当当xijlij时时:此此时时在在节节点点上上势势的的修修改改前前后后（i

29、,j）一一定定都都是是瑕瑕疵疵弧弧.如果如果 0,则则 0,kij=kij=uij(x)=lij-xij不变不变.如果如果 0,则则:若若 0,0,则则kij=kij=uij-xij不变不变;若若 0,0,则则kij=lij-xij uij-xij44 -正确性正确性7.4瑕疵算法 引引理理7.7 7.7 在在瑕瑕疵疵算算法法中中,沿沿增增广广圈圈P P (p,qp,q)增增广广流流量量不不会会增增加任何弧上的加任何弧上的KilterKilter数数,且弧且弧(p,qp,q)的的KilterKilter数严格减少数严格减少 沿增广圈沿增广圈P (p,q)增广流量只可能改变圈上的弧及其反向弧的增

30、广流量只可能改变圈上的弧及其反向弧的Kilter数数.对对于于增增广广圈圈上上容容量量不不可可行行的的弧弧(i,j),由由残残量量网网络络的的构构造造方方法法可可知知:流流量量增增广广后后该弧的该弧的Kilter数一定严格下降数一定严格下降,且不会在残量网络中加入新的弧且不会在残量网络中加入新的弧(j,i).对于增广圈上容量可行的弧对于增广圈上容量可行的弧,流量增广不改变容量可行弧的容量可行性流量增广不改变容量可行弧的容量可行性.=-+=-(i-d(i)+(j-d(j)=+(d(i)-d(j)0 对于最短路对于最短路P上的容量可行弧上的容量可行弧(i,j),由最短路方程有由最短路方程有 d(j

31、)=d(i)+max0,d(i)+若若弧弧(i,j)在在原原网网络络中中对对应应的的弧弧为为(i,j),则则流流的的增增广广不不会会增增加加其其Kilter数数，且当且当 0时实际上会严格减少其时实际上会严格减少其Kilter数数.若若弧弧(i,j)在在原原网网络络中中对对应应的的弧弧为为(j,i),则则由由 =-0可可知知,流流的的增增广广也不会增加其也不会增加其Kilter数，且当数，且当 0时实际上会严格减少其时实际上会严格减少其Kilter数数.45 -正确性正确性7.4瑕疵算法 最后看看弧最后看看弧(p,q),也只需要分析它为容量可行的弧的情况也只需要分析它为容量可行的弧的情况.证毕

32、证毕 注注意意到到沿沿容容量量可可行行弧弧(i,j)的的增增广广可可能能会会在在残残量量网网络络中中加加入入新新的的弧弧(j,i).但但由由于于 =-0,所所以以在在残残量量网网络络中中新新加加入入的的弧弧(j,i)是满足是满足Kilter条件的条件的.由由算算法法STEP3,只只有有它它为为瑕瑕疵疵弧弧时时才才进进行行增增广广,即即 0,因因此此增增广广也也不不会会使使(q,p)成成为为残残量量网网络中的瑕疵弧络中的瑕疵弧.46 -复杂度分析复杂度分析 7.4瑕疵算法 每每次次循循环环迭迭代代修修改改圈圈上上的的流流值值和和节节点点上上的的势势各各一一次次,并并使使所所有有弧上的总弧上的总K

33、ilterKilter数至少下降数至少下降1 1个单位个单位.设初始流和势对应的总设初始流和势对应的总Kilter数为数为K,则总迭代次数不会超过则总迭代次数不会超过K.记记求求解解非非负负弧弧长长网网络络的的最最短短路路算算法法的的复复杂杂度度为为S(n，m，C),则则本本算法复杂度为算法复杂度为O(K S(n，m，nC).特特别别地地,当当取取初初始始流流x=0时时,由由于于每每条条弧弧上上的的Kilter数数不不超超过过U,算算法复杂度可以写成为法复杂度可以写成为O(mU S(n，m，nC).由此可以看出由此可以看出,瑕疵算法仍然不是多项式时间算法瑕疵算法仍然不是多项式时间算法.47 -

34、算法思想算法思想对对(7.1)引引入入Lagrange乘乘子子(仍仍然然称称为为i节节点点上上的的势势,由由于于约约束束(7.1)为为等等式式,所所以以没没有有符符号号限限制制),则则得得到到如如下下的的Lagrange松松弛弛问题问题:7.5 7.5 松弛算法（松弛算法（Relaxation AlgorithmRelaxation Algorithm）如如果果 0,0,则则令令xij=0=0(下下界界););如如果果 0,0时时,称称e(i)为为节节点点i的的盈盈余余(Excess);e(i)r(,S):同时修改同时修改 和和x,使得使得LR()严格增加严格增加.7.5 7.5 松弛算法松弛

35、算法由（由（7.29）：）：LR()增加增加 e(S)-r(,S)算算法法首首先先沿沿(S,)中中满满足足 =0的的弧弧增增广广流流量量使使之之饱饱和和,即即流流量量达达到残留容量的上界到残留容量的上界,相应的弧不再属于残量网络相应的弧不再属于残量网络;从从(7.29)可可知知,这这样样的的修修改改不不会会改改变变 c(x,)的的值值,但但使使得得S中的节点上的总盈余减少中的节点上的总盈余减少为为 e(S)-r(,S)（仍然为正数）仍然为正数）.由由于于算算法法保保持持互互补补松松弛弛条条件件,对对于于N(x)中中的的任任意意弧弧一一定定有有 0.增增广广后后前前向向弧弧集集(S,)中中的的弧

36、弧满满足足 0,记记其其中中的的最最小小值值为为 0.N(x)中的任意弧仍有中的任意弧仍有 0：保持互补松弛条件保持互补松弛条件51 -算法思想算法思想(case2)若若e(S)r(,S):不变，不变，修改修改x,使得使得e(S)严格减少严格减少.7.5 7.5 松弛算法松弛算法如果如果e(j)0,则算法沿子树中从则算法沿子树中从 s 到到 j 的一条增广路增广流量的一条增广路增广流量.从从(7.29)可可知知,这这样样的的修修改改不不会会改改变变 c(x,)的的值值,但但使使得得S中中的节点上的总盈余减少的节点上的总盈余减少由由0 r(,S),则则转转STEP 3;否否则则在在(S,)中中选

37、选取取一一条条满满足足 =0的的弧弧（i,j）.若若e(j)0.转转STEP 1.STEP 4.根根据据pred中中记记录录的的节节点点,确确定定子子树树中中从从s到到j的的一一条条增增广广路路P.沿沿P增增广广流流量量 .转转STEP 1.53松弛算法松弛算法 复杂度分析当当给给定定的的数数据据都都是是整整数数时时,算算法法每每执执行行一一次次第第二二类类操操作作,则则LR()至少增加至少增加1个单位个单位.算算法法开开始始时时LR()=0,且且算算法法执执行行过过程程中中LR()不不可可能能超超过过最最小小费用的上界费用的上界mCU.因此因此STEP 3最多执行最多执行mCU次次.算法每执

38、行一次第一类操作算法每执行一次第一类操作,则总赢余至少减少则总赢余至少减少1个单位个单位;而而总总赢赢余余不不可可能能超超过过上上界界(m+n)U,因因此此在在两两次次连连续续第第二二类类操操作作之之间间,执行第一类操作执行第一类操作(STEP 4)的次数不超过的次数不超过(m+n)U=O(mU)次次.执执行行一一次次第第一一类类操操作作(包包括括构构造造增增广广路路的的STEP2在在内内)的的复复杂杂度度为为O(mn),因此算法的总时间复杂度为因此算法的总时间复杂度为O(mCUmUmn)=O(nm3CU2).思考：如果不是整数数据，算法一定有限步停止吗？思考：如果不是整数数据，算法一定有限步

39、停止吗？从从理理论论看看,复复杂杂度度高高；但但计计算算测测试试表表明明松松弛弛算算法法的的实实际际计计算算效效率率非非常常高高,是是目目前前实实际际计计算算效效率率最最高高的的两两个个算算法法之之一一(另另一一个个算算法是网络单纯形方法法是网络单纯形方法,我们将在下一节进行介绍我们将在下一节进行介绍).).54 -例例略略7.5 7.5 松弛算法松弛算法55布 置 作 业（第第2 2讲）讲）目的掌握瑕疵算法及复杂性分析；掌握松弛算法松弛算法及复杂性分析内容网络优化第网络优化第245-251页页7;17;20（第（第2讲）讲）思考8；10；18（不交）（不交）56网网 络络 优优 化化 Net

40、work Optimizationhttp:/ 谢金星办公室：理科楼2206#（电话：62787812）Email: http:/ 7章章 最小费用流问题最小费用流问题 (Minimum Cost Flow Problem)第第3讲讲57 线性规划问题的单纯形算法的一般思路是：线性规划问题的单纯形算法的一般思路是：首先求得问题的一个基本可行解；首先求得问题的一个基本可行解；如如果果它它不不是是最最优优解解，则则选选择择一一个个进进基基变变量量(列列)和和一一个个出出基基变变量（列），通过旋转（量（列），通过旋转（PivotPivot）变换改进到另一个基本可行解；）变换改进到另一个基本可行解；如

41、如此此反反复复迭迭代代，直直到到检检验验数数（或或称称相相对对费费用用，Reduced Reduced CostCost）都大于等于）都大于等于0 0为止，获得最优解为止，获得最优解.算法的计算过程通常利用单纯形表进行算法的计算过程通常利用单纯形表进行.对对于于网网络络优优化化问问题题,基基的的结结构构是是非非常常特特殊殊的的,因因此此可可以以避避免免显显式地列出单纯形表式地列出单纯形表.7.6 7.6 网络单纯形算法网络单纯形算法(Network Simplex Algorithm)(Network Simplex Algorithm)7.6.1 7.6.1 算法的一般思路算法的一般思路 不

42、不失失一一般般性性,以以下下总总是是假假设设流流网网络络是是连连通通的的 (否否则则该该问题可以自然地分解为几个小问题来考虑问题可以自然地分解为几个小问题来考虑).).58引引理理7.8 关关联联矩矩阵阵B的的列列构构成成一一组组基基的的充充要要条条件件是是它它所所对对应应的的弧弧为支撑树为支撑树(不考虑方向时不考虑方向时).流流网网络络是是连连通通的的,所所以以r(B)=n-1.记记B的的(n-1)列列构构成成的的子子矩矩阵阵为为B1.6.5 6.5 最高标号预流推进算法最高标号预流推进算法 -基的特殊性基的特殊性首先考虑容量无限的最小费用流问题首先考虑容量无限的最小费用流问题 7.6.1

43、7.6.1 算法的一般思路算法的一般思路 必必要要性性.若若B1为为一一组组基基,则则r(r(B1)=n-1.B1所所对对应应的的n-1条条弧弧如如果果不不连连通通,则则至至少少含含有有一一个个圈圈,因因此此r(r(B1)=0；(7.37)当当 0 时，时，=0；(7.38)设设给给定定了了一一个个基基本本可可行行解解x,基基矩矩阵阵所所对对应应的的可可行行树树为为T T.由由于于只只有有树树弧弧上上的的流流量量可可以以为为正正数数,所所以以只只有有树树弧弧才才可可能能满满足足(7.38).支支撑撑树树上上的的弧弧共共有有(n-1)条条,而而对对偶偶变变量量(节节点点上上的的势势)共共有有n个

44、个.在在相相差差一一个个常常数数的的意意义义下下,由由T T中中的的弧弧满满足足 =0可可以唯一地确定对偶变量以唯一地确定对偶变量.可可以以任任意意选选定定一一个个节节点点（这这一一节节点点通通常常称称为为“根根”（Root）,令令它它的的势势为为0;然然后后利利用用(7.38)计计算算与与它它相相邻邻的的其其它它节节点点上上的的势势,如此重复就可以方便地获得所有节点上的势如此重复就可以方便地获得所有节点上的势.如果此时使得如果此时使得(7.37)也成立也成立,则则x就是原问题的最优解就是原问题的最优解.617.6.1 7.6.1 算法的一般思路算法的一般思路 旋转变换旋转变换 W为一个负费用

45、圈为一个负费用圈,所以沿所以沿W增广流量将会使得总费用下降增广流量将会使得总费用下降.为为了了在在W中中找找出出一一条条弧弧出出基基,我我们们应应当当令令增增广广的的流流量量等等于于W-所有弧上当前流量中的最小值所有弧上当前流量中的最小值,而取到该最小值的弧出基而取到该最小值的弧出基 如果如果W-=,则原问题是无界的则原问题是无界的,即最小费用可以趋于负无穷即最小费用可以趋于负无穷为为了了找找出出一一条条弧弧出出基基,我我们们可可以以看看出出T T(p,q)一一定定含含有有唯唯一一的的圈圈W,我们把弧我们把弧(p,q)的方向定义为的方向定义为W的方向的方向.W的费用为的费用为 若若x不不最最优

46、优,则则存存在在一一条条非非树树弧弧(p,q)使使得得(7.37)不不成成立立,即即 0，弧弧(p,q)可以进入基可以进入基.62STEP 0.获得一个初始的可行树获得一个初始的可行树T及对应的基本可行解及对应的基本可行解x -步骤步骤 STEP 1.计算对偶变量计算对偶变量.7.6.1 7.6.1 算法的一般思路算法的一般思路STEP 2.判判断断是是否否最最优优解解,若若是是,则则停停止止;否否则则选选定定一一个个进进基基变变量量(即选进基弧即选进基弧(p,q).STEP 3.选选定定一一个个出出基基变变量量(即即选选出出基基弧弧),如如果果找找不不到到这这样样的的弧弧,则原问题是无界的则

47、原问题是无界的,停止停止;否则进行下一步否则进行下一步.STEP 4.设设W为为T T(p,q)所所含含的的圈圈.沿沿W的的正正向向增增广广流流量量,即即修改修改x 及对应的可行树及对应的可行树T,回到回到STEP 1.问题问题获得一个初始的可行树获得一个初始的可行树T及对应的基本可行解及对应的基本可行解x？退化与循环退化与循环？90%以上退化以上退化容量有界情形容量有界情形？复杂度复杂度？一般非为多项式算法，但可以设计多项式算法？一般非为多项式算法，但可以设计多项式算法63略略7.6.1 7.6.1 算法的一般思路算法的一般思路 例例64计算测试表明，网络单纯形法中往往计算测试表明，网络单纯

48、形法中往往90%以上的旋转是退化的以上的旋转是退化的.能否要求能否要求每次所操作的可行树每次所操作的可行树“都不相同都不相同”？7.6.2 7.6.2 处理退化的方法处理退化的方法 定定义义7.6 假假定定计计算算节节点点上上的的势势时时所所选选定定的的根根节节点点是是固固定定的的.对对于于可可行行树树T中中的的一一条条树树弧弧 (i,j),),如如果果T中中从从根根到到j的的路路通通过过节节点点i，则则(i,j)称称为为远远离离根根节节点点的的弧弧（Downward Pointing Arc）.如如果果T中中的的所所有有流流量量为为0的的弧弧都都是是远远离离根根节节点点的的弧弧，则则称称可可

49、行行树树T为为强强可可行行树树（Strongly Strongly Feasible Feasible Spanning Spanning TreeTree）.例例7.8 假假设设弧弧上上的的数数字字表表示示当当前可行流前可行流.节点节点1为根节点为根节点.T1=(1,3),(3,2),(3,4)为为 强强 可可行树行树,T2=(1,3),(2,3),(3,4)不不是是强强可可行行树树,因因为为T2中中(2,3)不不是是远远离根节点的弧离根节点的弧.1 12 23 34 40 00 00 00 02 22 265引引理理7.9 7.9 如如果果网网络络单单纯纯形形算算法法中中生生成成的的所所有

50、有可可行行树树都都是是强强可可行行树，则这些树互不相同树，则这些树互不相同.7.6.2 7.6.2 处理退化的方法处理退化的方法如果如果T T为生成树，为生成树，r r为根节点，记为根节点，记证明证明:如如果果网网络络单单纯纯形形算算法法中中的的旋旋转转变变换换不不是是退退化化的的，则则相相应应的的可可行行树对应的可行流费用互不相同，因此这些树也一定互不相同树对应的可行流费用互不相同，因此这些树也一定互不相同.所以，我们只需要考虑旋转变换退化的情况所以，我们只需要考虑旋转变换退化的情况.考考 虑虑 算算 法法 过过 程程 中中 连连 续续 生生 成成 的的 两两 棵棵 强强 可可 行行 树树

51、T，=T (p,q)(k,l),即即(p,q)为为进进基基弧弧,(k,l)为为出出基基弧弧,且且从从T到到 的旋转是退化的的旋转是退化的.66 7.6.2 7.6.2 处理退化的方法处理退化的方法记记 对应的势为对应的势为 ,根据势的确定方法根据势的确定方法,可以得到可以得到(留作练习留作练习):当当i Tp 时时,=i;当当i Tq 时时,=i +;旋旋转转变变换换前前后后,(p,q)上上的的流流量量都都是是0,由由于于 是是强强可可行行树树,所所以以(p,q)弧弧一一定定是是远远离离根根节节点点r的的弧弧.(p,q)弧弧将将 分分解解为为两两棵棵子子树树 和和 ,并且并且p,q分别属于分别

52、属于 和和 ,则则r .因此,T和 是两棵不同的强可行树.所以 =+|（0,则加入人工弧则加入人工弧(i,0);否则加入人工弧否则加入人工弧(0,i).7.6.3 初始的基本可行解初始的基本可行解 记记所所有有人人工工弧弧的的集集合合为为 ,所所有有人人工工弧弧上上的的费费用用假假定定为为一一个个充分大的正数充分大的正数M M,并称原网络假入人工弧后的新网络为人工网络并称原网络假入人工弧后的新网络为人工网络.是人工网络的一棵是人工网络的一棵(初始）强可行树初始）强可行树 70由于由于M是一个充分大的正数是一个充分大的正数,因此当算法终止时因此当算法终止时,有三种情况有三种情况:(1)(1)人人

53、工工网网络络上上的的最最小小费费用用流流问问题题有有有有界界的的最最优优解解,且且最最优优解解中中所所有有人人工工弧弧上上的的流流量量为为0,0,则则原原问问题题也也有有有有界界的的最最优优解解,且且人人工工网网络络上上非非人工弧上的流量正好就是原问题的最优解人工弧上的流量正好就是原问题的最优解.(2)人人工工网网络络上上的的最最小小费费用用流流问问题题有有有有界界的的最最优优解解,且且最最优优解解中中某某些些人工弧上的流量不为人工弧上的流量不为0,则原问题是不可行的则原问题是不可行的.实际计算中实际计算中M取多大才是取多大才是“充分大充分大”？理论上：？理论上：M (n-1)C/27.6.3

54、 初始的基本可行解初始的基本可行解(3)(3)人人工工网网络络上上的的最最小小费费用用流流问问题题没没有有有有界界的的最最优优解解(即即最最优优值值趋趋向向负无穷负无穷),),则原问题也没有有界的最优解则原问题也没有有界的最优解(即最优值趋向负无穷即最优值趋向负无穷).).实实用用中中：自自适适应应策策略略-先先取取M为为某某中中等等规规模模大大小小的的正正数数计计算算;若最优解中有人工弧上的流量不为若最优解中有人工弧上的流量不为0,则增加则增加M的规模重新计算的规模重新计算.如如果果M的的取取值值不不足足够够大大,即即使使原原问问题题有有有有界界的的最最优优解解,人人工工网网络络上上的的最小

55、费用流问题可能也会没有有界的最优解最小费用流问题可能也会没有有界的最优解(即最优值趋向负无穷即最优值趋向负无穷).).71基基可可以以用用所所有有弧弧的的一一个个划划分分(T,L,U)来来表表示示,其其中中T是是一一棵棵支支撑撑树树,L是是非非树树弧弧中中流流量量等等于于下下界界的的弧弧的的集集合合,U是是非非树树弧弧中中流流量量等等于于上上界界的的弧弧的的集集合合.三三元元组组(T,L,U)可可以以称称为为基基结结构构(有有时时也也直直接接简称为基简称为基),或支撑树结构或支撑树结构.6.5 6.5 最高标号预流推进算法最高标号预流推进算法 用用支支撑撑树树表表示示基基,只只有有树树弧弧上上

56、的的流流量量可可以以不不等等于于下下界界和和上上界界,而而所所有有非非树树弧弧上上的流量只能等于下界或上界的流量只能等于下界或上界.给给定定一一个个基基结结构构(T,L,U),非非树树弧弧上上的的流流量量已已经经确确定定,所所以以树树弧弧上上的的流流量量也也可可以以方方便便地地根根据据节节点点上上的的流流量量守守恒恒约约束束计计算算出出来来,并并且也是唯一的且也是唯一的.如如果果这这些些流流量量同同时时满满足足容容量量的的上上下下界界约约束束,则则(T,L,U)是是可可行行支支撑树结构撑树结构(简称简称可行树结构可行树结构).节点上的势也可以与前面的讨论完全类似地进行计算节点上的势也可以与前面

57、的讨论完全类似地进行计算.7.6.4 容量有界的情形容量有界的情形 72初始的强可行树结构：仍然可以构造人工网络初始的强可行树结构：仍然可以构造人工网络,采用大采用大-M方法方法.6.5 6.5 最高标号预流推进算法最高标号预流推进算法 定定义义7.7 假假定定计计算算节节点点上上的的势势时时所所选选定定的的“根根节节点点”是是固固定定的的.在在可可行行树树结结构构(T,L,U)中中,如如果果树树弧弧中中所所有有流流量量等等于于下下界界的的弧弧都都是是远远离离根根节节点点的的,并并且且树树弧弧中中所所有有流流量量等等于于上上界界的的弧弧都都不不是是远远离离根节点的根节点的(可以称为面向根节点的可以称为面向根节点的),则则(T,L,U)是强可行树结构是强可行树结构.具体细节（略，自己看书）具体细节（略，自己看书）7.6.4 容量有界的情形容量有界的情形 736.5 6.5 最高标号预流推进算法最高标号预流推进算法 说明说明目目前前，求求解解最最小小费费用用流流问问题题的的多多项项式式时时间间算算法法中中，复复杂杂度度较较低低的几个算法的最坏时间界为的几个算法的最坏时间界为 74布 置 作 业目的掌握网络单纯形算法网络单纯形算法及复杂度；内容网络优化第网络优化第245-251页页25（第（第3讲）讲）思考21；26；（不交）（不交）7576