设施选址问题的近似算法pdf/txt下载_在线阅读全文

内容简介

设施选址问题是经典的NP-难解问题之一, 在运筹学、计算机科学和管理科学中有着广泛的应用.《设施选址问题的近似算法》介绍了设施选址问题及其变形的近似算法. 主要内容包括：无容量限制的设施选址问题的线性规划舍入算法、无容量限制的设施选址问题的原始对偶算法、无容量限制的设施选址问题的局部搜索算法、有容量限制的设施选址问题、k层设施选址问题、凹设施选址问题、不确定设施选址问题、设施选址问题的其他变形等.

作者简介

徐大川，北京工业大学数理学院教授、博士生导师。研究方向：组合优化，近似算法，数学规划，博弈论，供应链管理。中国运筹学会数学规划分会秘书长、常务理事，北京运筹学会常务理事，中国运筹学会理事，中国科学院数学与系统科学研究院优化与应用研究中心成员。北京工业大学数理学院“运筹学与控制论”二级学科责任教授。《运筹与管理》编委。Mathematical?Reviews评论员。发表学术论文60余篇，先后承担国家自然科学基金项目3项。

目　　录

《运筹与管理科学丛书》序总序前言第1章绪论................................................................... 1
1.1 无容量限制的设施选址问题............................................ 2

1.2 设施选址问题的各种变形.............................................. 4
第2 章无容量限制的设施选址问题的线性规划舍入算法...................... 9

2.1 STA 算法...............................................................9

2.2 Chudak-Shmoys 算法.................................................. 14

2.2.1简单的4-近似算法................................................ 14

2.2.2随机(1+3/e)-近似算法........................................... 16

《运筹与管理科学丛书》序总序前言第1章绪论................................................................... 1 1.1 无容量限制的设施选址问题............................................ 2 1.2 设施选址问题的各种变形.............................................. 4 第2 章无容量限制的设施选址问题的线性规划舍入算法...................... 9 2.1 STA 算法...............................................................9 2.2 Chudak-Shmoys 算法.................................................. 14 2.2.1简单的4-近似算法................................................ 14 2.2.2随机(1+3/e)-近似算法........................................... 16 2.2.3随机(1+2/e)-近似算法........................................... 20 2.2.41.7336-近似算法.................................................. 24 2.3 Sviridenko 算法....................................................... 30 2.4 Byrka-Aardal 算法.................................................... 38 2.5 Li 算法................................................................ 45 第3 章无容量限制的设施选址问题的原始对偶算法..........................54 3.1 Jain-Vazirani 算法.....................................................54 3.2 P′al-Tard¨os 算法....................................................... 59 3.3 MMSV 算法...........................................................63 3.4 JMS 算法............................................................. 71 3.5 MYZ 算法.............................................................78 第4 章无容量限制的设施选址问题的局部搜索算法..........................86 4.1 AGKMMP 算法....................................................... 86 4.2 贪婪增广算法......................................................... 93 4.3 Guha-Khuller 算法.................................................... 96 4.3.12.408-近似算法................................................... 96 4.3.2 设施费用相同情形................................................. 99 4.3.3 近似比下界...................................................... 102 4.4 Charikar-Guha 算法.................................................. 104 4.4.1(1+√2+.)-近似算法............................................ 105 4.4.21.8526-近似算法.................................................. 106 4.4.31.728-近似算法................................................... 108 第5 章有容量限制的设施选址问题......................................... 110 5.1 软容量限制的设施选址问题..........................................110 5.2 硬容量限制的设施选址问题的局部搜索算法........................ 114 5.2.1 多交换局部搜索算法. ............................................. 114 5.2.2 算法分析........................................................ 120 5.2.3 紧的例子........................................................ 128 5.3 硬容量限制的设施选址问题的线性规划舍入算法.................... 129 第6 章k 层设施选址问题................................................... 141 6.1 问题介绍.............................................................141 6.2 线性规划舍入算法................................................... 142 6.3 光滑化的原始对偶算法.............................................. 145 6.4 组合算法.............................................................150 6.5 2 层设施选址问题....................................................157 第7 章凹设施选址问题..................................................... 168 7.1 光滑化的原始对偶算法.............................................. 168 7.2 对偶拟合算法........................................................ 175 第8 章不确定设施选址问题................................................ 186 8.1 两阶段随机设施选址问题............................................ 186 8.2 风险可调的两阶段随机设施选址问题................................ 189 8.3 动态设施选址问题................................................... 190 第9 章设施选址问题的其他变形........................................... 195 9.1 次模惩罚设施选址问题.............................................. 195 9.2 带服务安置费用的设施选址博弈..................................... 201 9.3 极大形式的k 层设施选址问题....................................... 205 9.4 硬容量限制的k 层设施选址问题.................................... 207 参考文献.......................................................................213 索引........................................................................... 217 《运筹与管理科学丛书》已出版书目........................................... 221

