| 特殊多维0-1背包问题的约束简化方法--不等式单约束生成法 |
| |
| 引用本文： | 高天,翟延慧,王梦光.特殊多维0-1背包问题的约束简化方法--不等式单约束生成法[J].东北师大学报(自然科学版),2002,34(3):21-26. |
| |
| 作者姓名： | 高天 翟延慧 王梦光 |
| |
| 作者单位： | 1. 东北大学信息学院系统研究所,辽宁,沈阳,110004
2. 长春师范学院数学系,吉林,长春,130032 |
| |
| 基金项目： | 国家自然科学基金，7970006， |
| |
| 摘 要： | 针对一类组合优化问题中多维0－1背包问题（MKP），给出一种能减少求解难度的方法：不等式单约束生成法；定义了MKP的紧约束概念，指出MKP也是一个NP－难问题；提出了一种代替多约束组的计算方法，并证明了经过替换后所得到的新问题与原问题在解精度上的等价性。
|
| 关 键 词： | 多维0－1背包问题 约束简化方法 不等式单约束生成法 NP－难问题 紧约束 解精度等价性 O－1规划 组合优化 |
| 文章编号： | 1000-1832(2002)03-0021-06 |
| 修稿时间： | 2002年4月18日 |
A predigesting method for the special multi-dimension--the generation method of lnequality single restrict |
| |
| GAO Tian ,ZHAI Yan-hui ,WANG Meng-guang.A predigesting method for the special multi-dimension--the generation method of lnequality single restrict[J].Journal of Northeast Normal University (Natural Science Edition),2002,34(3):21-26. |
| |
| Authors: | GAO Tian ZHAI Yan-hui WANG Meng-guang |
| |
| Institution: | GAO Tian 1,ZHAI Yan-hui 2,WANG Meng-guang 1 |
| |
| Abstract: | In this paper, it lodged a method of reducing the solving difficulty--the creative method of non-equivalence single restrict, aim at a kind of combination and optimize problem-multi-dimension 0-1 knapsack problem(also called the NP-hard problem). It defined the tightness restrictive conception of this problem, and lodged a calculation method of replacing a restrict group with a single restrict condition. It proved the equivalence property of solution precision between original problem and new problem that be replaced. |
| |
| Keywords: | NP-hard problem non-equivalence single restrict tightness restrict solution precision equivalence |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
