運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析

上傳人:牛*** 文檔編號(hào):108303185 上傳時(shí)間:2022-06-15 格式:PPTX 頁數(shù):33 大?。?15.41KB
收藏 版權(quán)申訴 舉報(bào) 下載
運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析_第1頁
第1頁 / 共33頁
運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析_第2頁
第2頁 / 共33頁
運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析_第3頁
第3頁 / 共33頁

下載文檔到電腦,查找使用更方便

20 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析》由會(huì)員分享,可在線閱讀,更多相關(guān)《運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析(33頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、會(huì)計(jì)學(xué)1運(yùn)籌學(xué)運(yùn)籌學(xué) 圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析2022-6-15 第1頁/共33頁2022-6-15第2頁/共33頁2022-6-15續(xù)為止。續(xù)為止。第3頁/共33頁2022-6-15 T第4頁/共33頁2022-6-15 例例 用破圈法求下圖的最小樹用破圈法求下圖的最小樹12222312222333445第5頁/共33頁2022-6-15 第6頁/共33頁2022-6-15第7頁/共33頁2022-6-15 第8頁/共33頁2022-6-15第9頁/共33頁2022-6-15V1V4V2V3V6V9V8V7V542466234442第10頁/共33頁2022-6-15第11頁/共33頁202

2、2-6-15第12頁/共33頁2022-6-15 例:例: 求下圖所示有向圖中從求下圖所示有向圖中從v1到各點(diǎn)的到各點(diǎn)的最短路。最短路。v1v4v2v3v5v6v7v825-34674-23-1-342第13頁/共33頁2022-6-15 wij d(t)(v1,vj) v1 v2 v3 v4 v5 v6 v7 v8v1v2 v3 v4v5v6v7v80 25-30 -2406400-3 0720320t=1 t=2 t=3 t=4 t=5 t=6025-3020-3611020-36615020-3361410020-336910020-336910說明:表中空格處為說明:表中空格處為+ 。

3、第14頁/共33頁2022-6-15例例 設(shè)備更新問題設(shè)備更新問題制訂一設(shè)備更新問題,使得總費(fèi)用最小制訂一設(shè)備更新問題,使得總費(fèi)用最小 第第1年年 第第2年年 第第3年年 第第4年年 第第5年年 購買費(fèi)購買費(fèi) 13 14 16 19 24 使用年數(shù)使用年數(shù) 0-1 1-2 2-3 3-4 4-5 維修費(fèi)維修費(fèi) 8 10 13 18 27 解解設(shè)以設(shè)以vi(i=1,2,3,4,5)表示表示“第第i年初購進(jìn)一臺(tái)年初購進(jìn)一臺(tái)新設(shè)備新設(shè)備”這種狀態(tài),以這種狀態(tài),以v6表示表示“第第5年末年末”這種狀態(tài)這種狀態(tài);以??;以弧(vi, vj)表示表示“第第i年初購置的一臺(tái)設(shè)備一直使用年初購置的一臺(tái)設(shè)備一直使

4、用到第到第j年初年初”這一方案,以這一方案,以wij表示這一方案所需購置表示這一方案所需購置費(fèi)和維護(hù)費(fèi)之和。費(fèi)和維護(hù)費(fèi)之和。第15頁/共33頁2022-6-15這樣,可建立本例的網(wǎng)絡(luò)模型。于是,該問題就這樣,可建立本例的網(wǎng)絡(luò)模型。于是,該問題就可歸結(jié)為從圖中找出一條從可歸結(jié)為從圖中找出一條從v1到到v6的最短路問題的最短路問題。用用Dijkstra標(biāo)號(hào)法,求得最短路為標(biāo)號(hào)法,求得最短路為 v1v3v6 即第一年初購置的設(shè)備使用到第三年初予以更即第一年初購置的設(shè)備使用到第三年初予以更新,然后一直使用到第五年末。這樣五年的總新,然后一直使用到第五年末。這樣五年的總費(fèi)用最少,為費(fèi)用最少,為78。第1

5、6頁/共33頁2022-6-15v1v2v3v5v6v4214432228962316345244734273732(0,Vs)(0,V1)(31, V1)(44,V1)(62,V1)(78,V3)第17頁/共33頁2022-6-15第三節(jié)第三節(jié) 最大流問題最大流問題 如下是一運(yùn)輸網(wǎng)絡(luò),弧上的數(shù)字表示每條弧如下是一運(yùn)輸網(wǎng)絡(luò),弧上的數(shù)字表示每條弧上的容量,問:該網(wǎng)絡(luò)的最大流量是多少?上的容量,問:該網(wǎng)絡(luò)的最大流量是多少?vsv2v1v3v4vt432312234第18頁/共33頁2022-6-15第19頁/共33頁2022-6-152、可行流與最大流、可行流與最大流定義定義2 滿足下列條件的流稱

6、為滿足下列條件的流稱為可行流可行流:1) 0 fij cij2)平衡條件:平衡條件:中間點(diǎn)中間點(diǎn) fij = fji(vi,vj) A(vj,vi) A發(fā)點(diǎn)發(fā)點(diǎn)vs fsj fjs=v(f)(vs,vj) A (vj,vs) A ftj fjt= v(f)(vt,vj) A收點(diǎn)收點(diǎn)vt,(vj,vt) A式中式中v(f)稱為這個(gè)可行流的流量,即發(fā)點(diǎn)的凈輸出量稱為這個(gè)可行流的流量,即發(fā)點(diǎn)的凈輸出量(或收點(diǎn)的凈輸入量)。(或收點(diǎn)的凈輸入量)。第20頁/共33頁2022-6-15最大流問題:求一流最大流問題:求一流fij滿足滿足0 fij cij v(f) i=s fij fji= 0 i s,t

