（管理科学与工程专业论文）广义最大并行流问题的研究.pdf

广义最大并行流问题的研究 摘要 现代物流的迅速发展和广泛的应用，导致越来越多的人对其进行理论 研究，网络流问题是重要的理论之一，在现代物流中也有着非常广泛的应用 前景网络流是运筹学中的传统学科，广义网络流是在传统网络上为每条边 增加个收益因子，由于收益因子的存在。使得广义网络流有着更加实际的 应用，广义多物资流是广义网络流中个重要研究领域，如何使广义多物资 流的近似算法运行更陕，结果更加接近最优值是当前的研究热点本文从三 个方面对广义多物资流中的广义最大并行流问题进行了深入的研究 在对网络流简述的基础上，对广义网络流进行具体的介绍。根据收益因 子的不同，对广义网络进行分类，由于前人对广义网络流问题的研究都会讨 论有流广义圈的网络和没有流广义圈的网络两种情况。但对于如何判断网 络中是否有流广义圈都没做提及，针对这一问题，本文根据寻找图中平均权 和最小的圈的算法，自我创新的给出了判断流广义圈的算法，并对算法的正 确性和时间复杂性给出证明 由于求解广义并行流问题的算法需要调用广义最短路子程序，所以广 义最大并行流算法的运行速度主要取决于广义最短路算法的时间复杂性的 多少，在简单讲述了广义最短路问题后，提出了广义最短路新的线性规划形 式，使得广义最短路问题更简单易懂，并介绍了在各种广义网络下求解广义 最短路的算法 着重介绍了广义最大并行流问题，对广义最大并行流问题进行具体的 描述，给出线性规划形式及其对偶形式，通过对将没有流广义圈的网络转化 成l o s s y 网络算法的分析，给出了没有流广义圈的网络下求解广义最大并行 流问题的近似算法，这种算法的每次循环都同时求出具有共同发点的所有 物资的广义最短路，所以和原有算法相比减少了调用广义最短路的次数， 使得算法的时间复杂性不依赖于物资数k ，最后用c 语言编程，计算数值例 子，充分验证了l o s s y 网络下算法的有效性 关键词：广义网络，流广义圈，广义最大并行流，l o s s y 网络，收益因子 t h es t u d yo fg e n e r a l i z e dm a x i m u mc o n c u r r e n tf l o w p r o b l e m a b 吼阳c t ：w i t ht h eq u i c kd e v e l o p m e n ta n dt h ew i d ea p p l i c a t i o n so fm o d e r nl o - g i s t i c s ，m o r ea n dm o r ep e o p l eb e g i nt oi n v e s t i g a t et h et h e o r ya b o u ti t b e c a u s e n e t w o r kf l o wp r o b l e mi sa ni m p o r t a n tt h e o r y , i ta l s oh a sp r o s p e c t so f 丽d ea p - p l i c a t i o n si nm o d e r nl o g i s t i c s n e t w o r kf l o wi sat r a d i t i o n a ls u b j e c ti no p e r a t i o n g e n e r a l i z e dn e t w o r kf l o wp r o b l e mg e n e r a l i z e dt r a d i t i o n a ln e t w o r kf l o wp r o m l e m b ys p e c i f y i n gag a i nf a c t o rf o re a c ha r c b o y a t u s eo ft h eg a i nf a c t o r ，g e n e r a l i z e d n e t w o r kf l o wh a sm a n ym o r ep r a c t i c a la p p l i c a t i o n s g e n e r a l i z e dm u l t i c o m m o d i t y f l o w p r o b l e m i s a n i m p o r t a n t f i e l d i n t h es t u d y o f g e n e r a l i z e d n e t w o r k f l o w ，h o w t o r u nt h ef u l l yp o l y n o m i a la p p r o x i m a t i o ns c h e m e sf o rg e n e r a l i z e dm u l t i c o m m o d i t y f l o wp r o b l e mf a s t e ra n d p r e c i s e ri sa ni m p o r t a n tc o n t e n tt od i s c u s s t h i st h e s i s m a k e sas t u d yo ft h r e ef o rg e n e r a l i z e dn e t w o r kf l o wp r o m l e mo fg e n e r a l i z e dn e t - w o r kf l o wp r o b l e m b a s e do nt h es i m p l ei n t r o d u c t i o na b o u tt h en e t w o r kf l o w ，t h i sp a p e ri n t r o - d u c ew h a ti sg e n e r a l i z e dn e t w o r kf l o w w ec l a s s i f i e dt h eg e n e r a l i z e dn e t w o r kf l o w a c c o r d i n gt ot h ed i f f e r e n tg a i nf a c t o r b e c a u s ee x p e r td i dn o tr e f e rt oh o wt od e - t e r m i n ew h e t h 日t h e r ei sf l o w - g e n e r a t i n gc y c l ei ng e n e r a l i z e dn e t w o r k ，t h i st h e s i s p r e s e n t st h ea l g o r i t h mf o rd e t e r m i n i n gw h e t h e rt h e r ei saf l o w - g e n e r a t i n gc y c l e i n d e p e n d e n t l ya c c o r d i n gt ot h ea l g o r i t h mf o rs e a r c h i n gm i n i m u mm e a nc y c l ea n d p r o v et h ea c c u r a c ya n dc o m p l e x i t yo fa l g o r i t h m t os o l v eg e n e r a l i z e dm a x i m u mc o n c u r r e n tf l o wp r o b l e mi nt h i sp a p e r ，w ew i l l n e e das u b r o u t i n gt os o l v et h eg e n e r a l i z e ds h o r t e s tp a t hp r o b l e m 8 0t h er u n n i n g t i m eo ft h ea l g o r i t h mf o rg e n e r a l i z e dm a x i m u m0 0 n c r e 】1 tf l o wd 印e n d so nt h e r u n n i n gt i m eo ft h ea l g o r i t h mf o rg e n e r a l i z e ds h o r t e s tp a t h w er e m a r kt h et h e g e n e r a l i z e ds h o r t e s tp a t hp r o b l e m ，a n dp r e s e n tt h en e wl i n e a rp r o g r a m m i n ga b o u t i tt om a k et h ep r o m l e ms i m p l e a tt h es a m et i m e ，w e 百、，eas p e c i i ca l g o r i t h mf o r g e n e r a l i z e ds h o r t e s tp a t hf o rd i 舭n tg e n e r a l i z e dn e t w o r k t h i sp a p e rm a i n l yi n t r o d u c eg e n e r a l i z e dm a x i m u mc o n c u r r e n tf l o wp r o b l e m w eg i v ei t sm a t h e m a t i cm o d e li nl i n e a rp r o g r a m m i n ga n di t sd u a lp r o g r a m m i n g f o r m t h o u g ht r a n s f o r m i n gt h en e t w o r kw i t h o u tf l o w - g e n e r a t i n gc y c l ei n t ol e s s y n e t w o r k ，w ep r e s e n tp o l y n o m i a la p p r o x i m a t i o ns c h e m ef o rg e n e r a l i z e dm a x i m u m c o n c u r r e n tf l o wp r o b l e m i ne a c hi t e r a t i o n ，w ec o m p u t et h es h o r t e s tp a t ho ft h e c o m m o d i e sw h o s es o u r c ei st h es a m ep o i n t 8 0a 8t or e d u c et h ec a l l i n gt i m e so f g e n e r a l i z e ds h o r t e s tp a t h s ow eg e tt h ea l g o r i t h mw h o s er u n n i n gt i m ei si n d e - p e n d e n to ft h en u m b e ro fc o m m o d i t i e sk f i n a l l y , a nn u m e r i c a le x a m p l ei ss i r e n b ycp r o g r a m m i n gt oi l l u s t r a t eo u ra l g o r i t h mi sv a l i di nl o s s yn e t w o r k k e yw o r d s ：g e n e r a l i z e dn e t w o r k - f l o w - g e n e r a t i n gc y c l e g e n e r a l i z e dm a x i - m u mc o n c u r r e n tf l o w ，l o s s yn e t w o r k g a i nf a c t o r 第一章引言 一，网络流简述 本研究课题的学术背景是网络流( n e t w o r ka o w ) ，网络流问题在理论研究和实际应 用中都受到了广泛的关注从理论研究上看，网络流问题在数学规划中占有重要地位 在实际问题中，网络流问题在工程学，管理科学，计算机科学，交通运输，通信工程 及经济领域都有非常广泛的应用 由于本课题会涉及图和物资数，为方便起见，我们用n 表示图的顶点数，m 表示 边数，表示物资数我们研究k w , n 的图，这样才能显出算法的时间复杂性不 依赖于k 的好处为了简化表示算法的时间复杂性，以6 表示l o g o ( 1 ) m ( m 为任意常 数) 下面就简单的介绍一下有关网络流的基本概念【15 】 一个给定的有向图g w , e ) 和一个定义在e 上的函数：e ( g ) 一风( 对g 的每一 条弧e e ( g ) ，相应有一函数值u ( e ) ，称为e 的容量，它是e 上的最大容许通过量) ，以及 y 中s ，t 两个特殊的点集( 通常称为发点集和收点集) 组成的四元图( g ，u ，只研为网络 所谓流，是指定义在e 上的个函数，：e ( g ) 一冗+ ，满足关系，( e ) s 札( e ) ，v e e ( g ) 若在某一点 v ，有 ，( e ) = e ，( e ) e 6 + ( 口)e e 5 一( f ) 则称，在 点满足守恒律若对所有的”v ，皆满足守恒律，则称，为一环流若 在g 上，除了两点8 和t ( s s , t t ) 之外，皆满足守恒律，则称，为一8 一t 一流 对于一s t 一流，称 v a u e ( f ) = f ( e ) 一( e ) e e & + ( 5 )e e 5 一( 5 ) 为，的流值 网络流问题分单物资流问题和多物资流问题单物资流问题是经典的物资流问题， 它有两类问题：最大流问题和最小费用最大流问题，这些问题已经研究的比较充分， 解决这些问题已经有了很好的多项式算法，一般的组合最优化的文献都有介绍 s i l a s 多物资流问题在现代物流中有广泛的应用前景，近十几年受到有关学者的重视，并对 它进行了一些研究1 4 1 1 7 1 9 1 但研究的还很不深入，有很多问题等待解决，下一节我们将 对多物资流进行简单的介绍 二、网络流中的多物资流 ( 一) 多物资流综述 在研究多物资流问题之前，我们首先描述一下什么是多物资流【1 引，给定一个有向 图g ，容量u ：e ( g ) 一r + ，霈求量d ：e ( 日) 一乜，其中e ( 日) 是所有从收点到发点的 有向弧( t ，8 ) 所组成的弧集由于技术的原因，通常用第二个图h = g ( y ( g ) ，e ( 日) ) 表 示收发点对多物资流问题可以描述为；给定一对具有相同顶点的有向图( g ，日) ，容 量u ：e ( g ) 一耳，需求量d ：e ( h ) 一耳，令z ，表示g 上对，= ( t ，8 ) e ( h ) 的一个 8 一t 一流需要求出一簇( x f ) i e ，使得对于所有的e e ( g ) ，有 z ，( e ) s “( e ) f e e ( h ) 其中图g 中的边叫做供应边，图日中的边叫做需求边 多物资流问题被频繁的应用于信息系统和分配运输系统，下面我们就来介绍它的 两个应用； 计算机网络【2 1 | ：在计算机通信网络中，图中的顶点表示存储设备、终端设备、或 是计算机系统，图中的边表示存储设备，终端设备和计算机之间的传输线，边上的容 量对应传输线上的容量，供应和需求对应着计算机，终端设备和存储设备之间的数据 传输率 分配网络【2 1 1 ：在分配系统的计划方案中，我们想把不同的产品从工厂运送到零售 商处，运输过程中要使用货车队或火车皮，还需要一些中转站，图中的顶点表示工厂 中转站和仓库，图中的边表示连接工厂，中转站，仓库的线路，边上的容量对应着货 车队或火车皮的装载量，供应和需求对应着传输的产品 根据实际应用中不同的要求，所以对多物资流问题，也存在几种不同的要求， 1 将尽量多的物资从8 1 ，8 2 ，s l 通过g 送到t l ，t 2 ，坛 2 尽可能照顾各巩的情况，将一定量的物资从毛送到t i ，使总的流量最大； 3 将给定物资需求量也的物资a = 1 ，z ) 从以送到缸 要解决第一类问题是容易的，只需引入两个新的顶点8 和t 就可以了连接s 和 以，t i 和t ( i = 1 ，z ) 令连接边上的容量为o o ，然后利用单物资流问题中求最大流问题 的方法，问题就可以得到解决这样的处理可能会使某些以或如落空或过多，失去了 多物资流的意义 第二类问题被称为最大多物资流问题，我们根据要求给出概念 最大多物资流t 给定一对具有相同顶点的有向图( g ，日) ，容量u ：e ( g ) 一目，令z ， 表示g 上对，= ( t ，8 ) e ( h ) 的一个8 一t 一流需要求出一簇( z ，) ，e ( 日) ，使得对于所 有的e e ( g ) ，有 ( e ) u ( e ) ， f e e ( h ) 且使得 v a l u e ( = f ) f e e ( h ) 最大 对第三类问题，我们首先要对问题的可解性进行研究由于有让( e ) 的限制，问题 不一定有可行解 【1 5 】中的第1 9 章给出了一个该问题有可行解的充要条件，但这个 条件很难验证目前对求解这类问题的算法研究成果很少，但我们可以考虑求解每种 物资需求量的最大比倒，这就是近几年来有关学者研究的最大并行流问题，也是本文 重点讨论的问题我们根据要求给出概念 最大并行流z 给定一对具有相同顶点的有向图( g ，日) ，容量u ：e ( g ) 一r + ，需求量 d ：e ( h ) 一皿，令z ，表示g 上对f = ( t ，8 ) e ( h ) 的个值为a d ( ，) 的8 一t - 流需 要求出一簇( 。7 ) ，e e ( 日) ，使得对于所有的e e ( g ) ，有 z ，( e ) t ( e ) ，f ( 哪 且使得a 值最大 无论是最大多物资流还是最大并行流等多物资流问题都可以用线性规划描述，它 们除了用单纯形法解决外，目前没有发现更好的多项式算法，但很多文献对多物资流 问题设计了近似算法【8 】【1 3 1 【1 4 1 下一节我们将介绍多物资流的发展过程 ( 二) 多物资流的发展过程 近十几年来多物资流问题受到有关学者的广泛重视y o u n g 在m a t u l a 和s h a h r o k h i ( 1 9 9 0 ) 1 4 1 的工作基础上，对多物资流的有关问题给出了个近似算法i s ，它是一种原始一 对偶算法，出发点是线性规划和其对偶线性规划g a r g 和k s n e m a n n ( 1 9 9 8 ) 对这个算法 进行了改进，并对有关算法的近似性和时间复杂性的结果进行了证明【1 3 】f l e i s c h e r ( 2 0 0 0 ) 改进了g a r g 和k s n e m a n n 给出的有关算法，给出了最大多物资流问题的第一个时间 复杂性不依赖于物资数的近似算法【1 4 1 ，其算法的时间复杂性为6 ( s - 2 m 2 ) ，对于最大 并行流问题和最小费用最大并行流问题，当图较为疏松或物资数较多时，f l e i s c h e r 给 出的算法的时间复杂性要比之前的近似算法的时间复杂性好得多，其算法复杂性分别 为d ( - 2 r e ( m + ) ) 和6 ( 2 m ( m + 女) l o gm ) ，但可以看出时间复杂性仍依赖于物资数k ， k a r a k o s t a s ( 2 0 0 2 ) 对最大并行流问题进一步研究，给出了时间复杂性不依赖于物资数k 的最大并行流算法【切，其时间复杂性为d ( e - 2 m 2 ) 广义网络是传统网络的推广，在广义网络流中也有多物资流问题，对于广义网络流 我们将在下一章做详细的介绍，这里仅说明一下广义网络流的研究成果广义网络流 问题首先由k a n t o r o v i c h ( 1 9 6 0 ) 1 l 提出，g o l d b e r g ，p l o t k i n 和t a r d o s ( 1 9 9 1 ) 给出了广义最 大流的第一个多项式算法【5 1 ，f l e i s c h e r 和w a y a e ( 2 0 0 2 ) 1 6 】在对传统网络流研究的基础上 给出求解广义网络流问题的近似算法，在对其中的广义最大并行流算法进行讨论时， 给出了求解广义最大并行流算法的时间复杂性为6 ( s - 2 m ( m + ) ) ( 网络中不含流广义 圈) 和0 g 一2 m n ( m + ) ) ( 网络中含有流广义圈) ，k a r a k o s t a s ( 2 0 0 2 ) 1 7 】主要讨论的是时间 复杂性不依赖于物资数的部分网络流的算法，在文章中k a r a k o s t a s 提到了类似于时 间复杂性不依赖于物资数的最大并行流算法可以应用到求解l o s s y 网络下的广义最 大并行流问题，使得其时间复杂性提高倍因子，为d ( 以m 2 ) 三、本文的组织 本文系统介绍了广义网络流的基础知识，在对广义网络研究的基础上，给出时间 复杂性不依赖于物资数的求解广义最大并行流的算法本文的具体安排如下； 第一章引言，介绍网络流的基础及对其研究的意义，简述了网络流的发展现状 第二章广义网络流；比较系统的介绍了广义网络流，对广义网络进行分类，提出 了判断广义网络类型的算法 第三章广义最短路z 介绍了广义最短路问题，给出广义最短路新的线性规划形 式，研究了广义最短路算法 第四章广义最大并行流t 介绍了广义最大并行流问题，给出其在没有流广义圈网 络下的近似算法，用c 语言编程，给出实例 结论对本文作简单的总结，介绍将来要完成的工作 第二章广义网络流 一，广义网络流简述 广义网络流问题首先由k a n t o r o v i c h b 】和d a n t i z i g n 提出它是传统网络问题的推 广，它在传统网络流的基础上将每条边增加一个收益因子7 ( e ) 0 ，使得一个单位的 流流进边e 后，有7 ( e ) 单位的流流出广义网络流和传统网络流一样要满足容量约束 和点守恒约束一个广义网络可以描述为有向图g e ) ，此有向图的边上包括容量 让：e ( g ) 一j “，收益因子7 ：e ( g ) 一见 我们称广义网络上的流为广义流由于收益 因子的存在，广义网络流有很多应用，收益因子可以表示物资由于泄露，蒸发，增生， 利息率等的物理变化，还可以表示由于制造，货币兑换使得一种物资到另一种物资的 转换，例如。美元兑换成欧元，原材料加工成生产材料再t u - r 成成品等广义网络流 问题分为广义单物资流问题 1 0 1 1 1 1 h 1 2 和广义多物资流问题，本文主要研究后者广义 多物资流和传统多物资流一样，也有下面几种常见问题，这里不做具体描述，只是根 据传统网络流情况给出文字叙述，我们将在下一章对广义最大并行流问题进行详细描 述，并给出其线性规划形式 广义最大多物资流，给定一个有向图g ，容量让：e ( g ) 一蜀，f 对收发点对( 即，t j ) ， 找到一个广义流使得对从彤出发到达岛的广义流流值和最大，( 1 j f ) 广义最大并行流t 给定一个有向图g ，容量“：e ( g ) 一目，z 对收发点对( 勺，) 和 需求量d j ( 1 j z ) ，找到一个最大值a 和对应的广义流，使得从勺到达的广义流 的流值为a d j ，坳( 1sj f ) 广义网络流允许每条边上的收益因子是任意的正数，根据收益因子的不同，广义 网络又分为两种不同的类型，在介绍类型之前，我们首先介绍一个概念 流广义圈【1 7 】：当网络中有圈且该圈所包含弧上的收益因子1 的乘积大于1 ，我们称 此圈为流广义圈 下面我们就来介绍一下广义网络的类型； 有流广义圈的网络；当网络中含有流广义圈时，我们称此网络为有流广义圈的网 络 没有流广义圈的网络；当网络中不含流广义圈时，此网络是没有流广义圈的网络 可见没有流广义圈的网络分为两种情况，一种是网络中所有边的收益因子7 1 ， 这时我们称此网络为l o s s y 网络，当所有边上的收益因子7 = 1 时，此l o s s y 网络就成 为了传统网络，l o s s y 网络在实际应用中十分广泛，在这种网络中，通过网络的流仅 可以是泄漏或是守恒另一种是网络中有收益因子1 1 的边，但1 1 的边构不成 流广义圈，我们称此网络为没有流广义圈的非l o s s y 网络 本文主要讨论没有流广义圈的网络( 即l o s s y 网络和没有流广义圈的非l o s s y 网络) 下的广义最大并行流问题 二、广义网络中流广义圈的判断 在研究l o e m y 网络下和没有流广义圈的非k 日y 网络下的广义最大并行流问题之 前，我们首先要知道广义网络的类型，l o s s y 网络是显而易见的，如果网络相当大， 网络中存在的圈相当多时，网络中是否存在流广义圈就不能人工一一计算了，在这一 节我们给出一个算法来判断网络中是否有流广义圈 算法的基本思想是将7 因子取对数再取负数，记为权值c ，找到圈中平均权和最小 的圈，如果此圈的平均权和小于0 ，那么网络中就含有流广义圈具体算法如下t 判断流广义圈算法， ( 1 ) 在图g 中添加一个点8 ，和边( 毛x ) , v x y ( g ) ，并令7 ( ( ) ) = 1 ( 2 ) 置c ( e ) = 一1 0 9 ，y ( e ) ，v e e c g ) ( 3 ) 置n = i v ( a ) l ，f o ( s ) = 0 ，并置昂( z ) = o 。，y ( g ) d f 4 ) f o r = 1 t o n d o f o ra l l 霉v ( 0 1d o 置最( z ) = m e n d f o r f o fa l l ( 伽，z ) 6 - ( $ ) d o i ff k 一1 ( w ) + c ( ( 叫，z ) ) f k ( z ) t h e n 置最仕) = f k 一1 ( ) + c ( ( 删，神) e n d f o r e n d f o r ( 5 ) i fr ( o ) = o 。v x v ( c ) 算法停止( 图g 是无圈的) ( 6 ) 置p ( z ) = 。箩尚。兰知 竹m r a x ( 冰丘气# i ；姓。y ( g ) s ) ( 7 ) i fp ( z ) 0 ，则有流广义圈 e l s e 没有流广义圈 在证明此算法的有效性之前，我们先来看一下k a r p 于1 9 7 8 年给出的最小一最大 定理 引理2 1 【1 q 给定有向图g ，权值c ：e ( g ) 一r 令点8 y ( g ) ，使得图g 中的每一 个点可由8 到达，令最( z ) 表示从点8 到点x ( x y ( g ) ) 的边级数为的权和最小的 值，记为： 最0 ) = n f i n c ( ( q 一1 ，仇) ) ：咖= 8 ，= z ，( 一1 ，仇) e ( g ) ， 如果p ( g ) 表示图g 中圈的最小平均权值( 如果g 是无圈的，则p ( g ) = o 。) ，我们有； p ( g ) = 。r a y i ( n g 。k 。m ，晶a x ( 。) 。1 1 ：! ； i ；。j ；1 盟 一 。 $ y ( g ) o 七如，晶( 神 一“ 证明我们先证无圈的情况，当图g 中无圈，则晶( z ) = o 。，比y ( g ) ，所以引理 成立 接下来我们考虑图中有圈的情况，我们首先证明图中圈的最小平均权值为0 的情 况，即p ( g ) = 0 ，我们要证t m i nm a x 丘唣二掣：0 o 矿( g ) 蜷k 墨n ，n ( z ) 因为p ( 回= 0 ，所以g 中不含负圈对于z y ( g ) ，令z ( 功表示s 一。一路的最短 路长度因为圈g 的权和是非负的，我们有r ( z ) z ( z ) = m i n o k 。一1 毋( z ) ，所以 咄然胁磷掣竺鹱型o 我们只要再证明存在一个点使得r 扣) = z ( ) 即可 因为肛( g ) = 0 ，所以我们可以令d 表示图g 中平均权值为0 的圈，并令”y ( c ) 令p 表示长度为l ( w ) 在圈g 上萤复走n 次的8 一硼一路，即最短路，再令一表示路p 上的前竹条边的路，并设路一的最后一个点为霸我们有8 一z 一路的最短路为一，所 以我们有 e ) c ( e ) = f ( z ) = f 忭0 ) 所以 r a j nm a x 型窭晏盟：0 v ( g ) o s k s n ，风( $ ) 一 在证明了l ( g ) = 0 的情况后，我们来证明更普遍的情况，当p ( g ) 0 时，我们 将图g 中每条边的权值都增加常数q ，那么p ( g ) 则增加了q y ( x ) 增加了咖，见( z ) 增 加了女q ，所以。詈船) 。鲺m s , x 扛) 。垦镰三 姓也增加了常数g 当我们把这个常数选为 一p ( g ) 时，就归结到p ( g ) = 0 的情况了 下面我们就来证明判断流广义圈的算法的有效性和算法的时间复杂性。 定理2 1 判断流广义圈的算法是有效的，其算法的时间复杂性为d ( n + m ) ) 证明我们在算法的第一步并没有添加任何的环，只是保证了图g 中每个点可由s 到达，算法的第三步和第四步保证了求得的最( 。) 为从点8 到点z p y ( g ) ) 的边级数 为的权和最小的值，所以第五步算法结束时，根据引理2 1 ，我们得此图是无圈的 如果第五步后算法不结束，那么我们通过第六步根据引理2 1 ，求得了平均权和最 小的圈的值 再根据算法的第七步，当p ( z ) 0 时，我们记包含点z 的圈为e ，设e 上的权值 为c 1 c 2 、c q ( q 表示圈g 上的边数) ，我们有c l + c 2 + + 勺 0 ，我们有m 他 1 ，根据流广义圈的定义，我们有如果p ( z ) 掣蒿产t h e n 置”( ”) = 型掣，p ( ”) = 。 e n d f o r ( 5 ) i fr y ( g ) ，t h e n 转( 2 ) 因为经典的d i j k s t r a 算法在求最短路时是有效的，通过之前的分析，我们知道我 们对d i j k s t r a 的修正对求l o s s y 网络下的广义最短路是有效的 f l e s c h e r 和w a y n e 给 出了类d i j k s t r a 算法的时间复杂性，我们做一下简单的介绍 引理3 1 1 6 1 在l o s s y 网络中( 权值非负) ，广义最短路可以在o ( m + n l o g n ) 时间内解 出 我们知道在传统网络中，当边上的权值为负但满足权守恒时，我们用m o o r e - b e l l m a n - f o r d 算法解决最短路问题，根据类d i j k s t r a 算法的思想，我们可以将此思想应用到 m o o r e - b e l l m a n - f o r d 算法中，用类m o o r e - b e l l m a n - f o r d 算法来解决没有流广义圈的非 l o s s y 网络下的广义最短路问题，具体算法如下， 类m o o r e - b e l l m a n - f o r d 算法i ( 1 ) 置，r ( s ) = 0 ；7 r ( 口) = o o , v y ( g ) 8 ) ； f 2 ) f o r i = 1 t o n 一1d o f o r 每一条边( ，t l ，) e ( g ) d o i f ，r ( ) 掣描产t h e n 置”( 伽) = 巫帮护( 叫) = ” e n d f o r e n d f o r 亡墨墨盔羞堑煎旦堑塑受塞 1 1 我们可以看出上述算法的时间复杂性为o ( 7 t m ) 三、小结 本章围绕上一章介绍的广义网络的不同类型对如何求广义最短路给出详细的介 绍在介绍如何求广义最短路的过程中，我们给出了广义最短路新的线性规划形式， 并具体介绍了求妇y 网络下广义最短路的算法，通过改进m o o r e - b e l l m a n - f o r d 算法 给出没有流广义圈的非l 0 8 昭网络下广义最短路的算法 一，问题描述 第四章广义最大并行流 广义最大并行流问题可描述为t 给定有向图g e ) ，给定容量u ：e ( g ) 一日，l 对 发收点( s j ，t j ) ，1 j f ，对于每种物资j ，需求量为d j 0 令乃表示勺到如的路集， p = u r j ，变量z ( p ) 表示经过路p 到达收点的流量给定一条路p 巧，p = e 1 ，钾， 我们定义 ( e 口) = 1 n7 慨) ，于是我们知道x ( p ) f p ( e q ) 表示路p 上经过边e q 的实际 z = q 流值需要求出一个最大值凡使得每种物资到达收点t 的流量都至少为a 由个单位， 。( p ) 磁，并且对所有的边e e ( g ) 有t静( e ) 。( p ) s u ( e ) p乃p：effp 此问题用线性规划表示为t h l a xa 8 t 竹( e ) $ ( p ) p ：e e p ( p ) 尸乃 o ( 尸) 它的对偶线性规划为【1 8 l ： “( e ) v e 确巧 0v p m i l l “( 叫( e ) e e e ( v ) 8 t e ( e ) f ( e )芝巧，v p 乃 8 尹 由z 1 1 j = l l ( e )0 v e 勺0 ( 2 ) 对偶线性规划表示对图g 中每条弧都分配非负弧长度f ( e ) ，使得“( e ) 2 ( e ) 最 e e e ( g ) 小，令 弓1 ，p j r ) 乃，我们对每种物资都分配非负权值勺，令勺2 咄。邑。协t ( e ) 2 ( e ) ， i n i 啦弼。( e ) z ( e ) 表示由f ( e ) 求出的从勺到岛的广义最短路长度，即d i s t j ( 1 ) 那么 对偶线性规划满足对所有物资j ，由f ( e ) 求得的从到t j 的广义长度至少是z j ，同时 满足所有物资的权值与需求量的乘积之和至少是1 。每条弧的长度表示多一单位弧容 量的边际费用，每种物资的权值表示不满足额外的一单位物资需求的边际费用 定理4 1 给定长度z ，d ( z ) = u ( e ) f ( e ) ，n ( 1 ) = e 而d i s 白( z ) = 嘞勺，卢= e e e ( g )j = 1，= l r a i n 器：娶 ( e ) z ( e ) 刁，v p ；l ( e ) 2o ，y e ；z j o ，) ，那么卢等于对偶线性规划、， p ；p ( 2 ) 的最优值，即卢为最大并行流问题的最优值o p t 证明考虑下面两个最优化问题 m i n 韶 8 t 7 p ( e ) z ( e ) w ，v p 乃 e e p z ( e ) 0y e 0v j ( 3 ) m i n d ( 1 ) s t e y p ( e ) l ( e ) 句w ，v p 乃 。尹 d j 勺 1 j = l f ( e )0 v e 句0 ( 4 ) 显然卢是最优化问题( 3 ) 的最优值，线性规划( 4 ) 是对偶线性规划( 2 ) 的不同形式只 要证明最优化问题( 3 ) 和( 4 ) 最优值相同即可而( 4 ) 的最优值为o p t ，即证出p = o p t 首先证明p _ 1 ，令沁) = - ( e ) 肛( - ) ，v e e ( g ) ，则2 = 南，a ( o = 辩= 1 ，因为量 ( e ) “e ) 一 b z l , v j ， 乃，所以善嘴严2 南，即善7 p ( e ) f ( e ) 2z 4 j , 坳，v p 乃，而暑嘞勿2 n ( f ) = 1 所以；也是( 4 ) 的可行解，又有d ( f ) d ，这与 是( 4 ) 的最优解矛盾) 于 是有d ( d = d ( d o ( d 因为r 是( 3 ) 的可行解，则有p 器= d ( i ) = o p t 下面证明p o p t ，令r 是( 3 ) 的最优解。 情况1 ：n ( - ) = 1 r 是( 4 ) 的可行解，则有卢= d ( i ) 口( d = d ( - ) o p t 情况2 ：- ( h 1 ，令f ( e ) = 虱e ) 口( d ，v e e ( g ) ，则a ( f ) = 1 ，且d ( - ) 纽囝= d ( f ) o ( f ) ，即 是( 3 ) 的最优解，也是( 4 ) 的可行解，这就归结到了情况1 综上所述，p = o p t 。 二、l o s s y 网络下求解广义最大并行流的算法 ( 一) 最优值大于等于1 的情况 我们要给出最优值大于等于1 ( 即卢21 ) 时的广义最大并行流问题的近似算法，出 发点是线性规划( 1 ) 和对偶线性规划( 2 ) 对任意近似参数 0 ，我们的算法要得到 这个问题的5 一近似解广义最大并行流问题的e 一近似解是指算法得到的a 值至少 是( 1 一s ) a o p t 而算法的时间复杂性不依赖于物资数，该算法的时间复杂性要好于 f l e i s c h e r 和w a g n e 给出的算法【 根据k a r a k o s t a s 给出的算法的时间复杂性不依赖于物资数的最大并行流算法 吲，我们给出了l o s s y 网络下广义最大并行流算法算法分阶段进行，每一个阶段由 吲8 次迭代组成( 8 是发点的集合) 在第i 个阶段的第j 次迭代中，我们考虑发点为s j 的所有物资，设c l ，c 2 ，讳是这些物资我们在这一次迭代中要通过一系列的步骤把 物资勺的流量增加d c 。( 其中口= 1 ，r ) 令如j ，。是在第i 个阶段第j 次迭代中第8 步后的长度函数在第s 步中我们同时计算从彤出发到勺的收点的广义最短路哟 即均一的长度为d i s t 勺( b ，一t ) ，可见在一个阶段中要计算有共同源点彤的所有物资 的广义最短路只需调用一次类d i j k s t r a 8 算法令锡，。 0 表示在第s 步物资勺的剩 余需求量可见略，o = d c q 在第s 步，我们让每种物资沿路饬一流到勺的汇点 的流量为瑞一= m i n 彩p 1 ，m a n e e ，器。瓦u 蓦e 。，、w = 1 ，r ) ) ，接下来我们更新铌，。一， 和k j ，( e ) ，v e 曩z 。 = 1 ，r ) 的值，在最后一步，对于所有源点为勺的物资勺有 奶，。= o ( q = 1 ，r ) ，当d ( ，s ) 1 时，整个过程结束 初始时，置原问题的解$ = 0 ，对偶问题的解l l ，0 ，o ( e ) = 6 “( e ) ，v e e ( g ) ，其中6 由 m 和s 确定为简便，我们用，如表示第i 个阶段第j 次迭代中第8 步的物资勺的 广义最短路端，。和到达物资c q 汇点的流值岛，具体算法描述如下t l o s s y 网络下广义最大并行流算法。 ( 1 ) 置z ( p ) = 0 ，y p p 计算6 = 赤( 鲁) ，其中( o ，1 ) 置t ( e ) = 6 肛( e ) ，v e e ( g ) ( 2 ) w h i l e d c l ) 0 置民是中的广义最短路 e n dw h i l e e n d f o r c = m i n e p q 韵( 口= 1 ，r ) ， f o r 口= 1 t ord o w h i l e 0 如= m i n 屯，c ) ， 屯= 屯一如， 。( ) = $ ( ) + 屯， e n dw h i l e e n d f o r z ( e ) = z ( e ) ( 1 + e 垦型掣) ，r ，u u ， e n dw h i l e e n d f o r e n dw h i l e ( 3 ) 置x (