可靠性網(wǎng)絡(luò)最優(yōu)化算法研究.pdf

1、現(xiàn)代科技的發(fā)展帶動(dòng)社會生活水平的整體提高，日常生活與科技發(fā)展息息相關(guān)．隨著各種系統(tǒng)和網(wǎng)絡(luò)的日趨復(fù)雜，人們在依賴科技的同時(shí)也對系統(tǒng)的可靠性提出了更高的要求，比如對各種風(fēng)險(xiǎn)管理和操作系統(tǒng)一方面要考慮其費(fèi)用和資源消耗問題，另一方面還要保證其可靠性，因此研究網(wǎng)絡(luò)系統(tǒng)的可靠性問題和費(fèi)用極小化問題有很重要的現(xiàn)實(shí)意義。眾所周知，系統(tǒng)可靠性可以由采用高可靠性的單個(gè)部件或子系統(tǒng)來提高。然而，在很多情況下，由于技術(shù)瓶頸限制，提高單個(gè)部件或子系統(tǒng)的可靠性往往

2、代價(jià)昂貴或不可行。因此，通過增加子系統(tǒng)的冗余部件的冗余最優(yōu)化方法對于設(shè)計(jì)高效的網(wǎng)絡(luò)系統(tǒng)起著重要的作用。 本文首先考慮簡單串并系統(tǒng)的可靠性問題。該問題是在滿足一定資源約束下，尋找最優(yōu)的冗余分配使系統(tǒng)的可靠性最大。其優(yōu)化模型為如下非線性整數(shù)規(guī)劃： 問題(P<,1>)的一個(gè)相關(guān)問題是費(fèi)用極小化問題．該問題是在滿足系統(tǒng)可靠性最低限度要求下，尋找最優(yōu)的冗余數(shù)，使系統(tǒng)的費(fèi)用最小．其優(yōu)化模型可描述如下： 本文第三章提出了求解簡

3、單可靠性系統(tǒng)兩個(gè)相關(guān)問題(P<,1>)和(P<,2>)的精確算法，此方法基于拉格朗日對偶搜索和一種整數(shù)區(qū)域剖分方案。由于這類問題可靠性函數(shù)的可分離性，通過對偶搜索算法可以有效地計(jì)算出問題的拉格朗日界。另一方面，利用可靠性函數(shù)以及約束函數(shù)的單調(diào)性，把一個(gè)整數(shù)箱子剖分為若干整數(shù)子箱，從而可以逐步減少對偶間隙。我們在算法中還利用了簡單系統(tǒng)的一類特殊最優(yōu)性準(zhǔn)則，加快了算法的收斂速度．?dāng)?shù)值結(jié)果表明，算法可以在合理時(shí)間內(nèi)求解較大規(guī)模問題。數(shù)值試驗(yàn)還

4、表明，對于多約束問題，用外逼近法作為對偶搜索算法大大優(yōu)于次梯度法．在某些網(wǎng)絡(luò)系統(tǒng)設(shè)計(jì)中，一些子系統(tǒng)除了整體的資源約束外，還需考慮局部約束或組約束．這些組約束只對這些子系統(tǒng)中的元件起作用，而不影響整個(gè)系統(tǒng)的其它部分，此時(shí)問題的非線性整數(shù)規(guī)劃模型為： 我們在第三章中提出一個(gè)求解帶組約束串并網(wǎng)絡(luò)最優(yōu)冗余問題(P<,3>)的精解算法．這個(gè)方法利用了全局約束和局部約束的特殊結(jié)構(gòu)，采用Dantzig-wblfe分解方案來計(jì)算問題的上界。由于

5、松馳子問題只有單個(gè)約束，我們采用動(dòng)態(tài)規(guī)劃來求解分解的子問題。為了消除對偶間隙，我們采用一種有效的區(qū)域剖分方案，并應(yīng)用了隱枚舉準(zhǔn)則來改進(jìn)算法的收斂性。 本文第四-五章討論了多選擇串聯(lián)系統(tǒng)可靠性問題．這類問題的優(yōu)化模型可描述如下： 與問題(P<，4>)相關(guān)的費(fèi)用極小化問題可以表示為如下的非線性整數(shù)規(guī)劃： 因?yàn)樵诿總€(gè)子系統(tǒng)r<，ij>不同，因此可靠性函數(shù)R(x)是一個(gè)不可分離函數(shù)。這使得問題(P<，4>)和(P<，5>

6、)的求解變得很困難。在第四章中，我們對(p<，4>)提出了一種基于線性逼近和拉格朗日對偶相結(jié)合的分枝定界算法．為克服不可分離性帶來的困難，我們首先構(gòu)造不可分離可靠性函數(shù)的線性逼近，并由此得到原問題的可分離整數(shù)規(guī)劃近似問題。利用外逼近法求解對偶問題就可得到相應(yīng)的拉格朗日界。我們還利用啟發(fā)式算法尋找可行解以提高算法收斂速度。 第五章對問題(P<，5>)提出了相應(yīng)的精確算法。該算法對函數(shù)R(x)的不可分離性的處理類似于(P<，4>)的