多约束非线性背包问题的拉格朗日对偶方法

摘要

多约束非线性背包问题是一类特殊而重要的整数规划问题，它可以定义为在有限整数集上极大化一个可分离非线性函数的多约束(可分离)最优化问题。由于这类问题在资源分配，工业生产及计算机网络的最优化模型中有着十分广泛的应用，因此研究非线性背包问题的算法具有十分重要的现实意义。本文所讨论的多约束非线性背包问题可以描述如下： maxf(x)=n∑j=1fj(xj)s.t.gi(x)=n∑j=1gij(xj)≤bi，i=1，…，m，x∈X={lj≤xj≤uj，xj整数，j=1，…，n}，其中fj，gij为定义在[lj,uj]上的单调递增函数，lj和uj为整数，分别表示整数变量xj的下界和上界，bi是常数。 本文根据背包问题的结构特点，提出了拉格朗日对偶和区域分割方法，并用此算法求解了多约束非线性背包问题。利用外逼近方法求解对偶问题以得到上界，为了消除对偶间隙以保证算法的收敛性，我们利用区域割技术丢掉某些整数箱子，并把剩下的区域划分为一些整数箱子的并集，以便使拉格朗日松弛问题能有效求解，并使算法在有限步内收敛到最优解。算法的特色和创新之处是把外逼近方法用于求解对偶问题并与区域分割有效结合起来解决多约束非线性背包问题。本文还将传统的次梯度方法运用到算法中，并将得到的数值结果与外逼近方法进行了比较，我们的数值结果揭示了外逼近方法在求解多约束非线性背包问题的对偶问题时明显优于次梯度方法。此外，我们还对来自实际应用中的多约束非线性背包问题进行了大量的数值试验。 本文总共分为五章，第一章简单地介绍了非线性背包问题的模型，以及它与整数规划问题算法的研究现状和研究进展。第二章简单介绍了求解非线性背包问题(单约束)的现有的算法，以及求解多约束非线性背包问题的研究进展，如：分枝定界算法，约束替代松弛算法以及动态规划与分枝定界的混合算法。第三章是我们的主要结果，提出了一种新的拉格朗日对偶和区域割算法求解多约束非线性背包问题。第四章是我们的数值试验部分，主要介绍一些数值试验的结果。另外，还把拉格朗日和区域割算法中使用外逼近方法求上界的数值结果与传统的次梯度方法进行了比较，并将此算法与基于分枝定界和动态规划的混合算法进行了比较。第五章是结论部分，是对本文结果的总结以及对未来研究的展望。

目录

文摘

英文文摘

原创性声明及本论文使用授权说明

第一章前言

§1.1多约束非线性背包问题的定义

§1.2多约束非线性背包问题的应用模型

§1.3多约束非线性背包问题的研究现状和研究进展

第二章多约束非线性背包问题的现有算法

§2.1非线性凸整数规划的分枝定界算法

§2.2二次多约束非线性背包问题的约束替代松弛算法

§2.3一般整数规划问题的分枝定界和动态规划混合算法

第三章多约束非线性背包问题的一种新的有效算法

§3.1拉格朗日对偶

§3.2区域分割及其替代约束

§3.3主要算法及例子

第四章数值试验

§4.1问题模型描述

§4.2数值结果与比较

第五章结论

参考文献

作者在攻读硕士学位期间公开发表的论文

致谢