下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領
文檔簡介
基于模糊最小生成樹的城域通信網(wǎng)絡優(yōu)化模型
1網(wǎng)絡拓撲結(jié)構(gòu)的優(yōu)化近年來,隨著計算機網(wǎng)絡應用的蓬勃發(fā)展,新的網(wǎng)絡產(chǎn)品和網(wǎng)絡技術也得到了應用,使計算機網(wǎng)絡的規(guī)??梢詳U大。在現(xiàn)實生活中,有許多問題類似于建筑工地之間的電話線、管道和建筑物之間的道路。通常,在一些早期的發(fā)展階段,由于技術和財力的限制,人們總是從降低成本的角度設計網(wǎng)絡,并嘗試連接不同的城市。這是最短的長度。某省的7個城市需要架設通信網(wǎng)絡系統(tǒng),為連接這7個城市,每2個城市之間的距離如表1所示.考慮地理環(huán)境的影響,綜合考慮各城市之間的距離和每公里修建網(wǎng)絡的費用,各城市之間修建網(wǎng)絡每公里的費用可用與10000元之間的比較來估計(表2).試問如何架設通信網(wǎng)絡,使總費用最小?對于此類網(wǎng)絡架設問題,通常采用星型、環(huán)型或總線型網(wǎng)絡拓撲結(jié)構(gòu),能夠較好地解決網(wǎng)絡建設過程中的連接和通信問題.但僅僅是基于網(wǎng)絡拓撲結(jié)構(gòu)的網(wǎng)絡構(gòu)架,往往達不到建設費用最小的要求.圖與網(wǎng)絡是運籌學中的一個經(jīng)典和重要的分支,所研究的問題涉及經(jīng)濟管理、工業(yè)工程、交通運輸、計算機科學與信息技術、通訊與網(wǎng)絡技術等諸多領域.因此,在網(wǎng)絡拓撲結(jié)構(gòu)的優(yōu)化中引入圖論的方法,以獲得實際應用中較理想的網(wǎng)絡建設方案.同時,以往對于此類問題的處理,通常都是采用精確數(shù)學的方法去解決.然而,人們的思維中有許多沒有明確外延的概念,即模糊概念.語言上有許多模糊概念的詞,例如以人的年齡為論域,那么“年青”、“中年”、“老年”都沒有明確的外延.在上述問題中所給出的“相當接近”、“可認為是”、“差不多是”等詞都是模糊概念,無法用精確數(shù)學的方法去解決.所以,又引入了模糊數(shù)學,模糊集合是其基本概念之一.2相關概念和符號的表達2.1圖論與線性規(guī)劃圖、邊、權(quán)、無向圖、鏈、連通圖、樹、生成樹、最小生成樹的概念及符號表示見文獻.圖論方法已經(jīng)成為數(shù)學模型中重要的數(shù)學方法,許多數(shù)學問題如果能夠歸結(jié)為圖論問題,往往能夠迎刃而解,在計算機理論以及數(shù)學的其他分支中有廣泛的應用.在管理科學中,基于圖論的統(tǒng)籌方法也得到廣泛的應用.許多圖論問題可以化為線性規(guī)劃問題,不過圖論中的許多特殊算法比利用一般線性規(guī)劃方法有效得多.2.2模糊數(shù)學的基本方法將被討論的全體對象或范圍叫做論域,常用U,V,E,…,X,Y,…大寫字母表示.將論域中的每個對象稱為元素,用相應的小寫字母u,v,e,…,x,y,…表示.隸屬函數(shù):用解析形式描術元素屬于集合的程度.設A是論域X上的集合,記為UA(x)={1當x∈A,0當x?A.UA(x)={1當x∈A,0當x?A.集合A的特征函數(shù),也稱為隸屬函數(shù).模糊集:論域X上的模糊集合AˉˉˉAˉ由隸屬函數(shù)U(x)來表征,其中U(x)在實軸的閉區(qū)間[0,1]上取值,U(x)的值反映了X中的元素x對于AˉˉˉAˉ的隸屬程度.模糊數(shù)學是研究現(xiàn)實中許多界限不分明問題的一種數(shù)學工具,它的主要概念包括模糊集合、隸屬函數(shù)等.模糊集合完全由隸屬函數(shù)所刻劃.接下來用圖論法和模糊集合的方法來解決網(wǎng)絡架設問題的數(shù)學模型.3模糊集合的確定按照圖論法的規(guī)則建立通信網(wǎng)絡的圖論模型,即以7個相鄰的城市為圖的頂點,兩頂點之間的網(wǎng)絡線路為圖的邊,其定義如下:G={V,E},V={R1,R2,R3,R4,R5,R6,R7},E={(R1,R2),(R1,R3),(R1,R4),(R1,R5),(R1,R6),(R1,R7),(R2,R3),(R2,R4),(R2,R5),(R2,R6),(R2,R7),(R3,R4),(R3,R5),(R3,R6),(R3,R7),(R4,R5),(R4,R6),(R4,R7),(R5,R6),(R5,R7),(R6,R7)}.由該定義所構(gòu)成的無向連通圖如圖1所示.每條邊的權(quán)w為某2個頂點之間網(wǎng)絡建設的費用,如聯(lián)結(jié)頂點R1和R2的邊上的權(quán)值記為w(R1,R2).因此,一個無向連通圖可以定義為頂點、邊、權(quán)值構(gòu)成的集合,即G={V,E,W}.通過以上定義,可將城市之間的通信網(wǎng)絡架設問題轉(zhuǎn)化為以建設費用最省為優(yōu)化目標,求解最優(yōu)通信網(wǎng)絡的問題.在建設費用函數(shù)未知的情況下,可先將建設網(wǎng)絡的費用看作城市之間距離的線性函數(shù),并考慮其他因素(地理、環(huán)境)的影響,先求解城域網(wǎng)絡的初始布局,即將這些頂點用邊聯(lián)結(jié)起來,用兩頂點間的直線距離與每公里網(wǎng)絡建設費用的乘積作為邊的權(quán),使總的權(quán)值最小.可用圖論中的求解最小生成樹的方法求解.所以,問題的關鍵在于如何確定各條邊上的權(quán)值.在前面定義過,權(quán)值等于城市之間距離與每公里網(wǎng)絡建設費用的乘積.各城市之間的距離是以公里為單位的確定值,可以定義L(Ri,Rj)為兩頂點Ri和Rj之間的距離,在表1中已列出所有具體值.由于考慮到受地理、環(huán)境因素的影響,相同距離、不同地段的建設費用存在差別,而表2中只列出了各地段每公里建設費用與10000元之間的比較關系,因此,引入模糊集合來表示這種界限不分明的情況.前面提到過,模糊集合完全由隸屬函數(shù)所刻劃,隸屬函數(shù)及其確定是模糊數(shù)學中最重要、最基本的量.在實際應用中,它的確定方法主要有模糊統(tǒng)計法、德爾菲法、對比排序法、綜合加權(quán)法等等,當然也可以直接使用常見的規(guī)則的隸屬度函數(shù),但必須知道變量的確定量度和意義.按照表2所列出的各種比較關系,根據(jù)語義規(guī)則,可以得到一個程度集合(完全是、可認為是、差不多是、非常接近、十分接近、相當接近、很接近、比較接近、大致接近).根據(jù)相對于10000元的各種比較關系,分3種情況討論每公里網(wǎng)絡建設的實際費用:(1)10000元是最大值;(2)10000元是最小值;(3)10000元是一個中間值.由于問題要求求解最小費用,因此可以暫且只考慮以10000元為每公里網(wǎng)絡建設費用的最大值,這樣使得總花費最小.于是給定程度集合的一個加權(quán)因子P=[1,0.95,0.9,0.85,0.8,0.75,0.7,0.65,0.6],這些因子與10000的乘積,可用于計算每公里網(wǎng)絡建設費用的近似值.在表3中給出程度集合的符號表示以及按語義規(guī)則所分配的值.通過上述定義,可以進一步描述圖1中聯(lián)接每對頂點的邊的權(quán)值w(vi,vj)=L(vi,vj)·Cn·M,(1)其中M為常數(shù)10000.為計算每條邊的權(quán)值,參照表1至表3得到2個矩陣,其對應位置上分別列出L(vi,vj)和Cn的值:??????????41011581084326965510107955?????????????????????0.60.950.7510.650.90.850.80.9510.70.90.850.80.60.9510.650.70.850.65??????????(41058610118491010367259555)?(0.60.9510.850.70.950.750.650.80.910.90.950.850.6510.80.70.60.850.65)表4是根據(jù)(1)式計算得到的任意2個城市之間網(wǎng)絡建設的費用.圖論中求無向連通圖G={V,E,W}的最小生成樹法.最小生成樹法將城域網(wǎng)絡看作無向連通圖,求該圖的最小生成樹,常用經(jīng)典算法有prim算法、Kruskal算法.下面將介紹以Kruskal算法解決上述問題的步驟.4執(zhí)行文件和運行結(jié)果4.1賦權(quán)圖g中的邊的排列每次添加權(quán)盡量小的邊,使新的圖無圈,直到生成1棵樹為止,便得最小生成樹.算法步驟如下:(ⅰ)將賦權(quán)圖G中的邊按權(quán)的非減次序排列;(ⅱ)按(ⅰ)排列的次序檢查G中的每一條邊,如果這條邊與已得到的邊不產(chǎn)生圈,就取這一條邊為解的一部分;(ⅲ)若已取到n-1條邊,算法終止,此時以V為頂點集,以取到的n-1條邊為邊集的圖即為最小生成樹.4.2s1.4.3t4.3賦權(quán)的連通圖G={V,E,W}中m=|E|,n=|V|.S1對E中各邊的權(quán)排序,設w1≤w2≤…≤wm,wi=w(ei).S2初始化:w←0,T←?,k←1,t←0.S3若t=n-1則轉(zhuǎn)S6,否則轉(zhuǎn)S4.S4若T∪{ek}有圈則k←k+1轉(zhuǎn)S4,否則轉(zhuǎn)S5.S5T←T∪{ek},w←w+wk,t←t+1,k←k+1,轉(zhuǎn)S3.S6輸出T及w,結(jié)束.其中T為最小樹,w為T的權(quán).具體流程圖見圖2.4.3計算機上測試按照上述思想,用C語言編寫了Kruskal算法的實現(xiàn)程序,并在計算機上測試.測試結(jié)果與預期結(jié)果完全一樣,即得到了連結(jié)7個城市的最小生成樹.程序運行后,得到圖1的最小生成樹見圖3.其總權(quán)值為1670,為連接7個城市的最小權(quán)值.5算法實現(xiàn)程序模擬對現(xiàn)代城域網(wǎng)絡架設問題進行了建模分析,基于模糊最小生成樹理論對網(wǎng)絡初始模型實施優(yōu)化處理,在現(xiàn)實界限不分明的情況下,以投資建設費用最省為目標,獲得了7個城市間網(wǎng)絡架設的最佳方案,并使用C語言編寫了算法實現(xiàn)程序,得到正確的運行結(jié)果.通過分析認為,在
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 廣東省湛江市坡頭區(qū)2023-2024學年七年級上學期期末考試數(shù)學試卷(含答案)
- 養(yǎng)老院老人生活照顧人員福利待遇制度
- 養(yǎng)老院老人健康監(jiān)測人員考核獎懲制度
- 2024年土地儲備與供應股權(quán)合作開發(fā)合同3篇
- 拖欠廠房租協(xié)議書
- 2025年慶陽貨運考試題目
- 2024年新型內(nèi)墻膩子涂料施工合作協(xié)議3篇
- 2025年日照貨運上崗證考試題庫1387題
- 2024年版:解除品牌授權(quán)協(xié)議書3篇
- 2025年池州普通貨運從業(yè)資格證考試
- 讀了蕭平實導師的《念佛三昧修學次第》才知道原來念佛門中有微妙法
- 周邊傳動濃縮刮泥機檢驗報告(ZBG型)(完整版)
- 紙箱理論抗壓強度、邊壓強度、耐破強度的計算
- 土地增值稅清算審核指南
- 死亡通知書模板
- 鷸蚌相爭課件
- PMC(計劃物控)面試經(jīng)典筆試試卷及答案
- 失業(yè)保險金申領表_11979
- 《質(zhì)量管理體系文件》風險和機遇評估分析表
- 食品安全約談通知書
- 舒爾特方格A4直接打印版
評論
0/150
提交評論