关于可靠性设施布局问题的近似算法
设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小。设施布局问题自提出以来,就一直占据着运筹学研究中的中心位置,在理论、算法设计和应用方面得到了广泛研究。随着实际应用的深入,设施布局问题产生了许多相应的变型和扩展。其中,具有可靠性的设施布局问题就是近年来一个热点研究问题。
在现实生活中,受自然灾害,工人罢工,恐怖袭击等因素的影响,修建的设施可能会出现故障,故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性。针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题。现有的可靠性设施布局问题的算法基本都是基于拉格朗日松弛与连续近似方法设计的,虽然对某些实例有较好的效果,但是往往运算时间过长,而且不具有理论上好的近似度。
本文着重讨论可靠性设施布局问题的组合算法设计,主要工作如下:
(1)对经典设施布局问题的各种变型和推广进行了概括总结,并系统地给出了可靠性设施布局问题的数学模型；
(2)对设施布局问题现有的算法和算法设计技巧进行了归纳；分析了现有可靠性设施布局问题的算法——拉格朗日松弛方法和连续近似方法的缺点与不足,提出了该问题组合算法的设计思路；
(3)参考经典设施布局问题的贪心算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法。该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点。这对于之前的可靠性设施布局问题只有数值实验算法,是一个很大的进步。
设施布局;近似算法;贪心算法;原始对偶
中国海洋大学
硕士
运筹学与控制论
方奇志
2011
中文
O221
51
2011-10-31（万方平台首次上网日期，不代表论文的发表时间）