發(fā)布時間：2024-07-06 13:42

　　網(wǎng)絡最大流問題是特殊的組合優(yōu)化以及線性規(guī)劃問題,其在很多領域都存在著廣泛的應用,例如物流行業(yè)的貨物運輸、快遞企業(yè)的站點選址、社交網(wǎng)絡的信息分析等,都可以轉(zhuǎn)化為網(wǎng)絡最大流問題。在如今大數(shù)據(jù)時代背景下,雖然網(wǎng)絡最大流問題已有幾十年的發(fā)展歷史,但經(jīng)典的算法很難滿足大規(guī)模網(wǎng)絡的計算要求。于是,對最大流問題的進一步深入鉆研具備重大的實際價值。本文對網(wǎng)絡最大流問題的經(jīng)典算法進行了改進,主要成果如下:1、給出基于余網(wǎng)絡的最短增廣鏈算法,將余網(wǎng)絡與剩余網(wǎng)絡進行比較,發(fā)現(xiàn)余網(wǎng)絡的構(gòu)造比剩余網(wǎng)絡的簡單。通過減弱對最短增廣鏈算法的約束,用余網(wǎng)絡替換剩余網(wǎng)絡,并且將余網(wǎng)絡進行劃分區(qū)域,使得算法的運行效率得以提高。通過分析實驗數(shù)據(jù)可知:新算法與最短增廣鏈算法求解的最大流流值一致,且比經(jīng)典的最短增廣鏈算法運行效率更高。2、通過分析容量網(wǎng)絡圖,提出基于分層剩余網(wǎng)絡的最短增廣鏈改進算法,首先刪除容量網(wǎng)絡中不能通向終點的弧,來簡化容量網(wǎng)絡;其次對分層剩余網(wǎng)絡中刪除的飽和弧,相應的在原網(wǎng)絡中刪除該弧,降低構(gòu)建剩余網(wǎng)絡和分層剩余網(wǎng)絡的復雜性,于是使算法的運行效率得以進一步的提升。實驗結(jié)果顯示,改進算法能夠得到最大流的精確解...

【文章頁數(shù)】：52 頁

【學位級別】：碩士

【部分圖文】：

圖!9*()多源多匯的仿真結(jié)果

結(jié)果中可以看到相關的比較結(jié)果!從多源多匯的規(guī)劃公式及相應的結(jié)果可以看出"對應每一源&匯的最大流值和相應弧上的流量映射都是相互獨立的"完全可以采用在單源&單匯研究中算法’分別找出相應于某一源&匯對的所有路徑"并建立相應源&匯之間的路徑#()*$"實現(xiàn)各源&匯間的流量傳輸"從....

圖!9*()多源多匯的仿真結(jié)果

結(jié)果中可以看到相關的比較結(jié)果!從多源多匯的規(guī)劃公式及相應的結(jié)果可以看出"對應每一源&匯的最大流值和相應弧上的流量映射都是相互獨立的"完全可以采用在單源&單匯研究中算法’分別找出相應于某一源&匯對的所有路徑"并建立相應源&匯之間的路徑#()*$"實現(xiàn)各源&匯間的流量傳輸"從....

圖1容量網(wǎng)絡及可行流

2)去掉所有標號,回到第10步,對f~′={f~′ij}重新標號.5　計算示例圖1表明一容量網(wǎng)絡及初始可行流,即零流.每條弧上的有序數(shù)表示(c~ij,f~ij),求容量網(wǎng)絡的最大流.圖1　容量網(wǎng)絡及可行流10標號過程.先給1標以(Δ,+∞),其它節(jié)點的標號見圖22、轉(zhuǎn)入調(diào)整過....

圖46結(jié)束語

2、轉(zhuǎn)入調(diào)整過程,調(diào)整后的可行流見圖33、重新開始標號過程,尋找可增廣鏈.其標號亦示于圖3中.4、再轉(zhuǎn)入調(diào)整過程,調(diào)整后的可行流見圖45、對圖4可行流進行標號過程,尋找可增廣鏈.其標號亦示于圖4中.可見只能對1,3點進行標號,由此得到標號集合S={1,3},未標號集合S-={....

本文編號：4002638