通信網(wǎng)絡(luò)的設(shè)計(jì)問題

1、通信網(wǎng)絡(luò)的設(shè)計(jì)問題摘 要本文針對(duì)通訊網(wǎng)絡(luò)設(shè)計(jì)問題，使用圖論中最小生成樹法、節(jié)點(diǎn)排除法、網(wǎng)絡(luò)故障分析法、對(duì)比分析法等方法，分別構(gòu)建普里姆（prim）模型、節(jié)點(diǎn)故障模型、鏈路故障模型等模型，使用matlab軟件編輯算法，得到通訊網(wǎng)絡(luò)總費(fèi)用最省的鋪設(shè)方案、可靠性條件下最省鋪設(shè)方案以及綜合條件下最省鋪設(shè)方案。針對(duì)問題一要求，具體要求為使得通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最省，首先使用了簡化模型分析、反證法等方法，證明最小生成樹算法能測(cè)算無向圖遍歷節(jié)點(diǎn)的最省方案，其次應(yīng)用最小生成樹法中的普里姆（prim）算法構(gòu)造通訊網(wǎng)絡(luò)總費(fèi)用最省模型使用matlab軟件編程，得到最優(yōu)鋪設(shè)方案并作圖。針對(duì)問題二要求任意一個(gè)結(jié)點(diǎn)出現(xiàn)故

2、障時(shí)，其它結(jié)點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá)到90%時(shí)最省鋪設(shè)方案設(shè)計(jì)問題，首先使用節(jié)點(diǎn)排除法進(jìn)行處理，找到重要節(jié)點(diǎn)，利用樹圖將節(jié)點(diǎn)分類，再通過分類失效節(jié)點(diǎn)與有效節(jié)點(diǎn)連接達(dá)到通暢性要求，最后使用matlab軟件編程得出節(jié)點(diǎn)故障模型下最省鋪設(shè)方案。針對(duì)問題三要求，任意一條鏈路被破壞時(shí)，能夠保持通信暢通的結(jié)點(diǎn)都能夠達(dá)到90%時(shí)最省鋪設(shè)方案設(shè)計(jì)問題，首先找到重要鏈路，并分析鏈路影響的節(jié)點(diǎn)，用樹圖將節(jié)點(diǎn)分類，再通過分類失效節(jié)點(diǎn)與有效節(jié)點(diǎn)連接達(dá)到通暢性要求，最后使用matlab軟件編程得出鏈路故障模型下最省鋪設(shè)方案。針對(duì)問題四要求，綜合考慮網(wǎng)絡(luò)的可靠性以及鋪設(shè)費(fèi)用確定合理的鋪設(shè)方案問題，首先對(duì)比分析

3、問題二與問題三的節(jié)點(diǎn)分類，得出節(jié)點(diǎn)穩(wěn)定性比鏈路穩(wěn)定性更重要的結(jié)論；再通過節(jié)點(diǎn)故障模型分別構(gòu)造通信暢通的可能性都達(dá)到85%、90%、95%時(shí)所對(duì)應(yīng)的最低鋪設(shè)費(fèi)用，使用matlab軟件編程，得到綜合考慮下的鋪設(shè)方案。本文后續(xù)對(duì)模型進(jìn)行了誤差分析。還基于對(duì)問題四中可靠性不僅僅與節(jié)點(diǎn)和鏈路的穩(wěn)定性有關(guān)，還與節(jié)點(diǎn)的度有關(guān)，故引進(jìn)節(jié)點(diǎn)的度對(duì)模型進(jìn)行改進(jìn)，并利用蟻群算法建立綜合目標(biāo)下的鋪設(shè)模型；最后對(duì)模型做出了縱向的推廣和橫向的推廣。關(guān)鍵詞：網(wǎng)絡(luò)通訊設(shè)計(jì)；最小生成樹法；故障分析法；蟻群算法；matlab §1 問題的重述一、背景知識(shí)傳統(tǒng)的通信網(wǎng)絡(luò)是由傳輸、交換和終端三大部分組成。傳輸是傳送信息的媒

4、體，交換是各種終端交換信息的中介體，終端是指用戶使用的話機(jī)、手機(jī)、傳真機(jī)和計(jì)算機(jī)等?，F(xiàn)代電信網(wǎng)是由專業(yè)機(jī)構(gòu)以通信設(shè)備（硬件）和相關(guān)工作程序（軟件）有機(jī)建立的通信系統(tǒng)，為個(gè)人、企事業(yè)單位和社會(huì)提供各類通信服務(wù)的總和。現(xiàn)在計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)在各個(gè)領(lǐng)域的應(yīng)用范圍已經(jīng)逐步廣泛起來，其發(fā)展也在不斷的推動(dòng)人類社會(huì)逐漸走向信息時(shí)代。網(wǎng)絡(luò)技術(shù)的發(fā)展不僅促進(jìn)了社會(huì)生產(chǎn)力的提高，也為人們的生活帶來了很大的方便。然而，與此同時(shí)也存在著很多不足，諸如安全隱患、信息漏洞等，這些對(duì)于人們的工作和生活造成了很大的影響。我們?cè)谛枰谘芯客ㄐ啪W(wǎng)絡(luò)鋪設(shè)問題時(shí)的費(fèi)用問題時(shí)，也要充分考慮其的可靠性。可靠性是其重要的整體指標(biāo)，通信網(wǎng)絡(luò)的可

5、靠性不僅與通信設(shè)備、鏈路有關(guān)，而且還與網(wǎng)絡(luò)結(jié)構(gòu)有關(guān)。由于網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜多變，通信網(wǎng)絡(luò)的可靠性分析一直是個(gè)棘手的問題。二、相關(guān)資料180個(gè)節(jié)點(diǎn)之間的距離表和鋪設(shè)線路的單位費(fèi)用表（見附表1）；三、要解決的問題問題1要使得通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最省，請(qǐng)建立問題的數(shù)學(xué)模型，設(shè)計(jì)求解算法，給出鋪設(shè)方案，并討論方案的可靠性；問題2考慮到通信網(wǎng)絡(luò)結(jié)點(diǎn)的可靠性，若要求任意一個(gè)結(jié)點(diǎn)出現(xiàn)故障時(shí)，其它結(jié)點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá)到90%，請(qǐng)建立問題的數(shù)學(xué)模型，設(shè)計(jì)求解算法，并給出使總鋪設(shè)費(fèi)用最少的鋪設(shè)方案；問題3：考慮到通信網(wǎng)絡(luò)鏈路的可靠性，若要求任意一條鏈路被破壞時(shí)，能夠保持通信暢通的結(jié)點(diǎn)都能夠達(dá)到90%

