运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2013年
2期
1-9
,共9页
次模惩罚%随机需求%近似算法%原始对偶算法
次模懲罰%隨機需求%近似算法%原始對偶算法
차모징벌%수궤수구%근사산법%원시대우산법
submodular penalties%stochastic demands%approximation algorithm%primal-dual algorithm
考虑带次模惩罚和随机需求的设施选址问题,目的是开设设施集合的一个子集,把客户连接到开设的设施上并对没有连接的客户进行惩罚,使得开设费用、连接费用、库存费用、管理费用和惩罚费用之和达到最小.根据该问题的特殊结构,给出原始对偶3-近似算法.在算法的第一步,构造了一组对偶可行解；在第二步中构造了对应的一组原始整数可行解,这组原始整数可行解给出了最后开设的设施集合和被惩罚的客户集合.最后,证明了算法在多项式时间内可以完成,并且算法所给的整数解不会超过最优解的3倍.
攷慮帶次模懲罰和隨機需求的設施選阯問題,目的是開設設施集閤的一箇子集,把客戶連接到開設的設施上併對沒有連接的客戶進行懲罰,使得開設費用、連接費用、庫存費用、管理費用和懲罰費用之和達到最小.根據該問題的特殊結構,給齣原始對偶3-近似算法.在算法的第一步,構造瞭一組對偶可行解；在第二步中構造瞭對應的一組原始整數可行解,這組原始整數可行解給齣瞭最後開設的設施集閤和被懲罰的客戶集閤.最後,證明瞭算法在多項式時間內可以完成,併且算法所給的整數解不會超過最優解的3倍.
고필대차모징벌화수궤수구적설시선지문제,목적시개설설시집합적일개자집,파객호련접도개설적설시상병대몰유련접적객호진행징벌,사득개설비용、련접비용、고존비용、관리비용화징벌비용지화체도최소.근거해문제적특수결구,급출원시대우3-근사산법.재산법적제일보,구조료일조대우가행해；재제이보중구조료대응적일조원시정수가행해,저조원시정수가행해급출료최후개설적설시집합화피징벌적객호집합.최후,증명료산법재다항식시간내가이완성,병차산법소급적정수해불회초과최우해적3배.
