（管理科学与工程专业论文）有预算限制多物资流问题的研究.pdf

有预算限制多物资流问题的研究 摘要 网络流问题在理论研究和实际应用中都受到广泛的关注，多物资流问 题是网络流问题中的一个重要研究领域多物资流的迅速发展及其广泛的 应用领域导致越来越多的人致力于对其进行理论研究多物资流问题大多 都可以用线性规划描述，虽然他们都可以得到最优解，但在许多实际问题 中，这些问题的规模相当大，得到最优解要花费很长时间目前的算法都是 近似算法如何既能减少算法的时间复杂性，又能使得近似解接近最优解， 是当前多物资流问题的一个研究热点有预算限制的多物资流问题是在多 物资流问题基本问题的基础上，添加费用约束得到的本文分别从两方面对 有预算限制的多物资流问题的两个常见模型进行了深入研究 对于有预算限制的最大多物资流问题，给出了时闻复杂性不依赖于物 资数k 的算法由于求解有预算限制的多物资流问题的算法大都要以调用 最短路为子程序，目前，求解最短路的最好的算法是改进后的狄杰斯特拉 算法，我们不能再对该算法进行改进使得其运行时间更少，所以，我们试图 减少调用最短路的次数来减少有预算限制的多物资流问题算法的时间复杂 性本文通过将发点相同的所有物资汇聚到共同的源点的方法来减少迭代 的次数，从而减少调用最短路的次数，使得算法的时间复杂性减少对此给 出严格的理论证明 对于有预算限制的最大并行流问题，本文详细地描述了算法的执行过 程该问题算法的时间复杂性已经不依赖于物资数k ，我们从使得算法求出 的近似值更加接近最优值的角度入手，对该算法的参数进行调整，使得用调 整参数后的算法求解得到的近似值较以前的算法得到的近似值能更加接近 最优值，同时不改变算法的时间复杂性对算法的性质进行了详细严格的 证明同时，用c 语言编程用于求解数值例子，验证了算法调整的有效性 关键词t 有预算限制多物资流问题，近似算法，时间复杂性 t h es t u d yo fm u l t i c o m m o d i t yf l o wp r o b l e mw i t hb u d g e t c o n s t r a i n t a b s t r a c t ：n e t w o r kf l o wp r o b l e mh a sa t t r a c t e dm a n yp e o p l e si n t e r e s t m u l t i e o m - m o d i f y f l o w p r o b l e m i s i m p o r t a n ts t u d y d o m a i n o f n e t w o r k f l o w p r o b l e m t h e r a p i dd e v e l o p m e n ta n dt h eb r o a da p p l i c a t i o nd o m a i no ft h em u l t i c o m m o d i t yf l o w p r o b l e ml e a dt om o r ea n dm o r ep e o p l ed e v o t i n gt h e m s e l v e st od or e s e a r c ho ni t s t h e o r y m o s to ft h em u l t i e o m m o d i t yf l o wp r o b l e m sc a nb ed e s c r i b e db yl i n e a r p r o g r a m m i n g a l t h o u g hb yt h el i n e a rp r o g r a m m i n gw ec a ng e to p t i m a ls o l u - t i o n ，i t 饿凰bal a r g ea n l i n o u n to ft i m et os o l v et h ep r o b l e m sb e c a u s eo fm a n y p r a c t i c a lp r o b l e m s l a r g es c a i e s of 缸m o s to ft h ea l g o r i t h m sa x ea p p r o x i m a t i o n a l g o r i t h m s h o wt or e d u c et h et i m ec o m p l e x i t yo ft h ea l g o r i t h m sa n dm a k et h e a p p r o x i m a t i o ns o l u t i o n sc l o s et ot h eo p t i m a ls o l u t i o n sa t t r a c tm a n yp e o p l ed o i n g r e s e a r c ho ni t w eg e tm u l t i c o m m o d i t yf l o wp r o b l e m sw i t hb u d g e tc o n s t r a i n tb y a d d i n gb u d g e tc o n s t r a i n tt ot h eb a s i cm u l t i c o m m o d i t yf l o wp r o b l e m 。t h i st h e s i s m a k e sas t u d yo nt w oe o n l n l o nm o d e l so ft h em u l t i c o m m o d i t yf l o wp r o b l e mw i t h b u d g e tc o n s t r a i n tf r o mt w of l l o w i n ga s p e c t s ： f o rt h em a x h n u m 州t i c o m m o d i t yf l o wp r o b l e mw i t hb u d g e tc o n s t r a i n t ，w e g i v ea na l g o r i t h mf o ri t t h ea l g o r i t h m st i m ec o m p l e x i t yi si n d e p e n d e n to ft h e n n u lko ft h ec o m m o d i t i e s w en e e dt h es u b r o u t i n go ft h es h o r t e s tp a t ht os o l v e t h em u l t i c o m m o d i t yf l o wp r o b l e mw i t hb u d g e tc o n s t r a i n t s of a r ，t h eb e t t e ra l g o - r i t h mf o rc o m p u t i n gt h es h o r t e s tp a t hi si m p r o v e dd i j k s t r a sa l g o r i t h m ( b yb - i e d - n l a na n dt a r j a n ) w ec a n tr e d u c et h er u n n i n gt i m e ，s ow er e s o r tt or e d u c i n gt h e c a l l i n gt i m e so ft h es h o r t e s tp a t ht or e d u c et h ea l g o r i t h m st i m ec o m p l e x i t y t h e t h e s i sr e d u c e st h e c a l l i n gt i m e so ft h es h o r t e s tp a t hb yg r o u p i n gt h ec o m m o d i t i e s b yac o n l i n o ns o u r c en o d e ，f u r t h e rr e d u c i n gt h et i m ec o m p l e x i t yo fa l g o r i t h mf o r m a x i m u mm u l t i c o m m o d i t yf l o wp r o b l e mw i t hb u d g e tc o n s t r a i n t w ea l s og i v e t h es t r i c tp r o v e m e n ta b o u ti t f o rt h em a x i m u mc o n c u r r e n tf l o wp r o b l e mw i t hb u d g e te o n s t r s i n t w ep r e s e n t t h ed e t a i la l g o r i t h mf o ri t t h i sa l g o r i t h m 8t i m ec o m p l e x i t yi si n d e p e n d e n to f t h ec o m m o d i t yu u mko ft h ec o m m o d i t i e s i no r d e rt om a k et h ea p p r o x i m a t i o n v a l u ec l o s e rt ot h eo p t i m a lv a l u e ，w em u s tt h ea l g o r i t h m sp a r a m e t e r s t h ea l - g o r i t h m 8t i m ec o m p l e x i t yd o e s n tc h a n g w ep r e s e n tt h ed e t a i lp r o v e m e n t a t t h es a m et i m e ，w eu s ecp r o g r a m m i n gt oc o m p u t ean m n e r i c a le x a m p l e ，w h i c h v e r i f yt h ee f f e c t i v e n e s so ft h ea d j u s t m e n tt 0t h ea l g o r i t h m k e yw o r d s ：m u l t i c o m m o d i t yf l o wp r o b l e m w i t hb u d g e tc o n s t r a i n t ，a p p r o x i - m a t i o na l g o r i t h m t i m ec o m p l e x i t y 有预算限制多物资流问题的研究 第一章引言 一多物资流问题简述 网络流是一门传统的学科，它集数学和计算科学知识于一身，还融合了深奥的学 术内容与广泛的适用性，涉及宽泛的应用领域，比如化学和物理、计算机网络，工程 学的大多数分支，制造、公共政策，调度和路由，电信、运输等等 下面就简单的介绍一下和网络流有关的一些概念【1 】【1 目由于文中会涉及图和物资 数，为方便起见，我们用站表示图的顶点数，仇表示边数，k 表示物资数假设我们 研究的图都是连通图，而且物资数较多当物资数很多的时候，会在很大程度上影响 算法的时间复杂性，所以我们要研究时间复杂性不依赖于物资数k 的算法为了简化 表示算法的时间复杂性，以6 表示il o g o ( 1 ) m ( m 为任意常数) 网络：给定有向图g e ) ，容量u ：e ( g ) 一冗斗，即对g 的每一条弧e e 相应有一 函数值u ( e ) ，称为e 的容量它是e 边上的最大容许通过量两个特殊的点集s ( 发点 集) 和t ( 收点集) ，这个四元图( g ，u ，s ，t ) 被称为网络 流守恒：给定有向图g ，容量”：e ( g ) _ 风，流是一个函数，：e ( g ) 一日，满足 ，( e ) “( e ) ，v e e ( g ) ，如果在某个顶点口满足，( e ) = ，( e ) ，我们称流，在 e 6 一( 砷e e 6 + ( ) 点”满足流守恒 8 一流：给定个网络( g ，t ，s ，t ) ，8 一t 流0 s ，t t ) 是一个流，在所有的顶点除了 s ，t 点外都满足流守恒，我们定义8 一t 流的流值为：v a l u e ( f ) = ，( e ) 一i ( e ) e e , f + ( a )e e 6 一( 5 ) 多物资流问题是网络流的一个重要研究领域，现已被广泛的应用到工程学，管理 科学、计算机科学、交通运输、通信工程，经济等领域对社会的发展和科技进步有着 积极的推动作用，近十年受到有关学者的广泛重视下面给出多物资流问题的概念 多物资流。给定有向图g ，容量u ：e ( g ) 一日，需求量d ：e ( h ) 一日，其中e ( h ) 是所有从收点到发点的有向弧( t ，8 ) 所组成的弧集由于技术的原因，通常用第二个 图h = g ( g ) ，e ( 日) ) 表示收发点对有向多物资流问题可以描述为：给定一对具有 相同顶点的有向图( g ，日) ，容量u ：e ( g ) 一日，需求量d ：e ( h ) 一日，令z ，表示g 上 对于，= ( t ，s ) z ( t t ) 的一个s t 流需要求出一簇4 e ，使得所有的e e ( 回， 有z i ( e ) t ( e ) ，其中图g 中的边叫做供应边，图日中的边叫做需求边 ，e ( 日) 多物资流问题产生于几种物资共同使用同一个网络，可以是物资本身不同，也可 以是同一种物资具有不同的发收点不同的物资具有不同的发收点，在每一个中间结 点处，要求每一种物资都要达到自身流值的守恒然而，多种物资的共享边把不同种 物资联系在一起，使得所有物资在该共享边上的流量和不能超过该边的容量在此基 础上添加不同的约束条件，得到不同的模型 有预算限制多物资流问题的研究2 ( 一) 多物资流问题常见模型 为了方便阐述，我们记 ( 毋，t t ) ，i = 1 ，2 ，h 来表示由收发点对构成的集合 1 将同一种物资从发点8 i 通过g 送到对应的收点t i ，0 = 1 ，2 ，f ) ； 2 将不同种物资从发点毋通过g 送到对应的收点如“= 1 ，2 ，f ) ，存在几种不同 的要求， ( 1 ) 将给定的物资、r a l u e ( 魂) ，从8 送到t i ，( i = 1 ，2 ，；) ； ( 2 ) 尽可能照顾各8 i 的情况，将一定量的物资从s t 送到t t ，找到满足容量约束的 可行多物资流并且极大化从巩运到h ( i = l ，2 ，：) 的流值和的问题，即最大多物资流 问题若每条弧给出了单位流的费用，就又引申出两个问题；有预算限制的最大多物 资流问题( 在上述问题的基础上还要添加费用约束) ；最小费用最大多物资流问题 ( 3 ) 给定各物资的需求量d f ，t = 1 ，f 找一个最大的比例值 ，使得每种物资都 将需求量的最大比例值a 倍的流量，从以送到，同时满足容量约束，即最大并行流 问题若每条弧给出了单位流的费用，就又引申出两个问题，有预算限制的最大并行 流问题( 在上述问题的基础上还要添加费用约束) ；最小费用最大并行流问题 ( 二) 多物资流问题解决方法 要解决第一类问题是容易的，只须引入两个新的顶点8 和t 就可以了连接8 和 8 i 和t ( i = 1 ， ) 令它们上面的容量为o 。，然后利用单种物资流问题中求最大流的 方法。问题就可得到解决但这样的处理可能会使某些8 t 或亡落空或过多，失去了多 物资流的意义 要解决第二类问题的第一个问题，我们首先要对问题的可解性进行研究由于有 u ( e ) 的限制，问题不一定有可行解【1 5 1 的第十九章给出了一个该问题有可行解的充 要条件，但这个条件很难验证目前对求解这类问题的算法研究成果很少 解决第二类的第二，三个问题，所用的思想方法是相同的，都是利用原一对偶的 思想进行求解对于此类问题的第二个问题，其引申问题有预算限制的最大多物资流 问题可作为子问题用于解决最小费用最大多物资流问题我们利用二分搜索法寻找最 优费用，每得出一个费用时，就利用求解有预算限制的最大多物资流问题的算法得出 近似最大多物资流该类的第三个问题的引申问题之间也有上述关系本文所研究的 问题，都是利用原对偶的方法解决的 现实生活中，人们经常见到一些网络，如铁路网、公路网、通信网、煤气管网等 这些网络有个共同的特点，就是在网络中都有诸如，物资，人或信息等某种量从一个 地方流向另一个地方，这里的物资、人或信息可以是多种的，因而如何安排这些量的 流动以便取得最大效益是多物资流问题中很有意义的课题下面介绍两个应用多物资 流问题的数学模型来解决问题的实际例子t 通信网络，在通信网络中，顶点代表信息的发点和收点站，边代表传输线，不同 点对之间的信息可看作是不同的物资，每种物资的供应量和需求量对应着这种物资的 发收点之间要发送的信息量每条传输线都有固定的容量在这个网络中，求传输信 息所需的最小费用问题也是一个多物资流问题 运输网络t 运输网络中的发点可看作是不同产品的产地，收点可看作是不同产品 的销售地，中间点可看作是中转站，边代表传输航线，边上的容量可看作是该边代表 的线路的最大运输能力对给定的网络，常常考虑使得某种效益达到最大化的问题是 多物资流问题，可通过构建相应的数学模型来解决 多物资流问题大都可以构建出用线性规划来表示的数学模型，解线性规划问题能 得到最优解，但是许多实际问题的规模相当的大，得到最优解要花费大量的时间本 文的主要内容是从减少算法的时间复杂性和使得近似值更加接近最优值两方面来寻求 多物资流问题的近似算法 二，多物资流问题发展过程 目前，已有许多文献对多物资流问题设计了近似算法有些文献【5 】【6 】吲【8 】【9 1 【1 1 】的 研究是基于拉格朗日松弛法和线性规划分解方法1 3 】来减小多物资流问题的运行时间 的y o u n g ( 1 9 9 5 ) 【1 0 】在s h a h r o k h i 和m a t u l a ( 1 9 9 0 ) a 的工作的基础之上，第一次 提出利用原对偶思想求解最大多物资流问题 g r i g o r i a d i s 和k h a c h i y a n ( 1 9 9 6 ) 12 1 给 出了与y o u n g 具有相同结果的不同算法g a r g 和k s n e m a n n ( 1 9 9 8 ) 1 目对y o u n g 的算 法进行了改进，使得求解最大多物资流问题及其带有费用约束的问题的算法性能比为 硅p ，算法的时间复杂性为d p - 2 k m 2 ) ，使得求解最大并行流问题及其带有费用约束 的问题的算法的性能比为击p ，算法的时间复杂性为d e k m n ) f l e i s c h e r ( 2 0 0 0 ) 14 】改 进了g a r g 和k s n e m a n n 给出的最大多物资流问题的算法，给出了第一个不依赖于物 资数k 的近似算法，算法的性能比为1 + 4 e ，算法的时间复杂性为o ( _ 2 m 2 ) 对于最大 并行流问题及其带有费用约束的问题，当图较为疏松或物资数较多时，f l e i s c h e rl 给 出的算法的时间复杂性要比之前的近似算法的时间复杂性好得多，给出算法的性能比 为硅p ，算法的时间复杂性为6 ( - 2 m + m ) ) k a r a k o s t a s ( 2 0 0 2 ) 1 6 】对最大并行流问题 及其带有费用约束的问题进行改进，给出算法的性能比为击- ，算法的时间复杂性为 石( s _ 2 m 2 ) ，改进了倍因子 三、本文相关的其他理论 优化问题相关概念 1 8 1 5 1 ； 算法复杂性：分为空间复杂性和时间复杂性 空间复杂性：算法在执行过程中所占存储的多少，讨论它需要一些计算机硬件和 数据结构的知识，主要由计算机专业人员进行研究 有预算限制多物资流问题的研究 4 时间复杂性z 算法执行时间的长短我们往往用时间复杂性的标准来衡量算法的 好坏而最广泛采用的标准是它在得到最终结果前所用时间的多少然而，由于计算 机的速度不同，指令系统不同，所用计算机语言不同和并发执行程序的多少不同，同 个算法求解同一问题在不同的计算机环境下执行，所用的时间会有很大的差别因 此，大部分算法分析的文献中，用算法所使用的算术运算、逻辑运算、比较、和转移指 令的步数来表示在假设的计算机上执行所需的时间，把每一个这样的指令称为一个初 等运算，并假设每做一次初等运算就需要一个单位时间我们主要讨论时间复杂性 输人规模，在组合最优化问题中，输入是具有某种数据结构的数据，可能是整数数 组、图和优先集等。为了把输入的数据提供给计算机求解，必须利用某种编码方法把 输入的数据用符号串表示输入规模就是该符号串的长度，即符号串中符号的数目 多项式时间算法一求解一个可计算问题的算法，如果其复杂性函数随输入规模的增 加而多项式的增长时，这个算法才是实际有效的把这种算法称为多项式时间算法 缸因子近似算法。令尹是一个具有非负权值的最优化问题，a 是问题p 的个 多项式时间算法，j 是问题p 的任意一个实例，作为算法a 的输入，若存在之1 ，并 使得 i o p t ( j ) sa f t ) sk o p t ( t ) 我们称a 是p 的一个一因子近似算法，k 也称为算法a 的性能比 近似方案，令p 是一个具有非负权值的最优化问题，该问题的一个近似方案是指 个算法a ，在该算法中，对于问题p 的任意一个实例j - 和s 0 作为输入，满足下列 条件，对于任意一个固定的值，算法a 都是问题p 的( 1 + ) 一因子近似算法 引理1 1 线性规划m a x c x ：a x 6 ) 与m i n y b ：y a = c ，o ) 互为原一对偶线性 规划正和y 分别是对应问题的可行解，即a x sb ，并且y a = c ，g 0 则下面的陈述 是等价的 ( a ) x 和y 是对应问题的最优解； ( b ) c x = y b ； ( c ) y ( b - a x ) - - 0 ； ( a ) 与( b ) 说明原问题和其对偶问题具有相同的最优值 下面介绍和计算机科学相关的概念 1 7 2 0 l 。 堆；是一种数据结构，n 个元素的序列 1 ，k 2 ，k ) 当且仅当满足下列关系时， 称之为堆 笔i 乏。 乏麓k 2 i ，陋坍，幢- ， 查塑复垦型垒塑塞煎回壁塑堑窒 5 满足一组条件关系式即可 关键字t 数据元素中某个数据项的值 最短路问题是网络优化问题的核心问题，它的产生是以大量的实际问题为背景的 它既可以作为一个单独的问题，又可以作为更多复杂问题的子问题经典的求最短路 的算法是狄杰斯特拉给出的求解单源最短路的算法，该算法的时间复杂性为0 ( n z ) 后 人在此算法的基础上进行改进，目前有该问题的强多项式时间算法，称为斐波那契堆 狄杰斯特拉算法 2 1 1 2 1 】，下面给出该算法； f i l m a a e _ e ih e a p d i j k s t r a 算法l ( 1 ) 创建个空的斐波那契堆日； ( 2 ) 置7 r ( 8 ) = 0 ，7 r ( 口) = o ，咖y ( g ) 8 ) ，p r e d ( 8 ) = o 濠示该点的前驱点) ； ( 3 ) 将s 点插入日中； ( 4 ) w h i l e 日od o 找到日中关键字最小的顶点i ，并将其返回； f o r 每一条弧( i ，j ) gd o v a l u e = 7 r ( ) + ； i f7 r ( 0 v a l u et h e n i f u ) = t h e n 7 r o ) = v a l u e ； p r e d = ； 将j 点插入日中； e l s e 0 ) = v a l u e ； p r e d ( j ) = ； 将日中点j 的关键字赋值为v a l u e ； e n d i f e n d i f e n d f o r e n dw h i l e 引理1 2 1 2 1 】上述算法的时间复杂性为o ( m + n l o g n ) 四，本文的组织 本文系统地介绍了有预算限制的多物资流问题，在介绍一般理论的基础上作了进 一步的探索，表明自己的见解，本文的具体安排如下； 第一章引言，简述网络流和多物资流问题，重点介绍多物资流问题常见模型、相 应的解决方法简述多物资流问题的发展现状及对其研究的意义给出和本文内容相 关的其他理论 第二章有预算限制的最大多物资流问题t 给出了有预算限制的最大多物资流问题 的数学模型，研究该问题的时间复杂性不依赖于物资数的算法 第三章有预算限制的最大并行流问题t 给出了有预算限制的最大多并行流问题的 数学模型，研究该问题的算法，优化近似值，而算法的时间复杂性不变 结论总结本文的内容，提出有待于进一步深入研究的工作 有预算限制多物资流问题的研究7 第二章有预算限制的最大多物资流问题 一、问题描述 有预算限制的最大多物资流问题可描述为，给定有向图g e ) ，容量u ：e ( g ) 一 珥，费用c ：e ( g ) 一r + ，k 对发收点( s 1 ，t j ) ，1 j k 令乃表示8 j 到t j 的路 集，p = l ，j ，变量z ( p ) 表示路p 的流量给定预算b ，需要求出一个最大多物资流 m a x e p e pz ( p ) ，其费用不能超过b ，p p e e pc ( e ) z ( p ) b ，并且对所有的e e ( g ) ， 有p ：e px ( p ) 札( e ) 此问题用线性规划表示为 它的对偶线性规划为 m a x z ( p ) p e 尹 s t $ ( p )( e ) v e p ：e e p e c ( e ) 。( p ) s b ( 1 ) p pe e p x ( p )0 v p m i n u ( e ) 2 ( e ) + b e 曰 8 t 【z ( e ) + c ( e ) 纠1 v p ( 2 ) e e p z ( e ) 0v e 20 对偶线性规划表示对g 中的每条弧分配非负弧长度1 和对容量为b 的虚拟弧分配 非负弧长度以使得e e e u ( e ) f ( e ) + b 妒最小，并且满足由l ( e ) + c ( e ) 求得的最短路长 至少是1 每条弧的长度表示多用一单位弧容量的边际费用 二、时间复杂性不依赖于物资数k 的算法 初始时，置原问题的解x ( p ) = 0 ，对偶问题的解f ( e ) = 6 ，v e e ( g ) ，= 6 ，其中6 由n 和e 确定对偶线性规划要求由非负弧长度( z ，) 求得的最短路长至少是1 给 定长度( f ，毋) ，令l + ( z ，) = m i n p p e e p ( f ( e ) + c ( e ) ) 是p 中的最短路长记第t 次迭 代的长度为( k ，也) ，为了简化记号，记( ) = l ( “，也) 令l ( t ) 是l + ( ) 的下界，初 始时置l ( 0 ) = 6 在算法的每次迭代中不是从p 中找出一条由当前长度得出的最短路 进行增广，而是找出一些小于( 1 + e ) l ( g p d 、于( 1 + ) 口) 的路增广设s 为源点组成 的集合，其元素的个数不一定等于物资数k ，在第j 次迭代中，我们考虑具有共同源 有预算限制多物资流同题的研究8 点毋的所有物资，设这些物资为c q ，口= 1 ，2 ，r ，计算由岛为源点出发，长度函数 为( 1 ) 的单源最短路，可求出以岛为源点的所有物资的最短路的值，选取最短路值 最小的路p ，若该值小于1 和( 1 + ) 工( ) 的最小值，就对p 增广，增广的流量由p 上 的最小容量边的容量和焉的最小值确定，即增广m i n m i 沁e p “( e ) ，南) ，记为u ，更 新原问题的解x ( p ) = x ( p ) + 札( 这样得到的流量虽然满足非负条件，但可能会违反容 量限制条件，在算法最后一步要对流值做调整使之可行) 同时更新路p 上的弧长度z 和咖对于具有共同源点岛的所有物资，直到由当前( f ，) 求出的以毋为源点的所 有物资的最短路的值都不小于m i n 1 ，( i + ) 工( t ) ) 时，再考虑具有共同源点岛+ 1 的所 有物资，而l ( ) 不变当具有共同源点西引的所有物资全部考虑完时，即对p 中所 有路长小于m i n l ，( 1 + e ) l ( t ) 的路增广完时，再进行下一次迭代，置全局最短路的下 界l c i + 1 ) = ( 1 + ) l ( ) 在整个算法中，工在 6 ( 1 + ) ) 讵n 中取值令t 是最后一 次迭代因为f ( o ) 4 f ( t i ) 1 ，所以有l + ( t ) 1 + e ，那么，当算法停止时， 1 l ( t ) 1 + 毛即is5 ( 1 + ) 。 l + e l 每次增加( 1 + s ) 倍，所以增加l 的次数是 l o g l + 字 有预算限制的最大多物资流问题的算法 ( 1 ) 置。( 砷= o ，y p p 计算6 = ( 1 + ) ( ( 1 + s ) n ) 1 斥 置l ( e ) = d ，v e e ( g ) ，= 6 ( 2 ) f o ri = 1t o 【l 0 9 1 押半jd o f o r j = 1 t o 旧d o 置p 是具有共同源点毋的所有物资最短路的值最小的路， w h i l ep 的路长 r a i n 1 ，6 ( 1 + ) ) 钍= m i n m i n e e e u ( e ) ，希，其中c ( p ) = 。pc ( e ) ， z ( p ) = z ( p ) + ， t ( e ) = 2 ( e ) ( 1 + 责备) ，v e p ， = 曲( 1 + ! 华) ， 置p 是具有共同源点$ 的所有物资最短路的值最小的路， e n dw h i l e ( 3 ) 置z ( p ) 2 暴，v p p 三、算法分析 引理2 1 2 2 】算法的增广次数是o ( ml 0 9 1 + 。字) 引理2 2 算法对有预算限制的最大多物资流问题产生了一个可行解 引理2 3 z 2 1 给定长度( z ，驴) ，令d ( 1 ，币) = 。l ( e ) u ( e ) + b 妒l + ( f ，咖) = i n i n p p 。p ( z ( e ) + 有预算限制多塑堡流问题的研究 9 c ( e ) ) 记卢= m i n 揣，z ( e ) o , v e ，毋o ，那么p 等于对偶线性规划( 2 ) 的最优值， 即卢等于有预算限制的最大多物资流问题的最优值o p t 引理2 4 【2 q 算法得到的流值至少是( 1 3 e ) o p t 定理2 1 费用不超过b 的最大多物资流问题近似算法的时间复杂性是o ( e - 2 m ( m + n l o g n ) l o g n ) 证明因为进行第二个f o r 循环时，每次循环只有一次最短路计算不会迸行增广。 所以至多有i s l l o g l + 。半次最短路计算用于更新厶其余最短路计算用于增广，由引 理2 1 ，增广次数为o ( ml 0 9 1 押半) 利用f r e d m a n 和t a r j a n 【q 改进的狄杰斯特拉算 法。求最短路算法的时间复杂性为o ( m + n l o g n ) 因此，总的算法的时间复杂性是 o ( ( i s l + m ) ( m + n l o g n ) l 0 9 1 + 。字) ，我们通常假设nsm ，由于吲n ，可得算法的时 间复杂性为o ( m ( m + nl o gn ) l 0 9 1 托半) 对于给定的d = ( 1 + g ) ( ( 1 + s ) ) 挑， l o g l + 。丁l + e = 1 + 两l o 蕊9 6 - 1i s1 + e - 1 l o g ( 1 ( 1 + 而e ) n 石) - 厂l o g ( 1 + e ) = ；( 1 + 而i o g n j ；( 1 + l 们o g n ，、 = d f e l o g n ) 其中，对0 0 令乃表示s j 到t j 的路集，p = u 乃，变量七( p ) 表示路p 的流量给定预算b ，需要 求出一个最大值a ，使得每种物资都至少流m f 单位的流量，z ( p ) 呐，其费用 不能超过e 曼譬c ( e ) 。( p ) b ，并且对所有的e e ( g ) 有tx ( p ) su ( e ) p c 啻p pd d 此问题用线性规划表示为 m a xa s t ez ( p )缸( e ) v e p ：e e p 点z ( p )弛 ( 3 ) p n 。 c ( e ) z ( 尸) b p pe e r 。 $ ( p ) 0v p 它的对偶线性规划为 r a i n eu ( e ) f ( e ) + b e 6 e s t 。 ( f ( e ) + c ( e ) 勺坳，v p b # p e 嘞刁 1 ( 4 ) l ( e 10 v e 0 句 20w 对偶线性规划表示对图g 中的每条弧分配非负弧长度l 和容量为b 的虚拟弧分 配非负弧长度使得磊“( e ) 2 ( e ) + b e 最小对每种物资都分配非负权值刁，满足对 所有物资j ，由l ( e ) + c ( e ) 妒求得的从勺到巧的最短路长度至少是，同时满足所有物 资的权值与需求量的乘积之和至少是1 每条弧的长度表示多一单位弧容量的边际费 用 设原问题和对偶问题的最优目标函数值为p 由于f l e i s c h e r 1 4 1 中提出的方法能将 卢 o ( q = 1 ，2 ，r ) 的最短路旃长度值为威魄。( 缸j ，咖，加) ， 每求一次最短路都要运行一次狄杰斯特拉算法 初始时，置原问题的解z ( p ) = 0 ，置对偶问题的解z ( e ) = 南，v e e ( g ) ，西= 吾，巧= d i s t j ( t ，) ，d i s t j ( t ，咖) 表示物资j 的用o ，) 求出的最短路，j = 1 ，2 ，其中6 由m 和确定具体算法描述如下t 有预算限制的最大并行流问题的算法 ( 1 ) 置。( p ) ：= o ，v p p 计算6 = ( 1 + e ) 孚( 糟) 0 e 1 置l ( e ) = 者，v e e ( g ) ，毋= 軎 ( 2 ) w h i l e o ( t ，毋) 0 厶= m i n 屯，0 ， 屯= 屯一厶， z ( p o , ) = z ( p o ) + 如， e n dw h i l e e n d f o r 2 ( 。) ：猁1 + 挈) ， ：毋( 1 + 垄掣垫) ， e n dw h i l e e n d f o r e n dw h i l e ( 3 ) 置x ( p ) = 每，v p p ( 4 ) a ：m i m 攀扣1 ，2 ， 查塑基眍型墨塑堡煎囹壁笪堑窒 1 2 我们改进算法中的疋令6 = ( 1 + s ) e - c 3l 而1 - - 5 ) ；o o p t 壹重复垦型垒塑塞壅旦堑塑受塞 1 3 情况2 ：令a o ，- ) 1 ，f = 南，v e e ( g ) ，孑= 磊葛，则a ( 初= l ，且器署= d ( 两= 器骞，令勺= 威嘞( 面，j = l ，2 ，k ，( 两是( 4 ) 的可行解，这就归结到了情 况1 综上所述，p = o p t 算法按阶段进行，设算法在t 阶段停止b ，咖j ，代表第i 个阶段第j 次迭 代的第s 步停止后各条弧( 包括虚拟弧) 的长度，路，。代表路吃所增加的流量， 出8 ( 1 i j ，1 ，母t j a _ 1 ) 为本次迭代所选择的用( b ，1 ，也j 户1 ) 计算出的物资e q 的最短路 的值则在第i 个阶段第j 次迭代的第s 步停止后有 d ( 三f 加，氟加) = ( e ) 幻，。( e ) + b 识j ， e e e = u ( e ) l t d ，一1 ( e ) + sl i , j _ 一1 ( b ) 岛， e e e e e p e z u u f 0e q ：e e p e 。 + b 也矗。一l + a ，如一l c ( p q ) 患， 勺 rr = d ( t _ l 咖加一1 ) + 匹瑰。b “( e ) + 瑞一c ( e ) 4 d i a 户l 】 口；1 e 俨1 e r = d ( 1 i a p l ，也，如一1 ) + 端，f 纸伊l ( ) + c ( e ) 也和一l 梵 q = l e r 4 r = d ( h ，p 1 ，西i j 产1 ) + 饬，d i s t e q ( 1 i o 一一1 ，咖j 产1 ) 口；1 设第j 次迭代的最后一步为s l a s t ，此时，以岛为源点的每种物资q = 1 ，2 ，r ) 都 已经各自增加屯单位的流量，则 d ( 如j ，$ z 口武，a j ，s l 。舯) = d ( f i ，o 毋ij ，o ) + e 量l 饬一d i s t e 口( 1 i d ，s 一1 ，如j ，s 一1 ) 由于在算法中z ，咖是严格增加的，所以 d i s t e 日( z i ，j ，b 一1 ，以j ，p 1 ) 战8 屯( f i ，j ，s z 口时，咖，5 f a 8 t ) 一= 1 ，2 ，一，s l a s t 为简单起见，我们记如j ，咖时= l i , j + l ，o ，咖，纠。，t = 也j + 1 ，0 ，我们令幻，a j 表示第j + 1 次 迭代开始时各条边( 包括虚拟边) 的长度，有t 0 f tr d ( h a ，。l ”t ，也j ，武d 。t ) d ( h a ，0 ，也，j ，o ) + 端，。d i a t e g ( 如矗“删，也j ，咖村) s = l 口= 1 rs l a s t = d ( h a ，0 ，嘞，o ) + e 塌d i s t e 。( b ，l a s t ，a 删喊) 口= 1f = l r = d ( 1 i ，j ，0 ，也囊o ) + d 勺出s t c g ( 1 f j ，日f t ，觑j ，s f t ) q = l d ( 岛口，也j ) d ( k j 一1 ，a ，一1 ) + e 如。d i s t e q ( f j ，也j ) q ； 同理可得； d ( h ，籼) sd ( 2 一1 ，也一1 ) + s d q d i s t q ( z t ，也) 查塑蔓垦型墨塑塞煎旦壑笪受塞 1 4 由于o ( z ，钟= d q d i s t g ( z ，有。 d = j d ，破) d ( k 一1 ，也一1 ) + e a ( 1 ，纠，由定理2 可知p j ； 姑，我们有。 d (