6、，請(qǐng)建立問題的數(shù)學(xué)模型，設(shè)計(jì)求解算法，并給出使總鋪設(shè)費(fèi)用最少的鋪設(shè)方案；問題4：綜合考慮網(wǎng)絡(luò)的可靠性以及鋪設(shè)費(fèi)用，試確定合理的鋪設(shè)方案。§2 問題的分析一、問題的總分析 對(duì)于問題的總分析，可以給出四個(gè)問題整體框架圖，見圖1圖1 四個(gè)問題的整體框架圖二、對(duì)具體問題的分析1對(duì)問題一的分析某通信公司擬建一個(gè)具有80個(gè)結(jié)點(diǎn)的通信網(wǎng)絡(luò)，需要在這些結(jié)點(diǎn)之間鋪設(shè)線路，進(jìn)行數(shù)據(jù)傳輸。我們需要根據(jù)附件內(nèi)容建立數(shù)學(xué)模型，并設(shè)計(jì)算法使得通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最省，并證明可靠性。我們引入圖論中普里姆算法（prim算法），算法對(duì)通信網(wǎng)絡(luò)的每條路的鋪設(shè)費(fèi)用總額進(jìn)行模擬測(cè)算，形成鋪設(shè)費(fèi)用的最小生成樹，并通過簡化模型

7、進(jìn)行檢驗(yàn)算法的可靠性。2對(duì)問題二的分析問題要求這80個(gè)節(jié)點(diǎn)任意一個(gè)節(jié)點(diǎn)出現(xiàn)故障時(shí)，其它節(jié)點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá)到90%，在問題一所得出的最小生成樹的的基礎(chǔ)上，若其中只有一個(gè)重要節(jié)點(diǎn)發(fā)生故障時(shí)，會(huì)造成八個(gè)節(jié)點(diǎn)以上故障，那么通信暢通的可能性就不能達(dá)到90%，故通過節(jié)點(diǎn)刪除法找到重要節(jié)點(diǎn)，再從重要節(jié)點(diǎn)引起故障的其他失效節(jié)點(diǎn)中找到一個(gè)節(jié)點(diǎn)與其他正常節(jié)點(diǎn)連通使得發(fā)生故障的節(jié)點(diǎn)數(shù)少于八個(gè)即可，并且改進(jìn)方案所鋪設(shè)的費(fèi)用是最省的。3對(duì)問題三的分析問題要求79個(gè)鏈路中任意一條鏈路被破壞時(shí)，能夠保持通信暢通的節(jié)點(diǎn)都能夠達(dá)到90%。同樣在問題一所得出的最小生成樹的的基礎(chǔ)上，我們考慮到若其中只要有一個(gè)重

8、要鏈路被破壞時(shí)，會(huì)造成八個(gè)節(jié)點(diǎn)以上故障，那么通信暢通的可能性就不能保證達(dá)到90%，所以，我們可以通過逐個(gè)分析每條鏈路，找到重要鏈路，一個(gè)鏈路被破壞會(huì)使最小生成樹分割成兩個(gè)部分，其中一部分則是失效的，然后再從重要鏈路被破壞而引起的其他失效節(jié)點(diǎn)中找到一個(gè)節(jié)點(diǎn)與其他正常節(jié)點(diǎn)連通使得發(fā)生故障的節(jié)點(diǎn)數(shù)少于或等于八個(gè)，我就能保證通信暢通的可能性達(dá)到90%，并且我們要找到的這個(gè)節(jié)點(diǎn)與其他正常節(jié)點(diǎn)連通所鋪設(shè)的費(fèi)用是最省的。4對(duì)問題四的分析問題要求是綜合考慮網(wǎng)絡(luò)的可靠性以及鋪設(shè)，試確定合理的鋪設(shè)方案。首先對(duì)比分析問題二與問題三的節(jié)點(diǎn)分類，發(fā)現(xiàn)問題三中節(jié)點(diǎn)的分類包含了問題二中節(jié)點(diǎn)的分類，若滿足了了節(jié)點(diǎn)穩(wěn)定性的要求

9、，則一定能滿足鏈路穩(wěn)定性的要求，故得出節(jié)點(diǎn)穩(wěn)定性比鏈路穩(wěn)定性更重要的結(jié)論；再通過節(jié)點(diǎn)故障模型分別構(gòu)造通信暢通的可能性都達(dá)到85%、90%、95%時(shí)所對(duì)應(yīng)的最低鋪設(shè)費(fèi)用，使用matlab軟件編程，綜合考慮穩(wěn)定性和鋪設(shè)費(fèi)用得出鋪設(shè)方案。§3 模型的假設(shè)1 兩個(gè)節(jié)點(diǎn)之間的費(fèi)用僅由節(jié)點(diǎn)之間的距離和鋪設(shè)線路的單位費(fèi)用決定；2 各節(jié)點(diǎn)和各鏈條間發(fā)生故障是相互獨(dú)立的，節(jié)點(diǎn)1發(fā)生故障不影響節(jié)點(diǎn)2發(fā)生故障；3每個(gè)節(jié)點(diǎn)的重要性是相等的，不存在次級(jí)差別；4任意兩個(gè)節(jié)點(diǎn)之間可以進(jìn)行連接，且一個(gè)節(jié)點(diǎn)可以連接的節(jié)點(diǎn)不受限制；5網(wǎng)路的穩(wěn)定性與節(jié)點(diǎn)所連的鏈路條數(shù)無關(guān)，即每個(gè)節(jié)點(diǎn)和鏈路出現(xiàn)故障的可能性是相等的；

