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

Direct algorithm of separable quadratic knapsack problem

研究了可分离二次背包问题的一种直接算法.此类背包问题的目标函数是二次的,且含有严格的一次项,其不等式约束是线性的.给出所求模型的一般形式,经过预处理该模型,最终归为求解两类问题(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结合起来,能够快速有效地求解此类更一般的二次背包问题.

A direct algorithm of the separable quadratic knapsack problem is presented. The quadratic knapsack problem whose objective function is quadratic and contains strict one-time items is defined on the linear inequality constraint. The general form of the model is given, and by pretreatment, this model ultimately can be converted into two types of problems （Pl） and （P2）. By analyzing the structural features of the problem （P2） and comparing the corresponding Lagrange multiplier with the coefficient of the one-time items, the direct algorithm for solving （P2） is proposed. The optimal solution of the problem （P1）can be characterized on the same lines as described by Bretthauer and Shetty （Bretthauer K M, Shetty B. A pegging algorithm for the nonlinear resource allocation problem. Computers and Operations Research, 2002, 29（5）： 505-527）. The computational complexity of this algorithm is O （n）. Numerical examples are presented to support the theory.