通信網(wǎng)絡(luò)的設(shè)計(jì)優(yōu)化問題-研賽建模論文

2013高教社杯全國大學(xué)生數(shù)學(xué)建模競(jìng)賽我們仔細(xì)閱讀了《全國大學(xué)生數(shù)學(xué)建模競(jìng)賽章程》和《全國大學(xué)生數(shù)學(xué)建模競(jìng)賽參賽規(guī)則》(以下簡稱為“競(jìng)賽章程和參賽規(guī)則”,可從全國大學(xué)生數(shù)學(xué)建模競(jìng)賽網(wǎng)站下載)。我們完全明白，在競(jìng)賽開始后參賽隊(duì)員不能以任何方式(包括電話、電子郵件、網(wǎng)上咨詢等)與隊(duì)外的任何人(包括指導(dǎo)教師)··、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競(jìng)賽章程和參賽規(guī)則的，如果引用別人的成果或其他公開的資料(包括網(wǎng)上查到的資料),必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文我們鄭重承諾，嚴(yán)格遵守競(jìng)賽章程和參賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽章程和參賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們授權(quán)全國大學(xué)生數(shù)學(xué)建模競(jìng)賽組委會(huì)，可將我們的論文以任何形式進(jìn)行公開展示(包括進(jìn)行網(wǎng)上公示，在書籍、期刊和其他媒體進(jìn)行正式或非正式發(fā)表等)。我們參賽選擇的題號(hào)是(從A/B/C/D中選擇一項(xiàng)填寫):我們的參賽報(bào)名號(hào)為(如果賽區(qū)設(shè)置報(bào)名號(hào)的話):所屬學(xué)校(·填寫完整的全名):參賽隊(duì)員(打印并簽名):1.指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人(打印并簽名):(論文紙質(zhì)版與電子版中的以上信息必須一致，只是電子版中無需簽名。以上內(nèi)容請(qǐng)仔細(xì)核對(duì)，提交后將不再允許做任何修改。如填寫錯(cuò)誤，論文可能被取消評(píng)獎(jiǎng)資格。)賽區(qū)評(píng)閱編號(hào)(由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)):2013高教社杯全國大學(xué)生數(shù)學(xué)建模競(jìng)賽賽區(qū)評(píng)閱編號(hào)(由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)):賽區(qū)評(píng)閱記錄(可供賽區(qū)評(píng)閱時(shí)使用):評(píng)閱人評(píng)分備注全國統(tǒng)一編號(hào)(由賽區(qū)組委會(huì)送交全國前編號(hào)):全國評(píng)閱編號(hào)(由全國組委會(huì)評(píng)閱前進(jìn)行編號(hào)):摘要設(shè)費(fèi)用為29478元。信網(wǎng)絡(luò)的連通效率低于90%,從中選取3個(gè)邊界節(jié)點(diǎn)51,70,77作為依據(jù)將問題一求得的通信網(wǎng)絡(luò)圖劃分為pl,p2,p3,p4,四個(gè)區(qū)域，通過求前三個(gè)區(qū)域間的最短路徑得出方案(15-38,61-68)的鋪設(shè)路線的最少費(fèi)用為30542元。要的節(jié)點(diǎn)所在的鏈路，再以分界點(diǎn)(51,70,77)為分區(qū)依據(jù)，劃分為我、W1,W2,W3,關(guān)鍵詞：最小生成樹prim算法節(jié)點(diǎn)收縮法鏈路收縮法鄰接矩陣關(guān)聯(lián)矩陣 1 3 3二、模型假設(shè) 4三、符號(hào)說明 4 55.1通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用 55.1.1構(gòu)造最小生成樹計(jì)算最小鋪設(shè)費(fèi)用 55.1.2最小鋪設(shè)費(fèi)用模型的結(jié)果 55.2通信網(wǎng)絡(luò)節(jié)點(diǎn)可靠度評(píng)估及最小費(fèi)用計(jì)算 65.2.1節(jié)點(diǎn)重要度評(píng)估：幾種節(jié)點(diǎn)重要度評(píng)估方法的比較 65.2.2節(jié)點(diǎn)重要度評(píng)估的符號(hào)說明 65.2.3基于網(wǎng)絡(luò)凝聚度的節(jié)點(diǎn)收縮法 75.2.4基于節(jié)點(diǎn)收縮法的節(jié)點(diǎn)重要度評(píng)估 75.2.5節(jié)點(diǎn)收縮算法極其復(fù)雜性 85.2.6基于節(jié)點(diǎn)重要度的鋪設(shè)方案及最小鋪設(shè)費(fèi)用 95.3通信網(wǎng)絡(luò)鏈路可靠度評(píng)估及最小費(fèi)用計(jì)算 5.3.1通信網(wǎng)絡(luò)鏈路重要度的模型假設(shè)與理論基礎(chǔ) 5.3.2鏈路收縮法和鏈路刪除法 5.3.3基于鏈路重要度的網(wǎng)絡(luò)鋪設(shè)方案及最小費(fèi)用 5.4綜合考慮網(wǎng)絡(luò)可靠性及鋪設(shè)費(fèi)用的鋪設(shè)方案 6.1模型的優(yōu)點(diǎn) 6.2模型的不足與改進(jìn) 七、參考文獻(xiàn) 八、附錄 結(jié)構(gòu)有關(guān)。結(jié)合題目給出的背景知識(shí)本文需要解決四個(gè)問題，以期得到鋪設(shè)費(fèi)用最小，問題1.要使得通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最省，請(qǐng)建立問題的數(shù)學(xué)模型，設(shè)計(jì)求解算法，問題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ì)求解算法，問題3:考慮到通信網(wǎng)絡(luò)鏈路的可靠性，若要求任意一條鏈路被破壞時(shí)，能夠保持通信問題4:綜合考慮網(wǎng)絡(luò)的可靠性以及鋪設(shè)費(fèi)用，試確定合理的鋪設(shè)方案。問題一：本文已經(jīng)告訴節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的單位鋪設(shè)費(fèi)用及距離，要使得總的鋪設(shè)費(fèi)性都達(dá)到90%。本文先通過算法計(jì)算出80個(gè)節(jié)點(diǎn)在整個(gè)通信網(wǎng)絡(luò)中的重要程度，然后一一找出出現(xiàn)故障后會(huì)對(duì)通信網(wǎng)絡(luò)影響超過90%的節(jié)點(diǎn)，總共有17個(gè)，經(jīng)過作圖發(fā)現(xiàn)，這17點(diǎn)均位于以其中三個(gè)點(diǎn)為分界點(diǎn)的主干道上，繼而將整個(gè)通信網(wǎng)絡(luò)分區(qū)，在分區(qū)然能夠保持通信暢通的可能性都達(dá)到90%,繼而求得最小的鋪設(shè)費(fèi)用。90%,運(yùn)用鏈路收縮法，構(gòu)建關(guān)聯(lián)矩陣，計(jì)算各條鏈路的重要性，分析得到重要的鏈路1)假設(shè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)故障率相同；2)假設(shè)不考慮鋪設(shè)過程中因路況的不同而產(chǎn)生的費(fèi)用的差異，即節(jié)點(diǎn)間的費(fèi)用僅由節(jié)3)假設(shè)每個(gè)節(jié)點(diǎn)故障發(fā)生與否相互獨(dú)立；4)假設(shè)節(jié)點(diǎn)和鏈路只有兩種狀態(tài)：正常和失效；5)假設(shè)所有的節(jié)點(diǎn)和邊失效的概率相同；四、符號(hào)說明2)Aj表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離；3)B;表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的鋪設(shè)費(fèi)用(單位：元/米);4)C;表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間總的鋪設(shè)費(fèi)用(單位：元);7)R表示重要節(jié)點(diǎn)出現(xiàn)故障后造成可靠性小于90%的節(jié)點(diǎn)集合；13)W?表示鏈路出現(xiàn)故障后造成可靠性小于90%的節(jié)點(diǎn)的集合；14)W,表示鏈路出現(xiàn)故障后造成可靠性不小于90%的節(jié)點(diǎn)的結(jié)合，5.1通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用案。由于節(jié)點(diǎn)間距離是已知的，首先構(gòu)造節(jié)點(diǎn)間距離矩陣，矩陣中第i行j列的元素值就是節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離。為了表達(dá)節(jié)點(diǎn)之間的聯(lián)系，根據(jù)距離矩陣，轉(zhuǎn)化為無向賦根據(jù)prim算法，構(gòu)造最小生成樹，利用MATLAB計(jì)算得出最小鋪設(shè)費(fèi)用為29478元。根據(jù)附件一中通信網(wǎng)絡(luò)節(jié)點(diǎn)連接情況繪制節(jié)點(diǎn)連接圖如下：5.2通信網(wǎng)絡(luò)節(jié)點(diǎn)可靠度評(píng)估及最小費(fèi)用計(jì)算(1)將節(jié)點(diǎn)的連接度作為節(jié)點(diǎn)重要度的評(píng)估方法。此種評(píng)估方法過于片面，并不是一(2)介數(shù)衡量節(jié)點(diǎn)的重要度。即經(jīng)過該節(jié)點(diǎn)的最短路徑越多該節(jié)點(diǎn)就越重要，但計(jì)算(3)基于生成樹數(shù)目的節(jié)點(diǎn)刪除法。這種方法定義節(jié)點(diǎn)的重要如果多個(gè)節(jié)點(diǎn)度為去掉(4)本文使用的評(píng)估準(zhǔn)則，假設(shè)節(jié)點(diǎn)在正常工作的情況下，通過收縮與該節(jié)點(diǎn)有關(guān)的(1)節(jié)點(diǎn)收縮(2)網(wǎng)絡(luò)凝聚度當(dāng)n=1時(shí)，我們令0=1,則0<0≤1,當(dāng)網(wǎng)絡(luò)中只有一個(gè)節(jié)點(diǎn)時(shí)，0取最大值1。由(2)和(3)可得到又因?yàn)?≤I(G*vi)<1(G),kj≥1,所以k;=n-1,1,將該節(jié)點(diǎn)收縮以后網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目就越少。網(wǎng)絡(luò)的凝聚度就越大。該節(jié)點(diǎn)越重要。另5.2.5算法極其復(fù)雜性下面我們給出評(píng)估節(jié)點(diǎn)重要度的簡單算法步驟.2)根據(jù)(2)計(jì)算網(wǎng)絡(luò)廚師凝聚度0[G];3)FORi=1ton//主循環(huán)，評(píng)估所有節(jié)點(diǎn)重要度；;根據(jù)(3)式計(jì)算IMC(v;);在每次節(jié)點(diǎn)收縮操作以后重新用Floyd算法計(jì)算D整個(gè)算法的時(shí)間復(fù)雜性將為0(n?)下面我們將給出一個(gè)計(jì)算D的時(shí)間復(fù)雜性為0(n2)的新算法。該算法只需在初始最短距離矩5)5.2.6基于節(jié)點(diǎn)重要度的鋪設(shè)方案及最小鋪設(shè)費(fèi)用通過程序得出這80個(gè)節(jié)點(diǎn)在通信網(wǎng)中的重要程度節(jié)點(diǎn)重要程度圖110.853730.862810.90927320.9510760.9531190.91624430.865680.9001020.8637150.86691340.8781710.866790.8863560.8730065676893由節(jié)點(diǎn)重要程度表可以看出(節(jié)點(diǎn)中任意一個(gè)節(jié)點(diǎn)出現(xiàn)故障對(duì)整個(gè)通信網(wǎng)絡(luò)的影響率高于90%,由由圖2可以看出這這三個(gè)因此可以51,70,77這三個(gè)點(diǎn)為分類依據(jù)，將圖1劃分為四類p1,p2,p3,p4,位于紅色主干道上的節(jié)點(diǎn)及其支干上的點(diǎn)分為一類，位于70節(jié)點(diǎn)以外的節(jié)點(diǎn)集(見紅色區(qū)域)為p1注釋：紅線主干道代表其上的節(jié)點(diǎn)任意一個(gè)節(jié)點(diǎn)出現(xiàn)故障對(duì)通信網(wǎng)絡(luò)的影響率高于90%●粉色節(jié)點(diǎn)集代表區(qū)域P1●綠色節(jié)點(diǎn)集代表區(qū)域P2●黃色節(jié)點(diǎn)集代表區(qū)域P3余下的節(jié)點(diǎn)集也為分布在紅色主干道兩側(cè)的節(jié)點(diǎn)集代表區(qū)域P4p1,p2,p3區(qū)域均不包含出現(xiàn)故障之后造成影響率超過90%的節(jié)點(diǎn)，因?yàn)樵谶@三個(gè)區(qū)域任意節(jié)點(diǎn)出現(xiàn)故障導(dǎo)致的影響都小于90%,因此只要保證鋪設(shè)的線路能降低紅色主干道上任意節(jié)點(diǎn)出現(xiàn)故障造成的影響。鋪設(shè)方案如下：在p1,p2間尋求一條最短路徑，使得紅色主干道上某一節(jié)點(diǎn)出現(xiàn)故障時(shí)，其他節(jié)點(diǎn)能通過這條新路連通，p3部分通過再與p1或p2建立一條最短路徑，就能保證主干道上任一節(jié)點(diǎn)出現(xiàn)故障導(dǎo)致的影響低于90%。通過程序求出D??,D??,D??以及D?.D?,D?,又由題目所要求的費(fèi)用最省得出目標(biāo)函數(shù)min{D??+D?,D??+D?,D?3+D?};第三步編程計(jì)算得D?z,D??,D?3分別為2091(60-61),536(15-38),780(1-72)百元。D?,D?D?分別為528(61-68),536(15-38),470(2-10)百元?？紤]到可靠性增加的費(fèi)用最省為min(2561,1064,1316)=1064百元。5.3通信網(wǎng)絡(luò)鏈路重要性的研究(1)模型假設(shè)(2)理論基礎(chǔ)路收縮法的原理是設(shè)e是圖G=(V,E)的一條邊，則G將連接邊e的兩個(gè)端點(diǎn)短接并由一個(gè)新的頂點(diǎn)代替，鏈路e從現(xiàn)在變?yōu)橛蒼個(gè)節(jié)點(diǎn)和m-1條邊組成，設(shè)G*e是從圖G中收縮邊e后得到的子令通信網(wǎng)絡(luò)的抽象模型為無自環(huán)連通圖G,則對(duì)鏈路收縮法的流程描述如下所示：第1步：輸入G的完全相關(guān)矩陣。并用(6)式計(jì)算全網(wǎng)第3步：收縮鏈路e;(即將連接鏈路的兩個(gè)節(jié)點(diǎn)，在完全關(guān)聯(lián)矩陣中表示第a行和第b行合并為一行),得到矩陣B,并計(jì)算矩陣B的kirchhoff矩陣C。第4步：刪除矩陣C的第1行和第1列，并用式(6)計(jì)算子網(wǎng)的生成樹數(shù)目t(G-e;)。第5步：用最小生成樹法計(jì)算每條鏈路歸一化后的重要性結(jié)果并輸出。若還沒有計(jì)算得鏈路，則返回第3步；否則，終止程序。令通信網(wǎng)絡(luò)的抽象模型為無自環(huán)連通圖G,則對(duì)鏈路刪除法的流程描述如下所示：第1步：輸入G的完全關(guān)聯(lián)矩陣。第2步：計(jì)算完全關(guān)聯(lián)矩陣的Kirchhoff矩陣，記為矩陣A,并用式(6)計(jì)算全網(wǎng)第3步：刪除鏈路e;(即刪除完全關(guān)聯(lián)矩陣第i列),得到矩陣B,并計(jì)算矩陣B的第4步：刪除矩陣C的第1行和第1列，并用式(6)計(jì)算子網(wǎng)的生成樹數(shù)目t(G-e;).第5步：用最小生成樹法計(jì)算每一條鏈路歸一化后的重要性結(jié)果并輸出。若還沒有計(jì)算的鏈路，則返回第3步；否則，終止程序。若要求任意一條鏈路被破壞時(shí)，能夠保持通信暢通的結(jié)點(diǎn)都能夠達(dá)到90%,也即當(dāng)某一鏈路被破壞時(shí)，失效的節(jié)點(diǎn)不超過8個(gè)。由以上鏈路重要性的分析可得重要鏈路也二分析的重要節(jié)點(diǎn)所在鏈路中，任一鏈路出現(xiàn)故障，都會(huì)導(dǎo)致至少8個(gè)節(jié)點(diǎn)失效，故可以這條主干道的邊界鏈路為分界點(diǎn)，將圖1劃分為4個(gè)區(qū)域W?,W?,W?W,,W?包含節(jié)點(diǎn)含主干道及其周圍節(jié)點(diǎn)數(shù)目較少的支鏈，W?,W?,W?任一鏈路出現(xiàn)故障都不會(huì)導(dǎo)致8個(gè)以上節(jié)點(diǎn)失效。故問題可轉(zhuǎn)化為求W?,W?,W?區(qū)域再根據(jù)題目要求的求最短鋪設(shè)方案求出六、模型的評(píng)價(jià)與改進(jìn)6.1模型的優(yōu)點(diǎn)(1)模型在解決節(jié)點(diǎn)可靠性的時(shí)候首先定義了網(wǎng)絡(luò)的凝聚度，在此基礎(chǔ)上提出了節(jié)點(diǎn)(2)節(jié)點(diǎn)收縮法綜合考慮了節(jié)點(diǎn)的連接度以及經(jīng)過該節(jié)點(diǎn)的最短路徑的數(shù)目，如果一(3)本文在評(píng)估鏈路可靠性的時(shí)候采用鏈路收縮法，通過計(jì)算收縮后子網(wǎng)的生成樹數(shù)(1)針對(duì)第三個(gè)問題運(yùn)用鏈路收縮法所編寫的程序存在疑點(diǎn)問題，導(dǎo)致模型無法得出(2)針對(duì)問題二問題三后面的分區(qū)問題，還可以再選取更精確的點(diǎn)集，使得所劃分的[3]YuhuaLi,ZuhairA.Bandar,DavidMcLean.Anapbetweenwordsusingmultipleinformationsources[J].DataEngineering,2003,15(4).[4]MatthewGardenandGregoryDudek.SemanticfeedbackforhybridrecommendationsinRecommendz[DBPOL].PuserPbjParticleP380924.function[result,D,tot]=myprim(C)C(C==0)=inf;%初始化，先構(gòu)造無向，然后把不可通設(shè)為infwhilesize(result,2)~=length(C)-1temp=C(p,tb);temp=temp(:);d=min(temp);3把剩下最小權(quán)取出[jb,kb]=find(C(p,tb)==d);%result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];gk找到每個(gè)納入p,未納入部分刪除kfunctionZ=nodedel(a,dy)8a為鄰接矩陣a(a==inf)=0;a(a~=0)=1;Z=zeros(n,1);8由鄰接矩陣a得到直接距離矩陣H%H表示c(ij)H(i,j)=0;elseifa(i,j)==1H(i,j)=1;endend%矩陣維數(shù)8節(jié)點(diǎn)重要度向量8用Floyd法計(jì)算節(jié)點(diǎn)收縮前的最短距離矩陣DD=H;forforj=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);end8計(jì)算節(jié)點(diǎn)重要度D2=zeros(size(D));%得到與節(jié)點(diǎn)i鄰接的節(jié)點(diǎn)向量II=zeros(1,0);t=0;forj=1:nifa(i,j)==1t=t+1;I=[I,j];end8計(jì)算收縮前的最短距離矩陣D2p=1:nforq=1:nifp~=i&q~=iifD(p,i)+D(i,q)==D(p,q)D2(p,q)=D(p,q)-2;elseifD(p,i)+D(i,q)==D(p,q)+1D2(p,q)=D(p,q)-1;elseifD(p,i)+D(i,q)>=D(p,q)+2D2(p,q)=D(p,q);endelseifp==ilq==iD2(p,q)=D(p,q)-1;D2(p,q)=0;endn3=n-t;g收縮后的節(jié)點(diǎn)數(shù)n3D3=D2;S計(jì)算收縮后的最短距離矩陣D3,D3為DD3(I,:)=[];8刪除與節(jié)點(diǎn)i鄰接的節(jié)點(diǎn)對(duì)應(yīng)的行D3(:,I)=[];8刪除與節(jié)點(diǎn)i鄰接的節(jié)點(diǎn)對(duì)應(yīng)的列8計(jì)算節(jié)點(diǎn)i收縮后的節(jié)點(diǎn)重要度s=s+D3(p,q);Z(i)=1/(n3*1);%電源節(jié)點(diǎn)重要度歸一化Zd=Z(dy);Zdm=max(Zd);Z(dy(i))=Z(dy(i))/Zdm;Z(dy(1))=1;8負(fù)荷節(jié)點(diǎn)重要度歸一化Zl=Z';Zl(:,dy)=[];Z1m=max(Zl);k=0;forj=1:tifi~=dy(j)k=k+1;ifk==tZ(i)=Z(i)/Zlm;%disp(['Z[',num2str(i),']=',num2str(Z(i))])8編寫m文件[distance,path]=mydijkstra(A,s,e)S[8A:adjcentmatrix%s:startnodeSe:endnodepath=[];visit=ones(1,n);visit(s)=0;parent=zeros(1,n);%sourcenodeisunvisibletheshortestdistancetemp=zeros(1,n);forj=1:ntemp=[temp(1:count)D(j)];temp=[temp(1:count)inf];j=index;visit(j)=0;ifD(k)>D(j)+A(j,k)D(k)=D(j)+A(j,k);parent(k)=j;theshortestdistancepathifparent(e)==0return;path=zeros(1,2*n);%pathpreallocationp=parent(t);path=[ppath(1:count)];t=p;error(['Thepathprealloca'Pleaseredefinepathpreallocationparameter.']);path(1)=s;path=path(1:count);function[result,AA1,AA2,AA3,AA4]=miniarea(C,S2,S3,S1)forj=1:length(S3)[distance,path]=mydijkstra(C,S2(i),S3(j));AA1=S2(i);AA2=S3(j);S23=[S2,S3];[distance,path]=mydijkstra(C,S23(q),S1(k));AA3=S1(k);AA4=S23(q);DD1=min;result=DD1+D23;function[minresult,xx1,xx2,xxxx1=0;xx2=0;xx3=0;[result,AA1,AA2,AA3,AA4]=miniarea(C,S2,S3,S1);if(minresult>result)minresult=result;[result,AA1,AA2,AA3,AA4]=miniarea(C,S1,S2,S3);if(minresult>result)minresult=result;if(minresult>result)minresult=result;End問題2鋪設(shè)方案連接費(fèi)用鋪設(shè)最小方連接點(diǎn)1連接點(diǎn)2連接點(diǎn)3連接點(diǎn)4function[result,D,tot]=myprimC(C==0)=inf;%初始化，先構(gòu)造無向，然后把不可通設(shè)為infresult=[];p=1;tb=2:length(C);whilesize(result,2)~=length(C)-1temp=C(p,tb);temp=temp(:);d=min(temp);g把剩下最小權(quán)取出[jb,kb]=find(C(p,tb)==d);%找到每個(gè)j=p(jb(1));k=tb(kb(1));result=[result,[j;k;dD(k,j)=d;D(j,k)=d;p=[p,k];tb(find(tb==k))=[];gk納入p,未納入部分刪除ktot=sum(result(3,:));問題1分配方案頂點(diǎn)A12255374頂點(diǎn)B25374頂點(diǎn)A-B費(fèi)用functionZ=nodedel(a,dy)8a為鄰接矩陣a(a==inf)=0;a(a~=0)=1;Z=zeros(n,1);8由鄰接矩陣a得到直接距離矩陣H8H表示c(ij)%矩陣維數(shù)8節(jié)點(diǎn)重要度向量endi=1:nforj=1:nifj==ielseifa(i,j)==1elseend8用Floyd法計(jì)算節(jié)點(diǎn)收縮前的最短距離矩陣Dfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)endendendend8計(jì)算節(jié)點(diǎn)重要度fori=1:n%得到與節(jié)點(diǎn)i鄰接的節(jié)點(diǎn)向量Iforj=1:nifa(i,j)==18計(jì)算收縮前的最短距離矩陣D28D2為d1(pq)D為d(pq)p=1:nforforifp~=i&q~=iifD(p,i)+D(i,q)==D(p,q)D2(p,q)=D(p,q)-2;elseifD(p,i)+D(i,q)==D(p,q)+1D2(p,q)=D(p,q)-1;elseifD(p,i)+D(i,q)>=D(p,q)+2D2(p,q)=D(p,q);endelseifp==i|q==iD2(p,q)=D(p,q)-1;endn3=n-t;8收縮后的節(jié)點(diǎn)數(shù)n3D3=D2;號(hào)計(jì)算收縮后的最短距離矩陣D3,D3為DD3(I,:)=[];8刪除與節(jié)點(diǎn)i鄰接的節(jié)點(diǎn)對(duì)應(yīng)的行D3(:,I)=[];%刪除與節(jié)點(diǎn)i鄰接的節(jié)點(diǎn)對(duì)應(yīng)的列%計(jì)算節(jié)點(diǎn)i收縮后的節(jié)點(diǎn)重要度forp=1:n3s=s+D3(p,q);end1=s/(n3*(n3-1)/2);8為nZ(i)=1/(n3*1);號(hào)電源節(jié)點(diǎn)重要度歸一化t=length(dy);Zd=Z(dy);Zdm=max(Zd);Z(dy(i))=Z(dy(i))/Zdm;Z(dy(1))=1;%負(fù)荷節(jié)點(diǎn)重要度歸一化Zl=Z';Z1(:,dy)=[];Z1m=max(Zl);k=0;forj=1:tifi~=dy(j)k=k+1;ifk==tZ(i)=Z(i)/Zlm;問題2節(jié)點(diǎn)重要度重要度頂點(diǎn)編號(hào)0.8637147280.8643826960.8644432930.86462513430.8669133290.8770318470.87817072640.8781707260.8791976640.9061183060.9092727650.9138377460.9145920970.9145920970.916244290.9226333810.9345941950.9420