10、67;4 名詞解釋與符號(hào)說明一、名詞解釋1最小生成樹：一個(gè)有 n 個(gè)結(jié)點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個(gè)結(jié)點(diǎn)，并且有保持圖連通的最少的邊。2普里姆算法（prim算法） 指可在加權(quán)連通圖里搜索最小生成樹。意即由此算法搜索到的邊子集所構(gòu)成的樹中，不但包括了連通圖里的所有頂點(diǎn)，且其所有邊的權(quán)值之和亦為最小。二、主要符號(hào)說明序號(hào)符號(hào)符號(hào)說明1表示加權(quán)連通圖的節(jié)點(diǎn)集合2表示加權(quán)連通圖的邊集合3表示集合中的任意節(jié)點(diǎn)4表示初始的節(jié)點(diǎn)集合5表示集合中的元素6表示中的節(jié)點(diǎn)但不是中的節(jié)點(diǎn)7表示一個(gè)0、1變量，0，1分別表示選中和未選中 8表示節(jié)點(diǎn)i到節(jié)點(diǎn)j鋪設(shè)線路所花費(fèi)的費(fèi)用9z表

11、示所選的鋪設(shè)方案所花費(fèi)的總費(fèi)用10表示最小生成樹的鏈路§5 模型的建立與求解一、問題一的分析與求解1問題的分析問題要求根據(jù)附件內(nèi)容建立數(shù)學(xué)模型，并設(shè)計(jì)算法使得通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最省，并證明可靠性；我們引入圖論中普里姆算法（prim算法），算法對(duì)通信網(wǎng)絡(luò)的每條路的鋪設(shè)費(fèi)用總額進(jìn)行模擬測(cè)算，形成鋪設(shè)費(fèi)用的最小生成樹，并通過簡化模型進(jìn)行檢驗(yàn)算法的可靠性。本文中連通圖的頂點(diǎn)為80個(gè)通訊網(wǎng)絡(luò)的節(jié)點(diǎn)，所有邊的權(quán)值為兩節(jié)點(diǎn)之間的鋪設(shè)通訊鏈路的總費(fèi)用，通過普里姆算法可以得出聯(lián)通所有頂點(diǎn)并且使總鋪設(shè)費(fèi)用最低的樹圖，即相對(duì)于問題一的最優(yōu)鋪設(shè)方案。2問題的求解模型總鋪設(shè)費(fèi)用最省模型 模型的建立普里姆算法

12、（prim算法）的步驟：從單一點(diǎn)開始，普里姆算法按照以下步驟逐步擴(kuò)大樹中所含節(jié)點(diǎn)的數(shù)目，直到遍歷連通圖的所有節(jié)點(diǎn)。首先設(shè)加權(quán)連通圖的節(jié)點(diǎn)集合為，邊集合為，初始化，其中為集合中的任意節(jié)點(diǎn)，其次在集合中選取權(quán)數(shù)最小的邊，其中為集合中的元素，而不是，如果存在權(quán)數(shù)一樣的可任選其中之一，再次，將加入到，重復(fù)第二第三步，直到。引入一個(gè)變量，時(shí)說明該路徑未被選中，1則表示被選中為總結(jié)點(diǎn)數(shù)建立的數(shù)學(xué)模型如下算法流程圖見圖2圖2 問題一的算法流程圖為了更好的表現(xiàn)算法內(nèi)容，用以下簡化模型來表示并驗(yàn)證：表1普里姆算法示例圖設(shè)置一個(gè)加權(quán)連通圖，頂點(diǎn)集合為，邊集合為。（為頂點(diǎn)，連線為邊,邊上數(shù)字為權(quán)值）選擇頂點(diǎn)集合中任

13、意頂點(diǎn)，此處選擇為初始點(diǎn)。頂點(diǎn)a、b、c、d都有與直接相連的邊，選取其中權(quán)重最小的點(diǎn)（圖中為a）下一個(gè)頂點(diǎn)為距離a或最近的頂點(diǎn)，a距離c為10，距d為6，距b為5；距c為10，距d為15，距b為15；所以最短的距離是a到b得距離為5，連接a與b繼續(xù)重復(fù)上面的步驟。可以發(fā)現(xiàn)距離a,b和最短的是b到c得距離為5，連接b和c。最后d與a,b,c, 之中最短的距離為c到d的連線為6，故連接c到d,得出了最小生成樹。軌跡為到a到b到c到d 模型可靠性的檢驗(yàn)反證法：設(shè)生成的樹為,假設(shè)存在使得總花費(fèi)；則一定存在一個(gè)不屬于；將加入，而 在本被其他點(diǎn)連接，加入后會(huì)形成一個(gè)環(huán)；而一定小于環(huán)中某一邊的權(quán)重，這與在生

14、成樹時(shí)每次都取權(quán)重最小值的步驟矛盾；故假設(shè)不成立，原模型成立。 模型的求解根據(jù)matlab運(yùn)行結(jié)果見表1（程序見附錄1），可以得到通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用為2947800元。得到的最優(yōu)鋪設(shè)方案如圖3。表1 問題一結(jié)果圖連接順序12345678節(jié)點(diǎn)序號(hào)346170623647219連接順序910111213141516節(jié)點(diǎn)序號(hào)5352737849713連接順序1718192021222324節(jié)點(diǎn)序號(hào)4028425366672254連接順序2526272829304647節(jié)點(diǎn)序號(hào)1652561851127417連接順序4849505152535455節(jié)點(diǎn)序號(hào)10442367564821連接順序5657

15、585960616263節(jié)點(diǎn)序號(hào)1129201550327226連接順序6465666768697071節(jié)點(diǎn)序號(hào)439637924396569連接順序7273747576777879節(jié)點(diǎn)序號(hào)5737482541146080圖3最優(yōu)鋪設(shè)方案圖二、問題二的分析與求解1對(duì)問題的分析在問題一所得出的最小生成樹的的基礎(chǔ)上，我們考慮到若其中只要有一個(gè)重要節(jié)點(diǎn)發(fā)生故障時(shí)，會(huì)造成八個(gè)節(jié)點(diǎn)以上故障，那么通信暢通的可能性就不能保證達(dá)到90%，所以，我們可以通過節(jié)點(diǎn)刪除法找到重要節(jié)點(diǎn)，然后再從重要節(jié)點(diǎn)引起故障的其他失效節(jié)點(diǎn)中找到一個(gè)節(jié)點(diǎn)與其他正常節(jié)點(diǎn)連通使得發(fā)生故障的節(jié)點(diǎn)數(shù)少于八個(gè)，我們就能保證通信暢通的可能性達(dá)到

