不確定圖上流分布可靠性問題研究.pdf

1、在實(shí)際應(yīng)用中，不確定性是許多系統(tǒng)的固有特性，如電力傳輸網(wǎng)中的元器件、數(shù)據(jù)通信網(wǎng)中的節(jié)點(diǎn)都存在著發(fā)生故障的概率，交通運(yùn)輸網(wǎng)中也有著發(fā)生擁塞的概率等?？蓪⑦@類應(yīng)用中的系統(tǒng)建模成不確定圖，從而將問題轉(zhuǎn)化成不確定圖中的問題來(lái)解決。不確定圖最可靠最大流問題是指在不確定圖中可以傳遞最大流的多個(gè)流分布中選擇可靠性最高的一個(gè)。該問題能夠很好的解決諸如構(gòu)建可靠性網(wǎng)絡(luò)、可靠傳輸路徑的選擇以及系統(tǒng)薄弱環(huán)節(jié)的分析等一系列問題。
　　針對(duì)現(xiàn)有的最可靠最大流

2、算法時(shí)間復(fù)雜度較高，難以應(yīng)用于大規(guī)模網(wǎng)絡(luò)的不足，本文給出負(fù)權(quán)群落的概念，并借鑒最小費(fèi)用流中平移思想提出了基于負(fù)權(quán)群落消去的算法(NCEA)。NCEA算法首先求得一個(gè)最大流分布，然后在該最大流分布對(duì)應(yīng)的剩余圖中查找負(fù)權(quán)群落，通過(guò)負(fù)權(quán)群落的消去得到可靠性更高的最大流分布，接著繼續(xù)在更新后的剩余圖中查找負(fù)權(quán)群落并消去，直到剩余圖中不存在負(fù)權(quán)群落，此時(shí)求得的最大流分布經(jīng)論證即為最可靠最大流。然而在NCEA算法中涉及到組合運(yùn)算，容易產(chǎn)生組合爆炸，

3、為此提出了基于剪枝策略的改進(jìn)算法(PBA)，PBA算法利用若一個(gè)組合滿足條件，則包含該組合的其余組合均不滿足條件的性質(zhì)很好的解決了組合爆炸的問題，并顯著的提高了算法的性能。
　　為了進(jìn)一步提高算法性能，滿足對(duì)算法速度要求很高而精度要求不高的應(yīng)用需求，本文根據(jù)負(fù)權(quán)群落的特點(diǎn)給出了基于單環(huán)消去的近似算法(OCEA)，該算法具有很好的性能，能夠很快的求出一個(gè)近似解，但算法精度波動(dòng)性較大，為此，本文又提出的另一個(gè)基于雙環(huán)消去的近似算法(T