非線性資源分配問題的分枝定界算法.pdf

1、本文主要討論用分枝定界算法求解上述非線性資源分配問題,并把該方法的計(jì)算效率和特點(diǎn)與拉格朗日對偶和區(qū)域分割方法以及0-1線性化方法進(jìn)行比較.首先,我們簡單地介紹了非線性整數(shù)規(guī)劃問題現(xiàn)有的一些解法,以及求解凸資源分配問題的連續(xù)松弛問題的乘子搜索法和Pegging算法.然后,我們介紹了求解整數(shù)規(guī)劃問題的分枝定界算法,并且用分枝定界算法求解了凸資源分配問題.最后,我們討論了凹資源分配問題的線性下逼近和連續(xù)松弛的方法.在某些情況下,這樣得到的松弛

2、問題仍然能用乘子搜索法或Pegging算法求解.在此基礎(chǔ)上,我們對分枝定界算法進(jìn)行了修改,并把乘子搜索法(或Pegging算法)與修改后的分枝定界算法相結(jié)合,成功地求解了單約束的凹資源分配問題.此外,我們還對來自實(shí)際應(yīng)用中的非線性資源分配問題進(jìn)行了大量的數(shù)值實(shí)驗(yàn).本文總共分為六章,其中第一章簡單地介紹了非線性背包問題與整數(shù)規(guī)劃問題算法的研究現(xiàn)狀和研究進(jìn)展.第二章主要討論凸資源分配問題連續(xù)松弛后的兩種不同解法.第三章主要給出了整數(shù)規(guī)劃問題