歡迎來(lái)到裝配圖網(wǎng)! | 幫助中心 裝配圖網(wǎng)zhuangpeitu.com!
裝配圖網(wǎng)
ImageVerifierCode 換一換
首頁(yè) 裝配圖網(wǎng) > 資源分類 > PPT文檔下載  

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

  • 資源ID:3257496       資源大小:1.83MB        全文頁(yè)數(shù):167頁(yè)
  • 資源格式: PPT        下載積分:14.9積分
快捷下載 游客一鍵下載
會(huì)員登錄下載
微信登錄下載
三方登錄下載: 微信開放平臺(tái)登錄 支付寶登錄   QQ登錄   微博登錄  
二維碼
微信掃一掃登錄
下載資源需要14.9積分
郵箱/手機(jī):
溫馨提示:
用戶名和密碼都是您填寫的郵箱或者手機(jī)號(hào),方便查詢和重復(fù)下載(系統(tǒng)自動(dòng)生成)
支付方式: 支付寶    微信支付   
驗(yàn)證碼:   換一換

 
賬號(hào):
密碼:
驗(yàn)證碼:   換一換
  忘記密碼?
    
友情提示
2、PDF文件下載后,可能會(huì)被瀏覽器默認(rèn)打開,此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁(yè)到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請(qǐng)使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無(wú)水印,預(yù)覽文檔經(jīng)過(guò)壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒有明確說(shuō)明有答案則都視為沒有答案,請(qǐng)知曉。

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

