可分离的二次背包问题的一种直接算法

摘要：

研究了可分离二次背包问题的一种直接算法.此类背包问题的目标函数是二次的,且含有严格的一次项,其不等式约束是线性的.给出所求模型的一般形式,经过预处理该模型,最终归为求解两类问题(P1)和(P2).重点是求解(P2)问题的最优解,通过分析(P2)问题的结构特点,假设固定一次项后问题的最优解和相应不等式的拉格朗日乘子已求出,通过比较拉格朗日乘子和(P2)问题的一次项系数来调节λ的大小,从而求出(P2)问题的最优解.对于(P1)问题,改进了Bretthauer和Shetty给出的算法(Bretthauer K M,Shetty B.A pegging algorithm for the nonlinear resource allocation problem.Computers and Operations Research,2002,29(5):505-527).此算法的计算复杂性为O(n).数值算例表明,将这种固定变量算法和文中的定理5结合起来,能够快速有效地求解此类更一般的二次背包问题.

关键词：可分离、二次背包问题、固定变量算法

所属期刊栏目：28

分类号：O221.2(运筹学)

资助基金：国家自然科学基金资助项目11271128;上海市重点学科建设资助项目S30104

在线出版日期：2014-07-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共16页

页码：150-165