《运筹与管理科学丛书》序

总序

前言

第1章绪论

1.1无容量限制的设施选址问题

1.2设施选址问题的各种变形

第2章无容量限制的设施选址问题的线·性规划舍入算法

2.1STA算法

2.2Chudak—Shmoys算法

2.2.1简单的4一近似算法

2.2.2随机（1 3/e）一近似算法

2.2.3随机f1 2/e）一近似算法

2.2.41.7336一近似算法

2.3Sviridenko算法

2.4Byrka—Aardal算法

2.5Li算法

第3章无容量限制的设施选址问题的原始对偶算法

3.1Jain—Vazirani算法

3.2Pal—Tardos算法

3.3MMSV算法

3.4JMS算法

3.5MYz算法

第4章无容量限制的设施选址问题的局部搜索算法

4.1AGKMMP算法

4.2贪婪增广算法

4.3Guha—Khuller算法

4.3.12.408—近似算法

4.3.2设施费用相同情形

4.3.3近似比下界

4.4Charikar—Guha算法

4.4.1（1 √2 ε）一近似算法

4.4.21.8526—近似算法

4.4.31.728—近似算法

第5章有容量限制的设施选址问题

5.1软容量限制的设施选址问题

5.2硬容量限制的设施选址问题的局部搜索算法

5.2.1多交换局部搜索算法

5.2.2算法分析

5.2.3紧的例子

5.3硬容量限制的设施选址问题的线性规划舍入算法

第6章k层设施选址问题

6.1问题介绍

6.2线性规划舍入算法

6.3光滑化的原始对偶算法

6.4组合算法

6.52层设施选址问题

第7章凹设施选址问题

7.1光滑化的原始对偶算法

7.2对偶拟合算法

第8章不确定设施选址问题

8.1两阶段随机设施选址问题

8.2风险可调的两阶段随机设施选址问题

8.3动态设施选址问题

第9章设施选址问题的其他变形

9.1次模惩罚设施选址问题

9.2带服务安置费用的设施选址博弈

9.3极大形式的k层设施选址问题

9.4硬容量限制的k层设施选址问题

参考文献

索引

《运筹与管理科学丛书》已出版书目2100433B

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

《设施选址问题的近似算法》可作为运筹学、计算机科学、管理科学和应用数学专业的高年级本科生和研究生的教材和参考书，亦可供相关研究领域科研人员参考。

所谓设施，是指生产运作过程得以进行的硬件手段，通常是由工厂、办公楼、车间、设备、仓库等物质实体所构成。

所谓设施选址，是指如何运用科学的方法决定设施的地理位置，使之与企业的整体经营运作系统有机结合，以便有效、经济地达到企业的经营目的。

设施选址包括两个层次的问题：

第一：选位，即选择什么地区（区域）设置设施，沿海还是内地，南方还是北方，等等。在当前全球经济一体化的大趋势之下，或许还要考虑是国内还是国外；

第二：定址。地区选定以后，具体选择在该地区的什么位置设置设施，也就是说，在已选定的地区内选定一片土地作为设施的具体位置。设施选址还包括这样两类问题：一是选择一个单一的设施位置；二是在现有的设施网络中部新点。

设施选址单一设施选址

单一设施选址是指独立地选择一个新的设施地点，其运营不受企业现有设施网络的影响。在有些情况下，所要选择位置的新设施是现有设施网络中的一部分，如某餐饮公司要新开一个餐馆，但餐馆是与现有的其他餐馆独立运营的，这种情况也可看作单一设施选址。单一设施选址又分以下几种方法：

负荷距离法（load-distance method）

负荷距离法的目标是在若干个候选方案中，选定一个目标方案，他可以使总负荷（货物、人或其他）移动的距离最小。当与市场的接近程度等因素至关重要时，使用这一方法可从众多候选方案中快速筛选出最有吸引力的方案。这一方法也可在设施布置中使用。

因素评分法

因素评分法在常用的选址方法中也许是使用得最广泛的一种，因为它以简单易懂的模式将各种不同因素综合起来。运用这种因素评分法应注意：在运用因素评分法计算过程中可以感觉到，由于确定权数和等级得分完全靠人的主观判断，只要判断有误差就会影响评分数值，最后影响决策的可能性。关于确定权数的方法很多，比较客观准确的方法是层次分析法，该方法操作并不复杂，有较为严密的科学依据，我们推荐在做多方案多因素评价时尽可能采用层次分析法。

