带有惩罚和软容量约束的下界设施选址问题的双标准近似算法研究
- 格式：pdf
- 大小：315.39 KB
- 文档页数：10
下载文档原格式
合集下载
改进樽海鞘算法求解带时间窗的应急选址路径问题
包装工程第45卷第5期·220·PACKAGING ENGINEERING2024年3月改进樽海鞘算法求解带时间窗的应急选址路径问题徐帆，马良，张惠珍*，陈曦（上海理工大学管理学院，上海200093）摘要：目的为使应急物资及时高效地送到灾区, 针对多目标应急选址−路径问题，在考虑灾区的时间窗及物资运输过程中道路安全的情况下，以最小化经济成本、最小化时间惩罚成本及最大化道路安全性为目标，构建多目标优化模型。
同时，设计改进的樽海鞘算法求解问题，以验证模型的可行性和算法的有效性。
方法根据模型的特征对樽海鞘算法进行改进，运用随机生成和贪心算法相结合的方式生成初始解，利用交叉算子和邻域搜索算子改进原始算法的位置更新操作，引入非支配排序遗传算法（NSGA-Ⅱ）的精英保留策略，以提高算法的性能。
结果经过多个算例测试，该算法能快速获得一簇Pareto解，与基本樽海鞘算法进行对比后可知，改进后的算法性能更优越。
结论对于灾后及时响应的应急选址路径问题，采用改进的樽海鞘算法具有一定优越性，并在多个目标权衡的情况下，可供决策者根据目标的偏好找到较满意的解，对于研究应急选址路径问题具有一定的参考价值。
关键词：选址−路径问题；应急物资；时间窗；改进樽海鞘算法中图分类号：TP301.6；TB485.3 文献标志码：A 文章编号：1001-3563(2024)05-0220-10DOI：10.19554/ki.1001-3563.2024.05.027Improved Salp Swarm Algorithm for Solving Multi-objectiveEmergency Location Routing Problem with Time WindowsXU Fan, MA Liang, ZHANG Huizhen*, CHEN Xi(School of Management, University of Shanghai for Science & Technology, Shanghai 200093, China)ABSTRACT: In order to ensure timely and efficient delivery of emergency resources to disaster areas, the work aims to construct a multi-objective optimization model for the multi-objective emergency location routing problem by taking into account the time windows of the disaster area and road safety during resources transportation, with the objectives of minimizing economic costs, time penalty costs, and maximizing road safety. At the same time, an improved salp swarm algorithm is designed to solve the problem, in order to verify the feasibility of the model and the effectiveness of the algorithm. Based on the characteristics of the model, the algorithm was improved by combining random generation and greedy algorithm to generate initial solutions. The position update operation of the original algorithm was improved by crossover operators and neighborhood search operators. The elite retention strategy of NSGA-Ⅱ was introduced to improve the performance of the algorithm. After test of multiple examples, this algorithm could quickly obtain a cluster of Pareto solutions and was compared with the original salp swarm algorithm. The improved algorithm had better performance. For the emergency location routing problem of timely response after a disaster, the improved salp swarm algorithm has certain advantages, and can provide decision-makers with satisfactory solutions based on the preferences of multiple objectives. It has a certain reference value for the field of emergency location routing problems.KEY WORDS: location routing problem; emergency resources; time windows; improved salp swarm algorithm收稿日期：2023-05-11基金项目：国家自然科学基金（72101149）；教育部人文社会科学基金（21YJC630087）；国家外国专家项目（G2023013029）*通信作者第45卷第5期徐帆，等：改进樽海鞘算法求解带时间窗的应急选址路径问题·221·近年来，地震、洪涝等自然灾害突发事件频繁发生。
费用与资源约束双重模糊下的联合采购模型——基于差分进化算法的研究
定， 可用模糊变量表示不确定 的资源约 束来拓展 Ｊ Ｐ研究 ， Ｒ 模
０ 引言
联 合采 购问题 （Ｒ ）是指从 一个供应 商处对 多种产 品进 ＪＰ 行 分组采购 ， 从而达到分摊 主要准备 费用 、 节省 采购总费 用之
糊约束条件对最优 基本 联合 补货周期 有影 响 ， 模糊资源约束下 Ｊ Ｐ通过模糊运算 可转 换为确 定性 Ｊ Ｐ Ｒ Ｒ 。例 如李 成严 等人 】 研究了模糊资金约束下的联合补充问题 ， 用三角模糊数表示不
ｔ ｅｔ ｓｓｏ ｅ ｐ ｒｏｍａ ｃ ｙ ｔｐ ｃ ｌ ｕ ｃｉｎ ． ｈ ｅ ｔ ｆ ｅ ｆｒ ｎ ｅ ｂ ｙ ｉａ ｎ ｔ ｓ ｈ ｔ ｆ ｏ Ｎｕ ｒ ａ ｘ ｍｐｅ ｌ ｓ ａ ｅ ｔ ｅ ｐ ｏ ｏ ｅ Ｅ ａｇ ｒ ｈ ｃ ｎ ｂ ｕｔ ｂ ｅ ｍｅ ｃ ｌｅ ａ ｌｓ ｉ ｕ ｔ ｔ ｈ ｒ ｐ ｓ ｄ Ｄ ｌｏ ｉ ｍ ａ ｅ ａ ｓ ｉ ｌ ｉ ｌ ｒ ｔ ａ
ａｆｚｙＪ ｄ ｌｕ ｉｇ ｔ ａ ｇ ｌｒｆｚｙ ｎ ｍｂ ｒｔ ｅ ｒｓｎ ｈ ｎ ｒｓｔｐ ｃ ｓ ａ ｏｄｎ ｏｔａ ｄ ｆｚｙ ｃｐｔｌｃ ｎ ｕ ｚ ｍｏ ｅ ｓｎ ｒ ｎ ｕａ ｕｚ ｕ ｅ ｏｒｐｅｅ ｔｔｅｍｉｏ ｅｕ ｏｔ ｒ ｈ ｌｉｇ ｃｓ ｎ ｕ ｚ ａ ｉ ｏ ． ＲＰ ｉ ｄ ａ －
确定的资源约束 ， 并基于遗传算法 （ｅ ｅｃａ ｏｉ ｍ， Ａ） ｇｎｔ ｌ ｒｈ Ｇ 进行 ｉ ｇ ｔ
了求解 。实际上除了资金约束 ， 还有更多贴近管理实践 的资源 约束 （ 如存储 空间 和运 输能 力等 ） 尚待进行 深入研 究 。另 外 ， 库存保管费用包括多种费用 （ 库空 间占用费 、 仓 为存货所 支 出 的保险费 、 保管 过程 中的 自然损耗 和技术 进步导致 的报 废 、 库
给定限期条件下应急选址问题的量子竞争决策算法
Ｌ ｃ ｔ ｎ ｗｉ ｅ ａ ｌ ｅ ｏ ａ ｉ ｔ ａ Ｇｉ ｎ Ｄｅ ｄ ｉ ｏ ｈ ｖ ｎ
ＬＩ Ｙｏ ｇ 一。 ＭＡ ａ ｇ Ｕ ｎ Ｌｉｎ ， ＮＩ ＮＧ — ｉ ｇ Ａｉｂ ｎ 。
（ ．ｃｏｌｆＭ ｎ ｇｒ ｎ，Ｕ ｉｒｔ ｈ ｎ ｈｉ ｏ ｃ ｎｅａ ｄＴｃｎ ｌ ｙ Ｓａ ｇ ａ ２０ ９ ， ｈｎ ； ． ｅａｔ １Ｓｈ ｏ ｏ ａ ａ ｅｅ ｔ ｎ ｅ ｉ ｏ ａｇ ａ ｆｒＳｉ ｃ ｎ ｅｈｏ ｇ ， ｈ ｎｈ ｉ ００３ Ｃ ｉ ２ Ｄ ｐ ｒ ａ ｖ ｓｙ ｆＳ ｅ ｏ ａ —
０ 引 言
应 急 设施 选 址是 当今 深受 关 注的一 个重 要 的研究 方 向 ， 直接 影 响到应 对 突 发 事 件 的实 效 性 … 。如 在 城 市 规划 建设 中 ， 策者 往往 要决定 一 些公共 紧急 服 务设 施 点 的优化 选 址 问题 ， １０出警 中心 、 防大 决 如 １ 消 队 、 救 中心 、 急 交通 控 制点 ， 以保 证城 市 中某些 地点 发生 突发 事件 时 ， 应 的服务 设施点 能在规 定 的时 间 内 相
ｏ ｕ ｉｎａ ｙ ｇ ｍ ｅ ｔ ｅ ｒ ． Ｔｈ ｘ ｅ ｉ ｎ ｓ ｓ ｗ ｈ ｌｏ ｉｈ ｉ ｅ ｓｂ ｅ ａ ｄ ｅｆ ｃｉ ｅ ｌ ｔｏ ｒ ａ ｈ ｏ ｙ ｅ ｅ ｐ ｒｍｅ ｔ ｈｏ ｔ ｅ ａ ｇ ｒｔ ｍ ｓｆ ａ ｉ ｌ ｎ ｆｅ ｔｖ ．
Ｋｅｙ ｗｏｒ ｄｓ： ｐ ｒ ｔ ｎ ｅ ｅ ｒ ｈ；ｑ ｎ ｕ ｃ ｍｐ ｔｎ ｏ ｅａｉ ｓｒｓａｃ ｏ ｕａ ｔ ｍ ｏ ｕ ｉ ｇ；ｃ ｍｐ ｔｔｖ ｅ ｉｉｎ；ｅ ｒ ｅ ｃ ａ ｉｉ ｏ ａｉｎ ｏ ｅｉｉｅ ｄ ｃ ｓｏ ｍｅ ｇ ｎ ｙ ｆ ｃｌ ｙ ｌｃ ｔｏ ｔ
关 键 词 ： 筹 学 ； 子计 算 ； 争 决 策 ； 急 设 施 选 址 运 量 竞 应
ＬＩ Ｙｏ ｇ 一。 ＭＡ ａ ｇ Ｕ ｎ Ｌｉｎ ， ＮＩ ＮＧ — ｉ ｇ Ａｉｂ ｎ 。
（ ．ｃｏｌｆＭ ｎ ｇｒ ｎ，Ｕ ｉｒｔ ｈ ｎ ｈｉ ｏ ｃ ｎｅａ ｄＴｃｎ ｌ ｙ Ｓａ ｇ ａ ２０ ９ ， ｈｎ ； ． ｅａｔ １Ｓｈ ｏ ｏ ａ ａ ｅｅ ｔ ｎ ｅ ｉ ｏ ａｇ ａ ｆｒＳｉ ｃ ｎ ｅｈｏ ｇ ， ｈ ｎｈ ｉ ００３ Ｃ ｉ ２ Ｄ ｐ ｒ ａ ｖ ｓｙ ｆＳ ｅ ｏ ａ —
０ 引 言
应 急 设施 选 址是 当今 深受 关 注的一 个重 要 的研究 方 向 ， 直接 影 响到应 对 突 发 事 件 的实 效 性 … 。如 在 城 市 规划 建设 中 ， 策者 往往 要决定 一 些公共 紧急 服 务设 施 点 的优化 选 址 问题 ， １０出警 中心 、 防大 决 如 １ 消 队 、 救 中心 、 急 交通 控 制点 ， 以保 证城 市 中某些 地点 发生 突发 事件 时 ， 应 的服务 设施点 能在规 定 的时 间 内 相
ｏ ｕ ｉｎａ ｙ ｇ ｍ ｅ ｔ ｅ ｒ ． Ｔｈ ｘ ｅ ｉ ｎ ｓ ｓ ｗ ｈ ｌｏ ｉｈ ｉ ｅ ｓｂ ｅ ａ ｄ ｅｆ ｃｉ ｅ ｌ ｔｏ ｒ ａ ｈ ｏ ｙ ｅ ｅ ｐ ｒｍｅ ｔ ｈｏ ｔ ｅ ａ ｇ ｒｔ ｍ ｓｆ ａ ｉ ｌ ｎ ｆｅ ｔｖ ．
Ｋｅｙ ｗｏｒ ｄｓ： ｐ ｒ ｔ ｎ ｅ ｅ ｒ ｈ；ｑ ｎ ｕ ｃ ｍｐ ｔｎ ｏ ｅａｉ ｓｒｓａｃ ｏ ｕａ ｔ ｍ ｏ ｕ ｉ ｇ；ｃ ｍｐ ｔｔｖ ｅ ｉｉｎ；ｅ ｒ ｅ ｃ ａ ｉｉ ｏ ａｉｎ ｏ ｅｉｉｅ ｄ ｃ ｓｏ ｍｅ ｇ ｎ ｙ ｆ ｃｌ ｙ ｌｃ ｔｏ ｔ
关 键 词 ： 筹 学 ； 子计 算 ； 争 决 策 ； 急 设 施 选 址 运 量 竞 应
运筹学作业-王程130404026
运筹学作业王程信管1302130404026目录运筹学作业 (1)第一章线性规划及单纯形法 (3)第二章线性规划的对偶理论与灵敏度分析 (24)第三章运输问题 (53)第四章目标规划 (63)第五章整数规划 (73)第六章非线性规划 (85)第七章动态规划 (94)第八章图与网络分析 (97)第九章网络计划 (99)第一章 线性规划及单纯形法1.1分别用图解法和单纯形法求下列线性规划问题，⑴指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解；⑵当具有限最优解时，指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。
121212121min 23466 s.t.324,0z x x x x x x x x =++≥⎧⎪+≥⎨⎪≥⎩（） 1212121,22max 3222s.t.34120z x x x x x x x x =++≤⎧⎪+≥⎨⎪≥⎩（）121212123max 105349 s.t.528 ,0z x x x x x x x x =++≤⎧⎪+≤⎨⎪≥⎩（） 121212124max 5622 s.t.232,0z x x x x x x x x =+-≥⎧⎪-+≤⎨⎪≥⎩（）解：⑴图解法：当212133x x z =-经过点6155（，）时，z 最小，且有无穷多个最优解。
⑵图解法：1x该问题无可行解。
⑶图解法：当21125x x z =-+经过点312（，）时，z 取得唯一最优解。
单纯形法：在上述问题的约束条件中分别加入松弛变量34,x x ， 化为标准型：12341231241234max 10+500349s.t.528,,,0z x x x x x x x x x x x x x x =++++=⎧⎪++=⎨⎪≥⎩由线性规划问题的标准型可列出单纯初始形表逐步迭代，计算结果如下表所示：**33(,1,0,0),10512022(0,0,9,8)821(,0,,0)553(1,,0,0)2T T T T X Z X O X C X B ==⨯+⨯====（0）（1）（2）单纯形表的计算结果表明：单纯形表迭代的第一步得，表示图中原点（0,0）单纯形表迭代的第二步得，表示图中点单纯形表迭代的第三步得，表示图中点⑷图解法：当215166x x z =-经过点2,2（）时，z 取得唯一最优解。
第1章 线性规划基本性质
1. X1≥0, X2 ≥0 2. 2X1 + 3X2 ≤ 100 3. 4X1 + 2X2 ≤ 120
所有约束条件的的交集为R.
A B R
10 60
现在,问题变为在R内找一点, O 使目标函数值最大.如何找?…
C
20 30 40 50
Ｘ1
§1.2 线性规划的图解法
Ｘ2
（三）目标函数的图形表示 Z = 6X1 + 4X2 将上式改写： X2 ＝－3X1/2 ＋ Z/4 令Z为参量，使其取不同 的值，则得到以－3/2为斜率的 一族平行等值线. 如令: 60, 则经过点(10,0)和(0,15); Z=0, 则经过原点; Z=120,则经过点(20,0)和(0,30);
0.8X1 + X2≥1.6 X1 X2 ≤2 ≤1.4
X1 ≥0, X2 ≥0
§1.1 线性规划的一般模型
所谓线性规划问题： 就是求一组变量 ( x1 , x2 , , xn ) 的值，它们 在满足一组线性等式或不等式的限制条件下，使某 一线性函数的值达到极大或极小。而线性规划就是 研究并解决这类问题的一门理论和方法。 请问在企业中有哪些问题属于线性规划问题？
§1.2 线性规划的图解法
maxZ = 6X1 + 4X2 2X1 + 3X2 ≤ 100 --① 4X1 + 2X2 ≤ 120 --② X1≥0, X2 ≥0 （一）建立坐标系 （二）约束条件的图形表示
Ｘ2
60 50 40 30 20 10
两个概念:
1.可行解:满足约束条件的点. 2.可行域:全部可行解的集合, 即区域OABCO,用R表示.
X1 ≥0, X2 ≥0
§1.1 线性规划的一般模型
基于遗传算法的应急物流多设施选址模型研究
ａ ｄ ｓｆ ｔ ， ｎ ｏ ｖ ｒ ｎ ｈ ｓ ｏ ｄ ｃ ａ ａ ｔｒｓｉｓｔ ｎ ｉ ｔｇ ａｅ ｏ ｄ ｗｅｇ ｔ． ｎ ｔ ｉ ｗａ ｔ ｅ ｐ ａ ｔ ａ ｅ ｒ ｅａ ｏ ｔ ｈ ｓｍｏ ｅ ｎ ａｅｙ ａ ｄ ｃ ｎ ｅｔ ｇ ｔ ｏ ｅ ｒａ ｈ ｒｃ ｅ ｔ ｏ ａ ｎｅ ｒ ｔｄ ｒ ａ ｉ ｈｓ Ｉ ｈ ｓ ｙ， ｒ ｃｉ ｌｄ ｇ ｅ ｂ ｕ ｉ ｉ ｉ ｃ ｈ ｃ ｔ ｄｌ ｗｉ ｅ ｉ ｃ ｅ ｓ ｄ Ｇ ｎ ｔ ｌｏｉ ｍ ｓｕ ｅ ｏ ｓ ｌ ｙ ｔ ｅ ｐ ｏ ｌ ｍ ｓ ｌｉ ｇ ｐ ｏ ｅ ｓ ＡｔＬ ｓ ， ｅ ｍｏ ｅ ｓ ｖ ｌ ａ ｅ ｙ ａ ｘ ｍｐ ｅ ｌ ｂ ｎ ｒ ａ ｅ ． ｅ ｅ ｉ ａｇ ｒ ｈ ｉ ｓ ｄ ｔ ｉ ｉ ｒ ｂ ｅ ｏ ｖｎ ｒ ｃ ｓ ． ａ ｔ ｔ ｄ ｌ ａ ｉ ｔｄ ｂ ｎ ｅ ａ ｌ． ｌ ｃ ｔ ｍｐ ｆ ｈ ｈ ｉ ｄ Ｔ ｅ ｒｓ ｌ ｓ ｏ ｓ ｔ ａ ｅ ｍｏ ｅ Ｓ ｒａ ｏ ａ ｌ ． ｈ ｅ ｕｔ ｈ ｗ ｈ ｔｔ ｄ ｌｉ ｅ ｓ ｎ ｂ ｅ ｈ
是 十分必要 的 。
应 急物流设施选址属于应急 系统选址 问题 ， 应急系统选址 问题 是一个广受关 注的研 究方 向 ， 内外众 多 国
学者在此方面取得 了重要 的研 究成 果 Ｊ大多 数研 究 都是 通 过成 本 最小 化 或距 离最 小化 模 型来 确 定 选 ，
收稿 日期 ： １ ～ ２ ０ ２ ０ ０ —１ ０ 基金项 目： 国家社会科学基金资助项 目 ０ ＣＹ １） （９ Ｊ０２ 作者简 介 ： 刘洪娟， 讲师， 女， 博士生， 主要从事物流、 供应链理论研究。
基于 遗传 算法 的应 急 物 流 多设 施 选 址模 型研 究
应用运筹学补充练习题参考答案
+（333X22+335X23+317X24－325Y2）＋（352X33+327X34－348Y3）
+（344X44－340Y4）
s.t:Y1≤200 000
Y1－X11－X12－X13－X14=0
X11≤100 000
X12+X13+X14+Y2≤200 000
Y2－X22－X23－X24=0
X12+X22≤140 000
X22*=，X23*=，X24*=，Y2*= ,
X33*=，X34*=，Y3*= ,
X44*=，Y4*= ,Z*=
9、对以下线性规划问题：
MinZ＝2X1+3X2+5X3+2X4+3X5
s.t. X1+X2+2X3+X4+3X5≥4
2X1X2+3X3+X4+X5≥3
X1,X2,X3,X4,X5≥ 0
设按第j种截法截Xj根圆钢，则相应的线性规划模型为：
目标函数：MinZ= Xj
s.t:X1+X2≥100
X1+2X3+X4≥200
2X2+X3+2X4+4X5≥400
xj≥0且为整数（j=1,2.....,5）
EXCEL求解最优解结果：X1*=0，X2*=100，X3*=100,X4*=0 ,X5*=25, Z*=225
《应用运筹学》补充练习题参考答案
1、某商店要制定明年第一季度某种商品的进货和销售计划，已知该店的仓库容量最多可储存该种商品500件，而今年年底有200件存货。该店在每月月初进货一次。已知各个月份进货和销售该种商品的单价如下表所示：
+（344X44－340Y4）
s.t:Y1≤200 000
Y1－X11－X12－X13－X14=0
X11≤100 000
X12+X13+X14+Y2≤200 000
Y2－X22－X23－X24=0
X12+X22≤140 000
X22*=，X23*=，X24*=，Y2*= ,
X33*=，X34*=，Y3*= ,
X44*=，Y4*= ,Z*=
9、对以下线性规划问题：
MinZ＝2X1+3X2+5X3+2X4+3X5
s.t. X1+X2+2X3+X4+3X5≥4
2X1X2+3X3+X4+X5≥3
X1,X2,X3,X4,X5≥ 0
设按第j种截法截Xj根圆钢，则相应的线性规划模型为：
目标函数：MinZ= Xj
s.t:X1+X2≥100
X1+2X3+X4≥200
2X2+X3+2X4+4X5≥400
xj≥0且为整数（j=1,2.....,5）
EXCEL求解最优解结果：X1*=0，X2*=100，X3*=100,X4*=0 ,X5*=25, Z*=225
《应用运筹学》补充练习题参考答案
1、某商店要制定明年第一季度某种商品的进货和销售计划，已知该店的仓库容量最多可储存该种商品500件，而今年年底有200件存货。该店在每月月初进货一次。已知各个月份进货和销售该种商品的单价如下表所示：
第8章松弛算法
拉 格 朗 日 松 弛
LR :
SLR {x Z | Bx d}
n
Z LR ( ) min{cT x T (b Ax)} Bx d（简单约束） , s.t. n x Z .
定理7.2.1 LR同下整数规划问题(7.2.1)有相同 的复杂性,且若IP可行解非空，则:
T T T z ( ) min( c A ) x b 证明: LR xQ
min (cT T A) x T b
xCon ( Q )
min [cT x T (b Ax)]
xCon ( Q )
k 设Con(Q)的极点为{x | k K},极方向为 {r j | j J }则:
7.1 基于规划论的松弛方法
整数规划模型:
Z IP min cT x Ax b, s.t. n x Z .
7.1.1
松弛的定义（7.1.1）: 问题 RP :
Z R min zR ( x)
xSR
满足下列性质时,称为7.1.1的一个松弛(relaxation).
上述问题等价于: zLD max
cT x k T (b Ax k ) , k K s.t. (cT T A)r j 0, j J 0
整理得:
z LD max
T ( Ax k b) cT x k , k K
s.t.
( SC )
松弛问题:
( LRSC )
松弛模型:
( LRSC )
n m zLRSC min d j x j i j 1 i 1 j 1 n s.t.x j {0,1}, 0
LR :
SLR {x Z | Bx d}
n
Z LR ( ) min{cT x T (b Ax)} Bx d（简单约束） , s.t. n x Z .
定理7.2.1 LR同下整数规划问题(7.2.1)有相同 的复杂性,且若IP可行解非空，则:
T T T z ( ) min( c A ) x b 证明: LR xQ
min (cT T A) x T b
xCon ( Q )
min [cT x T (b Ax)]
xCon ( Q )
k 设Con(Q)的极点为{x | k K},极方向为 {r j | j J }则:
7.1 基于规划论的松弛方法
整数规划模型:
Z IP min cT x Ax b, s.t. n x Z .
7.1.1
松弛的定义（7.1.1）: 问题 RP :
Z R min zR ( x)
xSR
满足下列性质时,称为7.1.1的一个松弛(relaxation).
上述问题等价于: zLD max
cT x k T (b Ax k ) , k K s.t. (cT T A)r j 0, j J 0
整理得:
z LD max
T ( Ax k b) cT x k , k K
s.t.
( SC )
松弛问题:
( LRSC )
松弛模型:
( LRSC )
n m zLRSC min d j x j i j 1 i 1 j 1 n s.t.x j {0,1}, 0
组合最优化问题及其求解优化算法
组合最优化问题最基本的特点就是变量是离散的, 由此导致其数学模型中的目标函数和约束函数在其可行域内是也是离散的。
在现实世界中，许多的实际问题本质上是离散事件的而不是连续事件，都可归结为组合最优化问题。
这类问题在理论上多数都属于NP难问题，NP类问题仍属于可计算问题，即存在算法来求解。
求解这类组合最优化问题方法分为精确算法和近似算法两类。
常用的精确算法有动态规划、分支定界和枚举等。
精确算法只能解决一些小规模问题，当求解小规模组合优化问题时可以用这类精确算法在较短的时间内得到最优解。
当求解大规模组合优化问题时，理论上可以得到问题的最优解，但由于计算量太大，所以使用精确算法并不可行。
利用精确算法求解NP-hard组合优化问题时，即使能得到最优解，但所需要的计算时间过长，在实际问题中难以直接应用。
近似算法是指在合理的计算时间内找到一个近似的最优解。
近似算法虽然求解速度较快，但并不能保证得到问题的全局最优解。
近似算法分为基于数学规划（最优化）的近似算法、启发式算法和基于智能优化的近似算法。
1) 基于数学规划（最优化）的近似算法是根据对问题建立的数学规划模型，运用如拉格朗日松弛、列生成等算法以获得问题的近似解，是以数学模型为基础，采用列生成、拉格朗日松弛和状态空间松弛等求解问题。
拉格朗日松弛（LR）算法求解问题的主要思想是分解和协调。
首先对于NP难的优化问题，其数学模型须具有可分离性。
通过使用拉格朗日乘子向量将模型中复杂的耦合约束引入目标函数，使耦合约束解除，形成松弛问题，从而分解为一些相互独立的易于求解的子问题，设计有效的算法求得所有子问题的最优解。
利用乘子的迭代更新来实现子问题解的协调。
列生成(Column generation, CG)算法是一种已经被认可的成功用于求解大规模线性规划、整数规划及混合整数规划问题的算法。
与智能优化算法相比，基于数学规划的近似算法的优点是通过建立问题的数学模型，松弛模型中难解的耦合约束或整数约束，得到的松弛问题的最优解可以为原问题提供一个下界。
运筹学(本)_201906_模拟卷2_答案
华东理工大学网络教育学院（全部答在答题纸上，请写清题号，反面可用。
试卷与答题纸分开交）运筹学（本）_201906_模拟卷2_答案一、判断题（共5题,每题2分,共10分）1. 目标规划中正偏差变量应取正值，负偏差变量应取负值。
（）（2分）( ) .★标准答案：错误2. 动态规划的维数是由决策变量的个数决定的（2分）( ).★标准答案：错误3. 在其他费用不变的条件下，随着单位存储费的增加，最优订货批量也相应增加（2分）( ).★标准答案：错误4. 用分支定界法求解一个整数规划问题，若已求得一个不违反任何整数约束的解，则停止分支（2分）( ).★标准答案：错误5. 指派问题效率矩阵的每个元素都乘上同一个不为0的常数k，将不影响最忧解。
（）（2分） ( ).★标准答案：错误二、单选题（共5题,每题3分,共15分）1. Kruskal算法属于哪种思路的方法（）。
（3分）A.破圈B.避圈C.智能搜索D.枚举.★标准答案：A2. 最优性原理是1951哪位数学家提出的（）。
（3分）nd DoigB.BellmanC.CooperD.Dantzig.★标准答案：B3. 1931谁设计出了第一张投入产出表（）。
（3分）A.ErlangB.HarrisC.ShewhartD.Leontief .★标准答案：D4. 1924年谁给出了第一张质量控制图（）。
（3分）A.ErlangB.NeumannC.ShewhartD.Dantzig.★标准答案：C5. 1947年谁得到了线性规划的单纯形法（）。
（3分）A.ErlangB.HarrisC.ShewhartD.Dantzig.★标准答案：D三、问答题（共5题,每题15分,共75分）1.（15分）★标准答案：2. （15分）★标准答案：3. 某农场有100公顷土地及25万元资金可用于发展生产。
农场劳动力情况为秋冬季4500人日，春夏季6000人日，如劳动力本身过剩可外出打工，春夏季收入为20元／人日，秋冬季12元／人日。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
２０１３年３月 Ｍａｒｃｈ，２０１３ 运筹学学报 Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ Ｔｒａｎｓａｃｔｉｏｎｓ 第１７卷第１期 Ｖｌ０１．１７ Ｎｏ．１
－…● ●・● ＿●● ＾ ｔＳｉｃｒｉｔｅｒｉａ ａＤｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｔ－ｏｒ ｔｈｅ ｌｏｗｅｒ－－ｂｏｕｎｄｅｄ ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ —ｈ ｐｅｎａｌｔｉｅｓ ａｎｄ ＳＯｆｔ—ｃａｐａｃｉｔｙｗｉｔｈ ｐｅｎａｌｔｌｅｓ ａｎｄ ＳＯ ｃａｐａｃｉｔｙ木一 币 ＬＩ Ｇａｉｄｉ１，十ＷＡＮＧ ＺｈｅｎＩ ＷＵ ＹｕｌｉｎＩ Ａｂｓｔｒａｃｔ Ｗｌｅ ｓｔｕｄｙ ｔｈｅ ｌｏｗｅｒ—ｂｏｕｎｄｅｄ ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ ｗｉｔｈ ｐｅｎａｌｔｉｅｓ （ＬＢＦＬＰ）ａｎｄ ｔｈｅ ｓｏｆｔ—ｃａｐａｃｉｔｙ ＬＢＦＬＰ．Ｆｏｒ ｔｈｅ ＬＢＦＬＰ，ｗｅ ｐｒｅｓｅｎｔ ａｎ ｕｐｄａｔｅｄ ｂｉｃｒｉｔｅｒｉａ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｗｈｉｃｈ ｍａｉｎｔａｉｎｓ ｔｈｅ ｓａｍｅ ｐｅｒｆｏｒｍａｎｃｅ ｆａｃｔｏｒ １ｌ＋一ａ
ｒｎ ａｓ ｔｈａｔ ｆｏｒ
ｔｈｅ ｐｒｏｂｌｅｍ ｗｉｔｈｏｕｔ ｐｅｎａｌｔｉｅｓ ｉｎ Ｈｉｅｒａｒｃｈｉｃａｌ ｐｌａｃｅｍｅｎｔ ａｎｄ ｎｅｔｗｏｒｋ ｄｅｓｉｇｎ ｐｒｏｂｌｅｍｓ （Ｇｕｈａ Ｓ，Ｍｅｙｅｒｓｏｎ Ａ，Ｍｕｎａｇａｌａ Ｋ．Ｈｉｅｒａｒｃｈｉｃａｌ ｐｌａｃｅｍｅｎｔ ａｎｄ ｎｅｔｗｏｒｋ ｄｅｓｉｇｎ ｐｒｏｂｌｅｍｓ ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆＦｏｕｎｄａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２０００：８９２３２８，ＤＯＩ：１０．１ｌ０９／ＳＦＣ－ ｓ．２０００．８９２３２８）ａｎｄ Ｂｕｉｌｄｉｎｇ ｓｔｅｉｎｅｒ ｔｒｅｅｓ ｗｉｔｈ ｉｎｃｏｍｐｌｅｔｅ ｇｌｏｂａｌ ｋｎｏｗｌｅｄｇｅ（Ｋａｒｇｅｒ Ｄ Ｒ，Ｍｉｎｋｏｆｆ Ｍ．Ｂｕｉｌｄｉｎｇ ｓｔｅｉｎｅｒ ｔｒｅｅｓ ｗｉｔｈ ｉｎｃｏｍｐｌｅｔｅ ｇｌｏｂａｌ ｋｎｏｗｌｅｄｇｅ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ Ｆｏｕｎｄａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２０００：８９２３２９，ＤＯＩ：１０．１１０９／ＳＦＣＳ．２０００．８９２３２９）． Ｗｅ ｆｕｒｔｈｅｒ ｅｘｔｅｎｄ ｔｈｉｓ ｒｅｓｕｌｔ ｔｏ ｔｈｅ ｓｏｆｔ．ｃａｐａｃｉｔａｔｅｄ ＬＢＦＬＰ ａｎｄ ａｃｈｉｅｖｅ ａ ｐｅｒｆｏｒｍａｎｃｅ ｆａｃｔｏｒ ｔｗｉｃｅ ａｓ ｍｕｃｈ ａｓ ｔｈａｔ ｆｏｒ ＬＢＦＬＰ． Ｋｅｙｗｏｒｄｓ ｌｏｗｅｒ—ｂｏｕｎｄｅｄ ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ，ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ，ｂｉｃｒｉｔｅｒｉａ ａｌ— ｇｏｒｉｔｈｍ． Ｃｈｉｎｅｓｅ Ｌｉｂｒａｒｙ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ Ｏ２２１．４
２０１０ Ｍａｔｈｅｍａｔｉｃｓ Ｓｕｂｊｅｃｔ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ９０Ｃ３０
带有惩罚和软容量约束的下界设施选址 问题的双标准近似算法研究 李改弟 ，十 王真１ 吴裕林
摘要研究带惩罚和软容量约束的下界设施选址问题．扩展Ｇｕｈａ等ｆＧｕｈａ Ｓ，Ｍｅｙｅｒｓｏｎ Ａ，Ｍｕｎａｇａｌａ Ｋ．Ｈｉｅｒａｒｃｈｉｃａｌ ｐｌａｃｅｍｅｎｔ ａｎｄ ｎｅｔｗｏｒｋ ｄｅｓｉｇｎ ｐｒｏｂｌｅｍｓ ｆＣ１／／Ｐｒｏｃｅｅｄｉｎｇｓ ０．，Ｆｏｕｎｄａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２０００：８９２３２８，ＤＯＩ：１０．１１０９／ＳＦＣＳ．２０００．８９２３２８） 和Ｋａｒｇｅｒ等（Ｋａｒｇｅｒ Ｄ Ｒ，Ｍｉｎｋｏｆｆ Ｍ．Ｂｕｉｌｄｉｎｇ ｓｔｅｉｎｅｒ ｔｒｅｅｓ ｗｉｔｈ ｉｎｃｏｍｐｌｅｔｅ ｇｌｏｂａｌ ｋｎｏｗｌｅｄｇｅ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｆｏｕｎｄａｔｉｏｎｓ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，２０００：８９２３２９，ＤＯＩ： ｌＯ．１１０９／ＳＦＣＳ．２０００．８９２３２９）的工作到带有惩罚的下界约束设施选址问题，提出了一个新的 双标准近似算法，得到了同样的近似比÷ ｐ．进一步考虑带惩罚和软容量约束的下界设施选
收稿日期：２０１１年ｌ１月１３日 Ｔｈｅ ｒｅｓｅａｒｃｈ ｉｓ ｓｕｐｐｏｒｔｅｄ ｂｙ Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆＣｈｉｎａ（Ｎｏｓ．１１２０１０１３，１１０７１２６８）． １．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ，Ｂｅｉｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ １００１２４，Ｃｈｉｎａ；北京 工业大学应用数理学院，北京１００１２４ ｔ通讯作者Ｃｏｒｒｅｓｐｏｎｄｉｎｇ ａｕｔｈｏｒ，Ｅｍａｉｌ：ｌｉｇｄ＠ｂｊｕｔ．ｅｄｕ．ｃａ １ｌ８ ＬＩ Ｇａｉｄｉ．ＷＡＮＧ Ｚｈｅｎ．ＷＵ Ｙｕｌｉｎ １７卷 址问题，得到了近似比为２÷ ｐ的双标准近似算法． 关键词下界约束设施选址，近似算法，双标准算法 中图分类号Ｏ２２１．４ ２０１０数学分类号９０Ｃ３０
０ Ｉｎｔｒ０ｄｕｃｔｉ０ｎ Ｔｈｅ ｆｉｅｌｄｓ ｏｆ ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ ｆＦＬＰ１ ａｎｄ ｉｔｓ ｖａｒｉａｎｔｓ ｈａｖｅ ｂｅｅｎ ｅｘｔｅｎｓｉｖｅｌｙ ｉｎｖｅｓｔｉｇａｔｅｄ ｉｎ ｔｈｅ ｏｐｅｒａｔｉｏｎｓ ｒｅｓｅａｒｃｈ，ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ ａｎｄ ｍａｎａｇｅｍｅｎｔ ｓｃｉｅｎｃｅ ｌｉｔｅｒａｔｕｒｅｓ （ｅ．ｇ．［１－１０］）。Ｔｈｅ ｍｏｓｔ ｂａｓｉｃ ＦＬＰ ｉｓ ｔｈｅ ｕｎｃａｐａｃｉｔａｔｅｄ ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ（ＵＦＬＰ）， ｆｏｒ ｗｈｉｃｈ，ｔｈｅ ｆｉｒｓｔ ｃｏｎｓｔａｎｔ ｆａｃｔｏｒ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｈａｓ ｂｅｅｎ ｏｂｔａｉｎｅｄ ｂｙ Ｓｈｍｏｙｓ ｅｔ ａｌｌ１１１ ｕｓｉｎｇ ＬＰ－ｒｏｕｎｄｉｎｇ ｔｅｃｈｎｉｑｕｅ．Ｓｉｎｃｅ ｔｈｅｎ ａ ｇｒｅａｔ ｄｅａｌ ｏｆ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ
ｗｉｔｈ ｄｉｆｆｅｒｅｎｔ ｔｅｃｈｎｉｑｕｅｓ ｈａｖｅ ｂｅｅｎ ｐｒｏｐｏｓｅｄ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ａｐｐｒｏｘｉｍａｔｉｏｎ ｆａｃｔｏｒ．Ｔｈｅ ｃｕｒｒｅｎｔ ｂｅｓｔ ｆａｃｔｏｒ ｆｏｒ ｔｈｅ ＵＦＬＰ ｉｓ １．４８８ ｄｕｅ ｔｏ Ｌｉ［１ ．ｗｈｉｃｈ ｉｍｐｒｏｖｅｓ ｔｈｅ ａｐｐｒｏｘｉｍａｔｉｏｎ
ｆａｃｔｏｒ １．５０ ｏｆ Ｂｙｒｋａ ａｎｄ Ａａｒｄａｌ［１ａ］．Ｆｕｒｔｈｅｒｍｏｒｅ．Ｇｕｈａ ａｎｄ Ｋｈｕｌｌｅｒ［１４］ｐｒｏｖｅｄ ｔｈａｔ ｔｈｅ
ａｐｐｒｏｘｉｍａｔｉｏｎ ｆａｃｔｏｒ ｃａｎ ｎｏｔ ｂｅ ｂｅｔｔｅｒ ｔｈａｎ １．４６３ ｕｎｌｅｓｓ Ｐ＝ⅣＰ． Ａｍｏｎｇ ｉｔｓ ｍａｎｙ ｖａｒｉａｎｔｓ，ｏｕｒ ｗｏｒｋ ｉｓ ｐａｒｔｉｃｕｌａｒｌｙ ｒｅｌａｔｅｄ ｔｏ ｔｈｅ ｌｏｗｅｒ—ｂｏｕｎｄｅｄ ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ（ＬＢＦＬＰ）．Ｔｈｅ ＬＢＦＬＰ ｉｎｃｌｕｄｅｓ ａｎ ａｄｄｉｔｉｏｎａｌ ｓｅｔ ｏｆ ｃｏｎｓｔｒａｉｎｔｓ，ｗｈｉｃｈ ｒｅｑｕｉｒｅｓ ｔｈａｔ ｅａｃｈ ｏｐｅｎ ｆａｃｉｌｉｔｙ ｍｕｓｔ ｂｅ ｓｅｒｖｉｎｇ ａｔ ｌｅａｓｔ Ｂ ｃｌｉｅｎｔｓ．Ｓｕｃｈ ｐｒｏｂｌｅｍ ｒｅｄｕｃｅｓ ｔｏ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ＦＬＰ ｉｆ Ｂ ｄｒｏｐｓ ｔｏ ０．Ｔｈｅ ＬＢＦＬＰ ｗａｓ ｉｎｔｒｏｄｕｃｅｄ ｉｎｄｅｐｅｎｄｅｎｔｌｙ ｂｙ Ｇｕｈａ ｅｔ ａｌｌ１５】ａｎｄ ｂｙ Ｋａｒｇｅｒ ａｎｄ Ｍｉｎｋｏｆｆ［１６］ｆ０ｒ ｓｏｌｖｉｎｇ ｃｅｒｔａｉｎ ｎｅｔｗｏｒｋ ｄｅｓｉｇｎ ｐｒｏｂｌｅｍｓ．Ｔｈｅｙ
ｂｏｔｈ ｇａｖｅ ｂｉｃｒｉｔｅｒｉａ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ ＬＢＦＬＰ．Ｔｈｅｓｅ ｂｉｃｒｉｔｅｒｉａ ａｌｇｏｒｉｔｈｍｓ ｇｅｎｅｒａｔｅｄ ａ ｃｏｎｓｔａｎｔ ｆａｃｔｏｒ Ｐ ｏｆ ｔｈｅ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｃｏｓｔ，ｂｕｔ ｖｉｏｌａｔｅｄ ｔｈｅ ｌｏｗｅｒ ｂｏｕｎｄ ｃｏｎ— ｓｔｒａｉｎｔ ｗｉｔｈ ａ ｃｏｎｓｔａｎｔ ｆａｃｔｏｒ ｏ１．Ｒｅｃｅｎｔｌｙ，Ｓｖｉｔｋｉｎａ［１７】ｐｒｅｓｅｎｔｅｄ ａ ｃｏｎｓｔａｎｔ ａｐｐｒｏｘｉｍａｔｉｏｎ ｒａｔｉｏ ｆｏｒ ｔｈｅ ｌｏｗｅｒ—ｂｏｕｎｄｅｄ ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ，ｗｈｉｃｈ ｉｓ ｔｈｅ ｆｉｒｓｔ ｒｅａｌ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｗｅ ａｒｅ ｉｎｔｅｒｅｓｔｅｄ ｉｎ ｔｗｏ ｄｉｆｆｅｒｅｎｔ ｖａｒｉａｎｔｓ ｔｈａｔ ａｒｅ ｂｏｔｈ ｒｅｌｅｖａｎｔ ｔｏ ｔｈｅ ＬＢＦＬＰ．Ｔｈｅ ｆｉｒｓｔ ｖａｒｉａｎｔ ｉｓ ｔｈｅ ＬＢＦＬ ｗｉｔｈ ｐｅｎａｌｔｉｅｓ ＬＢＦＬＰ．Ｔｈｉｓ ｐｒｏｂｌｅｍ ｄｏｅｓ ｎｏｔ ｒｅｑｕｉｒｅ ｔｈａｔ ｅａｃｈ ｃｌｉｅｎｔ ｓｈｏｕｌｄ ｂｅ ａｓｓｉｇｎｅｄ ｔｏ ａｎ ｏｐｅｎ ｆａｃｉｌｉｔｙ．Ｉｎｓｔｅａｄ，ｉｔ ｃａｎ ｂｅ ｒｅｊｅｃｔｅｄ ｂｙ ｐａｙｉｎｇ ａ ｐｅｎａｌｔｙ．Ｔｈｅ ＵＦＬＰ ｗｉｔｈ ｐｅｎａｌｔｉｅｓ ｗａｓ ｆｉｒｓｔ ｓｔｕｄｉｅｄ ｂｙ Ｃｈａｒｉｋａｒ ｅｔ ａｌｌ１８Ｊ，ｗｈｏ ｇａｖｅ ａ ｐｒｉｍａｌ—
ｄｕａｌ ３一ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ．Ｌａｔｅｒ，Ｘｕ ａｎｄ Ｘｕ［１９，２０］ｉｍｐｒｏｖｅｄ ｔｈｅ ｒａｔｉｏ ｔｏ（２＋２／ｅ）
ａｎｄ １．８５２６ ｕｓｉｎｇ ＬＰ—ｒｏｕｎｄｉｎｇ ａｎｄ ｐｒｉｍａｌ－ｄｕａｌ ｗｉｔｈ ｇｒｅｅｄｙ ａｄｄｉｎｇ ｔｅｃｈｎｉｑｕｅ ｒｅｓｐｅｃｔｉｖｅｌｙ． Ｔｈｅ ｓｅｃｏｎｄ ｖａｒｉａｎｔ ｗｅ ａｒｅ ｉｎｔｅｒｅｓｔｅｄ ｉｎ ｉｓ ｔｈｅ ｓｏｆｔ—ｃａｐａｃｉｔｙ ＬＢＦＬＰ ｆＳＣＬＢＦＬＰ１．Ｔｈｉｓ ｐｒｏｂｌｅｍ ｒｅｑｕｉｒｅｓ ｔｈａｔ ｅａｃｈ ｏｐｅｎ ｆａｃｉｌｉｔｙ ｉ ｓｅｒｖｅｓ ａｔ ｍｏｓｔ ｕｉ ｃｌｉｅｎｔｓ ａｎｄ ｔｈｅ ｓａｍｅ ｆａｃｉｌｉｔｙ ｃａｎ ｏｐｅｎ ａｎｙ ｎｕｍｂｅｒ ｏｆ ｔｉｍｅｓ．Ｍａｎｙ ｃｏｎｓｔａｎｔ—ｆａｃｔｏｒ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｈａｖｅ ｂｅｅｎ ｐｒｏｐｏｓｅｄ ｆｏｒ ｔｈｅ ｓｏｆｔ—ｃａｐａｃｉｔｙ ｆａｃｉｌｉｔｙ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ（ＳＣＦＬＰ）．Ｃｈｕｄａｋ ａｎｄ Ｓｈｍｏｙｓ［２１】 ｇａｖｅ ａ ３一ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ＳＣＦＬＰ ｗｉｔｈ ｕｎｉｆｏｒｍ ｃａｐａｃｉｔｉｅｓ ｕｓｉｎｇ ＬＰ—ｒｏｕｎｄｉｎｇ ｔｅｃｈｎｉｑｕｅ．Ｊａｉｎ ａｎｄ Ｖａｚｉｒａｎｉ［２２ｊ ｒｅｄｕｃｅｄ ｔｈｉｓ ｐｒｏｂｌｅｍ ｔｏ ｔｈｅ ＵＦＬＰ ａｎｄ ｏｂｔａｉｎｅｄ ａ ｐｒｉｍａｌ—