通信網(wǎng)絡(luò)的設(shè)計(jì)問(wèn)題_第1頁(yè)
通信網(wǎng)絡(luò)的設(shè)計(jì)問(wèn)題_第2頁(yè)
通信網(wǎng)絡(luò)的設(shè)計(jì)問(wèn)題_第3頁(yè)
已閱讀5頁(yè),還剩26頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

2、案 并作圖。針對(duì)問(wèn)題二要求任意一個(gè)結(jié)點(diǎn)出現(xiàn)故障時(shí), 其它結(jié)點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá) 到 90%時(shí)最省鋪設(shè)方案設(shè)計(jì)問(wèn)題,首先使用節(jié)點(diǎn)排除法進(jìn)行處理,找到重要節(jié)點(diǎn),利用樹(shù)圖將節(jié) 點(diǎn)分類(lèi),再通過(guò)分類(lèi)失效節(jié)點(diǎn)與有效節(jié)點(diǎn)連接達(dá)到通暢性要求, 最后使用 Matlab 軟件編程得出節(jié) 點(diǎn)故障模型下最省鋪設(shè)方案。針對(duì)問(wèn)題三要求, 任意一條鏈路被破壞時(shí), 能夠保持通信暢通的結(jié)點(diǎn)都能夠達(dá)到 90%時(shí)最省 鋪設(shè)方案設(shè)計(jì)問(wèn)題,首先找到重要鏈路,并分析鏈路影響的節(jié)點(diǎn),用樹(shù)圖將節(jié)點(diǎn)分類(lèi),再通過(guò)分 類(lèi)失效節(jié)點(diǎn)與有效節(jié)點(diǎn)連接達(dá)到通暢性要求, 最后使用 Matlab 軟件編程得出鏈路故障模型下最省 鋪設(shè)方案。針對(duì)問(wèn)

3、題四要求, 綜合考慮網(wǎng)絡(luò)的可靠性以及鋪設(shè)費(fèi)用確定合理的鋪設(shè)方案問(wèn)題, 首先對(duì)比 分析問(wèn)題二與問(wèn)題三的節(jié)點(diǎn)分類(lèi), 得出節(jié)點(diǎn)穩(wěn)定性比鏈路穩(wěn)定性更重要的結(jié)論; 再通過(guò)節(jié)點(diǎn)故障 模型分別構(gòu)造通信暢通的可能性都達(dá)到 85%、90%、95%時(shí)所對(duì)應(yīng)的最低鋪設(shè)費(fèi)用,使用Matlab 軟件編程,得到綜合考慮下的鋪設(shè)方案。本文后續(xù)對(duì)模型進(jìn)行了誤差分析。 還基于對(duì)問(wèn)題四中可靠性不僅僅與節(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ì);最小生成樹(shù)法;故障分析法;蟻群算法; matlab&#

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

5、在研究通信網(wǎng)絡(luò) 鋪設(shè)問(wèn)題時(shí)的費(fèi)用問(wèn)題時(shí),也要充分考慮其的可靠性??煽啃允瞧渲匾恼w指標(biāo),通 信網(wǎng)絡(luò)的可靠性不僅與通信設(shè)備、鏈路有關(guān),而且還與網(wǎng)絡(luò)結(jié)構(gòu)有關(guān)。由于網(wǎng)絡(luò)結(jié)構(gòu)的 復(fù)雜多變,通信網(wǎng)絡(luò)的可靠性分析一直是個(gè)棘手的問(wèn)題。、相關(guān)資料1. 80個(gè)節(jié)點(diǎn)之間的距離表和鋪設(shè)線路的單位費(fèi)用表(見(jiàn)附表 1);三、要解決的問(wèn)題問(wèn)題1要使得通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最省,請(qǐng)建立問(wèn)題的數(shù)學(xué)模型,設(shè)計(jì)求解算 法,給出鋪設(shè)方案,并討論方案的可靠性;問(wèn)題2.考慮到通信網(wǎng)絡(luò)結(jié)點(diǎn)的可靠性,若要求任意一個(gè)結(jié)點(diǎn)出現(xiàn)故障時(shí),其它結(jié) 點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá)到90%,請(qǐng)建立問(wèn)題的數(shù)學(xué)模型,設(shè)計(jì)求解算法,并給出使總鋪設(shè)費(fèi)用最

