不確定隨機網(wǎng)絡下的度約束最小生成樹問題.pdf

1、最小生成樹問題是網(wǎng)絡優(yōu)化中的基本問題之一，在通信網(wǎng)絡、交通網(wǎng)絡、物流網(wǎng)絡等領域中有廣泛的應用。電路設計中為了減小節(jié)點的脆弱性，Narula和Ho在1980年提出度約束最小生成樹問題。該問題旨在尋找最小權重的生成樹，且每個節(jié)點的度滿足給定的約束的要求。在經(jīng)典網(wǎng)絡中，所有權重都是已知的常數(shù)，因此可以利用經(jīng)典的算法求解。
　　然而在現(xiàn)實網(wǎng)絡中，由于非決定性因素的存在，導致網(wǎng)絡中盼權重是非決定性的。為了描述非決定性的網(wǎng)絡，F(xiàn)rank和Ha

2、kimi在1965年首先提出了隨機網(wǎng)絡的概念，目的是描述通信網(wǎng)絡的隨機現(xiàn)象。在2010年，Knowles和David首先把度約束最小生成樹問題引入到隨機網(wǎng)絡中，但該方法對權重的估計十分依賴歷史數(shù)據(jù)。然而在現(xiàn)實網(wǎng)絡中，很多網(wǎng)絡是沒有歷史數(shù)據(jù)的，因此Liu在2010年提出了不確定網(wǎng)絡的概念。本文主要研究了不確定網(wǎng)絡下的度約束最小生成樹問題?；诓淮_定變量的不同的比較原則，我提出了三種不確定規(guī)劃模型:不確定期望值度約束最小生成樹模型，不確定α

3、-度約束最小生成樹模型和不確定最大機會度約束最小生成樹模型。論文運用改進的遺傳求解模型，并給出數(shù)值算例。
　　在實際生活的網(wǎng)絡中，有的權重沒有歷史數(shù)據(jù)，有的權重有歷史數(shù)據(jù)，因此不確定性和隨機性往往同時出現(xiàn)在一個復雜的網(wǎng)絡。最近，Liu在不確定網(wǎng)絡的基礎上進一步提出了不確定隨機網(wǎng)絡的概念。本文首次研究了不確定隨機網(wǎng)絡下的度約束最小生成樹問題，提出了一個理想機會分布的概念。為了尋找與理想機會分布最接近的度約束生成樹作為度約束最小生成樹