选址问题是广泛应用在运筹学和管理科学中的一类重要问题,并在近似算法方面引起了很大的关注。在k-层无容量限制的设施选址问题中,我们假定F为设施的集合,D为顾客的集合,每个顾客的需求是已知的,他需要k个不同的设施为其服务,且每个设施属于不同的层。这里所说的设施没有容量限制,且建造这些设施对应一个建造费用,设施给顾客提供服务时也会对应一个服务费用(连接费用),我们假设这些连接费用满足非负性、对称性和三角不等式。问题的目标是确定在哪里建造设施,以及每个顾客由哪k个设施形成的路径为其服务,才能满足顾客的需求且使总的建造设施的费用和连接费用之和达到最小。无容量限制的设施选址问题属于NP-hard问题,人们已经证明近似算法对于解决长期以来实际中难处理的NP-hard组合优化问题是一个能产生较优解的有效算法。Shmoys首次给出了解决无容量限制的设施选址问题的常数近似算法,该算法基于线性规划随机取整以及Lin和Vitter提出的对偶拟合技术,得到了3.16的近似比。最近Aardal,Chudak,Shmoys又将这一结果进行扩展应用到求解k-层无容量限制的设施选址问题中并得到了最多不超过最优值3倍的结果。由于k-层无容量限制的设施选址问题是NP-hard的,因而对它的研究大部分还是集中在近似算法上,多年来有关k-层无容量限制的设施选址问题的算法研究工作还是非常少见的。因此,结合实践应用,分析k-层无容量限制的设施选址问题,进而设计有效的求解算法成为本文一个重要的研究课题。本文主要研究了k-层无容量限制的设施选址问题以及解决设施选址问题的各种算法,受这些算法的启发,我们设计了解决k-层无容量限制的设施选址问题的一种随机取整算法。利用该算法时,首先将原问题进行松弛求解得到松弛问题的最优解,由松弛问题的最优解通过具体的随机取整算法进而得到原问题的整数解。为了测试这一算法的性能,我们采用数值计算的方法取k=2时用一组算例进行验证,算例的结果表明:1.在所给的算例中,随着顾客和设施个数的不断增加,近似比可能会增大,但总体变化不是很大,即近似比与顾客和设施的总数没有必然的联系;2.该算法所求得的近似比均不超过1.463且得到的原问题的整数解所对应的函数值大部分都能较好地接近松弛问题的最优值,同时相对于Shmoys的随机取整算法,该算法能在很大程度上节省计算时间,提高算法的效率,因此该算法是求解k-层无容量限制的设施选址问题的一种较好的方法。