系統(tǒng)優(yōu)化算法課程設(shè)計(jì)論文-最小費(fèi)用最大流算法設(shè)計(jì)與實(shí)現(xiàn)(參考版)
2025-06-11 02:17本頁面
【正文】 本案例由程序運(yùn)行所得結(jié)果框圖如下： 第 20 頁 共 20 頁 參考文獻(xiàn) [1]胡運(yùn)權(quán) .《運(yùn)籌學(xué)》 .清華大學(xué)出版社， 2021 [2]譚浩強(qiáng)，《 C程序設(shè)計(jì)》，清華大學(xué)出版社， 2021 [3]韓明亮 ， 求最小費(fèi)用最大流問題的一種方法 [J]， 中國民航學(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 。在原網(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。 ⑵ 構(gòu)造關(guān)于 f(0)的有向費(fèi)用網(wǎng)絡(luò) L（ f(0)），如圖（ b）所示； 第 19 頁 共 20 頁 ⑶ 可求得 L（ f(0)）的最短路為 Vs→ V2→ V1→ Vt。 測(cè)試案例詳述 例：給定費(fèi)用、容量網(wǎng)絡(luò)圖（ a），弧旁數(shù)字為（ cij， bij），試求該網(wǎng)絡(luò)的最大流 為 10 時(shí)的 最小費(fèi)用 。本文綜合求最大流原理和求最短路原理 ,在VC++ 的軟件開發(fā)環(huán)境 下 直接輸入初始狀態(tài)下就求出任何一個(gè)網(wǎng)絡(luò)圖的最小費(fèi)用值 ,最大流值以及其他一些相關(guān)數(shù)據(jù)。在輸入數(shù)據(jù)時(shí)，依次輸入容量限制 ijc 、邊上的流量 ijf 和費(fèi)用 (cos )ij ijdt，三個(gè)數(shù)據(jù)之間用逗號(hào)隔開，然后再空格輸入下一邊上的數(shù)。 printf(最小費(fèi)用為 ： %d\n,mincost)。 scost[i][j]!=100) { mincost+=flow[i][j]*scost[i][j]。j++) { if(flow[i][j]!=100 amp。i++) { for(j=0。 } for(i=0。j++) { printf(%d ,cost[i][j])。i++) { for(j=0。 for(i=0。 } printf(\n)。jn。in。 //采用逐次逼近法得到一條增廣鏈 } printf(最終流量矩陣： \n)。 modifycost()。j++) { if(flow[0][j]!=max) maxflow+=flow[0][j]。 for(j=0。 while(1) { modify()。 } } } //END approach()// void main() { int i,j。 j=p[j1]。 j=p[i]。in。i++) { D[i]=pt[i]。 } } for(i=0。 j=i。i++) //找出最短路徑走向 { if(pt[i]+cost[i][j]==pt[j]) { p[j]=i+1。 for(i=0。 //兩次迭代的值不同 ,繼續(xù) } 第 14 頁 共 20 頁 }while(flag==0)。i++) { pt[i]=ptf[i]。 } for(i=0。j++) { if(min(pt[j]+cost[j][i])) min=pt[j]+cost[j][i]。 for(j=0。in。j++) pf[j]=pt[j]。 for(j=0。j++) pt[j]=cost[0][j]。 for(j=0。//當(dāng) N 變動(dòng)時(shí)， 0 的個(gè)數(shù)應(yīng)與 N一致 第 13 頁 共 20 頁 int min=max。 } printf(\n)。jn。in。 } } /* printf(費(fèi)用矩陣： \n)。 flow[j][i]==0)) 第 12 頁 共 20 頁 cost[i][j]=max。 c[i][j]==flow[i][j]) || (c[i][j]==max amp。 if((c[i][j]!=max amp。amp。amp。 flow[i][j]==max)) cost[i][j]=max。 c[i][j]==flow[i][j]) || (c[i][j]==max amp。 if((c[i][j]!=max amp。amp。jn。in。j++) { costpre[i][j]=cost[i][j]。i++) { for(j=0。 第 11 頁 共 20 頁 for(i=0。 }*/ } //END modify()// //調(diào)整費(fèi)用矩陣 cost[][]// void modifycost() { int i,j。j++) { printf(%d ,flow[i][j])。i++) {
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1