数学的实践与认识
數學的實踐與認識
수학적실천여인식
MATHEMATICS IN PRACTICE AND THEORY
2007年
22期
71-77
,共7页
优化问题%NP-完全问题%约束归并%单约束
優化問題%NP-完全問題%約束歸併%單約束
우화문제%NP-완전문제%약속귀병%단약속
提出一种新的关于多维背包(Multi-dimensions Knapsack Problem,MKP)的约束替代问题,MKP是NP-完全问题,称这种约束替代方法为不等式单约束平面生成法.叙述了单约束不等平面生成算法的基本思想,证明了此方法的一些性质及化简问题后所得到的新问题MKPS与原问题MKP的等价性.最后用实例证实了这种化简方法及其有效性.
提齣一種新的關于多維揹包(Multi-dimensions Knapsack Problem,MKP)的約束替代問題,MKP是NP-完全問題,稱這種約束替代方法為不等式單約束平麵生成法.敘述瞭單約束不等平麵生成算法的基本思想,證明瞭此方法的一些性質及化簡問題後所得到的新問題MKPS與原問題MKP的等價性.最後用實例證實瞭這種化簡方法及其有效性.
제출일충신적관우다유배포(Multi-dimensions Knapsack Problem,MKP)적약속체대문제,MKP시NP-완전문제,칭저충약속체대방법위불등식단약속평면생성법.서술료단약속불등평면생성산법적기본사상,증명료차방법적일사성질급화간문제후소득도적신문제MKPS여원문제MKP적등개성.최후용실예증실료저충화간방법급기유효성.