6、少的鋪設(shè)方案;問(wèn)題3:考慮到通信網(wǎng)絡(luò)鏈路的可靠性,若要求任意一條鏈路被破壞時(shí),能夠保持 通信暢通的結(jié)點(diǎn)都能夠達(dá)到90%,請(qǐng)建立問(wèn)題的數(shù)學(xué)模型,設(shè)計(jì)求解算法,并給出使 總鋪設(shè)費(fèi)用最少的鋪設(shè)方案;問(wèn)題4:綜合考慮網(wǎng)絡(luò)的可靠性以及鋪設(shè)費(fèi)用,試確定合理的鋪設(shè)方案。§問(wèn)題的分析、問(wèn)題的總分析對(duì)于問(wèn)題的總分析,可以給出四個(gè)問(wèn)題整體框架圖,見(jiàn)圖1彳I可趙二*考底與戸林沖慨率田低成豐請(qǐng)直*拾障分殼*析槓型*用舟怎優(yōu)冇秦*間題四即冋題一、推廣對(duì)出吩析搓1做不同可靠性槪率下的圖1四個(gè)問(wèn)題的整體框架圖二、對(duì)具體問(wèn)題的分析1. 對(duì)問(wèn)題一的分析某通信公司擬建一個(gè)具有80個(gè)結(jié)點(diǎn)的通信網(wǎng)絡(luò),需要在這些結(jié)點(diǎn)之間鋪設(shè)

7、線路,進(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)用的最小生成樹(shù),并通過(guò)簡(jiǎn)化模型進(jìn)行檢驗(yàn)算法的可靠性。2. 對(duì)問(wèn)題二的分析問(wèn)題要求這80個(gè)節(jié)點(diǎn)任意一個(gè)節(jié)點(diǎn)出現(xiàn)故障時(shí),其它節(jié)點(diǎn)間仍然能夠保持通信暢 通的可能性都達(dá)到90%,在問(wèn)題一所得出的最小生成樹(shù)的的基礎(chǔ)上,若其中只有一個(gè) 重要節(jié)點(diǎn)發(fā)生故障時(shí),會(huì)造成八個(gè)節(jié)點(diǎn)以上故障,那么通信暢通的可能性就不能達(dá)到 90%,故通過(guò)節(jié)點(diǎn)刪除法找到重要節(jié)點(diǎn),再?gòu)闹匾?jié)點(diǎn)引起故障的其他失效節(jié)點(diǎn)中找到 一個(gè)節(jié)

8、點(diǎn)與其他正常節(jié)點(diǎn)連通使得發(fā)生故障的節(jié)點(diǎn)數(shù)少于八個(gè)即可,并且改進(jìn)方案所鋪設(shè)的費(fèi)用是最省的。3. 對(duì)問(wèn)題三的分析問(wèn)題要求79個(gè)鏈路中任意一條鏈路被破壞時(shí),能夠保持通信暢通的節(jié)點(diǎn)都能夠達(dá) 到90%。同樣在問(wèn)題一所得出的最小生成樹(shù)的的基礎(chǔ)上,我們考慮到若其中只要有一 個(gè)重要鏈路被破壞時(shí),會(huì)造成八個(gè)節(jié)點(diǎn)以上故障,那么通信暢通的可能性就不能保證達(dá) 到90%,所以,我們可以通過(guò)逐個(gè)分析每條鏈路,找到重要鏈路,一個(gè)鏈路被破壞會(huì) 使最小生成樹(shù)分割成兩個(gè)部分,其中一部分則是失效的,然后再?gòu)闹匾溌繁黄茐亩?起的其他失效節(jié)點(diǎn)中找到一個(gè)節(jié)點(diǎn)與其他正常節(jié)點(diǎn)連通使得發(fā)生故障的節(jié)點(diǎn)數(shù)少于或 等于八個(gè),我就能保證通信暢通的

9、可能性達(dá)到 90%,并且我們要找到的這個(gè)節(jié)點(diǎn)與其他正常節(jié)點(diǎn)連通所鋪設(shè)的費(fèi)用是最省的4. 對(duì)問(wèn)題四的分析問(wèn)題要求是綜合考慮網(wǎng)絡(luò)的可靠性以及鋪設(shè),試確定合理的鋪設(shè)方案。首先對(duì)比分析問(wèn)題二與問(wèn)題三的節(jié)點(diǎn)分類(lèi),發(fā)現(xiàn)問(wèn)題三中節(jié)點(diǎn)的分類(lèi)包含了問(wèn)題二中節(jié)點(diǎn)的分類(lèi),若滿足了了節(jié)點(diǎn)穩(wěn)定性的要求,則一定能滿足鏈路穩(wěn)定性的要求,故得出節(jié)點(diǎn)穩(wěn)定性比鏈路穩(wěn)定性更重要的結(jié)論; 再通過(guò)節(jié)點(diǎn)故障模型分別構(gòu)造通信暢通的可能性都達(dá)到85%、90%、95%時(shí)所對(duì)應(yīng)的最低鋪設(shè)費(fèi)用,使用Matlab軟件編程,綜合考慮穩(wěn)定性和鋪設(shè)費(fèi)用得出鋪設(shè)方案。§模型的假設(shè)1. 兩個(gè)節(jié)點(diǎn)之間的費(fèi)用僅由節(jié)點(diǎn)之間的距離和鋪設(shè)線路的單位費(fèi)用決定;

