网络优化

网络优化内容摘要：

(1,0) (1,0) (1,2) 33 对偶算法 – 复杂性分析 算法每次循环迭代修改弧上的流值和节点上的势各一次 . 由于流值不可能超过 nU, 且任何节点上的势不可能低于 nC, 因此总迭代次数不会超过 min{nU,nC}. 记求解 非负弧长网络 的最短路算法的复杂度为 S(n， m， C), 最大流算法的复杂度为 M(n， m， U) 本算法复杂度为 O(min{nU,nC}[S(n， m， nC)+ M(n， m， U)] ) 这一算法仍然不是多项式时间算法 与最小费用路算法相比 , 可能会以每次迭代调用一次最大流算法为代价 , 希望减少一些迭代次数 . 34 布 置 作 业 目的 掌握最小费用流问题的 基本概念和建模方法 ； 掌握 消圈算法与最小费用路算法及其 复杂度； 掌握原始 对偶算法的基本思想。 内容 《 网络优化 》 第 245251页 3； 6； 15；（第 1讲） 思考 4； 5； （不交） 35 网 络 优 化 Network Optimization 清华大学数学科学系 谢金星 办公室：理科楼 2206 （电话： 62787812） Email: 清华大学课号： 70420203（研） 第 7章 最小费用流问题 (Minimum Cost Flow Problem) 第 2讲 36 (OutOfKilter Algorithm) 瑕疵算法 (也翻译为 “ 状态算法 ” )在迭代过程中则对这些条件更为放宽 : • 只要求满足节点上的流量守恒条件 , 而不要求 x为伪流 (即可能不满足容量约束 ), • 并且也不一定保持互补松弛条件 . 最小费用路算法和原始 对偶算法的特点 : • 对偶变量 为对偶问题的可行解 , 并始终保持互补松弛条件； • 但原始变量 x在算法终止前通常不是原问题的可行解 （ 即只是伪流 ， 而不一定满足节点上的流量守恒条件 , 即不是流值为 v的可行流 ） . 37 (OutOfKilter Algorithm) 想一想 ,非循环流的情况是否都可以转化为循环流的情况 ? 算法的思想： •通过一定步骤 , 使非最优的 “ 程度 ” 不断降低 ， 最后达到最优 . •可以认为 , 瑕疵算法是原始 对偶算法的一种变形 . 瑕疵算法的考察对象： 循环流 (Circulation) ：流值为 0的可行流 （ 没有所谓源点和汇点 , 网络中的所有节点都是转运点 ） 网络中容量下限 L 不一定为 0； 38 Kilter条件 L0 L=0 最小费用循环流模型 当 0 时 ， = 0； (’) 当 0 时 ， = ； (’) 当 时 ， = 0. (’) ijij ux 0ijxijx ijuijcijcijc.),(,0..m i n),(:),(:),(AjiuxlVixxtsxcijijijAijjjiAjijijAjiijij 当 0 时 ， = ； () 当 0 时 ， = ； () 当 时 ， = 0. () ijijij uxl ijxijx ijuijcijcijcijl互补松弛条件 jiijij cc   Kilter条件 （ 或译为瑕疵条件 、 状态条件等 ） 满足该条件的弧为无瑕的 (InKilter), 否则称为有瑕的 (OutOfKilter). 39 Kilter图。 Kilter数 如果所有弧都是无瑕的 , 则得到了原问题的最优解 . 定义 对于每条弧 (i,j), 我们定义其 Kilter数 （ 瑕疵数 、 状态数 ）为将流量 xij修正为满足 Kilter条件所需要修改的量 (假设保持节点上的势不变 ), 记为 K (xij)或 kij, 即 Kilter图 （ 瑕疵图 、 状态图等 ） 当 0 时 ， = ； () 当 0 时 ， = ； () 当 时 ， = 0. () ijijij uxl ijxijx ijuijcijcijcijlijcijl ijuijx.,0,0,0,0,0,其它时且当时且当时当时当ijijijijijijijijijijijijijijijijuxcuxlxcxlcuxclx40 残量网络 当 xijlij时 , 则 (i,j)N(x), uij(x)=lijxij, cij(x)=cij 当 xijuij 时 , 则 (j,i)N(x), uji(x)=xij uij, cji(x)= cij. 瑕疵算法仍然是在残量网络上对弧上的流量进行操作。 由于流不一定满足容量约束 , 需定义这时残量网络的构造方法 : 把原网络中可能增加流量的弧 (前向弧 )、 减少流量的弧 (反向弧 )纳入残量网络 . 具体 方法如下 : 瑕疵算法的思想： 在算法过程中使弧上的 Kilter数不断下降 ,最后降为 0. 当 时 : 如果 xijuij, 则 (i,j)N(x), uij(x)=uijxij, cij(x)=cij。 如果 xijlij , 则 (j,i)N(x), uji(x)=xij lij, cji(x)= cij. ijijijuxl 41 残量网络 可以直接定义弧 (i,j)N(x)的 Kilter数 ， 分三种情况讨论 : 可知 :原网络中的任何一条瑕疵弧一定会在残量网络中得到反映(即瑕疵弧不以前向弧的形式出现 , 就以反向弧的形式出现 ). 当 时 : 如果 (i,j)是瑕疵弧 ( 0), 则其 Kilter数必然等于 (i,j)的残留容量 : kij =uij(x) ijijijuxl  ijc当 xijlij时 : 如果  0, 则 kij = uij(x)=lijxij。 如果 0, 则 kij = uijxij. ijc ijc当 xjiuji 时 :如果 0(即 0),则 kij=xjilji。 如果  0(即 0),则kij=uij(x)=xji uji. ijcjic jic ijcijcijl ijuijx42 步骤 STEP 0 . 给出初始势和初始循环流 (如 =0, x=0). Yakovleva(1959), Minty(1960), Fulkerson(1961)等提出。 Aashtiani和 Magnanti(1976)给出一种高效率的实现方法 . STEP 1. 计算弧上的 Kilter数 . 若网络中不存在瑕疵弧 , 则已经得到最优解 , 计算结束；否则在残量网络 N(x)中 ， 选择一条瑕疵弧（ p,q） , 继续下一步 . STEP 3. 若 （ p,q） 仍为瑕疵弧 , 则沿 P {(p,q)} 确定的增广圈增广流量 (增广的流值为该增广圈的容量 ), 转 STEP 1。 否则直接转STEP 1. STEP 2. 在 N(x)\{(q,p)}中 , 以 max{0, }为 （ i,j） 弧的弧长 ， 计算从节点 q到所有节点 i 的最短路路长 d(i)， 并记从节点 q到节点 p的最短路为 P. 令 i = i d(i), 继续 STEP 3. ijc主要过程 : 一是对节点上势的修改。 一是沿增广圈增广 43 正确性 证明 引理 在瑕疵算法中 , 对节点上势的修改不会增加任何弧上的 Kilter数 . 对残量网络 N ( x ) 的一条弧（ i , j ）  ( p , q ) , 由最短路方程得d ( j )  d ( i ) + m a x { 0 ,ijc }, 即 d ( i ) d ( j ) m a x { 0 , ijc }. 记修改后的势39。 i = i d ( i ), 则 = + = (i d(i)) +(j d(j))= +(d(i)d(j)) max{0, } 39。 ijc ijc 39。 i 39。 j ijc ijcijc ijc当 0:  max{0, } =0 () ijc 39。 ijc ijc ijc当 0:  max{0, } = () ijc 39。 ijc ijc ijc ijc而对于弧 （ i,j） = (p,q)， 由于 d(q)=0， d(p) 0, 所以 = + = (i d(i)) +(j d(j))= +(d(i)d(j)) () 39。 ijc ijc 39。 i 39。 j ijc ijc ijc44 正确性 从 Kilter数的定义知 : 当弧上流量保持不变时 , 只有的符号改变时 , 弧上的 Kilter数才可能改变 . 下面分别对几种情况讨论 : 节点上势的修改不会增加任何弧上的 Kilter数 . 沿增广圈增广呢 ? 当 时 :如果 (i,j) 关于 是无瑕弧 ,则关于 ’ 也是无瑕弧。 如果 (i,j)关于 是瑕疵弧 ( 0), 则关于 ’ 可能是无瑕弧 ,也可能是瑕疵弧 (其 Kilter数必然等于 (i,j)的残留容量 : k’ij = kij =uij(x)) ijijij uxl ijc当 xjiuji 时 :此时在节点上势的修改前后 (i,j)一定都是瑕疵弧 . 与 xijlij类似可证 当 xijlij时 : 此时在节点上势的修改前后 （ i,j） 一定都是瑕疵弧 . 如果  0, 则 0, k’ij = kij = uij(x)=lijxij不变 . 如果 0, 则 : 若 0,则 k’ij = kij = uijxij不变。 若  0,则 k’ij = lijxij  uijxij ijc39。 ijcijc39。 ijc39。 ijc45 正确性 引理 在瑕疵算法中 , 沿增广圈 P {(p,q)}增广流量不会增加任何弧上的 Kilter数 , 且弧 (p,q)的 Kilter数严格减少 沿增广圈 P {(p,q)} 增广流量只可能改变圈上的弧及其反向弧的 Kilter数 . 对于增广圈上容量不可行的弧 (i,j), 由残量网络的构造方法可知 :流量增广后该弧的 Kilter数一定严格下降 , 且不会在残量网络中加入新的弧 (j,i). 对于增广圈上容量可行的弧 , 流量增广不改变容量可行弧的容量可行性。