16、90%，并且我們要找到的這個(gè)節(jié)點(diǎn)與其他正常節(jié)點(diǎn)連通所鋪設(shè)的費(fèi)用是最省的?？梢越o出具體的算法流程圖，如圖4，圖4問題二的算法流程圖2對(duì)問題的求解我們以節(jié)點(diǎn)22為中心節(jié)點(diǎn)，可以將最小生成樹分成四個(gè)大部分：為節(jié)點(diǎn)22左邊部分，為節(jié)點(diǎn)22右上方部分，為節(jié)點(diǎn)22右下方部分，即為剩下的部分，即=22 56 54。例如部分，當(dāng)這部分有節(jié)點(diǎn)出現(xiàn)故障時(shí)，我們通過或的點(diǎn)與這個(gè)故障點(diǎn)引起的失效點(diǎn)之間用最省的方案再鋪設(shè)一條線路后，保證任一點(diǎn)發(fā)生故障后也能使通信暢通的可能性達(dá)到90%。通過此方法，我們可以在部分找到重要節(jié)點(diǎn)70，部分找到重要節(jié)點(diǎn)51，部分找到重要節(jié)點(diǎn)77。找到重要節(jié)點(diǎn)后，要考慮這三個(gè)重要節(jié)點(diǎn)任一發(fā)生故障

17、時(shí)，怎么增加最省的鋪設(shè)線路問題，然后我們?cè)俜謩e將、分成兩個(gè)部分，第一部分是重要節(jié)點(diǎn)出現(xiàn)故障后造成可靠性小于90%的節(jié)點(diǎn)之和，即我們必需增加鋪設(shè)線路的點(diǎn)，第二部分是重要節(jié)點(diǎn)發(fā)生故障后不影響可靠性的節(jié)點(diǎn)之和。所以可分為:bc=703681466676247692291949285783520802439406379273713425337;可分為:d=303845831596048e=5112463341686573182152439165525可分為:f=71 11 74 7217104415g=772366457757645對(duì)于任意節(jié)點(diǎn)發(fā)生故障時(shí)，要通過增加鋪設(shè)后保證

18、至少有70個(gè)節(jié)點(diǎn)是通信暢通的。所以這六個(gè)部分要考慮連接的方案有：bd和； bf和d；df 和b；b、d和；可以通過matlab編程（見附錄程序2）分別計(jì)算9條線路各自最小的費(fèi)用，然后計(jì)算4個(gè)方案費(fèi)用。費(fèi)用最小的方案所對(duì)應(yīng)的線路即是我們要增加的鋪設(shè)線路。matlab算出的結(jié)果見表2：表2 問題二結(jié)果圖節(jié)點(diǎn)1節(jié)點(diǎn)2鋪設(shè)費(fèi)用6168528817645467152861685282354465102470bd是60-61連接，對(duì)應(yīng)費(fèi)用為209100元；是2-10連接，對(duì)應(yīng)費(fèi)用為47000元，所以增加的總費(fèi)用為256100元。bf是1-72連接，對(duì)應(yīng)費(fèi)用為78000元；d是15-38連接，對(duì)應(yīng)費(fèi)用為53

19、600元，所以增加的總費(fèi)用為131600元。df 是15-38連接，對(duì)應(yīng)費(fèi)用為53600元， b是61-68連接，對(duì)應(yīng)費(fèi)用為52800元，所以增加的總費(fèi)用為106400元。b是61-68連接，對(duì)應(yīng)費(fèi)用為52800元；d是15-38連接，對(duì)應(yīng)費(fèi)用為53600元；是2-10連接，對(duì)應(yīng)費(fèi)用為47000元；所以增加的總費(fèi)用為153400元。通過比較4個(gè)方案，可以得知第三個(gè)方案所需要增加的費(fèi)用是106400元，所以總的鋪設(shè)費(fèi)用=+106400=3054200元。增加的路線如圖5。圖5 任一節(jié)點(diǎn)出現(xiàn)故障可靠性達(dá)到90%的最優(yōu)鋪設(shè)方案圖三、問題三的分析與求解1對(duì)問題的分析同樣在問題一所得出的最小生成樹的的基

20、礎(chǔ)上，我們考慮到若其中只要有一個(gè)重要鏈路被破壞時(shí)，會(huì)造成八個(gè)節(jié)點(diǎn)以上故障，那么通信暢通的可能性就不能保證達(dá)到90%，所以，我們可以通過逐個(gè)分析每條鏈路，找到重要鏈路，一個(gè)鏈路被破壞會(huì)使最小生成樹分割成兩個(gè)部分，其中一部分則是失效的，然后再從重要鏈路被破壞而引起的其他失效節(jié)點(diǎn)中找到一個(gè)節(jié)點(diǎn)與其他正常節(jié)點(diǎn)連通使得發(fā)生故障的節(jié)點(diǎn)數(shù)少于或等于八個(gè)，我就能保證通信暢通的可能性達(dá)到90%，并且我們要找到的這個(gè)節(jié)點(diǎn)與其他正常節(jié)點(diǎn)連通所鋪設(shè)的費(fèi)用是最省的。2對(duì)問題的求解在第二問的基礎(chǔ)上，我們已經(jīng)將最小生成樹分成四個(gè)大部分、和。再比如部分，當(dāng)這部分的一個(gè)鏈路被破壞時(shí)，我們通過或的點(diǎn)與這個(gè)故障點(diǎn)引起的失效點(diǎn)之間用

