非線性背包問題的0-1線性化方法.pdf

1、非線性背包問題是一類特殊的非線性整數規(guī)劃問題.由于在管理,經濟以及工業(yè)生產的最優(yōu)化模型中的廣泛應用,它在非線性整數規(guī)劃中擔當著十分重要的角色.一個非線性背包問題可描述如下:max f(x) =<'n>∑<,j=1> f<,j>(x<,j>) s.t.g(x) = <'n>∑<,j=1>g<,j>(x<,j>) ≤ b, x ∈ X = {x | l<,j> ≤ x<,j> ≤ u<,j>, x<,j> integer},其中f<,j>,

2、g<,j>為定義在[l<,j>,u<,j>]上的連續(xù)實函數,l<,j>和u<,j>分別是變量x<,j>的下界和上界.不失一般性,設l<,j>,u<,j>為整數,這里j=1,...,n.本文研究的主要問題是兩類非線性背包問題-凸背包問題和凹背包問題.根據這兩類背包問題的單調性和凸性,本文給出了0-1線性化方法.凸背包問題可以直接轉化成一個等價的0-1線性背包問題,然后通過隱枚舉法或動態(tài)規(guī)劃法解這個0-1線性背包問題就可以得到原凸背包問題的

3、最優(yōu)解.本文把這種0-1線性化方法同Pegging方法以及拉格朗日對偶和區(qū)域割方法做了數值比較,數值結果充分體現了0-1線性化算法的有效性和優(yōu)越性.而對于凹背包問題,首先用一個線性函數逼近目標函數,約束條件不變,這樣就得到了一個目標函數是線性函數的凸背包問題,接下來就可以把得到的這個凸背包問題轉化成一個等價的0-1線性背包問題,同樣可用隱枚舉法求解這個0-1線性背包問題.為了保證收斂性,我們利用函數的單調性和區(qū)域割技巧丟掉一些整數箱子,

4、然后把保留下來的區(qū)域分割成一些整數箱子的并集.本文共由五章組成.第一章是前言部分,對非線性背包問題作了簡單的介紹,并給出了幾個非線性背包問題的模型;第二章介紹了求解非線性背包問題的現有算法;第三章給出了凸背包問題的0-1線性化方法和數值結果,以及解0-1線性背包問題的幾個常用算法,并與Pegging方法,拉格朗日對偶和區(qū)域割方法做了數值結果比較;第四章著重介紹了凹背包問題的0-1線性化分支定界算法;第五章是本文工作的總結以及對未來的研究