7、v(f) i=t且使且使v(f)達(dá)到最大。達(dá)到最大。第21頁/共33頁2022-6-153、增廣鏈、增廣鏈 給定可行流給定可行流f=fij,使,使fij=cij的弧稱為的弧稱為飽和弧飽和弧,使使fij0的弧稱為的弧稱為非零流弧非零流弧。 若若 是網(wǎng)絡(luò)中連接發(fā)點(diǎn)是網(wǎng)絡(luò)中連接發(fā)點(diǎn)vs和收點(diǎn)和收點(diǎn)vt的一條鏈,定的一條鏈,定義鏈的方向是從義鏈的方向是從vs到到vt,則鏈上的弧被分成兩類:,則鏈上的弧被分成兩類:前向?。夯〉姆较蚺c鏈的方向一致前向弧:弧的方向與鏈的方向一致 全體全體 +后向?。夯〉姆较蚺c鏈的方向相反后向?。夯〉姆较蚺c鏈的方向相反 全體全體 定義定義3 設(shè)設(shè)f是一可行流,是一可行流, 是

8、從是從vs到到vt的一條鏈,的一條鏈,若若 滿足下列條件,則稱之為(關(guān)于流滿足下列條件,則稱之為(關(guān)于流f的)一條的)一條增廣鏈:增廣鏈: 在弧在弧(vi,vj)+上,上,0 fijcij 在弧在弧(vi,vj)上,上,0fij cij第22頁/共33頁2022-6-15 4、截集與截量、截集與截量 定義定義4 給定網(wǎng)絡(luò)給定網(wǎng)絡(luò)D=(V,A,C),若點(diǎn)集,若點(diǎn)集V被被剖分為兩個(gè)非空集合剖分為兩個(gè)非空集合V1和和V1,使,使vs V1,vt V1,則把弧集,則把弧集(V1,V1)稱為是(分離稱為是(分離vs和和vt的的)截集。)截集。截集是從截集是從vs到到vt的必經(jīng)之路。的必經(jīng)之路。 定義定義

9、5 給定一截集給定一截集(V1,V1),把截集,把截集(V1,V1)中所有弧的容量之和稱為這個(gè)截集的容量中所有弧的容量之和稱為這個(gè)截集的容量(截量截量),記為記為C(V1,V1)。v(f) C(V1,V1)第23頁/共33頁2022-6-15 若對(duì)于一可行流若對(duì)于一可行流f*,網(wǎng)絡(luò)中有一截集,網(wǎng)絡(luò)中有一截集(V1*,V1*),使得,使得v(f*)= C(V1*,V1*),則,則f必是最大必是最大流,而流,而(V1*,V1*),必定是容量最小的截集,即,必定是容量最小的截集,即最小截集。最小截集。 定理定理1 可行流可行流f*是最大流的充要條件是不存是最大流的充要條件是不存在關(guān)于在關(guān)于f*的最大

