求解可分离连续凸二次背包问题的直接算法  

Direct algorithm for separable continuous convex quadratic knapsack problem

作　　者：华中生[1] 张斌[1] 

机构地区：[1]中国科学技术大学商学院,安徽合肥230026

出　　处：《系统工程与电子技术》2005年第2期331-334,共4页Systems Engineering and Electronics

基　　金：国家自然科学基金(70172041);安徽省自然科学基金(03042308)资助课题

摘　　要：经典算法一般采用迭代过程求解连续凸二次背包问题,研究了求解可分离连续凸二次背包问题的直接算法。分析了可分离连续凸二次背包问题的结构特性,通过两个命题和两个定理研究了可分离连续凸二次背包问题的解的特性,提出了一种快速的求解该问题的直接算法。该算法能快速有效地求解可分离连续凸二次背包问题的最优解,算法的时间复杂度和空间复杂度都是O(n),都比经典算法节约很多。Classical algorithms often solve continuous convex quadratic knapsack problem through iteration process, a direct algorithm is investigated for separable continuous convex quadratic knapsack problem. By analyzing the structural characteristics of the problem, and investigating the properties of the solutions by giving two propositions and two theorems, a direct algorithm for separable continuous convex quadratic knapsack problem is proposed, by which the optimal solution to the problem can be obtained fast and effectively. The computational complexity on time and space of the proposed algorithm are both O (n), which are both smaller than those of the classical algorithms.

关 键 词：凸二次背包问题 可分离问题 松弛 算法 

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