一类特殊覆盖问题的解构造方法研究  

A Solution Construction Method for Solving a Specified Covering Problem

作　　者：任庆娟[1,2] 许保光[2] 高敏刚[2] 

机构地区：[1]中国科学技术大学管理学院,合肥230026 [2]中国科学院科技政策与管理科学研究所,北京100190

出　　处：《应用数学学报》2014年第6期1056-1067,共12页Acta Mathematicae Applicatae Sinica

摘　　要：本文研究一类特殊覆盖问题,这里的覆盖指覆盖水平,优化目标为最小最大化覆盖水平。通过分析解的特性,本文提出一个解构造方法,该方法在N/(w_1)≥m下,得到原问题的最优解,其他条件下得到与最优解的绝对差异不超过N/w_n★的解,这里w_1和w_n分别是同类物品的最大数量和最小数量,N是物品总数量,m是给定的正整数.This paper deals with a special covering problem with minmax objective function. For this problem we propose an algorithm and prove that under the condition that N/w1≥m, the output of this algorithm is optimal; otherwise the output has an absolute difference at most N/wn between with the optimum, where w1 and wn are the largest and Wn smallest weights of items, respectively, N is the sum of weights of all items and m is a given integer.

关 键 词：覆盖问题 最小最大 解构造方法 

分 类 号：O224[理学—运筹学与控制论]