选址问题是组合优化领域中的一类重要问题,它是对于一些网络服务器、核电站或者物流中心等有限且重要的资源进行选址决策,在生产管理与调度,网络通信,理论计算机科学等方面有广泛的应用。本文研究了设施选址中的一类模型:多产品选址模型(K-PUFLP)。Huang和Li(2007)首先提出了一类在度量空间特性下的多产品选址模型,并给出了一个近似比不超过2k-1的启发式算法。本文的主要工作如下:第一章是绪论部分,简单地介绍了选址问题的相关定义、记号及相关知识,描述了多产品选址模型的一些特性。第二章研究了多产品选址问题的整数及线性模型。对于K-PUFLPN(K≥2),提出了一个改进的算法ME,并证明了该算法最坏性能比不超过3/2k-1。另外,对于算法ME求解2-PUFLPN,给出了2是该算法紧界的证明。并讨论了它的线性规划问题的松驰的整数间隙。第三章对两类算法落到树结构上的性能进行了分析和讨论,通过找到一个反例,给出了算法ME的解落到树结构上不是最优解的推理过程。文章末,对工厂选址问题做出总结和研究展望。