21、最省的方案再鋪設(shè)一條線路后，保證任何一條鏈路被破壞后也能使通信暢通的可能性達(dá)到90%。通過此方法，我們可以在部分找到的重要鏈路是70與62之間的鏈路，在部分找到重要鏈路是18與51之間的鏈路，在部分找到重要鏈路是76與77之間的鏈路。找到三個(gè)重要的鏈路、和后，我們要研究這三個(gè)重要鏈路任一發(fā)生故障時(shí)，怎么增加最省的鋪設(shè)線路問題，這三個(gè)重要的鏈路任意一個(gè)被破壞時(shí)都會(huì)導(dǎo)致其所在的部分被分割成兩個(gè)小的部分，一個(gè)部分中的節(jié)點(diǎn)都是有效的，一個(gè)部分的節(jié)點(diǎn)都是失效的。所以我們將分成：= 1342661503270368146667= 62476922919492857835208024394063792737

22、13425337所以我們將分成：= 5130384583159604812684665334173= 182152439165525所以我們將分成：= 7723664577571117472171044157645= 7645=22 56 54比如鏈路被破壞后，會(huì)導(dǎo)致部分的節(jié)點(diǎn)都失效，保持通信暢通的節(jié)點(diǎn)就不能達(dá)到90%，同樣，和也是如此，即要保證這三條鏈路之一破壞時(shí)，、和都不能失效，所以要考慮的連接方案有：和； 和；和；、和通過matlab（見附錄程序3）算出的結(jié)果如表3：表3 問題三結(jié)果圖節(jié)點(diǎn)1節(jié)點(diǎn)2鋪設(shè)費(fèi)用6168528817645467152861685282354465102470是6

23、1-68連接，對(duì)應(yīng)費(fèi)用為52800元；是2-10連接，對(duì)應(yīng)費(fèi)用為47000元，所以增加的總費(fèi)用為998000元。是8-17連接，對(duì)應(yīng)費(fèi)用為64500元；是23-54連接，對(duì)應(yīng)費(fèi)用為46500元，所以增加的總費(fèi)用為111000元。是46-71連接，對(duì)應(yīng)費(fèi)用為52800元， 是61-68連接，對(duì)應(yīng)費(fèi)用為52800元，所以增加的總費(fèi)用為105600元。是是2-10連接，對(duì)應(yīng)費(fèi)用為47000元，是23-54連接，對(duì)應(yīng)費(fèi)用為46500元，；是61-68連接，對(duì)應(yīng)費(fèi)用為52800元，；所以增加的總費(fèi)用為146300元。通過比較4個(gè)方案，可以得知第一個(gè)方案所需要增加的費(fèi)用最省，費(fèi)用是是99800元，所以總的

24、鋪設(shè)費(fèi)用=+99800=3047600元。圖6 任一鏈路出現(xiàn)故障可靠性達(dá)到90%的最優(yōu)鋪設(shè)方案圖四、問題四的分析與求解1對(duì)問題的分析在問題二及問題三的基礎(chǔ)上，首先對(duì)比分析問題二與問題三的節(jié)點(diǎn)分類，發(fā)現(xiàn)問題三中節(jié)點(diǎn)的分類包含了問題二中節(jié)點(diǎn)的分類，若滿足了了節(jié)點(diǎn)穩(wěn)定性的要求，則一定能滿足鏈路穩(wěn)定性的要求，故得出節(jié)點(diǎn)穩(wěn)定性比鏈路穩(wěn)定性更重要的結(jié)論；再通過節(jié)點(diǎn)故障模型分別構(gòu)造通信暢通的可能性都達(dá)到85%、90%、95%時(shí)所對(duì)應(yīng)的最低鋪設(shè)費(fèi)用，使用matlab軟件編程，綜合考慮穩(wěn)定性和鋪設(shè)費(fèi)用得出鋪設(shè)方案。2對(duì)問題的求解我們以節(jié)點(diǎn)22為中心節(jié)點(diǎn)，可以將最小生成樹分成四個(gè)大部分：為節(jié)點(diǎn)22左邊部分，為節(jié)點(diǎn)

25、22右上方部分，為節(jié)點(diǎn)22右下方部分，即為剩下的部分，即=22 56 54。所問題二中可分為:bc=703681466676247692291949285783520802439406379273713425337;問題三中將可分為：= 1342661503270368146667= 6247692291949285783520802439406379273713425337可見問題三中的節(jié)點(diǎn)分類包括了問題二中的分類問題二中可分為:d=303845831596048e=5112463341686573182152439165525問題三中將分成：= 513038458

26、3159604812684665334173= 182152439165525利用matlab求解結(jié)果見表4。（程序間附錄程序4）表4 問題四結(jié)果圖節(jié)點(diǎn)1節(jié)點(diǎn)2鋪設(shè)費(fèi)用節(jié)點(diǎn)1節(jié)點(diǎn)2鋪設(shè)費(fèi)用26332070636425761382716246510302675342039413000110326340592738363810922431190066751296631011908176451962565364128101962565可見問題三中的節(jié)點(diǎn)分類包括了問題二中的分類故節(jié)點(diǎn)穩(wěn)定性的要求更高，即只要滿足了節(jié)點(diǎn)穩(wěn)定性就能滿足鏈條穩(wěn)定性的要求，下面僅考慮節(jié)點(diǎn)穩(wěn)定性需求下的故障模型。當(dāng)若要求任意一個(gè)

27、結(jié)點(diǎn)出現(xiàn)故障時(shí)，其它結(jié)點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá)到85%時(shí)，通過問題二與問題三的模型計(jì)算出的最省鋪設(shè)方案為3047600元。分配方案為：圖7 通暢度85%時(shí)最省鋪設(shè)方案同樣若要求任意一個(gè)結(jié)點(diǎn)出現(xiàn)故障時(shí)，其它結(jié)點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá)到90%時(shí)，通過問題二與問題三的模型計(jì)算出的最省鋪設(shè)方案為3054200元。分配方案為：圖8 通暢度90%時(shí)最省鋪設(shè)方案同樣若要求任意一個(gè)結(jié)點(diǎn)出現(xiàn)故障時(shí)，其它結(jié)點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá)到90%時(shí)，通過問題二與問題三的模型計(jì)算出的最省鋪設(shè)方案為3578800元。分配方案為：圖9 通暢度95%時(shí)最省鋪設(shè)方案可見當(dāng)通暢度從85%增加至90

