【正文】 152535455節(jié)點(diǎn)序號10442367564821連接順序5657585960616263節(jié)點(diǎn)序號1129201550327226連接順序6465666768697071節(jié)點(diǎn)序號439637924396569連接順序7273747576777879節(jié)點(diǎn)序號5737482541146080圖3最優(yōu)鋪設(shè)方案圖二、問題二的分析與求解1．對問題的分析在問題一所得出的最小生成樹的的基礎(chǔ)上，我們考慮到若其中只要有一個重要節(jié)點(diǎn)發(fā)生故障時，會造成八個節(jié)點(diǎn)以上故障，那么通信暢通的可能性就不能保證達(dá)到90%，所以，我們可以通過節(jié)點(diǎn)刪除法找到重要節(jié)點(diǎn)，然后再從重要節(jié)點(diǎn)引起故障的其他失效節(jié)點(diǎn)中找到一個節(jié)點(diǎn)與其他正常節(jié)點(diǎn)連通使得發(fā)生故障的節(jié)點(diǎn)數(shù)少于八個，我們就能保證通信暢通的可能性達(dá)到90%，并且我們要找到的這個節(jié)點(diǎn)與其他正常節(jié)點(diǎn)連通所鋪設(shè)的費(fèi)用是最省的。⑤最后d與a,b,c, 之中最短的距離為c到d的連線為6，故連接c到d,得出了最小生成樹。引入一個變量，時說明該路徑未被選中，1則表示被選中為總結(jié)點(diǎn)數(shù)建立的數(shù)學(xué)模型如下算法流程圖見圖2圖2 問題一的算法流程圖為了更好的表現(xiàn)算法內(nèi)容，用以下簡化模型來表示并驗(yàn)證：表1普里姆算法示例圖①設(shè)置一個加權(quán)連通圖，頂點(diǎn)集合為，邊集合為。5 模型的建立與求解一、問題一的分析與求解1．問題的分析問題要求根據(jù)附件內(nèi)容建立數(shù)學(xué)模型，并設(shè)計算法使得通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最省，并證明可靠性；我們引入圖論中普里姆算法（Prim算法），算法對通信網(wǎng)絡(luò)的每條路的鋪設(shè)費(fèi)用總額進(jìn)行模擬測算，形成鋪設(shè)費(fèi)用的最小生成樹，并通過簡化模型進(jìn)行檢驗(yàn)算法的可靠性。4 名詞解釋與符號說明一、名詞解釋1．最小生成樹：一個有 n 個結(jié)點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結(jié)點(diǎn)，并且有保持圖連通的最少的邊。4．對問題四的分析問題要求是綜合考慮網(wǎng)絡(luò)的可靠性以及鋪設(shè)，試確定合理的鋪設(shè)方案。我們引入圖論中普里姆算法（Prim算法），算法對通信網(wǎng)絡(luò)的每條路的鋪設(shè)費(fèi)用總額進(jìn)行模擬測算，形成鋪設(shè)費(fèi)用的最小生成樹，并通過簡化模型進(jìn)行檢驗(yàn)算法的可靠性。二、相關(guān)資料1．80個節(jié)點(diǎn)之間的距離表和鋪設(shè)線路的單位費(fèi)用表（見附表1）；三、要解決的問題問題1．要使得通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最省，請建立問題的數(shù)學(xué)模型，設(shè)計求解算法，給出鋪設(shè)方案，并討論方案的可靠性；問題2．考慮到通信網(wǎng)絡(luò)結(jié)點(diǎn)的可靠性，若要求任意一個結(jié)點(diǎn)出現(xiàn)故障時，其它結(jié)點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá)到90%，請建立問題的數(shù)學(xué)模型，設(shè)計求解算法，并給出使總鋪設(shè)費(fèi)用最少的鋪設(shè)方案；問題3：考慮到通信網(wǎng)絡(luò)鏈路的可靠性，若要求任意一條鏈路被破壞時，能夠保持通信暢通的結(jié)點(diǎn)都能夠達(dá)到90%，請建立問題的數(shù)學(xué)模型，設(shè)計求解算法，并給出使總鋪設(shè)費(fèi)用最少的鋪設(shè)方案；問題4：綜合考慮網(wǎng)絡(luò)的可靠性以及鋪設(shè)費(fèi)用，試確定合理的鋪設(shè)方案。然而，與此同時也存在著很多不足，諸如安全隱患、信息漏洞等，這些對于人們的工作和生活造成了很大的影響。傳輸是傳送信息的媒體，交換是各種終端交換信息的中介體，終端是指用戶使用的話機(jī)、手機(jī)、傳真機(jī)和計算機(jī)等。本文后續(xù)對模型進(jìn)行了誤差分析。針對問題一要求，具體要求為使得通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最省，首先使用了簡化模型分析、反證法等方法，證明最小生成樹算法能測算無向圖遍歷節(jié)點(diǎn)的最省方案，其次應(yīng)用最小生成樹法中的普里姆（prim）算法構(gòu)造通訊網(wǎng)絡(luò)總費(fèi)用最省模型使用Matlab軟件編程，得到最優(yōu)鋪設(shè)方案并作圖。針對問題二要求任意一個結(jié)點(diǎn)出現(xiàn)故障時，其它結(jié)點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá)到90%時最省鋪設(shè)方案設(shè)計問題，首先使用節(jié)點(diǎn)排除法進(jìn)行處理，找到重要節(jié)點(diǎn)，利用樹圖將節(jié)點(diǎn)分類，再通過分類失效節(jié)點(diǎn)與有效節(jié)點(diǎn)連接達(dá)到通暢性要求，最后使用Matlab軟件編程得出節(jié)點(diǎn)故障模型下最省鋪設(shè)方案。還基于對問題四中可靠性不僅僅與節(jié)點(diǎn)和鏈路的穩(wěn)定性有關(guān)，還與節(jié)點(diǎn)的度有關(guān)，故引進(jìn)節(jié)點(diǎn)的度對模型進(jìn)行改進(jìn)，并利用蟻群算法建立綜合目標(biāo)下的鋪設(shè)模型；最后對模型做出了縱向的推廣和橫向的推廣?，F(xiàn)代電信網(wǎng)是由專業(yè)機(jī)構(gòu)以通信設(shè)備（硬件）和相關(guān)工作程序（軟件）有機(jī)建立的通信系統(tǒng)，為個人、企事業(yè)單位和社會提供各類通信服務(wù)的總和。我們在需要在研究通信網(wǎng)絡(luò)鋪設(shè)問題時的費(fèi)用問題時，也要充分考慮其的可靠性。167。2．對問題二的分析問題要求這80個節(jié)點(diǎn)任意一個節(jié)點(diǎn)出現(xiàn)故障時，其它節(jié)點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá)到90%，在問題一所得出的最小生成樹的的基礎(chǔ)上，若其中只有一個重要節(jié)點(diǎn)發(fā)生故障時，會造成八個節(jié)點(diǎn)以上故障，那么通信暢通的可能性就不能達(dá)到90%，故通過節(jié)點(diǎn)刪除法找到重要節(jié)點(diǎn)，再從重要節(jié)點(diǎn)引起故障的其他失效節(jié)點(diǎn)中找到一個節(jié)點(diǎn)與其他正常節(jié)點(diǎn)連通使得發(fā)生故障的節(jié)點(diǎn)數(shù)少于八個即可，并且改進(jìn)方案所鋪設(shè)的費(fèi)用是最省的。首先對比分析問題二與問題三的節(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%時所對應(yīng)的最低鋪設(shè)費(fèi)用，使用Matlab軟件編程，綜合考慮穩(wěn)定性和鋪設(shè)費(fèi)用得出鋪設(shè)方案。2．普里姆算法（Prim算法） 指可在加權(quán)連通圖里搜索最小生成樹。本文中連通圖的頂點(diǎn)為80個通訊網(wǎng)絡(luò)的節(jié)點(diǎn)，所有邊的權(quán)值為兩節(jié)點(diǎn)之間的鋪設(shè)通訊鏈路的總費(fèi)用，通過普里姆算法可以得出聯(lián)通所有頂點(diǎn)并且使總鋪設(shè)費(fèi)用最低的樹圖，即相對于問題一的最優(yōu)鋪設(shè)方案。（為頂點(diǎn)，連線為邊,邊上數(shù)字為權(quán)值）②選擇頂點(diǎn)集合中任意頂點(diǎn)，此處選擇為初始點(diǎn)。軌跡為到a到b到c到d⑵ 模型可靠性的檢驗(yàn)反證法：設(shè)生成的樹為,假設(shè)存在使得總花費(fèi)；則一定存在一個不屬于；將加入，而 在本被其他點(diǎn)連接，加入后會形成一個環(huán)；而一定小于環(huán)中某一邊的權(quán)重，這與在生成樹時每次都取權(quán)重最小值的步驟矛盾；故假設(shè)不成立，原模型成立。可以給出具體的算法流程圖，如圖4，圖4問題二的算法流程圖2．對問題的求解我們以節(jié)點(diǎn)22為中心節(jié)點(diǎn)，可以將最小生成樹分成四個大部分：為節(jié)點(diǎn)22左邊部分，為節(jié)點(diǎn)22右上方部分，為節(jié)點(diǎn)22右下方部分，即為剩下的部分，即={22 56 54}。所以可分為:B={1 34 26 61 50 32}。費(fèi)用最小的方案所對應(yīng)的線路即是我們要增加的鋪設(shè)線路。B－是6168連接，對應(yīng)費(fèi)用為52800元；D－是1538連接，對應(yīng)費(fèi)用為53600元；－是210連接，對應(yīng)費(fèi)用為47000元；所以增加的總費(fèi)用為153400元。2．對問題的求解在第二問的基礎(chǔ)上，我們已經(jīng)將最小生成樹分成四個大部分、和。所以我們將分成：={ 1 34 26 61 50 32 70 36 8 14 66 67}={ 62 47 69 2 29 19 49 28 5 78 35 20 80 24 39 40 63 79 27 3 7 13 42 53 37}所以我們將分成：={ 51 30 38 4 58 31 59 60 48 12 68 46 65 33 41 73}={ 18 21 52 43 9 16 55 25}所以我們將分成：={ 77 23 6 64 57 75 71 11 74 72 17 10 44 15 76 45}={ 76 45}={22 56 54}比如鏈路被破壞后，會導(dǎo)致部分的節(jié)點(diǎn)都失效，保持通信暢通的節(jié)點(diǎn)就不能達(dá)到90%，同樣，和也是如此，即要保證這三條鏈路之一破壞時，、和都不能失效，所以要考慮的連接方案有：－和－； －和－；－和－；－、和通過Matlab（見附錄程序3）算出的結(jié)果如表3：表3 問題三結(jié)果圖節(jié)點(diǎn)1節(jié)點(diǎn)2鋪設(shè)費(fèi)用6168528817645467152861685282354465102470－是6168連接，對應(yīng)費(fèi)用為52800元；－是210連接，對應(yīng)費(fèi)用為47000元，所以增加的總費(fèi)用為998000元。通過比較4個方案，可以得知第一個方案所需要增加的費(fèi)用最省，費(fèi)用是是99800元，所以總的鋪設(shè)費(fèi)用=+99800=3047600元。C={70 36 8 14 66 67 62 47 69 2 29 19 49 28 5 78 35 20 80 24 39 40 63 79 27 3 7 13 42 53 37}。分配方案為：圖7 通暢度85%時最省鋪設(shè)方案同樣若要求任意一個結(jié)點(diǎn)出現(xiàn)故障時，其它結(jié)點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá)到90%時，通過問題二與問題三的模型計算出的最省鋪設(shè)方案為3054200元。6 誤差分析一、誤差分析1．在取得兩節(jié)點(diǎn)之間的距離數(shù)據(jù)時由于人工記取數(shù)據(jù)或者測量距離的工具不標(biāo)準(zhǔn)，會造成讀取數(shù)據(jù)的誤差，從而造成模型的誤差。7 模型的評價與推廣一、模型的優(yōu)點(diǎn) 1．本文對問題有合理的猜想、假設(shè)、計算以及檢驗(yàn)；2．按照需要求解的問題靈活選取數(shù)據(jù)，而不是每次都使用同一個數(shù)據(jù)；3．問題三在求解出來之后又提出一個