特殊一维背包问题的降维替换算法研究  

The Research for the Reductive Dimension and Replacive Variable Algorithm of Special Restrict 0—1 ILP

作　　者：高天[1] 王梦光[1] 唐立新[1] 宋建海[2] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110004 [2]上海宝钢计算机系统工程有限公司,上海201900

出　　处：《系统工程理论方法应用》2002年第2期125-130,共6页Systems Engineering Theory·Methodology·Applications

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

摘　　要：对问题单约束 0 - 1线性整数规划问题 ( 0 - 1 ILP,背包问题 )的特性进行了分析 ,设计了问题求解的算法——降维替换算法 (线性规划求解与特殊启发式相结合的方法 )。In this paper, we analyzed some property for the single restrict 0-1 ILP(one dimension knapsack problem, knapsack problem), designed an algorithm using the linear programming solution combined with heuristic——reduce dimension and replace variable algorithm.

关 键 词：O-1线性整数规划 背包问题 启发式算法 降维替换算法 目标函数 最优解 

分 类 号：O221.4[理学—运筹学与控制论]