2-种产品选址问题的计算复杂性浅析

Analysis of Computational Complexity of 2-product Location Problem

产品选址问题是组合优化中一类有重要理论意义和广泛实际背景的问题。问题的要求是要从若干厂址中选择一组厂址来建立工厂，给每个工厂指定一种需要生产的产品，并且给每一个客户提供一组指派使每个客户都能有一组工厂集合来为其供应不同的产品。对于此类问题，我们的优化目标是最小化运输费用。该问题模型在网络设施的安放、网格服务点的分布等诸多方面有着大量的应用。文中对2种产品选址问题的计算复杂性进行了分析。

The product location problem is one kind of important combinatorial optimization problem. The problem is to select a set of facilities to be set up and their designated products and to find an assignment for each client to a set of facilities. The optimal goal of this problem is to minimize the sum of the shipping costs. The product location problem has extensive applications within production management, network communication and computer theory. Assuming that fixed setup cost are zero, we analyze the computational complexity of 2-PUFLPN.