10、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ù)無(wú)關(guān),即每個(gè)節(jié)點(diǎn)和鏈路出現(xiàn)故障的可能 性是相等的;§4名詞解釋與符號(hào)說(shuō)明、名詞解釋1. 最小生成樹(shù):一個(gè)有n個(gè)結(jié)點(diǎn)的連通圖的生成樹(shù)是原圖的極小連通子圖,且包 含原圖中的所有n個(gè)結(jié)點(diǎn),并且有保持圖連通的最少的邊。2. 普里姆算法(Prim算法)指可在加權(quán)連通圖里搜索最小生成樹(shù)。意即由此算 法搜索到的邊子集所構(gòu)成的樹(shù)中, 不但包括了連通圖里的所有頂點(diǎn),

11、且其所有邊的權(quán)值 之和亦為最小。、主要符號(hào)說(shuō)明序 號(hào)符 號(hào)符號(hào)說(shuō)明1V表示加權(quán)連通圖的節(jié)點(diǎn)集合2E表示加權(quán)連通圖的邊集合3t表示V集合中的任意節(jié)點(diǎn)4V。表示初始的節(jié)點(diǎn)集合5u表示集合Vo中的元素6v表示V中的節(jié)點(diǎn)但不是V。中的節(jié)點(diǎn)7Xj表示一個(gè)0、1變量,0,1分別表示選中和未選中8Wj表示節(jié)點(diǎn)i到節(jié)點(diǎn)j鋪設(shè)線路所花費(fèi)的費(fèi)用9Z表示所選的鋪設(shè)方案所花費(fèi)的總費(fèi)用10 | e表示最小生成樹(shù)的鏈路§5模型的建立與求解一、問(wèn)題一的分析與求解1 問(wèn)題的分析問(wèn)題要求根據(jù)附件內(nèi)容建立數(shù)學(xué)模型,并設(shè)計(jì)算法使得通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最 省,并證明可靠性;我們引入圖論中普里姆算法( Prim算法),算法對(duì)

12、通信網(wǎng)絡(luò)的每條 路的鋪設(shè)費(fèi)用總額進(jìn)行模擬測(cè)算, 形成鋪設(shè)費(fèi)用的最小生成樹(shù),并通過(guò)簡(jiǎn)化模型進(jìn)行檢 驗(yàn)算法的可靠性。本文中連通圖的頂點(diǎn)為80個(gè)通訊網(wǎng)絡(luò)的節(jié)點(diǎn),所有邊的權(quán)值為兩節(jié)點(diǎn)之間的鋪設(shè)通 訊鏈路的總費(fèi)用,通過(guò)普里姆算法可以得出聯(lián)通所有頂點(diǎn)并且使總鋪設(shè)費(fèi)用最低的樹(shù) 圖,即相對(duì)于問(wèn)題一的最優(yōu)鋪設(shè)方案。2 問(wèn)題的求解模型I總鋪設(shè)費(fèi)用最省模型模型的建立普里姆算法(Prim算法)的步驟:從單一點(diǎn)開(kāi)始,普里姆算法按照以下步驟逐步擴(kuò)大樹(shù)中所含節(jié)點(diǎn)的數(shù)目,直到遍歷連通圖的所有節(jié)點(diǎn)。首先設(shè)加權(quán)連通圖的節(jié)點(diǎn)集合為V ,邊集合為E,初始化V t,其中t為集合V中的任意節(jié)點(diǎn),其次在集合E中選取權(quán)數(shù)最小的邊(u,v),

13、其中u為集合 Vo中的元素,而v不是,如果存在權(quán)數(shù)一樣的可任選其中之一,再次,將v加入到Vo,重復(fù)第二第三步,直到Vo V。引入一個(gè)變量Xjj, Xjj 0時(shí)說(shuō)明該路徑未被選中,1則表示被選中count(V)為總結(jié)n nmin Zwij xij點(diǎn)數(shù)建立的數(shù)學(xué)模型如下i 1 j 1為 n 1st. i 1 j 1xijcoun t(V)i,j V。算法流程圖見(jiàn)圖2切姫祀鄰檢矩陲兒嶄小費(fèi)用劉1 口 數(shù)組也乳標(biāo)記訪冋矩陣vlshix乩 帶果辿陣R尤裟為0,粗陣大從第測(cè)開(kāi)刪曳尋可沖元耒為呻券點(diǎn)弄謝T距鬲帔加謹(jǐn)?shù)跣聵?biāo)壬疥陣此【*莘合每拽赫記為1卸騰電垣陣第一列表示述複砸序弟二歹I表示連扳序號(hào)片圖2問(wèn)題一