盈亏分析法

盈亏分析法是厂房选址的一种基本方法，亦称生产成本比较分析法。这种方法基于以下假设：可供选择的各个方案均能满足厂址选择的基本要求，但各方案的投资额不同，投产以后原材料、燃料、动力等变动成本不同。这时，可利用损益平衡分析法的原理，以投产后生产成本的高低作为比较的标准。

选址度量法

选址度量法是一种既考虑定量因素、又考虑定性因素的用以支持设施选址的方法。

重心法

重心法是一种布置单个设施的方法，这种方法要考虑现有设施之间的距离和要运输的货物量。它经常用于中间仓库的选择。在最简单的情况下，这种方法假设运入和运出成本是相等的，它并未考虑在不满载的情况下增加的特殊运输费用。

设施选址设施网络选址

设施网络中的新址选择比单一设施选择问题更复杂，因为在这种情况下决定新设施的地点位置时，还必须同时考虑到新设施与其它现有设施之间的相互影响和作用。如果规划的好，各个设施之间会相互促进，否则就会起到副面作用。设施网络选址包括以下几个方法：

简单的中线模式法

简单的中线模式法是一种厂址选择的方法。这种方法有其局限性。这种方法只假设坐标上最优的点（即是使总的运输距离最短的点）是一个可行的建厂点，并不考虑在那里现在是否有道路，也不考虑自然地形、人口密度，以及其他许多在布点时应考虑的重要事项。

德尔菲分析模型

典型的布置分析考虑的是单一设施的选址，其目标有供需之间的运输时间或距离极小化，成本的极小化，平均反应时间的极小化。但是，有些选址分析涉及多个设施和多个目标，其决策目标相对模糊，甚至带有感情色彩。解决这类选址问题的一个方法是使用德尔菲分析模型，该模型在决策过程中考虑了各种影响因素。使用德尔菲分析模型涉及三个小组，即协调小组、预测小组和战略小组。每个小组在决策中发挥不同的作用。

启发式方法（heuristics）

启发式方法只寻找可行解，而不是最优解。负荷距离法中的重心法就是一种启发式方法。有许多计算机化了的启发式方法，可解决m，n达几百、几千的问题。早在60年代，就有人提出了用启发式方法解决大型设施选址问题。今天，启发式方法已经广泛在很多场合应用。

模拟方法（simulation）

模拟是试图通过模型重现某一系统的行为或活动，而不必实地去建造并运转一个系统，那样会造成巨大的浪费，或根本没有可能实地去进行运转实验。模拟方法有许多种应用，在选址问题中，模拟可以使分析者通过反复改变和组合各种参数，多次试行来评价不同的选址方案，模拟方法可描述多方面的影响因素，因此比运输表法有更大的实用意义。

优化方法（optimization）

运输表法实际上就是一种优化方法，虽然只是某一方位问题的最优。这种方法求出的不是可行解、满意解，而是最优解，即：在所有可能的方案中，不会有比它更好的了。但是由于这种方法要从理论上证明是最优，所以它在使用上有两大局限性：

1）模型必须较抽象、较简单，否则得不出解。但由此而使模型的描述距实际较远；

2）很多定性因素被忽略掉了，因此不可能得出在考虑定性条件下可能得出的很多结论。2100433B

对一个企业来说，设施选址是建立和管理企业的第一步，也是事业扩大的第一步。设施选址的重要性显而易见。其重要性主要在于：设施选支队设施建成后的设施布置以及投产后的生产经营费用、产品和服务质量以及成本都有极大而长久的影响。一旦选择不当，它所带来的不良后果不是通过建成后的加强和完善管理等其他措施可以弥补的。因此，在进行设施选址时，必须充分考虑到多方面因素的影响，慎重决策。其次，除新建企业的设施选址问题以外，随着经济的发展，城市规模的扩大，以及地区之间的发展差异，很多企业面临着迁址的问题。等等。可见，设施选址是很多企业都面临的，现代企业生产运作管理中的一个重要问题。

战略目标

对于一个特定的企业，其最优选址取决于该企业的类型。工业选址决策主要是为了追求成本最小化；而零售业或专业服务性组织机构一般都追求收益最大化；至于仓库选址，可能要综合考虑成本及运输速度的问题。总之，设施选址的战略目标是使厂址选择能给工厂带来最大化的收益。