28、%時(shí)，費(fèi)用僅僅增加了6400元，而當(dāng)通暢度從90%增加至95%時(shí)，費(fèi)用增加了524600元，故選擇90%的通暢度，此時(shí)可以滿足當(dāng)一個(gè)節(jié)點(diǎn)或一個(gè)鏈條出現(xiàn)故障時(shí)，其它結(jié)點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá)到90%，且費(fèi)用適中，可以同時(shí)滿足穩(wěn)定性和鋪設(shè)成本的條件，故本題選擇圖5所示的鋪設(shè)方案為綜合的最優(yōu)方案。§6 誤差分析一、誤差分析1在取得兩節(jié)點(diǎn)之間的距離數(shù)據(jù)時(shí)由于人工記取數(shù)據(jù)或者測(cè)量距離的工具不標(biāo)準(zhǔn)，會(huì)造成讀取數(shù)據(jù)的誤差，從而造成模型的誤差。2在論文中直接認(rèn)為總的鋪設(shè)費(fèi)用是有距離和節(jié)點(diǎn)單位費(fèi)用決定的，在實(shí)際解決問題中，總鋪設(shè)費(fèi)用還要考慮其他因素的影響。3在問題二的分析方法中，我們直接認(rèn)

29、為每個(gè)節(jié)點(diǎn)之間發(fā)生故障的概率是相同的，其實(shí)有的節(jié)點(diǎn)發(fā)生故障的概率大，我們考慮的太理想化，而且有的節(jié)點(diǎn)發(fā)生故障會(huì)導(dǎo)致其他某些節(jié)點(diǎn)發(fā)生故障的概率增大或者減小。§7 模型的評(píng)價(jià)與推廣一、模型的優(yōu)點(diǎn) 1本文對(duì)問題有合理的猜想、假設(shè)、計(jì)算以及檢驗(yàn)；2按照需要求解的問題靈活選取數(shù)據(jù)，而不是每次都使用同一個(gè)數(shù)據(jù)；3問題三在求解出來之后又提出一個(gè)新思路，并且有一個(gè)新的解法。一題兩解，并且可以互相驗(yàn)證結(jié)果；4研究問題時(shí)循序漸進(jìn)，在求解的過程中慢慢進(jìn)步，逐步完善。二、模型的缺點(diǎn)1求解問題時(shí)用的數(shù)據(jù)是自己觀察，手工計(jì)數(shù)的，這樣得出的數(shù)據(jù)難免會(huì)有些誤差，有些沒有考慮到的因素；2在最后模型改進(jìn)的時(shí)候，我們提出

30、了思路和解法但是由于時(shí)間有限，我們并沒有將最后的具體結(jié)果計(jì)算出來；三、模型的推廣1排隊(duì)論模型我們所研究的排隊(duì)論是把排隊(duì)論應(yīng)用到交通中，道路發(fā)生事故時(shí)堵車所形成的類似排隊(duì)現(xiàn)象這種情況運(yùn)用排隊(duì)論的相關(guān)知識(shí)來求解，我們還可以將排隊(duì)論延伸到其它的領(lǐng)域，比如車站買票、醫(yī)院取藥、通訊服務(wù)等其它領(lǐng)域；2交通流模型由于進(jìn)出匝道或交通事故等原因而形成的交通瓶頸，是導(dǎo)致高速道路交通擁擠和堵塞的最主要的根源，我們通過這個(gè)模型不僅僅能夠?qū)鉀Q堵車時(shí)的排隊(duì)長度問題還可以解決密度，速度等其他的交通指標(biāo)；3在解決第三問時(shí)，我們發(fā)現(xiàn)交通堵塞問題與管道收縮而導(dǎo)致的運(yùn)動(dòng)氣流中形成激動(dòng)波過程很相似，所以我們就通過研究后者的模型來類

31、比我們要解決的問題，這種聯(lián)想類比法也可以推廣到其它問題。§8 模型的改進(jìn)本題中線路的可靠性僅僅考慮了節(jié)點(diǎn)和鏈路的穩(wěn)定性，在保證連通性的情況下最小化了鋪設(shè)成本；但未考慮流量因素，流量與節(jié)點(diǎn)的度有關(guān)，節(jié)點(diǎn)的度是指與節(jié)點(diǎn)直接連接的鏈路的數(shù)量，流量因素是指：一個(gè)節(jié)點(diǎn)的度越多，流過這個(gè)節(jié)點(diǎn)的最大流量就越大。所以，流量可以看作是圖中節(jié)點(diǎn)的度數(shù)之和的增函數(shù)。而在節(jié)點(diǎn)度之和一定的情況下，各個(gè)節(jié)點(diǎn)度數(shù)的波動(dòng)越大，度數(shù)小的節(jié)點(diǎn)就成為流量的約束。因此，流量的大小是節(jié)點(diǎn)度數(shù)的方差函數(shù)。令代表圖中度的均值，代表方差構(gòu)造流量函數(shù)： （1）而本文問題一中有鋪設(shè)成本的目標(biāo)函數(shù)為： （2）將兩個(gè)因素綜合考慮，這里利用

32、線性加權(quán)的辦法將其綜合，首先將式（1）、（2）歸一化，然后定義偏好系數(shù)，越接近0表是決策者越傾向于費(fèi)用因素，越接近于1越傾向于流量因素，所以，最終的目標(biāo)函數(shù)為：設(shè)置約束條件，其中假定每一個(gè)節(jié)點(diǎn)的度數(shù)屬于2,5的閉區(qū)間。凡是有節(jié)點(diǎn)度數(shù)不在詞區(qū)間的方案都被認(rèn)為是不可行解。為防止螞蟻在尋優(yōu)的過程中產(chǎn)生不可行解，定義（low,up）為度的約束區(qū)間。對(duì)于每一個(gè)節(jié)點(diǎn)i，其度，在此定義一個(gè)函數(shù)：則可以定義罰函數(shù)為：預(yù)算成本的約束：因?yàn)榍懊嫱茖?dǎo)出了一個(gè)新目標(biāo)函數(shù)，所有鋪設(shè)成本不再是要優(yōu)化的對(duì)象。而在實(shí)際過程中，決策放能夠承擔(dān)的最大鋪設(shè)成本一定不大于預(yù)算。所以，定義一個(gè)最大預(yù)算。根據(jù)心理學(xué)的知識(shí)，決策者對(duì)費(fèi)用的

