网络优化7最小费用流问题ppt课件

1、网网 络络 优优 化化 Network O/netopt清华大学数学科学系 谢金星办公室：文科楼2206# ：62787812: /jxie清华大学课号：清华大学课号：70420193研研第第7 7章章 最小费用流问题最小费用流问题 (Minimum Cost Flow Problem) (Minimum Cost Flow Problem) 第第1 1讲讲 许多实践问题都可以转化为最小费用流问题 S ST T最小费用流问题的例子公路交通网络：车辆道路确定最短路问

2、题 最小费用流问题 1辆车 多辆车:车流 定义定义7.1 7.1 在流网络在流网络N=(V,AN=(V,A，L,U,D) L,U,D) 上添加如下的权函数：上添加如下的权函数： C C： A A R R为弧上的权函数，弧为弧上的权函数，弧i i，j j对应的权对应的权 C Ci i，j j记为记为cij cij ，称为弧，称为弧i i，j j的单位流量的本钱或费用的单位流量的本钱或费用costcost; ; 此时网络可称为容量此时网络可称为容量- -费用网络费用网络 ( (普通仍可简称为网络普通仍可简称为网络),),记为记为 N=(V,A,CN=(V,A,C，L,U,D). L,U,D). 7

3、.1.1 7.1.1 最小费用流问题最小费用流问题 di 0:供应点供应点(supply node)或源或源(source)、起始点或发货点、起始点或发货点 di 0:需求点需求点(demand node)或汇或汇(sink) 、终止点或吸收点、终止点或吸收点 di 0:转运点转运点(transshipment node)或平衡点、中间点或平衡点、中间点 可以把可以把L 0的网络转化为的网络转化为L=0的网络进展研讨的网络进展研讨(思思索？索？)除非特别阐明除非特别阐明, 假设假设L=0,网络简记为网络简记为N=(V,A,C，U,D). 定义定义7.2 容量容量-费用网络中的流费用网络中的流(

4、flow) 的定义同前一章的定义同前一章流流x的总费用定义为的总费用定义为 通常又称为转运问题(transshipment problem)或容量受限的转运问题(capacitated transshipment problem). 最小费用流问题就是在网络中寻觅总费用最小的可行流. 最小费用流问题最小费用流问题Ajiijijxcxc),()(. .)(min),(tsxcxcAjiijij) 1 . 7(,),( :),( :VidxxiAijjjiAjijij)2 . 7(),(,0Ajiuxijij引理引理7.1 7.1 最小费用流问题存在可行流的必要条件最小费用流问题存在可行流的必要条

5、件 . 0Viid经典的最小费用流问题：单源单汇(起点s，终点t)，寻觅从s流到t的给定流量(或最大流量、最小流量等)的最小费用流. vdvdts ,),(0tsidi线性费用网络线性费用网络思索：思索： 经典问题与普通问题有什么关系？能否等价？经典问题与普通问题有什么关系？能否等价？例 7.1 最短路问题在有向网络中，令一切弧上容量下界为0，容量上界为1，并令图中节点s的供需量为1，节点t的供需量为-1，那么： 从s到t的一条有向路正好对应于网络中的一个可行流x 弧(i，j)位于s-t路上：xij =1；弧(i，j)不在s-t路上：xij=0. 假设再令一切弧上的(单位流量)的费用为“弧长,

6、 那么此时的最小费用流问题就是第五章讨论过的最短路问题. 在第五章我们正是用这样的方式对最短路问题进展建模的 7.1.2 7.1.2 最小费用流模型的特例及扩展最小费用流模型的特例及扩展 P Ps st t例 - 最大流问题 设s为起点,t为终点,添加弧(t,s),令7.1.2 7.1.2 最小费用流模型的特例及扩展最小费用流模型的特例及扩展s st ttstsuc, 1而令一切其他弧上的费用为0,一切顶点上的供需量(外部流量)全为0. 例 -运输问题(transportation Problem)又称Hitchcock问题Hitchcock,1941年完全二部图只需源和汇没有中间转运点 ST

7、7.1.2 7.1.2 最小费用流模型的特例及扩展最小费用流模型的特例及扩展)8 . 7(.),(, 0)7 . 7(,)6 . 7(,. .)5 . 7(min),( :),( :),(AjixTjbxSiaxtsxcijjAjiiijiAjijijAjiijij假设每条弧上还有容量(上下限)的限制, 那么称为容量受限的运输问题(capacitated transportation problem). 有解的必要条件TjjSiiba可以不失普通性TjjSiiba指派问题(assignment problem) | , 1TSbaji7.1.2 7.1.2 最小费用流模型的特例及扩展最小费用流

8、模型的特例及扩展1当一定的流量流过一条弧时，该弧上导致的总费用与流量大小成线性正比关系，这样的流网络普通称为线性费用网络.假设当一定的流量流过一条弧时，该弧上导致的总费用不一定与流量大小成线性正比关系，而是流量大小的一个凹或凸函数，那么这样的网络称为凹或凸费用网络，相应的最小费用流问题称为凹凸费用网络上的最小费用流问题. 2当流量流过一条弧时，流出该弧的流量即流入该弧终点的流量与进入该弧的流量即流出该弧起点的流量相等. 假设当流量流过一条弧时，流出该弧的流量是进入该弧的流量的一个线性函数，即流出该弧的流量是对进入该弧的流量按一定比例进展放大或减少的结果，那么这样的流网络普通称为带增益(或盈亏)

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

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

11、V,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 i，j jA A时，弧时，弧j j，i i A A；c ij = - cjic ij = - cjiA Ax x=A (=A (允许容量为允许容量为0 0的弧依然保管在网络中就可以了的弧依然保管在网络中就可以了) ) 0,),( |

12、 ),(,),( | ),()(jiijijxAijjiuxAjijixA, 0,),(,),(,)(jijiijijijijijxAijxuxAjixuxu其中称其中称, uij(x), uij(x)为弧为弧(i,j)(i,j)上的残留容量上的残留容量(residual capacity). (residual capacity). , 0,),(,),(,)(jijiijijijijxAijcuxAjicxc定义W的费用为 对于N(x)中的任何一个有向圈W, 它一定对应于原网络N中的一个增广圈(增广弧构成的圈)；经过沿W对当前流x进展增广，可以获得流值相等的s-t可行流y. 消圈算法的思想

13、消圈算法的思想那么当增广的流量为那么当增广的流量为时时 只需N中存在费用为负数的增广圈W，即CW0，那么可以经过沿W 对当前流 x 进展增广，获得流值相等但费用更小的s-t可行流y. WjiijxcWC),()()()()()(WCxcyc 设设x0为不同于的可行流，但费用低于为不同于的可行流，但费用低于x的费用，即的费用，即 7.2.1 7.2.1 消圈算法消圈算法(cycle-canceling algorithm) (cycle-canceling algorithm) 定理定理7.1 7.1 可行流可行流x x为最小费用流的充要条件是为最小费用流的充要条件是N(x)N(x)中不存在负费

14、中不存在负费用增广圈用增广圈. . vxvxv)()(0)()(0 xcxc令令 x1 =x0-x, 那么那么 ，即令，即令x1为网络为网络N中的循环中的循环流流. 0)()()(, 0011xvxvxvx一个循环流一定可以表示为至多一个循环流一定可以表示为至多m m个非零圈流之和，所以可以将个非零圈流之和，所以可以将x1x1表示为表示为r r个个非零圈流之和非零圈流之和 。设对应的有向圈为。设对应的有向圈为WkWk， mr 1rkkkijWjiWvx11),( | )(rkkrkkkAjiijijAjiijWCWjiWvcxcxc11),(1),(1)(),( | )()(rkkWCxcxc

15、xcxc110)()()()()(至少存在一个费用为至少存在一个费用为负的增广圈负的增广圈. . 矛盾矛盾 必要性是显然的必要性是显然的. . 反证法证明充分性：反证法证明充分性： N(x)中找负圈可用最短路算法中找负圈可用最短路算法(如如Bellman-Ford算法，算法，O(m n ) )那么该算法的复杂度为那么该算法的复杂度为O(n m 2CU), 不是多项式时间算法不是多项式时间算法. STEP 2. 沿找到的负圈增广流量沿找到的负圈增广流量, 转转STEP 1. Step0Step0可借用最大流算法可借用最大流算法 ，复杂度为，复杂度为O(n2m) O(n2m) STEP 0 . 在

16、网络在网络N=(s,t,V,A,C,U)中计算流值为中计算流值为v的可行流的可行流 x. 7.2.1 7.2.1 消圈算法消圈算法: Klein (1967): Klein (1967)等等 STEP 1. 在残量网络在残量网络N(x)中判别负圈中判别负圈. 假设无负圈假设无负圈, 那么曾经找到那么曾经找到了最小费用流，终了；否那么转了最小费用流，终了；否那么转STEP 2. 如按一些特定次序消圈如按一些特定次序消圈, , 可得到一些多项式时间算法可得到一些多项式时间算法 复杂度？复杂度？v任何可行流的费用不能够超越任何可行流的费用不能够超越mCUmCUv设数据是整数设数据是整数, , 每次消

17、去一个负圈至少使费用下降一个单位每次消去一个负圈至少使费用下降一个单位v设数据是整数设数据是整数, , 消去负圈的消去负圈的STEP12STEP12最多执行最多执行O(mCU )O(mCU )次次略略 7.2.1 7.2.1 消圈算法消圈算法, ,例：例：能否首先在网络能否首先在网络N=(s,t,V,A,C,U)N=(s,t,V,A,C,U)中计算流值为中计算流值为v v且费用最小的且费用最小的s-ts-t可行流可行流(v(v v) v)，然后对它沿增广路增广以添加流值呢，然后对它沿增广路增广以添加流值呢? ? 7.2.2 7.2.2 最小费用路算法最小费用路算法 为了获得最小费用流，我们希望

18、沿费用最小的增广路对当前流为了获得最小费用流，我们希望沿费用最小的增广路对当前流x x进展增广，以最小的费用添加获得流值更大的进展增广，以最小的费用添加获得流值更大的s-ts-t可行流可行流y y 对于对于N(x)N(x)中的一条从中的一条从s s到到t t的有向路的有向路P,P,它一定对应于原网络它一定对应于原网络N N中的中的一条增广路，即可以经过沿一条增广路，即可以经过沿P P对当前流对当前流x x进展增广，获得流值更进展增广，获得流值更大的大的s-ts-t可行流可行流y. y. 定义定义P P的费用为的费用为 PjiijxcPC),()()(那么当增广的流量为那么当增广的流量为时时 )

