多約束非線性背包問題的拉格朗日對偶方法.pdf

1、多約束非線性背包問題是一類特殊而重要的整數(shù)規(guī)劃問題，它可以定義為在有限整數(shù)集上極大化一個可分離非線性函數(shù)的多約束(可分離)最優(yōu)化問題。由于這類問題在資源分配，工業(yè)生產(chǎn)及計算機(jī)網(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，x∈X={lj

2、≤xj≤uj，xj整數(shù)，j=1，…，n}，其中fj，gij為定義在[lj,uj]上的單調(diào)遞增函數(shù)，lj和uj為整數(shù)，分別表示整數(shù)變量xj的下界和上界，bi是常數(shù)。 本文根據(jù)背包問題的結(jié)構(gòu)特點，提出了拉格朗日對偶和區(qū)域分割方法，并用此算法求解了多約束非線性背包問題。利用外逼近方法求解對偶問題以得到上界，為了消除對偶間隙以保證算法的收斂性，我們利用區(qū)域割技術(shù)丟掉某些整數(shù)箱子，并把剩下的區(qū)域劃分為一些整數(shù)箱子的并集，以便使拉格朗日松弛

3、問題能有效求解，并使算法在有限步內(nèi)收斂到最優(yōu)解。算法的特色和創(chuàng)新之處是把外逼近方法用于求解對偶問題并與區(qū)域分割有效結(jié)合起來解決多約束非線性背包問題。本文還將傳統(tǒng)的次梯度方法運用到算法中，并將得到的數(shù)值結(jié)果與外逼近方法進(jìn)行了比較，我們的數(shù)值結(jié)果揭示了外逼近方法在求解多約束非線性背包問題的對偶問題時明顯優(yōu)于次梯度方法。此外，我們還對來自實際應(yīng)用中的多約束非線性背包問題進(jìn)行了大量的數(shù)值試驗。 本文總共分為五章，第一章簡單地介紹了非線性

4、背包問題的模型，以及它與整數(shù)規(guī)劃問題算法的研究現(xiàn)狀和研究進(jìn)展。第二章簡單介紹了求解非線性背包問題(單約束)的現(xiàn)有的算法，以及求解多約束非線性背包問題的研究進(jìn)展，如：分枝定界算法，約束替代松弛算法以及動態(tài)規(guī)劃與分枝定界的混合算法。第三章是我們的主要結(jié)果，提出了一種新的拉格朗日對偶和區(qū)域割算法求解多約束非線性背包問題。第四章是我們的數(shù)值試驗部分，主要介紹一些數(shù)值試驗的結(jié)果。另外，還把拉格朗日和區(qū)域割算法中使用外逼近方法求上界的數(shù)值結(jié)果與傳統(tǒng)