33、容忍度通常都是在與最小成本的比較中產(chǎn)生的，所以定義一個(gè)容忍百分比其取值如下：相應(yīng)的最大容忍度為。節(jié)點(diǎn)穩(wěn)定性的約束：首先引入一個(gè)故障矩陣， 表示在節(jié)點(diǎn)和節(jié)點(diǎn)之間存在連接線時(shí)，連接線出現(xiàn)故障的概率。仍然假定節(jié)點(diǎn)不會(huì)出現(xiàn)故障，所有故障都來自于鏈路。而每一條邊對(duì)于點(diǎn)來說是并聯(lián)的，利用概率統(tǒng)計(jì)的知識(shí)，可以求得節(jié)點(diǎn)能夠正常工作的概率為：令為用戶規(guī)定的平均最小工作概率。如果在整個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)工作的概率的算數(shù)平均值大于，則這個(gè)網(wǎng)絡(luò)是可接受的，否則是不可接受的。故由上述分析，這個(gè)優(yōu)化的模型是一個(gè)組合優(yōu)化模型，可以用蟻群算法來求解，這里簡要介紹一下蟻群算法的求解過程。1.初始化參數(shù)2. 利用概率的方法構(gòu)建螞蟻的

34、路徑。本文綜合考慮了最小成本模型和度約束條件，同時(shí)在本模型中又加入了流量及鏈路概率的影響。如當(dāng)前位于節(jié)點(diǎn)的螞蟻選擇作為下一個(gè)節(jié)點(diǎn)的概率為：其中，為鏈路信息素強(qiáng)度； 為一個(gè)預(yù)先給定的啟發(fā)式信息，初始值為鏈路距離的倒數(shù)。為本算法設(shè)置了啟發(fā)式信息的優(yōu)先級(jí)：鏈路如果有一個(gè)端點(diǎn)的度為1，則加1 倍，若鏈路 2 個(gè)端點(diǎn)的度都為1，加2 倍。、 是2 個(gè)參數(shù)，它們分別決定了信息素和啟發(fā)式信息的相對(duì)影響力。代表位于節(jié)點(diǎn)的螞蟻可以直接到達(dá)的相鄰節(jié)點(diǎn)的集合，也就是還沒有被螞蟻訪問的節(jié)點(diǎn)的集合。step3 本文使用的后臺(tái)策略是在螞蟻前進(jìn)一步時(shí)就計(jì)算各個(gè)約束的值，看是否滿足要求，當(dāng)有一個(gè)約束不再滿足要求時(shí)，螞蟻不再前

35、行。一輪路徑探索完之后，計(jì)算目標(biāo)函數(shù)的值，進(jìn)而挑選出最優(yōu)的路徑。step4 在每一輪路徑探索之后，更新信息素，更新規(guī)則如下：其中為信息素?fù)]發(fā)程度；表示第次循環(huán)是否選擇了鏈路，如果先擇，否則，是常數(shù)。5.當(dāng)路徑探索的論述達(dá)到時(shí)輸出結(jié)果。因?yàn)橄伻核惴ㄓ休^強(qiáng)的收斂性，故當(dāng)經(jīng)過不同次數(shù)的迭代實(shí)驗(yàn)是，會(huì)得出較為相近的結(jié)果，此時(shí)則為最優(yōu)的結(jié)果，最終的結(jié)果可有c語言編程完成。參考文獻(xiàn)：1 /wiki/prim%e6%bc%94%e7%ae%97%e6%b3%95 .2 基于蟻群算法的多目標(biāo)網(wǎng)絡(luò)鋪設(shè)策略研究龔承柱1，諸克軍1，郭海湘1,2(1. 中國地質(zhì)大學(xué)經(jīng)濟(jì)管理

36、學(xué)院，武漢 430074；2. 西安交通大學(xué)管理學(xué)院，西安 710049). 3 姜啟源，謝金星，葉俊.數(shù)學(xué)模型m 北京；高等教育出版社，2011，1.10附錄程序1：%a表示權(quán)值矩陣%c表示生成樹的權(quán)和%visit標(biāo)記是否訪問過（1表示訪問，0表示未訪問），dis記錄當(dāng)前最短距離，r矩陣表示結(jié)點(diǎn)序號(hào)之間從前往后依次連接clc,cleara=xlsread('date.xls');%權(quán)值矩陣（節(jié)點(diǎn)之間的費(fèi)用表=距離*單位費(fèi)用）l=length(a);a(a=0)=inf;%初始化鄰接矩陣dis=zeros(1,l);dis(:)=inf;%初始化dis數(shù)組visit=zeros

