系統(tǒng)優(yōu)化算法課程設(shè)計(jì)論文-最小費(fèi)用最大流算法設(shè)計(jì)與實(shí)現(xiàn)-資料下載頁(yè)
2025-06-07 02:17本頁(yè)面
【正文】 if(flow[0][j]!=max) maxflow+=flow[0][j]。 } if(maxflow==stream) break。 modifycost()。 approach()。 //采用逐次逼近法得到一條增廣鏈 } printf(最終流量矩陣： \n)。 for(i=0。in。i++) 第 16 頁(yè) 共 20 頁(yè) { for(j=0。jn。j++) { printf(%d ,flow[i][j])。 } printf(\n)。 } printf(最終費(fèi)用矩陣： \n)。 for(i=0。in。i++) { for(j=0。jn。j++) { printf(%d ,cost[i][j])。 } printf(\n)。 } for(i=0。in。i++) { for(j=0。jn。j++) { if(flow[i][j]!=100 amp。amp。 scost[i][j]!=100) { mincost+=flow[i][j]*scost[i][j]。 } } } 第 17 頁(yè) 共 20 頁(yè) printf(最大流為： %d\n,stream)。 printf(最小費(fèi)用為 ： %d\n,mincost)。 } 3 實(shí)驗(yàn)研究小結(jié) 使用說(shuō)明詳述 本部分功能操作注意事項(xiàng) 在初始化每條邊上的容量限制、流量和費(fèi)用時(shí)， 當(dāng)兩個(gè)點(diǎn) 不 直接連通 時(shí)用 100 來(lái)代替無(wú)窮大，當(dāng)題目所給數(shù)字本來(lái)就大時(shí)，也可用更大的數(shù)如 1000 來(lái)答題無(wú)窮大 ，當(dāng)起始點(diǎn)和終點(diǎn)相同時(shí)，容量、流量和費(fèi)用均用 0 來(lái)表示。在輸入數(shù)據(jù)時(shí)，依次輸入容量限制 ijc 、邊上的流量 ijf 和費(fèi)用 (cos )ij ijdt，三個(gè)數(shù)據(jù)之間用逗號(hào)隔開(kāi)，然后再空格輸入下一邊上的數(shù)。 本部分功能與其他系統(tǒng)的關(guān)系 最小費(fèi)用最大流是一類網(wǎng)絡(luò)優(yōu)化問(wèn)題 , 在現(xiàn)實(shí)生活中 往往被系統(tǒng)管理者和決策者所重視。本文綜合求最大流原理和求最短路原理 ,在VC++ 的軟件開(kāi)發(fā)環(huán)境 下 直接輸入初始狀態(tài)下就求出任何一個(gè)網(wǎng)絡(luò)圖的最小費(fèi)用值 ,最大流值以及其他一些相關(guān)數(shù)據(jù)。該算法程序可以為我們減少大量計(jì)算 ,提高工作效率 。 測(cè)試案例詳述 例：給定費(fèi)用、容量網(wǎng)絡(luò)圖（ a），弧旁數(shù)字為（ cij， bij），試求該網(wǎng)絡(luò)的最大流 為 10 時(shí)的 最小費(fèi)用 。 第 18 頁(yè) 共 20 頁(yè) ( a )( b ) L ( f( 0 ))( c ) f( 1 )( d ) L ( f( 1 ))( e ) f( 2 )( f ) L ( f( 2 )) ( g ) f( 3 )v1vsvtv3v2（10,4）（7,1）（ 8 , 1 ）（ 5 , 2 ）（2,6）（ 4 , 2 ）（ 1 0 , 3 ）vsvsvsvsvsvsv2v2v2v2v2v2v3v3v3v3v3v3vtvtvtvtvtvtv1v1v1v1v1v1412621305550004 162 21 1327500504 1 21 136227053831 4解 ：⑴ 取 0流為初始最小費(fèi)用可行流 f(0)，即 v(f(0))=0。 ⑵ 構(gòu)造關(guān)于 f(0)的有向費(fèi)用網(wǎng)絡(luò) L（ f(0)），如圖（ b）所示； 第 19 頁(yè) 共 20 頁(yè) ⑶ 可求得 L（ f(0)）的最短路為 Vs→ V2→ V1→ Vt。在原網(wǎng)絡(luò)圖中與這條最短路相應(yīng)的增廣鏈 {Vs， V2， V1， Vt}上，對(duì)流量 v(f(0))進(jìn)行調(diào)整，調(diào)整量θ =min{8,5,7}=5，從而得到新的最小費(fèi)用流 f(1),其流量v(f(1))=5，如圖（ c）所示； ⑷ 構(gòu)造關(guān)于 f(1)的有向費(fèi)用網(wǎng)絡(luò) L（ f(1)），如圖（ d）所示； ⑸ 可求得 L（ f(1)）的最短路為 Vs→ V1→ Vt。在原網(wǎng)絡(luò)圖中與這條最短路相應(yīng)的增廣鏈 {Vs， V1， Vt}上，對(duì)流量 v(f(1))進(jìn)行調(diào)整，調(diào)整量θ =min{10,75}=2，從而得到新的最小費(fèi)用流 f(2),其流量 v(f(2))=7，如圖（ e）所示； ⑹ 構(gòu)造關(guān)于 f(2)的有向費(fèi)用網(wǎng)絡(luò) L（ f(2)），如圖（ f）所示； ⑺ 可求得 L（ f(2)）的最短路為 Vs→ V2→ V3→ Vt。在原網(wǎng)絡(luò)圖中與這條最短路相應(yīng)的增廣鏈 {Vs， V2， V3， Vt}上，對(duì)流量 v(f(2))進(jìn)行調(diào)整，調(diào)整量θ =min{85， 10,4}=3，從而得到新的最小費(fèi)用流 f(3),其流量v(f(3))=10，如圖（ g）所示； 它對(duì)應(yīng)的總費(fèi)用為： d（ f(3)） =2 4＋ 8 1＋ 5 2＋ 3 3＋ 3 2＋ 7 1=48。 本案例由程序運(yùn)行所得結(jié)果框圖如下： 第 20 頁(yè) 共 20 頁(yè) 參考文獻(xiàn) [1]胡運(yùn)權(quán) .《運(yùn)籌學(xué)》 .清華大學(xué)出版社， 2021 [2]譚浩強(qiáng)，《 C程序設(shè)計(jì)》，清華大學(xué)出版社， 2021 [3]韓明亮 ， 求最小費(fèi)用最大流問(wèn)題的一種方法 [J]， 中國(guó)民航學(xué)院學(xué)報(bào) ,2021 [4]張遠(yuǎn)福 ,譚毓澄 ,余劍敏 ， 制造網(wǎng)絡(luò)的一個(gè)最小費(fèi)用最大流算法 [J]. 江西師范 大學(xué)學(xué)報(bào) (自然科學(xué)版 ). 2021 [5]寇瑋華 ,董雪 ,呂林劍 ， 交通運(yùn)輸網(wǎng)絡(luò)中兩個(gè)結(jié)點(diǎn)間有流量約束的最小費(fèi)用最大流算法 [J]， 蘭州交通大學(xué)學(xué)報(bào) . 2021
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1