文件名称：论文研究-一个关于求解.pdf
文件大小：487KB
文件格式：PDF
更新时间：2022-10-01 06:48:34
论文研究
对于k-种产品工厂选址问题，有如下描述：存在一组客户和一组可以建立工厂的厂址。现在有k种不同的产品，要求每一个客户必须由k个不同的工厂来提供k种不同的产品，其中每个工厂都只能为客户提供唯一的一种产品。在该问题中，假定建厂费用以及任意两个结点之间的运输费用都为非负，并且任意两个结点之间的运输费用都满足对称和三角不等式关系的性质。问题的要求是要从若干厂址中选择一组厂址来建立工厂，给每个工厂指定一种需要生产的产品，并且给每一个客户提供一组指派使每个客户都能有k个工厂来为其供应这k种不同的产品。对于此类问题，优化目标是最小化建厂费用以及运输费用。论文在假设建厂费用为零的前提下，提出了求解该类问题的一种最坏性能比为3k/2-1的近似算法。