19、()()(PCxcyc7.2.2 7.2.2 最小费用路算法最小费用路算法定理定理7.2 7.2 设设x x为流值为为流值为v v的最小费用流，的最小费用流，P P为关于为关于x x的从的从s s到到t t的一的一条最小费用增广路，且沿条最小费用增广路，且沿P P所能增广的流量为所能增广的流量为 ，那么增广后，那么增广后得到流值为得到流值为v+ v+ 的最小费用流的最小费用流y. y. 只需证明网络中不存在关于只需证明网络中不存在关于y y的负费用增广圈的负费用增广圈. . 用反证法用反证法 假设增广后存在关于假设增广后存在关于y的负费用增广圈的负费用增广圈W. 由于除由于除P以外的弧及其流量

20、在增广以外的弧及其流量在增广前后没有发生改动前后没有发生改动, 于是于是P和和W至少有一条公共弧至少有一条公共弧. 无妨假设无妨假设P和和W只需一条公只需一条公共弧共弧,记为记为(i,j) 假设假设 (i,j) 在在P中是正向弧中是正向弧, 那么在那么在W中是反向弧中是反向弧; 反之反之, 假设假设 (i,j) 在在P中是反向弧中是反向弧, 那么在那么在W中是正向弧中是正向弧 )()()(),(PCWCPCjiWPC 也是网也是网络中关于络中关于x x的增广路的增广路, , 且且 ),(jiWP t tP PW Ws si ij j7.2.2 7.2.2 最小费用路算法最小费用路算法也称为延续

21、最短路算法也称为延续最短路算法, 即即Successive Shortest Path Algorithm), Jewell(1958), Iri(1960), Busacker & Gowen (1961) 独立提出的独立提出的STEP 0 . 取取x为任一为任一s-t可行流、且在同一流值的流中费用最小的可行流、且在同一流值的流中费用最小的流流 (如如x=0). STEP 1. 假设假设x的流值到达的流值到达v, 终了；否那么在残量网络终了；否那么在残量网络N(x)中判中判别最小费用路别最小费用路. 假设无这样的路假设无这样的路,那么流值不可到达那么流值不可到达v, 终了；否那终了；

