摘要
提出一种新的关于多维背包(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.
出处
《数学的实践与认识》
CSCD
北大核心
2007年第22期71-77,共7页
Mathematics in Practice and Theory
基金
辽宁省教育厅高等学校科研资助(2004C9)
关键词
优化问题
NP-完全问题
约束归并
单约束
optimal problem
NP-complete problem
restrict merger
single constraint