10、流。的最大流。 若若f*是最大流,則網(wǎng)絡(luò)中必存在一個(gè)截集是最大流,則網(wǎng)絡(luò)中必存在一個(gè)截集(V1*,V1*),使得,使得 v(f*)= C(V1*,V1*) 定理定理2 任一網(wǎng)絡(luò)任一網(wǎng)絡(luò)D中,中,從從vs到到vt的最大流的的最大流的流量等于分離流量等于分離vs,vt的最小截集的截量。的最小截集的截量。第24頁/共33頁2022-6-15步驟步驟:2、 標(biāo)號(hào)過程標(biāo)號(hào)過程1、選取一個(gè)可行流(可選擇零流?。⑦x取一個(gè)可行流(可選擇零流?。?從從Vs出發(fā),出發(fā),在在前向前向弧弧上上(vi,vj) ,若,若fij0,則給,則給vj標(biāo)號(hào)標(biāo)號(hào)( Vi,l(vj),其中其中l(wèi)(vj)=minl(vi),fji。

11、二、尋找最大流的標(biāo)號(hào)法二、尋找最大流的標(biāo)號(hào)法(Ford Fulkerson) 思想:從一可行流出發(fā),檢查關(guān)于此流是否思想:從一可行流出發(fā),檢查關(guān)于此流是否存在增廣鏈。若存在增廣鏈,則增大流存在增廣鏈。若存在增廣鏈,則增大流量,使此量,使此鏈變?yōu)榉窃鰪V鏈;這時(shí)再檢查是非還有增廣鏈,鏈變?yōu)榉窃鰪V鏈;這時(shí)再檢查是非還有增廣鏈,若還有,繼續(xù)調(diào)整,直至不存在增廣鏈為止。若還有,繼續(xù)調(diào)整,直至不存在增廣鏈為止。第25頁/共33頁2022-6-15 3、若標(biāo)號(hào)延續(xù)到、若標(biāo)號(hào)延續(xù)到vt,表明得到一條從,表明得到一條從vs到到vt的增的增廣鏈廣鏈 ,轉(zhuǎn)入調(diào)整階段,轉(zhuǎn)入調(diào)整階段4,否則當(dāng)前流即為最大流。,否則當(dāng)前

12、流即為最大流。4、調(diào)整過程、調(diào)整過程令調(diào)整量為令調(diào)整量為 = l(vt)令令 fij+ (vi,vj)+ fij = fij (vi,vj) fij (vi,vj)去掉所有的標(biāo)號(hào),對(duì)新的可行流去掉所有的標(biāo)號(hào),對(duì)新的可行流f =fij ,重新進(jìn),重新進(jìn)入標(biāo)號(hào)過程。入標(biāo)號(hào)過程。第26頁/共33頁2022-6-15可結(jié)合下圖理解其實(shí)際涵義??山Y(jié)合下圖理解其實(shí)際涵義。vsv1v2v3v4vt(4,4)(8,1)(4,3)(2,2)(4,0)(2,2)(1,1)(7,2)(9,2)第27頁/共33頁2022-6-15vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2

13、,1)(6,3)(7,7)例例 求下列網(wǎng)絡(luò)的最大流與最小截集。求下列網(wǎng)絡(luò)的最大流與最小截集。解解一、標(biāo)號(hào)過程一、標(biāo)號(hào)過程 (2)檢查)檢查vs,在弧在弧(vs,v1)上上,fs1=7,cs1=9,fs1cs1,則則v1的標(biāo)號(hào)為的標(biāo)號(hào)為(vs,l(v1),其中,其中第28頁/共33頁2022-6-15l(v1)=minl(vs),cs1fs1=min+ ,9 2=2(3)檢查)檢查v1,在弧在弧(v1,v4)上上,f14=7,c14=9,f140,則則v3的標(biāo)號(hào)為的標(biāo)號(hào)為(-v4, l(v3),其中,其中l(wèi)(v3)=minl(v4),f34=min2,1=1(5)檢查)檢查v3,在弧在弧(v3,

14、vt)上上,f3t=3,c3t=6,f3tc3t,第29頁/共33頁2022-6-15則則vt的標(biāo)號(hào)為的標(biāo)號(hào)為(v3,l(vt),其中,其中l(wèi)(vt)=minl(v3),c3tf3t=min1,6-3=1這樣,我們得到了一增廣鏈這樣,我們得到了一增廣鏈 ,如圖所示。如圖所示。vsv1vtv4v2v3(9,7)(5,3)(3,2)(4,4)(5,5)(3,1)(2,1)(6,3)(7,7)(0, )(vs,2)(v1,2)(-v4,1)(v3,1)其中其中 +=(vs,v1),(v1,v4),(v3,vt), =(v3,v4)第30頁/共33頁2022-6-15二、調(diào)整過程二、調(diào)整過程取調(diào)整量為

15、取調(diào)整量為 =1,在,在 上調(diào)整上調(diào)整f。在在 +上:上: fs1+ =7+1=8 f14+ =2+1=3 f4t+ =5+1=6在在 上:上: f43 =11=0其余弧上的流量不變,這樣得到一個(gè)新的流,如下圖所示。其余弧上的流量不變,這樣得到一個(gè)新的流,如下圖所示。s1vtv4v23(9,8)(5,3)(3,2)(5,5)(3,2)(2,0)(6,4)(7,7)第31頁/共33頁2022-6-15 在上圖中重復(fù)上述標(biāo)號(hào)過程,依次給在上圖中重復(fù)上述標(biāo)號(hào)過程,依次給vs,v2,v1,v4標(biāo)號(hào)標(biāo)號(hào)后,由于標(biāo)號(hào)無法繼續(xù)下去,算法結(jié)束。這時(shí)的流為最后,由于標(biāo)號(hào)無法繼續(xù)下去,算法結(jié)束。這時(shí)的流為最大流,最大流的流量為大流,最大流的流量為vvv(4,4)v(f)=8+3=11 與此同時(shí),可找到最小截集與此同時(shí),可找到最小截集(V1,V1),其中,其中V1為標(biāo)號(hào)點(diǎn)為標(biāo)號(hào)點(diǎn)集合,集合,V1為未標(biāo)號(hào)點(diǎn)集合,弧集合為未標(biāo)號(hào)點(diǎn)集合,弧集合(V1,V1) 即為最小截集。即為最小截集。此例中,此例中, V1=vs,v2,v1,v4, V1=v3,vt,(V1,V1)=(v1,v3), (v4,vt)第32頁/共33頁

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!