（运筹学与控制论专业论文）需求不确定的有容量限制网络设计问题.pdf

复口天学管理学院需新确定的有容歙制麓设计6 问5 题15 61 摘要 本文研究的是需求不确定的有容量限制网络设计问题。( c a p a c i t a t e d n e t w o r kd e s i g np r o b l e mw i t hu n c e r t a i nd e m a n d ，简写为c n d p u d ) 。在该网络中， 每个结点对每种商品的需求都是不确定的，构成了一个随机规划问题。同时现有 的网络图中的任意两点间允许存在多条有向弧，决策者必须从网络中选出一些实 际使用的弧来供应需求。同时每条弧上运载的商品数量不得超过其额定的容量限 制，在此条件下安排多商品流的运输任务。每选用一条弧就会发生一个相应的固 定启用成本。此外，在每个结点上，允许短缺或是过量供应，分别给予相应的短 缺或持有成本加以惩罚，目的使得这都分短缺或是多余的需求量尽量小，以降低 成本( 比如失去客户和过量供应造成的额外仓储成本) 。问题的目标是使得弧的 启用成本、短缺持有惩罚成本和线性运输成本三者之和达到最小。 f ： 文中用b e n d e r s 分解算法求解该随机网络设计问题，通过分支定界方法和延 迟约束生成来求解这种夫规模有容量限制的网络设计问题。并在微机上测试了一 夺钱黉墨个结点2 0 条弧的网络i ；3 题，形成运算结果。 关键漏；弼络设计问题，需求不确定，多商品流，随机规划，b e n d e r s 分解。 分类号：0 2 2 窳醢”锄一等脚商叠 心。古r 一。鬻- 复日大学管型学院需求不确定的有容量艰制网络设计问题 a b s t r a c t a c a p a c i t a t e dn e t w o r kd e s i g np r o b l e mw i t hu n c e r t a i nd e m a n d ( c n d p u d ) i s p r o p o s e di nt h i sp a p e r i ti sal a r g es c a l es t o c h a s t i ci n t e g e rp r o g r a m m i n go nw h i c h e a c hn o d eh a sa nu n c e r t a i nd e m a n da n de v e r yp a i ro ft w on o d e sh a ss e v e r a la r c s l i n k i n gt h e m t h ep r o b l e mi st od e c i d ew h i c ha r c ss h o u l db ei n c l u d e di nt h en e t w o r k t om e e tc u s t o m e rd e m a n dw h i l et h et o t a lt r a f f i cf l o w0 i ie a c ha r ci sl e s st h a no re q u a l t oi t sc a p a c i t y o n c ea na r ci ss e l e c t e d ，t h e r ei saf i x e do p e n i n gc o s ta s s o c i a t e dw i t hi t m o r e o v e li f t h ed e m a n do nan o d ei sn o te m i r e l ym e t ，ap u n i s h m e n tc o s ti si n d u c e di n o r d e rt ol e tt m s m i s f i e dd e m a n dm i n i m i z e t h eo b j e c t i v eo ft h i s m u l t i c o m m o d i t y n e t w o r kd e s i g np r o b l e mi st om i n i m i z ea l lt h e s e t h r e ec o s t s ：a r c o p e n i n gc o s t p u n i s h m e n tc o s ta n dl i n e a rt r a n s p o r t a t i o nc o s t b e n d e r sd e c o m p o s i t i o na l g o r i t h mb a s e do nt h ei d e ao fd e l a y e dc o n s t r a i n t g e n e r a t i o nh a sb e e nu s e di nt h i sp a p e rt os o l v ec n d p u d a n db r a n c ha n db o m l d m e t h o dw a se m p l o y e dw h e nd e a l i n gw i t ht h ei n t e g e rv a r i a b l e s t h ea l g o r i t h mw a s t e s t e do nap r o b l e mw i t h5n o d e s ，2 0a r c sa n ds o m er e s u l t so ft h ec o m p u t a t i o n a l e x p e r i m e n ta r ep r e s e n t e d k e yw o r d s ：n e t w o r kd e s i g np r o b l e m ，u n c e a a i nd e m a n d ，m u l t i c o m m o d i t yn e t w o r k f l o w s ，s t o c h a s t i cp r o g r a m m i n g ，b e n d e r sd e c o m p o s i t i o n 2 复日人学管理学院需求不确定的有容量限制网络设计问题 引言 网络设计问题( n e t w o r kd e s i g np r o b l e m ) 是一类具有网络结构的组合优化 问题，主要解决商品如何从供应点集合运输到需求点集合的一大类问题。它是线 性规划领域中经典的运输问题的延伸，是n p h a r d 问题( j o h n s o n 等1 9 7 8 ) 。 网络设计问题研究的内容由最初简单的无容量约束问题发展到有容量约束问题， 从单商品流问题到多商品流问题。其中有关多商品流问题的研究，主要是从上世 纪6 0 年代f o r d 和f u l k e r s o n ( 1 9 6 2 ) 2 1 以及h u ( 1 9 6 3 ) j 发表的研究成果开始 的。多商品流问题的应用十分广阔，其特点是结构庞大，通常拥有大量的变量和 约束条件。线性的多商品流问题不仅是网络设计和运营问题的优化模型，而且所 具有的分解结构特性，使之成为线性优化分解算法的天然例子【4 】。七八十年代出 版了多商品硫问题的一些经典研究成果 5 j 6 1 ，许多采用次梯度法求解的计算实验 获得了成功。这些方法虽然收敛速度慢，但是对对偶变量的数目相对不敏感【4 】。 九十年代以来，随着计算机的发展，多处理机和巨型平行结构的出现，使得分解 技术成为研究热点。线性规划领域经典的分解算法如d a n t z i g w o l f e 算法( 参见 j o n e s 等1 9 9 3 i 7 j ) 和p a r t i t i o n i n g 算法( 参见f a r v o l d e n 等1 9 9 3 8 】) ，都被推广到求 解大规模网络流问题中。 通常在上述问题的研究中一般假定需求是确定的，或是用历史数据中获得的 期望值去代替随机的需求，但这样求得的最优结果在实际应用中往往不能达到令 人满意的效果。在实际应用背景中，决策者除了受到容量约束的限制以外，往往 还要面对顾客需求的不确定( 通常用p o i s s o n 分布描述) ，这就需要我们以一种更 灵活的网络设计方法加以解决。由此引出了一大类更一般的问题称为随机运输规 划s t o c h a s t i ct r a n s p o r t a t i o np r o b l e m s t p 。c o o p e r ，l e b l a n c ( 1 9 7 7 ) 9 】，h o l m b e r g ， j 6 r n s t e n ( 1 9 8 4 ) i 【叫分别提出了求解 s t p l 的有效算法。 本文研究的是需求不确定的有容量限制的多商品流网络设计问题。这是一类 应用十分广泛的问题尤其是在通信网络和配送网络。由于在决策时真实的需求 是无法预知的，或者说我们只有关于需求的不完全信息( 可能是来源于过去的信 息，或是预测) ，这一不确定性增加了网络的复杂性。近年来在通信行业中，网 络供应商一直面临高速增长的顾客需求，如何对现有的网络加以设计，使之尽量 满足顾客需求，同时又能将网络运营成本控制在一定程度内，这已成为网络供应 商关注的中心。在此背景下，网络上弧的容量约束往往成为问题的关键，容量扩 充问题c e p ( c a p a c i t y e x p a n s i o n p r o b l e m ) 等一些旨在增加弧的运力的问题应运 而生。这类问题的研究核心是在需求呈增长趋势时，如何增加网络的运能，使之 满足需求。在研究过程中，随机规划一直担当着强有力的建模工具，国内外许多 学者致力于需求不确定的随机规划问题的研究。 4 复日太学管理学院需求不确定的育容量限制嘲络设计问题 本文所讨沦的大规模网络系统中，点对点的需求也是随机的，所不同之处在 于本文讨论的网络上任意两点间存在多条供选择的有向弧，决策者可以选择同时 启用两点问的多条弧来供应需求，每条弧都有各自固定的启用成本。每个结点上 的需求并不要求完全满足，即允许出现短缺或是过剩供应的情况，并分别给予相 应的短缺或持有成本加以惩罚，目的是使得这部分短缺过量的供应尽量小，以 降低成本( 比如失去客户和过量供应造成的额外仓储成本) 。整个网络设计问题 的最终目标是使弧的启用成本、短缺持有惩罚成本和线性运输成本三者之和达 到最小。并为该模型寻求一个有效算法，求得它的最优解或者在合理的计算时间 和计算机存储空间下寻得该问题的良好上界。 浚模型实际的应用背景有很多，例如现代发达的交通运输业使得两个地区之 间拥有多种运输方式：火车、飞机、轮船、公路运输甚至管道运输方式。这多种 运输方式就构成了网络图上两点之间可供选择的多条有向弧，显然每种运输方式 有着各自的固定建设成本( 比如铁路的铁轨铺设成本) 和单位运输成本，当单一 运输方式不能满足需求，可以同时选择多种运输方式共同完成运输任务。另一方 面，它乜可以被应用在电信行业中。随着市场对通信产品的需求不断扩大，终端 客户往往需要多条电话线来满足其通信的需求，这又是一个两点间多弧的决策问 题。考虑到需求点上的需求是不确定的，在网络中增加选弧的决策，同时考虑需 求的不确定，将有很大的现实意义。本文就是尝试在以往文献的研究基础上，采 用b e n d e r s 分解方法来求解这种需求不确定的网络选弧设计问题：即需求不确定 的有容量限制网络设计问题( c a p a c i t a t e dn e t w o r kd e s i g np r o b l e mw i t hu n c e r t a i n d e m a n d ) 。 本文的第一节将介绍网络设计问题及其应用背景：第二节中，描述问题，定 义决策变量，构建模型和论证问题的复杂性；第三节是求解过程。首先分析模型， 针对这一需求不确定的特性，对模型加以分解，形成主问题和子问题。接着设计 算法求解子问题，并将予问题的解带入主问题进行求解。在这节中将运用b e n d e r s 分解方法；第四节给出算法思路、步骤和框图；第五节构造实例进行计算实验。 同时给出测试的结果，形成运算报告和结论；最后的第六节是对全文的总结。 复且大学管理学院 需求小确定的有容量限制网络设计问题 网络设计问题及其应用背景 网络设计问题是工程师们在设计运输网络和通信网络时常常遇到的问题。 它要求工程师们在一个基础的网络中设计出一个子网络，再用这个子网络来完成 一些运输任务或是通信任务。设计网络时应考虑尽量地使得发生的设计费用和运 输费用( 或通信费用) 之和达到最少。以运输任务为例，用数学的语言来讲，就 是给定一个含有个结点m 条弧的有向图g = ( 矿，a ) ，要求从中选出一些弧构成 一个子网络，用于完成分别将第种商品( k = 1 , 2 ，k ) 从起点s ( k ) 运送至终点 d ( k ) 的世个运输任务。如果弧盘，被选入运输网络，将发生一个固定的设计费用 g ，而第七种商品在弧a ，上的单位运输费用为c ? ( z = 1 , 2 ，m ；k = 1 , 2 k ) 。问 题的目标是使所有发生的费用达到最小。 具体的应用背景不同，会使得构造的网络设计问题的模型有所差异。当在 网络设计问题中加上不同的约束时，其模型结构和求解难度就会发生很大的变 化。下面就从约束的由简到繁，一一来介绍这些网络设计问题。 1 1 无容量限制的网络设计问题 ( u n c a p a c i t a t e dn e t w o r kd e s i g np r o b l e m u n d p i ) 这种网络设计问题是最基础的一种网络设计问题，后面介绍的网络设计问 题都是在它的基础上提出来的。仍以运输问题为例，在这种网络设计问题罩，每 一条用于运输商品的弧上可容纳的商品数量是无穷的。也就是说，在所有的弧上 均可以运输任意多的商品。 用，z o ，( ，= 1 , 2 ，m ；k = 1 , 2 k ) 表示第k 种商品在弧盘，上的运输 量，又用0 1 变量x ，表示是否将弧盘，选入子网络，即 f l 若孤，被选用， 0 否则。 那么无容量约束的网络设计问题可以用下面的数学模型 u n d p 来描述： 复_ 习大学管理学院 需求小确定的有容量限制网络设计问题 u n d p m 烈 0 x t = 0 ，1 v i ，k ：v ，v ；k k ( 1 ) v ，：q a ( 2 ) v l ，k ：嘶a ；k k ( 3 ) v f ：q a ( 4 ) 其中c 为一个足够大的值。 模型中的约束( 1 ) 对应流量守恒的条件，约束( 2 ) 表明只有当弧 盘( f = 1 , 2 ，m ) 被选入子网络时，才能用这条弧来运输商品，而大c 则表示一 旦弧被选中则弧上的容量没有限制，一般称这个约束为连接约束( 1 i n k i n g c o n s t r a i n t ) 。显然 u n d p 是一个混合整数规划问题，含有la 卜m 个o - l 变量x ，和 k m 个连续变量。进一步观察可以发现，约束条件( 2 ) 的系数矩阵是全幺模 的，所以一旦固定了变量x 的取值，总能在整数值上使目标函数值达到最小。 实际上，厂的取值可由所有x ，= l 的弧口，组成的那个子网络中第k 种商品的起 点s ( k ) 运送至终点d ( k ) 的相应于运输费用c j 的最短路得到。 1 2 有容量限制的网络设计问题 ( c a p a c i t a t e dn e t w o r kd e s i g np r o b l e m c n d p i ) 在实际应用中，无论哪条运输线路或通信线路都有它的最大负荷，超过了这 个负荷就会引起整个系统的崩溃，所以在上述一般的网络设计问题的基础上又提 出了有容量限制的网络设计问题 c n d p i 。在这种网络设计问题中，网络中的每 条弧口，( ，= 1 , 2 ，m ) 都给定了一个容量限制d ，要求在上面运输的商品的总量 不得超过d ，。问题可用下面的数学模型来描述： x g + 矿霄 m h。m 复口大学管理学院需求不确定的有容量限制嗍络设计问题 【c n d p m i n s 一。，磊落一协磊瘩2 影，v i , 七：v ，矿；尼k 符 z d i x ， z “0 x 1 = 0 ，l v ，：a a v i ，k ：q 爿；k k v ，：a 4 ( 2 ) f 3 ) ( 4 ) 模型 c n d p 与模型 u n d p i 的区别就在于连接约束( 2 ) 上，约束( 2 ) 要求 即使当弧口，被选使用，其上负载的商品总数量也不能超过q 。 1 3 容量扩充问题c e p ( c a p a c i t ye x p a n s i o np r o b l e m ) 有向图g = ( v ，a ) 上的每条弧扩容前的容量限制为d ，如果对现有的弧进行 容量扩充( 扩充的容量通常是某些基量的整数倍) ，这样模型中不仅有流量变量 还包含扩容变量，目的是使扩容后的网络在满足需求的前提下，整个网络的扩容 成本和运输成本之和达到最小。假定可供选择的扩容设备有两类( t w o f a c i l i t y i n s t a l l a t i o n p r o b l e m ) ，一种是小容量的扩容设备，另一种是大容量的( 定义为小 容量的五倍旯z 。) 。不失一般性，令小容量设备为1 。c e p 问题如下： r a i nc i x + c 2 1 ，+ c 3 f ；。一z = 彰v i ，k ：v ，v ；k k ， l ：a l = f ，叶 c al ：a ，= 叶，+ e a r s _ tz q + x ，+ 砒v i ：a ，a ， x ，y ，z +v i ：a ，a ， 石2 0v i ，k ：a ，a ，k k 在该模型中，x ，( y ，) 代表a i ( 1 = 1 , 2 ，m ) 上所增加的小( 大) 容量设备的 数量，可见它们都是非负整数变量。为弧口，上商品k 的流量，c 1 ( c 2 ) 为小 x g h ， 霄 m 闰。心 复旦人学管理学院 需求小确定的午j 容量限制嗍络设计问题 ( 大) 容量设备的单位扩容成本，钟为点v ，对商品k 的需求。 显然地，c e p 问题包含固定费用流的网络设计问题，所以它是一类强n p 一 困难问题。b i e n s t o c k 和g t i n l t i k ( 1 9 9 6 ) 】讨论了该混合整数规划的多面体结构。 g f i n l f i k f l 9 9 9 ) u 2 i 给出了一种分支一割( b r a n c h c u t ) 算法。 如果弧上的最初的容量为零，且不考虑运输成本，就构成了它的一类特殊问 题，称做网络装载问题n l p ( n e t w o r kl o a d i n gp r o b l e m ) 1 3 1 1 4 1 或称为 m c c i ( m i n i m u mc o s tc a p a c i t yi n s t a l l a t i o np r o b l e m ) 吲。 目前相关文献中有关c e p 问题的求解规模在1 5 个结点2 2 条边，n l p 问题 可以做到1 6 个结点4 9 条边i ”】u 2 1 。对于需求不确定的c e p 问题，可能出现情景 规模最大为5 0 0 个“。 1 4 网络设计问题的研究现状和本文的主要工作 对无容量约束的网络设计问题 u n d p ，已有许多文献作过研究。七十年代 和八十年代初的文献中曾提出过分支定界的精确算法，例如h o a n g ( 1 9 7 3 ) t 1 7 1 ， b o y c e ，f a r h i 年口w i s c h e d e l ( 1 9 7 3 ) 1 8 ，d i o n n e 矛口f l o r i a n ( 1 9 7 9 ) u 9 】，b o f f e y 幂口 h i n x m a n ( 1 9 7 9 ) 20 1 ，l o s 和l a r d i n o i s ( 1 9 8 0 ) 【2 1 以及g a l l o ( 1 9 8 1 ) 2 2 】提出用分支定界 的方法去尝试求解 u n d p i 。但他们能够求解的问题的规模受到很大的限制。1 9 7 8 年，j o h n s o n ，l e n s t r a 和r i n n o o yk a n 1 】三人证明了u n d p 是n p 难的问题。1 9 8 4 年，m a g n a n t i 和w o n g 2 3 j y i s t ! nt u n d p 其实包含了许多组合优化早的特殊问 题，如：最短路问题，最小生成树问题及t s p 问题。八十年代中期的文献中开始提 出包括b e n d e r 分解算法和对偶上升( d u a l a s c e n t ) 算法在内的近似算法。 九十年代以后，拉格朗r 松弛方法备受关注，不少研究者尝试将它融入分支定界 方法来求解网络设计问题。1 9 9 3 年a h u j i a ，m a g n a n t i 和o d i n l 2 6 1 提出松弛约束条 件( 2 ) 的松弛方法，将 u n d p 分解为k + 1 个独立的子问题，即关于k 种商品 的以，1 。( k _ 1 ，2 ，k ) 为变量的k 个最短路问题和另一个关于变量x 的极小 化问题。9 8 年k a jh o l m b e r g 和j o h a nh e l l s t r a n d 2 7 】又提出另一种松弛方法，即松 弛流量守恒约束( 1 ) ，得到对应每一条边的共m 个子问题。将这种松弛方法融 入分支定界结构中，求解问题的规模和效果较为令人满意，求解的问题规模最大 可以达到7 0 个点，1 0 0 0 条边1 3 8 种商品或4 0 个点，1 0 0 0 条边6 0 0 种商品。 复旦人学管理学院 需求不确定的有容量限制网络设计问题 对于在网络设计问题中加入容量约束，得到的有容量约束的网络设计问题 c n d p 也有一些学者作过研究。2 0 0 0 年，k a jh o l m b e r g 和d iy u 印 2 8 1 提出基于 拉格朗日松弛的分支定界方法。这种算法同样松弛流量守恒的约束( 1 ) ，得到 子问题的结构与k a jh o l m b e r g 和j o h a nh e l l s t r a n d9 8 年提出的无容量约束的网络 设计问题的分支定界方法的子问题很相似。但较9 8 年的对 u n d p 提出的方法， 该方法是一种近似方法，因为在求解分支问题的过程中，用到了近似的方法( 体 现在分支原则和剪支原则上) 。这个方法能在合理的运算时间和内存限制下，得 到大规模问题的较好的可行解。 到目前为止，还未见有任何文献在需求不确定的条件下，加入相应的惩罚成 本和选弧成本到网络设计中。本文就是针对对有容量限制需求不确定的网络设计 问题 c n d p u d 进行研究，加以求解。并用它尝试求解一些实际应用背景中的网 络设计问题。 复日大学管理学院需求不确定的有容量限制网络设计问题 2 模型和问题的复杂性 2 1 问题描述 本文研究的有向图g = ( v ，a ) 包含个结点肘条弧，v 为点集，爿为弧集( 边 集) ，即有i v l = n ，a m 。 网络上任意两点间存在多条弧，弧a i 爿( ，= 1 , 2 ，m ) 上的的容量限制记 为d j ( 日 0 ，= t , 2 ，m ) ，如果启用了弧日，那么相对应有一个启用成本( 或称 为选弧成本) g l ( g ， o ，扛1 , 2 ，m ) ，同时弧乜，上第t 种商品的单位的运输成本 记为t ( 彳 o ，= 1 , 2 ，m ；k = 1 , 2 ，k ) 。 2 1 1 商品的定义 在多商品流的网络中，如何定义商品可以有许多选择，主要采用如下两种定 义：一是把不同的源点和汇点的需求定义为不同的商品，即记为巧，( 源点为v ， 汇点为v ) ，这种定义方法下共产生d ( 1 矿1 2 ) 种商品：二是把来源于同一个点的 需求定义为一种商品，这样商品的数量等于点的数量，在此种定义方法下至多有 1 v 1 种商品。这样定义的好处是可以在保持线性松弛问题( l p r e l a x a t i o n ) 最有 解相同的前提下，大大的缩小问题的规模。考虑到这种优势，本文采取第二种方 法定义商品，即商品k 对应于所有汇总到结点v + 的需求。集合k = t ，足 记做 商品集合，共有k 种商品。 2 1 2 需求的不确定性 按照2 1 1 中对商品的定义，结点v ，对商品七的需求，可以用彰来表示 ( v ，v ，t k 并且i 七) 。 对于不确定的需求( 结点v 对商品女的需求) ，是以不同的概率加以描述。 复且人学管理学院需求小确定的有容量限制网络设计问题 当需求量落在某个区间内时，会有相应的概率与之对应。该区间也被称为情景。 将整个问题划分为主问题和子问题的求解，其中每个子问题对应一个情景，对子 问题所求得的最优解就是在该隋景下的最优解，而对于主问题的求解就是各情景 按照各自发生的概率的综合。 由于在决策时需求是不确定的，网络供应商需要一种切实有效的解决方案， 可以使得整个网络的代价降到最低。不考虑科技的因素，对网络供应商而言，只 要他们把弧上的容量限制提高到足够高，面对任何需求他都可以满足。但是弧的 架设成本非常高，这种做法在现实中却不可行。本文借鉴n e w s v e n d e r s 和库存模 型的做法，即不要求网络在任何情况下都能百分之百的满足需求。在对弧扩充容 量后，需求仍未满足的部分或超量供应造成的过剩，分别给予相应的缺货惩罚( 该 惩罚成本也可以视作未满足的需求，发包给外部网络，同时给予外包费用) 或过 剩惩罚。 2 2 定义决策变量 问题的决策变量有三类，分别是： 1 ) 对网络上的弧a ，a ( t = 1 , 2 ，m ) ，用0 - i 变量z ，表示是否将弧选入 网络，它的取值： f i 若弧口，被选用， _ 2 1 0 否则。 z = k = 0 , 1 1 l = 1 ，2 ，删 2 ) 弧口，上第种商品的流变量用f l ( f = l 2 ，m ：k = l ，z 固表示，f k o 。 f = l ，k ：，= i , z 必七= 坛竭，f r p l ： 3 ) 商品k 在结点v 上的短缺或是过剩的的供给记为 ( 江坛后= 垃固，y j 为自由变量。 y = 协i i ，k ：i = i , z m j = 垃尉，y r i k i i v i 。 设置这组并变量正是f h 于我们设计网络时并不知道未来时刻需求的确切的 数量，所以在需求结点v 。上对商品k 的需求存在两种可能性：一是不能满足 该需求，二是供给大于需求造成过剩。汜短缺过剩的供给为y ? ，则在v 。需求点 复旦大学管理学院需求小确定的有容量限制网络设计问题 对k 商品的流量守恒约束条件为： 一石+ y ? = 钟，v i ，k ：v ，v ；k k ； ，砷= ，叶 一l ：a ，= v ，+ ) e 上述约束条件中没有关于变量y ? 正负性的限制，即_ y ? o 或”0 均可，通 过引入以下两组变量取代矿可取任意数的条件： 1 ) 需求未满足时，短缺的需求量记为”k + ，”k + 0 2 ) 需求超额满足时，过剩的需求量记为”k 一，y ? 一0 同时以y ? = y ? + 一y ? 一代入原流量守恒约束中消去y ? 。即有： 一十一= 西，v j ，七：v ，v ；k ak ( 5 ) f q = + ，u ) 一：a t = i v ，+ e a v i ：a ，彳；( 6 ) 同时满足 ”k ，y ? - 0 v i ：v ，矿，k 髟；( 7 ) z 。0v l ，k ：a ，a ，k k ；( 8 ) x ，= 0 ，lv z ：a ，a ( 9 ) 其中( 5 ) 是流量守恒约束条件，( 6 ) 是容量约束条件。( 7 ) ( 8 ) 是流量非 负要求。( 9 ) 为o 一1 变量要求。所有的变量的非负要求和0 - 1 整数要求，可以用 一个矩阵形式写成：( x ，y + ，y - , 厂) o ，1 ) r ”l r ，川r 掣“。 2 3 模型的构建 在结点v 上对商品k 的需求，若能未满足，常常会给网络供应商带来损失( 如 失去客户) ，为此给予相应的单位缺货成本口? ，a ? 20 ：另方面，供给过剩也会 带来一定的持有成本，相应给予单位惩罚矿，b ? 0 。同时弧a ，的固定启用成本 记为曲，商品k 在弧q 上的单位流量代价记为寸，这样模型的求解目标就是最小 化所有的成本，整个网络的优化目标由三项构成：弧的固定启用成本、线性的网 络运输成本、凸的缺货持有成本。网络设计的目的就是将整个成本最小化。最 后把所要解决的网络设计问题转化为两阶段随机规划问题，即在满足流守恒和容 x q ， 。纠 复且大学管理学院需求小确定的有容量限制f 5 9 络设计问题 量约束的条件下的弧启用成本和期望流成本及惩罚成本最小化。整个不确定网络 的求解模型为： mlng+蕃蕃口?y?+十百xf百sbkykl=1i一十善i i = 1c ? ( 2 1 )=l= = iz = l =l z 1j s t ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) 由于d ? 0 和b , k 0 ，这样可以确保最优值中y ? 。和y ? 一不会同时取值大于 零。因为若两者均大于零，不失一般性，假定”k + y ? 一 0 ，那么构造 p ：= y ? + 一y ? 一，y ；”；0 ，显然它也满足约束条件，而且目标值优于y ? + ，y ? 一 的目标值。 用记做随机规划( s t o c h a s t i cp r o g r a m m i n g ) 模型( 2 1 ) 的最优解。( 2 1 ) 用矩阵形式描述为：奄= m i 遗弘+ 砂+ 妙+ 卅( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) j ( 这旱的转置 符号均省略) 。 需求的不确定指的是当判断需要启用哪些弧时，需求是不确定的。此时让每 种商品的需求量由一些随机变量善来决定。事实上选弧的决策早于这些弧被实际 选中并投入运营。另一方面，网络上弧的流量决策则是在确切的需求数据已被观 测到的情况下作出的。故整个决策过程可以分为两阶段：第一阶段决策变量 而，a l a 仅仅根据需求的分布信息来决策；第二阶段在需求d ( 善) 已被观测到的 情况下安排流变量f ( f f ) 。将有容量限制的网络设计问题归结为一个两阶段的随 机规划，其中第一阶段是整数0 1 规划，第= 二= 阶段是连续变量规划。 以下对分布变量f 的假定可以让我们用情景s c e n a r i o s 定义不确定性。 假定：随机变量善是离散分布，取值有限，即互= 转1 ，善8 ，相应的概率为 p 偕= 手) = p 1 ，p 皓= 善5 ) = p 3 。 这里s = l ，s ) 即为s 个情景的集合。情景善所对应的随机需求记为 d ( 善。) 。相应的，当情景孝5 出现时，网络上有一组对应的流变量记为，( 善) 。这 样网络上的运输成本也由随机变量f 决定。注意到，为了完整的描述随机变量， 情景的数量规模是卜分庞大的。以下为了标记的方便，记情景s 发生时的需求d ， 一1 4 复臣火学管理学院 需求小确定的冉容量限制嗍络设计问题 流变量，“，流代价c 5 。 在特定的某一情景s 下，有容量限制的随机网络设计问题的可行域为 胄s ；i + 1 +s_1 _ s ，- ，厂s ) 0 , 1 i a i r t + x l l v lx - - x 月，1 ( 5 7 ) ( 6 ) d i x ， y ? 一、= d ? 。，v i ，k ：v ，矿，k k ，i k ( 5 ) n 整个随机规划的可行域为r = n 。 v i ：a ，a( 67 ) 原问题( 2 1 ) j 以进一步表不成： z s p = m i nx + p 5 ( a y 一+ 砂一+ c f _ ( 五y + - ，y + 5 ，y 一，y 一5 ，厂- ，厂s ) c o n v r 下面进一步讨论缺货持有惩罚函数的性质。由于结点v ，上对商品t 的需求 群为随机变量，如果商品k 在需求点t 有9 7 数量被实际接受，相应的惩罚成本 记为f ( 曰? ，d ? ) ，本文定义的惩罚函数是线性的，但可以证明在多数实际应用中， 。h i 。( q i 。) = e k ? ( q ? ，钟) 】是一个凸函数m 。通常假定概率密度函数 为痧kl 口，k ) 。那么需求的期望值为e 钟】_ r v ( v ) 咖，连续分布函数为 只( ) = r 彤( v ) 咖。只有当g ? 严格小于或是严格大于d ? 时，惩罚成本才会 发生。由过量供应带来的一个单位的持有成本记为 0 ，同时一单位的缺货 成本记为岔 0 ，那么整个持有缺货成本为： h k ，k ，x = 等e ( v g ，k 肥k ( v ) 咖+ o , kf ；( g ? 一v 埘( v ) 咖 上式也可以表示如下： 臂( g ? ) = 等( 研西卜曰? ) + ( 等+ 彰) r p ( v 沙 膨的导数为： 复旦人学管理学院 需求不确定的有容量限制网络设计问题 ! 墨：；：! l ：一 j + ( 芎? + 8 j ) f ? 心 ) d 口 本文讨论的线性惩罚函数的一些结果，可以推广到更一般意义上的凸函数 硝( 9 7 ) 上。 2 4 问题的复杂性 不考虑模型( 2 1 ) 目标函数中的缺货持有惩罚成本和流量成本，原问题简 化为： s t ；。一石= 影v i ，k ：v ，矿，k k ，i k ， l ：a = v ， ai ：a j = “，+ 一 z 。0 x ，= 0 ，1 v ，：以，a ， ( 2 3 ) v i ，k ：a ，a ，k k ， v i ：口，a 这里我们证明问题( 2 3 ) 和背包问题( k n a p s a c k ) 难度相同。 命题2 1 ：平行序列图( s e r i e s p a r a l l e lg r a p h s ) 上的问越( 2 3 ) 是n p - h a r d 】司题。 证明： o l 背包问题( k n a p s a c k ) ：m a x 医：w j ：q 一6 ，一：o ，1 j ，其中 q i ，v i ，b 1 。构造一个有向图g = ( 矿，a ) ，其中v = p ，1 ，2 ，胛，n + l ， 爿= ( s ，i ) t i = 1 ，n + l 扎j ( 胛+ l ，z ) l i = l ，胛) ，d 。= a l , i l ，” ，d 。+ = 1 一b 。 令g ，= w ，v 如，叫浮l ，2 ，g 咖= 0 ，v b + l ，i ) l i = 1 ，棚) ，g 。+ 。= m ，其 中m 是一个比：w ，大的数。每条弧上的容量都定为1 个单位，口= l ，v a 卢a 对每个点1 n + 1 定义一个商品。这样构造的网络图如下： x g h x q w j x i ，则有一x ； w ，一i ， l = l忙l持】，= lr _ lf _ l n 即存在x ”，w ，x ? w i x 这就与x + 是最优解矛盾。基于上述变化都是线性 f = 】i ；1 的，所以证明了问题( 2 3 ) 也是一个n p h a r d 问题。 复旦人学管理学院 需求不确定的有容量限制删络设计问题 3 模型的求解 如果变量没有整数要求，对于求解两阶段的随机规划已有许多十分有效的方 法。而带整数变量要求的随机规划由于存在随机和整数两类难题，相应的研究不 多。而本文讨论的模型结构由于只在第一阶段涉及整数变量，而第二阶段的函数 仍然能保持其线性，所以针对该问题的求解方法是在一般随机规划的求解方法的 基础上加以改进得来的。对第一阶段变量的整数要求，采用分支定界的方法。首 先在3 1 节中对模型进行改进便于后面的算法讨论。 3 1 模型转化 问题( 2 2 ) 是一个大规模的混合整数规划司题，司以借助一些标准的软件 包求解。但是研究发现，x , j - # - 大规模问题，如果能研究其特殊结构进而化繁为简， 往往可使整个求解取得十分好的效果。对于问题( 2 2 ) 的求解我们也想利用这 个方法。 事实上，目标函数是三项的和：1 ) 线性的网络运输成本；2 ) 凸的缺货持 有成本和3 ) 弧的固定启用成本。 如果我们将集合r 5 和尺投影到离散变量x 的空间上。记： 乓= 仁 0 ，l 州砂，y 一叫一，3 尺# 1 1 l 1x r 掣： ( x ，y ，。y ，y 一，叫- s , f l ，5 ) r5 r ，= n 这样问题( 2 2 ) 也可以改写为 =mingxzspm i + 妻此侧工哦_ ， + p 5 2 5 ( x ) k 尺， ( 3 1 而第二阶段的优化的目标是 z s ：m i 匆3 + 幻厂5 + ，s | ( 五y + 1 ，y + s ，yi ，y _ s ，s ) f ( 3 2 ) 复【= l 大学管理学院需求不确定的有容量限制网络设计问题 3 2b e n d e r s 分解算法 本节中，将讨论求解两阶段随机规划( s t o c h a s t i cp r o g r a m m i n g ) 的问题。在这 类重要的研究领域中，在连续两个决策阶段中，需要接连求解两组决策变量。同 时，求解过程中，有一些外部的未知参数将影响第二阶段决策的制定，有关这些 外部参数的信息，仅当第一阶段决策变量取值确定后才能获知，求解这类随机规 划问题，要利用b e n d e r s 分解算法( b e n d e r sd e c o m p o s i t i o n ) ，该算法建立在延 迟约束生成( d e l a y e dc o n s t r a i n tg e n e r a t i o n ) 的思想基础上( 与延迟列生成 ( d e l a y e dc o l u m ng e n e r a t i o n ) 方法类似) 。本文的求解也将利用b e n d e r s 分解算 法。 假定需求存在s = 1 , 2 ，s 种可能的情景，在第一阶段的决策中，仅涉及0 - 1 变量一，向量形式记为x = ( 而，x ：，x 。) ，当第一阶段决策变量z 的值确定后， 我们获得了有关需求的进一步信息，确定了真实发生情景s ，之后的第二阶段决 策中，根据情景s 下与之相对应的需求d 5 ，对变量( y + ，y - , 厂) 进行决策。 考虑决策变量x 的某个耿值i = ( i ，x 2 ，x m ) ，其中i ，= 0 , 1 ( w = 1 ，2 ，m ) 假定它是第一阶段的一个可行解，那么原来v ，v ，两点间不确定入选的多条弧， 现已明确哪些弧入选，哪些未入选，就构成了一个确定的网络图结构。第二阶段 的优化问题就成为在确定的网络图上如何根据发生的实际需求安排流量的优化 问题。这样第二阶段决策变量( y + ，y - , f ) 在不同的情景s 下的最优解，可以分别 求得。 第二阶段的优化的模型： xn。kn。km m i n n ? + 钟一一十才 k = li = 1k = li = 1k = l = l ；”一_ ；舻+ y ? 一一= 彩5 ，v i , k ：v i 矿，k k ， s j t 7 ：畸。 4 一6 。芷7 砷2 。+ 拒爿 ( 3 3 ) d f 写， w ：a e a ， 抄，y + 5 ，y 一，一，ys ，厂1 ，f s ) t e n d + i k i i q r r 1 用矩阵描述： 复且大学管理学院 需求不确定的有容量限制网络设计问题 m i n a y + s 七吟3 七 s l 。 够+ e 矿：一e 矿s = d s ，勺v t v , k e k , k q 写， v l ：a ，e a ， t = i ( y ，y ，y 一，y 一，八，厂5 ) 础i ”磷憎抄， ，一， ，k ”“ 其中矩阵a 为网络的点弧矩阵，e 是单位阵。 记z 5 0 ) 为问题( 3 3 ) 的最优解，用记号2 s ( x ) = 表明问题( 3 3 ) 不可 行。这时我们回到第一阶段对变量五的优化，就得到模型( 3 1 ) ： rs z 口= m i n 豁+ p 5 2 5 ( x ) 睢r ， ( 3 1 ) l s = l j 很自然地，求解模型( 3 1 ) 仅需要考虑那些令z s ( x ) 不等于无穷的x 。