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

1、非線性背包問題是一類特殊的非線性整數(shù)規(guī)劃問題.由于在管理,經(jīng)濟(jì)以及工業(yè)生產(chǎn)的最優(yōu)化模型中的廣泛應(yīng)用,它在非線性整數(shù)規(guī)劃中擔(dān)當(dāng)著十分重要的角色.一個非線性背包問題可描述如下: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ù)實函數(shù),l<,j>和u<,j>分別是變量x<,j>的下界和上界.不失一般性,設(shè)l<,j>,u<,j>為整數(shù),這里j=1,...,n.本文研究的主要問題是兩類非線性背包問題-凸背包問題和凹背包問題.根據(jù)這兩類背包問題的單調(diào)性和凸性,本文給出了0-1線性化方法.凸背包問題可以直接轉(zhuǎn)化成一個等價的0-1線性背包問題,然后通過隱枚舉法或動態(tài)規(guī)劃法解這個0-1線性背包問題就可以得到原凸背包問題的

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

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