3.
$k$-种产品设施选址问题是指存在一组客户和一组可以建设设施的地址。现有
$k$种不同的产品,每一客户均需要
$k$种不同的产品,且每一设施最多只能生产一种产品。问题的要求是从若干地址中选择一组地址来建立设施,对所要建立的设施指定其生产的产品,并为每一个客户提供一组指派确保每一客户都有
$k$个设施来为其提供
$k$种不同的产品,使得设施建设费用与运输费用之和最小。对于
$k$-种产品设施选址问题,我们通常简写为
$k$-PUFLP,其中,当所有设施建设费用为0时,记为
$k$-PUFLPN。本文对
$k$-PUFLPN进行线性舍入,通过分析最优分数解特殊结构,当
$k\geq 3$时分析算法将
$k$-PUFLPN的近似比从
$\frac{3k}{2}-1$提升到了
$\frac{3k}{2}-\frac{3}{2}$。鲁棒
$k$-种产品设施选址问题是指在该问题中,最多有
$q$个客户可以不被服务。我们首次对无容量限制下建设费用为0时的鲁棒
$k$-种产品选址问题建立模型,当
$k\geq 3$,得到了
$\frac{3k}{2}-\frac{3}{2}$近似算法。对顾客伴有线性惩罚的鲁棒
$k$-种产品设施选址问题,本文同时考虑异常值与惩罚性,利用
$k$-PUFLPN中最优整数解与最优分数解的关系,得到了
$\frac{3k}{2}-\frac{3}{2}$近似算法。
相似文献