（运筹学与控制论专业论文）带惩罚的有下界约束设施选址问题.pdf

iiijilij i ll ll l ll r lllli 17 8 8 9 9 2 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他入已经发表和撰写过的研究成果，也不包含为获 得北京工业大学或其他教育机构的学位或证书而使用过的材料，与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意 鹳娲醐： 辫修 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文 ( 保密的论文在解密后应遵守此规定) 懿。漱够劓程各 摘要 摘要 本论文考虑带惩罚的有下界约束设施选址问题在该问题中，每个 开放的设施有下界j e 7 约束，即服务的客户数目要求不少于b 个，而且 客户可以不被服务但有惩罚费用特别的，当b = 0 且每个客户的惩罚 费用足够大时，该问题就退化为标准的设施选址问题 对于带惩罚的有下界约束无容量设施选址问题，我们利用化归技巧 给出双准则算法，得到的解满足下界约束c z b ( 1 3 口 1 ) ，解的费用不 超过最优值的五1 - i - 。倍，其中p 为带惩罚的无容量设施选址问题目前最 好的近似比我们还考虑了上述问题的软容量情形我们利用拉格朗日 松弛技巧给出双准则算法，得到的解满足下界约束a b ( 1 3 口 1 ) ，解 的费用不超过最优值的2 而l + a p 倍 关键词设施选址问题；近似算法；双准则算法 北京工业大学理学硕士学位论文 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 el o w e r - b o u n d e df a c i l i t yl o c a t i o np r o b l e mw i t h p e n a l t i e s ( l b f l w p ) w h e nb = 0 a n da l lp e n a l t i e sa x el a r g ee n o u g h ，t h ep r o b l e m i sr e d u c e dt ot h es t a n d a r df a c i l i t yl o c a t i o np r o b l e m u s i n gr e d u c t i o nt e c h n i q u e ，w eg i v ea b i c r i t e r i aa l g o r i t h mf o rt h el o w e r - b o u n d e d u n c a p a c i t a t e df 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 t h eb i c r i t e r i aa l g o r i t h m p r o d u c e sas o l u t i o nw h i c hv i o l a t e st h el o w e rb o u n dc o n s t r a i n t sb y 口s ( i 3 o t 1 ) ，b u tw i t h i n 鲁po ft h eo p t i m a ls o l u t i o nc o s t ，w h e r epi st h eb e s ta p p r o x i m a t i o n r a t i of o rt h ef 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 w ea l s oc o n s i d e rt h es o f t - c a p a c i t a t e dv e r s i o no ft h ea b o v ep r o b l e m 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 eg i v eab i c r i t e r i aa l g o r i t h mw h i c hp r o d u c e sas o l u t i o nv i o l a t e dt h el o w e rb o u n d c o n s t r a i n t sb yq b ( 1 3 q 0 或= ，则边( i ，j ) 被称 为是好边，否则就是坏边如果ez , j d j = ，则备选地址i 被称为是好 j 点考虑只包含好边的二分图k ，构造一个图g = ( j ，e ) ，其中，是好点 的集合，e 是图k 中一些边的集合，那些边的两点之间存在长度不超 过2 的路径 第二阶段：构造出上面所说的图g = ( j ，e ) ，同时求出它的最大独立 集开放那些被选进最大独立集的备选地址，那些与开放的备选地址通 过好边被服务的客户j 保持被服务，其他的客户j 表示不由任何设施服 务，被惩罚 贪婪增广算法：对每个未开放的设施i ，9 i 表示开放这个设施所节省 的费用，计算譬，开放那个比值最大且正的设施，同时离它更近的客户 由它服务( 取消原来的服务方式) ，不断执行这个步骤，直到不再存在使 得比值为正且未开放的设施至此，关于他们的算法介绍结束 h a y r a p e t y a n 等【17 】首先提出惩罚函数为次模函数的无容量设施选 址问题( f l p s p ) 如果函数儿) 定义在有限集y 上，且满足，u y ) + f ( x ny ) f ( x ) + ，( y ) ，x ，y v 则称函数，( ) 是次模函数如果函数 满足当x y 时，有f ( x ) f w ) ，则称函数九) 是单调递增的通过假 设惩罚函数是定义在客户集d 上单调递增的次模函数，他们提出了近 似比为( 1 + 7 ) 近似算法，其中7 是无容量选址问题的近似比，而目前无 北京工业大学理学硕士学位论文 容量选址问题最好的近似比是1 5 0 ，所以他们得到算法的近似比是2 5 0 但是，他们的算法不是组合算法，而是利用椭球算法解一个含有指数个 变量的整数规划的线性松弛后来，c h u d a k 和n a g a n o 9 提出了一个更 有效的算法( 不是组合算法) ，近似比是( 1 + ) ( 1 + 7 ) 他们的算法基于松 弛f l p s p 的一个等价的紧凸集，再利用非光滑凸优化的技术解决最 近，d u 等【1 3 】通过原始对偶技术得到一个3 近似比的组合算法 3 有下界约束的无容量设施选址问题( l b f l ) 有下界约束的无容量设施选址问题与无容量设施选址问题不同的 地方是每个设施如果开放则必须至少服务j e i 个客户，否则就不能被开 放，我们用如下线性整数规划来描述： r a i n + 玑 诞f ，j e d i e f 8 t x i j = 1 ，坳d t f z 玎一y is0 ，只j d( 1 ) x q b y t ，v i f j e d z 巧 o ，1 ) ，v i 只j d y i o ，1 ) ，v i d 其中x i j ，y i 是0 1 整数变量，表示客户j d 是否由设施i f 服 务，y i 表示设施i f 是否开放第一个约束表示每个客户由设施提供 服务，第二个约束表示客户只能由开放的设施提供服务，第三个约束表 示每个设施如果开放则必须有至少b 个客户由它提供服务，否则就不 能被开放 6 第1 章绪论 有下界约束的无容量设施选址问题分别由k a r g e r 和m i n k o f f 2 1 】和 g u h a 等【1 5 在解决网络设计问题时独立提出他们都给出了双准则算 法( b i c r i t e r i aa l g o r i t h m ) 来解决这个问题双准则算法通过对设施开放费 用进行重新定义，构建出一个无容量选址问题，用近似算法解决这个 无容量选址问题后，在实现总费用增加有限的基础上通过不断调整， 使得每个设施至少服务a b ( o 口 1 ) 个客户双准则算法( b i c r i t e r i a a l g o r i t h m ) 虽然给出了一个解不超过最优解的p 倍，但这个解是引进了 一个常数因子a ，使得每个设施至少服务a b 个客户，违反了原问题要 求每个开放设施必须至少服务b 个设施的约束，不一定是不可行解 最近，s v i t k i n a 3 4 】提出了关于这个问题的第一个真正意义上的常数 近似比算法下面我们分三个阶段具体描述一下这个算法 第一阶段：( 双准则算法) 构建如下规划： r a i n 踟+ c i j x i j i e f i e fj e d s 8 t = 1 ，v j d i 6 f z o 一轨0 ，ej d( 2 ) z 巧 o ，1 ) ，v i 只j d 玑【o ，1 ) ，v i d 这里= ，+ a ，其中a = 瓮，a ( ；，1 ) ，d ( i ) 表示离设施i 最近的 j e d ( i ) b 个客户此时，问题( 1 ) 中的下界约束没有出现在问题( 2 ) 中 1 用无容量设施选址问题中目前最好的近似算法解决这个问题， 北京工业大学理学硕士学位论文 同时保证每个客户都由离它最近的开放设施提供服务 2 以任意的顺序，关闭上面解中服务客户数小于b 的开放设施，而 那些原本由它提供服务的客户都由离各自最近的开放设施提供服务不 断重复这个过程，直至剩下的每个开放的设施都至少服务a b 个客户 第二阶段：( 构造有容量设施选址问题) 1 构建一个l b f l 的实例，：用i ( 歹) 表示第一阶段中给j 提供服务 的开放设施i 这个实例中的客户的集合，设施的集合和b 都和原问题 一样，但服务费用的定义修改如下：喙= q ；c a ，- 龟u ，) 1 ，= c “，；同 时在第一阶段中已经被开放的设施的开放费用现在定义为零，而还没 开放的设施开放费用和原来一样 2 再构建一个实例。：这个实例与实例。唯一的区别就是设施集 合改变了，这里的设施集合r 定义为所有在第一阶段后开放的设施 3 再构建一个实例。：对于r 中的开放设施i ，如果它服务客户数 为啦且m b ，则在那里建造一个供应量为b 的供应点，建造费用为 6 n d 其中j 为一个待定的常数，也表示i 与见中最近的设施间的距 离，同时在那里建造一个需求量为b 一毗的需求点；如果它服务客户数 为毗且m b ，则在那里建造两个供应点，不建需求点一个供应点的 供应量为b ，建造费用为5 b d i ，另外一个供应点的供应量为b 一建造 费用为零这个实例是一个有容量约束设施选址问题( c f l ) ，接下来用 z h a n g 等【4 4 的近似算法解决这个问题 第三阶段：( 构造树形图进行调整) 8 第1 章绪论 首先按照第二阶段算法实行后要求的那样，给各个设施和客户进行 重新调整因为这个特殊的有容量约束设施选址问题( c f l ) 只要求每个 需求点的需求量被满足，而并不要求被选中的每个供应点的供应量变 无，所以经过重新调整后剩下两类设施第一类设施记为a ，a r ，a 中的所有设施都至少服务b 个客户；第二类设施记为s ，s = f a ，s 中的所有设施服务的客户数少于b 对于a 中的设施只需开放，并使它服务相应的客户，满足原问题的 下界要求 对于s 中的设施，我们通过以下措施来解决构造一个有向图g ， g 中的顶点由r 中的所有设施构成下面构造有向边：对每一个i 昂， 在r 中找出离它最近的设施i 7 ，这时就构造一条有向边( i ，i ，) ，方向从i 指向i 最终，有向图g 会由以下两类树构成：第一类树的根在a 中，该 类树的其它所有边都指向根；第二类树有且只有一条重边，该类树的其 它所有边都指向这条重边 对于第一类树中的每个设施，如果它至少服务b 个客户，则开放 这个设施，并移除从它那里指向父一代的边；如果它服务的客户数少于 b 个，则把它服务的客户都调整到它指向的那个设施对于第二类树中 的每个设施，采取的措施唯一不同于第一类树的就是对构成重边的那两 个设施的处理如果两个设施都至少服务b 个客户，则两个设施都开 放；如果只有一个设施至少服务b 个客户，则开放那个服务客户数不 小于b 的设施，把另一个设施的客户都调整到那个开放的设施上；如 北京工业大学理学硕士学位论文 果两个设施服务的客户数都小于b 但总和大于等于b ，则任意开放其中 一个设施并把另一个设施的客户都调整过来；如果两个设施服务的客户 数都小于b 且总和还小于b ，则在a 中找一个离其中一个设施最近的 设施，并把这两个设施的所有客户都调整到那个a 中的设施上 至此，算法结束 4 有容量设施选址问题 软容量设施选址问题( s c f l p ) 已经有很多常数比的近似算法c h u - d a k 和s h o m y s 1 0 利用线性规划舍入技巧( l pr o u n d i n g ) 得到容量约束一 致的软容量设施选址问题( s c f l p ) 一个3 近似比的算法j a i n 和v a z i - r a n i 2 0 】把这个问题归约到无容量约束设施选址问题( u f l ) ，利用原始对 偶算法( p r i m a l - d u a lm e t h o d ) 得到一个4 近似比的算法目前最好的近似 比是2 ，由m a h d i a n 等【27 】通过把软容量设施选址问题转化到设旋开放 费用为线性的选址问题整合因子揭示线性规划( f a c t o r r e v e a l i n gl p ) 的一 些技术得到 硬容量设施选址问题( c f l p ) ，因为它的整数规划和线性规划松弛之 间的间隙无穷大，所以目前主要的近似算法是基于局部搜索技术的当 所有设施的容量都一样时，k o r u p o l u 等 2 2 】利用局部搜索技术得到一 个8 近似比的算法c h u d a k 和w i l l i a m s o n 1 2 通过更简洁的分析，把这 个近似比改进到5 8 3 当所有设施的开放费用一样时，l e v i 等 2 4 通过 求解线性规划构建聚类得到一个近似比为5 的算法当设施容量不一 样且开放费用不一样时，p a l 等【2 8 利用局部搜索技术得到一个近似比 介于4 到8 5 3 之间的近似算法他们主要通过以下三类改进措施：开放 一1 0 - 第1 章绪论 一个设施；开放一个设施同时关闭一个或多个设施；关闭一个设施同时 开放一个或多个设施后来，m a h d i a n 和p a l 2 6 组合前面的改进措施把 上界改进到7 8 8 最近，z h a n g 等【4 4 利用多交换技术，也就是同时开放 多个设施并关闭多个设施，得到的近似比为5 8 3 ，是目前最好的结果 1 3主要贡献 在这篇文章中，我们的主要贡献是第一次利用改进的双准则算法 ( b i c r i t e r i aa l g o r i t h m ) 整合在 7 ，1 5 ，2 1 ，3 4 中的一些技巧应用到带惩罚的有 下界约束无容量设施选址问题( l b u f l w p ) 和带惩罚的有下界约束软容 量设施选址问题( s c l b f l w p ) 对于带惩罚的有下界约束无容量设施址问题，利用化归的技巧并提 出改进的双准则算法进行解决算法得到的解满足下界a b ( 1 3 口 1 ) ， 且近似比与 1 5 】和 2 1 得到的一样对于带惩罚的有下界约束软容量设 施选址问题，我们利用拉格朗日松弛技巧并利用改进的双准则算法，使 得算法得到的解满足下界a b ( 1 3 口 1 ) ，且近似比是【15 】和【2 1 】得到 的2 倍 1 4论文结构 第一章介绍预备知识，问题背景和国内外研究现状第二章介绍我 们用改进的双准则算法( b i c r i t e r i aa l g o r i t h m ) 解决带惩罚的有下界约束无 容量设施选址问题( l b f l w p ) 第三章介绍我们如何把带惩罚的有下界 北京工业大学理学硕士学位论文 约束软容量设施选址问题转化到带惩罚的无容量设施选址问题，并用 改进的双准则算法进行解决 第2 章带惩罚的有下界约束无容量设施选址问题 第2 章带惩罚的有下界约束无容量设施选址问题 2 1问题介绍 在这一章，我们考虑带惩罚的有下界约束无容量设旅选址问题，我 们用f 表示所有备选设施的集合，用d 表示所有客户的集合，用，t ， o 表示设施i f 开放的费用，用勺表示客户j d 由设施i f 提 供服务的服务费用与有下界约束的无容量选址问题不同的是，每个客 户j d 或者被开放的设施i 服务或者被惩罚乃我们把带惩罚的有下 界约束设施选址问题写成如下的数学规划形式： o p t ( i ) ：= m i n a y i + c t j x i j + 乃勺 i e f i e f j q d sj e s 8 t x q + z i 1 ，v j d i f z 玎一玑s0 ， v i f 歹d b y i ，f ( 1 ) j e d z 巧 o ，1 ) ，只j d y i o ，1 ) ，d 刁 o ，1 ) ，坳d 在上面的规划中，用变量y i 表示设施i f 是否开放，变量勺表示客户 j d 是否被惩罚，表示客户j d 是否由设施i f 服务第一个 和第二个约束保证每个客户j 或者由开放的设施i 提供服务或者被惩罚 一笔费用乃，第三个约束表示开放的设施至少服务b 个客户 一1 3 - 北京工业大学理学硕士学位论文 在双准则算法【1 5 】， 2 1 ，【3 4 】的思想基础上，我们考虑如下规划： o p t ( i ，) = m i n 如+ c i j x i j + 乃乃 i e fi e fj e d sj e $ 8 t z i j + 勺1 ，6d i 6 f z 玎一玑0 ， 只 j6d 6 ( o ，1 ) ，6f ，j6d 轨 o ，1 】- ，6d 勺 o ，1 ) ，6d 这里月= + a ，其中a = 鲁，q ，1 ) ，d ( i ) 表示离设施i 最近的 j e d ( i ) b 个客户此时，问题( 1 ) 中的下界约束没有出现在问题( 2 ) 中 2 2 算法 第2 章带惩罚的有下界约束无容量设施选址问题 施i 7 提供服务，否则惩罚客户j 当n ( i ) 中的所有客户或被重新服务或 被惩罚后，关闭设施i 同时s ( i ) 中的所有客户保持被惩罚 当每个开放的设施i 服务至少a b 个客户后，第二阶段结束用 s = ( x ，z ) 表示= ( x 7 ，y ，z 7 ) 经过第二阶段后得到的整数解 注意：此时我们通过把d ( i ) 中被惩罚的客户重新调整到服务客户 数小于a b 的开放设施上后，保证了开放的设施i 至少服务a b 个客户 2 3 算法分析 问题( 1 ) 和问题( 2 ) 的最优解有如下关系： 引理2 1o p t ( 1 7 ) ( a + 1 ) o p t ( i ) 证明假设问题( 1 ) 中的最优解开放了一部分设施，设此集合为0 ，设施 开放费用为p ，连接费用为c ，被惩罚费用为p 而问题( 1 ) 的最优解 显然是问题( 2 ) 的可行解而且这个时候问题( 1 ) 和问题( 2 ) 的连接费用 和被惩罚费用是一样的问题( 2 ) 中的设施开放费用为 所以 证毕 爿= ( + a c 巧) f + a c i e oi e o j e d c i ) o p t ( 1 7 ) 一+ c + p + sf + + ( a + 1 ) c + p + l e o s ( 入+ 1 ) ( f + + c + p + ) 北京工业大学理学硕士学位论文 我们改进的双准则算法的思路是在整个过程中，通过把一部分被惩 罚的客户重新调整到开放的设施上，使得该问题的修改过的下界约束 条件保证被满足 引理2 2经过算法的第一阶段得到的解s ，_ ( x 7 ，y 7 ，z 7 ) 的费用小于等 于( a + 1 ) p o p t ( i ) 证明设整数解s ，- ( x ，y ，z 7 ) 的费用为c ( s ，) i 因为用了近似比为p 的 算法，再利用引理3 1 ，很容易得到 证毕 c ( s ) p o p t ( 1 7 ) ( a + 1 ) p o p t ( i ) 引理2 3 问题( 1 ) 的解s = ( x ，k z ) 的费用小于等于问题( 2 ) 中的解 s 7 = ( x 7 ，y 7 ，z 7 ) 的费用 证明假设问题( 2 ) 的解s ，- ( x 7 ，y 7 ，z 7 ) 开放了设施i ，此时( i ) 中的客户 都由它服务考虑到算法的第二阶段中s ( i ) 的定义，显然( i ) n s ( i ) = 仍 ( 1 ) 如果i n ( o l + i s ( i ) i 乜b ，则解s i = ( x 7 ，y 7 ，z 7 ) 中开放设施i 的费 用和n ( i ) us ( i ) 中客户的服务费用和惩罚费用和为 爿+ + p j j e l v ( i )f e s ( i ) 相应地，在解s = ( 五y ；z ) 中它们的费用为 + j e n ( i ) u s ( i ) 第2 章带惩罚的有下界约束无容量设施选址问题 而s ( i ) cd ( i ) ，所以 + + + j e n ( ) u s ( i )j e n ( i ) j d ( ) ，+ + + 乃 i e n ( i )j d ( t ) j e s ( i ) s + 勺+ p j j ( i ) j e s ( o 也就是此时经过算法的第二阶段调整后相应的总费用没增加 ( 2 ) 如果i ( i ) i + i s ( t ) i q b ，则足够让我们界定解s ，- ( x 7 ，y 7 ，z 7 ) 中 开放设施i 的费用和n ( i ) 中客户重新调整的服务费用 我们观察到在解s = ( x ，y 7 ，z 7 ) 中，集合d ( i ) 中至少有( 1 一a ) b 个客户由其它开放的设施服务而d ( i ) 中所有客户的服务费用之和为 fc t 暑，勺，所以不由i 服务的客户中至少存在一个客户j 7 ，满足，器， t 上j l lj 根据算法的第一阶段，客户j 7 由离它最近的开放设施i 7 t 服务，即 q ，所以由三角不等式知 2 q 矿c 妒+ c 4 ，j ，s2 c 尚 所以当( t ) 中所有的客户从设施i 处重新调整到次近的开放设施i 7 i 处，或者被惩罚时，解s = ( x ，z ) 中关闭设施i 和( i ) 中所有客户重 一 新调整的服务费用小于等于 j 赢+ 海歹赢勺 = q + a s + 一 1 7 北京工业大学理学硕士学位论文 而+ 恰好是解s ，_ ( x 7 ，y 7 ，z 7 ) 中相应的开放设施i 和( i ) 中 j s n ( i ) 所有客户的总费用证毕 定理2 1 对于带惩罚的有下界约束设施选址问题，我们通过改进的双 准则算法得到的解s = ( x ，y , z ) 的总费用小于等于商l + a 加p 丁( n 证明假设解s = ( x ，z ) 的费用为g ( s ) ，则 c ( s ) 5c ( ) ( a + 1 ) o p t ( i ) = 嵩p o p t ( i ) 证毕 2 4 本章小结 这一章，我们通过改进的双准则算法解决带惩罚的有下界约束无容 量设施选址问题，但是得到的解s = ( x ，z ) 不是带惩罚的有下界约束 无容量设施选址问题( l b f l w p ) 的可行解，而是跟有下界约束的设施选 址问题( l b f l ) 7 ，1 5 ，2 1 ，3 4 】一样，对l b f l w p 利用双准则算法得到一个相 同的近似比啬p 第3 章 带惩罚的有下界约束软容量设施选址问题 第3 章带惩罚的有下界约束软容量设施选址问题 3 1 问题介绍 这一章我们考虑带惩罚的有下界约束软容量设施选址问题，我们用 下面的线性整数规划来描述： 五玑+ c t j x i j + 乃乃 i e fi e fj e d s j e s 。巧+ 乃1 ，v j d i f z 巧一玑0 ， v i 只j d ( 日) u i y i ，觇f j 6 d b 缸n 溉1 ) ，v i f j d z 巧 o ，1 】- ，v i 只j d y i z + d 勿 0 ，1 ) ，坳d 整数变量玑表示设施i 开放的次数，0 1 变量勺表示客户j d 是否 被惩罚，表示客户j d 是否由设施i f 提供服务与带惩罚的有 下界约束无容量选址问题( l b f l w p ) 不同的是设施i f 最多只能服务 u t 个客户，但是设施i f 可以重复开放多次 在文章 7 】的基础上，我们把带惩罚的有下界约束软容量设篪选址 问题转化到修改过的无容量设施选址问题把规划( h ) 线性松弛后并去 满足三角 第3 章带惩罚的有下界约束软容量设施选址问题 不等式 而d l p 2 的对偶规划为： 恳车m i n 五m + 嘞如+ 乃乃 i fi 6 fj e d sj e s s t 粕+ 乃1 ，v i d i 6 f ( l p 2 )粕一m 0 ，v i6ej d 考虑如下整数规划： o p t ( i f l ：= m i n ，k ，乃0 ，v i6ej d s t x , j + 乃1 ，坳6dz jj 一 。 f ( 日日) 一k 0 ，v i6 只j d ) 岛6 o ，1 ) ，m o ，1 ) ，z j o ，1 ，v i f 歹6d o p t ( 1 2 ) ：= m i n 五k + 龟j x , j + 乃历 i 6 f i 6 fj e d sj s 8 t x , j + 历1 ，6d t f ( 日日日)一k 0 ， v i f 歹6d x , j6 o ，1 ，k6 _ o ，1 ) ，历6 o ，1 ) ，v i6f 歹d 其中五= _ t + a 葡，d ( i ) 表示在新定义的服务费用下离设施i 最近 j 6 d ( i ) 的b 个客户 2 1 乙乃 徊 琏 ； 神 +k 一 触 北京工业大学理学硕士学位论文 3 2算法 第一阶段：我们用p 近似算法解决规划( h h h ) ，得到一个整数解s 7 = ( x 7 ，y 7 ，z ，) i 同时保证这个整数解中每个客户都是由开放的最近的设施 第二阶段：对于整数解= ( x 7 ，y 7 ，z 7 ) 中服务客户数少于a b 的设施， 用n ( i ) = j d ：z 0 = 1 ) 表示由设施i 服务的客户的集合，用s ( ) = d d ( t ) ：2 ；= 1 ) 表示d ( t ) 中被惩罚的客户的集合下面分两种情况： 情况1 ：如果l ( i ) i + i s ( i ) i a b ，这时s ( i ) 中的客户都被取消惩罚， 同时都由设施i 给他们提供服务同时n ( i ) 中的客户被服务情况保持 不变经过这一步，设施i 至少服务a b 个客户 情况2 ：如果i ( i ) i + i s ( t ) i 冬a b ，这时对于n ( i ) 中的每个客户j 采 取如下措施：找出离客户j 次近的开放设施i ，若q ， 乃，则客户j 由设 施i 7 提供服务，否则惩罚客户j 当n ( i ) 中的所有客户或被重新服务或 被惩罚后，关闭设施i 同时s ( i ) 中的所有客户保持被惩罚 当每个开放的设施i 服务至少a b 个客户后，第二阶段就结束了用 s = ( - 2 ，驴，- 2 ) 表示s ，_ ( x 7 ，y 7 ，z 7 ) 经过第二阶段后得到的关于规划( h h ) 注意：此时我们通过把d ( i ) 中被惩罚的客户重新调整到服务客户数 小于a b 的开放设施上后，保证了开放的设施i 至少服务a b 个客户 第三阶段：构造规划( h ) 的可行解( 把下界b 换成乜b ) ： 一轴= f 斜舢 。劢= 砀而= i 等i ，虮只佧d 3 3 算法分析 规划( h h h ) 和规划( h ) 的最优解有如下关系： 引理3 1o p t ( 1 2 ) ( a + 1 ) o p t ( i ) 证明假设规划( h ) 中的最优解开放了一些设施，设此集合为0 ，设施 开放费用为p ，连接费用为c ，被惩罚费用为p 而规划( h ) 的最优解 显然是规划( h h h ) 的可行解设这个时候规划( h h h ) 的设施开放费用 为p ，连接费用为c ”，被惩罚费用为p ”则 p 2 五= i e o 尝+ a l e o j e 蚤d ( i ) ( + 去) i d _ 一o 半p + a c c ”= l e o i e d s = 1 6 0 e d s ( + 去) 筘+ 等 一 p ”= p + 所以 d p t ( j 2 ) f ”+ c “+ p ”垡二生+ ( 入+ 1 ) c + 尸 ( a + 1 ) ( f 4 + c + + p ) = ( a + 1 ) o p t ( i ) 证毕 我们改进的双准则算法的思路是在整个过程中，通过把一部分被惩 罚的客户重新调整到开放的设施上，使得该问题的修改过的下界约束 条件保证被满足 引理3 2经过算法的第一阶段得到的解s 7 = ( x 7 ，y ，z 7 ) 的费用小于等 于( a + 1 ) p o p t ( i ) 北京工业大学理学硕士学位论文 证明设整数解= ( x 7 ，y 7 ，z 7 ) 的费用为c ( s ，) 因为用了近似比为p 的 算法，再利用引理3 1 ，很容易得到 c ( ) sp o p t ( 1 2 ) ( 入+ 1 ) p o p t ( i ) 证毕 引理3 3经过算法的第二阶段得到的解s = ( 叉，驴，z ) 的费用小于等于 规划( h h h ) 中的解= ( x 7 ，y 7 ，z ) 的费用 证明假设规划( h h h ) 的解s = ( x ，y 7 ，z ) 开放了设施i ，此时n ( i ) 中的 客户都由它服务考虑算法第二阶段中s ( i ) 的定义，显然n ( i ) q s ( i ) = o ( 1 ) 如果l ( i ) l + i s ( t ) i 理b ，则解s ，- 7 ，y 7 ，z 7 ) 中开放设施i 的费 用和n ( i ) u s ( i ) 中客户的服务费用和惩罚费用为五十勃+ 功相 应地，在解s = ( - x ，y ，- z ) 中它们的费用为五+，而s ( i ) cd ( t ) ， j e n ( i ) u s ( i ) 所以 五+ 岛_ i + 葡+ 萄 j e n ( i ) u s ( i )j e n ( oj e d ( i ) 五+ 勺+ + 功 j e n ( i )j e d ( i )j s ( i ) 五+ 锄+ 巧 j e n ( i )j e s ( i ) 也就是此时经过算法的第二阶段调整后相应的总费用没增加 ( 2 ) 如果j ( i ) i + i s ( i ) i a b ，则足够让我们界定解s ，- 7 ，y 7 ，z 7 ) 中 开放设施i 的费用和n ( i ) 中客户重新调整的服务费用 我们观察到在解s 7 = ( x 7 ，y 7 ，z 7 ) 中，此时集合d ( i ) 中至少有( 1 一a ) j e 7 个客户由其它开放的设施服务而d ( i ) 中所有客户的服务费用之和为 第3 章带惩罚的有下界约束软容量设施选址问题 勘，所以不由i 服务的客户至少存在一个客户j 7 ，满足，器， ，d “) 。 根据算法的第一阶段，客户j 7 由离它最近的开放设施i i 服务，即 魂劭，所以由三角不等式知 2 瓦，勃，+ 舀7 2 劭，t 兰 尝河 所以当n ( i ) 中所有的客户从设施i 处重新调整到次近的开放设施i 处， 或者被惩罚时，解s = ( 一x ，一y ，劢中关闭设施i 和( i ) 中所有客户的重新 调整的服务费用小于等于 ，赢，葡+ 尚，赢， = 嘞+ a s 锄+ 五 j e n ( i )j e d ( i )j e n ( o 而+ 五恰好是解s 7 = ( x 7 ，y 7 ，z 7 ) 中相应的开放设施i 和( i ) 中 所有客户的总服务费用证毕 定理3 1 带惩罚及有下界约束的软容量选址问题通过改进的双准则算 法得到的解( z ，可) 的费用小于等于2 鲁o p t ( i ) 证明由解的构造可知，甄=降1 降卜 ief蜘ief勺ieff j e dff 【等+ e 卜j e d i 6 f 确、 一 ， = i 6 f - 斛rr 。( f j 6 df + 毫) 瓦 c 2 ( e 五+ 岛瓦) i pni c p 北京工业大学理学硕士学位论文 由前面的算法分析知道经过算法的第二阶段后，解的费用没有增加 又经过算法的第一阶段后 综上， 证毕 霹五+ 勃羁( 1 + a ) p o p t ( i ) i e fj di e f 玩 + e e c t f x o 2 嵩妒，( n t f j 6 dt f 一 一 3 4 本章小结 这一章，我们先把带惩罚的下界约束软容量设施选址问题去掉下界 问题转化 惩罚的有 是带惩罚 跟有下界 算法应用 第3 章 带惩罚的有下界约束的软容量设施选址问题 结论 本文提出带惩罚的有下界约束无容量设施选址问题和带惩罚的有 下界约束软容量设施选址问题，并提出改进的双准则算法加以解决对 于带惩罚的有下界约束无容量设施选址问题，通过化归技巧构建出带 惩罚的无容量设施选址问题，然后利用改进的双准则算法解决；对于带 惩罚的有下界约束软容量设施选址问题，通过拉格朗日松弛技术转化 为带惩罚的无容量设施选址问题，然后利用改进的双准则算法解决 下面是值得进一步研究的一些问题： 1 设计带惩罚的有下界约束设施选址问题和带惩罚的有下界约束 软容量设施选址问题的近似算法 2 当惩罚函数是次模函数时，设计带惩罚的有下界约束设施选址 问题和带惩罚的有下界约束软容量设施选址问题的近似算法 3 对于有下界约束的设施选址问题，设计更好的近似算法 4 对于有下界约束的k 一层设旋选址问题，设计近似算法 5 对于有下界约束的硬容量设施选址问题，设计近似算法 北京工业大学理学硕士学位论文 参考文献 1k i a a r d a l ，f a c h u d a k ，a n dd b s h m o y s ，a3 - a p p r o x i m a t i o na l g o r i t h mf o r t h ek - l e v e lu n c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e m ，i n f o r m a t i o hp r o c e s s i n g l e t t e r s ，1 9 9 9 ，7 2 ：1 6 1 1 6 7 2a a g e e v ，i m p r o v e da p p r o x i m a t i o na l g o r i t h m sf o rm u l t i l e v e lf a c i l i t yl o c a t i o n p r o b l e m s ，o p e r a t i o n sr e s e a r c hl e t t e r s ，2 0 0 2 ，3 0 ：3 2 7 - 3 3 2 3a a g e e v ，y y e ，a n dj z h a n g ，i m p r o v e dc o m b i n a t o r i a la p p r o x i m a t i o na l - g o r i t h m sf o rt h e 七- l e v e lf a c i l i t yl o c a t i o np r o b l e m s i a mj o u r n a lo nd i s c r e t e m a t h e m a t i c s ，2 0 0 5 ，1 8 ：2 0 7 - 2 1 7 4v a r y a ，n g a r g ，r k h a n d e k a r ，a m e y e r s o n ，k m u n a g a l a ，a n dv p a n d i t ， l o c a ls e a r c hh e u r i 8 t i cf o rk - m e d i a na n df a c i h t yl o c a t i o np r o b l e m s ，p r o c e e d i n g s o fs t o c ，2 0 0 1 ，p p 2 1 2 9 j b y r k aa n dk i a a r d a l ，a no p t i m a lb i f a c t o ra p p r o x i m a t i o na l g o r i t h mf o rt h e m e t r i cu n c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e m ，s i a mj o u r n a lo nc o m p u t i n g ， 2 0 1 0 ，3 9 ：2 2 1 2 2 2 3 1 m c h a r i k a ra n ds g u h a ，i m p r o v e dc o m b i n a t o r i a la l g o r i t h m sf o rf a c i l i t yl o - c a t i o na n dk - m e d i a np r o b l e m s ，p r o c e e d i n g so ff o c s ，1 9 9 9 ，p p 3 7 8 3 8 8 m c h a r i k a r ，s k h u l l e r ，d m m o u n t ，a n dg n a r a a s i m b a n ，a l g o r i t h m sf o r f a c i l i t yl o c a t i o np r o b l e m sw i t ho u t l i e r s ，p r o c e e d i n g so fs o d a ，2 0 0 1 ，p p 6 4 2 6 5 1 2 8 - 参考文献 8f a c h u d a k ，i m p r o v e da p p r o x i m a t i o na l g o r i t h m sf o ru n c a p a c i t e df a c i l i t yl o - c a t i o n ，p r o c e e d i n g so fi p c o ，1 9 9 8 ，p p 1 8 0 1 9 4 9f a c h u d a ka n dk n a g a n o ，e f f i c i e n ts o l u t i o n st or e l a x a t i o n so fc o m b i n a t o r i a l p r o b l e m sw i t hs u b m o d u l a rp e n a l t i e sv i at h el o v a s ze x t e n s i o na n dn o n - s m o o t h c o n v e xo p t i m i z a t i o n ，p r o c e e d i n g so fs o d a ，2 0 0 7 ，p p 7 9 8 8 1 0f c h u d a ka n dd s h o m y s ，i m p r o v e da p p r o x i m a t i o na l g o r i t h m sf o rac a p a c i - t a t e df a c i l i t yl o c a t i o