（运筹学与控制论专业论文）无容量约束选址与软容量约束选址博弈.pdf

摘要 选址问题一直备受优化界和管理科学界的关注。作为最基本的选址问题， 无容量约束选址问题已经被广泛的研究这个问题是通过于选择一些备选地 址，希望最小化总费用，总费用包括设施建设费用和设施与顾客之间的连通 费用一般情况下，我们假设连通费用满足三角不等式和对称性我们通过对 j m s 算法和算法的修改得到两个新的算法数值试验表明这两个算法表现 良好 我们也考虑了软容量约束选址博弈，旨在解决费用分摊问题。软容量约束 选址问题作为选址问题的一个变种仍然是n p - h a r d 问题，我们先将软容量约束 选址问题转化成一个无容量约束选址问题，然后使用一个关于无容量约束选 址问题的费用分摊方法，这个费用分摊方法是单调的，竞争的并且至少可以补 偿无容量约束选址问题总费用的l 3 我们可以证明这样得到的费用分摊对于 原问题满足单调性，竞争性，并且至少补偿了原问题总费用的1 6 关键词：选址；近似算法；博弈；费用分摊 北京工业大学理学硕士学位论文 a bs t r a c t f a c i l i t ) ，l o c a t i o np r o b l e mr e c e i v e dc o n s i d e r a b l ea t t e n t i o ni nt h ea r e ao ft h et h e o p e r a t i o n sr e s e a r c ha n dm a n a g e m e n ts c i e n c e a st h e 如n d a m e n t a lf a c i i i t yl o c a t i o n ， u n c a p a c i t a t e df a c i l i t ) ，l o c a t i o n ( u f l ) p r o b l e mh a sb e e ns t u d i e de x t e n s i v e l y - t h e p r o b l e mi st oc h o o s et h el o c a t i o n so ff a c i l i t i e st om i n i m i z et h et o t a lc o s to fo p e n i n g f a c i l i t ya n dt r a n s p o r t a t i o nb e t w e e no p e n e da n dc l i e n t s g e n e r a l l y ，w ea s s u m em e c o s to fn a n s p o r t a t i o nf o mam e t r i c ，m e a n i n gt h a tt h e ya r es y m m e t r i ca n ds a t i s 矽 t h et r i a n g l ei n e q u a l i 妙w em o d i 母t h ej m sa l g o r i m ma n dt h ea l g o r i t h mt og e tt w o n e w g r e e d ya l g o t h m sa n dt h en u m e r i c a le x p e r i m e n ts h o w so u ra l g o r i t h m sp e r f o m w e u w ea l s oc o n s i d e rt h es o r c a p a c i t a t e df a c i l i t yl o c a t i o ng a m e ，w h i c hd e a l sw i t h c o s ta l l o c a t i o n f o rt h en p - h a r dv 撕a n to ft h ef a c i l i t yl o c a t i o np r o b l e m ，w ec h a n g e i ti n t oa nu n c a p a c i t a t e df a c i l i 够l o c a t i o np r o b l e mn r s t ，t h e nu s ea c o s t - s h a r i n gm e t h o d f o rt h eu 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 ，w h i c hi sc r o s s - m o n o t o n i ca n dc o m p e t i t i v e ，a n dr e c o v e r sa1 3 r do ft h et o t a lc o s to ft h eu n c a p a c i t a t e df a c i l i 够l o c a t i o n p r o b l e m w 色p r o v et h a tc o s t - s h a r i n gi sc m s s m o n o t o n i ca n dc o m p e t i t i v e ，a n dr e c o v e r sa1 6 劬c t i o no f t h et o t a lc o s to f t h eo r i g i n a ls o r c a p a c i t a t e df - a c i l i t ) ，l o c a t i o n p r o b l e m k e y w o r d s ： f a c i l i t yl o c a t i o n ；a p p r o x i m a t i o na l g o r i t h m ；g a m e ；c o s ts h a r e i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它 教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文 ( 保密的论文在解密后应遵守此规定) 签名：韭导师签名：匕期：一 第1 章绪论 第1 章绪论 随着社会的进步和科技的发展，各种各样的工业问题被总结出数 学模型并被学术界广泛研究通过这些研究我们可以更好地优化资源 配置，节约成本选址问题一在供应链管理以及电信设施布局中有着广 泛的应用背景，一直备受工业界和学术界的关注是开建更多的设施 ( f a c i l i t y ) 或者仓库( w a r e h o u s e ) 以减少每个顾客( c l i e n t ) 或者城市( c 时) 的连通成本还是为了节约建设的费用开建尽量少的设施( f a c i l i t y ) 或者仓 库( w a r e h o u s e ) ，同时也导致了顾客( c l i e n t ) 或者城市( c 时) 的连通成本 上升? 这是每一个面对选址问题的决策者必须权衡的两个方面然而众 所周知，选址问题作为n p - c o m p l e t e 问题，在p n p 的情况下，我们无法 在多项式时间内求出最优解，因此设计近似算法一直是解决选址问题的 重要方法之一近似算法的基本思想是：对于一类问题，既然设计一个 精确算法在多项式时间内给出一个精确解是困难的，那么我们设计一个 近似算法在多项式时间内给出一个可行解，并且我们能从理论上分析解 得质量一一称之为近似比对于一个最小化问题，是这个问题的任意实 例，o p t ( ，) 是关于，的最优值，算法a 的近似比等于m 衅( a ( ，) 0 p t ( 驯 1 选址博弈在实际问题中有很多应用一个公平有效的费用分摊机制 可以保障参与者的利益并且可以从利益的角度对联盟的稳定给予支持 对于选址问题这类n p c o m p l e t e 问题，在多项式时间内求出精确的总费 用就是困难的，在这种情况下如何开建一个有效、公平的费用分摊机制 也有很重要的研究意义 1 1问题介绍 选址问题有着各种各样的变形，其中最受到基本的选址问题是无容 北京工业大学理学硕士学位论文 量约束的选址问题( u n c 印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 ) 我们可以很简单 地描述这个问题：给出m 个可用来建设设施( f a c i l i 够) 的地点，n 个需要供 应的顾客( c l i e n t ) 决策者需要给出一个选址方案，在m 个备选地址中选 择一些地址建设设施并且将每一个顾客分配到一个建设好的设施其中 涉及到两方面的费用：一方面是对于每一备选地址都对应一个五，可以理 解为在该地址开建设施要投入的开建费；另一方面对于每一顾客歹与设施 i 之间存在一个单位连通费用白f ，可以理解为在这两点之间运输每一单位 物品所要付出的连通费用目标是使得两方面的总费用最少我们假设 备选地址的集合为f ，顾客的集合为c ，每个顾客的需求量为1 ，我们可 以用下面的数学规划来描述选址问题： m i n 五纺+ 勺 i fj c i f 毗 莩1 ， ( 1 1 ) z 巧玑， v i ，j 玑，z 玎 o ，1 ) ， v t 当然，对于每一个顾客歹他们的需求量不一定恰好都是1 ，但是对于 需求量为而的顾客，我们可以把他视作如个需求为1 的顾客，即各种需 求情况都可以转化成需求为1 的的情况求解这样我们只要关注需求为 l 的情况 在生产实际中，我们为了使模型更接近实际情况往往要对上面的模型加 新的约束比如对每个设施i 的产能是有限的，即它的供应能力有一个 容量上限讹当每个顾客的需求量为1 时，我们也可以用下面的数学规 划来描述这一类硬容量约束的选址问题： 2 第1 章绪论 m i n 五玑+ m ml 玑+ 乙l 诞f j c i f s t z 玎1 ， t z 巧玑， 、j v i ，歹 ( 1 2 ) v i v 20 ， ，) ； 还有一类带容量约束的选址问题我们可以在某一个备选地址i 支付 玑倍的开建费玑五用来获得玑倍的容量玑蚴，其中犰是非负整数我们称 这一类问题为软容量约束的选址问题，可以用数学规划描述如下： m i n 犰+ z 巧 i fj c i f s t 1 ， z 巧玑， z 巧玑u t ， j 玑z + ， 0 ， 、j 、i j ( 1 3 ) v i 、气。1 注意到对于带容量约束的问题我们不再要求是整数，即一个顾客可 以由多个设施来满足他的需求并且当顾客的需求不恰好为l 的情况， 我们依旧可以问题转化成需求一致为1 的情况来求解 3 北京工业大学理学硕士学位论文 围绕选址问题还存在一类博弈问题一选址费用分摊即如果选址 方案所引发的费用要由所有的顾客来承担时，决策者就面对了一个费用 分摊问题由于每个顾客的地理位置和选址方案的不同，简单的平摊费 用显然是不合理的并且选址问题本身的难度也增加了设计费用分摊算 法的难度一般的对于这一由n p _ h a r d 问题引发的博弈我们希望设计一 个费用分摊算法满足：竞争性、近似成本补偿和单调性即：任给一个 参与人的集合s ( s f ) ，c + ( s ) 是当选址问题中的顾客集合为s 时该问 题的最优目标函数值能够计算v 歹s 所分配的费用叩( s ，歹) 的算法，称 为一个费用分摊方法 我们希望得到的费用分摊方法满足如下若干性质： 竞争性：集合s 中的每个参与人分摊的费用总和不会超过他们合作 的最优费用，即 _ ，7 ( s ，七) c + ( s ) k f s q - 近似成本补偿：要求参与人至少支付1 q 最优费用，即 叩( s ，南) c + ( s ) q 七s 单调性：如果参与人的集合变大，每一个参与人分摊的费用不增加， 也就是说对于所有的s s 7 都有 1 2已有研究成果 叩( s ，歹) 叩( s 7 ，j ) 选址问题的算法研究可以追溯到上个世纪6 0 年代参见b a l i n s k i 4 ，l o e l l l l 和h a m b u 唱e r 【1 9 】，m a n n e 2 2 和s t o l l s t e i m e r 3 6 ，s h m o y s 等 3 7 】给出了第一 4 第1 章绪论 一个常数近似比的算法，他们先用确定性的方法得到一个近似比为4 的算 法，然后通过对参数q 在区间( 0 ，1 ) 中的随机选取得到了一个在期望上总 费用不大于最优解3 1 6 倍的算法g u h a 和k h u l l e r 1 2 改进了s h m o y s 3 7 】 的算法，他们采用了一种贪婪增广的技术将算法近似比改进到2 4 1 ，并且 他们证明了在p 尸的情况下，不存在一个近似比小于1 4 6 3 的多项式 复杂度算法c h a d a k 和s h m o y s 9 采用了一种新的聚类方法，将近似比改 进到了1 7 3 6 k o m p o l u 2 0 给出了一个5 + e 组合近似算法，这是第一个 常数近似比的组合算法j a i n 和v a z i 眦i 1 7 】给出了一个基于原始对偶分 析的组合算法，这个算法的近似比为3 ，并且这算法中的分析方法被广 泛地用于各种相关的优化问题，这个算法通常被称为算法c h a r i k a r 和g u h a 8 】使用了比例缩放和贪婪增广的技术，将j a i n 和v a z i r a n i 1 7 的 结果改进到了1 8 5 3 ，并且当他们的结果和c h a d a k 和s h m o y s 9 】取最好时， 近似比可以改进到1 7 2 8 j a i n 等 1 5 】给出了两个组合算法采用一种用线 性规划寻找近似比的分析办法得到两个紧的分析结果，这两个算法的紧 的近似比分别是1 8 6 l 和1 6 1 ，这两个算法一般被称为蹦s 算法m a h d i a n 等 2 9 采用了比例缩放和贪婪增广的技术改进了州s 算法，得到了目前 组合算法中最好的近似比1 5 2 b y r k a 6 】，改进了c h a d a k 和s h m o y s 9 】的 算法，得到一个( 1 6 7 7 4 ，1 3 7 3 8 ) 一近似算法，并且将这个算法与s 算法 以一定概率组合，得到了一个近似比为1 5 的近似算法，这是目前近似比 最好的算法 对于软容量约束选址问题，这一类问题也被广泛的研究 9 ，1 7 ，1 ，1 6 ， 2 9 】m a h d i a n ，y e 和z h a n g 3 0 】给出了目前最好的近似算法，近似比为2 ， 达到了这个问题的整数间隙费用分摊问题作为一个合作博弈问题被广 泛地研究 2 ，3 ，1 0 ，7 ，1 3 ，1 4 ，1 8 ，2 l ，2 6 ，2 8 ，3 1 ，3 4 ，3 5 ，更进一步基于费用分 摊方法还可以设计费用分摊机制，m o u l i n 2 7 】证明了单调性直接导致了 5 北京工业大学理学硕士学位论文 无操纵性( g r o u ps t r a t e g y p r o o f ) 机制p a l 和t a r d o s 2 4 针对选址问题设计了 一个单调的费用分摊算法，此算法满足单调性、竞争性，和3 近似成本 补偿x u 和d u 4 0 运用类似的对偶上升算法设计了关于七层选址问题的 一个费用分摊算法，他们的算法满足单调性、竞争性和6 近似成本补偿 1 3 结构和研究内容 第一章介绍了问题及其理论与实际意义，并且追溯了问题发展历史 第二章研究了无容量约束的选址问题，给出了两个新的算法，数值试验 表明这两个算法表现良好第三章给出了关于一个软容量约束的选址问 题的算法的费用分摊方法，并且证明了该方法满足：单调性、竞争性、近 和6 似成本补偿 6 第2 章无容量约束选址问题 2 1准备工作 第2 章无容量约束选址问题 ( 1 1 ) 是无容量约束选址问题的一种整数规划描述。但是在已有的算 法设计中，还有一类基于集合覆盖思想的整数规划可以用来描述无容量 约束的选址问题j a i n 等 1 5 】给出了这种整数规划 我们称一个设施和若干个顾客的集合为星每一个星的费用是开建星 里设施的费用加上星内所有的顾客到设施的连通费用即对于一个星 s = ( i ，c ，) ，其中i f ，c 7 c 若用岛表示星s 的费用，c 。= 丘+ j c t 那么我们可以说无容量约束的选址问题可以描述成一个集合覆盖问题， 即挑选出一个星的集合使得他们的费用和最小并且要保证每一个顾客至 少在一个被挑选到的星里我们可以用下面的整数规划描述无容量选址 问题： t m m 2 c s s s s t 1 ，v 歹 8 ：j 8 z 。( o ，1 ) ， v s s ( 2 1 ) 其中s 是所有星的集合，其中的元素有指数多个在前面我们介绍了无容 量约束的选址问题是一个n p - h a r d 问题在设计这类问题的近似算法是 往往把该问题的整数规划松弛成线性规划作为最优解的一个下界对于 ( 1 1 ) 和( 2 1 ) 松弛后的线性规划我们有以下引理： 引理2 1 1 ( 1 1 ) 和( 2 1 ) 松弛后的线性规划最优值相等 证明我们先给出两个整数规划的线性规划松弛： ( 1 1 ) 的线性规划松弛： 7 北京工业大学理学硕士学位论文 m i n 五犰+ f j c i f s t z 巧1 ， i ( 2 2 ) 甄，j 玑， ，j ( 2 1 ) 的线性规划松弛： 玑，z 巧0 ， t 1 m ml c 8 占s s t 1 ，坳 ( 2 3 ) s ：j s 0 ， v s s 设( 2 3 ) 的一个最优解为z ：，我们可以构造一个( 2 2 ) 的可行解( 犰，) ： 犰= 8 ：i 8 = 占：i s ，j s 容易验证，z o ) 是( 2 2 ) 的一个可行解且目标函数值不变这就得到了 d 尸t ( 2 2 ) 0 p t ( 2 3 ) 同样的我们假设( 2 2 ) 的一个最优解是( 耖+ t ，z + 巧) 若这解是一个完整解，即z 订= 孵 0 或者z + 玎= 0 我们也可以构造 ( 2 3 ) 的一个可行解：z 。= 夕。i ，如果i s ，并且任意z ，歹s ，z + 玎 0 ，否则 z 。= o 若( 旷，z 巧) 不是一个完整解我们可以通过以下方法得到( 2 3 ) 的一个可行解： 1 对于每一个z ，对于所有的s ：t s 令托：= 0 ，令p ：= 1 2 对所有的歹最= d ：z 巧 o ) 排序设o o ) ，z 8 i p ：= z + 订l ，z i 九：= z 巧 一z 订1 ， 4 p ：= p + 1 重复上面的过程直到鼠为空集 这样我们得一个( 2 3 ) 的一个可行解，容易验证目标函数值不改变， 这就得到了0 p t ( 2 2 ) d p t ( 2 3 ) 所以d 尸t ( 2 2 ) = 0 p t ( 2 3 ) 口 注意到，上面引理证明中解的转变保证了目标函数值得不改变，这 样我们就可以有效地解线性规划( 2 3 ) ，而不用调用椭球算法同时( 2 2 ) 和( 2 3 ) 对偶问题也有类似的关系我们先分别给出它们的对偶： ( 2 2 ) 的对偶： m a xf a j - - jj j c s t 哟一如，歹 ( 2 4 ) 锄五， j ，如o ， 坳 ( 2 3 ) 的对偶： t - 、 m a x 乙 j e s t g ，v s ：s s ， ( 2 5 ) j 8 n c 哟0 ，：歹c 引理2 1 2 设( q + ，p + ) 是( 2 4 ) 的最优解，那么a 是( 2 5 ) 的最优解 证明因为( 2 4 ) ，( 2 5 ) 的对偶问题最优值相等，所以只要证明q 对 9 北京工业大学理学硕士学位论文 于( 2 5 ) 是可行的对于任意的s ，不妨设i s q j + 巧+ ) j sj 8 + c 巧g 所以q + 对( 2 5 ) 是可行的，并且是最优解 口 j 8 2 2 算法描述 j a i n 等 1 5 】给出了一个关于无容量约束的贪婪算法并且证明了这算 法达到了紧的近似比1 6 1 我们先回顾一下这个算法： 算法2 2 1 ( j m s ) ： 1 我们引入一个时间的概念，算法从0 时刻开始在o 时刻所有的顾 客被定义成未分配( 定义未分配的顾客集合为u ，此时u = c ) ，所有设施 被定义成未开建，每个顾客的预算q j 被定为0 在每一个时刻，每一个 顾客对未开建的设施i 都做出贡献最f 贡献的数量可以如下计算：对于 未分配的顾客歹，贡献等于= m a x ( 一，o ) 对于已经分配的顾客歹， 假设他被分配到t 7 ，他的贡献鼠j = m a x ( q ，j 一，o ) 2 当u c ，增长时间，同时对于每一个歹矿，以同以速率增长， 直到下面两类情况中的一类发生( 如果两类情况同时发生，任意挑选一 个先发生) ( a ) ：对于某一个没有开建的设施i ，它得到总的贡献等于它的开建费， 即：最j = 五这种情况下我们开建设施 ，并且把所有对i 的贡献非零 j c 的顾客分配到这个新开建的设施上把已分配的顾客从u 里去掉 ( b ) ：对于某一个已经开建的设施t ，和一个没有分配的顾客j ，如果= 在这种情况下，把歹分配到这设施上去，把已分配的顾客从里去掉 蹦s 1 5 】算法中的一般被解释成每个顾客歹的预算而线性规划 ( 2 5 ) 中的变量也解释成每个顾客的预算所以我们考虑可以的增长可 1 0 第2 章无容量约束选址问题 以从( 2 5 ) 的最优解出发而不是像j m s 算法中那样从0 出发，显然这样 定起始点给我们带来了更多的信息根据引理2 1 2 ，我们知道( 2 4 ) 的最 优解实际上就是( 2 5 ) 的最优解我们的算法描述如下： 算法2 2 2 ( j m s l p ) ： 1 解l p 求( 2 4 ) 的最优解q f 2 我们引入一个时间的概念，从0 时刻开始在0 时刻所有的顾客被 定义成未分配( 定义未分配的顾客集合为u ，此时u ：= c ) ，所有设施被 定义成未开建，每个顾客的预算q j 被定为乜j 在每一个时刻，每一个顾 客对未开建的设施i 都做出贡献b i j 贡献的数量可以如下计算：对于未 分配的顾客歹，贡献：= m a x ( 哟一，o ) 对于已经分配的顾客歹，假设 他被分配到i 7 ，他的贡献等于如：= m a ) ( ( q ，j c 巧，o ) 3 当c ，增长时间，同时对于每一个歹u ，以同以速率增长a ， 直到下面两类情况中的一类发生。( 如果两类情况同时发生，任意挑选一 个先发生) ( a ) ：对于某一个没有开建的设施i ，它得到总的贡献等于它的开建费， 即：嘞= 五这种情况下我们开建设施i ，并且把所有对i 的贡献非零 j c 的顾客分配到这个新开建的设施上把已分配的顾客从u 里去掉 ( b ) ：对于某一个已经开建的设施i ，和一个没有分配的顾客歹，如果= 在这种情况下，把歹分配到这设施上去把已分配的顾客从u 里去掉 可以看到在我们的算法中在0 时刻是( a ) 类情况恰好发生，因为 a + j 是( 2 5 ) 的最优解，则对于( 2 5 ) 的约束至少有一个是紧的但是不 会出现b 巧 五的情况，如果这种情况出现，我们可以构造集合 j c 北京工业大学理学硕士学位论文 s = i ) u 歹： o ) 嘞 五弓 a ，这就破坏了q 。对于 j cj 8 ( 2 5 ) 的可行性 通过上面的讨论，我们发现从任意一个对偶可行解出发，都可以将 算法继续下去如果采用上面的算法，要求解一个线性规划这样的算 法就不再是一个组合的算法，我们考虑用算法【1 7 】第一阶段得到的a j 作为初始点，这样的算法我们称为删s 算法这样的改动实际上是修 改了算法的第二阶段，在算法的第二阶段从暂时开放的设施里挑 出一个极大独集合进行开建然后把所有的顾客分配到最近的已经开建的 设施上去我们给出的蹦s - 算法采用了蹦s l p 的2 ，3 步来取代算 法的第二阶段具体算法如下： 算法2 2 3 ( j m s - j v ) ： 1 我们引入一个时间亡1 的概念，从0 时刻开始在0 时刻所有的顾客 被定义成未连接，每个顾客的初始预算q j 被定成0 对于( 2 4 ) ，随着亡。得 增长，以同样的速率增长所有未连接顾客歹的初始预算当对于某一条 边( z ，歹) ，= ，称这条边是紧的同时对偶变量如也以同样的速率增 长保证( 2 4 ) 的约束不被违背当如= 六时，设施i 称为被支付的所 j 有与被支付的设施之间存在紧边的未连接顾客被定义成已连接( 不再增 长初始预算) 每个顾客在被定义成已连接时的预算记作q f 直到所有 的顾客都被定义成已连接时第一阶段停止 2 我们引入一个时间2 的概念，从o 时刻开始在0 时刻所有的顾客 被定义成未分配( 定义未分配的顾客集合为u ，此时u ：= c ) ，所有设施 被定义成未开建，每个顾客的预算q ，被定为q + ，在每一个时刻，每一个 顾客对未开建的设施i 都做出贡献鼠歹贡献的数量可以如下计算：对于 1 2 第2 章无容量约束选址问题 未分配的顾客歹，贡献：= m a x ( 一，o ) 对于已经分配的顾客歹，假 设他被分配到i 7 ，他的贡献等于鼠j ：= m a x ( q ，j 一，0 ) 3 当u c ，增长时间，同时对于每一个歹u ，以同以速率增长q j ， 直到下面两类情况中的一类发生( 如果两类情况同时发生，任意挑选一 个先发生) ( a ) ：对于某一个没有开建的设施 ，它得到总的贡献等于它的开建费， 即：嘞= 五这种情况下我们开建设施i ，并且把所有对i 的贡献非零 j c 的顾客分配到这个新开建的设施上把已分配的顾客从u 里去掉 ( b ) ：对于某一个已经开建的设施i ，和一个没有分配的顾客歹，如果哟= 在这种情况下，把j 分配到这设施上去把已分配的顾客从u 里去掉 可以看到在我们的算法中在0 时刻是( a ) 类情况恰好发生，因为 a + j 是( 2 5 ) 的最优解，则对于( 2 5 ) 的约束至少有一个是紧的但是不 会出现最j 的情况，如果这种情况出现，我们可以构造集合 j c s = 好ud ：嘞 o ) 嘞 五号哟 g ，这就破坏了a + j 对于 j cj 8 ( 2 5 ) 的可行性 2 3 算法分析 我们给出的算法是在已有的m s 算法上做出一些修改，我们的证明 本质上是和 15 方法一致我们可以得到类似的引理： 引理2 3 1 可以找到一个可行解，它的目标函数值不超过蹦s - l p 算 法得到的，其中7 s 由删s - l p 算法得到 j c 证明把所有的顾客分派到在算法中开建的最近的设施上这样一个 选址方案的总费用恰好等于口 j c 1 3 北京工业大学理学硕士学位论文 和 1 5 】中的证明一样我们要找到一个常数，y ，使得对于v s s ， j 8 n c ，y g 如果存在这样的常数7 ，y 就是删s l p 算法的一个上界即：我们的 目标是找到一个尽量小的常数，y ，使得对于任意 ，和任意s s ，a j j s n c ，y ( 五+ c 巧) j 8 n e 因为每个顾客的预算初始值定为q j 我们可以令= q + j + 哟 不失一般性，我们可以做以下假设： 乜1 2 q 七 ( 2 6 ) 我们还需要给多的变量来刻画我们的算法对于任意i ( o i 尼) ， 考虑算法在时刻= q i e 时的情况当e 非常小时，就是顾客i 第一 次分配到某一设施的前一时刻同时，每一个顾客1 ，2 ，3 ，z 一1 已经分 配到某一设施对于每一个歹 ，若顾客歹已分配到某一设施，我们用 乃，t 来表示歹到这设施单位连通费用；否则令巧，i = q + j + a ；第二种情 只出现在当锄= q f 时，即顾客z 与顾客歹在同一时刻第一次分配到某 两个设施上通过算法我们知道每个顾客歹会不断调整他的分配，他会 不断地将自己调整到单位连通费用更便宜的设施上去，所以他到被分配 的设施的单位连通费用是不上升的于是对于每一个j 我们得到以下的 不等式： 巧，j + 1 乃，j + 2 巧，七 ( 2 7 ) 同时我们考虑茌亡= 叱一e 时刻，每个顾客歹对于未开建的任意设施地 贡献假设他到这设施的单位连通费为奶，该设施的开建费为厂对于 j z 和歹i ，两类情况我们分别有： m a x ( 一奶，o ) ，如果歹 t ， 1 4 第2 章无容量约束选址问题 m a x ( a j + 亡一奶，o ) ，如果歹t 由蹦s l p 算法可知，在a i 时刻，顾客对于任意设施的贡献和不能 超过这设施的开建费，于是我们得到以下不等式： ( 2 8 ) 考虑顾客歹和z ，且有歹 i 在t = i e 时刻，顾客歹已经被分配 到某一个已经开建的设施，乃， 表示他在这个时刻的单位连通费用，由三 角不等式我们知道顾客i 到顾客歹已经分配到的设施的单位连通费用不 超过q ，i + 吨+ 奶。否则就是叱= q j 的情况，这个时候根据乃， 的定 义，吩，i + 以+ 而+ a + 不小于t 时刻的这时候，我们有以下的不等式： 有： q i + 叱勺，i + 矾+ 奶+ q t 骨a t 巧，i + 吨+ 吗 ( 2 9 ) 因为a + t 是对偶最优解，那么就不能破坏( 2 5 ) 的任意一个约束所以 南七 q + 厂+ 也 i = 1i = 1 1 5 ( 2 1 0 ) ， 一 办 一 叱 + 牛， 口缸m 南例 + 嘭 一 巧 腿m 触 北京工业大学理学硕士学位论文 根据上面给出的约束我们可以写出一个线性规划用来分析近似比： ( n + a n i ) 魏5 璁觚曼l 1 广 ，+ e 喀 t 群l s 。t 。 貔冬及 + l ， 勺，t q ，件1 ， 戏t 吩，t 十或+ 呜， i l 凇敬( 鬈菇一鸯，o ) j = l 七 + m a x ( a 4 i + q t 一如，o ) ， j 一 知奄 也4 i 厂十以， v l 竞。 v 1 j i 惫， v l 歹 i 惫， v 1 竖i 2 t ( p ) 亡) + t ( g ) 如果有一个歹s ( p ) ns ( g ) ，我们得到勺q + t ( p ) + t ( g ) 得到矛盾 口 引理3 3 3 我们可以找到关于规划( 3 4 ) 的一个o 1 整数解( k j ，k ) ， 使得如+ 只m 3 a ( 歹) j c t f i f j e 证明我们按照算法b 构造一个整数解实际上如果p 是一个开建的 设施，对于所有歹昂，有3 亡( p ) 否则，我们假设哟 亡( p ) 3 设设施 g 是顾客歹第一个连接到的满的设施，即勺。且亡( 口) q j 如果按照 上面构造可行解的方式，若设施口被开建，锄) + q j 2 ( p ) ，得到矛 盾若g 没有被开建，那么存在某一个设施口7 满足c q g ，2 ( 口) 2 因为 勺口，c 南+ 勺q + c q q ，亡) + + 2 ( g ) t 0 ) + 3 0 ，j 2 亡) ，得到矛盾注 意到p q ，因为t ( 9 7 ) 哟 ( p ) 结合引理2 3 4 ，我们可以知道对于某 一开建的设施p ，s ( p ) 中的顾客可以的费用分摊足够支付设施p 的开建费 加上1 3 的连接费用类似的，我们也可以证明对于不属于任意品( 设施 p 已开建) 的顾客，他们每个人的费用分摊都足够支付1 3 的连接费用 所以我们构造的o 1 整数解满足g j + 只m 3 q ( 歹) 口 j c i f f j c 综合以上引理我们得到： 2 4 第3 章选址博弈 定理3 3 1 我们得到了一个费用分摊算法，满足竞争性，单调性，和 6 近似成本补偿 证明竞争性和单调性显然，由引理2 3 5 ，我们可以找到关于规划( 3 4 ) 的一个0 1 整数解，并且这个解满足： 粕+ 只k 3 j ci f 诞f j c x 玎 令玑：= 等 ，z 巧：= 五j 这样构造的( z 订) 是软容量约束选址问 题的一个可行解，并且犰s 争+ k 于是得到： 最后一个不等式由引理2 3 5 得到，于是可以得到： 3 4 本章小结 ( 3 5 ) 口 本章我们给出了软容量约束选址问题的一个费用分摊方法实际上我们 是把一个软容量约束选址问题转化成了一个无容量约束选址问题，再对 这个无容量约束选址问题做一个费用分摊最后我们可以证明我们得到 的费用分摊方法满足竞争性，单调性和6 一近似成本补偿 2 5 嚣 一 挲 + 玑 只 r 锄触 + + 1 1 花 咒 锄 聊 触触 触邶 = 一 缈 6 一 玑五 触 + 一叼 z q 钳缈 结论 结论 本文主要研究了无容量约束选址问题和软容量约束选址问题的费用 分摊问题 对于无容量约束选址问题已经存在大量的算法m y z 算法是目前近 似比最好的组合算法，并且这个算法的近似比1 5 2 距离这个问题的近似 比下界1 4 6 3 已经很近了但是数值试验表明m y z 算法在实际计算过程 中表现并不好至于j m s 算法我们可以很容易举出“坏”例子继续研 究这个问题，找出实际计算表现良好的算法并克服已有的“坏”例子，仍 然具有意义我们通过给j m s 算法重新选择起始点，得到了两个新的算 法虽然通过理论分析没有得到更好的近似比，但是数值试验表明这两 个算法在实际计算中表现良好删s l p 算法，在选择起始点的时候采用 了对偶问题的最优解这样的起始点可以克服了j a i n 等 1 5 给出的关于 删s 的一类“坏”例子我们给出的算法紧的近似比是多少? “坏”例子 又是怎样的并且在计算过程中发现，对于选址问题，解线性规划松弛 往往得到整数解，怎样定义距离和开建费才能得到“难”的选址问题? 对于软容量约束选址问题的费用分摊，我们给出了一个满足竞争性， 单调性，6 一近似成本补偿的费用分摊方法这样的费用分摊方法依赖一 个从软容量约束选址问题到无容量约束选址问题的转化对于无容量约 束选址问题p a l 和t a r d o s 3 2 】给出的3 - 近似成本补偿费用分摊算法是一 个紧的算法，我们给出的6 - 近似成本补偿的费用分摊方法是否也是一个 紧的算法7 2 6 参考文献 参考文献 1 】v a r y a ，n g a 唱，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 aa n dv p a n d i t l o c a l s e a r c hh e u r i s t i c sf o rk m e d i a na n df a c i l i t yl o c a t i o np r o b l e m s i np r o c e e d i n g so f3 3 r d a c ms y m p o s i u mo nt h e o d ，o fc o m p u t i n g 2 0 01 2 】s a n i l ya n dm h a v i v t h ec o s ta l l a c a i i o np r o b l e mf o rt h e 右r s to r d e ri n t e r a c t i o ni o i n t r e p l e n i s h e n tm o d e l ( 捆p 阳f 幻脚r 船p 口，曲f o r t c o m i n g 2 0 0 3 3 】o n b o n d a r e v a s o m ea p p l i c a t i o n so fl i i l e a rp r o 伊a m m i l l gm e t l l o d st ot 1 1 et h e o r yo f c o o p e r t i v eg a m e s 陋r u s s i 锄】尸m 6 ，p ，砂尉6 p 埘p 哟几1 9 6 3 ，l o ：1 1 9 1 3 9 4