14、的算法流程圖為了更好的表現(xiàn)算法內(nèi)容,用以下簡(jiǎn)化模型來(lái)表示并驗(yàn)證: 表1普里姆算法示例圖 設(shè)置一個(gè)加權(quán)連通圖,頂點(diǎn)集合為 V,邊集合為E o( So、a、b、c、d為頂點(diǎn), 連線為邊,邊上數(shù)字為權(quán)值) 選擇頂點(diǎn)集合中任意頂點(diǎn),此處選擇So為初始點(diǎn)。頂點(diǎn)a、b、c、d都有與So 直接相連的邊,選取其中權(quán)重最小的點(diǎn)(圖 中為a) 下一個(gè)頂點(diǎn)為距離a或So最近的頂 點(diǎn),a距離c為10,距d為6,距b為5; So距c為10,距d為15,距b為15;所 以最短的距離是a到b得距離為5,連接a 與b 繼續(xù)重復(fù)上面的步驟??梢园l(fā)現(xiàn)距 離a,b和So最短的是b到c得距離為5, 連接b和c。反證法:設(shè)生成的樹(shù)為,

15、假設(shè)存在使得總花費(fèi)cost( ) COSt(');則一定存在一個(gè)(U,v)不屬于;將(u, v)加入,而u,v在 本被其他點(diǎn)連接,加入(u, v)后會(huì)形成一個(gè)環(huán);而(u, v)一定小于環(huán)中某一邊的權(quán)重,這與在生成樹(shù)時(shí)每次都取權(quán)重最小值的步驟 矛盾;故假設(shè)不成立,原模型成立。模型的求解根據(jù)matlab運(yùn)行結(jié)果見(jiàn)表1 (程序見(jiàn)附錄1),可以得到通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用 乙 為2947800元。得到的最優(yōu)鋪設(shè)方案如圖 3。表1問(wèn)題一結(jié)果圖連接順序12345678節(jié)點(diǎn)序號(hào)346170623647219連接順序910111213141516節(jié)點(diǎn)序號(hào)5352737849713連接順序r 1718192

16、021222324節(jié)點(diǎn)序號(hào)4028425366672254連接順序2526272829304647節(jié)點(diǎn)序號(hào)1652561851127417連接順序4849505152535455節(jié)點(diǎn)序號(hào)10442367564821連接順序5657585960616263節(jié)點(diǎn)序號(hào)1129201550327226連接順序6465666768697071節(jié)點(diǎn)序號(hào)439637924396569連接順序7273747576777879節(jié)點(diǎn)序號(hào)5737482541146080圖3最優(yōu)鋪設(shè)方案圖二、問(wèn)題二的分析與求解1對(duì)問(wèn)題的分析在問(wèn)題一所得出的最小生成樹(shù)的的基礎(chǔ)上, 我們考慮到若其中只要有一個(gè)重要節(jié)點(diǎn) 發(fā)生故障時(shí),會(huì)造成

17、八個(gè)節(jié)點(diǎn)以上故障,那么通信暢通的可能性就不能保證達(dá)到90%,所以,我們可以通過(guò)節(jié)點(diǎn)刪除法找到重要節(jié)點(diǎn), 然后再?gòu)闹匾?jié)點(diǎn)引起故障的其他失效 節(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)連通所鋪2 對(duì)問(wèn)題的求解我們以節(jié)點(diǎn)22為中心節(jié)點(diǎn),可以將最小生成樹(shù)分成四個(gè)大部分: A為節(jié)點(diǎn)22左邊 部分,A為節(jié)點(diǎn)22右上方部分,A為節(jié)點(diǎn)22右下方部分,A4即為剩下的部分,即A4=22 56 54。例如A部分,當(dāng)這部分有節(jié)點(diǎn)出現(xiàn)故障時(shí),我們通過(guò) A或A的點(diǎn)與這個(gè)故障 點(diǎn)引起的失效點(diǎn)之間用最省的方案再鋪設(shè)一條線路

18、后, 保證任一點(diǎn)發(fā)生故障后也能使通 信暢通的可能性達(dá)到90%。通過(guò)此方法,我們可以在A部分找到重要節(jié)點(diǎn)70,A部分 找到重要節(jié)點(diǎn)51,A部分找到重要節(jié)點(diǎn)77。找到重要節(jié)點(diǎn)后, 要考慮這三個(gè)重要節(jié)點(diǎn)任一發(fā)生故障時(shí), 怎么增加最省的鋪設(shè)線 路問(wèn)題,然后我們?cè)俜謩e將Ai、A、A分成兩個(gè)部分,第一部分是重要節(jié)點(diǎn)出現(xiàn)故障 后造成可靠性小于 90%的節(jié)點(diǎn)之和,即我們必需增加鋪設(shè)線路的點(diǎn),第二部分是重要節(jié) 點(diǎn)發(fā)生故障后不影響可靠性的節(jié)點(diǎn)之和。所以 A1 可分為 :B=134 26 6150 32;C=70 36 81466 67 62 47 69 229 19 49 28 578 35 20 80 2439