第八章圖與網(wǎng)絡(luò)分析,主要內(nèi)容:8.1圖的基本概念與基本定理8.2樹和最小支撐樹8.3最短路問(wèn)題8.4最小費(fèi)用流問(wèn)題8.5最大流問(wèn)題8.6網(wǎng)絡(luò)計(jì)劃8.7中國(guó)郵遞員問(wèn)題8.7指派問(wèn)題,8.1圖的基本概念與基本定理,圖論是應(yīng)用非常廣泛的運(yùn)籌學(xué)分支,它已經(jīng)廣泛地應(yīng)用于物理學(xué)控制論,信息論,工程技術(shù),交通運(yùn)輸,經(jīng)濟(jì)管理,電子計(jì)算機(jī)等各項(xiàng)領(lǐng)域。對(duì)于科學(xué)研究,市場(chǎng)和社會(huì)生活中的許多問(wèn)題,可以同圖論的理論和方法來(lái)加以解決。例如,各種通信線路的架設(shè),輸油管道的鋪設(shè),鐵路或者公路交通網(wǎng)絡(luò)的合理布局等問(wèn)題,都可以應(yīng)用圖論的方法,簡(jiǎn)便、快捷地加以解決。,隨著科學(xué)技術(shù)的進(jìn)步,特別是電子計(jì)算機(jī)技術(shù)的發(fā)展,圖論的理論獲得了更進(jìn)一步的發(fā)展,應(yīng)用更加廣泛。如果將復(fù)雜的工程系統(tǒng)和管理問(wèn)題用圖的理論加以描述,可以解決許多工程項(xiàng)目和管理決策的最優(yōu)問(wèn)題。因此,圖論越來(lái)越受到工程技術(shù)人員和經(jīng)營(yíng)管理人員的重視。,關(guān)于圖的第一篇論文是瑞士數(shù)學(xué)家歐拉(E.Euler)在1736年發(fā)表的解決“哥尼,斯堡”七橋難題的論文;,德國(guó)的哥尼斯堡城有一條普雷格爾河,河中有兩個(gè)島嶼,河的兩岸和島嶼之間有七座橋相互連接,(見圖8.1a)當(dāng)?shù)氐木用駸嶂杂谶@樣一個(gè)問(wèn)題,一個(gè)漫步者如何能夠走過(guò)這七座橋,并且每座橋只能走過(guò)一次,最終回到原出發(fā)地。盡管試驗(yàn)者很多,但是都沒有成功。為了尋找答案,1736年歐拉將這個(gè)問(wèn)題抽象成圖8.1b所示圖形的一筆畫問(wèn)題。,哥尼斯堡七橋問(wèn)題,圖8.1a,A,B,C,D,哥尼斯堡七橋問(wèn)題可簡(jiǎn)化為以下圖形其中的四個(gè)頂點(diǎn)都是奇頂點(diǎn),A,B,C,D,圖8.1b,即能否從某一點(diǎn)開始不重復(fù)地一筆畫出這個(gè)圖形,最終回到原點(diǎn)。歐拉在他的論文中證明了這是不可能的,因?yàn)檫@個(gè)圖形中每一個(gè)頂點(diǎn)都與奇數(shù)條邊相連接,不可能將它一筆畫出,這就是古典圖論中的第一個(gè)著名問(wèn)題。,在實(shí)際的生產(chǎn)和生活中,人們?yōu)榱朔从呈挛镏g的關(guān)系,常常在紙上用點(diǎn)和線來(lái)畫出各式各樣的示意圖。,例8.1圖8.2是我國(guó)北京、上海、重慶等十四個(gè)城市之間的鐵路交通圖,這里用點(diǎn)表示城市,用點(diǎn)與點(diǎn)之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管道圖,民用航空線圖等等。,圖8.2,例8.2有六支球隊(duì)進(jìn)行足球比賽,我們分別用點(diǎn)v1,v6表示這六支球隊(duì),它們之間的比賽情況,也可以用圖反映出來(lái),已知v1隊(duì)?wèi)?zhàn)勝v2隊(duì),v2隊(duì)?wèi)?zhàn)勝v3隊(duì),v3隊(duì)?wèi)?zhàn)勝v5隊(duì),如此等等。這個(gè)勝負(fù)情況,可以用圖8.3所示的有向圖反映出來(lái),圖8.3,從以上的幾個(gè)例子可以看出,我們用點(diǎn)和點(diǎn)之間的線所構(gòu)成的圖,反映實(shí)際生產(chǎn)和生活中的某些特定對(duì)象之間的特定關(guān)系。一般來(lái)說(shuō),通常用點(diǎn)表示研究對(duì)象,用點(diǎn)與點(diǎn)之間的線表示研究對(duì)象之間的特定關(guān)系。由于在一般情況下,圖中的相對(duì)位置如何,點(diǎn)與點(diǎn)之間線的長(zhǎng)短曲直,對(duì)于反映研究對(duì)象之間的關(guān)系,顯的并不重要,因此,圖論中的圖與幾何圖,工程圖等本質(zhì)上是不同的。,綜上所述,圖論中的圖是由點(diǎn)和點(diǎn)與點(diǎn)之間的線所組成的。通常,我們把點(diǎn)與點(diǎn)之間不帶箭頭的線叫做邊,帶箭頭的線叫做弧。如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的,那么,稱為無(wú)向圖,記作G=(V,E),其中V表示圖G的點(diǎn)集合,E表示圖G的邊集合。連接點(diǎn)vi,vjV的邊記作vi,vj,或者vj,vi。如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的,那么稱為它為有向圖,記作D=(V,A),其中V表示有向圖D的點(diǎn)集合,A表示有向圖D的弧集合。一條方向從vi指向vj的弧,記作(vi,vj)。,例如.圖8.4是一個(gè)無(wú)向圖G=(V,E),其中V=v1,v2,v3,v4E=v1,v2,v2,v1,v2,v3,v3,v4,v1,v4,v2,v4,v3,v3,圖8.4,圖8.5是一個(gè)有向圖D=(V,A)其中V=v1,v2,v3,v4,v5,v6,v7A=(v1,v2),(v1,v3),(v3,v2)(v3,v4),(v2,v4),(v4,v5),(v4,v6),(v5,v3),(v5,v4),(v5,v6),(v6,v7),圖8.5,下面介紹一些常用的名詞:一個(gè)圖G或有向圖D中的點(diǎn)數(shù),記作P(G)或P(D),簡(jiǎn)記作P,邊數(shù)或者弧數(shù),記作q(G)或者q(D),簡(jiǎn)記作q。如果邊vi,vjE,那么稱vi,vj是邊的端點(diǎn),或者vi,vj是相鄰的。如果一個(gè)圖G中,一條邊的兩個(gè)端點(diǎn)是相同的,那么稱為這條邊是環(huán),如圖8.4中的邊v3,v3是環(huán)。如果兩個(gè)端點(diǎn)之間有兩條以上的邊,那么稱為它們?yōu)槎嘀剡?,如圖8.4中的邊v1,v2,v2,v1。一個(gè)無(wú)環(huán),無(wú)多重邊的圖稱為簡(jiǎn)單圖,一個(gè)無(wú)環(huán),有多重邊的圖稱為多重圖。,以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)v的度,記作d(v),如圖84中d(v1)=3,d(v2)=4,d(v3)=4,d(v4)=3。度為零的點(diǎn)稱為弧立點(diǎn),度為1的點(diǎn)稱為懸掛點(diǎn)。懸掛點(diǎn)的邊稱為懸掛邊。度為奇數(shù)的點(diǎn)稱為奇點(diǎn),度為偶數(shù)的點(diǎn)稱為偶點(diǎn)。端點(diǎn)的度d(v):點(diǎn)v作為端點(diǎn)的邊的個(gè)數(shù)奇點(diǎn):d(v)=奇數(shù);,偶點(diǎn):d(v)=偶數(shù);懸掛點(diǎn):d(v)=1;懸掛邊:與懸掛點(diǎn)連接的邊;孤立點(diǎn):d(v)=0;空?qǐng)D:E=,無(wú)邊圖,V=v1,v2,v3,v4,v5,v6,v7,d(v1)=3;d(v2)=5;,d(v3)=4;d(v4)=4;,d(v5)=1;d(v6)=3;,d(v7)=0,其中v5為懸掛點(diǎn),v7為孤立點(diǎn)。,定理8.1所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的2倍。證明:因?yàn)樵谟?jì)算各個(gè)點(diǎn)的度時(shí),每條邊被它的兩個(gè)端點(diǎn)個(gè)用了一次。,定理8.2在任一圖中,奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。證明:設(shè)V1,V2分別是圖G中奇點(diǎn)和偶點(diǎn)的集合,由定理8.1,有,因?yàn)槭桥紨?shù),也是偶數(shù),因此,也必是偶數(shù),從而V1中的點(diǎn)數(shù)是偶數(shù)。,圖的連通性:鏈:由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列。如:v0,e1,v1,e2,v2,e3,v3,vn-1,en,vn;v0,vn分別為鏈的起點(diǎn)和終點(diǎn)。記作(v0,v1,v2,,v3,vn-1,vn)簡(jiǎn)單鏈:鏈中所含的邊均不相同;初等鏈:鏈中所含的點(diǎn)均不相同,也稱通路;,圈:若v0vn則稱該鏈為開鏈,否則稱為閉鏈或回路或圈;,簡(jiǎn)單圈:如果在一個(gè)圈中所含的邊均不相同初等圈:除起點(diǎn)和終點(diǎn)外鏈中所含的點(diǎn)均不相同的圈;連通圖:圖中任意兩點(diǎn)之間均至少有一條通路,否則稱為不連通圖。,初等鏈:(v1,v2,v3,v6,v7,v5),初等圈:(v1,v2,v3,v5,v4,v1),簡(jiǎn)單圈:(v4,v1,v2,v3,v5,v7,v6,v3,v4),簡(jiǎn)單鏈:(v1,v2,v3,v4,v5,v3),以后除特別聲明,均指初等鏈和初等圈。,連通圖,子圖定義:如果V2V1,E2E1稱G2是G1的子圖;真子圖:如果V2V1,E2E1稱G2是G1的真子圖;部分圖:如果V2=V1,E2E1稱G2是G1的部分圖或支撐子圖;導(dǎo)出子圖:如果V2V1,E2=vi,vjvi,vjV2,稱G2是G1中由V2導(dǎo)出的導(dǎo)出子圖。,設(shè)G1=V1,E1,G2=V2,E2,G1,G2真子圖,G3子圖部分圖,G4導(dǎo)出子圖,G5生成樹,G6G5余樹,有向圖:關(guān)聯(lián)邊有方向弧:有向圖的邊a=(u,v),起點(diǎn)u,終點(diǎn)v;路:若有從u到v不考慮方向的鏈,且各方向一致,則稱之為從u到v的路;初等路:各頂點(diǎn)都不相同的路;初等回路:u=v的初等路;連通圖:若不考慮方向是無(wú)向連通圖;強(qiáng)連通圖:任兩點(diǎn)有路;,8.2樹和最小支撐樹,一、樹及其性質(zhì)在各種各樣的圖中,有一類圖是十分簡(jiǎn)單又非常具有應(yīng)用價(jià)值的圖,這就是樹。例8.3已知有六個(gè)城市,它們之間要架設(shè)電話線,要求任意兩個(gè)城市均可以互相通話,并且電話線的總長(zhǎng)度最短。,如果用六個(gè)點(diǎn)v1v6代表這六個(gè)城市,在任意兩個(gè)城市之間架設(shè)電話線,即在相應(yīng)的兩個(gè)點(diǎn)之間連一條邊。這樣,六個(gè)城市的一個(gè)電話網(wǎng)就作成一個(gè)圖。表示任意兩個(gè)城市之間均可以通話,這個(gè)圖必須是連通圖。并且,這個(gè)圖必須是無(wú)圈的。否則,從圈上任意去掉一條邊,剩下的圖仍然是六個(gè)城市的一個(gè)電話網(wǎng)。圖8.8是一個(gè)不含圈的連通圖,代表了一個(gè)電話線網(wǎng)。,圖8.8,v6,v3,v4,v2,v5,v1,定義8.1一個(gè)無(wú)圈的連通圖叫做樹。下面介紹樹的一些重要性質(zhì):定理8.3設(shè)圖G=(V,E)是一個(gè)樹P(G)2,那么圖G中至少有兩個(gè)懸掛點(diǎn)。定理8.4圖G=(V,E)是一個(gè)樹的充要條件是G不含圈,并且有且僅有P-1條邊。定理8.5圖G=(V,E)是一個(gè)樹的充要條件是G是連通圖,并且有且僅有p1條邊。定理8.6圖G是一個(gè)樹的充分必要條件是任意兩個(gè)頂點(diǎn)之間有且僅有一條鏈。,從以上定理,不難得出以下結(jié)論:(1)從一個(gè)樹中任意去掉一條邊,那么剩下的圖不是連通圖,亦即,在點(diǎn)集合相同的圖中,樹是含邊數(shù)最少的連通圖。(2)在樹中不相鄰的兩個(gè)點(diǎn)之間加上一條邊,那么恰好得到一個(gè)圈。,二.支撐樹,定義8.2設(shè)圖K=(V,EI)是圖G=(V,E)的,一支撐子圖,如果圖K=(V,EI)是一個(gè)樹,那么稱K是G的一個(gè)支撐樹。例如,圖8.10b是圖8.10a的一個(gè)支撐樹,圖8.10,顯然,如果圖K=(V,EI)是圖G=(V,E)的一個(gè)支撐樹,那么K的邊數(shù)是p(G)-1,G中不屬于支撐樹K的邊數(shù)是q(G)-p(G)+1。定理8.7一個(gè)圖G有支撐樹的充要條件是G是連通圖。證明:充分性:設(shè)圖G是連通的,若G不含圈,則按照定義,G是一個(gè)樹,從而G是自身的一個(gè)支撐樹。若G含圈,則任取G的,一個(gè)圈,從該圈中任意去掉一條邊,得到圖G的一支撐子圖G1。若G1不含圈,則G1是G的一個(gè)支撐樹。若G1仍然含圈,則任取G1的一個(gè)圈,再?gòu)娜χ腥我馊サ粢粭l邊,得到圖G的一支撐子圖G2。依此類推,可以得到圖G的一個(gè)支撐子圖GK,且不含圈,從而GK是一個(gè)支撐樹。,定理8.7充分性的證明,提供了一個(gè)尋找連通圖支撐樹的方法叫做“破圈法”。就是從圖中任取一個(gè)圈,去掉一條邊。再對(duì)剩下的圖重復(fù)以上步驟,直到不含圈時(shí)為止,這樣就得到一個(gè)支撐樹。例8.4用破圈法求出圖8-11的一個(gè)支撐樹。,圖8-11,取一個(gè)圈(v1,v2,v3,v1),在一個(gè)圈中去掉邊e3。在剩下的圖中,再取一個(gè)圈(v1,v2,v4,v3,v1),去掉邊e4。再?gòu)娜Γ╲3,v4v5,v3)中去掉邊e6。再?gòu)娜?v1,v2,v5,v4,v3,v1)中去掉邊e7,這樣,剩下的圖不含圈,于是得到一個(gè)支撐樹,如圖8.12所示。,圖8.12,三.最小支撐樹問(wèn)題定義8.3如果圖G=(V,E),對(duì)于G中的每一條邊vi,vj,相應(yīng)地有一個(gè)數(shù)Wij,那么稱這樣的圖G為賦權(quán)圖,Wij稱為邊vi,vj的權(quán)。這里所指的權(quán),是具有廣義的數(shù)量值。根據(jù)實(shí)際研究問(wèn)題的不同,可以具有不同的含義。例如長(zhǎng)度,費(fèi)用、流量等等。賦權(quán)圖在圖論及實(shí)際應(yīng)用方面有著重要的地位,被廣泛應(yīng)用于現(xiàn)代科學(xué)管理和工程技術(shù)等領(lǐng)域,最小支撐樹問(wèn)題就是賦權(quán)圖的最優(yōu)化問(wèn)題之一。,設(shè)G=(V,E)是一個(gè)連通圖,G的每一條vi,vj對(duì)應(yīng)一個(gè)非負(fù)的權(quán)Wij。定義8.4如果圖T=(V,EI)是圖G的一個(gè)支撐樹,那么稱EI上所有邊的權(quán)的和為支撐樹T的權(quán),記作S(T)。如果圖G的支撐樹T*的權(quán)S(T*),在G的所有支撐樹T中的權(quán)最小,即S(T*)=minTS(T),那么稱T*是G的最小支撐樹。,如前所述,在已知的幾個(gè)城市之間聯(lián)結(jié)電話線網(wǎng),要求總長(zhǎng)度最短和總建設(shè)費(fèi)用最少,一個(gè)問(wèn)題的解決可以歸結(jié)為最小支撐樹問(wèn)題。再如,城市間交通線的建造等,都可以歸結(jié)為這一類問(wèn)題。,下面介紹尋求最小支撐樹的方法-破圈法。在給定的連通圖中任取一個(gè)圈,去掉權(quán)最大的一條邊,如果有兩條以上權(quán)最大的邊,則任意,去掉一條。在剩下的圖中,重復(fù)以上步驟,直到得到一個(gè)不含圈的連通圖為止,這個(gè)圖便是最小支撐樹。例8.5某六個(gè)城市之間的道路網(wǎng)如圖8.13a所示,要求沿著已知長(zhǎng)度的道路聯(lián)結(jié)六個(gè)城市的電話線網(wǎng),使得電話線的總長(zhǎng)度最短。,圖8.13a,圖8.13b,解:這個(gè)問(wèn)題的解決就是要求所示賦權(quán)圖8.13a中的最小支撐樹。用破圈法求解。任取一個(gè)圈,例如(v1,v2,v3,v1),去掉這個(gè)圈中權(quán)最大的邊v1,v3。再取一個(gè)圈(v3,v5,v2,v3),去掉邊v2,v5。再取一個(gè)圈(v3,v5,v4,v2,v3),去掉邊v3,v5。再取一個(gè)圈(v5,v6,v4,v5),這個(gè)圈中,有兩條權(quán)最大的邊v5,v6和v4,v6。任意去掉其中的一條,例如v5,v6。這時(shí)得到一個(gè),不含圈的圖,如圖8.13b所示,即是最小支撐樹。關(guān)于破圈法正確性的證明略去。,例用破圈法求出下圖中的最小支撐樹,破圈法和生長(zhǎng)法兩個(gè)方法:,(1)在網(wǎng)絡(luò)圖中尋找一個(gè)圈。若不存在圈,則已經(jīng)得到最短樹或網(wǎng)絡(luò)不存在最短樹;,(2)去掉該圈中權(quán)數(shù)最大的邊;,反復(fù)重復(fù)兩步,直到最短樹。,1.破圈法,從網(wǎng)絡(luò)圖中任意節(jié)點(diǎn)開始尋找與該節(jié)點(diǎn)關(guān)聯(lián)的權(quán)數(shù)最小的邊,得到另一節(jié)點(diǎn)后,再?gòu)倪@個(gè)新節(jié)點(diǎn)開始尋找與該節(jié)點(diǎn)關(guān)聯(lián)的權(quán)數(shù)最小的另一邊。注意尋找過(guò)程中,節(jié)點(diǎn)不得重復(fù),即在找最小權(quán)數(shù)邊時(shí)不考慮已選過(guò)的邊,反復(fù)進(jìn)行,直到得到最短樹或證明網(wǎng)絡(luò)不存在最短樹。,2.成長(zhǎng)法,例用成長(zhǎng)法求出下圖中的最小支撐樹(最短樹),一.引言最短路徑問(wèn)題是圖論中十分重要的最優(yōu)化問(wèn)題之一,它作為一個(gè)經(jīng)常被用到的基本工具,可以解決生產(chǎn)實(shí)際中的許多問(wèn)題,比如城市中的管道鋪設(shè),線路安排,工廠布局,設(shè)備更新等等。也可以用于解決其它的最優(yōu)化問(wèn)題。,8.3最短路問(wèn)題,例86如圖8.14所示的單行線交通網(wǎng),每個(gè)弧旁邊的數(shù)字表示這條單行線的長(zhǎng)度?,F(xiàn)在有一個(gè)人要從v1出發(fā),經(jīng)過(guò)這個(gè)交通網(wǎng)到達(dá)v8,要尋求是總路程最短的線路。,圖8.14,1,從v1到v8的路線是很多的。比如從v1出發(fā),經(jīng)過(guò)v2,v5到達(dá)v8或者從v1出發(fā),經(jīng)過(guò)v4,v6,v7到達(dá)v8等等。但不同的路線,經(jīng)過(guò)的總長(zhǎng)度是不同的。例如,按照第一個(gè)線路,總長(zhǎng)度是6+1+6=13單位,按照第二個(gè)路線,總長(zhǎng)度是1+10+2+4=17單位。從這個(gè)例子中,可以給出一般意義下的最短路問(wèn)題。設(shè)一個(gè)賦權(quán)有向圖D=(V,A),,對(duì)于每一個(gè)弧a=(vi,vj),相應(yīng)地有一個(gè)權(quán)wij。Vs,vt是D中的兩個(gè)頂點(diǎn),P是D中從vs到vt的任意一條路,定義路的權(quán)是P中所有弧的權(quán)的和,記作S(p)。最短路問(wèn)題就是要在所有從vs到vt的路P0中,尋找一個(gè)權(quán)最小的路P0,亦即S(P0)=minS(p)。P0叫做從vs到vs的最短路。P0的權(quán)S(P0)叫做從vs到vt的距離,記作d(vs,vt)。由于D是有向圖,很明顯d(vs,vt)與d(vt,vs)一般不相等。,二.Dijkstra算法下面介紹在一個(gè)賦權(quán)有向圖中尋求最短路的方法Dijkstra算法,它是在1959年提出來(lái)的。目前公認(rèn),在所有的權(quán)wij0時(shí),這個(gè)算法是尋求最短路問(wèn)題最好的算法。并且,這個(gè)算法實(shí)際上也給出了尋求從一個(gè)始定點(diǎn)vs到任意一個(gè)點(diǎn)vj的最短路。,Dijkstra算法的基本思想是從vs出發(fā),逐步向外尋找最短路。在運(yùn)算過(guò)程中,與每個(gè)點(diǎn)對(duì)應(yīng),記錄一個(gè)數(shù),叫做一個(gè)點(diǎn)的標(biāo)號(hào)。它或者表示從vs到該點(diǎn)的最短路權(quán)(叫做P標(biāo)號(hào)),或者表示從vs到該點(diǎn)最短路權(quán)的上界(叫做T標(biāo)號(hào))。算法的每一步是去修改T標(biāo)號(hào),把某一個(gè)具有T標(biāo)號(hào)的點(diǎn)改變?yōu)榫哂蠵標(biāo)號(hào)的點(diǎn),使圖D中具有P標(biāo)號(hào)的頂點(diǎn)多一個(gè)。這樣,至多經(jīng)過(guò)P-1步,就可求出從vs到各點(diǎn)vj的最短路。,以例1為例說(shuō)明這個(gè)基本思想。在例1中,S=1。因?yàn)閃ij0,d(v1,v1)=0。這時(shí),v1是具有P標(biāo)號(hào)的點(diǎn)。現(xiàn)在看從v1出發(fā)的三條?。╲1,v2),(v1,v3)和(v1,v4)。如果一個(gè)人從v1出發(fā)沿(v1,v2)到達(dá)v2,這時(shí)的路程是d(v1,v1)+w12=6單位。如果從v1出發(fā),沿(v1,v3)到達(dá)v3,則是d(v1,v1)+w13=3單位。同理,沿(v1,v4)到達(dá)v4,是d(v1,v1)+w14=1單位。因此,他從v1出發(fā)到達(dá)v4的最短路必是(v1,v4),d(v1,v4)=1。,這是因?yàn)閺膙1到達(dá)v4的任一條路P,假如不是(v1,v4),則必先沿(v1,v2)到達(dá)v2,或者沿(v1,v3)到達(dá)v3,而這時(shí)的路程已是6或者3單位。由于所有的權(quán)wij0,因此,不論他如何再?gòu)膙2或者v3到達(dá)v4,所經(jīng)過(guò)的總路程都不會(huì)比1少,于是就有d(v1,v4)=1。這樣就使v4變成具有P標(biāo)號(hào)的點(diǎn)?,F(xiàn)在看從v1和v4指向其余點(diǎn)的弧。如上所述,從v1出發(fā),分別沿(v1,v2),(v1,v3)到達(dá)v2,v3,經(jīng)過(guò),的路程是6或者3單位。從v4出發(fā)沿(v4,v6)到達(dá)v6,經(jīng)過(guò)的路程是d(v1,v4)+w46=1+10=11單位。而mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46=d(v1,v1)+w13=3單位。根據(jù)同樣的理由,可以斷定,從v1到達(dá)v3的最短路是(v1,v3),d(v1,v3)=3。這樣,又使點(diǎn)v3變?yōu)榫哂蠵標(biāo)號(hào)的點(diǎn),不斷重復(fù)以上過(guò)程,就可以求出從vs到達(dá)任一點(diǎn)vj的最短路。,(0,0),(6,1),(3,1),(1,1),(0,0),(3,1),(1,1),(6,1),(11,4),(0,0),(3,1),(1,1),(5,3),(11,4),(0,0),(3,1),(1,1),(5,3),(11,4),(6,2),(0,0),(3,1),(1,1),(5,3),(10,5),(6,2),(9,5),(12,5),(0,0),(3,1),(1,1),(5,2),(10,5),(6,2),(9,5),(12,5),(0,0),(3,1),(1,1),(5,2),(10,5),(6,2),(9,5),(12,5),從v1到v8的最短路的長(zhǎng)度為:12從v1到v8的最短路線為:,v8,v5,v2,v1,步驟:,1、給起點(diǎn)一個(gè)永久標(biāo)號(hào)(0,0)。永久標(biāo)號(hào)用下劃線表示;標(biāo)號(hào)中的第一個(gè)數(shù)表示從起點(diǎn)到該點(diǎn)的距離;第二個(gè)數(shù)表示該點(diǎn)的前面沒有點(diǎn)了。,2、修改非永久標(biāo)號(hào)點(diǎn)vi的臨時(shí)標(biāo)號(hào)為(a,b),其中a為以vi為終點(diǎn)的弧,如果其起點(diǎn)為永久標(biāo)號(hào),則求其永久標(biāo)號(hào)的第一個(gè)數(shù)與弧長(zhǎng)的和,如果這樣的和有多個(gè),則取最小值。b為前一個(gè)點(diǎn)的下標(biāo)。,3、在臨時(shí)標(biāo)號(hào)中取第一個(gè)標(biāo)號(hào)的最小值,將該標(biāo)號(hào)該為永久標(biāo)號(hào),再返回到2步,三、含有負(fù)權(quán)的最短路的求法,例:求從v1到v8的最短路,0,-1,-2,3,0,-5,-2,-7,1,-1,5,0,-5,-2,-7,-3,-1,-5,6,0,-5,-2,-7,-3,-1,-5,6,從v1到v8的最短路的長(zhǎng)度為:6從v1到v8的最短路線為:,v8,v6,v3,v1,8.4最小費(fèi)用流問(wèn)題,一引言在許多實(shí)際的網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問(wèn)題。例如鐵路運(yùn)輸系統(tǒng)中的車輛流,城市給排水系統(tǒng)的水流問(wèn)題等等。而網(wǎng)絡(luò)系統(tǒng)流最大流問(wèn)題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問(wèn)題,它對(duì)于解決生產(chǎn)實(shí)際問(wèn)題起著十分重要的作用。,圖8.19是聯(lián)結(jié)某個(gè)起始地vs和目的地vt的交通運(yùn)輸網(wǎng),每一條弧vi旁邊的權(quán)cij表示這段運(yùn)輸線的最大通過(guò)能力,貨物經(jīng)過(guò)交通崗從vs運(yùn)送到vt.要求指定一個(gè)運(yùn)輸方案,使得從vs到vt的貨運(yùn)量最大,這個(gè)問(wèn)題就是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問(wèn)題。,問(wèn)題描述連通網(wǎng)絡(luò)G(V,A)有m個(gè)節(jié)點(diǎn),n條弧,弧eij上的流量上界為cij,求從起始節(jié)點(diǎn)vs到終點(diǎn)vt的最大流量。,圖8.19,二基本概念定義8.5設(shè)一個(gè)賦權(quán)有向圖D=(V,A),在V中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt,其它的點(diǎn)叫做中間點(diǎn)。對(duì)于D中的每一個(gè)?。╲i,vj)A,都有一個(gè)權(quán)叫做弧的容量。我們把這樣的圖D叫做一個(gè)網(wǎng)絡(luò)系統(tǒng),簡(jiǎn)稱網(wǎng)絡(luò),記做D=(V,A,C)。網(wǎng)絡(luò)D上的流,是指定義在弧集合A上的一個(gè)函數(shù)f=f(vi,vj)=fjjf(vi,vj)=fij叫做弧(vi,vj)上的流量。,例如圖8.19就是一個(gè)網(wǎng)絡(luò)。每一個(gè)弧旁邊的權(quán)就是對(duì)應(yīng)的容量(最大通過(guò)能力)cij.圖8.20表示的就是這個(gè)網(wǎng)絡(luò)上的一個(gè)流(運(yùn)輸方案),每一個(gè)弧上的流量fij就是運(yùn)輸量。例如fs1=5,fs2=3,f13=2等等。對(duì)于實(shí)際的網(wǎng)絡(luò)系統(tǒng)上的流,有幾個(gè)顯著的特點(diǎn):(1)發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必相等。(2)每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零。(3)每一個(gè)弧上的流量,不能超過(guò)它的最大通過(guò)能力(即容量)于是有:,圖8.20,定義8.6網(wǎng)絡(luò)上的一個(gè)流f叫做可行流,如果f滿足以下條件(1)容量條件:對(duì)于每一個(gè)?。╲i,vj)A,有0fijcij.(2)平衡條件:,對(duì)于發(fā)點(diǎn)vs,有,對(duì)于收點(diǎn)vt,有,對(duì)于中間點(diǎn),有,任意一個(gè)網(wǎng)絡(luò)上的可行流總是存在的。例如零流v(f)=0,就是滿足以上條件的可行流。網(wǎng)絡(luò)系統(tǒng)中最大流問(wèn)題就是在給定的網(wǎng)絡(luò)上尋求一個(gè)可行流f,其流量v(f)達(dá)到最大值。設(shè)流f=fij是網(wǎng)絡(luò)D上的一個(gè)可行流。我們把D中fij=cij的弧叫做飽和弧,fij0的弧為非零流弧,fij=0的弧叫做零流弧.,在圖8.20中,(v4,v3)是飽和弧,其他的弧是非飽和弧,并且都是非零流弧。設(shè)是網(wǎng)絡(luò)D中連接發(fā)點(diǎn)s和收點(diǎn)vt的一條鏈。定義鏈的方向是從s到vt,于是鏈上的弧被分為兩類:一類是弧的方向與鏈的方向相同,叫做前向弧,前向弧的集合記做+。二類是弧的方向與鏈的方向相反,叫做后向弧,,后向弧的集合記做。例如在圖8.19中,在鏈(vs,v1,v2,v3,v4,vt)中,+=vs,v1,(v1,v2),(v2,v3),(v4,vt),=(v4,v3).,增廣鏈:如果鏈滿足以下條件:1在弧(vi,vj)+上,有0fij<cij,即+中的每一條弧是非飽和弧。2在?。╲i,vj)上,有0<fijcij,即中的每一條弧是非零流弧。,例如在圖8.20中,鏈=(vs,v1,v2,v3,v4,vt)就是一條增廣鏈。設(shè)圖D=(V,A,C),點(diǎn)集S,TV,ST=。將起點(diǎn)在S,終點(diǎn)在T的所有弧作成集合,記做(S,T)。,定義8.8設(shè)一個(gè)網(wǎng)絡(luò)D=(V,A,C)。如果點(diǎn)集V被剖分為兩個(gè)非空集合v1和,發(fā)點(diǎn)vsv1,收點(diǎn)vt,那么將弧集(v1,)叫做是分離vs和vt的截集。,定義8.9設(shè)一個(gè)截集(V1,).將階截集(V1,)中所有的弧的容量的和叫做截集的截量,記做s(V1,),亦即,下面的事實(shí)是顯然的:一個(gè)網(wǎng)絡(luò)D中,任何一個(gè)可行流f的流量v(f)都小于或等于這個(gè)網(wǎng)絡(luò)中任何一個(gè)截集(V1,)的截量。并且,如果,網(wǎng)絡(luò)上的一個(gè)可行流f*和網(wǎng)絡(luò)中的一個(gè)截集(V1*,),滿足條件v*(f*)=c(V1*,),那么f*一定是D上的最大流,而(V1*,)一定是D的所有的截集中截量最小的一個(gè)(即最小截集),定理8.8網(wǎng)絡(luò)中的一個(gè)可行流f*是最大流的充分必要條件是,不存在關(guān)于f*的增廣鏈。定理8.9在一個(gè)網(wǎng)絡(luò)D中,最大流的流量等于分離vs和vt的最小截集的截量。,定理8.8為我們提供了一個(gè)尋求網(wǎng)絡(luò)系統(tǒng)最大流的方法。亦即,如果網(wǎng)絡(luò)D中有一個(gè)可行流f,只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流f的增廣鏈。如果沒有增廣鏈,那么f一定是最大流。如有增廣鏈,那么可以按照定理8.9中必要性,不斷改進(jìn)和增大可行流f的流量,最終可以得到網(wǎng)絡(luò)中的一個(gè)最大流。,三標(biāo)號(hào)法從網(wǎng)絡(luò)中的一個(gè)可行流f出發(fā)(如果D中沒有f,可以令f是零流),運(yùn)用標(biāo)號(hào)法,經(jīng)過(guò)標(biāo)號(hào)過(guò)程和調(diào)整過(guò)程,可以得到網(wǎng)絡(luò)中的一個(gè)最大流。下面用給頂點(diǎn)標(biāo)號(hào)的方法來(lái)定義V1*.在標(biāo)號(hào)過(guò)程中,有標(biāo)號(hào)的頂點(diǎn)是V1*中的點(diǎn),沒有標(biāo)號(hào)的點(diǎn)不是V1*中的點(diǎn)。如果vt有了標(biāo)號(hào),表示存在一條關(guān)于f的增廣鏈。如果標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去,并且vt未被標(biāo)號(hào),則表示不存在關(guān)于f的增廣鏈。這樣,就得到了網(wǎng)絡(luò)中的一個(gè)最大流和最小截集。,1標(biāo)號(hào)過(guò)程在標(biāo)號(hào)過(guò)程中,網(wǎng)絡(luò)中的點(diǎn)或者是標(biāo)號(hào)點(diǎn)(分為已檢查和未檢查兩種)?;蛘呤俏礃?biāo)號(hào)點(diǎn)。每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分:第一個(gè)標(biāo)號(hào)表示這個(gè)標(biāo)號(hào)是從那一點(diǎn)得到的。以便找出增廣鏈。第二個(gè)標(biāo)號(hào)是為了用來(lái)確定增廣鏈上的調(diào)整量。標(biāo)號(hào)過(guò)程開始,先給vs標(biāo)號(hào)(0,+)。這時(shí),vs是標(biāo)號(hào)未檢查的點(diǎn),其它都是未標(biāo)號(hào)點(diǎn)。一般地,取一個(gè)標(biāo)號(hào)未檢查點(diǎn)vi,對(duì)一切未標(biāo)號(hào)點(diǎn)vj:,(1)如果在?。╲i,vj)上,fij0,那么給vj標(biāo)號(hào)(-vi,l(vj)).其中l(wèi)(vj)=minl(vi),fji.這時(shí),vj成為標(biāo)號(hào)未檢查點(diǎn)。于是vi成為標(biāo)號(hào)已檢查的點(diǎn)。重復(fù)以上步驟,如果所有的標(biāo)號(hào)都已經(jīng)檢查過(guò),而標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去,則標(biāo)號(hào)法結(jié)束。這時(shí)的可行流就是最大流。,2.調(diào)整過(guò)程首先按照vt和其它的點(diǎn)的第一個(gè)標(biāo)號(hào),反向追蹤,找出增廣鏈。例如,令vt的第一個(gè)標(biāo)號(hào)是vk,則?。╲k,vt)在上。再看vk的第一個(gè)標(biāo)號(hào),若是vi,則弧(vi,vk)都在上。依次類推,直到vs為止。這時(shí),所找出的弧就成為網(wǎng)絡(luò)D的一條增廣鏈。取調(diào)整量=l(vt),即vt的第二個(gè)標(biāo)號(hào),令,但是,如果vt被標(biāo)上號(hào),表示得到一條增廣鏈,轉(zhuǎn)入下一步調(diào)整過(guò)程。,其它不變,再去掉所有的標(biāo)號(hào),對(duì)新的可行流f=fij,重新進(jìn)行標(biāo)號(hào)過(guò)程,直到找到網(wǎng)絡(luò)D的最大流為止。,例8.8求圖8.21的網(wǎng)絡(luò)最大流,弧旁的權(quán)數(shù)表示(cij,fij)。,圖820例88網(wǎng)絡(luò)圖,解:用標(biāo)號(hào)法。1.標(biāo)號(hào)過(guò)程。(1)首先給vs標(biāo)號(hào)(0,+)(2)看vs:在弧(vs,v2)上,fs2=cs3=3,不具備標(biāo)號(hào)條件。在弧(vs,v1)上,fs1=10,故給v2標(biāo)號(hào)(-v1,l(v2)),其中l(wèi)(v2)=minl(v1),f21=min4,1=1.,圖821例88網(wǎng)絡(luò)圖,(0,+),(vs,4),(v1,1),(v2,1),(-v2,1),(v3,1),(4)看v2:在?。╲2,v4)上,f24=30,故給v3標(biāo)號(hào)(-v2,l(v3),其中l(wèi)(l(v3)=minl(v2),f32=min1,1=1。(5)在v3,v4中任意選一個(gè),比如v3,在?。╲3,vt)上,f3t=1<c3t=2,故給vt標(biāo)號(hào)(v3,l(vt),其中l(wèi)(vt)=minl(v3),(c3t-f3t)=min1,1=1.因?yàn)関t被標(biāo)上號(hào),根據(jù)標(biāo)號(hào)法,轉(zhuǎn)入調(diào)整過(guò)程。,2.調(diào)整過(guò)程從vt開始,按照標(biāo)號(hào)點(diǎn)的第一個(gè)標(biāo)號(hào),用反向追蹤的方法,找出一條從vs到vt的增廣鏈,如圖822中雙箭線所示。不難看出,+=(vs,v1),(v3,vt),=(v2,v1),(v3,v2),取=1,在上調(diào)整f,得到,圖822例88網(wǎng)絡(luò)圖,(5,2),(1,0),(1,0),(2,2),(cij,fij),調(diào)整后的可行流f*,如圖8.22所示,再對(duì)這個(gè)可行流從新進(jìn)行標(biāo)號(hào)過(guò)程,尋找增廣鏈。首先給vs標(biāo)號(hào)(0,+),看vs,給v1標(biāo)號(hào)(vs,3)??磛1,在?。╲1,v3)上,f13=c13,?。╲2,v1)上,f21=0,均不符合條件。因此標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去,不存在從vS到vt的增廣鏈,算法結(jié)束。,這時(shí),網(wǎng)絡(luò)中的可行流f*即是最大流,最大流的流量v(f*)=fs1+fs2=5.同時(shí),也找出D的最小截集(V1,),其中V1是標(biāo)號(hào)的集合,是未標(biāo)號(hào)的集合。,(0,+),(vs,3),圖823例88網(wǎng)絡(luò)圖,例89求圖824所示網(wǎng)絡(luò)的最大流,圖824例89網(wǎng)絡(luò)圖,解:給定初始可行流為全零流,即f(0)=0,給vs標(biāo)號(hào)(0,+),檢查vs:給v1標(biāo)號(hào)(vs,4),給v3標(biāo)號(hào)(vs,3),給v3標(biāo)號(hào)(vs,10),(0,+),(vs,4),(vs,3),(vs,10),檢查v1:給v3標(biāo)號(hào)(v1,1),檢查完畢;,(v1,1),檢查v2:給v5標(biāo)號(hào)(v2,3),檢查完畢;,(v2,3),檢查v5:給vt標(biāo)號(hào)(v5,3),檢查完畢;,(v5,3),因?yàn)榻K點(diǎn)vt已標(biāo)號(hào),故找出一條從vs到vt的增廣鏈:vsv2v5vt.取=3,(vs,4),(v1,3),(vs,10),(v1,1),(v2,2),(0,+),(v5,2),(vs,2),(v3,3),(vs,10),(v2,3),(v3,4),(0,+),(v4,3),(0,+),(vs,2),(vs,10),(v3,4),(v5,2),(v5,3),(0,+),(vs,2),(vs,4),(v1,1),(v1,1),(v4,1),(0,+),(vs,4),(vs,1),(v3,1),(v5,1),(v4,1),(0,+),(vs,1),(vs,3),(v1,1),(v2,1),(v4,1),(0,+),(vs,3),首先給vs標(biāo)號(hào)(0,+),看vs,給v3標(biāo)號(hào)(vs,3)??磛3,在?。╲3,v2)上,f32=c32,?。╲3,v5)上,f35=c35,均不符合條件。因此標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去,不存在從vS到vt的增廣鏈,算法結(jié)束。最大流量f*=14。,8.4最小費(fèi)用最大流問(wèn)題,在實(shí)際的網(wǎng)絡(luò)系統(tǒng)中,當(dāng)涉及到有關(guān)流的問(wèn)題的時(shí)候,我們往往不僅僅考慮的是流量,還經(jīng)常要考慮費(fèi)用的問(wèn)題。比如一個(gè)鐵路系統(tǒng)的運(yùn)輸網(wǎng)絡(luò)流,即要考慮網(wǎng)絡(luò)流的貨運(yùn)量最大,又要考慮總費(fèi)用最小。最小費(fèi)用最大流問(wèn)題就是要解決這一類問(wèn)題。,我們首先考察,在一個(gè)網(wǎng)絡(luò)D中,當(dāng)沿可行流f的一條增廣鏈,以調(diào)整量=1改進(jìn)f,得到的新可行流f的流量,有v(f)=,設(shè)一個(gè)網(wǎng)絡(luò)D=(V,A,C),對(duì)于每一個(gè)弧(vi,vj)A,給定一個(gè)單位流量的費(fèi)用bij0,網(wǎng)絡(luò)系統(tǒng)的最小費(fèi)用最大流問(wèn)題,是指要尋求一個(gè)最大流f,并且流的總費(fèi)用達(dá)到最小。,=v(f)+1,而此時(shí)總費(fèi)用b(f)比b(f)增加了,結(jié)論:如果可行流f在流量為v(f)的所有可行流中的費(fèi)用最小,并且是關(guān)于f的所有增廣鏈中的費(fèi)用最小的增廣鏈,那么沿增廣鏈,我們將叫做這條增廣鏈的費(fèi)用。,調(diào)整可行流f,得到的新可行流f,也是流量為v(f)的所有可行流中的最小費(fèi)用流。依次類推,當(dāng)f是最大流時(shí),就是所要求的最小費(fèi)用最大流。,顯然,零流f=0是流量為0的最小費(fèi)用流。一般地,尋求最小費(fèi)用流,總可以從零流f=0開始。下面的問(wèn)題是:如果已知f是流量為v(f)的最小費(fèi)用流,那么就要去尋找關(guān)于f的最小費(fèi)用增廣鏈。,對(duì)此,重新構(gòu)造一個(gè)賦權(quán)有向圖M(f),其頂點(diǎn)是原網(wǎng)絡(luò)D的頂點(diǎn),而將D中的每一條弧(vi,vj)變成兩個(gè)相反方向的弧(vi,vj)和(vj,vi),并且定義M(f)中弧的權(quán)wij為:,并且將權(quán)為+的弧從M(f)中略去。,這樣,在網(wǎng)絡(luò)D中尋找關(guān)于f的最小費(fèi)用增廣鏈就等于價(jià)于在M(f)中尋求從vs到vt的最短路。算法開始,取零流f(0)=0.一般地,如果在第K-1步得到最小費(fèi)用流f(K-1),則構(gòu)造圖M(f(k-1)。在圖M(f(k-1)中,尋求從vs到vt的最短路。如果存在最短路,則f(k-1)就是最小費(fèi)用最大流。如果存在最短路,則在原網(wǎng)絡(luò)D中得到相對(duì)應(yīng)(一一對(duì)應(yīng))的增廣鏈0,在增廣鏈上對(duì)f(k1)進(jìn)行調(diào)整,取調(diào)整量,令:,得到一個(gè)新的可行流f(k),在對(duì)f(k)重復(fù)以上的步驟,直到D中找不到相對(duì)應(yīng)的增廣鏈時(shí)為止。,例8.9求圖8-24所示網(wǎng)絡(luò)中的最小費(fèi)用最大流,弧旁的權(quán)是(bij,cij).,圖8-24,解:(1)取初始可行流為零流f(0)=0,構(gòu)造賦權(quán)有向圖M(f(0),求出從vs到vt的最短路(vs,v2,v1,vt),如圖8.25a中雙箭頭所示。,圖8.25a,(2)在原網(wǎng)絡(luò)D中,與這條最短路相對(duì)應(yīng)的增廣鏈為=(vs,v2,v1,vt)。(3)在上對(duì)f(0)=0進(jìn)行調(diào)整,取=5,得到新可行流f(1),如圖8.25b所示。按照以上的算法,依次類推,可以得到f(1),f(2),f(3),f(4),流量分別為5,7,10,11,并且分別構(gòu)造相對(duì)應(yīng)的賦權(quán)有向圖M(f(1),M(f(2),M(f(3),M(f(4)。由于在M(f(4)中已經(jīng)不存在從vs到vt的最短路,因此,可行流f(4),v(f(1)=11是最小費(fèi)用最大流。,M(f(1),圖8.25c,M(f(2),圖8.25e,8.6網(wǎng)絡(luò)計(jì)劃,大型項(xiàng)目的開發(fā)涉及很復(fù)雜的項(xiàng)目協(xié)調(diào)和管理問(wèn)題,為使項(xiàng)目管理人員對(duì)項(xiàng)目進(jìn)度有全面的了解,進(jìn)行有效的控制,必須使用科學(xué)的管理方法.,網(wǎng)絡(luò)計(jì)劃法是使用最廣泛的方法之一,關(guān)鍵路徑法(CPM)和項(xiàng)目評(píng)審技術(shù)(PERT)是兩種使用最廣泛的網(wǎng)絡(luò)計(jì)劃技術(shù)。,網(wǎng)絡(luò)計(jì)劃方法的優(yōu)點(diǎn)使它適用于生產(chǎn)技術(shù)復(fù)雜,工作項(xiàng)目繁多,且緊密聯(lián)系的一些跨部門的工作計(jì)劃,如:新產(chǎn)品研制開發(fā)大型工程項(xiàng)目建設(shè)生產(chǎn)技術(shù)準(zhǔn)備復(fù)雜設(shè)備的大修計(jì)劃,網(wǎng)絡(luò)計(jì)劃方法的基本原理,將工程項(xiàng)目分解為相對(duì)獨(dú)立的活動(dòng),根據(jù)各活動(dòng)先后順序、相互關(guān)系以及完成所需時(shí)間做出反映項(xiàng)目全貌的網(wǎng)絡(luò)圖;從項(xiàng)目完成全過(guò)程著眼,找出影響項(xiàng)目進(jìn)度的關(guān)鍵活動(dòng)和關(guān)鍵路線,通過(guò)對(duì)資源的優(yōu)化調(diào)度,實(shí)現(xiàn)對(duì)項(xiàng)目實(shí)施的有效控制和管理。,網(wǎng)絡(luò)計(jì)劃方法的主要功能,1用網(wǎng)絡(luò)圖描述一個(gè)實(shí)際項(xiàng)目的管理問(wèn)題(畫網(wǎng)絡(luò)圖);2計(jì)算項(xiàng)目的最早、最晚完成和開工時(shí)間(網(wǎng)絡(luò)計(jì)算);3尋找關(guān)鍵活動(dòng)和關(guān)鍵路徑(網(wǎng)絡(luò)分析);4根據(jù)以上分析對(duì)網(wǎng)絡(luò)進(jìn)行優(yōu)化。,8.6.1網(wǎng)絡(luò)計(jì)劃與網(wǎng)絡(luò)圖,復(fù)雜工程項(xiàng)目可被分解為一系列小的事件或活動(dòng),各種事件和活動(dòng)之間的邏輯順序可以表述為一個(gè)由一系列弧和節(jié)點(diǎn)組成的網(wǎng)絡(luò)圖;網(wǎng)絡(luò)圖中的有向弧代表各種活動(dòng)(或工作),活動(dòng)完成需要的時(shí)間寫在弧上;節(jié)點(diǎn)表示事件(或事項(xiàng)),表示活動(dòng)的開始與結(jié)束,每個(gè)節(jié)點(diǎn)有唯一節(jié)點(diǎn)號(hào);,位于弧的起點(diǎn)和終點(diǎn)的節(jié)點(diǎn)表示活動(dòng)或事件的開始和結(jié)束,每個(gè)活動(dòng)有一個(gè)起點(diǎn)和一個(gè)終點(diǎn):,圓圈和里面的數(shù)字代表各事項(xiàng),寫在箭桿中間的數(shù)字5表示完成本工作所需時(shí)間,即工作a(1,2),事項(xiàng):(1,2)。,圖8.26,整個(gè)網(wǎng)絡(luò)的方向按慣例從左到右地反映活動(dòng)的邏輯順序,并有唯一的起點(diǎn)和終點(diǎn)。,畫網(wǎng)絡(luò)圖有以下四個(gè)階段:一、列出所有活動(dòng)一個(gè)完整的項(xiàng)目必須被分解為一系列獨(dú)立,活動(dòng)(稱為工序),分解程度取決于項(xiàng)目計(jì)劃的需要以及相應(yīng)的管理職能。二、確定每個(gè)活動(dòng)的緊前工序項(xiàng)目執(zhí)行的連續(xù)性確定了項(xiàng)目各項(xiàng)活動(dòng)的前后順序,為了從邏輯上搞清楚活動(dòng)之間的順序關(guān)系,需要確定每項(xiàng)活動(dòng)可以開始之前必須完成的活動(dòng)-緊前工序。,注意:區(qū)分習(xí)慣上發(fā)生的順序和它們?cè)谶壿嬌蠎?yīng)該發(fā)生的順序,例如,寄出一個(gè)發(fā)票的一般,方法是:,(1)檢查發(fā)票(2)將發(fā)票放入信封(3)封上信封(4)在信封上寫地址這不是唯一正確方法,網(wǎng)絡(luò)圖應(yīng)能反映所有可能性,而不僅僅是傳統(tǒng)方法。,三、畫網(wǎng)絡(luò)圖畫網(wǎng)絡(luò)圖應(yīng)注意以下規(guī)則:,1、網(wǎng)絡(luò)只能有一個(gè)總起點(diǎn)和一個(gè)總終點(diǎn);,圖8.27中,有兩個(gè)總起點(diǎn)事項(xiàng),;三個(gè)總終點(diǎn)事項(xiàng),不符合規(guī)則。,圖8.27,2、網(wǎng)絡(luò)圖為有向圖,且不能有回路;,圖8.28中是回路,不符合規(guī)則,圖8.28,3、兩個(gè)節(jié)點(diǎn)之間不能有兩條或兩條以上的?。▋蓚€(gè)及兩個(gè)以上的工作);,圖8.29不符合規(guī)則。,4、應(yīng)正確表示活動(dòng)之間的前行后繼關(guān)系;,如4道工作a,b,c,d的關(guān)系為:c必須在a,b均完成后才能開工,而d只要在b完工后,圖8.29,即可開工,如畫成下圖是錯(cuò)誤的,因本來(lái)與a工作的工作d被錯(cuò)誤地表為必須在a完工后才能開工。,5、虛擬活動(dòng)的運(yùn)用,網(wǎng)絡(luò)有時(shí)需要包括由虛線表示的虛擬活,圖8.30,動(dòng)。首先,它可以避免兩個(gè)活動(dòng)有相同的起點(diǎn)和終點(diǎn);其次,使用虛擬活動(dòng)可以幫助表示一些特殊的邏輯依賴關(guān)系。,如前面不符合規(guī)則的圖8.27,圖8.29,圖8.30,用添加虛工作的方法改圖為圖8.31,圖8.32,圖8.33就是正確的了。,圖8.32,圖8.31,圖8.33,商業(yè)中心建設(shè)網(wǎng)絡(luò)圖,錯(cuò)誤的依賴關(guān)系,6、平行工作虛工作還可以用于正確地表示平行工作與交叉工作。一道工作分為幾道工作同時(shí)進(jìn)行,稱為平行工作,如圖圖8.34(a)中市場(chǎng)調(diào)查(2,3)中需12天,如增加人力分為三組同時(shí)進(jìn)行,可畫為(b)。,圖8.34(a),圖8.34(b),7、交叉作業(yè)兩件或兩件以上的工作交叉進(jìn)行,稱為交叉工作。如工作A與工作B分別為挖溝和埋管子,那么它們的關(guān)系可以是挖一段埋一段,不必等溝全部挖好再埋,這就可以用交叉作,業(yè)來(lái)表示,如把這工作各分為三段,A=a1+a2+a3,B=b1+b2+b3,可用圖8.35表示:,圖8.35,如果要盡量避免弧的交叉,圖8.36(a)中許多交叉的弧可以避免,整體改為(b)就比較清晰了。,圖8.36(a),圖8.36(b),四、給節(jié)點(diǎn)編號(hào)編號(hào)應(yīng)注意以下規(guī)則:每條弧上起點(diǎn)的編號(hào)數(shù)小于終點(diǎn)的編號(hào)數(shù)。,方法:給起點(diǎn)一個(gè)編號(hào)數(shù),設(shè)想將該點(diǎn)為起點(diǎn)的弧都去掉,從而又有新的起點(diǎn),依次給新的起點(diǎn)編號(hào),反復(fù)這樣做直到終點(diǎn)已經(jīng)編號(hào)為止。,8.6.2網(wǎng)絡(luò)分析與計(jì)算,通過(guò)網(wǎng)絡(luò)分析可增加對(duì)項(xiàng)目整體的了解,并能發(fā)現(xiàn)活動(dòng)并行執(zhí)行的機(jī)會(huì),網(wǎng)絡(luò)分析可以分以下五個(gè)階段:1估計(jì)完成活動(dòng)需要的時(shí)間t(i,j)計(jì)算每個(gè)活動(dòng)完成的平均或期望時(shí)間:根據(jù)歷史數(shù)據(jù)計(jì)算平均完成時(shí)間;或通過(guò)主觀估計(jì)得到完成時(shí)間的期望值;,2計(jì)算最早開始時(shí)間(ES)與最早完工(EF)時(shí)間從網(wǎng)絡(luò)起點(diǎn)開始,用下列公式計(jì)算最早開始時(shí)間(tES)和最早完工時(shí)間(tEF):最早完工=最早開始時(shí)間+活動(dòng)持續(xù)時(shí)間tEF(i,j)=tES(i,j)+t(i,j)最早開始時(shí)間=(緊前活動(dòng)的)最早結(jié)束時(shí)間tES(i,j)=maxktEF(k,i)如果一個(gè)活動(dòng)有幾個(gè)緊前活動(dòng),取其中最晚的最早結(jié)束時(shí)間。,tES(i,j)=maxktEF(k,i)tEF(i,j)=tES(i,j)+t(i,j),圖8.37,3計(jì)算最晚開始時(shí)間與最晚結(jié)束時(shí)間從最后活動(dòng)開始依次按下式計(jì)算每個(gè)活動(dòng)最晚結(jié)束時(shí)間tLF和最晚開始時(shí)間tLS最晚開始時(shí)間=最晚結(jié)束時(shí)間活動(dòng)持續(xù)時(shí)間tLS(i,j)=tLF(i,j)-t(i,j)最晚結(jié)束時(shí)間=(緊后活動(dòng)的)最晚開始時(shí)間tLF(i,j)=minktLS(j,k)如果一個(gè)活動(dòng)有幾個(gè)緊后活動(dòng),取其中最早的最晚開始時(shí)間。,tLF(i,j)=minktLS(j,k)tLS(i,j)=tLF(i,j)-t(i,j),圖8.38,4允許時(shí)差允許時(shí)差又稱活動(dòng)的機(jī)動(dòng)或富裕時(shí)間,常用的時(shí)差有兩種:總時(shí)差:不影響總工期條件下,任務(wù)可以延遲的最大幅度,用R(i,j)表示:R(i,j)=tLS(i,j)-tES(i,j)=tLF(i,j)-tEF(i,j)總時(shí)差=最晚開始時(shí)間最早開始時(shí)間=最晚結(jié)束時(shí)間最早結(jié)束時(shí)間,單時(shí)差:不影響緊后工作的最早開工時(shí)間的條件下,任務(wù)可以延遲的最大幅度,用r(i,j)表示:r(i,j)=minktES(j,k)-tEF(i,j),圖8.39,5確定關(guān)鍵路徑網(wǎng)絡(luò)計(jì)劃技術(shù)根據(jù)活動(dòng)持續(xù)時(shí)間之間的關(guān)系找出項(xiàng)目的關(guān)鍵活動(dòng),時(shí)差為零的活動(dòng)是關(guān)鍵活動(dòng),它們的延誤將導(dǎo)致整個(gè)項(xiàng)目完成時(shí)間延誤,所有關(guān)鍵活動(dòng)形成網(wǎng)絡(luò)中的關(guān)鍵路徑,非關(guān)鍵活動(dòng)是那些可在某種程度上延誤而不會(huì)引起整個(gè)項(xiàng)目完成時(shí)間延誤的活動(dòng)。,0,20,20,28,52,34,52,58,70,76,0,7,5,11,10,10,11,18,14,19,16,26,24,30,

注意事項(xiàng)

本文(運(yùn)籌學(xué)8圖與網(wǎng)絡(luò)分析.ppt)為本站會(huì)員(za****8)主動(dòng)上傳,裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。 若此文所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng)(點(diǎn)擊聯(lián)系客服),我們立即給予刪除!

溫馨提示:如果因?yàn)榫W(wǎng)速或其他原因下載失敗請(qǐng)重新下載,重復(fù)下載不扣分。




關(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),我們立即給予刪除!