文献类型：期刊文章

作　　者：高天[1] 翟延慧[2] 王梦光[1]

机构地区：[1]东北大学信息学院系统研究所,辽宁沈阳110004 [2]长春师范学院数学系,吉林长春130032

出　　处：《东北师大学报（自然科学版）》

基　　金：国家自然科学基金资助项目 ( 7970 0 0 6 )

年　　份：2002

卷　　号：34

期　　号：3

起止页码：21-26

语　　种：中文

收录情况：AJ、BDHX、BDHX2000、BIOSISPREVIEWS、CAS、CSCD、CSCD2011_2012、JST、MR、RCCSE、WOS、ZGKJHX、ZMATH、ZR、核心刊

摘　　要：针对一类组合优化问题中多维 0 -1背包问题 (MKP) ,给出一种能减少求解难度的方法 :不等式单约束生成法 ;定义了MKP的紧约束概念 ,指出MKP也是一个NP -难问题 ;提出了一种代替多约束组的计算方法 ,并证明了经过替换后所得到的新问题与原问题在解精度上的等价性 .

关 键 词：多维0-1背包问题 约束简化方法  不等式单约束生成法  NP-难问题  紧约束  解精度等价性  O-1规划  组合优化

分 类 号：O221.4]