| 求解可分离连续凸二次背包问题的直接算法 |
| |
| 引用本文： | 华中生,张斌.求解可分离连续凸二次背包问题的直接算法[J].系统工程与电子技术,2005,27(2):331-334. |
| |
| 作者姓名： | 华中生 张斌 |
| |
| 作者单位： | 中国科学技术大学商学院,安徽,合肥,230026 |
| |
| 基金项目： | 国家自然科学基金(70172041)，安徽省自然科学基金(03042308)资助课题 |
| |
| 摘 要： | 经典算法一般采用迭代过程求解连续凸二次背包问题,研究了求解可分离连续凸二次背包问题的直接算法。分析了可分离连续凸二次背包问题的结构特性,通过两个命题和两个定理研究了可分离连续凸二次背包问题的解的特性,提出了一种快速的求解该问题的直接算法。该算法能快速有效地求解可分离连续凸二次背包问题的最优解,算法的时间复杂度和空间复杂度都是O(n),都比经典算法节约很多。
|
| 关 键 词： | 凸二次背包问题 可分离问题 松弛 算法 |
| 文章编号： | 1001-506X(2005)02-0331-04 |
| 修稿时间： | 2004年3月15日 |
Direct algorithm for separable continuous convex quadratic knapsack problem |
| |
| HUA Zhong-sheng,ZHANG Bin.Direct algorithm for separable continuous convex quadratic knapsack problem[J].System Engineering and Electronics,2005,27(2):331-334. |
| |
| Authors: | HUA Zhong-sheng ZHANG Bin |
| |
| Abstract: | 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. |
| |
| Keywords: | convex quadratic knapsack problem separable problem relaxation algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