19、 40 63 79 273 713 42 53 37;A可分為:D=30 38 4 5831 59 60 48E=51 12 46 3341 68 65 73 18 21 52 43 916 55 25A3 可分為 :F=7111 74 7217 10 44 15G=77 23 66457 75 76 45對(duì)于任意節(jié)點(diǎn)發(fā)生故障時(shí),要通過(guò)增加鋪設(shè)后保證至少有 70個(gè)節(jié)點(diǎn)是通信暢通的 所以這六個(gè)部分要考慮連接的方案有:CDB- D和 F BCDE;B F和D BCFG;D- F 和 B DEFG;(SB D E FG、D B C F G 和 F B C D E ;可以通過(guò) matlab 編程(見(jiàn)附

20、錄程序 2)分別計(jì)算 9條線路各自最小的費(fèi)用,然后計(jì)算 4個(gè)方案費(fèi)用。費(fèi)用最小的方案所對(duì)應(yīng)的線路即是我們要增加的鋪設(shè)線路。Matlab 算出的結(jié)果見(jiàn)表 2:表2問(wèn)題二結(jié)果圖節(jié)點(diǎn)節(jié)點(diǎn)鋪設(shè)12費(fèi)用6168528817645467152861685282354465102470CDB- D是60-61連接,對(duì)應(yīng)費(fèi)用為209100元;F BCD E是2-10連接, 對(duì)應(yīng)費(fèi)用為47000元,所以增加的總費(fèi)用為256100元。 B F是1-72連接,對(duì)應(yīng)費(fèi)用為78000元;D- B C F G是15-38連接,對(duì) 應(yīng)費(fèi)用為53600元,所以增加的總費(fèi)用為131600元。 D F是15-38連接,對(duì)應(yīng)費(fèi)用為

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

22、的的基礎(chǔ)上, 我們考慮到若其中只要有一個(gè)重要 鏈路被破壞時(shí),會(huì)造成八個(gè)節(jié)點(diǎn)以上故障, 那么通信暢通的可能性就不能保證達(dá)到 90%, 所以,我們可以通過(guò)逐個(gè)分析每條鏈路,找到重要鏈路,一個(gè)鏈路被破壞會(huì)使最小生成 樹(shù)分割成兩個(gè)部分, 其中一部分則是失效的, 然后再?gòu)闹匾溌繁黄茐亩鸬钠渌?效節(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ì)問(wèn)題的求解在第二問(wèn)的基礎(chǔ)上,我們已經(jīng)將最小生成樹(shù)分成四個(gè)大部分A、A、A和A。再比如A部分,當(dāng)這部分的一個(gè)鏈路被破壞時(shí)

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

24、2661503270368146667C = 624769229194928578352080243940 63 7927 3713 425337所以我們將A2 分成:D = 5130384583159604812684665334173E = 182152439165525所以我們將A3 分成:F = 7723664577571117472171044157645G = 7645A4=22 56 54比如鏈路ei被破壞后,會(huì)導(dǎo)致B部分的節(jié)點(diǎn)都失效,保持通信暢通的節(jié)點(diǎn)就不能達(dá) 到90%,同樣,e2和e3也是如此,即要保證這三條鏈路之一破壞時(shí),B、C和D都不能失效,所以要考慮的連接方案有:B -

25、D和FBCDEA ;B -F和DBCFGA4 ;® D -F和BFGDEA4 ;Cf -B CDEA4、BCFGA4 和 FGDEA4通過(guò)Matlab (見(jiàn)附錄程序3)算出的結(jié)果如表3:表3冋題二結(jié)果圖節(jié)點(diǎn)1節(jié)點(diǎn)2鋪設(shè)費(fèi)用6168528817645467152861685282354465102470COB D是61-68連接,對(duì)應(yīng)費(fèi)用為52800元;F BCD E A4是2-10 連接,對(duì)應(yīng)費(fèi)用為47000元,所以增加的總費(fèi)用為998000元。CB F是8-17連接,對(duì)應(yīng)費(fèi)用為64500元;D B C F G A4是23-54 連接,對(duì)應(yīng)費(fèi)用為46500元,所以增加的總費(fèi)用為111

