（运筹学与控制论专业论文）两类推广的动态设施选址问题的近似算法.pdf

独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表和撰写过的研究成果，也不包含为获 得北京工业大学或其他教育机构的学位或证书而使用过的材料与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意 签名：徘 日期：矽沙r 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文 ( 保密的论文在解密后应遵守此规定) 签名：丕奄0 钐导师签名： 期：舢j 摘要 摘要 本论文主要研究带惩罚的动态设施选址问题及软容量约束的动态设施选址问 题由于该问题是n p 困难的，我们考虑其近似算法的设计与分析论文有如下 两部分内容t 第一部分研究带惩罚的动态设施选址问题在该问题中给定若干时段，不同 时段内设施的开放费用、用户的需求及连接费用不一定相同，而且允许用户的需 求不被满足，但不满足的部分要有惩罚利用原始对偶技巧，我们给出了该问题 的3 一近似算法再运行贪婪增加程序后，近似比改进到1 8 5 2 6 第二部分研究软容量约束的动态设施选址问题在该问题中每一个设施都是 有软容量限制的利用拉格朗日松弛技巧，我们给出了该问题的6 一近似算法 运行贪婪增加程序后，近似比改进到3 7 0 5 2 关键词动态设施选址问题；近似算法；线性规划；原始对偶算法 i 北京工业大学理学硕士学位论文 a b s t r a c t i nt h i st h e s i s ，w ec o n s i d e rt h ed y n a m i cf a c i l i t yl o c a t i o np r o b l e mw i t hp e n a l t i e s a n dt h es o f t c a p a c i t a t e dd y n a m i cf a c i l i t yl o c a t i o np r o b l e m s i n c et h e s ep r o b l e m s a r en p h a r d ，w ec o n s i d e rt h ed e s i g na n da n a l y s i so ft h ea p p r o x i m a t i o na l g o r i t h m f o rt h ep r o b l e m s t h i st h e s i sc o n s i s t so ft h ef o l l o w i n gt w op a r t s ： i nt h ef i r s tp a r t ，w es t u d yt h ed y n a m i cf a c i l i t yl o c a t i o nw i t hp e n a l t i e s i nt h i s p r o b l e m ，w ea s s u m et h a tt h ef a c i l i t yc o s t ，t h es e r v i c ec o s t ，t h ed e m a n da n dt h e p e n a l t yo fe a c hc l i e n tm a yb ed i f f e r e n ta te a c ht i m ep e r i o d a te a c ht i m ep e r i o d ， ac l i e n tc a nb es e r v e db ya i lo p e n e df a c i l i t yo rr e j e c t e db yp a y i n gap e n a l t y u s i n g p r i m a l d u a lm e t h o d ，w eo b t a i na3 - a p p r o x i m a t i o na l g o r i t h m w e f u r t h e ri m p r o v e t h ea p p r o x i m a t i o nr a t i o nt o1 8 5 2 6u s i n gg r e e d ya u g m e n t a t i o ns c h e m e i nt h es e c o n dp a r t ，w es t u d yt h es o f t c a p a c i t a t e dd y n a m i cf a c i l i t yl o c a t i o n p r o b l e m i nt h i sp r o b l e m ，w ea s s u m et h a te a c hf a c i l i t yh a sas o f tc a p a c i t y u s - i n gl a g r a n g er e l a x a t i o nt e c h n i q u e ，w eo b t a i na6 - a p p r o x i m a t i o na l g o r i t h m w e f u r t h e ri m p r o v et h ea p p r o x i m a t i o nr a t i o nt o3 7 0 5 2u s i n gg r e e d ya u g m e n t a t i o n s c h e m e k e y w o r d sd y n a m i cf a c i l i t yl o c a t i o np r o b l e m ；a p p r o x i m a t i o na l g o r i t h m ；l i n e a r p r o g r a m m i n g ；p r i m a l - d u a lm e t h o d i i i 目录 目录 摘要一i a b s t r a c t i i 第1 章绪论1 1 1 研究背景1 1 2 问题介绍1 1 3 国内外研究现状6 1 4 主要结果8 1 5 论文结构8 第2 章带惩罚的动态设施选址问题9 2 1 d f l p w p 的原始对偶算法9 2 2 原始对偶算法的理论分析1 3 2 3 改进的算法及其分析1 5 2 4 本章小结1 8 第3 章软容量约束的动态设施选址问题1 9 3 1 算法2 1 3 2 算法分析2 2 3 3 改进的算法及其分析2 5 3 4 本章小结2 8 结论2 9 北京工业大学理学硕士学位论文 参考文献一3 1 攻读硕士学位期间发表的学术论文一3 7 致谢3 9 1 一 - 第1 章绪论 i i 研究背景 第1 章绪论 在科技的迅速发展的今天，作为一门数学学科的“最优化”在各行各业占有 非同寻常的重要地位( 【1 ) 最优化问题可以简单的表述为：在给定条件下求一函 数的极值最优化是一门应用相当广泛的学科，它讨论决策问题的最佳选择之特 性，构造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际计算表现 伴随着计算机的高速发展和优化计算方法的进步，规模越来越大的优化问题得到 解决因为最优化问题广泛见于经济计划、工程设计、生产管理、交通运输、国 防等重要领域，它已受到政府部门、科研机构和产业部门的高度重视 设施选址问题是一个典型的组合优化问题，在制造业、运输业、网络、信息、 资源配置等领域都有广泛而重要的应用( 2 ，5 ，1 8 】) 一般而言，某一设施一旦修 建要服务很长时间，但影响选址的因素是变化的，所以就产生了动态设施选址问 题( d y n a m i cf a c i l i t yl o c a t i o np r o b l e m ( d f l p ) ) 我们所要研究的就是该问题及其 变形 1 2 问题介绍 最经典的设施选址问题是无容量约束设施选址问题( u n c a p a c i t a t e df a c i l i t y l o c a t i o np r o b l e m ( u f l p ) ) ：给定设施集合f ，用户集合d 表示开放f 中设施 i 的费用； q j 表示连接i 与d 中用户j 的费用目标是开放f 的子集q 使得 任意用户都有开放的设施为其提供服务，并且总费用( 连接费用与开放费用之和) 北京工业大学理学硕士学位论文 最小我们假定是可度量的，即满足非负性0 ，对称性= ，和三角 不等式q 知+ c k j ，y i ，j ，k duf 我们可以将这一问题写成如下的线性整 数规划： m i n c t j x i j + 五玑 i e f j e d i e f s t x q 1 ，坳d l f z 订玑， y i 只j d z 巧，y i o ，1 ) ，y i f j d ( i - i ) 其中y i 表示设施是否开放，若是，则玑= 1 ，否则，y i = 0 x i j 表示设施i 是否 为用户j 提供服务，若足，则x i j = 1 ，否则，= o 在无容量约束设施选址问题中，有些用户与其他用户的距离可能非常远，它 们对解的影响很大，我们可以忽略这些用户，也就是不一定满足全部用户的需求， 但不满足的部分用户要接受惩罚这就是带惩罚的设施选址问题( f a c i l i t yl o c a t i o n p r o b l e mw i t hp e n a l t i e s ( f l p w p ) ) 任给j d ，d j 表示用户歹的需求，功表示 用户j 没有被服务的惩罚费用每一个用户可以决定接受服务或惩罚这个问题 可以表述为： s t x i j + 勺1 ，d ( 1 - 2 ) t f y i ，只歹d x i j ，y i ，乃 o ，1 ) ， y f ，j d ( 1 - 1 ) 与( 1 - 2 ) 的主要区别在于增加了惩罚项扔，当所有的功= 0 0 时， f l p w p 1 - 严 - - 、 第1 章绪论 退化为u f l p 实际中由于条件的变化，可能会使开放费用和连接费用随时间的变化而变 化，将时间离散化就得到应用更广泛的动态设施选址问题( d y n a m i cf a c i l i t yl o c a - t i o np r o b l e m ( d f l p ) ) ，我们可以用如下的线性整数规划表述这一问题： t丁t 曙+ 片孵 t = li e fs = lj ds = li e f t s t z 豸1 ，d ，1 tst s = lt f z 髫酣，v i f , j d ，1 s ，t t z 嚣，鳝 o ，1 ) ，v f , j d ，1 s ，t t ( 1 - 3 ) ( 1 - 3 ) 与( 1 - 1 ) 的不同点在于开放费用和连接费用都是与时间有关的当t = 1 时，d f l p 退化为u f l p 本文要研究的一类问题是带惩罚的动态设施选址问题( d y n a m i cf a c i l i t yl o - c a t i o np r o b l e mw i t hp e n a l t i e s ( d f l p w p ) ) ：给定设施集合f ，用户集合d ，及时间 t ，对于任意j d ，在t ( 1 t t ) 时刻j 有需求，只有在t 时刻或之前开放 的设施能为其提供服务任意i f ，疗表示在s 时刻开放设施i 的费用，其中 s ：1 s t 如果在8 时刻不允许开放i ，则疗= 。彰表示8 时刻的设施i 为 t 时刻的用户j 每提供一个单位的服务的连接费用，如果t o ，磅 0 ，就称( i ，s ) 与( i 7 ，s 7 ) 相关选择g 的极大独立子集g 7 ，并 且满足对任意( i ，s ) g c 7 ，都存在( i ，s ) g 其中s s ，使得( i ，s ) ，( i 7 ，s 7 ) 是 相关的开放g 7 中的设施，对处于临时休息的0 ，t ) ，若它没有直接连接到某个开 放的设施上，则选其作为接受惩罚的集合，记为q ，其他的用户连接到最近开放 的设施上 从算法2 1 1 的第一阶段可以知道算法产生的解( 嘭，鳄) 是对偶可行解在 算法2 1 1 的第二阶段中，由于g 7 是极大独立子集，则对任意( i ，8 ) a a ，一 定存在( i 7 ，8 7 ) g 7 ，s 7 s ，使得( i ，8 ) 与( i 7 ，s ) 相关令e ( i ，s ) 表示( i ，s ) 临时开 放的时刻在下面的算法具体实现过程中，g 表示临时开放的设施集合，g 表 示没有临时开放的设旌集合，则gug = ( i ，s ) ：i 只1 s t ) ，g ，表示最终 开放的设施集合，d 表示冻结的用户集合，西表示没有冻结的用户集合，国表 北京工业大学理学硕士学位论文 示临时休息的用户集合，q 表示最终接受惩罚的用户集合 算法2 1 2 步0( 初始化) 置g ：= d ，台：= ( ts ) ：i f 1 s t ) ，g 7 ：= d ，d ：= 仍， 西：= ( j ，t ) ：j d ，1st t ) ，国：= 0 ；噶：= 0 ，鳄：= 0 ，v ( i ，s ) 0 ，( 歹，) 西 步1 v ( i ，8 ) g ，求解关于伊的方程嘭m a x 口一嘭，o ) + 孵鳄= 0 ，0 e d0 ，o e d u q 疗，记其根为e ( i ，s ) 步2记护(i，吾)；(嚣in口(i，s)，s*jt_2托舞嗜，毒车缸minp虿js)eg s ) e gt ) e dt ) 6 d 。 刀： 一 ( t ， 。 ( ，0 ， 。 d ； 0 ， o ； 口i 。 步3 计算m i n 8 ( 7 ，可) ，c 搿：， 若p ( i ，吾) 最小，则( i ，动临时开放记砾，动：= 0 ，t ) d ：口( i ，动一彰o ) 置g ：= g u ( i ，吾) ，0 ：= 台 ( - ，吾) ，d ：= d u 砾，功，b ：= d 砾，功；呓：= p ( i ，写) ， p 孑：= m a x o ( i ，吾) 一c 豸，o ) ，v ( i ，s ) 0 u ( i ，吾) ) ，( 歹，t ) k ，动转步4 若善最小，则对应的( j ，刁为临时休息的用户置国：= 国u ( j ，动) ，b ：= 吁 ，； 眦 碱：= 鬟，喏：= 叫鬟一和s ) 葩转步4 若审；：最小，则冻结( j ，t 。) 并将其与( i + ，s 4 ) 连接置d ：= du ( 歹+ ，t + ) ) ， 西：= 西 ( 歹+ ，扩) ) ；嘭：= c 窍：，晦：= m a x c 搿：一嘭：，o 】，v ( i ，s ) 台转步4 如果有两个或三个数同时为最小，则任意选取其中一个执行上面的步骤 步4 若西= d ，转步5 ，否则转步1 步5将临时开放的设施集合g 中的元素按时刻蚕由小到大排列( 若蚕相 同，则按任意顺序排列) ，排序结果为 ( _ l ，吾1 ) ，函，而) ，& ，氟) ) ，其中吾l 而 孔，h = l a l 置k ：= 1 ，记砾舻。) ：= ( 歹，t ) ：喏 o ) ，g 7 ：= g ，u 匦，乳) 将所有0 ，t ) 瓴，氟) 连接到( 五，靠) 上 1 2 第2 章带惩罚的动态设施选址问题 步6 置七：= 七十1 ，m ，：= t c j ：喏 。，若( 6 ，裂m 和，) n 概，靠) d ，转步7 否则，置g 7 ：= g 7 u ( 该，氟) ) ，将所有( 歹，) g a 。，靠) 连接到 ( 瓦，靠) 上 步7 若k = h ，转步8 ，否则转步6 步8 记。= 浊口) 置肛卯，q 为最终接受惩罚的用户集 合- 对于任意用户o ，。) 聋duq ，记c 影：2 ( 器黔， 噶) ，将( 歹，) 连接到( ，矿) 上算法停止 2 2 原始对偶算法的理论分析 下面我们给出算法2 1 1 的理论分析记 d 7 = ( j ，t ) ：j d ，1 t t ，0 ，t ) 聋q ，存在( i ，s ) g 7 ，使得鳄 o ) 由于g 7 是g 的极大独立子集，所以对任意0 ，t ) d 7 ，存在唯一的( ，s i t ) g ， 使得瞄 0 我们将算法找到的原问题的整数可行解的总费用分为三部分， f 表示开放设施的费用，c 表示连接费用，p 表示惩罚费用用o p t 表示原问 题( 1 4 ) 的最优值 定理2 2 1 算法2 1 1 是d f l p w p 的3 一近似算法 证明我们从惩罚费用，开放费用，连接费用三部分来估计算法2 1 1 产生的解的 总费用 1 估算惩罚费用 一1 3 - 所以 北京工业大学理学硕士学位论文 由算法2 1 知，若( 歹，t ) q ，则有够嘭= 巧所以 2 估计开放设施的费用 对于任意( i ，s ) g ，有 砖= 嘭q 5 0 ，t ) e q0 ，t ) e q 劈= 弓鳄 = 弓鳄 = 弓蟛 3 给出所有( j ，t ) 隹q 的连接费用的估计 分两种情形考虑； 情形3 1 ( 歹，t ) d 7 根据d 7 的定义，存在唯一的( 锄，s i t ) g 7 ，使得 q 厅s i 坩t t 0 ，这时我们将( 歹，t ) 连接到( i j t , s 豇) 上我们有c 荔+ 嘲= q j t 情形3 2 ( j ，t ) 萑d 7 我们考虑在算法2 1 1 第一阶段中( 歹，t ) 第一次连接上 的已经开放的设施( i ，s ) ，则有嗜a j t ，e ( i ，s ) 呓根据( i ，s ) 再分两种情形分 析 情形3 2 1 ( i ，s ) g 7 这时将( j ，t ) 连接到( i ，s ) 上，我们有嗜a ； 情形3 2 2 ( i ，s ) 隹g 7 从算法2 1 第二阶段知，存在( i 7 ，s 7 ) g i ，使得 ( i ，s ) 与( i 7 ，s 7 ) 是相关的而且s s 我们将( j ，t ) 连接到( t ，s ) 上这时存在 一1 乒 鳄 弓 徊 r 脚 = 搿 第2 章带惩罚的动态设施选址问题 ( 歹7 ，t ，) 使得硝 0 ，膨 0 所以，c 嚣：s ，彩：又a 多p ( t ，s ) ， 1 s s t ，t 7 t ，由弱三角不等式得， 吃c s 。t t 四多+ 豸：+ 曙 s2 4 + 2 0 ( i ，s ) + c 嚣3 4 综合情形3 2 1 3 2 2 ，- - f 知0 ，t ) 隹d 7 时，( j ，t ) 的连接费用不会超过3 嘭嘭 注意到q 与d 是不交的，综合上面3 种情形，我们估计算法2 1 1 产生的 解的总费用如下 cj 广f + psc - 4 - 3 f - 4 - 3 p 3 + s j 。t j t + 3 碰3 一? j r 。3 j + 3 4 0 l ； s 3 呓苗+ 3 ( s j 。t j t + 唧l ? $ j t ，t ) + 3 弓q ； 0 ，t ) 甓q u d 7 0 ，t ) e d ， 0 ，t ) e q r =3f f a ；3 0 p t 1 - j jo 2 3 改进的算法及其分析 口 c h a r i k e r 和g u h a 7 】对于u f l p 提出了贪婪增加程序，并用初始解和任意解 的费用可以估计运行贪婪增加程序后得到的解的费用对于d f l p w p 也有类似 的结果( 【3 5 ) 引理2 3 1 【7 ，3 5 】设j 是d f l p w p 的任意实例， s o l 是，的任意解，对应的 1 5 - 北京工业大学理学硕士学位论文 开设费用为f s o l ，连接费用为c s o l ，惩罚费用为p s o l 给定开设费用为f ，连接 费用为c ，惩罚费用为p 的初始解，经过贪婪增加程序后得到的解的总费用至多 为 f + m a x 0 ，h ( 型等堡) ) + 毋+ 二+ 设占 0 是下面算法用到的参数 算法2 3 1 1 将开设费用都乘以6 后运行原始对偶算法得到d f l p w p 的解s o l l 2 用s o l l 作为初始解运行贪婪增加程序 口 我们记算法2 3 1 得到的解为s o l 2 令p ，p ，驴分别为o p t 中对应的 总的开放设施的费用，连接费用和惩罚费用设s o l 为d f l p w p 的任一解，我 们用c o s t ( s 0 1 ) 表示该解的总费用类似于 2 6 ，3 5 】对u f l p 和f l p w p 的讨论 我们有， 定理2 3 2 取6 = 0 7 1 9 2 ，则算法2 3 1 是d f l p w p 的1 8 5 2 6 一近似算法 证明由定理2 2 1 的证明过程可以知道 3 5 f s o l l + c s o l l + 3 p s o l l 3 ( 5 f + c + + p + ) ( 2 1 0 ) 我们分两种情形讨论 情形1 c s o l l + p s o l l f + + c + + p + 一1 6 - 第2 章带惩罚的动态设施选址问题 由( 2 - i 0 ) 得到 c s o l z - j r - f 裔。l 。+ j l s 。l ，兰鱼! = ! 坚三兰l 三二! ；i ；出+ ( 1 一去) ( c 冶。l ，+ j ) s 。l 。) 型堕! 二土3 1 6 婴+ ( 1 一三3 6 ) ( f + c + p + ) 一 。，r 。一7 = ( 2 一刍) f 。+ ( ，+ 丢) c p + c ， 由于贪婪增加程序不会增加解的费用，我们有 8 t c s 。l z ，m a x f + + c + + p 由( 2 1 0 ) 得 c s o l l + p s o l l 3 ( ( i f + c + + p + ) 一3 6 f s o l l 由引理2 3 1 和上式我们有 c o s t ( s ) b 。时f h ( b 。l 。+ ph ( 一csolz+-psol,-c*-p*、+f+c+p f 一 一 3 6 f + 2 c + + 2 p + 一3 6 f s o l l f ) + f + + c + p + 当砖。l ，= 丢( 驴+ p ) 时，上式有最大值 c l + h c 3 6 ，f + + ( ，+ 品) c p + + ，m a x o 。f l 叼s , t 0 ，就称 ( i ，8 ) 与( i 7 ，s 7 ) 相关选择g 的极大独立子集g 7 ，并且满足对任意( i ，8 ) g g 7 ， 都存在( i 7 ，8 7 ) g 其中s 7 8 ，使得( i ，s ) ，( i ，s 7 ) 是相关的开放g 7 中的设施， 将用户对( j ，t ) 连接到最近开放的设施上得到( 3 - 1 5 ) 的一组可行解( x ，y ) 从算法3 1 的第一步可以知道算法产生的解( a ；，鳄) 是对偶可行解在算法 3 i 的第二步中，由于g ，是极大独立子集，则对任意( i ，8 ) g g ，一定存在 ( i 7 ，s 7 ) g 7 ，s 7 8 ，使得( i ，s ) 与( i ，s 7 ) 相关 第三步构造( 1 - 6 ) 的整数可行解 令弼= 礴霹= 陲岳霉u i 3 2 算法分析 记 下面我们给出算法3 i 1 的理论分析令e ( i ，s ) 表示( i ，8 ) 临时开放的时刻， d 7 = ( 歹，t ) ：j d ，1 t t ，存在( i ，s ) g 7 ，使得鳄 o ) 由于g 7 是g 的极大独立子集，所以对任意( j ，t ) d 7 ，存在唯一的( 味，s i t ) g ， 使得， 7 矧s j t t 0 我们将算法找到的( 3 1 5 ) 的整数可行解的总费用分为两部分，f 表示开放设施的费用，c 表示连接费用用o p t 表示原问题( 整数规划1 _ 6 ) 的 最优值 t 引理3 2 1 s c d f l p 的任一解的总费用至少为嘭 2 2 第3 章软容量约束的动态设施选址问题 t 证明因为a ；不超过( 3 - 1 5 ) 的任一解的总费用，也即 t - - - - 1j d 而 则有 引理3 2 2 1 3 9 岛= d 2 d i = p 1 o p t ， 证明我们分两步来估计算法3 1 1 产生的解( 文，矿) 的总费用 所以 1 首先我们来估计开放设施的费用f 对于任意( i ，8 ) g ，有 耳= 鳄 = 鳄- 0 j 。j = q s j t tj 【j 2 其次我们给出连接费用c 的估计 分两种情形考虑t 一2 3 - 口 b 一 嘭 徊 丁脚 rpd 0 ，蹦 0 所以，皤s ，q 多o l j f p 又嘭p ( i ，s ) ， 1 s 7 ss ，t 7 t ，由弱三角不等式得， 。c i s ，7 t 。c 巧i 8 e ，+ c 黟+ c 学2 + c 孑2 0 ( i ，s ) + c 豸3 噶 综合情形2 2 1 和2 2 2 ，可知( 歹，t ) 圣d 7 时， ( 歹，) 的连接费用不会超过3 呓 综合上面2 种情形，我们估计算法3 1 1 产生的解的总费用如下 g+fc+3f 3 t + 喵+ 3 麟呓 ( j ，) 隹d 70 ，t ) e d 7u ，t ) e d 7 3 a ；+ 3 ( 咧+ 麟) 0 ，t ) 隹d ，a ，f ) d 7 t ：3f f q 0 t - - - - 1j e d 口 trtt 定理3 2 3 嘭喏+ 疗黝y is6 呓，因此算法3 1 1 是 f = li e fs = l j 6 d 。s = 1i e ft = 1j d s c d f l p 的6 一近似算法 2 垂 第3 章 软容量约束的动态设施选址问题 证明由算法产生的解( 戈，矿) 以及( z ，刃的构造过程知 因此 则有 贸 ?t t = li e fs = lj e d tt f f 厶一厶一 t = lj e d x 嚣，移8 百p 弼+ 8 = 1 t e s t a 巧s t + t = li 6 fs = lj e d8 = 1i e f i 2 j d x 蔷i 飞七 t t 薹( 喏+ 翕) 霹+ ；t 善譬霉8 t = lt fs = lj d _ w l o = 1i f t = t - - - - 1t f t = lt fs = lj e d s = l f ft tt 2 ( 鳄瑶+ it = li 6 fs = lj e ds = l t 6 t t = lj 6 d 3 3 改进的算法及其分析 ；鬣 霉s ) ( 3 1 6 ) 口 c h a r i k e r 和g u h a 7 对于u f l p 提出了贪婪增加程序，并用初始解和任意解 2 5 露 疗虿 触 t 埘 野醪 触 耐 + 砑四 触 蹦 嘭 触 t 埘 3 0 是下面算法用到的参数 算法3 3 1 1 将开设费用都乘以6 后运行原始对偶算法得到d f l p 的解s o l l 2 用s o l l 作为初始解运行贪婪增加程序，记此组解为s o l 2 相应的分量 为x ，y 3 锅= 霹萨- i t 墨= l j e d 卦u i 我们令f ，c 分别为恳中对应的总的开放设施的费用和连接费用设s o f 为d f l p 的任一解，我们用c o s t ( s 0 1 ) 表示该解的总费用下面我们给出算法3 3 1 的理论分析其证明实质上由【2 6 ，3 5 在讨论u f l p 和f l p w p 时给出，为了完 整起见，我们给出证明 引理3 3 2 1 3 9 取6 = 0 7 1 9 2 ，则c o s t ( s o l 2 ) 1 s 5 2 6 p 2 证明由引理3 2 2 的证明过程可以知道 3 ( 5 f s o l l + c s o l l 3 ( 6 f + c + ) ( 3 1 7 ) 一2 6 第3 章软容量约束的动态设施选址问题 我们分两种情形讨论 情形1 c s o l l f + c + 由( 3 - 1 7 ) 得到 o l i + b 。l 。= 3 5 f s o l r i + c s o l l 十 3 ( 5 f + + c + 1 3 5 ( 2 一击) f + 由于贪婪增加程序不会增加解的费用，我们有 ( 1 一去) c 。， ( f + + e ) c c 。s t ( s o l 2 ) f + + c 4 由( 3 - 1 7 ) 得 c s o l l 3 ( 5 f + c ) 一3 5 f s o l ， 由引理3 3 1 和上式我们有 c 。s t ( s o l 2 ) s f s o l i + f * i n ( 罕) + f + c f s o l ，+ f * i n 3 5 f * + 2 c * - 3 5 f s o l i ) + f + c 当艮。l ，= 丢伊时，上式有最大值 c ，+ h c 3 6 ，f + ( 1 + 丢) c * m a x + h c 3 回，1 + 委) c f + c + ， 综合上面两种情形有 c o s t c s 。l 。，m a x 1 + - n c 3 n1 + 委，2 一去) b 2 7 - )0 r一筋，2一筋 一 + 1 ，几 卜 + 北京工业大学理学硕士学位论文 取6 = 0 7 1 9 2 ，我们得到c o s t ( s o l 2 ) 1 8 5 2 6 p 2 定理3 3 3 算法3 3 1 算足s c d f l p 的3 7 0 5 2 - 近似算法 t t 1 8 5 2 6 p 2 t 四胃+ j e d s = li e f 3 4 本章小结 f 翠； + 劈砑s3 7 0 5 2 p 2 3 7 0 5 2 0 p t 或8 ) 口 口 本章关键是利用y e 和z h a n g 3 9 ，j a i n 和v a z i r a n i ( 2 0 ) 以及l i 和x u 【2 4 】 的算法技巧，设计了软容量约束的动态设施选址问题的第一个组合近似算法给 出了第一个近似比6 ，并应用 7 ，1 6 ，2 6 ，3 9 的相关技巧，再次运行本算法，将近 似比改进到3 7 0 5 2 一2 8 - d 触 斟 结论 结论 本论文主要研究了两类推广的动态设施选址问题，此问题在制造业、运输业、 网络、信息、资源配置等现代化的诸多领域都有广泛而重要的应用，是一类具有 重要研究价值的问题由于该问题是n p 困难的，本文考虑其近似算法的设计与 分析在论文中，介绍了带惩罚的动态设施选址问题和软容量约束的动态设施选 址问题 关于带惩罚的动态设施选址问题的算法，主要是利用j a i n 和v a z i r a n i ( 2 0 ) 的u f l p 的算法，y e 和z h a n g ( 3 9 ) 的d f l p 的算法及c h a r i k a r 等( 8 ) 的 f l p w p 的算法设计了带惩罚的动态设施选址问题的原始对偶算法我们的算法 首先构造对偶问题的可行解，然后再根据对偶可行解设法找到原问题的整数可行 解并证明近似比为3 进一步采用贪婪、缩放等技巧( 2 6 ，3 5 ，7 ) ，将近似比改进到 1 8 5 2 6 对软容量约束的动态设施选址问题，参考l i 和x u ( 2 4 ) 及j a i n 和v a z i r a n i ( 2 0 ) 的算法技巧，本文首先将软容量约束的动态设施选址问题转化为动态设施 选址问题，调用y e 和z h a n g ( 3 9 ) d f l p 算法，得到动态设施选址问题的可行解， 最后利用这一可行解构造软容量约束的动态设施选址问题的整数可行解对此问 题我们给出了第一个近似比为6 的原始对偶( 组合) 算法，然后采用贪婪、缩放等 技巧( ( 2 6 ，7 ，3 9 】) 将近似比改进到3 7 0 5 2 待研究的问题本文对带惩罚的动态设施选址问题设计了第一个近似比为 1 8 5 2 6 的组合算法u f l p 的下界为1 4 6 3 ，而u f l p 为d f l p w p 的特例，所以 1 4 6 3 也是d f l p w p 的下界目前u f l p 的最好近似比为b y r k a 和a a r d a l ( 4 ) 一2 9 - 北京工业大学理学硕士学位论文 的1 5 0 ，因此d f l p w p 的近似比还有改进的空间同样我们给出了软容量约束 的动态设施选址问题的算法，近似比为3 7 5 0 2 d f l p 目前最好的近似比为y e 和 z h a n g ( 3 9 ) 的1 8 5 2 6 ，而这两个问题是包含关系，是否能给出关于软容量约束的 动态设施选址问题比1 8 5 2 6 大的下界也是非常有意义的问题 参考文献 参考文献 1 胡适耕，施保昌，最优化原理，华中科技大学出版社，2 0 0 0 ：1 - 3 2k a n d r e e v ，b m m a g g s ，a m e y e r s o n ，a n dr k s i t a r a m a n ，d e s i g n i n go v e r - l a r ym u l t i c a s tn