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

摘要：

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

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

分类号：TP301.6(计算技术、计算机技术)

资助基金：^A大学生创新创业训练计划项目、202006^B202010060119^D1

在线出版日期：2022-02-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：194-196