運(yùn)籌學(xué)——圖與網(wǎng)絡(luò)(參考版)
2025-08-04 15:24本頁面
【正文】 s t 10 15 10 25 第四節(jié) 應(yīng)用舉例 例．某工廠使用一臺設(shè)備，每年年初工廠都要作出決定，如果繼續(xù)使用舊的，要付維修費(fèi)；若購買一臺新設(shè)備，要付購買費(fèi)．試制定一個５年更新計劃，使總支出最少．若已知設(shè)備在各年的購買費(fèi)，及不同機(jī)器役齡時的殘值與維修費(fèi)如下表５－１所示． 項(xiàng)目 第 1年 第 2年 第 3年 第 4年 第５年 購買費(fèi) 11 12 13 14 14 機(jī)器役齡 01 12 23 34 45 維修費(fèi) 5 6 8 11 18 殘值 4 3 2 1 0 表５－１ 第四節(jié) 應(yīng)用舉例 例．設(shè)有５位待業(yè)者，５項(xiàng)工作，他們各自能勝任工作情況如圖所示，要求，設(shè)計一個就業(yè)方案，使盡量多的人能就業(yè)． x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 。 Vs、 Vt分別為發(fā)點(diǎn)和收點(diǎn)，弧旁數(shù)字為 (cij,fij)。 最大流 W=5?；?(vs,v1)上， fs1=1， cs1=5， fs1cs1，則 v1的標(biāo)號為(vs,l(v1))其中 l(v1)=min[l(vs),(cs1fs1)]=[+∞,51]=4 (3)檢查 v1 (vs,4) (v1,1) (4)檢查 v2 (5)在 v3， v4中任選一個進(jìn)行檢查 調(diào)整過程： 按點(diǎn)的第一標(biāo)號找到一條增廣鏈。ij令 去掉所有的標(biāo)號，對新的可行流 f’={fij’}，重新進(jìn)入標(biāo)號過程。令調(diào)整量 θ是 l(vt)，即 vt的第二個標(biāo)號。重復(fù)上述步驟，一旦 vt被標(biāo)上號，表明得到一條從 vs到 vt的增廣鏈 u，轉(zhuǎn)入調(diào)整過程。這時點(diǎn) vj成為標(biāo)號而未檢查的點(diǎn)。這時點(diǎn) vj成為標(biāo)號而未檢查的點(diǎn)。一般地，取一個標(biāo)號而未檢查的點(diǎn) vi，對一切未標(biāo)號點(diǎn) vj： GO (vi， vj)上， fijcij，則給 vj標(biāo)號 (vi,l(vj))。 第三節(jié) 網(wǎng)絡(luò)最大流問題 (4,3) (2,2) (1,1) (3,0) vs v1 v2 v3 v4 vt 例：用標(biāo)號法求下圖所示網(wǎng)絡(luò)的最大流。 第三節(jié) 網(wǎng)絡(luò)最大流問題 四、求最大流的標(biāo)號法 在這個過程中，網(wǎng)絡(luò)中的點(diǎn)或者是標(biāo)號點(diǎn)（又分為已檢查和未檢查兩種），或者是未標(biāo)號點(diǎn)。 在弧 (vi,vj)∈ u上， 0fij≤cij，即 u中每一弧是非零流鏈。 定義 3： 設(shè) f是一個可行流， u是從 vs到 vt的一條鏈，若 u滿足下述條件，稱之為 (關(guān)于可行流 f的 )一條增廣鏈。另一類弧與鏈的方向相反，稱為 后向弧 。我們定義鏈的方向是從 vs到 vt，則鏈上的弧被分為兩類：一類是弧的方向與鏈的方向一致，叫作 前向弧 。把 fij=0的弧稱為 零流弧 ， fij0的弧稱為 非零流弧 。 ??Cvvijjic),(定理：在網(wǎng)絡(luò)中的最大流等于它的最小割集的容量。而把 稱為該割集的 容量 。即 ?? ?kkijij ffWffjjtisi ?? ??最大流：最大流問題就是求一個可行流 {fij}，使流量W達(dá)到最大。 流量： 所謂網(wǎng)絡(luò)上的流，是指定義在弧集合 A上的一個函數(shù) f={f(vi,vj)}，并稱 f(vi,vj)為弧 (vi,vj)上的流量?，F(xiàn)在要求制定一個運(yùn)輸方案使從 v1運(yùn)到 v6的產(chǎn)品數(shù)量最多。 第三節(jié) 最短路問題 ??????????????????????0442406282032210052150)0(DDv1 v2 v3 v4 v5 v1 v2 v3 v4 v5 第三節(jié) 最短路問題 ???????????????????04424037282032276052150)1(D????????????????????0442406282032210052150213 214 412 413 第三節(jié) 最短路問題 ?????????????????0442740372520322760572150)2(D??????????????????04424037282032276052150213 214 412 413 125 325 521 213 214 412 413 ?????????????????0442640362520322760562140)3(D????????????????0442740372520322760572150125 325 521 213 214 412 413 132 1325 4132 531 第三節(jié) 最短路問題 213 214 325 413 第三節(jié) 最短路問題 ?????????????????0442640362520322760562140)4(D132 1325 4132 531 213 214 325 413 ??????????
研究報告相關(guān)推薦
鄂ICP備17016276號-1