带次模惩罚和随机需求的设施选址问题

• 作者: 徐大川 王星
• 来源期刊: 运筹学学报
• 学科: 数学
• 关键词: 次模惩罚 随机需求 近似算法 原始对偶算法
• 年，卷（期）: 2013,（2）
• 页码范围: 1-9
• 页数: 9页
• 分类号: O221.7
• 字数: 5061字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐大川	北京工业大学数理学院	18	30	3.0	4.0
2	王星	杭州电子科技大学理学院	6	11	2.0	3.0