论文部分内容阅读
非线性背包问题是一类特殊的非线性整数规划问题.由于在管理,经济以及工业生产的最优化模型中的广泛应用,它在非线性整数规划中担当着十分重要的角色.一个非线性背包问题可描述如下:max f(x) =∑<,j=1> f<,j>(x<,j>) s.t.g(x) = ∑<,j=1>g<,j>(x<,j>) ≤ b, x ∈ X = {x | l<,j> ≤ x<,j> ≤ u<,j>, x<,j> integer},其中f<,j>,g<,j>为定义在[l<,j>,u<,j>]上的连续实函数,l<,j>和u<,j>分别是变量x<,j>的下界和上界.不失一般性,设l<,j>,u<,j>为整数,这里j=1,...,n.本文研究的主要问题是两类非线性背包问题-凸背包问题和凹背包问题.根据这两类背包问题的单调性和凸性,本文给出了0-1线性化方法.凸背包问题可以直接转化成一个等价的0-1线性背包问题,然后通过隐枚举法或动态规划法解这个0-1线性背包问题就可以得到原凸背包问题的最优解.本文把这种0-1线性化方法同Pegging方法以及拉格朗日对偶和区域割方法做了数值比较,数值结果充分体现了0-1线性化算法的有效性和优越性.而对于凹背包问题,首先用一个线性函数逼近目标函数,约束条件不变,这样就得到了一个目标函数是线性函数的凸背包问题,接下来就可以把得到的这个凸背包问题转化成一个等价的0-1线性背包问题,同样可用隐枚举法求解这个0-1线性背包问题.为了保证收敛性,我们利用函数的单调性和区域割技巧丢掉一些整数箱子,然后把保留下来的区域分割成一些整数箱子的并集.本文共由五章组成.第一章是前言部分,对非线性背包问题作了简单的介绍,并给出了几个非线性背包问题的模型;第二章介绍了求解非线性背包问题的现有算法;第三章给出了凸背包问题的0-1线性化方法和数值结果,以及解0-1线性背包问题的几个常用算法,并与Pegging方法,拉格朗日对偶和区域割方法做了数值结果比较;第四章着重介绍了凹背包问题的0-1线性化分支定界算法;第五章是本文工作的总结以及对未来的研究展望.