【摘要】：最小生成樹問題是網(wǎng)絡(luò)優(yōu)化中的基本問題之一,在通信網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、物流網(wǎng)絡(luò)等領(lǐng)域中有廣泛的應(yīng)用。電路設(shè)計中為了減小節(jié)點的脆弱性,Narula和Ho在1980年提出度約束最小生成樹問題。該問題旨在尋找最小權(quán)重的生成樹,且每個節(jié)點的度滿足給定的約束的要求。在經(jīng)典網(wǎng)絡(luò)中,所有權(quán)重都是已知的常數(shù),因此可以利用經(jīng)典的算法求解。然而在現(xiàn)實網(wǎng)絡(luò)中,由于非決定性因素的存在,導(dǎo)致網(wǎng)絡(luò)中的權(quán)重是非決定性的。為了描述非決定性的網(wǎng)絡(luò),Frank和Hakimi在1965年首先提出了隨機網(wǎng)絡(luò)的概念,目的是描述通信網(wǎng)絡(luò)的隨機現(xiàn)象。在2010年,Knowles和David首先把度約束最小生成樹問題引入到隨機網(wǎng)絡(luò)中,但該方法對權(quán)重的估計十分依賴歷史數(shù)據(jù)。然而在現(xiàn)實網(wǎng)絡(luò)中,很多網(wǎng)絡(luò)是沒有歷史數(shù)據(jù)的,因此Liu在2010年提出了不確定網(wǎng)絡(luò)的概念。本文主要研究了不確定網(wǎng)絡(luò)下的度約束最小生成樹問題�；诓淮_定變量的不同的比較原則,我提出了三種不確定規(guī)劃模型:不確定期望值度約束最小生成樹模型,不確定?-度約束最小生成樹模型和不確定最大機會度約束最小生成樹模型。論文運用改進的遺傳求解模型,并給出數(shù)值算例。在實際生活的網(wǎng)絡(luò)中,有的權(quán)重沒有歷史數(shù)據(jù),有的權(quán)重有歷史數(shù)據(jù),因此不確定性和隨機性往往同時出現(xiàn)在一個復(fù)雜的網(wǎng)絡(luò)。最近,Liu在不確定網(wǎng)絡(luò)的基礎(chǔ)上進一步提出了不確定隨機網(wǎng)絡(luò)的概念。本文首次研究了不確定隨機網(wǎng)絡(luò)下的度約束最小生成樹問題,提出了一個理想機會分布的概念。為了尋找與理想機會分布最接近的度約束生成樹作為度約束最小生成樹,建立了一個不確定隨機規(guī)劃模型,最后論文給出了數(shù)值算法求解該模型。
[Abstract]:The minimum spanning tree problem is one of the basic problems in network optimization. It is widely used in communication network, transportation network, logistics network and so on. In order to reduce the vulnerability of nodes in circuit design, Narula and Ho proposed the minimum spanning tree problem with degree constraints in 1980. The aim of this problem is to find the spanning tree of minimum weight, and the degree of each node satisfies the requirement of given constraints. In classical networks, all weights are known constants, so the classical algorithm can be used to solve the problem. However, in real networks, the weights in networks are indeterminate due to the existence of indeterminate factors. In order to describe indeterminate networks, Frank and Hakimi first proposed the concept of stochastic networks in 1965, the purpose of which is to describe the stochastic phenomena of communication networks. In 2010, Knowles and David first introduced the degree constrained minimum spanning tree problem into stochastic networks, but the estimation of weights in this method relies heavily on historical data. However, in real networks, many networks do not have historical data, so Liu put forward the concept of uncertain networks in 2010. In this paper, we study the minimum spanning tree problem of degree constraints in uncertain networks. Based on the different comparison principles of uncertain variables, I propose three uncertain programming models: uncertain expectation degree constrained minimum spanning tree model. Uncertainty-degree constraint minimum spanning tree model and uncertain maximum opportunity constraint minimum spanning tree model. In this paper, an improved genetic solution model is used and a numerical example is given. In real life networks, some weights have no historical data, some weights have historical data, so uncertainty and randomness often appear in a complex network at the same time. Recently, Liu put forward the concept of uncertain stochastic network on the basis of uncertain network. In this paper, the degree constrained minimum spanning tree problem for uncertain stochastic networks is studied for the first time, and a concept of ideal opportunity distribution is proposed. In order to find the degree constraint spanning tree which is closest to the ideal chance distribution as the minimum spanning tree of degree constraint, an uncertain stochastic programming model is established. Finally, a numerical algorithm is presented to solve the model.
【學(xué)位授予單位】：華北電力大學(xué)(北京)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5

【相似文獻】

相關(guān)期刊論文 前10條

1 毛華;史田敏;高瑞;;求最小生成樹的矩陣算法[J];鄭州大學(xué)學(xué)報(理學(xué)版);2013年04期

2 石少儉,賀紅,趙然;最小生成樹邊與邊的權(quán)的調(diào)整[J];山東理工大學(xué)學(xué)報(自然科學(xué)版);2004年05期

3 何忠華;孟祥瑞;;基于節(jié)點編碼的最小生成樹算法[J];黑龍江科技信息;2008年34期

4 夏蘭芳;胡鵬;白軼多;黃夢龍;;基于地圖代數(shù)的最小生成樹實現(xiàn)方法[J];測繪科學(xué);2008年01期

5 曲建華;崔巖;徐廣印;姚新勝;應(yīng)繼來;;基于最小生成樹的河南省高速公路多義性路徑標識站設(shè)置[J];河南科學(xué);2012年05期

6 曹煥光;用最小生成樹存貯和檢索數(shù)據(jù)[J];山西大學(xué)學(xué)報(自然科學(xué)版);1985年03期

7 閻樹柏，張曄，王明東;最小生成樹的一個問題[J];吉林林學(xué)院學(xué)報;1994年04期

8 汪遐昌;最小生成樹問題[J];成都師專學(xué)報;1996年03期

9 汪遐昌;最小生成樹問題[J];四川師范大學(xué)學(xué)報(自然科學(xué)版);1997年01期

10 姚坤;劉希玉;李菲菲;;基于Global optimization尋找無向完全圖的最小生成樹[J];山東科學(xué);2006年02期

相關(guān)會議論文 前10條

1 黃宜真;張世R，

本文編號：2342340