可靠性網(wǎng)絡(luò)中費(fèi)用最小化問題.pdf

1、現(xiàn)代科技的發(fā)展帶動(dòng)社會(huì)生活水平的整體提高，日常生活與科技發(fā)展息息相關(guān)，隨著各種系統(tǒng)和網(wǎng)絡(luò)的日趨復(fù)雜，人們?cè)谝蕾嚳萍嫉耐瑫r(shí)也對(duì)系統(tǒng)的可靠性提出了更高的要求。比如對(duì)各種風(fēng)險(xiǎn)管理和操作系統(tǒng)一方面要考慮其費(fèi)用和資源消耗問題，另一方面還要保證其可靠性。因此研究可靠性網(wǎng)絡(luò)的費(fèi)用最小化問題有很重要的現(xiàn)實(shí)意義?？煽啃跃W(wǎng)絡(luò)的費(fèi)用最小化問題就是在滿足系統(tǒng)可靠性最低限度要求下，尋求一組最優(yōu)的部件冗余數(shù)，使網(wǎng)絡(luò)費(fèi)用最小。本文主要討論串-并可靠性網(wǎng)絡(luò)的費(fèi)用最小化

2、問題。此問題是一類特殊的非線性整數(shù)規(guī)劃問題，可描述如下： minn∑i=1fi(xi)s.t.R(x)=n∏i=1(1-(1-ri)xi)≥R0,Li≤xi≤Ui,xi整數(shù)，i=1,...,n.其中對(duì)i=1,…,n,xi表示第i個(gè)子系統(tǒng)中相同部件的個(gè)數(shù)，fi(xi)是第i個(gè)子系統(tǒng)中部件的費(fèi)用函數(shù)，ri是第i個(gè)子系統(tǒng)中相同部件的可靠性，R0是系統(tǒng)要求達(dá)到的可靠性，R(x)是整個(gè)系統(tǒng)的可靠性，Li，Ui是整數(shù)，分別表示變量xi的下界

3、和上界。 根據(jù)串-并系統(tǒng)可靠性函數(shù)的特殊性質(zhì)，提出一個(gè)新的最優(yōu)性必要條件及相應(yīng)的剪枝判斷準(zhǔn)則，由此設(shè)計(jì)的分枝定界算法通過解一個(gè)等價(jià)的0-1背包問題得到連續(xù)松弛問題的解，在每次解子問題前用相應(yīng)的判斷準(zhǔn)則檢驗(yàn)是否滿足該最優(yōu)性條件，從而減少子問題的求解次數(shù)，加快算法的收斂速度。 文章共由五部分組成。第一章簡單介紹可靠性網(wǎng)絡(luò)中費(fèi)用最小化問題及其研究現(xiàn)狀和進(jìn)展；第二章主要介紹解非線性整數(shù)規(guī)劃問題(背包問題)的一些現(xiàn)有算法；第三章主