显示全部信息

在线试读部分章节

第1 章绪论
自20世纪60年代初期以来,设施选址问题(facilitylocationproblem,简记为FLP)在运筹学中一直占据着中心位置[69].它来自于工厂、仓库、超市、学校、医院、图书馆、火车站、代理服务器、传感器等位置的确定问题.运筹学、管理科学和计算机科学领域有许多专家从事该问题的研究.
设施选址问题是NP-难解问题,除非P=NP,设施选址问题不存在多项式时间精确算法.由于设施选址问题具有很强的实际背景,处理该问题所取得的进展往往有助于提高生产效率和管理水平.因此,许多学者对设施选址问题感兴趣,设法从各种渠道来寻找处理它的方法,其中一个有效而合理的方法是采用近似算法来求解.此时要求设计出多项式时间算法,并要求估计算法所得到的解对应的目标函数值与最优值之间的比值(近似比).已知一个极小化问题,如果算法在多项式时间内能给出可行解,并且所对应的目标值不超过最优值的ρ(.1)倍,那么称该算法为ρ-近似算法,称ρ为近似比.对于极大化问题可以类似地定义近似比ρ(.1).关于NP-完全性理论和近似算法的更多介绍参见文献[58,59,70,79].
设计设施选址问题的近似算法主要分为三类：线性规划舍入(LProunding)、原始对偶(primal-dual)和局部搜索(localsearch).前两类算法基于线性规划松弛.在线性规划舍入算法中,首先给出原问题的线性整数规划模型,然后求解相应的线性规划松弛问题得到分数最优解,通常会根据可行性要求对分数最优解进行改造,最后在(改造的)分数解的基础上构造原问题的整数可行解.由于线性规划舍入算法需要求解线性规划,故不是组合算法.如果不直接求解线性规划松弛问题,而是设计组合算法给出对偶问题的可行解(通常为对偶上升过程),根据该对偶可行解的信息构造原始问题的整数可行解,通过与对偶可行解比较得到算法的近似比,这类算法称为原始对偶算法.原始对偶算法有两个优点：一是该算法是组合算法,可以揭示问题的组合结构;二是该算法具有鲁棒性,容易移植到其他变形问题上.对偶拟合(dual.tting)算法可以看做原始对偶算法的变形.该算法用组合算法构造对偶解(不一定可行)使得费用与原始整数可行解的费用相同,通过将对偶解一致缩小得到对偶可行解,同时缩小的系数即为近似比.在局部搜索算法中,给定初始可行解,定义适当的邻域,通过引入恰当的调整策略,在邻域中得到改进的可行解,依次迭代下去,直到按照给定的调整策略不能改进为止.局部搜索算法在硬容量限制的设施选址问题上得到了成功的应用.
1.1 无容量限制的设施选址问题
结构最简单同时也是最经典的设施选址问题是无容量限制的设施选址问题(un-capacitatedfacilitylocationproblem,简记为UFLP).在UFLP中,给定(F, C)的二部图G,其中F 表示设施(facility)集合,C 表示顾客(client)集合,对于任意i∈F, j ∈C,fi表示设施i的开设费用(openingcost),dj表示顾客j的服务需求量,cij表示设施i为顾客j提供单位服务的连接费用(connectioncost).我们的目标是选择F 的子集F., 开设F.中的设施,找到函数φ:C .→ F., 将C 中顾客连接到开设的设施上以满足其需求,最终使得总费用(开设费用与连接费用之和)最小.

