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

1、多約束非線性背包問題是一類特殊而重要的整數(shù)規(guī)劃問題，它可以定義為在有限整數(shù)集上極大化一個(gè)可分離非線性函數(shù)的多約束(可分離)最優(yōu)化問題。由于這類問題在資源分配，工業(yè)生產(chǎn)及計(jì)算機(jī)網(wǎng)絡(luò)的最優(yōu)化模型中有著十分廣泛的應(yīng)用，因此研究非線性背包問題的算法具有十分重要的現(xiàn)實(shí)意義。本文所討論的多約束非線性背包問題可以描述如下： 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)特點(diǎn)，提出了拉格朗日對偶和區(qū)域分割方法，并用此算法求解了多約束非線性背包問題。利用外逼近方法求解對偶問題以得到上界，為了消除對偶間隙以保證算法的收斂性，我們利用區(qū)域割技術(shù)丟掉某些整數(shù)箱子，并把剩下的區(qū)域劃分為一些整數(shù)箱子的并集，以便使拉格朗日松弛

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

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