不確定隨機(jī)網(wǎng)絡(luò)下的度約束最小生成樹(shù)問(wèn)題.pdf

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

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

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