清华大学 网络优化-第7章__最小费用流问题

1、1 网网 络络 优优 化化 Network Optimization http:/ 清华大学数学科学系 谢金星 办公室：理科楼2206# （电话：62787812） Email: http:/ 清华大学课号：清华大学课号：70420133（研）（研） 第第7 7章章 最小费用流问题最小费用流问题 (Minimum Cost Flow Problem) 第第1讲讲 2 许多实际问题都可以转化为最小费用流问题 S S T T 最小费用流问题的例子 公路交通网络：车辆路线确定 最短路问题 最小费用流问题 1辆车 多辆车:车流 3 定义定义7.1 在流网络在流网络N=( (V, ,A，L, ,U, ,

2、D) ) 上增加如下的权函数：上增加如下的权函数： C： A R为弧上的权函数，弧（为弧上的权函数，弧（i，j）对应的权）对应的权 C（i，j）记）记 为为cij ，称为弧（，称为弧（i，j）的单位流量的成本或）的单位流量的成本或费用费用（cost）; 此时网络可称为此时网络可称为容量容量- -费用网络费用网络 ( (一般仍可简称为一般仍可简称为网络网络),),记为记为 N=( (V, ,A, ,C，L, ,U, ,D) ). 7.1.1 7.1.1 最小费用流问题最小费用流问题 di 0:供应点供应点(supply node)(supply node)或源或源(source)(source)