26、000元。CD F是46-71連接,對(duì)應(yīng)費(fèi)用為52800元,B F G D E A是61-68 連接,對(duì)應(yīng)費(fèi)用為52800元,所以增加的總費(fèi)用為105600元。CF B C D E A是是2-10連接,對(duì)應(yīng)費(fèi)用為47000元,D B C F G A4是23-54連接,對(duì)應(yīng)費(fèi)用為46500元,;B F G D E A4是 61-68連接,對(duì)應(yīng)費(fèi)用為52800元,;所以增加的總費(fèi)用為146300元。通過(guò)比較4個(gè)方案,可以得知第一個(gè)方案所需要增加的費(fèi)用最省,費(fèi)用是是99800元,所以總的鋪設(shè)費(fèi)用 Z3 = Z1 +99800=3047600元。圖6任一鏈路岀現(xiàn)故障可靠性達(dá)到90%的最優(yōu)鋪設(shè)方案圖四、

27、問(wèn)題四的分析與求解1對(duì)問(wèn)題的分析在問(wèn)題二及問(wèn)題三的基礎(chǔ)上,首先對(duì)比分析問(wèn)題二與問(wèn)題三的節(jié)點(diǎn)分類(lèi),發(fā)現(xiàn)問(wèn)題三中節(jié)點(diǎn)的分類(lèi)包含了問(wèn)題二中節(jié)點(diǎn)的分類(lèi),若滿足了了節(jié)點(diǎn)穩(wěn)定性的要求,則一定能滿足鏈路穩(wěn)定性的要求,故得出節(jié)點(diǎn)穩(wěn)定性比鏈路穩(wěn)定性更重要的結(jié)論;再通過(guò)節(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ì)問(wèn)題的求解我們以節(jié)點(diǎn)22為中心節(jié)點(diǎn),可以將最小生成樹(shù)分成四個(gè)大部分: A為節(jié)點(diǎn)22左邊 部分,A為節(jié)點(diǎn)22右上方部分,A為節(jié)點(diǎn)22右下方部分,A4即為剩下的部分,即代=22 56 54。所問(wèn)

28、題二中A可分為:B=134 26 61 50 32;C=70 36 814 66676247692291949285783520802439 40 63 7927 3713425337;問(wèn)題三中將A可分為:B = 1 3426 61503270368146667C = 6247 69229194928578352080243940637927 3713 42 53 37可見(jiàn)問(wèn)題三中A的節(jié)點(diǎn)分類(lèi)包括了問(wèn)題二中 A的分類(lèi) 問(wèn)題二中A可分為:D=30 38 45831596048E=51 12 46 3341686573182152439165525問(wèn)題三中將A分成:D =5130384583159

29、60481268466533 41 73E = 182152439165525利用matlab求解結(jié)果見(jiàn)表4。(程序間附錄程序4)表4問(wèn)題四結(jié)果圖節(jié)點(diǎn)1節(jié)點(diǎn)2鋪設(shè)費(fèi)用節(jié)點(diǎn)1節(jié)點(diǎn)2鋪設(shè)費(fèi)用26332070636425761382716 :24651030 n267534203941300011032634059273836381092 n24311900 n66751296631011908176451962565364128101962565可見(jiàn)問(wèn)題三中A的節(jié)點(diǎn)分類(lèi)包括了問(wèn)題二中 A的分類(lèi)故節(jié)點(diǎn)穩(wěn)定性的要求更高,即只要滿足了節(jié)點(diǎn)穩(wěn)定性就能滿足鏈條穩(wěn)定性的要求, 下面僅考慮節(jié)點(diǎn)穩(wěn)定性需求下的故障

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

31、%增加至90%時(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í)際解決 問(wèn)題中,總鋪設(shè)費(fèi)用還要考慮其他因素的影響。3.在

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

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

34、激動(dòng)波過(guò)程很相似,所以我們就通過(guò)研究后者的模型來(lái)類(lèi)比我們要解決的問(wèn)題,這種聯(lián)想類(lèi)比法也可以推廣到其它問(wèn)題。§模型的改進(jìn)本題中線路的可靠性?xún)H僅考慮了節(jié)點(diǎn)和鏈路的穩(wěn)定性,在保證連通性的情況下最小化了鋪設(shè)成本;但未考慮流量因素,流量與節(jié)點(diǎn)的度有關(guān),節(jié)點(diǎn)的度是指與節(jié)點(diǎn)直接連 接的鏈路的數(shù)量,流量因素是指:一個(gè)節(jié)點(diǎn)的度越多,流過(guò)這個(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ù)。令M (deg)代表圖中度的均值,std(deg)代表方差構(gòu)造流量函數(shù):

