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

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