论文部分内容阅读
自从上个世纪六十年代，设施选址问题的研究在运筹学中已经占据重要位置．无容量约束设施选址问题是最经典的设施选址问题，己证明它是NP-难解问题．在本论文中，我们从近似算法角度研究无容量约束设施选址问题的几个变形． 本论文考虑的无容量约束设施选址问题的几个变形为：带相同要求的凹容错设施选址问题，带服务安装费用的随机设施选址问题，带次模惩罚和随机需求的设施选址问题，软容量约束带随机需求的设施选址问题和度量空间上的厌恶型设施博弈．关于这些问题，我们分别给出每个问题的近似算法及其分析结果． 关于带相同要求的凹容错设施选址问题，我们给出了对偶拟合算法，并通过算法分析得到了1.61近似比和(I.II，1.78)双因子近似比，然后，在对偶拟合算法的基础上，结合同比例缩放和贪婪增广给出一个两阶段算法，把近似比改进到1.52.关于带服务安装费用的随机设施选址问题，在服务安装费用满足一定的假设情形下，我们给出一个基于原始对偶的7一近似算法，关于带次模惩罚和随机需求的设施选址问题，本文给出了原始对偶算法，并分析出近似比为3．关于软容量约束带随机需求的设施选址问题，给出一个基于原始对偶的6-近似算法， 关于度量空间上的厌恶型设施博弈，给出了一个群策略防护确定性机制，近似比为3，并证明了任意群策略防护确定性机制给出的近似比都不会小于3；然后又给出了一个群策略防护随机性机制，近似比为3/2；紧接着，引入度量空间上的一般厌恶型设施博弈，在客户到设施的距离满足一定的假设时，给出了具有3近似比的群策略防护确定性机制． 最后，本论文给出了设施选址问题中一些亟待解决的问题，比如改进无容量约束设施选址问题的上界，凹容错设施选址问题（每个客户的要求不同）的近似算法设计，无假设的度量空间上的一般厌恶型设施选址问题的近似算法设计等．