35、M (deg)() std (deg)而本文問(wèn)題一中有鋪設(shè)成本的目標(biāo)函數(shù)為:min ZWjj xiji 1 j 1將兩個(gè)因素綜合考慮,這里利用線性加權(quán)的辦法將其綜合,首先將式(1)、( 2)歸一化,然后定義偏好系數(shù)(0,, 越接近0表是決策者越傾向于費(fèi)用因素,越接近于1越傾向于流量因素,所以,最終的目標(biāo)函數(shù)為:f std(Wj Xjj) std ( M (deg)i 1 j 1 j jstd (deg)設(shè)置約束條件,其中假定每一個(gè)節(jié)點(diǎn)的度數(shù)屬于2,5的閉區(qū)間。凡是有節(jié)點(diǎn)度數(shù)不 在詞區(qū)間的方案都被認(rèn)為是不可行解。為防止螞蟻在尋優(yōu)的過(guò)程中產(chǎn)生不可行解,定義(low,up)為度的約束區(qū)間。對(duì)于每一個(gè)

36、節(jié)點(diǎn)i,其度deg(i),在此定義一個(gè)函數(shù):0if deg(i) (low,up)s low deg(i) if deg(i) ( , low) deg(i) up if deg(i) (up,)則可以定義罰函數(shù)為:Nfhs(j)Sii 1預(yù)算成本的約束:因?yàn)榍懊嫱茖?dǎo)出了一個(gè)新目標(biāo)函數(shù),所有鋪設(shè)成本不再是要優(yōu)化的對(duì)象。而在實(shí)際過(guò)程中,決策放能夠承擔(dān)的最大鋪設(shè)成本一定不大于預(yù)算。所以,定 義一個(gè)最大預(yù)算Fmax。根據(jù)心理學(xué)的知識(shí),決策者對(duì)費(fèi)用的容忍度通常都是在與最小成 本的比較中產(chǎn)生的,所以定義一個(gè)容忍百分比Ratio,其取值如下:Fmax fpminRatio 100%fpmin相應(yīng)的最大容忍

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

38、考慮了最小成本模型和度約束條件, 同時(shí)在本模型中又加入了流量及鏈路概率的影響。如當(dāng)前位于節(jié)點(diǎn)i的螞蟻k選擇j作為下一個(gè)節(jié)點(diǎn)的概率為:k j jPij ij ijl M其中,ij為鏈路ij信息素強(qiáng)度;ij為一個(gè)預(yù)先給定的啟發(fā)式信息,初始值為鏈 路ij距離的倒數(shù)。為本算法設(shè)置了啟發(fā)式信息的優(yōu)先級(jí):鏈路ij如果有一個(gè)端點(diǎn)的度為1,貝U j加1倍,若鏈路ij 2個(gè)端點(diǎn)的度都為1,0加2倍°a B是2個(gè)參數(shù),它們分別決定了信息素和啟發(fā)式信息的相對(duì)影響力。N'代表位于節(jié)點(diǎn)i的螞蟻k可以直接到達(dá)的相鄰節(jié)點(diǎn)的集合,也就是還沒(méi)有被螞蟻k訪問(wèn)的節(jié)點(diǎn)的集合。Step3本文使用的后臺(tái)策略是在螞蟻前進(jìn)

39、一步時(shí)就計(jì)算各個(gè)約束的值,看是否滿足要求,當(dāng)有一個(gè)約束不再滿足要求時(shí),螞蟻不再前行。一輪路徑探索完之后,計(jì)算目標(biāo) 函數(shù)的值,進(jìn)而挑選出最優(yōu)的路徑。Step4在每一輪路徑探索之后,更新信息素,更新規(guī)則如下:mkj(n 1) ij (n)j (n)k 1其中 為信息素?fù)]發(fā)程度;jk(n)表示第k次循環(huán)是否選擇了鏈路ij,如果先擇ij,/(n) Q/diSjj,否則,/(n) 0, Q是常數(shù)。5當(dāng)路徑探索的論述達(dá)到NCmax時(shí)輸出結(jié)果。因?yàn)橄伻核惴ㄓ休^強(qiáng)的收斂性,故當(dāng)經(jīng)過(guò)不同次數(shù)的迭代實(shí)驗(yàn)是,會(huì)得出較為相近 的結(jié)果,此時(shí)則為最優(yōu)的結(jié)果,最終的結(jié)果可有C語(yǔ)言編程完成。參考文獻(xiàn):1 .2 基于蟻群算法的

40、多目標(biāo)網(wǎng)絡(luò)鋪設(shè)策略研究龔承柱1,諸克軍1,郭海湘1,2(1.中國(guó)地質(zhì)大學(xué)經(jīng)濟(jì)管理學(xué)院,武漢 430074; 2.西安交通大學(xué)管理學(xué)院,西安710049).3 姜啟源,謝金星,葉俊.數(shù)學(xué)模型M北京;高等教育出版社,2011, 1.附錄程序 1:%A 表示權(quán)值矩陣%C 表示生成樹(shù)的權(quán)和%visit標(biāo)記是否訪問(wèn)過(guò)(1表示訪問(wèn),0表示未訪問(wèn)),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;% 初始化鄰接矩陣

