带惩罚的软容量设施选址问题

郭远达 凌锐衡 马倩男 宁萌

【摘要】设施选址问题自20世纪60年代初期以来，在运筹学中一直占据着中心位置。传统设施选址问题要求所有顾客都被服务，这会造成一定的资源浪费，因此可以在模型中设置顾客的惩罚费用，以使得部分顾客不被服务（带惩罚设施选址问题）。另外，可以对模型中开设设施的容量做限制（带容量设施选址问题）。本文将结合以上两种情况建立带惩罚的软容量设施选址模型，通过原始-对偶框架得到4-近似算法，并通过程序验证算法的正确性。

【关键词】软容量设施选址问题  近似比  原始对偶算法

【基金项目】大学生创新创业训练计划项目、202006（编号：202010060119）。

【中图分类号】TP301.6   【文献标识码】A 【文章编号】2095-3089（2021）28-0194-03

一、绪论

设施选址问题的研究目标为开设设施，并且使得设施的开设费用及顾客连接到开设设施上的费用之和最小。设施选址问题是NP-难解问题[1]，除非P=NP，否则设施选址问题不存在多项式时间精确算法，因此本文将采用近似算法。

近似算法是指在多项式时间内给出优化问题的近似优化解的算法。用近似算法得到的解并不是理論上的最优解，而是可行解。目标函数值与最优值之间的比值称为近似比，称近似比为ρ的算法为ρ-近似算法。

无容量设施选址问题（uncapacitated facility location problem，简称UFLP）是设施选址问题中最经典的问题，其特点是开设设施没有容量限制。若每个设施有容量限制且可以多次开设，就称为软容量限制的设施选址问题（Soft capacitated facility location problem，简称SCFLP）。在实际运用中，有时会……