22、否那么么STEP 2. STEP 2. 沿该最小费用增广路增广流量沿该最小费用增广路增广流量(增广后的流值不超越增广后的流值不超越v), 转转STEP 1. STEP1可用最短路算法：记最短路算法的复杂度为可用最短路算法：记最短路算法的复杂度为S(n，m，C)STEP12最多执行最多执行O(v )次次 复杂度？复杂度？最大流流值不超越最大流流值不超越nUnU，本算法复杂度为，本算法复杂度为 O(nU O(nUS(nS(n，m m，C)C)采用特定的变尺度技术采用特定的变尺度技术, , 可以得到一些多项式时间算法可以得到一些多项式时间算法 略略 7.2.2 7.2.2 最小费用路算法最小费用路算

23、法, ,例：例： 7.3.1 7.3.1对偶问题及互补松弛条件对偶问题及互补松弛条件 依然思索传统的单源单汇网络的最小费用流问题依然思索传统的单源单汇网络的最小费用流问题 两类约束分别引入对偶变量两类约束分别引入对偶变量和和z, z, 那么这一问题的对偶问题为那么这一问题的对偶问题为 7.3 7.3 原始原始- -对偶算法对偶算法 )12. 7(.),(,0)11. 7, 0,. .)10. 7(min),( :),( :),(AjiuxtsiVitivsivdxxtsxcijijiAijjjiAjijijAjiijij) 12. 7(.),(,Ajiuxijij)16. 7(.),(, 0)

