论文部分内容阅读
本论文考虑带惩罚的有下界约束设施选址问题.在该问题中，每个开放的设施有下界B约束，即服务的客户数目要求不少于B个，而且客户可以不被服务但有惩罚费用.特别的，当B=0且每个客户的惩罚费用足够大时，该问题就退化为标准的设施选址问题.
对于带惩罚的有下界约束无容量设施选址问题，我们利用化归技巧给出双准则算法，得到的解满足下界约束αB(1/3≤α＜1)，解的费用不超过最优值的(?)ρ倍，其中ρ为带惩罚的无容量设施选址问题目前最好的近似比.我们还考虑了上述问题的软容量情形.我们利用拉格朗日松弛技巧给出双准则算法，得到的解满足下界约束αB(1/3≤α＜1)，解的费用不超过最优值的2(?)ρ倍.