多約束非線性背包問題的替代對偶方法.pdf

1、非線性背包問題是一類特殊而重要的非線性整數(shù)規(guī)劃問題，它可以定義為在有限整數(shù)集上極大化一個可分離非線性函數(shù)的約束(可分離)最優(yōu)化問題.由于這類問題在經(jīng)濟管理，金融投資，資源分配，工業(yè)生產(chǎn)及計算機網(wǎng)絡(luò)的最優(yōu)化模型中有著十分廣泛的應(yīng)用，因此研究非線性背包問題的算法具有重要的現(xiàn)實意義.本文所討論的多約束非線性背包問題可以描述如下： maxf(x)=n∑j=1fj(xj)s.t.gi(x)=n∑j=1gij(xj)≤bi，i=1，…，m，

2、x∈X={lj≤xj≤uj，xj為整數(shù)，j=1，…，n}，其中fj，gij為定義在[lj，uj]上的單調(diào)遞增函數(shù)，lj和uj為整數(shù)，分別表示整數(shù)變量xj的下界和上界，bi是常數(shù)，這里i=1，…，m，j=1，…，n. 本文根據(jù)背包問題的結(jié)構(gòu)特點，提出了一種替代對偶(surrogatedual)方法和區(qū)域分割方法來解這類多約束非線性背包問題.我們用替代松弛方法把多約束問題化為單約束問題，并利用0-1線性化方法求解替代松弛問題.為得到

3、更緊的上界，消除對偶間隙以保證算法的收斂性，我們利用割平面方法求解替代對偶問題，利用區(qū)域割技術(shù)丟掉某些整數(shù)箱子，并把剩下的區(qū)域劃分為一些整數(shù)箱子的并集，以便使替代松弛問題能有效求解，使算法在有限步內(nèi)收斂到最優(yōu)解.算法的特色和創(chuàng)新之處是把替代松弛方法用于求解對偶問題并與區(qū)域分割有效結(jié)合起來解決多約束非線性背包問題.數(shù)值結(jié)果表明本文提出的方法可以較有效地求解大規(guī)模多約束非線性背包問題.此外，我們還對來自實際應(yīng)用中的多約束非線性背包問題進行了

4、大量的數(shù)值試驗. 本文總共分為五章，第一章簡單介紹了非線性背包問題的背景和應(yīng)用，整數(shù)規(guī)劃問題算法的研究現(xiàn)狀和研究進展，并介紹了本文的主要內(nèi)容.第二章簡單介紹了求解非線性背包問題(單約束)的現(xiàn)有的算法，如：分枝定界算法，動態(tài)規(guī)劃與分枝定界的混合算法，0-1線性化方法，以及拉格朗日對偶與區(qū)域割算法等.第三章介紹替代對偶理論，包括替代松弛理論以及替代對偶搜索的幾種經(jīng)典算法.第四章介紹我們的非線性背包問題的替代對偶和區(qū)域割算法，并給出了