數(shù)據(jù)模型決策05網(wǎng)絡(luò)優(yōu)化-文庫(kù)吧
2025-02-27 11:33 本頁(yè)面
【正文】 ??????????????????所有變量非負(fù)為各個(gè)節(jié)點(diǎn)間運(yùn)輸量設(shè)50x,x,x,x90xx70xx0xxxx60xx80xx.x900x400x400x200x300x700zminx,x,x,x,x,x2DCWDC2F1DCWDC1F2W2F2DCW2W2FDC2FDC2FDC1F2DCW1DCW1DCW1W1FDC1F1W1F2W2F2DCWDC2F1DCWDC1F1W1F2W2F2DCWDC2F1DCWDC1F1W1F最佳的解決辦法 F1DCF2 W2W1(30)(40)[80] [ 60 ][ 90 ][70][0](50)(30)(30)(50)最小費(fèi)用流問(wèn)題的數(shù)學(xué)建模 設(shè)一個(gè)有 n個(gè)節(jié)點(diǎn)， m條弧的網(wǎng)絡(luò)圖 Ｎ＝ {Ｖ ,Ｅ ,Ｗ } ，每一個(gè)節(jié)點(diǎn) i都對(duì)應(yīng)于一個(gè)數(shù) bi，表示該節(jié)點(diǎn)要求的凈流量。 如果 bi0，節(jié)點(diǎn) i為供應(yīng)節(jié)點(diǎn)，供應(yīng)量為 bi；如果 bi0，則為需求節(jié)點(diǎn)，需求量為 bi； 如果 bi=0，該節(jié)點(diǎn)為轉(zhuǎn)運(yùn)點(diǎn)。 對(duì)于一個(gè)網(wǎng)絡(luò)，如果有 ，稱為 供求平衡的網(wǎng)絡(luò) 。 網(wǎng)絡(luò)所有弧 （ i,j） ∈ G上的流量 xij（一共 n個(gè)分量）組成的向量 X=[xij]稱為 網(wǎng)絡(luò)的一個(gè)流 。 1 0nii b? ??（１）網(wǎng)絡(luò)中求流量分配使總流量達(dá)到一定要求，而總費(fèi)用最低 如果網(wǎng)絡(luò)的一個(gè)流滿足以下條件，則這樣的流稱為 可行流 。 a、 平衡條件 ： 對(duì)網(wǎng)絡(luò)中的任一節(jié)點(diǎn) i，在網(wǎng)絡(luò)中從節(jié)點(diǎn) i通過(guò)弧 (i,j)流向關(guān)聯(lián)的他節(jié)點(diǎn) j的流量 xij之和 減去與節(jié)點(diǎn) i關(guān)聯(lián)的其他節(jié)點(diǎn) j通過(guò)弧 (j,i)流入 i的流量 xji之和 與該節(jié)點(diǎn)要求的凈流量平衡。即： ij( i, j ) E x?? ij ji i( i , j ) E ( j , i ) Ex x b , i 1 , 2 , ..., n??? ? ???b、 容量限制條件 ： ij ij0 x u , i , j 1 , 2 , ..., n? ? ?ji( j ,i ) E x?數(shù)學(xué)模型： 網(wǎng)絡(luò)的每一弧 (i,j),都有一個(gè)單位流量的費(fèi)用系數(shù) cij與它對(duì)應(yīng)，如果弧 (i,j)上的流量為 xij，則該弧上這些流量引起的費(fèi)用為 cijxij。 網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題就是找到使總費(fèi)用最小的可行流。 ij ij( i , j ) Eij ji i( i , j ) E ( j , i ) Eij ijm in z c xx x b , i 1 , 2 , ..., ns .t .0 x u ( ( i , j ) E )????? ? ? ???? ? ? ?????模型有可行解的必要條件是：該網(wǎng)絡(luò)是供求平衡的網(wǎng)絡(luò)。即： 。為什么？ 1 0nii b? ??最小費(fèi)用流問(wèn)題的數(shù)學(xué)建模 （ 2）另一類最小費(fèi)用流問(wèn)題是在預(yù)算費(fèi)用 C給定的情況下，求流量分配，使得從 能夠輸送的總流量達(dá)到最大。 仍用決策變量 表示通過(guò)弧 (i,j)的流量， 表示弧 (i,j)的費(fèi)用系數(shù)， 表示弧 (i,j)上的容量，則數(shù)學(xué)模型為： ts vv ?ijx ijcijuij ij( i , j ) Esij ji s t( i , j ) E ( j , i ) Etij ijm ax z fc x Cf , ( i v )s .t . x x 0 , ( i v , v )f , ( i v )0 x u ( ( i , j ) E )????? ????????? ? ?????????? ? ? ??????最大流問(wèn)題 一、 有關(guān)概念： 例：下圖是輸油管道網(wǎng)， 為起點(diǎn)， 為終點(diǎn)， ， ， ， 為中轉(zhuǎn)站，弧上的數(shù)字表示該管道的最大輸油能 力（也稱容量），記為 ，問(wèn)應(yīng)如何安排各管道輸油量， 才能使從 到 的總輸油量最大？ 1v3v2,4v5 sv tv6v iju1v3v2v4v5vsv tv6v2333554svt1v3v2v4v5vsv tv6v2333554① 分別稱 為 發(fā)點(diǎn)、收點(diǎn) 。其余的點(diǎn)稱為 轉(zhuǎn)運(yùn)點(diǎn) 。 ,svt② 每一個(gè)弧上都給定一個(gè)容量的網(wǎng)絡(luò)稱為 容量網(wǎng)絡(luò) ，記 )W,E,V(G ?③ 的每一個(gè)弧上都給定一個(gè)實(shí)際流量 的網(wǎng)絡(luò)稱為給 定了 網(wǎng)絡(luò)一個(gè)流 。 ijx1v3v2v4v5vsv tv6v)5,5( )2,3( )2,4( )2,( )2,4( )4,5( )3,3( ),3( )0,3( )2,( )2,( ： 對(duì)每一弧上都有 ij ij0 x u?? ： 轉(zhuǎn)運(yùn)點(diǎn)：流出量 流入量 =0。 發(fā)收點(diǎn)：發(fā)點(diǎn)流出量 =收點(diǎn)流入量 =網(wǎng)絡(luò)總流量。 若 ，稱弧 是飽和弧。 ij ijxu? )v,v( ji使網(wǎng)絡(luò)總流量達(dá)到最大的可行流稱為 最大流 。 如果網(wǎng)絡(luò)的一個(gè)流滿足以下條件，則這樣的流稱為 可行流 : 最大流問(wèn)題的數(shù)學(xué)建模 用決策變量 表示通過(guò)弧 (i,j)的流量， 表示弧 (i,j)的容量，則數(shù)學(xué)模型為： ijx ijusij ji s t( i , j ) E ( j , i ) Etij ijm ax z ff , ( i v )x x 0 , ( i v , v )s .t .f , ( i v )0 x u ( ( i , j ) E )???? ????? ? ???? ?????? ? ? ????1v3v2v4v5vsv tv6v2333554BMZ公司的最大流問(wèn)題 ? BMZ公司是歐洲一家生產(chǎn)豪華汽車的制造商。雖然它生產(chǎn)的汽車在所有發(fā)達(dá)國(guó)家銷量都不錯(cuò)，對(duì)它來(lái)講，出口到美國(guó)尤其重要。 BMZ汽車正在加利福尼亞變得特別受歡迎，因此保證洛杉磯中心良好的供應(yīng)顯得特別的重要。 ? 大部分汽車配件以及新車是在該公司位于德國(guó)的斯圖加特的總廠生產(chǎn)的， BMZ公司需要制定一個(gè)計(jì)劃，使得下個(gè)月從總廠運(yùn)送到洛杉磯配送中心的配件流盡可能大。 ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1