（运筹学与控制论专业论文）最小费用网络流的若干新问题研究.pdf

摘要 摘要 近几十年来，组合优化经历了飞速的发展。网络流在生产和社会实践中有 着广泛的应用，是组合优化中被广泛研究的问题之一。网络流上的优化问题涉 及多个学科领域，包括应用数学、计算机科学、管理学以及运筹学等。最小费 用流是最为基本的网络流模型，对于该模型已有丰富的研究成果。随着人类活 动和生产过程的日益复杂，新问题不断出现，这对原有的网络模型构成了挑 战，也为网络流的进一步发展提供了新的源泉。本文主要就近年来出现的来自 生产实践的若干最小费用流问题进行研究，提出了进一步的模型，并给出了求 解新模型的网络单纯形算法。 全文共分七章。第一章主要介绍了本文要研究的主要问题，并对文献中相 关问题的研究成果作了简要的回顾。 第二章介绍了有关网络流的若干基本概念和知识，为后面各章的展开做好 准备。 第三章我们对近年来新提出的一类网络流问题一最小费用分配流，做了进 一步的研究，给出了用单纯形法求解该问题时寻找初始基本可行解的方法，并 把经典网络流中的一些概念和方法推广到了最小费用分配流模型上。 第四章给出了上述最小费用分配流问题的一种推广，并对推广的模型进行 了研究，探讨了该问题的基本可行解的网络结构和性质，设计出了求解该问题 的网络单纯形法。 第五章提出了广义网络上的最小费用分配流问题，称为广义最小费用分配 流问题，第三章和第四章中研究的问题都是这种问题的特殊情形。我们研究了 此类问题的基本可行解的网络结构和性质，并给出了求解该问题的网络单纯形 法，并对如何有效的执行算法进行了探讨。 第六章主要研究了广义等流( g e n e r a le q u a lf l o w ) 问题。我们不仅推广了广 义等流的概念，而且还把广义等流问题推广到了广义网络上，称为广义比例流 问题。通过对该问题的基本可行解的网络结构的分析，提出了求解该问题的网 络单纯形法，并对如何有效的执行算法进行了研究。 第七章对本文的研究结果作了总结，并提出了若干值得进一步研究的问 题。 摘要 关键词：组合优化，网络流，最小费用流，网络单纯形法，供应链，等流问题 一i i a b s t r a c t a b s t r a c t e v e r y w h e r ew el o o ki no u rd a i l yl i v e s ，n e t w o r k sa r ea p p a r e n tn e t w o r kf l o w sa r e o ff o w m gi n t e r e s to v 盯t h el a s tf e wd e c a d e sf r o mt h ep o i n to fv i e wo fb o t ha p p l i c a t i o n sa n dt h e o r y t h et o p i co fn e t w o r kf l o w sh a sa p p l i c a t i o n si ns u c hw i d ef i e l d s 雒 c h e m i s t r ya n dp h y s i t s ，c o m p u t e rn e t w o r k i n g ，m o s tb r a n c h e so fe n g i n e e r i n g ，m a n u r e t u r i n g ，p u b l i cp o l i c y , a n ds o c i a ls y s t e m s ，s c h e d u l i n ga n dr o u t i n g ，t e l e c o m m u n i c a t i o n s ， a n dt r a n s p o r t a t i o n i ti sc l a s s i c a l ，d a t i n gf r o mt h ew o r ko f g u s t a vk i r c h h o f f a n do t h e r e m i n e n tp h y s i c a ls c i e n t i s t so fl a s tc e n t u r y , a n dy e tv i b r a n ta n dc u r r e n t ，b u r s t i n gw i t h n e wr e s u l t sa n dn e 、va p p r o a c h e s t h em i n i n l u mc o s tf l o wm o d e li st h em o s tf u n d a m e n t a lo f a l ln e t w o r kf l o wp r o b - l e r n i i th a sb e e ne x t e n s i v e l ys t u d i e da n df r u i t f u jr e s u l t sh a v eb e e nd e v e l o p e d i nt h i s t h e s i s ，w ef o c u so ns o m en e wp r o b l e m sa r i s i n gf r o mt h ef i e l dm i n i m u mc o s tn e t w o r k f l o wp r o b l e m s ，p r o p o s es o m eg e n e r a l i z e dm o d e l sb a s e dt h e s en e wp r o b l e m s ，a n dd c - v e l o pas e r i e so f r e s u l t s t h e r ea r et o t a l l ys e v e nc h a p t e r si nt h i st h e s i s i nc h a p t e r1 ，w ei n t r o d u c et h e p r o b l e m st h a tw ew i l lw o r ko n ，a n dm a k eab r i e fh i s t o r yo v e r v i e wo fr e l a t e de x i s t i n g r e s u l t si nt h el i t e r a t u r e i nc h a p t e r2 ，w em a k eab r i e fi n t r o d u c t i o nt ot h eb a s i cc o n c e p t sa n dn e c e s s a r y k n o w l e d g ea b o u tn e t w o r kf l o w s c h a p t e r3f i r s t l yg i v e sab r i e f o v e r v i e wo f t h e m a i np r o b l e ma n dr e s u l t sp r e s e n t e d b yp r o f s f a n ga n dq i n e x t ，w i t hr e g a r dt ot h en e t w o r ks i m p l e xm e t h o dp r o p o s e db y f a n ga n dq if o rs o l v i n gm d c f , am e t h o df o rf i n d i n ga ni n i t i a lb a s i cf e a s i b l es o l u t i o n o fm d c fi sp r o p o s e da f t e rt h a t ，w eg e n e r a l i z et h ed e f i n i t i o no ft h es o - c a l l e dp i v o t - i n gc y c l er e s u l t e df r o ma p p l y i n gn e t w o r ks i m p l e xm e t h o d , a n dc o n s e q u e n t l yd e v e l o p am o r ec o m b i n a t o r i a lm e t h o df o rc o m p u t i n gt h er e d u c e dc o s tf o rn o n b a s i cv a r i a b l e s ， w h i c h w o r k sd i r e c t l yo nt h en e t w o r k i nc h a p t e r4 ，w ee x t e n da n dp r e s e n t ss o m ef i l r t h e rr e s u l t so f ap r e v i o u sw o r ks t u d - i e db yf a n ga n dq io nam d c fn e t w o r km o d e lw i t hs p e c i a ls i d ec o n s t r a i n t sr e q u i r i n g p r o p o r i o n a ld i s t r i b u t i o na ts o m en o d e s t h i se x t e n s i o na l l o w sl i st om o d e lal a r g e r v a r i e t yo f p r a c t i c a ln e t w o r kf l o wp r o b l e m sw h e r e $ o m en o d e sm a y n o tn e c e s s a r i l y1 0 r e 一 一l 一 a b s l r a c t s e i n et h ef l o wc o n s e r v a u o nc o n s t r a i n t s t h en e t w o r ks t r u c t u r ea n dp r o p e m e so tt h e b a s i cf e a s i b l es o l u t i o na r ee x t e n s i v e l yi n v e s t i g a t e d , a n dav a r i a n to fn e t w o r ks i m p l e x a l g o r i t h mi sp r o p o s e df o rs o l v i n gs e v e r a lt y p e so fg e n e r a l i z e dm d c fp r o b l e m s t h e p r o p o s e dv a r i a n to f t h en e t w o r ks i m p l e xa l g o r i t h ma l l o w su st ot a k ea d v a n t a g eo ft h e p r a c t i c a lc o m p u t a t i o n a lc a p a b i l i t i e so f t h en e t w o r ks t r u c t u r eo f t h eb a s i cf e a s i b l eg r a p h i nc h a p t e r5 ，w ef i r s t l ye x t e n dt h em a n u f a c t u r i n gn e t w o r kf l o w ( m n f ) p r o b l e m b yf a n ga n dq it og e n e r a l i z e dn e t w o r km o d e l ，a n dt h e n , m o t i v a t e db yt h e i rw o r lw e f o e n so ni n v e s t i g a t i n gt h en e t w o r ks t r u c t u r eo ft h eb a s e so fs i m p l i f i e dv e r s i o no ft h e g e n e r a l i z e dm n fm o d e l ，c a l l e dg e n e r a l i z e dm i n i m u md i s t r i b u t e dc o s tf l o w ( g m d c f ) p r o b l e m e a c hb a s i so f t h eg m d c f p r o b l e mi sc h a r a c t e r i z e da st h eu n i o no fa9 0 0 d a u g m e n t e df o r e s t ( c o n t a i n i n ga r o o ta r ca tt h es n o d ea n ds o m ee x j t i n ga r c sa tt - n o d e s ) a n ds o m ea d d i t i o n a la r c s ，t h i ss t r u c t u r ep l a y sak e yr o l e i nd e s i g n i n ga n dd e v e l o p i n g o u rg e n e r a l i z e dd i s t r i b u t i o nn e t w o r ks i m p l e xa l g o r i t h m t h ep r o p o s e dn e t w o r ka p p r o a c hp r o v i d e ss o m ei n s i g h ti n t od e s i g n i n gc o m b i n a t o r i a la p p r o a c hf o rs o l v i n go t h e r g e n e r a l i z e dm a n u f a c t u n n gn e t w o r k f l o wp r o b l e m s 勘叫f l o wp r o b l e mi so n e o f t h ew i d e l ys t u d i e dn e t w o r kf l o wp r o b l e m s 州t l la d d i t i o n a ls i d ec o n s t r a i n t s i nc h a p t e r7 ，o nt h eo n eh a n d ，w ee x t e n dt h ee q u a lf l o wp r o b l e m t og e n e r a l i z e df l o wm o d e l o nt h eo t h e rh a n d ，w ee x t e n dt h ee q u a lf l o wc o n s l r a m t st o p r o p o r t i o n a t ef l o wc o n s t r a i n t s ，t h u sm a k i n gt h ee q u a lf l o wp r o b l e m a s p e c i a lc a s eo f o u r p r o b l e m ，w h i c hw e r e f e rt o 筋g e n e r a l i z e dm i n i m u mc o s tp r o p o r t i o n a t ef l o w ( g m c p f ) p r o b l e m a f t e rc h a r a c t e r i z i n gt h en e t w o r ks t r u c t u r eo fg m c p fp r o b l e m , w ep r o p o s e ag e n e r a l i z e dn e t w o r ks i m p l e xa l g o r i t h mw h i c he x p l o i t st h en e t w o r ks t r u c t u r eo ft h e g m p c fp r o b l e m m o r e o v e r , w ep r e s e n ti nd e t a i lt h em a i ns t e p so ft h ep r o p o s e dn e t - w o r ks i m p l e xa l g o r i t h ma n dn u m e r i c a le x a m p l ei sg i v e nt oi l l u s t r a t et h ee f f i c i e n c yo f t h ea l g o r i t h m f i n a l l yi nc h a p t e r 7c o n c l u s i o n sa r em a d ea n ds o m ei n t e r e s t i n go p e np r o b l e m sa r e g i v e nf o rf u r t h e rr e s e a r c h k e yw o r d s ： c o m b i n a t o r i a lo p t i m i z a t i o n , n e t w o r ko p t i m i z a t i o n , m i n i n l u n lc o s t f l o wp r o b l e m ，n e t w o r ks i m p l e xa l g o r i t h m ，s u p p l yc h a i n ，e q u a lf l o wp r o b l e m 一一 第一章序言 第一章序言 近几十年，组合优化和图论，广义上来讲作为组合数学的完整研究领域， 经历了飞速的发展i s 2 。网络流在生产和社会实践中有着广泛的应用，是组合 优化及图论中被广泛研究的问题领域之一，横跨多个学科的研究，包括应用数 学、计算机科学、工程学、管理学以及运筹学等。最小费用流是最为基本的网 络流模型，对于该模型已有丰富的研究成果。随着人类活动和生产过程的日益 复杂，新闻题不断出现，这对原有的网络模型构成了挑战，也为网络流的进一 步发展提供了良好的机遇。本文主要就近年来出现的来自生产实践的关于最小 费用流的新问题进行研究，并在此基础上提出了进一步的模型。这些新问题不 同于通常的最小费用流问题，而是带有特殊的额外线性约束。这些额外约束的 出现使得最小费用流问题的网络结构受到影响，因此求解最小费用流问题的网 络单纯形法无法求解这些新问题。 考虑我们所研究的网络流问题均为特殊的线性规訇j 问题，大量实践表明单 纯形法是求解线性规问题的最强有力的( p o w e r f u l ) 的算法。并且，在求解网络 优化问题时，网络单纯形法因其充分利用了问题的网络结构，更是显示其强大 的实际计算效率。因此，单纯形法是求解本章所讨论的问题的一个非常有吸引 力的算法。我们所研究的问题是否具备一定的网络结构，以及若这些问题仍然 保留一定的网络结构，那么如何利用这些问题的网络结构，是充分发挥单纯形 法求解网络问题的计算优势的关键。本篇论文在已有研究结果的基础上，作了 进一步探讨，提出了若干新的模型，并按照上述解决问题的思路进行深入的讨 论和研究，给出了一系列的研究结果。 下面，我们本论文所涉及的重要概念、研究内容、国内外研究现状以及我 们的研究结果作简要的介绍。 1 1 组合优化简介 组合优化又称离散优化，是一类重要的优化模型。一些组合优化问题有着 悠久的历史渊源，著名数学家费马( f e r m a t ) 、欧拉( e u l e r ) 等都对它们进行 过相关研究。但作为运筹学的一个独立分支而发展起来还是近几十年的事二 十世纪后半时，随着计算机科学、管理科学和现代化生产技术等的日益发展， 这类问题与日俱增，越来越受到运筹学、应用数学、计算机科学及管理科学等 诸多学科的高度重视。 第一章序言 定义1 1 1 ：组合优化问题是一个极小( 大) 化问题，它由下述三部分组成： ( 1 ) 实例集合： ( 2 ) 对每一个实例，有一个有穷的可行解集合s ( z ) ： ( 3 ) 目标函数，它对每一个实例，和每一个可行解口s ( j ) ，赋以一个有理 数( z ，盯) 如果该问题是极小( 大) 化问题，则实例珀最优解为这样一个可行 解矿s ( ，) ，它使得对所有的j s ( ，) ，都有f ( i ，c r ) ( z ，口) ( ，( j ，口) s ( z ，口) ) 尽管很多组合优化问题可以转化为整数规划( 或混合整数规划) 问 题，但由于整数规划的求解同样也是困难的，而组合优化又涵盖甚广，因 此人们致力于研究各个问题的组合结构，试图找到一些好的性质和有针 对性的求解方法。常见的组合优化问题有分划问题( p a r t i t i o n ) 、排序问题 ( s c h e d u l i n g ) 、装箱问题( b i np a c k i n g ) 、背包问题( k n a p s a c k ) 、指派问题 ( a s s i g n m e n t ) 、旅行售货商问题( t r a v e l l i n gs a l e s m a np r o b l e m ) 、斯坦纳最 小树问题( s t a i n e r m i n i m a l t r y ) 等。网络中的组合优化问题还包括最短路问 题( s h o r t e s tp a t h ) 、最小生成树问题( m i n i m a ls p a n n i n gt r e e ) 、最大流问题 ( m a x - f l o wp r o b l e m ) 、最小费用流问题( m i n c o s tf l o wp r o b l e m ) 等组合优 化全貌可参见 4 5 ；9 6 】。 1 2 算法和计算复杂性 定义1 2 1 ：算法是指一步步求解问题的通用程序，它是解决问题的程序步骤的 一个清晰描述。确定性算法从前一步到后一步的运行由当前状态唯一确定。如 果存在一个算法，它对组合优化问题7 r 的每个实例，在有限步后一定可以得到 该实例的关于7 r 的提问的答案，那么称该算法解此组合优化问题7 r 。 定义1 2 2 ：对于一个组合优化问题”，如果给定任意一个实例j ，算法a 总能 找到一个可行解c r s ( ，) ，那么就称 为7 r 的近似算法( a p p r o x i m a t i o na l g o - r i t h m ) ；如果进一步这个可行解的目标值总等于最优解值，则称月为最优算法 ( o p t i n i a la l g o r i t h m ) 。 例如，单纯形法就是解线性规划问题的最优算法，表上作业法就是求解运 一2 一 第一章序言 输问题的最优算法，匈牙利算法是求解指派问题的最优算法，而解非线性规划 问题的绝大多数算法由于不能总得到最优解，它们只是近似算法。 算法求解问题是需要时间的，通常，算法所用的时间是指算法中所含的 加、减、乘、除、比较等基本运算次数。而算法所用的时间与实例的规模有 关，为此我们用输入长度来刻划实例的规模。所谓实例的输入长度通常是指实 例所用的计算机内存单元数。 定义1 2 3 ：算法的时间复杂性是指关于实例输入长度n 的函数f ( n ) ，用来表示 算法的时间需求，对每一个可能的输入长度，它是指在最坏情况下该算法解此 输入长度的实例时所需时间( 基本运算步数) 。即对于输入长度相同的所有实 例，把算法对这些实例的最坏情况作为时间复杂性的度量。 如果存在一个多项式函数p ( n ) ，使得算法的时间复杂性为o 加( n ) ) ，那么称 该算法为多项式时间算法，否则称为指数时间算法。还有一类算法叫伪多项式 时间算法，它的时间复杂性是关于实例输入长度n 和实例中最大数的二元多项 式函数。在二进制编码下，伪多项式时间算法并不是多项式时间算法，而是 指数时间算法由此出发，可以导出计算复杂性理论的一系列重要概念和结 论【3 5 】。 例如，求解一般线性规划问题的单纯形算法不是多项式时间算法。尽管如 此，单纯形算法却被大量用来求解线性规划问题。这是因为在很多情况下它能 很快地求解，这与时间复杂性概念并不矛盾。时间复杂性是一种最坏情况下的 度量。单纯形算法这种情况在最优化理论和应用中并不多见。 计算复杂性理论兴起于二十世纪六十年代，和算法的设计与分析密切相 关通过几十年来人们在计算复杂性方面的研究，现今p v p 的猜想已被基 本接受在此前提下，所谓的n p h a r d 问题就不可能在多项式时间内找到最 优解从而，人们在解决方法的有效性、精确性和时间可行性上寻求平衡这 样，一个自然的想法就是放弃对最优解的寻找，而把研究的重点转向寻找能在 较短时间( 多项式时间) 内得到接近于最优解的可行解，称为近似解这种寻 求近似解的算法也就是如前所述的近似算法同时尸一h a r d f a q 题中有一类更 难的问题，称为强尸一h a r d ( s t r o n g l yn p - h a r d ) 问题，这类问题连伪多项式 时间最优算法都不存在1 3 5 1 我们衡量近似算法的优劣可从两个方面来看，一是算法的时间复杂性， 二是算法得到的解值与最优解值的接近程度另外一个在实际中常用的方法 一3 一 第一章序言 是对n p h a r d l h 题加些限制从而得到一些子问题，使其具有有多项式时间算 法这是因为一个问题是p h a r d 的，并不能排斥它的一些特殊子问题是多 项式时间可解的 定义1 2 4 ：如果7 r 是一个极小( 大) 化问题j 是任意实例设a 黾7 r 的一个近似 算法用c _ ( j ) 和c o 刀( j ) 分别表示算法a 解实例j 所得的目标函数值和离线情况 下实例j 的最优目标函数值记肌( j ) = a ；( 舶( ，) = c c o w ( ) ) ，) ，则近似算 法a 的最坏情况界( w o r s t c a s em f i o ) ( 对于离线情形) 或竞争比( c o m p e t i t i v e r a t i o ) ( 对于在线和半在线情形) 定义为 p a ( r ) = i n f p21p a ( i ) p ，v i ) 而问题7 r 的下界( 1 0 w e rb o u n d ) 定义为 ( 7 r ) = k lp a ，v a 如果p a ( r ) = f ( 7 r ) ，则称算法a 对于问题7 r 来讲是最优的( o p t i m a l ) 在不引起混淆的前提下，我们通常将上述定义中的c j ( mc b 刀( j ) 和舶( 7 r ) 分别简记为c 、c o f , r 和儿 定义1 2 5 ：如果某问题有一系列近似算法 a ) ，对于任意给定的 0 ， a 。) 是 一个多项式时间算法，而且p a 。l + e ，则称它为多项式时间近似方 案( p o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e ) ，简记为p t a s 进一步的，如 果 a 。) 的时间复杂性是关于输入长度以及的某个二元多项式，则称它为完 全多项式时间近似方案( f u l l yp o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e ) ，简记 为f p t a s 由于某些组合优化问题本身固有的难度以及最坏情况界估计需要很强的数 学基础和技巧，导致很多情况下无法证明某些算法的最坏情况界，而实际问题 又迫切需要给出一些方案来求解，在这样的前提下，我们给出了启发式算法的 概念 定义1 2 6 ：启发式算法是一个基于直观或经验构造的算法在可以接受的花费 ( 指计算时间、占用空间等) 下给出待解决组合优化问题每一个实例的一个可 行解，该可行解与最优解的偏离程度不一定事先可以预计 一4 一 第一章序言 评价启发式算法的性能主要分为两类，一是看算法占用的时间、空间等， 二是分析算法的效率算法效率往往采用大规模的随机数据进行实验验证，从 平均的角度以及最坏的角度来进行衡量 1 3 网络流问题 网络流是一个综合数学、计算科学、管理科学等多门学科的十分活跃 的研究领域。它就有丰富的研究成果，又有极其广泛的应用范围。网络流 有着悠久的研究历史，其早期工作可追溯至l j k a m o r o v i c h 4 6 、h i t c h c o c k 3 4 以 及k o o p m a n s 5 0 等人研究的运输问题。随1 9 4 7 年d a n t z i g 提出了求解线性规划的 单纯形算法，人们对网络流问题的研究兴趣也随之增强。i ：面d a n t z g 本人也给出 了专门求解运输问题的单纯形算法【2 7 】。 二十世纪5 0 年代，人们开始对最小费用流及其几种特殊情形( 最短路问 题，最大流问题和指派问题) 表现出越来越浓厚的兴趣，这主要是因为这 些模型在实际中有非常重要的应用。很快研究者们提出了专门求解这些问题 的算法，其中d a n t z i g 、f o r d 和f u l k e r s o n 等人作出了开创性的工作。d a n t z i g 主 要致力于基于单纯形的算法的研究，f o r d 和f u l k e r s o n 提出了原始对偶组合算 法。d a n t z i g 2 8 和f o r d 和f u l k e r s o n 3 3 在他们划时代的著作详尽讨论了这些早期 贡献。 继这些开创性的工作之后，网络流成为数以千计的文献及众多教材和 著作的主要的研究课题，新结果和新方法不断涌现。在过去的几十年中， 网络优化经历了飞速的发展。最小费用流问题是网络理论的最为基本的问 题，人们对于该问题的研究成果极为丰富。求解最小费用流的第一个多 项式时间的算法是e d m o n d s 和k a r p 2 9 于1 9 7 2 年提出的。此后相继有多项式 时间的算法提出【l ；7 3 ；1 9 ；1 2 ；3 9 ；4 0 ；8 7 ；8 8 ；9 2 。t a r d o s 9 0 求解最小费用 流的第一个强多项式时间算法，紧接着有许多强多项式时间算法见于文 献 8 ；3 1 ；8 0 ；8 1 ；3 9 ；4 0 ；8 5 ；8 3 ；9 1 】。第一个多项式时间的( 原始) 网络单纯形算 法是i 扫o r l i n 8 6 于1 9 9 7 年给出的。另外，二十世纪8 0 年代中期，许多研究者开 始用内点法 4 7 】来求解一些网络流问题，包括最小费用流问题【6 3 ；9 3 】。 对于广义最小费用流问题，目前已有不少多项式时间算法，如 4 1 ：9 5 等。 但目前还没有求解此问题的强多项式时间算法。 现实生活中很多计划( p l a n n i n g ) 问题都可以转化成最小费用流问题 3 ； 3 8 。然而，实践中有很多跟网络有关的问题包含一些额外的线性约束条件， 第一章序言 这些约束条件破坏了问题系数矩阵的网络结构 6 4 1 。对于这中带有嵌入网络 ( e m b e d d e dn e t w o r k ) 的网络流问题，由于其本身是特殊的线性规划问题，因 此可以用求解一般线性规划的方得以解决。但是，当额外约束的个数不是很多 时，问题仍具有一定的网络结构。若算法能充分利用问题的网络机构则求解问 题的效率会大大提高，目前已有不少这方面的研究1 3 ；1 9 ；1 6 ；2 3 ；3 6 ；3 7 ；4 4 ；4 3 ； 6 4 ；6 6 。另外，还可用拉格朗日松弛法 1 6 ；4 9 ；7 9 求解该类问题，对于一些特殊 问题，这种方法是成功的，但是收敛速度却较慢。c o h e n 和m e g i d d o 2 5 对几类 带额外约束的网络流问题的算法及其复杂性进行了分析，其研究结果表明，这 些问题中的任何一个若存在强多项式时间算法，则意味着一般线性规划问题存 在强多项式时间算法，并证明当额外约束的个数为一固定的数时，问题存在强 多项式时间算法。 最近，方述诚和祁力群教授 3 2 提出了一类新的网络流模型，称 为m a n u f a c t u r i n gn e t w o r kf l o w ( m n f ) 模型，用该模型刻画复杂的合成或 提炼等复杂的生产场景，而通常的网络流模型无法描述这些生产过程。m n f 模 型是带有特定的额外约束的网络流模型。作者在m n f 模型的基础上，给出来了 几类简化的网络优化问题。并主要对其中的最小费用分配流问题进行了研究， 分析并证明了该问题所具有的网络结构，给出了利用该网络结构求解该问题的 网络单纯形法。方述诚和祁力群教授开创性的工作为继续研究此类问题奠定了 良好的基础。本论文的一个重要工作就是对最小费用分配流问题进行进一步的 研究，并且我们在最小费用分配流问题的基础上，提出了新的模型，而且对新 模型进行了深入的研究和探讨，给出了一系列的研究结果【6 0 ；5 8 ；5 9 】。 等流问题是一类研究得较为广泛和深入的带有额外约束的最小费用流问 题，该类问题从等流 6 到简单等流 5 】再到一般等流 2 l 】经历了一系列演变，模 型得到了一些列扩展其应用范围也相应扩大。在本篇论文中，我们对等流问 题也作了进一步的推广，提出了新的模型，即广义最小费用比例流问题，并给 出了相应的研究结果。 在下一小节中，我们把本论文的主要研究作简要介绍。 1 4 论文主要结果 论文的第三章对文 3 2 e 0 的最小费用分配流问题作了进一步研究，给出了 构造问题的一个初始可行解的方法，并把在通常的最小费用流问题计算检验数 的“圈方法”推广到了最小费用分配流问题中，给出了实施网络单纯形法的另 一6 一 第一章序言 外一种方式。 在第四章中，我们给出了最小费用分配流问题的一种推广形式，突破了网 络中的所有顶点都必须保持流量平衡的限制。在推广的模型中，分配顶点处可 以不满足流量平衡条件，从而更加符合实际的应用场景。我们通过在网络中添 加适当的虚拟顶点和虚拟弧，把推广的模型转化成了与原先模型类似的形式， 但是并不完全等同。在对转化后的模型的网络结构进行分析和证明之后，并利 用该结构，给出了求解推广的模型的网络单纯形法。 由于实际问题的复杂多样，对于很多生产场景，通常的网络模型无法对进 行描述，而广义网络就可以对这些场景进行刻画。因此，在论文的第五章，我 们把最小费用分配流模型推广到了广义网络。我们证明，尽管由于额外约束条 件的出现，问题的网络结构不再是增广森林，当额外约束的的个数小于网络中 顶点的个数时，问题仍具有较好的网络结构，从而可以构造相应的广义网络单 纯形法求解该问题。 论文的第六章提出了一类新的广义网络上的比例流模型，该模型涵盖了文 献中提到的等流问题、简单等流问题和一般等流问题。模型中比例流是指给定 若干个弧的集合要求每个集合中弧上的流量成比例里，而且，我们的网络不再 局限于通常的网络，而是在每条弧上都有一个乘子，也就是，弧上的流量可以 不守恒。我们把推广的问题称为广义最小费用比例流。为求解该问题，我们首 先把问题的形式进行转换，然后考虑变化后的问题的网络结构。研究表明，当 额外约束的个数小于网络中顶点的个数时，我们可以利用问题特殊的网络结 构，设计出相应的广义网络单纯形法对其进行求解。 最后，我们在总结全文的基础上，提出了一些值得进一步研究的问题。 一一 第二章网络流基本知识 第二章网络流基本知识 本章介绍图与网络上的一些优化问题，包括图与网络的的基本概念和 基本知识，最短路问题，最大流问题，最小费用流问题等，为后面各章 节的展开作好必要的准备。本章内容主要参照姚恩瑜教授等人编著的教 材【9 6 】，以及a h u j a 等人的 3 】。有关图与网络流基本知识的更为详细的介绍，参 见【3 ；4 ；1 4 ；2 2 ；4 8 ；5 1 ；6 9 ；7 4 ；9 4 ；9 6 。 2 1 基本概念 2 1 1 图 我们经常需要描述和讨论一些事物之间的关系，如一群人之间是否相互认 识，一些城市之间是否可通过公路相互到达，不同的通信中心能否相互传输无 线或有线信息等等。对这类现象的数学抽象，就产生了图的概念，把对象用点 表示，两个对象间有关系就则用一条线段连接这相应的两点。 图论是由e u l e r 3 0 】于1 7 3 6 年研究哥尼斯堡七桥问题时最早创立的【1 8 】。普瑞 格尔( p r e g e l ) 河从古城哥尼斯堡( k 6 n i g s b e r g ) 市中心流过，河中有小岛两 座，筑有七座古桥。1 7 3 6 年，该市一位市民向大数学家e u l e r 提出如下问题： 从家里出发，七座桥每桥恰通过一次，在回到家里，是否可能? 事实上，人们此前已经反复试验过多次，不论怎样游行，都未成功地实现 每桥恰过一次的旅行。但又无人严格证明它。 e u l e r 把两岸分别用c 和d 两点来表示，两岛分别用a 和b 两点来表 示。a ，b ，c ，d 各点的位置无关紧要，仅当两块陆地之间有桥时，在上述相应 的两点间连一曲线段，此曲线段的取值长短也无关紧要，e u l e r 把他画出的这个 图形称为图( g r a p h ) ，见图2 1 。 e u l e r 对七桥问题的回答是“否”。他指出如果如果家在d 岸， 图2 1 中d 点处有三条桥，游人通过其中之一离家出游，不久又经另一桥回 到家，因为每桥恰经过一次，所以把他不得不经过第三条与d 相连的桥远行， 这时他已无法过桥回家了，因为三条与他家相通的桥他己都走过一次；对于家 在别处的情形道理是相似的。 e u l e r 对七桥问题的抽象和论证思想，开创了图论的研究，1 7 3 6 年是图论的 一8 一 第二章网络流基本知识 元年。 1 9 3 6 年，匈牙利数学家柯尼希( k 6 m g ) 出版有限图与无限图理论，这 算是图论的第一本专著，它总结了图论2 0 0 年的成果，是图论发展的第一座里程 碑。此后图论得到了迅速发展时期，又经过半个多世纪的发展，现已成为数学 科学重要的一个重要学科。它有很多分支，例如图论、算法图论、网络图论、 代数图论、随机图论等等。由于现当代科技尤其是大型计算机的迅猛发展，使 图论大有用武之地，无论是数学、物理、化学、天文、地理、生物等基础学 科，还是信息、交通、战争、经济乃至社会科学的众多问题，都可以应用图论 方法予以解决。其中的网络图论( 又称网络流理论) 是近二、三十年得到快速 发展的一个重要的图论分支。 图2 1哥尼斯堡七桥问题 一个( 无向) 图是g 是一个有序二元组( ，) ，其中= 口l ，”2 ，u 。) 是顶点集，= e 。，) 是边集，且白j 是一个无序二元组 饥，) ，它表示该边 连接项点仉和 ，。图2 2 是一个图，在保持图的点、边关系不变的情况下， 图形的位置、大小、形状都是无关紧要的。若e “= 仇，v a ，则称e i ，连 接饥和；弘和” 称为矗，的顶点：称或，与关联，玻与啦是邻接的顶点。如 果两条边有一个公共顶点，则称这两条边是邻接的；两个顶点重合为一点的边 称为环，如图2 2 中e “。如果有两条边的顶点是同一对顶点，则称这两条边为重 边如图2 2 中连接口，与8 “的为两条重边。不与任何边关联的边称为孤立点，如 图2 2 中。没有环的图称为无环图，既没有环也没有重边的图称为简单图。 设有两个图鼠= ( m ，& ) ，i = 1 ，2 ，如晃m 丘，晶岛，且9 1 中点与边的关 系与在岛中的一样，则称吼为岛的子图。若进一步，m = m ，则称岛为岛的 支撑子图( 或生成子图) 。 一o 一 第二章网络流基本知识 图g 中顶点口的度定义为和 关联的边的数目( 与口关联的每个环算作两条 边) ，记为如 。易证下述结论： 定理2 1 1 ：设9 = 0 厂，) 是一个图，则。 r 出( 口) = 2 1 e l ，从而度数为奇数的 顶点有偶数个。 图2 2 图 除非特别说明，本论文后面章节所涉及的图均为简单图。 2 1 2 有向图 一个有向图9 是一个有序二元组( ，4 ) ，其中= 1 ， 2 ，) 是顶 点集，a = ) 称为9 的弧集，为一个有序二元组慨，q ) 。称为从仇连 向t 。的弧，o 玎为地的出弧，t 。的入弧；地为的尾，为的头；钆称为q 的前 继，称为q 的后继。图2 3 给出了一个有向图的例子。与无向图一样，头和尾 重合的弧称为环，有相同的头和尾的弧称为重弧。没有环和重弧的有向图成为 简单有向图。如果把有向图9 中的每条弧似，v j ) 用边 v l ， 来代替，就得到一个 无向图，称为9 的基图。 有向图9 中顶点 的出弧的数目称为 的出度，记为d 吉( ”) ，顶点 入弧的数目 称为 的入度，记为屯( u ) 。定理2 1 2 是与定理2 1 1 平行的结论。 定理2 1 2 ：设岔= ( a c ，一4 ) 是一个有向图，则 矿扣) = d 一( ”) = 1 4