37、(1,l);result=zeros(l,l);visit(1)=1;dis(1)=0;next=1;c=0;a=zeros(1,80);%初始時(shí)刻1點(diǎn)加入集合中r=zeros(2,79);r(1,:)=1:79;%初始化結(jié)果矩陣for k=1:l-1; now=next;%now表示計(jì)算的當(dāng)前節(jié)點(diǎn) m=inf;%m保存當(dāng)前節(jié)點(diǎn)到集合的最短距離 for i=1:l; if visit(i)=0%如果沒有標(biāo)記，開始這個(gè)點(diǎn) dis(i)=min(dis(i),a(now,i);%更新這個(gè)i點(diǎn)到集合的最短距離，保存到dis中 if(dis(i)<m) m=dis(i); next=i;%記錄下

38、最小的那個(gè)點(diǎn)，作為下一個(gè)計(jì)算的點(diǎn)。 end end end c=c+m;%加權(quán)值 visit(next)=1;%標(biāo)記進(jìn)集合的點(diǎn) result(k,next)=1;%整合每次標(biāo)記endfor t=1:79; r(2,t)=find(result(t,:)=1);%按順序輸出節(jié)點(diǎn)表示連接過程endr %結(jié)果矩陣輸出，第一行表示連接順序，第二行表示表示依次連接節(jié)點(diǎn)數(shù)c %相應(yīng)情況下的最省鋪設(shè)費(fèi)用程序二：a=xlsread('date.xls'); %權(quán)值矩陣（節(jié)點(diǎn)之間的費(fèi)用表=距離*單位費(fèi)用）n1=1342661503270368146667;n2=51303845831596048

39、12684665334173;n3=772366457757111747217104415;m1=134266150327036814666762476922919492857835208024;m2=5130384583159604812684665334173182152439165525;m3=7723664577571117472171044157645;m4=542256;%輸入六個(gè)節(jié)點(diǎn)分類矩陣x1=m2 m3 m4;x2=m1 m3 m4;x3=m1 m2 m4;l1=length(n1);l2=length(n2);l3=length(n3);l4=length(m1);l5=l

40、ength(m2);l6=length(m3);l7=length(m4);%分別求其長度和兩兩組合長度t=1; for i=1:l1; for j=1:l2; r(t,:)=n1(i) n2(j) a(n1(i),n2(j) t=t+1; end end for i=1:l1; for k=1:l3; r(t,:)=n1(i) n3(k) a(n1(i),n3(k); t=t+1; end end for j=1:l2; for k=1:l3; r(t,:)=n2(j) n3(k) a(n2(j),n3(k); t=t+1; end end for i=1:l1; for p=1:l5+l6

41、+l7; r(t,:)=n1(i) x1(p) a(n1(i),x1(p); t=t+1; end end for j=1:l2; for q=1:l4+l6+l7; r(t,:)=n2(j) x2(q) a(n2(j),x2(q); t=t+1; end end for k=1:l3; for r=1:l4+l5+l7; r(t,:)=n3(k) x3(r) a(n3(k),x3(r); t=t+1; end end r1=sortrows(r(1:192,:),3); result(1,:)=r1(1,:); r2=sortrows(r(193:360,:),3); result(2,:)

42、=r2(1,:); r3=sortrows(r(361:584,:),3); result(3,:)=r3(1,:); r4=sortrows(r(585:1101,:),3); result(4,:)=r4(1,:); r5=sortrows(r(1102:1997,:),3); result(5,:)=r5(1,:); r6=sortrows(r(1998:2893,:),3);result(6,:)=r6(1,:);%逐個(gè)計(jì)算最省費(fèi)用result%輸出分類比較下的最省費(fèi)用及相應(yīng)連接節(jié)點(diǎn)序號(hào)程序三：a=xlsread('date.xls'); %權(quán)值矩陣（節(jié)點(diǎn)之間的費(fèi)用表=

43、距離*單位費(fèi)用）n1=1342661503270368146667;n2=5130384583159604812684665334173;n3=772366457757111747217104415;m1=134266150327036814666762476922919492857835208024;m2=5130384583159604812684665334173182152439165525;m3=7723664577571117472171044157645;m4=542256;x1=m2 m3 m4;x2=m1 m3 m4;x3=m1 m2 m4;l1=length(n1);l2=

44、length(n2);l3=length(n3);l4=length(m1);l5=length(m2);l6=length(m3);l7=length(m4); %分別求其長度和兩兩組合長度t=1; for i=1:l1; for j=1:l2; r(t,:)=n1(i) n2(j) a(n1(i),n2(j); t=t+1; end end for i=1:l1; for k=1:l3; r(t,:)=n1(i) n3(k) a(n1(i),n3(k); t=t+1; end end for j=1:l2; for k=1:l3; r(t,:)=n2(j) n3(k) a(n2(j),n3

45、(k); t=t+1; end end for i=1:l1; for p=1:l5+l6+l7; r(t,:)=n1(i) x1(p) a(n1(i),x1(p); t=t+1; end end for j=1:l2; for q=1:l4+l6+l7; r(t,:)=n2(j) x2(q) a(n2(j),x2(q); t=t+1; end end for k=1:l3; for r=1:l4+l5+l7; r(t,:)=n3(k) x3(r) a(n3(k),x3(r); t=t+1; end end %分別求其長度和兩兩組合長度 r1=sortrows(r(1:192,:),3); r

46、esult(1,:)=r1(1,:); r2=sortrows(r(193:360,:),3); result(2,:)=r2(1,:); r3=sortrows(r(361:584,:),3); result(3,:)=r3(1,:); r4=sortrows(r(585:1100,:),3); result(4,:)=r4(1,:); r5=sortrows(r(1101:1996,:),3); result(5,:)=r5(1,:); r6=sortrows(r(1997:2562,:),3); result(6,:)=r6(1,:); result %輸出分類比較下的最省費(fèi)用及相應(yīng)連接

47、節(jié)點(diǎn)序號(hào) 附錄四a=xlsread('date.xls'); %權(quán)值矩陣（節(jié)點(diǎn)之間的費(fèi)用表=距離*單位費(fèi)用）n1=263415032;n2=666736814;n3=79634020248039;n4=28491929;m1=65337341;m2=3159604838458;m3=6645775;m4=17104415;x1=m2 m3 m4;x2=m1 m3 m4;x3=m1 m2 m4;l1=length(n1);l2=length(n2);l3=length(n3);l4=length(n4);l5=length(m1);l6=length(m2);l7=length(

48、m3);l8=length(m4);%求矩陣長度t=1 for i1=1:l1; for j1=1:l5; r(t,:)=n1(i1) m1(j1) a(n1(i1),m1(j1); t=t+1; end end for i1=1:l1; for j1=1:l6; r(t,:)=n1(i1) m2(j1) a(n1(i1),m2(j1); t=t+1; end end for i1=1:l1; for j1=1:l7; r(t,:)=n1(i1) m3(j1) a(n1(i1),m3(j1); t=t+1; end end for i1=1:l1; for j1=1:l8; r(t,:)=n1(i1) m4(j1) a(n1(i1),m4(j1)