2023年8月1日发(作者：)
第ｌ６卷第４期 ２０１０年８月 上海大学学报（自然科学版） ＪＯＵＲＮＡＬ ＯＦ ＳＨＡＮＧＨＡＩ ＵＮＩＶＥＲＳＩＴＹ（ＮＡＴＵＲＡＬ ＳＣＩＥＮＣＥ） ＶｏＪ．１６ ＮＯ．４ Ａｕｇ．２０１０ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００７—２８６１．２０１０．０４．０１２ 可分离的二次背包问题的一种直接算法 任 燕， 陈 伟 （上海大学理学院，上海２００４４４） 摘要：二次背包问题是一个ＮＰ—ｈａｒｄ问题．给出一般的可分离二次背包问题的一种快速求解的直接算法，分析可分 离连续二次背包问题的结构特性，并研究此问题最优解与拉格朗日系数Ａ的关系．在此基础上，提出通过调节Ａ来 找到可分离二次背包问题的局部最优解的算法，此算法的计算复杂度为Ｏ（ｎ）． 关键词：二次背包问题；Ｋａｒｕｓｈ—Ｋｕｈｎ—Ｔｕｃｋｅｒ（ＫＫＴ）条件；可分离；拉格朗日系数 中图分类号：Ｏ ２１ １．４ 文献标志码：Ａ 文章编号：１００７・２８６１（２０１０）０４－０３８７－０７ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｄｉｒｅｃｔ Ｓｏｌｕｔｉｏｎ ｏｆ Ｓｅｐａｒａｂｌｅ Ｑｕａｄｒａｔｉｃ Ｋｎａｐｓａｃｋ Ｐｒｏｂｌｅｍ ＲＥＮ Ｙａｎ， ＣＨＥＮ Ｗｅｉ （Ｃｏｌｌｅｇｅ ｏｆ Ｓｃｉｅｎｃｅｓ，Ｓｈａｎｇｈａｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２００４４４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｑｕａｄｒａｔｉｃ ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍ ｉｓ ＮＰ－ｈａｒｄ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａｎ ａｌｇｏｒｉｔｈｍ ｔｏ ｄｉｒｅｃｔｌｙ ｏｂｔａｉｎ ａ ｌｏｃａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｏｆ ａ ｓｅｐａｒａｂｌｅ ｑｕａｄｒａｔｉｃ ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍ．Ｂｙ ａｎａｌｙｚｉｎｇ ｔｈｅ ｓｔｒｕｃｔｕｒａｌ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔｈｅ ｐｒｏｂｌｅｍ，ｗｅ ｓｔｕｄｙ ｔｈｅ ｒｅｌａｔｉｏｎｓ ｂｅｔｗｅｅｎ Ｌａｇｒａｎｇｉａｎ Ａ ａｎｄ ｔｈｅ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ．Ａｎ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｅｓｅｎｔｅｄ ｉｎ ｗｈｉｃｈ ｔｈｅ Ｌａｇｒａｎｇｉａｎ Ａ ｉｓ ａｄｊｕｓｔｅｄ ｔｏ ｇｉｖｅ ａ ｌｏｃａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ． Ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ ｉｓ Ｏ（ｎ）． Ｋｅｙ ｗｏｒｄｓ：ｑｕａｄｒａｔｉｃ ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍ；Ｋａｒｕｓｈ—Ｋｕｈｎ－Ｔｕｃｋｅｒ（ＫＫＴ）ｃｏｎｄｉｔｉｏｎ；ｓｅｐａｒａｂｌｅ； Ｌａｇｒａｎｇｉａｎ 二次背包问题在现实生活中被广泛应用于金 融…、资本预算 、生产计划和工作调度 等方 面，并且二次背包问题在组合优化领域有着重要的 地位，无论是从实际应用和理论研究方面都引起了 广泛的关注 ．二次背包问题的各种特殊化情形在 诸多文献中都有研究，如决策变量为二元０—１二次 虽然二次背包问题是ＮＰ．ｈａｒｄ问题，但是由于 其被广泛应用，因此，很多人致力于解决此类问题， 并提出了有效的解法．文献［７］讨论了集中连续凸 规划问题的求解方法．文献［８］通过Ｋａｒｕｓｈ—Ｋｕｈｎ— Ｔｕｃｋｅｒ（ＫＫＴ）条件求解一系列连续的二次背包松弛 问题，提出了一种求解可分离凸二次背包问题的算 背包问题 Ｊ、结构系数为正整数的超模二次背包问 题 ｊ、二次成本系数矩阵为对角阵的可分离二次背 法．文献［１０］对可分离连续凸二次背包问题提出了 直接算法．Ｊｏｒｅ等¨ 针对凹可分离的二次背包问题 提出了算法．但对一般的非凸非凹的二次背包问题， 目前还未见到相关的直接算法． 包问题 、放弃决策变量整数要求的连续二次背包 松弛问题 等． 收稿日期：２００９－０５一ｌ３ 通信作者：陈伟（１９６５～），女，副教授，研究方向为整数规划．Ｅ—ｍａｉｌ：ｃｈｅｎｗｅｉ＠ｓｔａｆｆ．ｓｈｕ．ｅｄｕ．ｃｎ ３８８ 上海大学学报（自然科学版） 第ｌ６卷 当二次背包问题规模比较大时，经典的求解方 法会有一定的困难，但对于可分离的二次背包问题， 问题（Ｐ）的目标函数配方后，可化为－厂（ ）＝ 本研究利用其结构特性和ＫＫＴ条件提出一种快速 耋 （ 一ｎ ） 一ｃ ］，其中ｎ ＝一 ｄｉ．因为ｃ 求解的直接算法，考虑的问题模型（Ｐ。）如下： ｍｉｎｆ（ｘ）＝∑ｑｉ＝１ ｉ（ ）＝∑Ｃｉ＝１ ｉ ＋ｄｉ ， ｓ．ｔ．∑∞ ≤ ， Ｚ≤ ≤Ｍ， ≥０，Ｃ ≠０，ｉ＝１，２，…，ｎ， 且∑Ｏ）ｉｆ ≤ ≤∑０９ｉｕ ．当不限制ｃ １＞０，ｉ＝１，２， …，ｎ时，问题（Ｐ ）为非凸的二次背包问题． 本工作将讨论如何得到问题（Ｐ。）的一个局部 极小解，基本思想是先不考虑线性约束，找到问题 （Ｐ。）的一个理想解．如果理想解满足线性约束，那 么理想解就是最优解；如果理想解不满足线性约束， 则由本工作给出的定理和命题，可以限定拉格朗日 系数Ａ的取值范围，从而可逐步确定某些变量的最 优取值． １ 模型求解 可分离的二次背包问题（Ｐ ）通常具有以下 形式： ｍｉｎｆ（ｘ）＝∑ｑｉ（ ）＝∑Ｃｉ ＋ｄｉ ＝ｌ ｉ＝１ ｓ．ｔ．∑ ≤ ， ｌ≤ ≤ｕ，∞ ≥０，Ｃ ≠０，ｉ＝１，２，…，ｎ． 设∑ｗｉｌ ≤ ≤∑ＯＪｉ“ ，则问题（ ）一定有可 行解． 令 ，＿ ，则上述问题转化为 ｍｉｎ ）＝耋ｑ （ ：）＝耋毒２（ ） ＋毒 ：， ≤ ， ｆ ≤ ≤Ｍ ，Ｃ ≠０，ｉ＝１，２，…，ｎ． 为了方便起见，将问题设为（Ｐ），有 ｍｉｎｆ（ｘ）＝∑ｑｉ＝ｌ ｉ（ ）：∑Ｃｉ＝１ ｉ ＋ｄｉ ， ｓ．ｔ．∑ ≤ ，ｉ＝ｌ １≤ ≤Ｍ，ｃ ≠０，ｉ＝１，２，…，ｎ． 为已知数，所以问题（Ｐ）可转化为下列问题（Ｐ ）来 求解： ｍｉｎｆ（ｘ）＝∑ｑｉ（ ）＝∑Ｃｉ（ 一口。）。， Ｉ＝ｌ ｉ＝】 ｓ．ｔ．∑ ≤ ， ＝ｌ Ｚ≤ ≤Ｍ，ｃ ≠０，ｉ＝１，２，…，ｎ． 在此问题中，我们将指标集，＝｛１，２，…，ｎ｝分为两个 指标集，其中， ＝｛ｉ∈ＩＩｃ ＞０｝，，２＝｛ｉ∈ＩＩｃ ＜０｝． 问题（Ｐ ）的ＫＫＴ条件如下： ∑ ≤ ；ｉ＝ｌ （１） ｆ ≤ ≤Ｍ ，ｉ＝１，２，…，ｎ； （２） ２ｃ （ 一ｎ ）＋Ａ一１．１ ＋ ＝０，ｉ＝１，２，…， ；（３） ｄ ｎ Ａ（∑ — ）＝０； （４） ‘ ｌ （Ｚ 一 ）＝０，ｉ＝１，２，…，ｎ； （５） （ 一Ｍ ）＝０，ｉ＝１，２，…，ｎ； （６） ≥０，ｉ＝１，２，…，ｎ； （７） ≥０，ｉ＝１，２，…，ｎ； （８） Ａ≥０． （９） 如果不考虑线性约束∑ ≤ ，ＮＮ，Ｎ（Ｐ ）的理想 解为 ｌ ， 口 ≤Ｚ ，ｉ Ｅ，１， ｎ ，ｌ ＜０ ＜ ，ｉ∈，Ｉ， ， ｎ ≥ ，ｉ∈，ｌ， ≥ ， ∈，２， ，， 。 ＜ ０￡＜— ～，，ｚ∈ ∈１—２．・ 定理１若理想解 满足线性约束（１），则 一定为问题（Ｐ ）的最优解． 证明只需证明存在非负的拉格朗日系数，使 得ＫＫＴ条件（３）～（９）成立． 若存在 ＝。 使得式（５）～（８）成立，只需令 ＝０， ＝０．若使式（３）成立，则Ａ＝０．从而式（４） 和（９）成立． 对于其他 ＝ｆ 的分量，式（６）要成立，则 ＝ 第４期 任燕，等：可分离的二次背包问题的一种直接算法 ３８９ ０．又因为Ａ＝０，式（３）即为２ｃ （Ｘ 一。 ）一 ＝０．注 意到，若ｃ ＞０，只有当。 ≤１ 时，才有互＝１ ，所以 ＝２ｃ （曩一ａ ）≥２ｃ （１ —ａ ）≥０；若ｃ ＜０，只有当 Ⅱ ≥ 时，才有互：ｆ ，仍有 ＝２ｃ （ 一。 ）≥ ２ｃ １ 一Ｉ丁ｉ＋ｕｉ）＝ｃ （ｆ —ｕ ）≥０，所以式（７）成立． 对于其他互＝“ 的分量，若式（５）成立，则 ＝ ０．又因为Ａ＝０，代入式（３）有２ｃ （ —ａ ）＋ ＝０． 若Ｃ ＞０，只有当ａ ≥ｕ 时，才有 ＝ｕ ，此时∞ ＝ 一２ｃ （互一ａ ）：一２ｃ （Ｕ —ａ ）≥０；若ｃ ＜０，只有当 ＜ 妄 时，有 ：Ｍ ，此时 ：一２ｃ；（互一。 ）≥ 一２ｃｉ（ 一１丁ｉ ４－ｌｇｉ）＝一ｃ。（ｕ 一 ≥０，所以式（８）成 立．从而 是问题（Ｐ。）的最优解． 若对１≤ ≤ｎ，互≠ａ。，则理想解为 １ ，ｉ∈｛ａ ≤ｌｉ，ｉ∈，１｝Ｕ ≥ ， ∈ ）， ， ｉ∈｛ａ ≥ ，ｉ∈，ｌ｝Ｕ ＜ ， ∈ ）． 当ｃ ＞０，ａ ≤ｆ 时，有互＝ｌ ，而ｑ：（ ）＝２ｃ （ 一 口 ）：２ｃ；（ｆ 一。 ）＞１０；当ｃ ＜０， ≥ 时，有 ＝ 而 瓦）＝２ 互 ）≥２ｃ ）＝ ｃ （ｆ —ｕ ）＞０；当ｃ ＞０，ａ ≥ｕ 时，有 ＝１１， ，而 ｑ：（瓦）：２ｃｉ（ 一。 ）≤０；当 ＜０，血 ＜ 时，有 ＝“ ，而ｇ （ ）＝２ｃ （Ｍ 一ａ ）＜０，只需取０≤ ≤ ｍｉｎ｛一ｑ：（ ）Ｉ曩＝Ｕ ，ｉ＝１，２，…， ｝．当 ＝１ 时， 因ｑ：（ ）／＞０，则可令 ＝ｑ：（ ）＋Ａ，式（３）成立， 且 Ｉ＞０；当曩＝“ 时，因ｑ：（ ）≤０，则可令 ＝ 一ｇ （ ）一Ａ，使得式（３）～（８）成立．综上所述， 可以满足ＫＫＴ条件（３）～（９）．证毕． 由理想解的取值可知，当ｉ∈， ，ａ ≤１ 或ｉ∈１２， 口 ≥ 时，理想解 ： ．上述变量取到盒约束的 下限且使得９ （ ）最小，这些变量的取值已经相对 固定，无改进的必要．所以，下面我们不再考虑这些 变量，但为叙述简便，在讨论下述问题（Ｐ。）时，仍将 变量个数设为ｎ． ａｒｉｎｆ（ｘ）＝∑ｑｉ（ ）＝∑ｃ （ 一ａｉ）。， ｓ．ｔ．∑ ≤ ， Ｚ≤ ≤Ｕ，Ｃ ≠０，ｉ∈， ｕ ， 其中， ＝｛ｉ Ｉ ｃ ＞０，８ ＞ｆ ，１≤ｉ≤ｎ｛，， ：｛ｉ Ｉ ｃ。＜０， ，ｌ≤ ≤凡＿｝，且， Ｕ１２＝｛ｌ，２，…，ｎ｝． 问题（Ｐ ）的理想解为 一 ｆａ ，ｆ ＜ａ ＜“ ，ｉ∈，：， 【 ，ｉ∈｛口 ≥“ ，ｉ∈，：｝ｕ， ． 由定理１知，若 满足线性约束条件，则 为 最优解．以下考虑当理想解不满足线性约束时，如何 改进 ，从而得到最优解． 当∑ｉ＞ 时，理想解 不满足线性约束，如 果让每个变量都变小或保持当前的取值 ，那么 ∑ 将变小，直到满足线性约束．令 为通过上述 方法找到的问题（Ｐ ）的局部最优解，则一定有ｆ ≤ ≤墨．令 ＝ 一∑弓十互，若取 ＝ｙ ，则有 Ｊ １ Ｘｉ＋∑弓＝ｙ ＋∑亏＝ｙ一∑ ＋互＋∑弓＝ ．该式表示当其他分量不改变时，对第ｉ个变量，只 需从互减小到ｙ ，就可以满足线性约束条件（１）． 但如果同时减少ｍ个变量，则显然每个变量不必减 小到 ，就可使∑ ≤ｙ成立，所以 是第ｉ个变 量取值的下限，从而有 ≥ ．但由于盒约束ｚ ≤ ≤“ ，有 Ｉ＞１ ．所以变量 的最优值的取值范围 为［ ，互］，其中 ＝ｍａｘ｛ ，ｆ ｝． 定理２对于问题（Ｐ ），设 是（Ｐ。）的最优 解，贝０当Ｃ ＞０时，若 ∈［ ， ］，有ｑ （ ）≤ ｑ （ ）≤ （ ）；当Ｃ ＜０时，若 Ｅ［ｙ ， ］，则 ３９０ 上海大学学报（自然科学版） 第１６卷 有ｑ；（ｙ ）ｌ＞ｑ （ ）ｌ＞ｑ （ ），且ｑ （ ）＜０． 证明当ｃ。＞０时，ｑ：（ ）＝２ｃ （ 一口 ）为单调 一０ ）≤ ｑ （ ）为单调递减函数，则有９ （ 。 ）≥ｑ （ ）＝ ｑ （Ｍ ），故当Ｚ ＜ ≤“ 时， ＝０．因为 为最优 递增函数，则有２ｃ （ｙ 一ｎ ）≤２ｃ （ 解，所以 ≥０．由ＫＫＴ条件（３）知，ｇ （ ）＋Ａ＋ ２ｃ （互一０ ）．而 ｑ：（互）＝２ｃ （互～ｎ ）＝ ｒ０， Ｚ ＜０ ＜ ，ｉ∈，１， 【２ｃ （ 一ｒ上 ）≤０， ｎ ≥Ｍ ，ｉ∈，１， 即当ｉ∈， ， ∈［ ，曩］，有ｑ （ ）≤ｇ （ ）≤ ｑ：（ ）≤０． 当ｃ ＜０时，ｑ：（ ）＝２ｃ （ 一ｎ ）为单调递减函 数，即当ｉ∈Ｉ２， ∈［７ ， ］时，有ｑ：（ ｉ）≥ ｑ：（ ）≥ｑ：（互），且ｑ （ ）＝２ｃ （ＩＩ， 一０ ）＜ ２ｃｉ ） 一ｌｉ）＜０． 定理３对问题（Ｐ ），设 是（Ｐ。）的理想解， 是问题（Ｐ ）的最优解，Ａ， （１≤ｉ≤ｎ）为相对于 的拉格朗日系数．若存在ｉ∈， ，使得第ｉ个变量的 最优解满足ｆ ＜ ＜“ ，当 ≠ 时，如果有ｑ （ ）≤ ｑ （ ），则取 ＝ ，可满足拉格朗日系数 ≥０． 证明因为 是问题（Ｐ ）的最优解，且存在ｉ∈ ，，满足２ ＜Ｘｉ ＜Ｍ ，则为满足ＫＫＴ条件，令 ＝∞ ＝０， 且有ｇ （ ）＋Ａ：０．又因为 ≤ ≤ｘｉ，从而由定理 ２知，Ａ＝一ｑ （ ）≥０，且Ａ＜一ｑ：（２ ）． 对于 ≠ ，有弓≠ ，从而 ＝０．为满足ＫＫＴ条 件（３），应有 （ ）＋Ａ＋ ＝０．若取 ＝弓，则由 ｑ （弓）≤ｑ：（ ）得， ：一（ｑ （ ）＋Ａ）＝ 一（ｑ （ ）一ｑ：（ ））≥０．证毕． 定理４对问题（Ｐ ），设 是（Ｐ ）的理想解， 是问题（Ｐ。）的最优解，Ａ，∞ （１≤ｉ≤ｎ）为相对于 的拉格朗日系数．若存在ｉ∈１２，使得第ｉ个变量的 最优解 满足ｚ ＜ ≤ｕ ，则拉格朗日系数Ａ满足 Ａ≤一ｑ （互）＝一２ｃ （“ 一口 ）．若存在 （弓）≤ ｑ （互），令 ＝ ，可满足拉格朗日系数 ≥０． 证明对问题（Ｐ ），当Ｃ ＜０时，有 ＝ｕ。．而 ＝０．从而可得Ａ≤一ｑ：（ ）≤一ｑ：（五）． 由理想解的取值知 ≠ｚ ，所以 ，＝０．为满足 ＫＫＴ条件（３），应有ｑ；（ ）＋Ａ＋（ｃＪ ＝０．若取 ， ＝ 弓，则由ｑ （ ）≤ｑ：（互），可得 ＝一（ｑ （ ）＋ Ａ）≥一（ｑ；（ ）一ｑ；（ ）＞１０．证毕． 由定理３知，当ｉ∈， ， 的最优值的取值范围 为［ ，曩］，有ｑ：（ｙ ）≤ｑ （Ｘｉ ）≤ｑ：（ ）．如果 ≠ｚ 或 ＝ｆ ， ≠ｆ ，则一定有Ａ≤一ｑ：（ｙ ）．当 ｉ∈，２， 的最优解的取值范围为［ｙ ，ｘｉ］，由定理４ 知，Ａ≤一ｑ （ ）．所以这两个定理给出了Ａ的取值 范围． 定理５若存在ｉ∈， ，有一ｑ （ ）＜Ａ，其中Ａ 为最优解对应的拉格朗日系数，为满足ＫＫＴ条件， 则第ｉ个变量的最优解为 ＝ ：ｚ ． 证明若 ≠ｙ ，则有 ＞Ｚ ，从而有 ＝０． 若 ＝Ｍ ，由ＫＫＴ条件（３）知，ｑ （ ）十Ａ＋ ＝０． 可得 ＝一ｑ：（ ）一Ａ＜一ｑ （ｙ ）一Ａ＜０，与ＫＫＴ 条件矛盾．若Ｚ ＜ 。 ＜ ，则有 ＝∞ ＝０，则由ＫＫＴ 条件（３）知，ｑ：（ ）＋Ａ＝０．可得Ａ＝一ｑ：（ ）＜ 一ｇ （ ），这与题意矛盾． 若 ＝ ≠ｆ ，则有 ＝（ｃＪ。＝０，则由ＫＫＴ条件 （３）知，ｑ （ ）＋Ａ：０，可得Ａ＝一ｇ：（ ）＜ 一ｑ：（ｙ ），与ＫＫＴ条件矛盾．若 ＝ｙ ：ｆ ，则有 ∞ ＝０，则由ＫＫＴ条件（３）知，ｑ （ ）＋Ａ＋ ＝０．可 得ｚ， ＝ｑ （ ）＋Ａ＝ｑ：（ ）＋Ａ＞０． 综上所述，只有当 ＝ ＝ｆ 时，才能满足 ＫＫＴ条件．证毕． 定理６若存在ｉ∈１２，有一ｑ：（ ）＜Ａ，其中Ａ 为最优解对应的拉格朗日系数，为满足ＫＫＴ条件， 则第ｉ个变量的最优解为 ｉ ＝ ｉ＝ｆｉ． 证明仿照定理５． 定理７ 若存在 ｉ＝ｚ ，且ｑ：（７ ）≥０，则取 第４期 任燕，等：可分离的二次背包问题的一种直接算法 ３９１ ＝ ，可满足 Ｉ＞０． 证明若取 ：ｆ ，可令∞ ＝０，对于任意非负 的拉格朗日系数Ａ≥０．为满足ＫＫＴ条件（３）， ｑ （ ）＋Ａ一 ＝０，所以有 ＝ｑ （ ）＋Ａ＞１０． 定理８ 假定 ＝（ ， ，…， ）是问题 （Ｐ，）的最优解，若存在ｉ≠ ，１≤ｉ， ≤凡，满足ｆ ＜ ＜ｕ ，Ｚ ＜ ｆ ＜ ，，则有 ｃ （ 一 ）＝ （ 一ａｊ）． 证明 由于 是问题（Ｐ．）的最优解，且满足 ＫＫＴ条件，从而得 ＝０９ ＝ ，：ＯＪｊ＝０．由２ｃ （ 一 ０ ）＋Ａ＝０，２ｃｉ（Ｘｊ 一 ）＋Ａ＝０，所以有 ｃ （ 一０ ）＝ （ 一ａｊ）． 证毕． 本研究将最优解 ，ｉ∈，满足ｆ ＜ ＜ｕ 的指 标集合记为， ，并记 ＝ 一∑ ．由定理６知， 对任意的ｉ， ∈， ，有ｃ （ 一口 ）：ｃｊ（Ｘｊ 一ａｊ）．可得 ｃ＝Ｊ（、ｘ 一ａｊ）＋０ ．若∑ ＝ｙ 成立，则问题 （Ｐ ）的线性约束被满足，即 ｉ ｅｌ＇ ＼Ｃｉ Ｊ 一 ）＋。 卜 ， 可得 ２求解二次背包问题的算法 ２．１算法思想 算法的基本思想是通过调节Ａ的取值范围，在 寻求 的同时，逐步确定各个变量的最优取值．由定 理３，当ｉ∈， 时，可以通过一ｑ：（ ）来限定Ａ的上 限．由定理４知，当ｉ∈１２时，可以通过一ｑ （ ）来限 定Ａ的上限．找到一ｑ （ ），ｉ∈，。和一ｑ （ ），ｉ∈１２ 中最小的一个值，记为Ａ㈩，并将满足Ａ 的指标记 人集合，Ｊ。．先限定０≤Ａ≤Ａ（１１，若存在ｇ （ ）≤ 一Ａ…，则令ｘｊ ＝ ，将指标 记人集合 ，然后利 用定理８和线性约束条件求得，＿ 中变量的值．若 求出的解对应的拉格朗日系数小于等于Ａ…，则最 优解即为所求的值．若求得解对应的拉格朗日系数 大于给定的Ａ…，则由定理５和定理６知，对 中的 指标对应的变量的最优解应取其下界，将此变量删 除，重新计算 ，ｉ∈，，然后重复上述过程，直至找到 最优解． 应该注意的是，当求得解对应的拉格朗日系数大 于Ａｆｌ１时，且 。中的元素不止一个时，应当取 ＝ｆ等 ， 其中 为满足ｑ （ ）＝ｍａｘ｛ｇ （ｙｆ）｝的指标，将ｋ从 ，，中删除．下面就问题（Ｐ ）给出具体的算法． 步０：令Ｊ『＝｛１，２，…， ｝，计算 ｌ ， ≤ｌ ，Ｃ ＞０， ０ ，ｌ ＜ｒ上 ＜ ，ｃ ＞０， ｕ ， ０ ≥ｕ ，Ｃ ＞０， ，ｃ ＜０， 。 ≥ ，ｃ ＜０． 步１：若∑互≤’，，则 为最优解，停止．否则 进入步２． 步２：对于１≤ｉ≤凡，若存在互＝ｆ ，令 ＝Ｚ ， ，＝八｛ｉ｝， ＝ —ｆ ． 步３：Ｌ＝ ，Ｕ＝（２ｊ． 步４：若，一Ｌ＝ ，则对ｉ∈，， ＝ｆ 为最优解， 停止．若，一，Ｊ≠ ，令，＝，一，Ｊ，进入步５． 步５：对于ｉ Ｅ，，计算 ＝ 一∑互＋互，若对 Ｅ ｌ 任意的ｉ∈，，有 ＝ ，则最优解为 ｆｆｆ， ｉ∈Ｌ， ＝？ 【 ， ｉ∈，， 停止．否则进入步６． 步６：对于ｉ∈，，令ｙ ＝ｍａｘ｛ ，ｆ ｝，记Ｗ＝ ｔｊｌ ＜０， ＝ ，ｑ （ ）＞１０， ∈Ｉｔ，若Ｗ＝（２ｊ，贝４进 入步７；若 ≠ ，则令 ＝ｆ ，Ｌ＝Ｌ Ｕ｛ｋ｝， ＝ 一 ，返回步４（其中 为满足ｑ （瓦）＝ｍ ａ ｘ｛ｑ （ ） 的指标）． 步７：对于ｉ∈，，当ｃ ＞０时，令Ａ ＝一ｑ （ｙ ）， 当ｃ ＜０时，令Ａ ＝一ｑ：（ ）．取Ａ 中最小值记为 Ａ（１），并记Ｌｌ＝｛ｉＩ Ａ ＝Ａ（１）｝． 步８：对于每一个 ∈，，若ｇ （ ）≤一Ａ【Ｉ），则 ３９２ 上海大学学报（自然科学版） 第１６卷 令 ＝瓦，Ｕ＝ＵＵ ． 步９：若ｙ一∑弓＜０，则令 ＝ｌｋ（其中 为 满足ｇ （ ） ｛ （ ）｝的指标），Ｌ＝，Ｊ ｕ｛ ｝， ｛【 ｉ， ｉ∈Ｕ， ， ∈，一 由算法可知，本研究是通过调节拉格朗日系数 Ａ的范围来找到问题（Ｐ．）的最优解．由步７，８，９，１１ ｙ＝ｙ—ｆ ，返回步４；若 一∑ ≥０，且，一 ＝ ， 则最优解为 ｒ Ｚ ， ∈Ｌ， ＝Ｊ 【互， ｉ∈Ｕ， 停止．若，一 ≠ ，且 一∑写≥０，则进入步１０． 步１０：对于任意的 ∈，一 ，有 一∑互一∑口 ■囊＿’ 并计算Ａ ＝一２ｃ （ 一ｎ ），ｉ∈，一 ． 步１１：若Ａ ＞Ａ㈩，则Ｘ，ｋ ＝Ｚ （其中 为满足 ｇ （ ）＝ｍ ａｘｔ ｑ （ ）｝的指标），Ｌ＝Ｌ Ｕ｛ ｝， ．一 ，返回步４；若Ａ ≤Ａ ，则最优解为 ｒｆ ， ｉ∈Ｌ， ｛Ｉ 互， ｉ∈Ｕ， 【 ， ｉ∈，一 ， 停止． 步０和步１是初始化过程，求得理想解并判断 这个理想解是否是原问题的最优解；步２将问题 （Ｐ ）转化为问题（Ｐ ）；步３和步４是判断算法是否 向下继续的条件；步５和步７先确定拉格朗日系数 的一个上限；步６依据定理７确定某些分量的最优 取值，并记人集合，Ｊ，返回到步４；步８是在步７已确 定拉格朗日系数Ａ的一个取值范围的基础上，由 ＫＫＴ条件确定某些分量的值，并将其记人集合 ；步 ９是判断步７确定的拉格朗日系数Ａ的取值范围是 否合适；步ｌ０是运用定理８来计算未确定值的分量 的值，并计算相应的拉格朗日系数Ａ ；步１１表明，如 果计算的Ａ 大于步６所确定的拉格朗日系数Ａ的 上限，则 ＝ｆ （其中 为满足ｑ （ ）＝ ｍ ａｘｔ ｇ （ ）｝的指标），Ｌ＝ ｕ｛ ｝， —ｆ ，返回 ．步４；若Ａ 在限定的范围内，则最优解为 知，最多只需对拉格朗日系数Ａ的范围进行ｎ次调 节，其中ｎ为原问题中变量的个数．对于每个变量， 只需要计算 ，ｑ：（ ）和ｑ：（ ）．那么，此算法的 计算复杂度为０（ｎ），其中ｎ为变量的个数，这比经 典算法或其他方法有效．本工作主要讨论对连续的 可分离的二次背包问题的求解算法．对于可分离的 二次整数背包问题，可以通过将二次整数规划问题 松弛化，转化为本工作中讨论的问题，找到连续问题 的最优解；然后利用其他方法（例如分支定界算法） 进一步求解整数问题． 例１ ａｒｉｎ ）＝（ 】一２） ＋２（ｘ２—１） ＋（ ３—３） 一 ２（ ４＋１） 一３（ ５＋１） ， Ｓ．ｔ． １＋ ２＋…＋ ５≤８， ０≤ １≤３，０≤ ２≤３，０≤ ３≤４， ０≤ ４≤２，０≤ ≤２， 计算结果如表１所示．表中， 为循环次数， 为理 想解， 为算法中步６确定的集合，Ａ…为算法中步 ７确定的Ａ的上限，Ａ 为算法中步ｌＯ确定的拉格朗 日系数， 为问题的最优解． 表１例１的计算结果 Ｔａｂｌｅ １ Ｒｅｓｕｌｔ ｏｆ ｔｈｅ ｅｘ￣ｐｌｅ １ Ａ（１） Ａ Ａ ≤Ａ（１） １（２，１，３，２，２） ４ １．６ 是 （１．２，０．６，２．２，２，２） 经过ＫＫＴ条件验证， ＝（１．２，０．６，２．２，２，２） 为例１的一个局部最优解，最优值为一４３．４．由 Ｍａｔｌａｂ软件求解得到的最优解为 ＝（０，０．６６６ ７， ３．３３３ ３，２．０００ ０，２．０００ ０），最优值为一４０．７． 例２ ｒａｉｎ ）＝３（ 】一２） ＋３（ ２—２）。＋４（ｘ３—３） 一 （ ４＋１） 一２（ｘ５＋１） 一（ ６＋２） ， ｓ．ｔ． ｌ＋ ２＋…＋ ６≤１３， ０≤ ｌ≤３，０≤ ２≤４，０≤ ３≤３， ０≤ ４≤２，０≤ ５≤３，０≤ ６≤４， 计算结果如表２所示． 第４期 任燕，等：可分离的二次背包问题的一种直接算法 ３９３ 表２例２的计算结果 例３ Ｔａｂｌｅ ２ Ｒｅｓｕｌｔ ｏｆ ｔｈｅ ｅｘａｍｐｌｅ ２ ｍｉｎ ） ＝ｘ１—２） ＋２（ ２—１） ＋（ ３—３） ＋ ｋ Ｗ Ａ（１）Ａ Ａ ≤Ａ（１） （ ４—４） ＋３（ ５—１） 一２（ｘ６＋１） 一（ ７—１） 一 ３ 一（ ９＋２） 一２（ｘｌｏ＋１） ， Ｓ．ｔ． ｌ＋ ２＋…＋ ｌｏ≤１５， 经过ＫＫＴ条件验证， ＝（１．６４，１．６４，２．７２，０， ０≤ ｌ≤２，０≤ ２≤３，０≤Ｘ３≤４， ３，４）为例２的一个局部最优解，最优值为一６７．９．由 ０≤ ４≤３，０≤ ５≤２，０≤ ６≤３，０≤ ７≤４， Ｍａｔｌａｂ软件求解得到的最优解为 ＝（１．５，１．５，３， ０≤ ８≤３，０≤ ９≤１，０≤ ｌｏ≤２， ０，３，４），最优值为一６７．５． 计算结果如表３所示． 表３例３的计算结果 Ｔａｂｌｅ ３ Ｒｅｓｕｌｔ ｏｆ ｔｈｅ ｅｘａｍｐｌｅ ３ 经过ＫＫＴ条件验证， ＝（１．６５，０．８３，２．６５，３， ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍ ｗｉｔｈ ｓｅｒｉｅｓ ｐａｒａｌｌｅｌ ｓｕｐｐｏｒｔ［Ｊ］． ０．９２，３，０，０，１，２）为例３的一个局部最优解，最优值 Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ Ｌｅｔｔｅｒｓ，２００２，３０（３）：１５９—１６６． 为一５８．７；由Ｍａｔｌａｂ软件求解得到的最优解为 ＝ ［６］ ＣＡＰＲＡＲＡ Ａ，ＰＩＳＩＮＧＥＲ Ｄ，ＴＯＴＨ Ｐ．Ｅｘａｃｔ ｓｏｌｕｔｉｏｎ ｏｆ （１．６，０．８，３．６，３，０，３，０，０，１，２），最优值为一５５．４． ｔｈｅ ｑｕａｄｒａｔｉｃ ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍ［Ｊ］．Ｉｎｆｏｒｍｓ Ｊｏｕｒｎａｌ ｏｎ 由上述３个例题知，通过此算法得到的最优值 Ｃｏｍｐｕｔｉｎｇ，１９９９，１ｌ：１２５—１３７． 好于采用Ｍａｔｌａｂ软件运用分支定界算法得到的最 ［７］ ＢＲＥＴＦＨＡＵＥＲ Ｋ Ｍ，ＳＨＥＴＦＹ Ｂ．Ｔｈｅ ｎｏｎｌｉｎｅａｒ ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍ—ａｌｇｏｒｉｔｈｍｓ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ［Ｊ］．Ｅｕｒｏｐｅａｎ 优值． Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎ Ｒｅｓｅａｒｃｈ，２００２，１３８（３）：４５９４７２． ［８］ ＢＲＥＴＦＨＡＵＥＲ Ｋ Ｍ。ＳＨＥＴＴＹ Ｂ，ＳＹＡＭ Ｓ．Ａ ｂｒａｎｃｈ ａｎｄ 参考文献： ｂｏｕｎｄ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｉｎｔｅｇｅｒ ｑｕａｄｒａｔｉｃ ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍｓ ［Ｊ］．ＯＲＳＡ Ｊｏｕｒｎａｌ ｏｎ Ｃｏｍｐｕｔｉｎｇ，１９９５，７（１）：１０９一 ＭＡＲＫＯＷＩＴＺＥ Ｈ Ｍ．Ｐｏｒｆｏｌｉｏ ｓｅｌｅｃｔｉｏｎ： ｅｆｆｃｌｅｎｔ ｌ１８． ｄｉｖｅｒｓｉｆｉｃａｔｉｏｎ ｏｆ ｉｎｖｅｓｔｍｅｎｔ［Ｍ］．Ｎｅｗ Ｙｏｒｋ：Ｗｉｌｅｙ， ［９］ ＰＡＲＤＡＬＳ Ｐ Ｍ，ＫＯＶＯＯＲ Ｎ．Ａｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａ ｓｉｎｇｌｙ １９５９：１２９—１８８． ｃｏｎｓｔａｉｎｅｄ ｃｌａｓｓ ｏｆ ｑｕａｄｒａｔｉｃ ｐｒｏｇｒａｍｓ ｓｕｂｊｅｃｔ ｔｏ ｕｐｐｅｒ ［２］ ＢＥＲＮＨＡＲＤ Ｒ Ｈ．Ｍａｔｈｅｍａｔｉｃａｌ ｐｒｏｇｒａｍｍｉｎｇ ｍｏｄｅｌｓ ｆｏｒ ａｎｄ ｌｏｗｅｒ ｂｏｕｎｄｓ［Ｊ］．Ｍａｔｈｅｍａｔｉｃａｌ Ｐｒｏｇｒａｍｍｉｎｇ， ｃａｐｔｉｌａ ｂｕｄｇｅｔｉｎｇ－－ａ ｓｕｒｖｅｙ ｇｅｎｅｒａｌｉｚａｔｉｏｎ ａｎｄ ｃｒｉｔｉｑｕｅ １９９０，４６：３２ｌ一３２８． ［Ｊ］．Ｊｏｕｒｎａｌｓ ｏｆ Ｆｉｎａｎｃｉａｌ Ｑｕａｒｔｅｒｌｙ Ａｎａｌｙｓｉｓ，１９６９，４： ［１０］ 华中生，张斌．求解可分离连续凸二次背包问题的直 ｌｌ１．１５８． 接算法［Ｊ］．系统工程与电子技术，２００５，２７（２）：３３１— ［３］ ＭＯＤＥＲ Ｊ Ｊ．ＰＨＩＬＩＰＳ Ｃ Ｒ．Ｐｒｏｊｅｃｔ ｍａｎａｇｅｍｅｎｔ ｗｉｔｈ ３３４． ＣＰＭ ａｎｄ ＰＥＲＴ『Ｍ１．Ｎｅｗ Ｙｏｒｋ：Ｒｈｅｉｎｈｏｌｄ，１９６４： ［１１］ ＪＯＲＥ Ｊ Ｍ．ＳＴＥＰＨＥＮ Ａ Ｖ．Ｏｎ ｔｈｅ ｓｏｌｕｔｉｏｎ ｏｆ ｃｏｎｃａｖｅ ｌ１９—１３５． ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍｓ［Ｊ］．Ｍａｔｈｅｍａｔｉｃａｌ Ｐｒｏｇｒａｍｍｉｎｇ， ［４］ ＫＥＬＬＥＶＥＲ Ｈ，ＰＦＥＲＳＣＨＹ Ｕ，ＰＩＳＩＮＧＥＲ Ｄ．Ｋｎａｐｓａｃｋ １９９１，４９：３９７－４１１． ｐｒｏｂｌｅｍｓ［Ｍ］．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，２００４：３４—８８． （编辑：孟庆勋） ［５］ ＲＡＤＥＲＪＩ Ｄ Ｊ，ＷＯＥＩＧＩＮＥＲ Ｇ Ｊ．Ｔｈｅ ｑｕａｄｒａｔｉｃ ０—１
2023年8月1日发(作者：)
第ｌ６卷第４期 ２０１０年８月 上海大学学报（自然科学版） ＪＯＵＲＮＡＬ ＯＦ ＳＨＡＮＧＨＡＩ ＵＮＩＶＥＲＳＩＴＹ（ＮＡＴＵＲＡＬ ＳＣＩＥＮＣＥ） ＶｏＪ．１６ ＮＯ．４ Ａｕｇ．２０１０ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００７—２８６１．２０１０．０４．０１２ 可分离的二次背包问题的一种直接算法 任 燕， 陈 伟 （上海大学理学院，上海２００４４４） 摘要：二次背包问题是一个ＮＰ—ｈａｒｄ问题．给出一般的可分离二次背包问题的一种快速求解的直接算法，分析可分 离连续二次背包问题的结构特性，并研究此问题最优解与拉格朗日系数Ａ的关系．在此基础上，提出通过调节Ａ来 找到可分离二次背包问题的局部最优解的算法，此算法的计算复杂度为Ｏ（ｎ）． 关键词：二次背包问题；Ｋａｒｕｓｈ—Ｋｕｈｎ—Ｔｕｃｋｅｒ（ＫＫＴ）条件；可分离；拉格朗日系数 中图分类号：Ｏ ２１ １．４ 文献标志码：Ａ 文章编号：１００７・２８６１（２０１０）０４－０３８７－０７ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｄｉｒｅｃｔ Ｓｏｌｕｔｉｏｎ ｏｆ Ｓｅｐａｒａｂｌｅ Ｑｕａｄｒａｔｉｃ Ｋｎａｐｓａｃｋ Ｐｒｏｂｌｅｍ ＲＥＮ Ｙａｎ， ＣＨＥＮ Ｗｅｉ （Ｃｏｌｌｅｇｅ ｏｆ Ｓｃｉｅｎｃｅｓ，Ｓｈａｎｇｈａｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２００４４４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｑｕａｄｒａｔｉｃ ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍ ｉｓ ＮＰ－ｈａｒｄ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａｎ ａｌｇｏｒｉｔｈｍ ｔｏ ｄｉｒｅｃｔｌｙ ｏｂｔａｉｎ ａ ｌｏｃａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｏｆ ａ ｓｅｐａｒａｂｌｅ ｑｕａｄｒａｔｉｃ ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍ．Ｂｙ ａｎａｌｙｚｉｎｇ ｔｈｅ ｓｔｒｕｃｔｕｒａｌ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔｈｅ ｐｒｏｂｌｅｍ，ｗｅ ｓｔｕｄｙ ｔｈｅ ｒｅｌａｔｉｏｎｓ ｂｅｔｗｅｅｎ Ｌａｇｒａｎｇｉａｎ Ａ ａｎｄ ｔｈｅ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ．Ａｎ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｅｓｅｎｔｅｄ ｉｎ ｗｈｉｃｈ ｔｈｅ Ｌａｇｒａｎｇｉａｎ Ａ ｉｓ ａｄｊｕｓｔｅｄ ｔｏ ｇｉｖｅ ａ ｌｏｃａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ． Ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ ｉｓ Ｏ（ｎ）． Ｋｅｙ ｗｏｒｄｓ：ｑｕａｄｒａｔｉｃ ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍ；Ｋａｒｕｓｈ—Ｋｕｈｎ－Ｔｕｃｋｅｒ（ＫＫＴ）ｃｏｎｄｉｔｉｏｎ；ｓｅｐａｒａｂｌｅ； Ｌａｇｒａｎｇｉａｎ 二次背包问题在现实生活中被广泛应用于金 融…、资本预算 、生产计划和工作调度 等方 面，并且二次背包问题在组合优化领域有着重要的 地位，无论是从实际应用和理论研究方面都引起了 广泛的关注 ．二次背包问题的各种特殊化情形在 诸多文献中都有研究，如决策变量为二元０—１二次 虽然二次背包问题是ＮＰ．ｈａｒｄ问题，但是由于 其被广泛应用，因此，很多人致力于解决此类问题， 并提出了有效的解法．文献［７］讨论了集中连续凸 规划问题的求解方法．文献［８］通过Ｋａｒｕｓｈ—Ｋｕｈｎ— Ｔｕｃｋｅｒ（ＫＫＴ）条件求解一系列连续的二次背包松弛 问题，提出了一种求解可分离凸二次背包问题的算 背包问题 Ｊ、结构系数为正整数的超模二次背包问 题 ｊ、二次成本系数矩阵为对角阵的可分离二次背 法．文献［１０］对可分离连续凸二次背包问题提出了 直接算法．Ｊｏｒｅ等¨ 针对凹可分离的二次背包问题 提出了算法．但对一般的非凸非凹的二次背包问题， 目前还未见到相关的直接算法． 包问题 、放弃决策变量整数要求的连续二次背包 松弛问题 等． 收稿日期：２００９－０５一ｌ３ 通信作者：陈伟（１９６５～），女，副教授，研究方向为整数规划．Ｅ—ｍａｉｌ：ｃｈｅｎｗｅｉ＠ｓｔａｆｆ．ｓｈｕ．ｅｄｕ．ｃｎ ３８８ 上海大学学报（自然科学版） 第ｌ６卷 当二次背包问题规模比较大时，经典的求解方 法会有一定的困难，但对于可分离的二次背包问题， 问题（Ｐ）的目标函数配方后，可化为－厂（ ）＝ 本研究利用其结构特性和ＫＫＴ条件提出一种快速 耋 （ 一ｎ ） 一ｃ ］，其中ｎ ＝一 ｄｉ．因为ｃ 求解的直接算法，考虑的问题模型（Ｐ。）如下： ｍｉｎｆ（ｘ）＝∑ｑｉ＝１ ｉ（ ）＝∑Ｃｉ＝１ ｉ ＋ｄｉ ， ｓ．ｔ．∑∞ ≤ ， Ｚ≤ ≤Ｍ， ≥０，Ｃ ≠０，ｉ＝１，２，…，ｎ， 且∑Ｏ）ｉｆ ≤ ≤∑０９ｉｕ ．当不限制ｃ １＞０，ｉ＝１，２， …，ｎ时，问题（Ｐ ）为非凸的二次背包问题． 本工作将讨论如何得到问题（Ｐ。）的一个局部 极小解，基本思想是先不考虑线性约束，找到问题 （Ｐ。）的一个理想解．如果理想解满足线性约束，那 么理想解就是最优解；如果理想解不满足线性约束， 则由本工作给出的定理和命题，可以限定拉格朗日 系数Ａ的取值范围，从而可逐步确定某些变量的最 优取值． １ 模型求解 可分离的二次背包问题（Ｐ ）通常具有以下 形式： ｍｉｎｆ（ｘ）＝∑ｑｉ（ ）＝∑Ｃｉ ＋ｄｉ ＝ｌ ｉ＝１ ｓ．ｔ．∑ ≤ ， ｌ≤ ≤ｕ，∞ ≥０，Ｃ ≠０，ｉ＝１，２，…，ｎ． 设∑ｗｉｌ ≤ ≤∑ＯＪｉ“ ，则问题（ ）一定有可 行解． 令 ，＿ ，则上述问题转化为 ｍｉｎ ）＝耋ｑ （ ：）＝耋毒２（ ） ＋毒 ：， ≤ ， ｆ ≤ ≤Ｍ ，Ｃ ≠０，ｉ＝１，２，…，ｎ． 为了方便起见，将问题设为（Ｐ），有 ｍｉｎｆ（ｘ）＝∑ｑｉ＝ｌ ｉ（ ）：∑Ｃｉ＝１ ｉ ＋ｄｉ ， ｓ．ｔ．∑ ≤ ，ｉ＝ｌ １≤ ≤Ｍ，ｃ ≠０，ｉ＝１，２，…，ｎ． 为已知数，所以问题（Ｐ）可转化为下列问题（Ｐ ）来 求解： ｍｉｎｆ（ｘ）＝∑ｑｉ（ ）＝∑Ｃｉ（ 一口。）。， Ｉ＝ｌ ｉ＝】 ｓ．ｔ．∑ ≤ ， ＝ｌ Ｚ≤ ≤Ｍ，ｃ ≠０，ｉ＝１，２，…，ｎ． 在此问题中，我们将指标集，＝｛１，２，…，ｎ｝分为两个 指标集，其中， ＝｛ｉ∈ＩＩｃ ＞０｝，，２＝｛ｉ∈ＩＩｃ ＜０｝． 问题（Ｐ ）的ＫＫＴ条件如下： ∑ ≤ ；ｉ＝ｌ （１） ｆ ≤ ≤Ｍ ，ｉ＝１，２，…，ｎ； （２） ２ｃ （ 一ｎ ）＋Ａ一１．１ ＋ ＝０，ｉ＝１，２，…， ；（３） ｄ ｎ Ａ（∑ — ）＝０； （４） ‘ ｌ （Ｚ 一 ）＝０，ｉ＝１，２，…，ｎ； （５） （ 一Ｍ ）＝０，ｉ＝１，２，…，ｎ； （６） ≥０，ｉ＝１，２，…，ｎ； （７） ≥０，ｉ＝１，２，…，ｎ； （８） Ａ≥０． （９） 如果不考虑线性约束∑ ≤ ，ＮＮ，Ｎ（Ｐ ）的理想 解为 ｌ ， 口 ≤Ｚ ，ｉ Ｅ，１， ｎ ，ｌ ＜０ ＜ ，ｉ∈，Ｉ， ， ｎ ≥ ，ｉ∈，ｌ， ≥ ， ∈，２， ，， 。 ＜ ０￡＜— ～，，ｚ∈ ∈１—２．・ 定理１若理想解 满足线性约束（１），则 一定为问题（Ｐ ）的最优解． 证明只需证明存在非负的拉格朗日系数，使 得ＫＫＴ条件（３）～（９）成立． 若存在 ＝。 使得式（５）～（８）成立，只需令 ＝０， ＝０．若使式（３）成立，则Ａ＝０．从而式（４） 和（９）成立． 对于其他 ＝ｆ 的分量，式（６）要成立，则 ＝ 第４期 任燕，等：可分离的二次背包问题的一种直接算法 ３８９ ０．又因为Ａ＝０，式（３）即为２ｃ （Ｘ 一。 ）一 ＝０．注 意到，若ｃ ＞０，只有当。 ≤１ 时，才有互＝１ ，所以 ＝２ｃ （曩一ａ ）≥２ｃ （１ —ａ ）≥０；若ｃ ＜０，只有当 Ⅱ ≥ 时，才有互：ｆ ，仍有 ＝２ｃ （ 一。 ）≥ ２ｃ １ 一Ｉ丁ｉ＋ｕｉ）＝ｃ （ｆ —ｕ ）≥０，所以式（７）成立． 对于其他互＝“ 的分量，若式（５）成立，则 ＝ ０．又因为Ａ＝０，代入式（３）有２ｃ （ —ａ ）＋ ＝０． 若Ｃ ＞０，只有当ａ ≥ｕ 时，才有 ＝ｕ ，此时∞ ＝ 一２ｃ （互一ａ ）：一２ｃ （Ｕ —ａ ）≥０；若ｃ ＜０，只有当 ＜ 妄 时，有 ：Ｍ ，此时 ：一２ｃ；（互一。 ）≥ 一２ｃｉ（ 一１丁ｉ ４－ｌｇｉ）＝一ｃ。（ｕ 一 ≥０，所以式（８）成 立．从而 是问题（Ｐ。）的最优解． 若对１≤ ≤ｎ，互≠ａ。，则理想解为 １ ，ｉ∈｛ａ ≤ｌｉ，ｉ∈，１｝Ｕ ≥ ， ∈ ）， ， ｉ∈｛ａ ≥ ，ｉ∈，ｌ｝Ｕ ＜ ， ∈ ）． 当ｃ ＞０，ａ ≤ｆ 时，有互＝ｌ ，而ｑ：（ ）＝２ｃ （ 一 口 ）：２ｃ；（ｆ 一。 ）＞１０；当ｃ ＜０， ≥ 时，有 ＝ 而 瓦）＝２ 互 ）≥２ｃ ）＝ ｃ （ｆ —ｕ ）＞０；当ｃ ＞０，ａ ≥ｕ 时，有 ＝１１， ，而 ｑ：（瓦）：２ｃｉ（ 一。 ）≤０；当 ＜０，血 ＜ 时，有 ＝“ ，而ｇ （ ）＝２ｃ （Ｍ 一ａ ）＜０，只需取０≤ ≤ ｍｉｎ｛一ｑ：（ ）Ｉ曩＝Ｕ ，ｉ＝１，２，…， ｝．当 ＝１ 时， 因ｑ：（ ）／＞０，则可令 ＝ｑ：（ ）＋Ａ，式（３）成立， 且 Ｉ＞０；当曩＝“ 时，因ｑ：（ ）≤０，则可令 ＝ 一ｇ （ ）一Ａ，使得式（３）～（８）成立．综上所述， 可以满足ＫＫＴ条件（３）～（９）．证毕． 由理想解的取值可知，当ｉ∈， ，ａ ≤１ 或ｉ∈１２， 口 ≥ 时，理想解 ： ．上述变量取到盒约束的 下限且使得９ （ ）最小，这些变量的取值已经相对 固定，无改进的必要．所以，下面我们不再考虑这些 变量，但为叙述简便，在讨论下述问题（Ｐ。）时，仍将 变量个数设为ｎ． ａｒｉｎｆ（ｘ）＝∑ｑｉ（ ）＝∑ｃ （ 一ａｉ）。， ｓ．ｔ．∑ ≤ ， Ｚ≤ ≤Ｕ，Ｃ ≠０，ｉ∈， ｕ ， 其中， ＝｛ｉ Ｉ ｃ ＞０，８ ＞ｆ ，１≤ｉ≤ｎ｛，， ：｛ｉ Ｉ ｃ。＜０， ，ｌ≤ ≤凡＿｝，且， Ｕ１２＝｛ｌ，２，…，ｎ｝． 问题（Ｐ ）的理想解为 一 ｆａ ，ｆ ＜ａ ＜“ ，ｉ∈，：， 【 ，ｉ∈｛口 ≥“ ，ｉ∈，：｝ｕ， ． 由定理１知，若 满足线性约束条件，则 为 最优解．以下考虑当理想解不满足线性约束时，如何 改进 ，从而得到最优解． 当∑ｉ＞ 时，理想解 不满足线性约束，如 果让每个变量都变小或保持当前的取值 ，那么 ∑ 将变小，直到满足线性约束．令 为通过上述 方法找到的问题（Ｐ ）的局部最优解，则一定有ｆ ≤ ≤墨．令 ＝ 一∑弓十互，若取 ＝ｙ ，则有 Ｊ １ Ｘｉ＋∑弓＝ｙ ＋∑亏＝ｙ一∑ ＋互＋∑弓＝ ．该式表示当其他分量不改变时，对第ｉ个变量，只 需从互减小到ｙ ，就可以满足线性约束条件（１）． 但如果同时减少ｍ个变量，则显然每个变量不必减 小到 ，就可使∑ ≤ｙ成立，所以 是第ｉ个变 量取值的下限，从而有 ≥ ．但由于盒约束ｚ ≤ ≤“ ，有 Ｉ＞１ ．所以变量 的最优值的取值范围 为［ ，互］，其中 ＝ｍａｘ｛ ，ｆ ｝． 定理２对于问题（Ｐ ），设 是（Ｐ。）的最优 解，贝０当Ｃ ＞０时，若 ∈［ ， ］，有ｑ （ ）≤ ｑ （ ）≤ （ ）；当Ｃ ＜０时，若 Ｅ［ｙ ， ］，则 ３９０ 上海大学学报（自然科学版） 第１６卷 有ｑ；（ｙ ）ｌ＞ｑ （ ）ｌ＞ｑ （ ），且ｑ （ ）＜０． 证明当ｃ。＞０时，ｑ：（ ）＝２ｃ （ 一口 ）为单调 一０ ）≤ ｑ （ ）为单调递减函数，则有９ （ 。 ）≥ｑ （ ）＝ ｑ （Ｍ ），故当Ｚ ＜ ≤“ 时， ＝０．因为 为最优 递增函数，则有２ｃ （ｙ 一ｎ ）≤２ｃ （ 解，所以 ≥０．由ＫＫＴ条件（３）知，ｇ （ ）＋Ａ＋ ２ｃ （互一０ ）．而 ｑ：（互）＝２ｃ （互～ｎ ）＝ ｒ０， Ｚ ＜０ ＜ ，ｉ∈，１， 【２ｃ （ 一ｒ上 ）≤０， ｎ ≥Ｍ ，ｉ∈，１， 即当ｉ∈， ， ∈［ ，曩］，有ｑ （ ）≤ｇ （ ）≤ ｑ：（ ）≤０． 当ｃ ＜０时，ｑ：（ ）＝２ｃ （ 一ｎ ）为单调递减函 数，即当ｉ∈Ｉ２， ∈［７ ， ］时，有ｑ：（ ｉ）≥ ｑ：（ ）≥ｑ：（互），且ｑ （ ）＝２ｃ （ＩＩ， 一０ ）＜ ２ｃｉ ） 一ｌｉ）＜０． 定理３对问题（Ｐ ），设 是（Ｐ。）的理想解， 是问题（Ｐ ）的最优解，Ａ， （１≤ｉ≤ｎ）为相对于 的拉格朗日系数．若存在ｉ∈， ，使得第ｉ个变量的 最优解满足ｆ ＜ ＜“ ，当 ≠ 时，如果有ｑ （ ）≤ ｑ （ ），则取 ＝ ，可满足拉格朗日系数 ≥０． 证明因为 是问题（Ｐ ）的最优解，且存在ｉ∈ ，，满足２ ＜Ｘｉ ＜Ｍ ，则为满足ＫＫＴ条件，令 ＝∞ ＝０， 且有ｇ （ ）＋Ａ：０．又因为 ≤ ≤ｘｉ，从而由定理 ２知，Ａ＝一ｑ （ ）≥０，且Ａ＜一ｑ：（２ ）． 对于 ≠ ，有弓≠ ，从而 ＝０．为满足ＫＫＴ条 件（３），应有 （ ）＋Ａ＋ ＝０．若取 ＝弓，则由 ｑ （弓）≤ｑ：（ ）得， ：一（ｑ （ ）＋Ａ）＝ 一（ｑ （ ）一ｑ：（ ））≥０．证毕． 定理４对问题（Ｐ ），设 是（Ｐ ）的理想解， 是问题（Ｐ。）的最优解，Ａ，∞ （１≤ｉ≤ｎ）为相对于 的拉格朗日系数．若存在ｉ∈１２，使得第ｉ个变量的 最优解 满足ｚ ＜ ≤ｕ ，则拉格朗日系数Ａ满足 Ａ≤一ｑ （互）＝一２ｃ （“ 一口 ）．若存在 （弓）≤ ｑ （互），令 ＝ ，可满足拉格朗日系数 ≥０． 证明对问题（Ｐ ），当Ｃ ＜０时，有 ＝ｕ。．而 ＝０．从而可得Ａ≤一ｑ：（ ）≤一ｑ：（五）． 由理想解的取值知 ≠ｚ ，所以 ，＝０．为满足 ＫＫＴ条件（３），应有ｑ；（ ）＋Ａ＋（ｃＪ ＝０．若取 ， ＝ 弓，则由ｑ （ ）≤ｑ：（互），可得 ＝一（ｑ （ ）＋ Ａ）≥一（ｑ；（ ）一ｑ；（ ）＞１０．证毕． 由定理３知，当ｉ∈， ， 的最优值的取值范围 为［ ，曩］，有ｑ：（ｙ ）≤ｑ （Ｘｉ ）≤ｑ：（ ）．如果 ≠ｚ 或 ＝ｆ ， ≠ｆ ，则一定有Ａ≤一ｑ：（ｙ ）．当 ｉ∈，２， 的最优解的取值范围为［ｙ ，ｘｉ］，由定理４ 知，Ａ≤一ｑ （ ）．所以这两个定理给出了Ａ的取值 范围． 定理５若存在ｉ∈， ，有一ｑ （ ）＜Ａ，其中Ａ 为最优解对应的拉格朗日系数，为满足ＫＫＴ条件， 则第ｉ个变量的最优解为 ＝ ：ｚ ． 证明若 ≠ｙ ，则有 ＞Ｚ ，从而有 ＝０． 若 ＝Ｍ ，由ＫＫＴ条件（３）知，ｑ （ ）十Ａ＋ ＝０． 可得 ＝一ｑ：（ ）一Ａ＜一ｑ （ｙ ）一Ａ＜０，与ＫＫＴ 条件矛盾．若Ｚ ＜ 。 ＜ ，则有 ＝∞ ＝０，则由ＫＫＴ 条件（３）知，ｑ：（ ）＋Ａ＝０．可得Ａ＝一ｑ：（ ）＜ 一ｇ （ ），这与题意矛盾． 若 ＝ ≠ｆ ，则有 ＝（ｃＪ。＝０，则由ＫＫＴ条件 （３）知，ｑ （ ）＋Ａ：０，可得Ａ＝一ｇ：（ ）＜ 一ｑ：（ｙ ），与ＫＫＴ条件矛盾．若 ＝ｙ ：ｆ ，则有 ∞ ＝０，则由ＫＫＴ条件（３）知，ｑ （ ）＋Ａ＋ ＝０．可 得ｚ， ＝ｑ （ ）＋Ａ＝ｑ：（ ）＋Ａ＞０． 综上所述，只有当 ＝ ＝ｆ 时，才能满足 ＫＫＴ条件．证毕． 定理６若存在ｉ∈１２，有一ｑ：（ ）＜Ａ，其中Ａ 为最优解对应的拉格朗日系数，为满足ＫＫＴ条件， 则第ｉ个变量的最优解为 ｉ ＝ ｉ＝ｆｉ． 证明仿照定理５． 定理７ 若存在 ｉ＝ｚ ，且ｑ：（７ ）≥０，则取 第４期 任燕，等：可分离的二次背包问题的一种直接算法 ３９１ ＝ ，可满足 Ｉ＞０． 证明若取 ：ｆ ，可令∞ ＝０，对于任意非负 的拉格朗日系数Ａ≥０．为满足ＫＫＴ条件（３）， ｑ （ ）＋Ａ一 ＝０，所以有 ＝ｑ （ ）＋Ａ＞１０． 定理８ 假定 ＝（ ， ，…， ）是问题 （Ｐ，）的最优解，若存在ｉ≠ ，１≤ｉ， ≤凡，满足ｆ ＜ ＜ｕ ，Ｚ ＜ ｆ ＜ ，，则有 ｃ （ 一 ）＝ （ 一ａｊ）． 证明 由于 是问题（Ｐ．）的最优解，且满足 ＫＫＴ条件，从而得 ＝０９ ＝ ，：ＯＪｊ＝０．由２ｃ （ 一 ０ ）＋Ａ＝０，２ｃｉ（Ｘｊ 一 ）＋Ａ＝０，所以有 ｃ （ 一０ ）＝ （ 一ａｊ）． 证毕． 本研究将最优解 ，ｉ∈，满足ｆ ＜ ＜ｕ 的指 标集合记为， ，并记 ＝ 一∑ ．由定理６知， 对任意的ｉ， ∈， ，有ｃ （ 一口 ）：ｃｊ（Ｘｊ 一ａｊ）．可得 ｃ＝Ｊ（、ｘ 一ａｊ）＋０ ．若∑ ＝ｙ 成立，则问题 （Ｐ ）的线性约束被满足，即 ｉ ｅｌ＇ ＼Ｃｉ Ｊ 一 ）＋。 卜 ， 可得 ２求解二次背包问题的算法 ２．１算法思想 算法的基本思想是通过调节Ａ的取值范围，在 寻求 的同时，逐步确定各个变量的最优取值．由定 理３，当ｉ∈， 时，可以通过一ｑ：（ ）来限定Ａ的上 限．由定理４知，当ｉ∈１２时，可以通过一ｑ （ ）来限 定Ａ的上限．找到一ｑ （ ），ｉ∈，。和一ｑ （ ），ｉ∈１２ 中最小的一个值，记为Ａ㈩，并将满足Ａ 的指标记 人集合，Ｊ。．先限定０≤Ａ≤Ａ（１１，若存在ｇ （ ）≤ 一Ａ…，则令ｘｊ ＝ ，将指标 记人集合 ，然后利 用定理８和线性约束条件求得，＿ 中变量的值．若 求出的解对应的拉格朗日系数小于等于Ａ…，则最 优解即为所求的值．若求得解对应的拉格朗日系数 大于给定的Ａ…，则由定理５和定理６知，对 中的 指标对应的变量的最优解应取其下界，将此变量删 除，重新计算 ，ｉ∈，，然后重复上述过程，直至找到 最优解． 应该注意的是，当求得解对应的拉格朗日系数大 于Ａｆｌ１时，且 。中的元素不止一个时，应当取 ＝ｆ等 ， 其中 为满足ｑ （ ）＝ｍａｘ｛ｇ （ｙｆ）｝的指标，将ｋ从 ，，中删除．下面就问题（Ｐ ）给出具体的算法． 步０：令Ｊ『＝｛１，２，…， ｝，计算 ｌ ， ≤ｌ ，Ｃ ＞０， ０ ，ｌ ＜ｒ上 ＜ ，ｃ ＞０， ｕ ， ０ ≥ｕ ，Ｃ ＞０， ，ｃ ＜０， 。 ≥ ，ｃ ＜０． 步１：若∑互≤’，，则 为最优解，停止．否则 进入步２． 步２：对于１≤ｉ≤凡，若存在互＝ｆ ，令 ＝Ｚ ， ，＝八｛ｉ｝， ＝ —ｆ ． 步３：Ｌ＝ ，Ｕ＝（２ｊ． 步４：若，一Ｌ＝ ，则对ｉ∈，， ＝ｆ 为最优解， 停止．若，一，Ｊ≠ ，令，＝，一，Ｊ，进入步５． 步５：对于ｉ Ｅ，，计算 ＝ 一∑互＋互，若对 Ｅ ｌ 任意的ｉ∈，，有 ＝ ，则最优解为 ｆｆｆ， ｉ∈Ｌ， ＝？ 【 ， ｉ∈，， 停止．否则进入步６． 步６：对于ｉ∈，，令ｙ ＝ｍａｘ｛ ，ｆ ｝，记Ｗ＝ ｔｊｌ ＜０， ＝ ，ｑ （ ）＞１０， ∈Ｉｔ，若Ｗ＝（２ｊ，贝４进 入步７；若 ≠ ，则令 ＝ｆ ，Ｌ＝Ｌ Ｕ｛ｋ｝， ＝ 一 ，返回步４（其中 为满足ｑ （瓦）＝ｍ ａ ｘ｛ｑ （ ） 的指标）． 步７：对于ｉ∈，，当ｃ ＞０时，令Ａ ＝一ｑ （ｙ ）， 当ｃ ＜０时，令Ａ ＝一ｑ：（ ）．取Ａ 中最小值记为 Ａ（１），并记Ｌｌ＝｛ｉＩ Ａ ＝Ａ（１）｝． 步８：对于每一个 ∈，，若ｇ （ ）≤一Ａ【Ｉ），则 ３９２ 上海大学学报（自然科学版） 第１６卷 令 ＝瓦，Ｕ＝ＵＵ ． 步９：若ｙ一∑弓＜０，则令 ＝ｌｋ（其中 为 满足ｇ （ ） ｛ （ ）｝的指标），Ｌ＝，Ｊ ｕ｛ ｝， ｛【 ｉ， ｉ∈Ｕ， ， ∈，一 由算法可知，本研究是通过调节拉格朗日系数 Ａ的范围来找到问题（Ｐ．）的最优解．由步７，８，９，１１ ｙ＝ｙ—ｆ ，返回步４；若 一∑ ≥０，且，一 ＝ ， 则最优解为 ｒ Ｚ ， ∈Ｌ， ＝Ｊ 【互， ｉ∈Ｕ， 停止．若，一 ≠ ，且 一∑写≥０，则进入步１０． 步１０：对于任意的 ∈，一 ，有 一∑互一∑口 ■囊＿’ 并计算Ａ ＝一２ｃ （ 一ｎ ），ｉ∈，一 ． 步１１：若Ａ ＞Ａ㈩，则Ｘ，ｋ ＝Ｚ （其中 为满足 ｇ （ ）＝ｍ ａｘｔ ｑ （ ）｝的指标），Ｌ＝Ｌ Ｕ｛ ｝， ．一 ，返回步４；若Ａ ≤Ａ ，则最优解为 ｒｆ ， ｉ∈Ｌ， ｛Ｉ 互， ｉ∈Ｕ， 【 ， ｉ∈，一 ， 停止． 步０和步１是初始化过程，求得理想解并判断 这个理想解是否是原问题的最优解；步２将问题 （Ｐ ）转化为问题（Ｐ ）；步３和步４是判断算法是否 向下继续的条件；步５和步７先确定拉格朗日系数 的一个上限；步６依据定理７确定某些分量的最优 取值，并记人集合，Ｊ，返回到步４；步８是在步７已确 定拉格朗日系数Ａ的一个取值范围的基础上，由 ＫＫＴ条件确定某些分量的值，并将其记人集合 ；步 ９是判断步７确定的拉格朗日系数Ａ的取值范围是 否合适；步ｌ０是运用定理８来计算未确定值的分量 的值，并计算相应的拉格朗日系数Ａ ；步１１表明，如 果计算的Ａ 大于步６所确定的拉格朗日系数Ａ的 上限，则 ＝ｆ （其中 为满足ｑ （ ）＝ ｍ ａｘｔ ｇ （ ）｝的指标），Ｌ＝ ｕ｛ ｝， —ｆ ，返回 ．步４；若Ａ 在限定的范围内，则最优解为 知，最多只需对拉格朗日系数Ａ的范围进行ｎ次调 节，其中ｎ为原问题中变量的个数．对于每个变量， 只需要计算 ，ｑ：（ ）和ｑ：（ ）．那么，此算法的 计算复杂度为０（ｎ），其中ｎ为变量的个数，这比经 典算法或其他方法有效．本工作主要讨论对连续的 可分离的二次背包问题的求解算法．对于可分离的 二次整数背包问题，可以通过将二次整数规划问题 松弛化，转化为本工作中讨论的问题，找到连续问题 的最优解；然后利用其他方法（例如分支定界算法） 进一步求解整数问题． 例１ ａｒｉｎ ）＝（ 】一２） ＋２（ｘ２—１） ＋（ ３—３） 一 ２（ ４＋１） 一３（ ５＋１） ， Ｓ．ｔ． １＋ ２＋…＋ ５≤８， ０≤ １≤３，０≤ ２≤３，０≤ ３≤４， ０≤ ４≤２，０≤ ≤２， 计算结果如表１所示．表中， 为循环次数， 为理 想解， 为算法中步６确定的集合，Ａ…为算法中步 ７确定的Ａ的上限，Ａ 为算法中步ｌＯ确定的拉格朗 日系数， 为问题的最优解． 表１例１的计算结果 Ｔａｂｌｅ １ Ｒｅｓｕｌｔ ｏｆ ｔｈｅ ｅｘ￣ｐｌｅ １ Ａ（１） Ａ Ａ ≤Ａ（１） １（２，１，３，２，２） ４ １．６ 是 （１．２，０．６，２．２，２，２） 经过ＫＫＴ条件验证， ＝（１．２，０．６，２．２，２，２） 为例１的一个局部最优解，最优值为一４３．４．由 Ｍａｔｌａｂ软件求解得到的最优解为 ＝（０，０．６６６ ７， ３．３３３ ３，２．０００ ０，２．０００ ０），最优值为一４０．７． 例２ ｒａｉｎ ）＝３（ 】一２） ＋３（ ２—２）。＋４（ｘ３—３） 一 （ ４＋１） 一２（ｘ５＋１） 一（ ６＋２） ， ｓ．ｔ． ｌ＋ ２＋…＋ ６≤１３， ０≤ ｌ≤３，０≤ ２≤４，０≤ ３≤３， ０≤ ４≤２，０≤ ５≤３，０≤ ６≤４， 计算结果如表２所示． 第４期 任燕，等：可分离的二次背包问题的一种直接算法 ３９３ 表２例２的计算结果 例３ Ｔａｂｌｅ ２ Ｒｅｓｕｌｔ ｏｆ ｔｈｅ ｅｘａｍｐｌｅ ２ ｍｉｎ ） ＝ｘ１—２） ＋２（ ２—１） ＋（ ３—３） ＋ ｋ Ｗ Ａ（１）Ａ Ａ ≤Ａ（１） （ ４—４） ＋３（ ５—１） 一２（ｘ６＋１） 一（ ７—１） 一 ３ 一（ ９＋２） 一２（ｘｌｏ＋１） ， Ｓ．ｔ． ｌ＋ ２＋…＋ ｌｏ≤１５， 经过ＫＫＴ条件验证， ＝（１．６４，１．６４，２．７２，０， ０≤ ｌ≤２，０≤ ２≤３，０≤Ｘ３≤４， ３，４）为例２的一个局部最优解，最优值为一６７．９．由 ０≤ ４≤３，０≤ ５≤２，０≤ ６≤３，０≤ ７≤４， Ｍａｔｌａｂ软件求解得到的最优解为 ＝（１．５，１．５，３， ０≤ ８≤３，０≤ ９≤１，０≤ ｌｏ≤２， ０，３，４），最优值为一６７．５． 计算结果如表３所示． 表３例３的计算结果 Ｔａｂｌｅ ３ Ｒｅｓｕｌｔ ｏｆ ｔｈｅ ｅｘａｍｐｌｅ ３ 经过ＫＫＴ条件验证， ＝（１．６５，０．８３，２．６５，３， ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍ ｗｉｔｈ ｓｅｒｉｅｓ ｐａｒａｌｌｅｌ ｓｕｐｐｏｒｔ［Ｊ］． ０．９２，３，０，０，１，２）为例３的一个局部最优解，最优值 Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ Ｌｅｔｔｅｒｓ，２００２，３０（３）：１５９—１６６． 为一５８．７；由Ｍａｔｌａｂ软件求解得到的最优解为 ＝ ［６］ ＣＡＰＲＡＲＡ Ａ，ＰＩＳＩＮＧＥＲ Ｄ，ＴＯＴＨ Ｐ．Ｅｘａｃｔ ｓｏｌｕｔｉｏｎ ｏｆ （１．６，０．８，３．６，３，０，３，０，０，１，２），最优值为一５５．４． ｔｈｅ ｑｕａｄｒａｔｉｃ ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍ［Ｊ］．Ｉｎｆｏｒｍｓ Ｊｏｕｒｎａｌ ｏｎ 由上述３个例题知，通过此算法得到的最优值 Ｃｏｍｐｕｔｉｎｇ，１９９９，１ｌ：１２５—１３７． 好于采用Ｍａｔｌａｂ软件运用分支定界算法得到的最 ［７］ ＢＲＥＴＦＨＡＵＥＲ Ｋ Ｍ，ＳＨＥＴＦＹ Ｂ．Ｔｈｅ ｎｏｎｌｉｎｅａｒ ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍ—ａｌｇｏｒｉｔｈｍｓ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ［Ｊ］．Ｅｕｒｏｐｅａｎ 优值． Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎ Ｒｅｓｅａｒｃｈ，２００２，１３８（３）：４５９４７２． ［８］ ＢＲＥＴＦＨＡＵＥＲ Ｋ Ｍ。ＳＨＥＴＴＹ Ｂ，ＳＹＡＭ Ｓ．Ａ ｂｒａｎｃｈ ａｎｄ 参考文献： ｂｏｕｎｄ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｉｎｔｅｇｅｒ ｑｕａｄｒａｔｉｃ ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍｓ ［Ｊ］．ＯＲＳＡ Ｊｏｕｒｎａｌ ｏｎ Ｃｏｍｐｕｔｉｎｇ，１９９５，７（１）：１０９一 ＭＡＲＫＯＷＩＴＺＥ Ｈ Ｍ．Ｐｏｒｆｏｌｉｏ ｓｅｌｅｃｔｉｏｎ： ｅｆｆｃｌｅｎｔ ｌ１８． ｄｉｖｅｒｓｉｆｉｃａｔｉｏｎ ｏｆ ｉｎｖｅｓｔｍｅｎｔ［Ｍ］．Ｎｅｗ Ｙｏｒｋ：Ｗｉｌｅｙ， ［９］ ＰＡＲＤＡＬＳ Ｐ Ｍ，ＫＯＶＯＯＲ Ｎ．Ａｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａ ｓｉｎｇｌｙ １９５９：１２９—１８８． ｃｏｎｓｔａｉｎｅｄ ｃｌａｓｓ ｏｆ ｑｕａｄｒａｔｉｃ ｐｒｏｇｒａｍｓ ｓｕｂｊｅｃｔ ｔｏ ｕｐｐｅｒ ［２］ ＢＥＲＮＨＡＲＤ Ｒ Ｈ．Ｍａｔｈｅｍａｔｉｃａｌ ｐｒｏｇｒａｍｍｉｎｇ ｍｏｄｅｌｓ ｆｏｒ ａｎｄ ｌｏｗｅｒ ｂｏｕｎｄｓ［Ｊ］．Ｍａｔｈｅｍａｔｉｃａｌ Ｐｒｏｇｒａｍｍｉｎｇ， ｃａｐｔｉｌａ ｂｕｄｇｅｔｉｎｇ－－ａ ｓｕｒｖｅｙ ｇｅｎｅｒａｌｉｚａｔｉｏｎ ａｎｄ ｃｒｉｔｉｑｕｅ １９９０，４６：３２ｌ一３２８． ［Ｊ］．Ｊｏｕｒｎａｌｓ ｏｆ Ｆｉｎａｎｃｉａｌ Ｑｕａｒｔｅｒｌｙ Ａｎａｌｙｓｉｓ，１９６９，４： ［１０］ 华中生，张斌．求解可分离连续凸二次背包问题的直 ｌｌ１．１５８． 接算法［Ｊ］．系统工程与电子技术，２００５，２７（２）：３３１— ［３］ ＭＯＤＥＲ Ｊ Ｊ．ＰＨＩＬＩＰＳ Ｃ Ｒ．Ｐｒｏｊｅｃｔ ｍａｎａｇｅｍｅｎｔ ｗｉｔｈ ３３４． ＣＰＭ ａｎｄ ＰＥＲＴ『Ｍ１．Ｎｅｗ Ｙｏｒｋ：Ｒｈｅｉｎｈｏｌｄ，１９６４： ［１１］ ＪＯＲＥ Ｊ Ｍ．ＳＴＥＰＨＥＮ Ａ Ｖ．Ｏｎ ｔｈｅ ｓｏｌｕｔｉｏｎ ｏｆ ｃｏｎｃａｖｅ ｌ１９—１３５． ｋｎａｐｓａｃｋ ｐｒｏｂｌｅｍｓ［Ｊ］．Ｍａｔｈｅｍａｔｉｃａｌ Ｐｒｏｇｒａｍｍｉｎｇ， ［４］ ＫＥＬＬＥＶＥＲ Ｈ，ＰＦＥＲＳＣＨＹ Ｕ，ＰＩＳＩＮＧＥＲ Ｄ．Ｋｎａｐｓａｃｋ １９９１，４９：３９７－４１１． ｐｒｏｂｌｅｍｓ［Ｍ］．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，２００４：３４—８８． （编辑：孟庆勋） ［５］ ＲＡＤＥＲＪＩ Ｄ Ｊ，ＷＯＥＩＧＩＮＥＲ Ｇ Ｊ．Ｔｈｅ ｑｕａｄｒａｔｉｃ ０—１
发布评论