第1 章绪论 自20世纪60年代初期以来,设施选址问题(facilitylocationproblem,简记为FLP)在运筹学中一直占据着中心位置[69].它来自于工厂、仓库、超市、学校、医院、图书馆、火车站、代理服务器、传感器等位置的确定问题.运筹学、管理科学和计算机科学领域有许多专家从事该问题的研究. 设施选址问题是NP-难解问题,除非P=NP,设施选址问题不存在多项式时间精确算法.由于设施选址问题具有很强的实际背景,处理该问题所取得的进展往往有助于提高生产效率和管理水平.因此,许多学者对设施选址问题感兴趣,设法从各种渠道来寻找处理它的方法,其中一个有效而合理的方法是采用近似算法来求解.此时要求设计出多项式时间算法,并要求估计算法所得到的解对应的目标函数值与最优值之间的比值(近似比).已知一个极小化问题,如果算法在多项式时间内能给出可行解,并且所对应的目标值不超过最优值的ρ(.1)倍,那么称该算法为ρ-近似算法,称ρ为近似比.对于极大化问题可以类似地定义近似比ρ(.1).关于NP-完全性理论和近似算法的更多介绍参见文献[58,59,70,79]. 设计设施选址问题的近似算法主要分为三类：线性规划舍入(LProunding)、原始对偶(primal-dual)和局部搜索(localsearch).前两类算法基于线性规划松弛.在线性规划舍入算法中,首先给出原问题的线性整数规划模型,然后求解相应的线性规划松弛问题得到分数最优解,通常会根据可行性要求对分数最优解进行改造,最后在(改造的)分数解的基础上构造原问题的整数可行解.由于线性规划舍入算法需要求解线性规划,故不是组合算法.如果不直接求解线性规划松弛问题,而是设计组合算法给出对偶问题的可行解(通常为对偶上升过程),根据该对偶可行解的信息构造原始问题的整数可行解,通过与对偶可行解比较得到算法的近似比,这类算法称为原始对偶算法.原始对偶算法有两个优点：一是该算法是组合算法,可以揭示问题的组合结构;二是该算法具有鲁棒性,容易移植到其他变形问题上.对偶拟合(dual.tting)算法可以看做原始对偶算法的变形.该算法用组合算法构造对偶解(不一定可行)使得费用与原始整数可行解的费用相同,通过将对偶解一致缩小得到对偶可行解,同时缩小的系数即为近似比.在局部搜索算法中,给定初始可行解,定义适当的邻域,通过引入恰当的调整策略,在邻域中得到改进的可行解,依次迭代下去,直到按照给定的调整策略不能改进为止.局部搜索算法在硬容量限制的设施选址问题上得到了成功的应用. 1.1 无容量限制的设施选址问题 结构最简单同时也是最经典的设施选址问题是无容量限制的设施选址问题(un-capacitatedfacilitylocationproblem,简记为UFLP).在UFLP中,给定(F, C)的二部图G,其中F 表示设施(facility)集合,C 表示顾客(client)集合,对于任意i∈F, j ∈C,fi表示设施i的开设费用(openingcost),dj表示顾客j的服务需求量,cij表示设施i为顾客j提供单位服务的连接费用(connectioncost).我们的目标是选择F 的子集F., 开设F.中的设施,找到函数φ:C .→ F., 将C 中顾客连接到开设的设施上以满足其需求,最终使得总费用(开设费用与连接费用之和)最小. 在本书中,如无特殊说明,一般考虑dj=1(.j ∈C)的情形.UFLP可写为如下形式的线性整数规划 min.fiyi+.cijxij i∈F i∈F,j∈C s.t..xij.1,.j ∈C, i∈F xij.yi,.i ∈F,j ∈C,xij,yi∈{0, 1}, .i ∈F,j ∈C. (1.1.1) 在上述规划中,yi表示设施i是否开设,若开设,则yi=1,否则yi=0;xij表示顾客j与设施i是否相连,若相连,则xij=1,否则xij=0;第一组约束条件表示任意顾客j至少与一个设施相连;第二组约束条件表示如果顾客j连接到某个设施i上,则设施i必须开设.记OPT为(1.1.1)的最优解,相应的设施开设费用和连接费用分别是FOPT和COPT.(1.1.1)的线性规划松弛为 min.fiyi+.cijxij i∈F i∈F,j∈C s.t..xij.1,.j ∈C, i∈F xij.yi,.i ∈F,j ∈C,xij,yi.0,.i ∈F,j ∈C. (1.1.2) 记(x.,y.)为(1.1.2)的最优解,相应的最优值记为LP.,并记 F.:=.fiyi.,Cj.:=.cijx.C.:=.C.=.cijx. ij, j ij. i∈F i∈F j∈C i∈F,j∈C 1.1 无容量限制的设施选址问题3

显示全部信息

设施选址问题的近似算法下载

设施选址问题的近似算法

发布书评

相关图书推荐