41、 dis=zeros(1,L);dis(:)=inf;% 初始化 dis 數(shù)組 visit=zeros(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% 如果沒(méi)有標(biāo)記,開(kāi)始這個(gè)點(diǎn) dis(i)=min(dis(i),A(now,i);%

42、更新這個(gè) i 點(diǎn)到集合的最短距離,保存 到 dis 中if(dis(i)<m) m=dis(i); next=i;% 記錄下最小的那個(gè)點(diǎn),作為下一個(gè)計(jì)算的點(diǎn)。endendendC=C+m;% 加權(quán)值 visit(next)=1;% 標(biāo)記進(jìn)集合的點(diǎn) RESULT(k,next)=1;% 整合每次標(biāo)記 end for t=1:79;R(2,t)=find(RESULT(t,:)=1);% 按順序輸出節(jié)點(diǎn)表示連接過(guò)程endR % 結(jié)果矩陣輸出,第一行表示連接順序,第二行表示表示依次連接節(jié)點(diǎn)數(shù)C % 相應(yīng)情況下的最省鋪設(shè)費(fèi)用程序二:A=xlsread('date.xls'); %

43、 權(quán)值矩陣(節(jié)點(diǎn)之間的費(fèi)用表 =距離 * 單位費(fèi)用)n1=1 341-2661503270368146667;n2=51 301-384583159604812684665334173;n3=77 231-66457757111747217104415;m1=1 3426615032703681466676247692291949285 78 351.208024;m2=5130384583159604812684665334173182152439 16 55125 ; m3=7723664577571117472171044157645;m4=5422 56;% 輸入六個(gè)節(jié)點(diǎn)分類(lèi)矩陣x1=

44、m2 m3 m4;x2=m1 m3 m4;x3=m1 m2 m4;L1=length(n1);L2=length(n2);L3=length(n3);L4=length(m1);L5=length(m2);L6=length(m3);L7=length(m4); %分別求其長(zhǎng)度和兩兩組合長(zhǎng)度 t=1;for i=1:L1;for j=1:L2;R(t,:)=n1(i) n2(j) A(n1(i),n2(j) t=t+1;endfor k=1:L3;R(t,:)=n1(i) n3(k) A(n1(i),n3(k); t=t+1;endendfor j=1:L2;for k=1:L3;R(t,:)

45、=n2(j) n3(k) A(n2(j),n3(k); t=t+1;endendfor i=1:L1;for p=1:L5+L6+L7;R(t,:)=n1(i) x1(p) A(n1(i),x1(p); t=t+1;endendfor j=1:L2;for q=1:L4+L6+L7;R(t,:)=n2(j) x2(q) A(n2(j),x2(q); t=t+1;endendfor 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,

46、:)=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: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% 輸出分類(lèi)比較下的最省費(fèi)用及相應(yīng)連接

47、節(jié)點(diǎn)序號(hào)程序三:A=xlsread('date.xls'); % 權(quán)值矩陣(節(jié)點(diǎn)之間的費(fèi)用表 =距離 * 單位費(fèi)用)n1=1 34|2661503270368146667;n2=51 301-384583159604812684665334173;n3=77 23;66457757111747217104415;m1=1 3426615032703681466676247692291949285 78 351.208024;m2=5130384583159604812684665334173182152439 16 55125 ; m3=77231-66457757111747

48、2171044157645;m4=542256;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=length(m2);L6=length(m3);L7=length(m4); % 分別求其長(zhǎng)度和兩兩組合長(zhǎng)度t=1;for i=1:L1;for j=1:L2;R(t,:)=n1(i) n2(j) A(n1(i),n2(j); t=t+1;endfor k=1:L3;R(t,:)=n1(i) n3(k) A(n1(i),n3(k); t=t+1;endend

49、for j=1:L2;for k=1:L3;R(t,:)=n2(j) n3(k) A(n2(j),n3(k); t=t+1;endendfor i=1:L1;for p=1:L5+L6+L7;R(t,:)=n1(i) x1(p) A(n1(i),x1(p); t=t+1;endendfor j=1:L2;for q=1:L4+L6+L7;R(t,:)=n2(j) x2(q) A(n2(j),x2(q); t=t+1;endendfor k=1:L3;for r=1:L4+L5+L7;R(t,:)=n3(k) x3(r) A(n3(k),x3(r); t=t+1;endend % 分別求其長(zhǎng)度和兩兩組合長(zhǎng)度R1=sortrows(R(1:192,:),3);Result(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,

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論