收录：
摘要：
考虑带次模惩罚和随机需求的设施选址问题,目的是开设设施集合的一个子集,把客户连接到开设的设施上并对没有连接的客户进行惩罚,使得开设费用、连接费用、库存费用、管理费用和惩罚费用之和达到最小.根据该问题的特殊结构,给出原始对偶3-近似算法.在算法的第一步,构造了一组对偶可行解；在第二步中构造了对应的一组原始整数可行解,这组原始整数可行解给出了最后开设的设施集合和被惩罚的客户集合.最后,证明了算法在多项式时间内可以完成,并且算法所给的整数解不会超过最优解的3倍.
关键词：
通讯作者信息：
电子邮件地址：
