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

摘要

研究了可分离二次背包问题的一种直接算法.此类背包问题的目标函数是二次的,且含有严格的一次项,其不等式约束是线性的.给出所求模型的一般形式,经过预处理该模型,最终归为求解两类问题(P_1)和(P_2).重点是求解(P_2)问题的最优解,通过分析(P_2)问题的结构特点,假设固定一次项后问题的最优解和相应不等式的拉格朗日乘子已求出,通过比较拉格朗日乘子和(P_2)问题的一次项系数来调节λ的大小,从而求出(P_2)问题的最优解.对于(P_1)问题,改进了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结合起来,能够快速有效地求解此类更一般的二次背包问题.