3、、起始点或发货点、起始点或发货点 di 0:需求点需求点(demand node)或汇或汇(sink) 、终止点或吸收点终止点或吸收点 di 0:转运点转运点(transshipment node)或平衡点、中间点或平衡点、中间点 可以把可以把L 0的网络转化为的网络转化为L=0的网络进行研究的网络进行研究(思考？思考？) 除非特别说明除非特别说明, 假设假设L=0,网络简记为网络简记为N=(V,A,C，U,D). 4 定义定义7.2 （容量容量- -费用网络中的费用网络中的流(flow) 的定义同前一章） 流x的（总）费用定义为 通常又称为转运问题转运问题(transshipment pro

4、blem)(transshipment problem)或容量受限的转容量受限的转 运问题运问题(capacitated transshipment problem).(capacitated transshipment problem). 最小费用流问题就是在网络中寻找总费用最小的可行流. 最小费用流问题最小费用流问题 Aji ijij xcxc ),( )( . .)(min ),( tsxcxc Aji ijij ) 1 . 7(, ),( :),( : Vidxx i Aijj ji Ajij ij )2 . 7(),(,0Ajiux ijij 引理引理7.17.1 最小费用流问题存在

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

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

7、on Problem) 又称Hitchcock问题（Hitchcock,1941年） 完全二部图 只有源和汇 没有中间转运点 ST 7.1.2 7.1.2 最小费用流模型的特例及扩展最小费用流模型的特例及扩展 )8 . 7(.),(, 0 )7 . 7(, )6 . 7(,. . )5 . 7(min ),( : ),( : ),( Ajix Tjbx Siaxts xc ij j Ajii ij i Ajij ij Aji ijij 如果每条弧上还有容量(上下限)的限制, 则称为容量受限的运容量受限的运 输问题输问题(capacitated transportation problem)(c

8、apacitated transportation problem). . 有解的必要条件 Tj j Si i ba 可以不失一般性 Tj j Si i ba 指派问题(assignment problem) | , 1TSba ji 8 7.1.2 7.1.2 最小费用流模型的特例及扩展最小费用流模型的特例及扩展 （1）当一定的流量流过一条弧时，该弧上导致的总费用与流量 大小成线性正比正比关系，这样的流网络一般称为线性费用网络线性费用网络. 如果当一定的流量流过一条弧时，该弧上导致的总费用不一定 与流量大小成线性正比关系，而是流量大小的一个凹（或凸） 函数，则这样的网络称为凹（或凸）费用网络

9、凹（或凸）费用网络，相应的最小费 用流问题称为凹（凸）费用网络上的最小费用流问题. （2）当流量流过一条弧时，流出该弧的流量（即流入该弧终点 的流量）与进入该弧的流量（即流出该弧起点的流量）相等相等. 如果当流量流过一条弧时，流出该弧的流量是进入该弧的流量 的一个线性函数线性函数，即流出该弧的流量是对进入该弧的流量按一 定比例进行放大或缩小的结果，则这样的流网络一般称为带增带增 益益( (或盈亏或盈亏) )的流网络的流网络（flow with gain network）. 增益除了可以发生在弧弧上，类似地可以考虑增益发生在节点节点上 9 7.1.2 7.1.2 最小费用流模型的特例及扩展最小费

10、用流模型的特例及扩展 最 小 费 用 流 问 题 指 派 问 题 运 输 问 题 最大流 问题 最短路 问题 带 增 益 的 最小费用流 问题 线性 规划 问题 凹费用网络 的最小费用 流问题 凸费用网络 的最小费用 流问题 狭义模型 广义模型 凸 规 划 10 单源单汇网络单源单汇网络 可行流可行流x的的流量流量（或（或流值流值）为）为v=v（x）= ds = - dt 如果我们并不给定如果我们并不给定ds 和和dt , 则网络一般记为则网络一般记为N=(s, t,V,A,C,U) 容量可行且转运点流量守恒的流称为容量可行且转运点流量守恒的流称为s-t可行流可行流，有时为了方，有时为了方 便

11、也称为可行流便也称为可行流. 最小费用流问题就是在网络最小费用流问题就是在网络N=(s,t,V,A,C,U)中计算流值为中计算流值为v的的 最小费用流最小费用流x 或者当不给定流值时或者当不给定流值时, 计算流值最大的最小费用流计算流值最大的最小费用流x (此时流此时流x 称为称为最小费用最大流最小费用最大流). 7.2 消圈算法与最小费用路算法消圈算法与最小费用路算法 最小费用最小流最小费用最小流? ? 11 7.2 消圈算法与最小费用路算法消圈算法与最小费用路算法 定义定义7.3 对网络对网络N=(s,t,V,A,C,U)中给定的中给定的s-t可行流可行流x，网络，网络N关于流关于流 x的

12、的残量网络残量网络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 = - cji A（x）=A ( (允许容量为允许容量为0的弧仍然保留在网络中就可以了的弧仍然保留在网络中就可以了) 0,),( | ),(,),( | ),()( jiijij xAijjiuxAjijixA , 0,),(, ,),(, )( ji

13、ji ijijijij ij xAijx uxAjixu xu 其中称其中称, uij(x)为弧为弧(i,j)上的上的残留容量残留容量(residual capacity). , 0,),(, ,),(, )( jiji ijijij ij xAijc uxAjic xc 12 定义W的费用为 对于N(x)中的任何一个有向圈W, 它一定对应于原网络N中的一 个增广圈(增广弧构成的圈)； 通过沿W对当前流x进行增广，可以获得流值相等的s-t可行流y. 消圈算法的思想消圈算法的思想 则当增广的流量为则当增广的流量为 时时 只要N中存在费用为负数的增广圈W， 即C（W）0，则可以通过沿W 对当 前流

14、 x 进行增广，获得流值相等但 费用更小的s-t可行流y. Wji ij xcWC ),( )()( )()()(WCxcyc 13 设设x0为不同于的可行流，但费用低于为不同于的可行流，但费用低于x的费用，即的费用，即 7.2.1 7.2.1 消圈算法消圈算法(cycle-canceling algorithm) (cycle-canceling algorithm) 定理定理7.1 7.1 可行流可行流x为最小费用流的充要条件是为最小费用流的充要条件是N( (x) )中不存在负费中不存在负费 用增广圈用增广圈. . vxvxv)()( 0 )()( 0 xcxc 令令 x1 =x0-x,

15、则则 ，即令，即令x1为网络为网络N中的循环流中的循环流. 0)()()(, 0 011 xvxvxvx 一个循环流一定可以表示为至多一个循环流一定可以表示为至多m个非零圈流之和，所以可以将个非零圈流之和，所以可以将x1表示为表示为r个个 非零圈流之和（非零圈流之和（ ）。设对应的有向圈为）。设对应的有向圈为Wk， mr 1 r k kkij WjiWvx 1 1 ),( | )( r k k r k kk Aji ijij Aji ij WCWjiWvcxcxc 11),( 1 ),( 1 )(),( | )()( r k k WCxcxcxcxc 1 10 )()()()()( 至少存在一

16、个费用为至少存在一个费用为 负的增广圈负的增广圈. 矛盾矛盾 必要性是显然的必要性是显然的. . 反证法证明充分性：反证法证明充分性： 14 N(x)中找负圈可用最短路算法中找负圈可用最短路算法(如如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)中计算流值为中计算

17、流值为v的可行流的可行流 x. 7.2.1 7.2.1 消圈算法消圈算法: Klein (1967): Klein (1967)等等 STEP 1. 在残量网络在残量网络N(x)中判别负圈中判别负圈. 若无负圈若无负圈, 则已经找到了最则已经找到了最 小费用流，结束；否则转小费用流，结束；否则转STEP 2. 如按一些特定次序消圈如按一些特定次序消圈, 可得到一些多项式时间算法可得到一些多项式时间算法 复杂度？复杂度？ v任何可行流的费用不可能超过任何可行流的费用不可能超过mCU v设数据是整数设数据是整数, 每次消去一个负圈至少使费用下降一个单位每次消去一个负圈至少使费用下降一个单位 v设数

18、据是整数设数据是整数, 消去负圈的消去负圈的STEP12最多执行最多执行O(mCU )次次 15 略略 7.2.1 7.2.1 消圈算法消圈算法, ,例：例： 16 能否首先在网络能否首先在网络N=(s,t,V,A,C,U)中计算流值为中计算流值为v且费用最小的且费用最小的s-t 可行流可行流(v v)，然后对它沿增广路增广以增加流值呢，然后对它沿增广路增广以增加流值呢? 7.2.2 7.2.2 最小费用路算法最小费用路算法 为了获得最小费用流，我们希望沿费用最小的增广路对当前流为了获得最小费用流，我们希望沿费用最小的增广路对当前流x 进行增广，以最小的费用增加获得流值更大的进行增广，以最小的

19、费用增加获得流值更大的s-t可行流可行流y 对于对于N(x)中的一条从中的一条从s到到t的有向路的有向路P,它一定对应于原网络它一定对应于原网络N中的中的 一条增广路，即可以通过沿一条增广路，即可以通过沿P对当前流对当前流x进行增广，获得流值更进行增广，获得流值更 大的大的s-t可行流可行流y. 定义定义P的费用为的费用为 Pji ij xcPC ),( )()( 则当增广的流量为则当增广的流量为 时时 )()()(PCxcyc 17 7.2.2 7.2.2 最小费用路算法最小费用路算法 定理定理7.2 设设x为流值为为流值为v的最小费用流，的最小费用流，P为关于为关于x的从的从s到到t的一条

20、的一条 最小费用增广路，且沿最小费用增广路，且沿P所能增广的流量为所能增广的流量为 ，则增广后得到流，则增广后得到流 值为值为v+ 的最小费用流的最小费用流y y. 只需证明网络中不存在关于只需证明网络中不存在关于y y的负费用增广圈的负费用增广圈. . 用反证法用反证法 假设增广后存在关于假设增广后存在关于y的负费用增广圈的负费用增广圈W. 由于除由于除P以外的弧及其流量在增广以外的弧及其流量在增广 前后没有发生改变前后没有发生改变, 于是于是P和和W至少有一条公共弧至少有一条公共弧. 不妨假设不妨假设P和和W只有一条公只有一条公 共弧共弧,记为记为(i,j) 如果如果 (i,j) 在在P中

21、是正向弧中是正向弧, 则在则在W中是反向弧中是反向弧; 反之反之, 如果如果 (i,j) 在在P中是反向弧中是反向弧, 则在则在W中是正向弧中是正向弧 )()()(),(PCWCPCjiWPC 也是网也是网 络中关于络中关于x x的增广路的增广路, , 且且 ),(jiWP t t P P W W s s i ij j 18 7.2.2 7.2.2 最小费用路算法最小费用路算法 也称为连续最短路算法也称为连续最短路算法, 即即Successive Shortest Path Algorithm), Jewell(1958), Iri(1960), Busacker 由于流不一定满足容量约束由于

22、流不一定满足容量约束, 需定义这时残量网络的构造方法需定义这时残量网络的构造方法: 把原网络中可能增加流量的弧把原网络中可能增加流量的弧(前向弧前向弧)、减少流量的弧、减少流量的弧(反向弧反向弧) 纳入残量网络纳入残量网络. 具体具体方法如下方法如下: 瑕疵算法的思想：瑕疵算法的思想： 在算法过程中使弧上的在算法过程中使弧上的Kilter数不断下降数不断下降,最后降为最后降为0. 当当 时时: 如果如果xijlij , 则则 (j,i) N(x), uji(x)=xij -lij, cji(x)= - cij. ijijij uxl 41 - -残量网络残量网络7.4瑕疵算法 可以直接定义弧可

23、以直接定义弧(i,j) N(x)的的KilterKilter数，分三种情况讨论数，分三种情况讨论: : 可知可知: :原网络中的任何一条瑕疵弧一定会在残量网络中得到反映原网络中的任何一条瑕疵弧一定会在残量网络中得到反映 ( (即瑕疵弧不以前向弧的形式出现即瑕疵弧不以前向弧的形式出现, , 就以反向弧的形式出现就以反向弧的形式出现). ). 当当 时时: 如果如果(i,j)是瑕疵弧是瑕疵弧( 0), 则其则其Kilter数必然等于数必然等于 (i,j)的残留的残留 容量容量: kij =uij(x) ijijij uxl ij c 当当xijlij时时: 如果如果 0, 则则kij = uij(

24、x)=lij-xij;如果如果 uji 时时:如果如果 0(即即 0), ,则则kij=xji-lji; 如果如果 0(即即 0), ,则则 kij=uij(x)=xji -uji. ij c ji c ji c ij c ij c ij l ij u ij x 42 - - 步骤步骤7.4瑕疵算法 STEP 0 . STEP 0 . 给出初始势和初始循环流给出初始势和初始循环流( (如如 =0, =0, x=0). =0). Yakovleva(1959), Minty(1960), Fulkerson(1961)Yakovleva(1959), Minty(1960), Fulkerson

25、(1961)等提出等提出; ; AashtianiAashtiani和和Magnanti(1976)Magnanti(1976)给出一种高效率的实现方法给出一种高效率的实现方法. . STEP 1. 计算弧上的计算弧上的Kilter数数. 若网络中不存在瑕疵弧若网络中不存在瑕疵弧, 则已经得则已经得 到最优解到最优解, 计算结束；否则在残量网络计算结束；否则在残量网络N(x)中，选择一条瑕疵弧中，选择一条瑕疵弧 （p,q）, 继续下一步继续下一步. STEP 3. 若（若（p,q）仍为瑕疵弧）仍为瑕疵弧, 则沿则沿 P (p,q) 确定的增广圈增确定的增广圈增 广流量广流量(增广的流值为该增广

26、圈的容量增广的流值为该增广圈的容量), 转转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. ij c 主要过程主要过程: : 一是对节点上势的修改一是对节点上势的修改; ; 一是沿增广圈增广一是沿增广圈增广 43 - - 正确性正确性7.4瑕疵算法 证明证明 引理引理7.6 7.6 在

27、瑕疵算法中在瑕疵算法中, , 对节点上势的修改不会增加任何弧上对节点上势的修改不会增加任何弧上 的的KilterKilter数数. . 对残量网络N(x)的一条弧（i,j）(p,q), 由最短路方程得 d(j)d(i)+max0, ij c , 即d(i)-d(j)- max0, ij c . 记修 改后的势 i =i - d(i), 则 = - + = - ( i- d(i) +( j -d(j)= +(d(i)-d(j) - max0, ij cij c i j ij c ij c ij c ij c 当当 0: - max0, =0 (6.26) ij c ij c ij c ij c

28、当当 0, ) 0, 所以所以 = - + = - ( i- d(i) +( j -d(j)= +(d(i)-d(j) (6.28) ij cij c i j ij c ij c ij c 44 - -正确性正确性7.4瑕疵算法 从从KilterKilter数的定义知数的定义知: : 当弧上流量保持不变时当弧上流量保持不变时, , 只有的符号改只有的符号改 变时变时, , 弧上的弧上的KilterKilter数才可能改变数才可能改变. . 下面分别对几种情况讨论下面分别对几种情况讨论: : 节点上势的修改不会增加任何弧上的节点上势的修改不会增加任何弧上的KilterKilter数数. . 沿增

29、广圈增广呢沿增广圈增广呢? ? 当当 时时:如果如果(i,j) 关于关于 是无瑕弧是无瑕弧, ,则关于则关于 也是无瑕也是无瑕 弧弧; ;如果如果(i,j)关于关于 是瑕疵弧是瑕疵弧( uji 时时:此时在节点上势的修改前后此时在节点上势的修改前后 (i,j)一定都是瑕疵弧一定都是瑕疵弧. 与与xijlij类似可证类似可证 当当xijlij时时: 此时在节点上势的修改前后（此时在节点上势的修改前后（i,j）一定都是瑕疵弧）一定都是瑕疵弧. 如果如果 0, 则则 0, kij = kij = uij(x)=lij-xij不变不变. 如果如果 0, 则则: : 若若 0,0,则则kij = kij

30、 = uij-xij不变不变; 若若 0, 0,则则kij = lij-xij uij-xij ij c ij c ij c ij c ij c 45 - -正确性正确性7.4瑕疵算法 引理引理7.7 7.7 在瑕疵算法中在瑕疵算法中, , 沿增广圈沿增广圈P P (p,qp,q)增广流量不会增增广流量不会增 加任何弧上的加任何弧上的KilterKilter数数, , 且弧且弧( (p,qp,q) )的的KilterKilter数严格减少数严格减少 沿增广圈沿增广圈P (p,q) 增广流量只可能改变圈上的弧及其反向弧的增广流量只可能改变圈上的弧及其反向弧的Kilter数数. 对于增广圈上容量不

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

32、短路方程有 d(j)= d(i)+max0, d(i)+ ij c ij c 若弧若弧(i,j)在原网络中对应的弧为在原网络中对应的弧为(i,j), 则流的增广不会增加其则流的增广不会增加其Kilter数，数， 且且 当当 0时实际上会严格减少其时实际上会严格减少其Kilter数数. ij c 若弧若弧(i,j)在原网络中对应的弧为在原网络中对应的弧为(j,i), 则由则由 = - 0可知可知, 流的增广也不会流的增广也不会 增加其增加其Kilter数，且当数，且当 0时实际上会严格减少其时实际上会严格减少其Kilter数数. ij c ij c ji c 46 - -正确性正确性7.4瑕疵算

33、法 最后看看弧最后看看弧(p,q), 也只需要分析它为容量可行的弧的情况也只需要分析它为容量可行的弧的情况. 证毕证毕 注意到沿容量可行弧注意到沿容量可行弧 (i,j)的增广可能会在残量网络中加入新的弧的增广可能会在残量网络中加入新的弧 (j,i). 但由于但由于 = - 0, 所以在残量网络中新加入的弧所以在残量网络中新加入的弧(j,i)是满是满 足足Kilter条件的条件的. ij c ji c 由算法由算法STEP3, 只有它为瑕疵弧时才进行增广只有它为瑕疵弧时才进行增广, 即即 0, 因此增广也不会使因此增广也不会使(q,p)成为残量网络成为残量网络 中的瑕疵弧中的瑕疵弧. qp c

34、pq c 47 - - 复杂度分析复杂度分析 7.4瑕疵算法 每次循环迭代修改圈上的流值和节点上的势各一次每次循环迭代修改圈上的流值和节点上的势各一次, , 并使所有并使所有 弧上的总弧上的总KilterKilter数至少下降数至少下降1 1个单位个单位. . 设初始流和势对应的总设初始流和势对应的总Kilter数为数为K,则总迭代次数不会超过则总迭代次数不会超过K. 记求解非负弧长网络的最短路算法的复杂度为记求解非负弧长网络的最短路算法的复杂度为S(n，m，C), 则本则本 算法复杂度为算法复杂度为O(K S(n，m，nC). 特别地特别地, 当取初始流当取初始流x=0时时, 由于每条弧上的

35、由于每条弧上的Kilter数不超过数不超过U, 算算 法复杂度可以写成为法复杂度可以写成为O(mU S(n，m，nC). 由此可以看出由此可以看出, 瑕疵算法仍然不是多项式时间算法瑕疵算法仍然不是多项式时间算法. 48 - - 算法思想算法思想 对对(7.1)引入引入Lagrange乘子乘子 (仍然称为仍然称为i节点上的势节点上的势, 由于约束由于约束(7.1) 为等式为等式,所以没有符号限制所以没有符号限制), 则得到如下的则得到如下的Lagrange松弛问题松弛问题: 7.5 7.5 松弛算法（松弛算法（Relaxation AlgorithmRelaxation Algorithm） .

36、 .)(min ),( tsxcxc Aji ijij ) 1 . 7(, ),( :),( : Vidxx i Aijj ji Ajij ij )2 . 7(),(,0Ajiux ijij )29. 7(),(min)( ),( :),( :),( ViAijj ji Ajij ijii Aji ijij x xxdxcxcLR )30. 7(),(,0. .Ajiuxts ijij Vi ii Aji ijjiij dxc ),( )( ) 29. 7( ),( Vi ii Aji ijij dxc 如果如果 0, 0, 则令则令xij=0 (=0 (下界下界); ); 如果如果 0, 0

37、时时, 称称e(i)为节点为节点i的的盈余盈余(Excess); e(i) r( ,S): 同时修改同时修改 和和x, 使得使得LR( )严格增加严格增加. 7.5 7.5 松弛算法松弛算法 由（由（7.29）：）：LR( ) 增加增加 e(S) - r( ,S) 算法首先沿算法首先沿(S, )中满足中满足 =0的弧增广流量使之饱和的弧增广流量使之饱和, 即流量达即流量达 到残留容量的上界到残留容量的上界, 相应的弧不再属于残量网络相应的弧不再属于残量网络; 从从(7.29)可知可知, 这样的修改不会改变这样的修改不会改变 c(x, ) 的值的值, 但使得但使得S中的节中的节 点上的总盈余减少

38、点上的总盈余减少为为 e(S) - r( ,S) （仍然为正数）仍然为正数）. ij c S 由于算法保持互补松弛条件由于算法保持互补松弛条件, 对于对于N(x)中的任意弧一定有中的任意弧一定有 0. 增广后前向弧集增广后前向弧集(S, )中的弧满足中的弧满足 0, 记其中的最小值为记其中的最小值为 0. ij c ij cS ,: ),(),(;: ),(),( ijijijij ccSSjiccSSji N(x)中的任意弧仍有中的任意弧仍有 0：保持互补松弛条件保持互补松弛条件 ij c 即令对,: ii Si 52 - - 算法思想算法思想 (case2) 若若e(S) r( ,S):

39、不变，不变，修改修改x, 使得使得e(S)严格减少严格减少. 7.5 7.5 松弛算法松弛算法 如果如果e(j) 0, 则算法沿子树中从则算法沿子树中从 s 到到 j 的一条增广路增广流量的一条增广路增广流量. 从从(7.29)可知可知, 这样的修改不会改变这样的修改不会改变 c(x, ) 的值的值, 但使得但使得S中的节中的节 点上的总盈余减少点上的总盈余减少 由由0 r( ,S), 则转则转STEP 3; 否则在否则在(S, )中选取一条中选取一条 满足满足 =0的弧（的弧（i,j）. 若若e(j)0. 转转STEP 1. S S ij c ij c STEP 4. 根据根据pred中记录

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

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

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

43、考8 ； 10 ；18（不交）（不交） 57 网网 络络 优优 化化 Network Optimization http:/ 清华大学数学科学系 谢金星 办公室：理科楼2206# （电话：62787812） Email: http:/ 清华大学课号：清华大学课号：70420133（研）（研） 第第7 7章章 最小费用流问题最小费用流问题 (Minimum Cost Flow Problem) 第第3讲讲 58 线性规划问题的单纯形算法的一般思路是：线性规划问题的单纯形算法的一般思路是： 首先求得问题的一个基本可行解；首先求得问题的一个基本可行解； 如果它不是最优解，则选择一个进基变量如果它不是

44、最优解，则选择一个进基变量( (列列) )和一个出基变和一个出基变 量（列），通过旋转（量（列），通过旋转（PivotPivot）变换改进到另一个基本可行解；）变换改进到另一个基本可行解； 如此反复迭代，直到检验数（或称相对费用，如此反复迭代，直到检验数（或称相对费用， Reduced Reduced CostCost）都大于等于）都大于等于0 0为止，获得最优解为止，获得最优解. . 算法的计算过程通常利用单纯形表进行算法的计算过程通常利用单纯形表进行. . 对于网络优化问题对于网络优化问题, , 基的结构是非常特殊的基的结构是非常特殊的, , 因此可以避免显因此可以避免显 式地列出单纯形表

45、式地列出单纯形表. . 7.6 7.6 网络单纯形算法网络单纯形算法(Network Simplex Algorithm)(Network Simplex Algorithm) 7.6.1 7.6.1 算法的一般思路算法的一般思路 不失一般性不失一般性, , 以下总是假设流网络是连通的以下总是假设流网络是连通的 ( (否则该否则该 问题可以自然地分解为几个小问题来考虑问题可以自然地分解为几个小问题来考虑). ). 59 引理引理7.8 关联矩阵关联矩阵B的列构成一组基的充要条件是它所对应的弧的列构成一组基的充要条件是它所对应的弧 为支撑树为支撑树(不考虑方向时不考虑方向时). 流网络是连通的流

46、网络是连通的, 所以所以r(B)=n-1. 记记B的的(n-1)列构成的子矩阵为列构成的子矩阵为B1. 6.5 6.5 最高标号预流推进算法最高标号预流推进算法 - - 基的特殊性基的特殊性 首先考虑容量无限的最小费用流问题首先考虑容量无限的最小费用流问题 7.6.1 7.6.1 算法的一般思路算法的一般思路 Cxmin dBxts. . 0 x 必要性必要性. 若若B1为一组基为一组基, 则则r(r(B1) )=n-1. B1所对应的所对应的n-1条弧如果不条弧如果不 连通连通, 则至少含有一个圈则至少含有一个圈, 因此因此r(r(B1) )=0 ； (7.37) 当当 0 时，时， = 0

47、 ； (7.38) ij x ij x ij c ij c 设给定了一个基本可行解设给定了一个基本可行解x, 基矩阵所对应的可行树为基矩阵所对应的可行树为T T. 由于由于 只有树弧上的流量可以为正数只有树弧上的流量可以为正数, 所以只有树弧才可能满足所以只有树弧才可能满足(7.38). 支撑树上的弧共有支撑树上的弧共有(n-1)条条, 而对偶变量而对偶变量(节点上的势节点上的势)共有共有n个个. 在相差一个常数的意义下在相差一个常数的意义下, 由由T T中的弧满足中的弧满足 =0可可 以唯一地确定对偶变量以唯一地确定对偶变量. jiijij cc 可以任意选定一个节点（这一节点通常称为可以任

48、意选定一个节点（这一节点通常称为“根根”（Root）, 令它的势为令它的势为0; 然后利用然后利用(7.38)计算与它相邻的其它节点上的势计算与它相邻的其它节点上的势, 如此重复就可以方便地获得所有节点上的势如此重复就可以方便地获得所有节点上的势. 如果此时使得如果此时使得(7.37)也成立也成立, 则则x就是原问题的最优解就是原问题的最优解. 62 7.6.1 7.6.1 算法的一般思路算法的一般思路 旋转变换旋转变换 W为一个负费用圈为一个负费用圈, 所以沿所以沿W增广流量将会使得总费用下降增广流量将会使得总费用下降. 为了在为了在W中找出一条弧出基中找出一条弧出基, 我们应当令增广的流量

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

50、以进入基. pq c pq Wji jiij Wji jiij Wji ij Wji ij cccccWC ),(),(),(),( )()()( 63 STEP 0. 获得一个初始的可行树获得一个初始的可行树T及对应的基本可行解及对应的基本可行解x - - 步骤步骤 STEP 1. 计算对偶变量计算对偶变量 . 7.6.1 7.6.1 算法的一般思路算法的一般思路 STEP 2. 判断是否最优解判断是否最优解, 若是若是, 则停止则停止; 否则选定一个进基变量否则选定一个进基变量 (即选进基弧即选进基弧(p,q). STEP 3. 选定一个出基变量选定一个出基变量(即选出基弧即选出基弧),

51、如果找不到这样的弧如果找不到这样的弧, 则原问题是无界的则原问题是无界的, 停止停止;否则进行下一步否则进行下一步. STEP 4. 设设W为为T T (p,q)所含的圈所含的圈. 沿沿W的正向增广流量的正向增广流量, 即修改即修改 x 及对应的可行树及对应的可行树T, 回到回到STEP 1. 问题问题 获得一个初始的可行树获得一个初始的可行树T及对应的基本可行解及对应的基本可行解x ？ 退化与循环退化与循环 ？90%以上退化以上退化容量有界情形容量有界情形 ？ 复杂度复杂度？一般非为多项式算法，但可以设计多项式算法？一般非为多项式算法，但可以设计多项式算法 64 略略 7.6.1 7.6.1

52、 算法的一般思路算法的一般思路 例例 65 计算测试表明，网络单纯形法中往往计算测试表明，网络单纯形法中往往90%以上的旋转是退化的以上的旋转是退化的. 能否要求能否要求每次所操作的可行树每次所操作的可行树“都不相同都不相同” ？ 7.6.2 7.6.2 处理退化的方法处理退化的方法 定义定义7.6 假定计算节点上的势时所选定的根节点是固定的假定计算节点上的势时所选定的根节点是固定的. 对于对于 可行树可行树T中的一条树弧中的一条树弧 ( (i, ,j), ), 如果如果T中从根到中从根到j的路通过节点的路通过节点 i，则，则( (i, ,j) )称为远离根节点的弧（称为远离根节点的弧（Dow

53、nward Pointing Arc）. 如果如果T中的所有流量为中的所有流量为0的弧都是远离根节点的弧，则称可行的弧都是远离根节点的弧，则称可行 树树T为为强可行树（强可行树（Strongly Feasible Spanning TreeStrongly Feasible Spanning Tree） . 例例7.8 假设弧上的数字表示当假设弧上的数字表示当 前可行流前可行流. 节点节点1为根节点为根节点. T1=(1,3),(3,2),(3,4)为强可为强可 行树行树, T2=(1,3),(2,3),(3,4)不是强可不是强可 行树行树,因为因为T2中中(2,3) 不是远离不是远离 根节点

54、的弧根节点的弧. 1 1 2 2 3 3 4 4 0 0 0 00 0 0 0 2 2 2 2 66 引理引理7.9 7.9 如果网络单纯形算法中生成的所有可行树都是强可行如果网络单纯形算法中生成的所有可行树都是强可行 树，则这些树互不相同树，则这些树互不相同. . 7.6.2 7.6.2 处理退化的方法处理退化的方法 如果如果T T为生成树，为生成树，r r为根节点，记为根节点，记 证明证明 : 如果网络单纯形算法中的旋转变换不是退化的，则相应的可行如果网络单纯形算法中的旋转变换不是退化的，则相应的可行 树对应的可行流费用互不相同，因此这些树也一定互不相同树对应的可行流费用互不相同，因此这些

55、树也一定互不相同. 所以，我们只需要考虑旋转变换退化的情况所以，我们只需要考虑旋转变换退化的情况. Vi ir T)()( 考虑算法过程中连续生成的两棵强可行树考虑算法过程中连续生成的两棵强可行树T， =T (p,q)(k,l), 即即 (p,q)为进基弧为进基弧, (k,l)为出基弧为出基弧, 且从且从T到到 的旋转是退化的的旋转是退化的. T T 67 7.6.2 7.6.2 处理退化的方法处理退化的方法 记记 对应的势为对应的势为 , 根据势的确定方法根据势的确定方法, 可以得到可以得到(留作练习留作练习):T 当当i Tp 时时, = i ; i 当当i Tq 时时, = i + ;

56、i pq c 旋转变换前后旋转变换前后, (p,q)上的流量都是上的流量都是0, 由于由于 是强可行树是强可行树, 所以所以 (p,q) 弧一定是远离根节点弧一定是远离根节点r的弧的弧. (p,q)弧将弧将 分解为两棵子树分解为两棵子树 和和 , 并且并且p, q分别属于分别属于 和和 , 则则r . T T p T q T p T q T p T 因此, T和 是两棵不同的强可行树. T 所以 = + | | （ 0, 则加入人工弧则加入人工弧(i,0); 否则加入人工弧否则加入人工弧(0,i) . 7.6.3 初始的基本可行解初始的基本可行解 记所有人工弧的集合为记所有人工弧的集合为 , , 所有人工弧上的费用假定为一个所有人工弧上的费用假定为一个 充分大的正数充分大的正数M M, , 并称原网络假入人工弧后的新网络为人工网络并称原网络假入人工弧后的新网络为人工网络. . )0( T 0)0( T 是人工网络的一棵是人工网络的一棵( (初始）强可行树初始）强可行树 )0( T 71 由于由于M是一个充分大的正数是一个充分大的正数, 因此当算法终止时因此当算法终止时, 有三种情况有三种情况: (1) (1) 人工网络上的最小费用流问题有有界的最优解人工网络上的最小费用流问题有有界的最优解, , 且最优解中所有且最优解中所有 人工弧上的流量为人工弧上的