一类多维0-1背包问题的约束归并方法  

The Restrict Merger Approach of a Kind of Multidimensional 0-1 Knapsack Problem

作　　者：迟东璇[1] 翟延慧[2] 

机构地区：[1]上海金融学院应用数学系,上海201209 [2]天津工业大学理学院,天津300160

出　　处：《数学的实践与认识》2007年第22期71-77,共7页Mathematics in Practice and Theory

基　　金：辽宁省教育厅高等学校科研资助(2004C9)

摘　　要：提出一种新的关于多维背包(Multi-dimensions Knapsack Problem,MKP)的约束替代问题,MKP是NP-完全问题,称这种约束替代方法为不等式单约束平面生成法.叙述了单约束不等平面生成算法的基本思想,证明了此方法的一些性质及化简问题后所得到的新问题MKPS与原问题MKP的等价性.最后用实例证实了这种化简方法及其有效性。This paper give a new Merfing restrict of the Multi-dimentions Knapsack Problem （MKP, and henceforth） is proposed. The MKP is NP-complete problem, and this merging restric as adressed in the article is called inequality single constrainted plane generation. The essential idea of single constrainted inequality plane generating algorithm is described, some of the properties of this method proved, and the equivalence of the attained problem of MKP to the original one testified. Besides, this simplification as well as its effectiveness are confirmed with examples.

关 键 词：优化问题 NP-完全问题 约束归并 单约束 

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