24、15. 7(,),(,. .)14. 7(),(max),(AjizAjicztszudzwijijijjiAjiijijViii互补松弛条件互补松弛条件 设设x和和(,z)分别为原问题和对偶问题的可行解：分别为原问题和对偶问题的可行解： )18. 7(.),(, 0)()17. 7(,),(, 0)(AjiuxzAjiczxijijijijijjiij下面我们阐明在一定的下面我们阐明在一定的“商定下商定下, 这一条件可以等价地写成这一条件可以等价地写成当当 时时 ， =0；(7.19)当当 时，时， = ；(7.20) 当当 时，时， . (7.21) ijjicijjicijijux 0i

25、jjicijxijxiju商定商定: :存在对偶可行的存在对偶可行的变量变量z z，使得上式成立，使得上式成立. . Ajiczijjiij),(,0 ,max定理定理7.3 设设x为原问题的可行解为原问题的可行解, 那么那么x为最小费用流的充要条件为最小费用流的充要条件是是: 存在节点的势存在节点的势, 满足条件满足条件(7.19)(7.21). .1对偶问题及互补松弛条件对偶问题及互补松弛条件记记“相对费用相对费用Reduced Reduced CostCostjiijijcc0ijc0ijc0ijc.1对偶问题及互补松弛条件对偶问题及互补松弛条件 引理引理

26、7.2 最优性条件最优性条件(7.19)(7.21)等价于，对于等价于，对于N(x)中恣意中恣意的的(i,j)弧弧, 0 ijc 假设假设(7.19)(7.21)(7.19)(7.21)成立成立, , 那么对于原网络中的一条弧那么对于原网络中的一条弧(i,j), (i,j), 当当 00, 所以所以 = =-( )= - 0, 因此因此(j,i)弧不属于残量网络弧不属于残量网络N(x). 所以所以 =0. ijcijjicjicijjicjiijcijcijx当当 时，即时，即 0, (i,j)弧不属于残量网络弧不属于残量网络N(x), =ijcijjicijxiju当当 时，时， (i,j)

27、,(j,i)弧均属于残量网络弧均属于残量网络N(x). 所所以以 , 所以所以0jic0ijcijjicijijux 0思绪：思绪： 从流值不一定到达从流值不一定到达v v的的s-ts-t可行流开场，迭代中一直坚持可行流开场，迭代中一直坚持最优性条件最优性条件(7.19)(7.21)(7.19)(7.21)成立，直到流值到达成立，直到流值到达v v为止为止. . 迭代包括两个方面：对弧上流的增广；对节点上势的修正迭代包括两个方面：对弧上流的增广；对节点上势的修正当当N0(x)中找不到增广路且流值小于中找不到增广路且流值小于v时，必需进展时，必需进展下一个过程，修正节点上的势下一个过程，修正节点

28、上的势. 原始原始-对偶算法就是在允许网络对偶算法就是在允许网络N0(x)中寻觅增广路并进中寻觅增广路并进展增广最大流展增广最大流 为保证流的增广过程中一直坚持最优性条件为保证流的增广过程中一直坚持最优性条件(7.19)(7.21)(7.19)(7.21)，原，原始始- -对偶算法只沿满足对偶算法只沿满足 的弧增广流量的弧增广流量. . ijjicN(x)中满足中满足 的弧组成的子网络称为允许网络的弧组成的子网络称为允许网络Admissible Network，记为，记为N0(x) = ijjicijijijjiuxcAji,|),(0,),( | ),(ijijjixcAjiij7.3.2原

29、始-对偶算法 根本思想N0(x)中的弧就是中的弧就是N(x)中满足中满足 =0的弧的弧 ijc.2原始原始- -对偶算法对偶算法 根本思想根本思想当当N0(x)中找不到增广路且流值小于中找不到增广路且流值小于v时，必需修正节点上的势时，必需修正节点上的势.坚持最优性条件坚持最优性条件(7.19)(7.21)，并且希望修正后并且希望修正后N0(x)中可以找到增广路中可以找到增广路 可以证明可以证明, 修正后最优性条件修正后最优性条件(7.19)(7.21)依然成立，且将会有依然成立，且将会有新的弧添加到新的弧添加到N0(x)中中. 希望把希望把N(x)中一些不满足中一些不满足 =

30、0的弧也纳入的弧也纳入N0(x)中中. ijc以以 为弧长在为弧长在N(x)中计算从节点中计算从节点s到一切节点到一切节点i的最短路路长的最短路路长d(i). ijc)(idii.2原始原始- -对偶算法：对偶算法：FordFord和和Forkerson(1957,1962) Forkerson(1957,1962) STEP 0 . 取取x为任一为任一s-t可行流可行流(如如x=0)，令初始势，令初始势 = 0. STEP 1. 假设假设x的流值到达的流值到达v, 计算终了；否那么在残量网络计算终了；否那么在残量网络N(x)中，以相对费用为弧长，计算从节点中，以相对费用为弧长

31、，计算从节点s到一切节点到一切节点i的最短路路长的最短路路长d(i)，并令，并令i=i-d(i), 继续继续STEP 2. STEP 2. 在允许网络在允许网络N0(x)中判别从中判别从s到到t的最大流的最大流 (如可用第如可用第6章章引见的算法引见的算法). 假设该最大流流值为假设该最大流流值为0, 那么原网络中流的流值不那么原网络中流的流值不可到达可到达v, 计算终了；否那么沿该最大流确定的增广路增广流量计算终了；否那么沿该最大流确定的增广路增广流量(增广后的流值不超越增广后的流值不超越v), 转转STEP 1. .2原始原始- -对偶算法对偶算法 正确性正确性引理引理7.

32、3 在算法运转过程中，最优性条件在算法运转过程中，最优性条件(7.19)(7.21)成立成立. 证明证明 算法开场时，最优性条件算法开场时，最优性条件(7.19)(7.21)(7.19)(7.21)显然成立显然成立. . 只需证只需证明：明：如如i i满足满足(7.19)(7.21), (7.19)(7.21), 那么改为那么改为i=i=i - d(i)i - d(i)后后, , 仍满仍满足足 (7.19)(7.21). (7.19)(7.21). 即即由引理由引理7.27.2，对于，对于N(x)N(x)中恣意的中恣意的(i,j)(i,j)弧弧, , 一定有一定有 0 0，且只需，且只需证明证

33、明ijc0ijc根 据 最 短 路 方 程根 据 最 短 路 方 程 , d ( j ) - d ( i ) , d ( j ) - d ( i ) = , = , 即即 cij- (cij- (i-d(i)+ (i-d(i)+ (j-d(j) j-d(j) 0, 0, jiijcijc0ijc.2原始原始- -对偶算法对偶算法 正确性正确性上面几个引理和讨论阐明，前面引见的算法是正确的上面几个引理和讨论阐明，前面引见的算法是正确的. . 即即讨论讨论 这一引理阐明，只需这一引理阐明，只需N(x)中从中从s到到t存在有向路增广路，存在有向路增广路，那么那么修正为修正为后，将会有

34、新的弧添加到后，将会有新的弧添加到N0(x)中，中， N0(x) 中从中从s到到t存在有向路增广路，即可以对当前流进展增广存在有向路增广路，即可以对当前流进展增广 。0ijc证明证明 对于最短路上的弧对于最短路上的弧(i,j) 有有 d(j)-d(i) = = , 即即 cij - (i - d(i) + (j - d(j) = 0, jiijcijc引理引理7.4 7.4 对于对于N(x)N(x)中一条弧中一条弧(i,j)(i,j)， 假设它位于从起点假设它位于从起点 s s 到某到某一节点的最短路上以一节点的最短路上以 为为p p，q q弧的弧长，那么弧的弧长，那么 0ijcpqc7.3.

35、27.3.2原始原始- -对偶算法对偶算法 - - 讨论讨论原始原始- -对偶算法的特点对偶算法的特点 在运转中一直坚持对偶变量在运转中一直坚持对偶变量为对偶问为对偶问题的可行解题的可行解, , 并一直坚持互补松弛条件，并一直坚持互补松弛条件，但原始变量但原始变量x x在算法终止前通常不是原问题的可行解即只是伪在算法终止前通常不是原问题的可行解即只是伪流，而不是流值为流，而不是流值为v v的可行流的可行流. . 最小费用路算法是一种特殊的原始最小费用路算法是一种特殊的原始- -对偶算法对偶算法 虽然没有显示地虽然没有显示地引入对偶变量引入对偶变量，但我们也可以与本节引见的算法一样引入对，但我们

36、也可以与本节引见的算法一样引入对偶变量偶变量，可以以为也是坚持对偶可行和互补松弛条件的；，可以以为也是坚持对偶可行和互补松弛条件的；特殊性在于要求增广流量时每次沿特殊性在于要求增广流量时每次沿“一条最小费用路增广一条最小费用路增广. . 下面引理阐明：本节引见的原始下面引理阐明：本节引见的原始- -对偶算法实践上也是沿最小费对偶算法实践上也是沿最小费用路增广流值，只是能够每次沿用路增广流值，只是能够每次沿“多条最小费用路同时增广多条最小费用路同时增广即最小费用路最大流增广即最小费用路最大流增广. . .2原始原始- -对偶算法对偶算法 - - 讨论讨论引理引理7.5 7.5 对

37、于对于N(x)N(x)中从任一节点中从任一节点p p到另一节点到另一节点q q的一条有向路的一条有向路P P，讨论讨论 对于对于N(x)中从中从s到到t的一条有向路增广路的一条有向路增广路P，一定有，一定有 即即)()(),(),(qpccPjiijPjiij)()(),(),(tsccPjiijPjiij)()()(),(),(tsccPCPjiijPjiij直接运用直接运用 的定义就可以得到上述结果的定义就可以得到上述结果. . ijcijc对于给定的对偶变量对于给定的对偶变量，由于，由于N(x)N(x)中中 0 0，所以满足，所以满足 =0=0的弧即允许网络的弧即允许网络N0(x)N0(

38、x)中的弧组成的增广路是中的弧组成的增广路是N(x)N(x)中的最小费用路中的最小费用路. . ijcijcN(x)=N 例例7.4 7.4 用原始用原始- -对偶算法计算如图对偶算法计算如图7.5(a)7.5(a)网络中的最小费用流网络中的最小费用流( (图中弧上的前一个数字表示弧上的容量图中弧上的前一个数字表示弧上的容量, , 后一个数字表示弧上后一个数字表示弧上的单位费用的单位费用; ; 节点上的数字表示节点的供需量节点上的数字表示节点的供需量). ). .2原始原始- -对偶算法对偶算法 , ,例：例：1 12 23 34 42 22 2-2-2-2-21 1，1 11

39、 1，1 11 1，2 21 1，2 21 12 23 34 40 00 00 00 01 1，1 11 1，1 14 s4 s1 1，2 2t -4t -42 2，0 02 2，0 02 2，0 02 2，0 0 x=0, =0,计算得到计算得到 d=(0,0,0,1,2,1), 修正得到修正得到=(0, 0, 0, -1, -2, -1) uijuij，cijcij.2原始原始- -对偶算法对偶算法 , ,例例计算得到计算得到 d=(0,0,0,1,0,1) , 修正得到修正得到=(0, 0, 0, -2, -2, -2) N0(x)1 12 23 34 41 1，1 11

40、 1，1 11 1，2 22 2，0 02 2，0 02 2，0 02 2，0 01 1，2 2最大流流值为最大流流值为2, 2, 增广增广N(x) (1,0)(1,0)(1,0)(1,0)(1,-1)(1,-1)(2,0)(2,0)(1,-1)(1,-1)(2,0)(2,0)(1,2)(1,2)(1,0)(1,0)(1,0)(1,0)(1,2)(1,2).2原始原始- -对偶算法对偶算法 , ,例例x的流值到达的流值到达4得到最小费用流得到最小费用流最大流流值为最大流流值为2, 2, 增广增广N0(x)(1,0)(1,0)(1,0)(1,0)(2,0)(2,0)(2,0)(2

41、,0)(1,2)(1,2)(1,0)(1,0)(1,0)(1,0)(1,2)(1,2).2原始原始- -对偶算法对偶算法 复杂性分析复杂性分析算法每次循环迭代修正弧上的流值和节点上的势各一次算法每次循环迭代修正弧上的流值和节点上的势各一次. . 由于流值不能够超越由于流值不能够超越nU, nU, 且任何节点上的势不能够低于且任何节点上的势不能够低于-nC, -nC, 因此总迭代次数不会超越因此总迭代次数不会超越minnU,nC. minnU,nC. 记求解非负弧长网络的最短路算法的复杂度为记求解非负弧长网络的最短路算法的复杂度为S(nS(n，m m，C), C), 最最大流算法

42、的复杂度为大流算法的复杂度为M(nM(n，m m，U)U)本算法复杂度为本算法复杂度为O(minnU,nCS(nO(minnU,nCS(n，m m，nC)+ M(nnC)+ M(n，m m，U) )U) )这一算法依然不是多项式时间算法这一算法依然不是多项式时间算法与最小费用路算法相比与最小费用路算法相比, , 能够会以每次迭代调用一次最大流算能够会以每次迭代调用一次最大流算法为代价法为代价, , 希望减少一些迭代次数希望减少一些迭代次数. . 布 置 作 业目的掌握最小费用流问题的根本概念和建模方法；掌握消圈算法与最小费用路算法及其复杂度；掌握原始-对偶算法的根本思想。内容第第245-251

43、页页3；6；15；第；第1讲讲思索4； 5； 不交不交网网 络络 优优 化化 Network O/netopt清华大学数学科学系 谢金星办公室：文科楼2206# ：62787812: /jxie清华大学课号：清华大学课号：70420193研研第第7 7章章 最小费用流问题最小费用流问题 (Minimum Cost Flow Problem) (Minimum Cost Flow Problem) 第第2 2讲讲 (Out-Of-Kilter Algorithm)

44、(Out-Of-Kilter Algorithm)瑕疵算法瑕疵算法( (也翻译为也翻译为“形状算法形状算法) )在迭代过程中那么对这些条件在迭代过程中那么对这些条件更为放宽更为放宽: : 只需求满足节点上的流量守恒条件只需求满足节点上的流量守恒条件, , 而不要求而不要求x x为伪流为伪流( (即能够即能够不满足容量约束不满足容量约束), ), 并且也不一定坚持互补松弛条件并且也不一定坚持互补松弛条件. . 最小费用路算法和原始最小费用路算法和原始- -对偶算法的特点对偶算法的特点 : : 对偶变量对偶变量为对偶问题的可行解为对偶问题的可行解, , 并一直坚持互补松弛条件；并一直坚持互补松弛条

45、件； 但原始变量但原始变量x x在算法终止前通常不是原问题的可行解在算法终止前通常不是原问题的可行解 即只是即只是伪流，而不一定满足节点上的流量守恒条件伪流，而不一定满足节点上的流量守恒条件, , 即不是流值为即不是流值为v v的的可行流可行流. . 7.4瑕疵算法 (Out-Of-Kilter Algorithm) (Out-Of-Kilter Algorithm)想一想想一想, ,非循环流的情况能否都可以转化为循环流的情况非循环流的情况能否都可以转化为循环流的情况? ? 算法的思想：算法的思想：经过一定步骤经过一定步骤, 使非最优的使非最优的“程度不断降低，最后到达最优程度不断降低，最后到

46、达最优. 可以以为可以以为, 瑕疵算法是原始瑕疵算法是原始-对偶算法的一种变形对偶算法的一种变形. 瑕疵算法的调查对象：瑕疵算法的调查对象：循环流循环流(Circulation) (Circulation) ：流值为：流值为0 0的可行流没有所谓源点和的可行流没有所谓源点和汇点汇点, , 网络中的一切节点都是转运点网络中的一切节点都是转运点网络中容量下限网络中容量下限 L L 不一定为不一定为0 0；7.4瑕疵算法 - Kilter - Kilter条件条件7.4瑕疵算法 L 0L=0L=0最小费用循环流模型最小费用循环流模型 当当 0 时时 ， = 0； (7.19)当当 0 时时 ， =

47、； (7.23)当当 0 时时 ， = ； (7.23)当当 0 时，时， = ； (7.24)当当 时，时， = 0. (7.25) ijijijuxlijxijxijuijcijcijcijlijcijlijuijx., 0,0,0,0,0,其它时且当时且当时当时当ijijijijijijijijijijijijijijijijuxcuxlxcxlcuxclx - -残量网络残量网络7.4瑕疵算法 当当xijlijxijuij xijuij 时时, , 那么那么(j,i)(j,i)N(x), uji(x)=xij -uij, cji(x)= - cij.N(x), uji(x)=xij -

48、uij, cji(x)= - cij.瑕疵算法依然是在残量网络上对弧上的流量进展操作瑕疵算法依然是在残量网络上对弧上的流量进展操作; ;由于流不一定满足容量约束由于流不一定满足容量约束, , 需定义这时残量网络的构造方法需定义这时残量网络的构造方法: :把原网络中能够添加流量的弧把原网络中能够添加流量的弧( (前向弧前向弧) )、减少流量的弧、减少流量的弧( (反向弧反向弧) )纳入残量网络纳入残量网络. . 详细方法如下详细方法如下: : 瑕疵算法的思想：瑕疵算法的思想：在算法过程中使弧上的在算法过程中使弧上的KilterKilter数不断下降数不断下降, ,最后降为最后降为0. 0. 当当

49、 时时: : 假设假设xijuij, xijlij , xijlij , 那么那么(j,i)(j,i)N(x), uji(x)=xij -lij, N(x), uji(x)=xij -lij, cji(x)= - cij.cji(x)= - cij.ijijijuxl - -残量网络残量网络7.4瑕疵算法 可以直接定义弧可以直接定义弧(i,j)(i,j)N(x)N(x)的的KilterKilter数，分三种情况讨论数，分三种情况讨论: : 可知可知: :原网络中的任何一条瑕疵弧一定会在残量网络中得到反映原网络中的任何一条瑕疵弧一定会在残量网络中得到反映( (即瑕疵弧不以前向弧的方式出现即瑕疵弧

50、不以前向弧的方式出现, , 就以反向弧的方式出现就以反向弧的方式出现). ). 当当 时时: : 假设假设(i,j)(i,j)是瑕疵弧是瑕疵弧( 0), ( 0), 那么其那么其KilterKilter数必然等数必然等于于 (i,j)(i,j)的残留容量的残留容量: kij =uij(x): kij =uij(x)ijijijuxlijc当当xijlijxijlij时时: : 假设假设 0, 0, 那么那么kij = uij(x)=lij-xij;kij = uij(x)=lij-xij;假设假设 0, uji xjiuji 时时: :假设假设 0(0(即即 0),0),那么那么kij=xji

51、-lji; kij=xji-lji; 假设假设 0(0(即即 0),0),那么那么kij=uij(x)=xji -uji.kij=uij(x)=xji -uji.ijcjicjicijcijcijlijuijx - - 步骤步骤7.4瑕疵算法 STEP 0 . STEP 0 . 给出初始势和初始循环流给出初始势和初始循环流( (如如=0, x=0). =0, x=0). Yakovleva(1959), Minty(1960), Fulkerson(1961)Yakovleva(1959), Minty(1960), Fulkerson(1961)等提出等提出; ;AashtianiAasht

52、iani和和Magnanti(1976)Magnanti(1976)给出一种高效率的实现方法给出一种高效率的实现方法. . STEP 1. 计算弧上的计算弧上的Kilter数数. 假设网络中不存在瑕疵弧假设网络中不存在瑕疵弧, 那么曾那么曾经得到最优解经得到最优解, 计算终了；否那么在残量网络计算终了；否那么在残量网络N(x)中，选择一条中，选择一条瑕疵弧瑕疵弧p,q, 继续下一步继续下一步. STEP 3. 假设假设p,q仍为瑕疵弧仍为瑕疵弧, 那么沿那么沿 P (p,q) 确定的增确定的增广圈增广流量广圈增广流量(增广的流值为该增广圈的容量增广的流值为该增广圈的容量), 转转STEP 1;

53、 否那否那么直接转么直接转STEP 1. STEP 2. 在在N(x)(q,p)中中, 以以max0, 为为i,j弧的弧长，计弧的弧长，计算从节点算从节点q到一切节点到一切节点 i 的最短路路长的最短路路长d(i)，并记从节点，并记从节点q到节点到节点p的最短路为的最短路为P. 令令i = i - d(i), 继续继续STEP 3. ijc主要过程主要过程: : 一是对节点上势的修正一是对节点上势的修正; ; 一是沿增广圈增广一是沿增广圈增广 - - 正确性正确性7.4瑕疵算法 证明证明 引理引理7.6 7.6 在瑕疵算法中在瑕疵算法中, , 对节点上势的修正不会添加任何弧上对节点上势的修正不

54、会添加任何弧上的的KilterKilter数数. . 对残量网络N(x)的一条弧（i,j）(p,q), 由最短路方程得d(j)d(i)+max0,ijc, 即d(i)-d(j)- max0, ijc. 记修改后的势i=i- d(i), 则 = - + = - (i- d(i) +(j -d(j)= +(d(i)-d(j) - max0, ijcijcijijcijcijcijc当当 0 : - m a x 0 , = 0 (6.26)ijcijcijcijc当当 0, d(p) 0, 所以所以 = - + = - (i- d(i) +(j -d(j)= +(d(i)-d(j) (6.28)ij

55、cijcijijcijcijc - -正确性正确性7.4瑕疵算法 从从KilterKilter数的定义知数的定义知: : 当弧上流量坚持不变时当弧上流量坚持不变时, , 只需的符号改只需的符号改动时动时, , 弧上的弧上的KilterKilter数才能够改动数才能够改动. . 下面分别对几种情况讨论下面分别对几种情况讨论: : 节点上势的修正不会添加任何弧上的节点上势的修正不会添加任何弧上的KilterKilter数数. .沿增广圈增广呢沿增广圈增广呢? ?当当 时时: :假设假设(i,j) (i,j) 关于关于是无瑕弧是无瑕弧, ,那么关于那么关于也是也是无瑕弧无瑕弧; ;假设假设(i,j)

56、(i,j)关于关于是瑕疵弧是瑕疵弧( 0), ( uji xjiuji 时时: :此时在节点上势的修正前后此时在节点上势的修正前后 (i,j) (i,j)一定都是瑕一定都是瑕疵弧疵弧. . 与与xijlijxijlij类似可证类似可证当当xijlijxijlij时时: : 此时在节点上势的修正前后此时在节点上势的修正前后i,ji,j一定都是瑕疵一定都是瑕疵弧弧. . 假设假设 0, 0, 那么那么 0, k0, kij = kij = ij = kij = uij(x)=lij-xijuij(x)=lij-xij不变不变. . 假设假设 0, 0, 那么那么: : 假设假设 0, 0,那么那么

57、k kij = kij = uij-ij = kij = uij-xijxij不变不变; ; 假设假设 0, 0,那么那么k kij = ij = lij-xij lij-xij uij-xij uij-xijijcijcijcijcijc - -正确性正确性7.4瑕疵算法 引理引理7.7 7.7 在瑕疵算法中在瑕疵算法中, , 沿增广圈沿增广圈P P (p,q)(p,q)增广流量不会添增广流量不会添加任何弧上的加任何弧上的KilterKilter数数, , 且弧且弧(p,q)(p,q)的的KilterKilter数严厉减少数严厉减少 沿增广圈沿增广圈P P (p,q) (p,q) 增广流量只

58、能够改动圈上的弧及其反向弧的增广流量只能够改动圈上的弧及其反向弧的KilterKilter数数. . 对于增广圈上容量不可行的弧对于增广圈上容量不可行的弧(i,j), (i,j), 由残量网络的构造方法可知由残量网络的构造方法可知: :流量增广流量增广后该弧的后该弧的KilterKilter数一定严厉下降数一定严厉下降, , 且不会在残量网络中参与新的弧且不会在残量网络中参与新的弧(j,i).(j,i).对于增广圈上容量可行的弧对于增广圈上容量可行的弧, , 流量增广不改动容量可行弧的容量可行性流量增广不改动容量可行弧的容量可行性. . = - + = - (i- d(i) +(j -d(j)

59、= +(d(i)-d(j) 0 ijcijcijijcijc对于最短路对于最短路P上的容量可行弧上的容量可行弧 (i,j), 由最短路方程有由最短路方程有 d(j)= d(i)+max0, d(i)+ ijcijc假设弧假设弧(i,j)(i,j)在原网络中对应的弧为在原网络中对应的弧为(i,j), (i,j), 那么流的增广不会添加其那么流的增广不会添加其KilterKilter数，数， 且当且当 0 0时实践上会严厉减少其时实践上会严厉减少其KilterKilter数数. . ijc假设弧假设弧(i,j)(i,j)在原网络中对应的弧为在原网络中对应的弧为(j,i), (j,i), 那么由那么

60、由 = - = - 0 0可知可知, , 流的增广也不会添加其流的增广也不会添加其KilterKilter数，且当数，且当 0 0时实践上会严厉减少其时实践上会严厉减少其KilterKilter数数. . ijcijcjic - -正确性正确性7.4瑕疵算法 最后看看弧最后看看弧(p,q), (p,q), 也只需求分析它为容量可行的弧的情况也只需求分析它为容量可行的弧的情况. . 证毕证毕 留意到沿容量可行弧留意到沿容量可行弧 (i,j)的增广能够会在残量网络中参与新的弧的增广能够会在残量网络中参与新的弧(j,i). 但由于但由于 = - 0, 所以在残量网络中新参与的弧所以在残量网络中新参与的弧(j