運籌學-圖論課件

圖論第五章圖與網(wǎng)絡分析運籌學-圖論主要內(nèi)容：1圖的基本概念與基本定理2樹和最小支撐樹3最短路問題4最大流問題5最小費用流問題運籌學-圖論什么是圖？圖論中所謂的圖是由一些點(vertices)，和一些連接兩點的邊(edges)所形成的運籌學-圖論5.1圖的基本概念與基本定理

圖論是應用非常廣泛的運籌學分支，它已經(jīng)廣泛地應用于物理學控制論、信息論、工程技術(shù)、交通運輸、經(jīng)濟管理、電子計算機等各項領域。對于科學研究、市場和社會生活中的許多問題，可以同圖論的理論和方法來加以解決。例如：各種通信線路的架設，輸油管道的鋪設，鐵路或者公路交通網(wǎng)絡的合理布局等問題，都可以應用圖論的方法，簡便、快捷地加以解決問題。運籌學-圖論關于圖的第一篇論文是瑞士數(shù)學家歐拉（E.Euler）在1736年發(fā)表的解決“哥尼斯堡”七橋難題的論文。德國的哥尼斯堡城有一條普雷格爾河，河中有兩個島嶼，河的兩岸和島嶼之間有七座橋相互連接，當?shù)氐木用駸嶂杂谶@樣一個問題：一個散步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地。盡管試驗者很多，但是都沒有成功。為了尋找答案，1736年歐拉將這個問題抽象成圖所示圖形的一筆畫問題。運籌學-圖論K?nigsberg(Koenigsberg)哥尼斯堡，原為東普魯士(Prussia)首府，現(xiàn)屬俄羅斯(飛地)，名為加里寧格勒(Kaliningrad)運籌學-圖論運籌學-圖論哥尼斯堡七橋問題:要如何走過每座橋恰一次，再返回出發(fā)點？普瑞格爾河運籌學-圖論哥尼斯堡七橋問題ABCD運籌學-圖論哥尼斯堡七橋問題可簡化為以下圖形其中的四個頂點都是奇頂點ABCD運籌學-圖論CADB哥尼斯堡七橋問題可以看成是：對這樣一個封閉的圖形，是否可以一筆畫完成它并且回到原點數(shù)學家歐拉(Euler,1707-1783)于1736年嚴格地證明了上述哥尼斯堡七橋問題無解，并且由此開創(chuàng)了圖論的典型思維方式及論證方式運籌學-圖論即能否從某一點開始不重復地一筆畫出這個圖形，最終回到原點。歐拉在他的論文中證明了這是不可能的，因為這個圖形中每一個頂點都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就是古典圖論中的第一個著名問題。

在實際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關系，常常在紙上用點和線來畫出各式各樣的示意圖。運籌學-圖論圖論應用舉例例如，在組織生產(chǎn)中，為完成某項任務，各工序之間怎樣銜接，才能使生產(chǎn)任務完成得既快又好。一個郵遞員送信，要走完他負責投遞的全部街道，完成任務后回到郵局，應該按照怎樣的路線走，所走的路程最短。各種通信網(wǎng)絡的合理架設交通網(wǎng)絡的合理分布等運籌學-圖論生活中的一些例子運籌學-圖論臺大網(wǎng)路架構(gòu)圖運籌學-圖論例5.1

圖5.2是我國北京、上海、重慶等十四個城市之間的鐵路交通圖，這里用點表示城市，用點與點之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管道圖，民用航空線圖等等。石家莊太原北京天津塘沽濟南青島徐州連云港南京上海鄭州武漢重慶圖5.3運籌學-圖論

例5.2

有六支球隊進行足球比賽，我們分別用點v1，…，v6表示這六支球隊，它們之間的比賽情況，也可以用圖反映出來，已知v1隊戰(zhàn)勝v2

隊，v2隊戰(zhàn)勝v3

隊，v3隊戰(zhàn)勝v5隊，如此等等。這個勝負情況，可以用圖5.3所示的有向圖反映出來v3v5v2v4v6v1運籌學-圖論

從以上的幾個例子可以看出，我們用點和點之間的線所構(gòu)成的圖，反映實際生產(chǎn)和生活中的某些特定對象之間的特定關系。通常用點表示研究對象，用點與點之間的線表示研究對象之間的特定關系。由于在一般情況下，圖中對象的相對位置如何，點與點之間線的長短曲直，對于反映研究對象之間的關系，顯的并不重要，因此，圖論中的圖與幾何圖、工程圖等本質(zhì)上是不同的。運籌學-圖論

圖論中的圖是由點、點與點之間的線所組成的。通常，我們把點與點之間不帶箭頭的線叫做邊，帶箭頭的線叫做弧。如果一個圖是由點和邊所構(gòu)成的，那么稱為無向圖，記作G=(V，E)，其中V表示圖G

的點集合，E表示圖G的邊集合。連接點vi,vjV的邊記作[vi,vj]，或者[vj,vi]。如果一個圖是由點和弧所構(gòu)成的，那么稱為它為有向圖，記作D=(V,A)，其中V表示有向圖D的點集合，A表示有向圖D的弧集合。一條方向從vi指向vj的弧，記作(vi,vj)。

圖的基本概念運籌學-圖論

圖5.4是一個無向圖G=（V，E），其中V={v1,v2,v3,v4}E={[v1,v2],[v2,v1],[v2,v3],[v3,v4],[v1,v4],[v2,v4],[v3,v3]}v3v2v1v4圖5.4運籌學-圖論圖5.5

是一個有向圖D=（V，A）其中V={v1

,v2

,v3

,v4

,v5

,v6

,v7}A={(v1,v2),(v1,v3),(v3

,v2)(v3

,v4),(v2

,v4),(v4

,v5),(v4

,v6),(v5,v3),(v5

,v4),(v5

,v6),(v6

,v7)}圖5.5v7v5v3v4v2v6v1運籌學-圖論

圖的基本概念一個圖G或有向圖D中的點數(shù)，記作P(G)或P(D)，簡記作P；邊數(shù)或者弧數(shù)，記作q(G)或者q(D)，簡記作q。如果邊[vi,vj]E，那么稱vi,vj

是邊的端點，或者vi,vj是相鄰的。如果一個圖G中，一條邊的兩個端點是相同的，那么稱為這條邊是環(huán)，如圖5.4中的邊[v3,v3]是環(huán)。運籌學-圖論

圖的基本概念如果兩個端點之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡?，如圖5.4中的邊[v1

,v2],[v2

,v1]。v3v2v1v4運籌學-圖論v1v5v4v3v2簡單圖（2）（4）（3）（3）（2）多重圖v1v5v4v3v2（4）（6）（3）（3）（2）一個無環(huán)，無多重邊的圖稱為簡單圖，一個無環(huán)，有多重邊的圖稱為多重圖。運籌學-圖論

以點v為端點的邊的個數(shù)稱為點v的度（次），記作d(v),如圖5.4中d(v1)=3，d(v2

)=4，d(v3

)=4，d(v4)=3。度為零的點稱為弧立點，度為1的點稱為懸掛點。懸掛點的邊稱為懸掛邊。度為奇數(shù)的點稱為奇點，度為偶數(shù)的點稱為偶點。端點的度

d(v)：點v作為端點的邊的個數(shù)奇點：d(v)=奇數(shù)；運籌學-圖論偶點：d(v)

=偶數(shù)；懸掛點：d(v)=1；懸掛邊：與懸掛點連接的邊；孤立點：d(v)=0；空圖：E=，無邊圖v1v2v3v4v5v6運籌學-圖論v1v7v6v5v4v3v2V={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

為懸掛點，v7為孤立點。圖5.7運籌學-圖論

定理5.1

所有頂點度數(shù)之和等于所有邊數(shù)的2倍。

證明：因為在計算各個點的度時，每條邊被它的兩個端點個用了一次。運籌學-圖論定理5.2

在任一圖中，奇點的個數(shù)必為偶數(shù)。證明：設V1，V2

分別是圖G中奇點和偶點的集合，由定理5.1，有因為是偶數(shù)，也是偶數(shù)，因此也必是偶數(shù)，從而V1

中的點數(shù)是偶數(shù)。運籌學-圖論

圖的連通性：鏈：由兩兩相鄰的點及其相關聯(lián)的邊構(gòu)成的點邊序列。如:v0,e1

,v1

,e2

,v2，e3

,v3

,…,vn-1,en

，

vn;v0，vn分別為鏈的起點和終點

。記作（v0,v1

,v2，,v3

,…,vn-1,vn）簡單鏈：鏈中所含的邊均不相同；初等鏈：鏈中所含的點均不相同,也稱通路；圈：若v0≠vn則稱該鏈為開鏈，否則稱為閉鏈或回路或圈；運籌學-圖論簡單圈：如果在一個圈中所含的邊均不相同初等圈：除起點和終點外鏈中所含的點均不相同的圈；v1v2v4v3v5v6v7初等鏈:(v1,v2,v3,v6,v7,v5)初等圈：(v1,v2,v3,v5,v4,v1)簡單鏈：(v1,v2,v3,v4,v5,v3)

簡單圈：(v4,v1,v2,v3,v5,v7,v6,v3,v4)運籌學-圖論以后除特別聲明，均指初等鏈和初等圈。v1v2v3v4v5不連通圖v1v5v4v3v2v6連通圖：圖中任意兩點之間均至少有一條通路，否則稱為不連通圖。

連通圖運籌學-圖論有向圖：關聯(lián)邊有方向?。河邢驁D的邊a=(u,v),起點u,終點v；路：若有從u

到v

不考慮方向的鏈,且各方向一致,則稱之為從u到v的路；初等路:

各頂點都不相同的路；初等回路:u=v

的初等路;連通圖：

若不考慮方向是無向連通圖;

強連通圖：任兩點有路;

運籌學-圖論基本概念點邊，弧無向圖鏈端點關聯(lián)邊有向圖圈始點，終點多重邊簡單圖初等鏈/圈度（次）環(huán)多重圖簡單鏈/圈奇點，偶點連通圖基礎圖懸掛點懸掛邊不連通圖路弧立點回路運籌學-圖論

例一擺渡人欲將一只狼、一頭羊、一籃菜從河西渡過河到河東，由于船小，一次只能帶一物過河，并且狼與羊,羊與菜不能獨處。給出渡河方法。

解：用四維0-1向量表示(人,狼,羊,菜)在河西岸的狀態(tài)(在河西岸則分量取1,否則取0)，共有24=16種狀態(tài)，在河東岸的狀態(tài)類似記作。

由題設,狀態(tài)(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允許的，從而對應狀態(tài)(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允許的。以可允許的10個狀態(tài)向量作為頂點，將可能互相轉(zhuǎn)移的狀態(tài)用線段連接起來構(gòu)成一個圖。根據(jù)此圖便可找到渡河方法。運籌學-圖論(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河西=(人,狼,羊,菜)河東=(人,狼,羊,菜)

將10個頂點分別記為A1,A2,…,A10,則渡河問題化為在該圖中求一條從A1到A10的路.

從圖中易得到兩條路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.運籌學-圖論圖的矩陣表示1.鄰接矩陣Adjacencymatrix表示圖中兩點之間的相互關系兩點之間有弧或邊的，用1表示，否則用0表示，構(gòu)成一個矩陣Av2v4v6v5v1v3v1v2v3v4v5v6v1011000v2101110v3110010v4010011v5011101v6000110運籌學-圖論有向圖v1v7v2v5v3v4v6v8v9v1v2v3v4v5v6v7v8v9v1011100000v2000010000v3010100000v4000001000v5000101110v6000010100v7000000010v8000000000v9000010010運籌學-圖論矩陣A的元素全為0的行所對應的點稱為匯點上圖v8矩陣A的元素全為0的列所對應的點稱為源點上圖v1、v9運籌學-圖論5.2樹和最小支撐樹一、樹及其性質(zhì)在各種各樣的圖中，有一類圖是十分簡單又非常具有應用價值的圖，這就是樹。

例5.3

已知有六個城市，它們之間要架設電話線，要求任意兩個城市均可以互相通話，并且電話線的總長度最短。運籌學-圖論如果用六個點v1…v6代表這六個城市，在任意兩個城市之間架設電話線，即在相應的兩個點之間連一條邊。這樣，六個城市的一個電話網(wǎng)就作成一個圖。表示任意兩個城市之間均可以通話，這個圖必須是連通圖。并且，這個圖必須是無圈的。否則，從圈上任意去掉一條邊，剩下的圖仍然是六個城市的一個電話網(wǎng)。圖5.2.1是一個不含圈的連通圖，代表了一個電話線網(wǎng)。運籌學-圖論圖5.2.1v6v3v4v2v5v1運籌學-圖論樹及其性質(zhì)樹：既簡單又很有用樹：一個無圈的連通圖運籌學-圖論組織結(jié)構(gòu)圖ManagerSubordSubord運籌學-圖論榮國公賈代善賈赦賈政賈璉賈珠賈寶玉賈環(huán)賈蘭運籌學-圖論定理定理1：設G=(V,E)是一個樹，p(G)>=2，則G中至少有兩個懸掛點。定理2：圖G=(V,E)是一個樹的充要條件是G不含圈，且恰有p-1條邊。定理3：圖G=(V,E)是一個樹的充要條件是G是連通圖，且q(G)=p(G)-1。定理4：圖G=(V,E)是一個樹的充要條件是任意兩個頂點之間恰有一條鏈。運籌學-圖論推論從一個樹中去掉任意一條邊，則余下的圖是不連通的。在樹中不相鄰的兩個點間添上一條邊，則恰好得到一個圈運籌學-圖論運籌學-圖論圖的支撐樹設圖T=(V,E')是圖G=(V,E)的一個支撐子圖，如果T是一個樹，則稱T是G的一個支撐樹定理5：圖G有支撐樹的充要條件是圖G是連通的。破圈法：任取一個圈，從中去掉一條邊，再對余下的圖重復直到不再含圖時為止。運籌學-圖論破圈法運籌學-圖論避圈法在圖中任取一條邊，找到一條與之不構(gòu)成圈的邊，再找一條前兩邊不構(gòu)成圈的邊重復直到不再能進行為止取出的邊數(shù)為p-1條運籌學-圖論避圈法運籌學-圖論最小支撐樹問題給定圖G=(V,E)，對G中的每一條邊[vi,vj]，相應地有一個數(shù)wij，則稱這樣的圖為賦權(quán)圖wij稱為邊[vi,vj]上的權(quán)權(quán)是與邊有關的數(shù)量指標，可以是距離、時間、費用等。運籌學-圖論賦權(quán)圖不僅指出各個點之間的鄰接關系，而且同時也表示出各點之間的數(shù)量關系廣泛應用于解決工程技術(shù)及管理等領域的最優(yōu)化問題最小支撐樹問題就是賦權(quán)圖上的最優(yōu)化問題之一。運籌學-圖論設有一個連通圖G=(V,E)，每一邊e=[vi,vj]有一個非負權(quán)w(e)=wij(wij>0)如果T=(V,E')，是G的一個支撐樹，稱E'中所有邊的權(quán)之和為支撐樹T

的權(quán)，記為w(T)運籌學-圖論如果支撐樹T*的權(quán)w(T*)是G的所有支撐樹的權(quán)中最小者，則稱T*是G的最小支撐樹（最小樹），即式中對G的所有支撐樹T取最小運籌學-圖論最小支撐樹問題就是要求G的最小支撐樹。方法有二：避圈法Kruskal破圈法常見求賦權(quán)圖的最小樹。運籌學-圖論

例5.4某廠內(nèi)聯(lián)結(jié)六個車間的道路網(wǎng)如下所示，已知每條路的長，要求沿道路架設聯(lián)結(jié)六個車間的電話線網(wǎng)，使電話線的總長最小。v1v2v4v6v3v5657152344運籌學-圖論避圈法求最小支撐樹v1v2v4v6v3v515234i=1,E0=Φ。從E中選最小權(quán)邊。依次選最小權(quán)邊，并使之不構(gòu)成圈。共選5條邊v1v2v4v6v5657152344最后，電話線總長1+2+3+4+5=15v3運籌學-圖論破圈法求最小支撐樹任取一個圈，從中去掉一條權(quán)最大的邊。依次重復，直到不含圈為止。v1v2v4v6v5657152344最后，電話線總長1+2+3+4+5=15v3運籌學-圖論矩陣計算方法T運籌學-圖論TT運籌學-圖論TTT運籌學-圖論TTTT運籌學-圖論TTTTT運籌學-圖論TTTTTT運籌學-圖論矩陣計算結(jié)果運籌學-圖論一.引言最短路徑問題是圖論中十分重要的最優(yōu)化問題之一，它作為一個經(jīng)常被用到的基本工具，可以解決生產(chǎn)實際中的許多問題，比如城市中的管道鋪設，線路安排，工廠布局，設備更新等等。也可以用于解決其它的最優(yōu)化問題。

5.3最短路問題運籌學-圖論例5.6如圖所示的單行線交通網(wǎng)，每弧旁的數(shù)字表示這條單行線的距離?，F(xiàn)在某人要從v1出發(fā)，通過這個交通網(wǎng)到達v8

，求使總距離最短的旅行線路。v1v7v2v5616321v32v4v610310v8v9246234?運籌學-圖論路很多v1v7v2v5616321v32v4v610310v8v92462341+10+2+4=176+1+6=133+2+1+3+4=133+2+10+10+6=31哪一條最短？運籌學-圖論最短路算法如果P是D中從vs到vi的最短路，vi是P中的一個點，那么從vs沿P到vi的路是從vs到vi的最短路。1.圖形的標號法2.所有wij≥0的情形—Dijkstra法1959運籌學-圖論1.圖形的標號法先標出離終點最近的一段，然后標號與該點距離最短的點，繼續(xù)逆推至始點。C4AB1B2C1C2C3D1D2D3E1E2E3F1F2G5313668766688222255333333443510437597681310913121618從A到G的最短路為：A-B1-C2-D1-E2-F2-G運籌學-圖論2.Dijkstra法基本思路：從vs出發(fā)，逐步地向外探尋最短路。執(zhí)行過程中，與每個點對應，記錄下一個數(shù)(稱為此點的標號)，它或者表示從vs到該點的最短路的權(quán)(稱為P標號)或者是從vs到該點的最短路的權(quán)的上界(稱為T標號)方法的每一步是修改T標號，并且把某一個具T標號的點改變?yōu)榫逷標號的點，從而使D中具P標號的點多一個，如此經(jīng)過p-1步，就可以求出從vs到各點的最短路。運籌學-圖論Dijkstra法具體步驟開始(i=0)，令S0={vs},P(vs)=0,λ(vs)=0,對每一個v≠

vs，令

T(v)=+∞,λ(v)=M,令k=s1.如果Si=V，算法終止，這時，對每個vSi，d(vs,v)=P(v)

；否則轉(zhuǎn)入步驟22.考察每個使(vk,vj)A且vjSi的點vj。如果T(v)>P(vk)+wkj，則把T(vj)修改為P(vk)

+wkj

，把λ(vj)修改為k；否則轉(zhuǎn)入步驟3運籌學-圖論3.令T(vji)=min{T(vj)}如果T(vji)<∞則把vji的T標號變?yōu)镻標號P(vji)=T(vji)，令Si+1=SiU{vji}，k=ji,把i換成i+1，轉(zhuǎn)入步驟1；否則終止，這時對每一個，而對每一個vSi，d(vs,v)=T(v)運籌學-圖論v1v2v3v4v5v6v7v80v2v3v4v5v6v7v8PTλ0∞0M∞M∞M∞M∞M∞M∞Mv1v7v2v5616321v32v4v610310v8v9246234若T(v)>P(vk)+wkj則T(v)=P(vk)+wkj

λ(vj)修改為k找到min{T(vj)}，將其TP標號P(vj)=T(vj)，S=

{v1，}6311111v4,v3,1143535v2,626v5,105951259v7,10v6,12v8v1到v8最短路V13258運籌學-圖論求s到t的最短路。s3t267452418291415530204416116196運籌學-圖論s3t267452418291415530204416116196

0S={}PQ={s,2,3,4,5,6,7,t}運籌學-圖論s3t267452418291415530204416116196

0S={}PQ={s,2,3,4,5,6,7,t}運籌學-圖論s3t267452418291415530204416116196

15

9

14

0S={s}PQ={2,3,4,5,6,7,t}

X

XX運籌學-圖論s3t267452418291415530204416116196

15

9

14

0S={s}PQ={2,3,4,5,6,7,t}

X

XX運籌學-圖論s3t267452418291415530204416116196

15

9

14

0S={s,2}PQ={3,4,5,6,7,t}

X

XX運籌學-圖論s3t267452418291415530204416116196

15

9

14

0S={s,2}PQ={3,4,5,6,7,t}

X

XXX

33運籌學-圖論s3t267452418291415530204416116196

15

9

14

0S={s,2}PQ={3,4,5,6,7,t}

X

XXX

33運籌學-圖論s3t267452418291415530204416116196

15

9

14

0S={s,2,6}PQ={3,4,5,7,t}

X

XXX

33

44XX

32運籌學-圖論s3t267452418291415530204416116196

15

9

14

0S={s,2,6}PQ={3,4,5,7,t}

X

XX

44X

X

33X

32運籌學-圖論s3t2674518291415530204416116196

15

9

14

0S={s,2,6,7}PQ={3,4,5,t}

X

XX

44X

35X

59X24

X

33X

32運籌學-圖論s3t267452418291415530204416116196

15

9

14

0S={s,2,6,7}PQ={3,4,5,t}

X

XX

44X

35X

59X

X

33X

32運籌學-圖論s3t267452418291415530204416116196

15

9

14

0S={s,2,3,6,7}PQ={4,5,t}

X

XX

44X

35X

59XX

51X

34

X

33X

32運籌學-圖論s3t2674518291415530204416116196

15

9

14

0S={s,2,3,6,7}PQ={4,5,t}

X

XX

44X

35X

59XX

51X

34

X

33X

3224運籌學-圖論s3t2674518291415530204416116196

15

9

14

0S={s,2,3,5,6,7}PQ={4,t}

X

XX

44X

35X

59XX

51X

3424X

50X

45

X

33X

32運籌學-圖論s3t2674518291415530204416116196

15

9

14

0S={s,2,3,5,6,7}PQ={4,t}

X

XX

44X

35X

59XX

51X

3424X

50X

45

X

33X

32運籌學-圖論s3t2674518291415530204416116196

15

9

14

0S={s,2,3,4,5,6,7}PQ={t}

X

XX

44X

35X

59XX

51X

3424X

50X

45

X

33X

32運籌學-圖論s3t2674518291415530204416116196

15

9

14

0S={s,2,3,4,5,6,7}PQ={t}

X

XX

44X

35X

59XX

51X

34X

50X

45

X

33X

3224運籌學-圖論s3t267452418291415530204416116196

15

9

14

0S={s,2,3,4,5,6,7,t}PQ={}

X

XX

44X

35X

59XX

51X

34X

50X

45

X

33X

32運籌學-圖論s3t267452418291415530204416116196

15

9

14

0S={s,2,3,4,5,6,7,t}PQ={}

X

XX

44X

35X

59XX

51X

34X

50X

45

X

33X

32運籌學-圖論237184566134105275934682求從1到8的最短路徑運籌學-圖論237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0運籌學-圖論237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2運籌學-圖論237184566134105275934682X={1,2,4}min{c13,c23,c25,c47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3運籌學-圖論237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3運籌學-圖論237184566134105275934682X={1,2,4,6,7}min{c23,c25,c75,c78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6運籌學-圖論237184566134105275934682X={1,2,4,6,7}min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8運籌學-圖論237184566134105275934682X={1,2,3,4,6,7}min{c38,c58,c78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10運籌學-圖論237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路徑為{1，4，7，5，8}，長度為10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10運籌學-圖論三、含有負權(quán)的最短路的求法83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v8例：求從v1

到v8

的最短路運籌學-圖論83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-1-2383-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-71-15運籌學-圖論83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56運籌學-圖論83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56從v1

到v8

的最短路的長度為：6從v1

到v8

的最短路線為：v8v6v3v1運籌學-圖論應用舉例設備更新問題。某企業(yè)使用一臺設備，在每年年初，企業(yè)領導部門就要決定是購置新的，還是繼續(xù)使用舊的。若購置新設備，就要支付一定的購置費用；若繼續(xù)使用舊的，則需支付一定的維修費用?，F(xiàn)在的問題是如何制定一個幾年之內(nèi)的設備更新計劃，使得總的支付費用最少。運籌學-圖論我們用一個五年之內(nèi)要更新某種設備的計劃為例，若已知該種設備在各年年初的價格如下表，還知使用不同時間的設備所需要的維修費用如下表。第1年第2年第3年第4年第5年價格1111121213使用年限0-11-22-33-44-5維修費用5681118運籌學-圖論可供選擇的設備更新方案顯然是很多的。例如，每年都購置一臺新設備，則其購置費用為11+11+12+12+13=59，而每年支付的維修費用為5，五年合計為25。于是5年的總費用為59+25=84再如，每1，3，5年各購進一臺。此時設備購置費用為11+12+13=36，維修費用為5+6+5+6+5=27，5年總費用為36+27=63。如何制定總費用最省的設備更新計劃呢？運籌學-圖論轉(zhuǎn)化為最短路問題。用點代表“第i年年初購進一臺新設備”

這樣上述設備更新問題就變?yōu)椋涸谟邢蛸x權(quán)圖G=(V,E,F)(圖解如下)中求v1到v6的最短路問題。運籌學-圖論

由實際問題可知,設備使用三年后應當更新,因此刪除該圖中v1到v5,v1到v6,v2到v6的連線；又設備使用一年后就更新則不劃算,因此再刪除該圖中v1v2,v2v3,v3v4,v4v5,v5v6五條連線后得到從上圖中容易得到v1到v6只有兩條路：v1v3v6和v1v4v6.

而這兩條路都是v1到v6的最短路.五年的總費用為53。運籌學-圖論例揀貨路徑問題Pickpath貨架分布要揀貨物運籌學-圖論第1步

從第1通道到第2通道

每條路徑代表圖中的一條邊運籌學-圖論第2步

找出從第2通道到第3通道的每條路徑運籌學-圖論第3步

找出從第3通道到第4通道的每條路徑運籌學-圖論第4步

找出從第4通道到完成的每條路徑運籌學-圖論Findtheshortestpathoftheassociatedgraph運籌學-圖論Theshortestpathontheassociatedgraphgivesanefficientpickpathinwarehouse對應圖的最短路給出了倉庫的有效揀選路徑運籌學-圖論運籌學-圖論5.4網(wǎng)絡的最大流5.4.1網(wǎng)絡的最大流的概念網(wǎng)絡流一般在有向圖上討論定義網(wǎng)絡上支路的容量為其最大通過能力，記為cij，支路上的實際流量記為fij

圖中規(guī)定一個發(fā)點s，一個收點t節(jié)點沒有容量限制，流在節(jié)點不會存儲容量限制條件：0fijcij平衡條件：viA(vi)B(vi)運籌學-圖論5.4網(wǎng)絡的最大流圖中規(guī)定一個發(fā)點s，一個收點t－節(jié)點沒有容量限制，流在節(jié)點不會存儲－容量限制條件：0fijcij－平衡條件：

滿足上述條件的網(wǎng)絡流稱為可行流，總存在最大可行流當支路上fij=cij，稱為飽和??；v(f)為可行流的流量最大流問題也是一個線性規(guī)劃問題viA(vi)B(vi)運籌學-圖論定義：設f是一個可行流，是vs從vt到的一條鏈，若

滿足下列條件，則是可行流的一條增廣鏈：(1)

弧(vi,vj)+上，即+

中每一條弧是非飽和??；(2)弧(vi,vj)-上，即-

中每一條弧是非零流?。贿\籌學-圖論定義：把網(wǎng)絡分割為兩個成分的弧的最小集合，其中一個成分包含s

點，另一個包含t

點。一般包含s

點的成分中的節(jié)點集合用V表示，包含t

點的成分中的節(jié)點集合用V表示截量集容量是指截量集中前向弧的容量之和

福特-富克森定理：網(wǎng)絡的最大流等于最小截量集容量運籌學-圖論5.4.2確定網(wǎng)絡最大流的標號法

從任一個初始可行流出發(fā)，如0流基本算法：找一條從s

到t

點的增廣鏈。若在當前可行流下找不到增廣鏈，則已得到最大流增廣鏈中與s

到t方向一致的弧稱為前向弧，反之后向弧

增廣過程：前向弧fij=fij+,后向弧fij=fij

增廣后仍是可行流運籌學-圖論

最大流最小截量的標號法步驟第一步：標號過程，找一條增廣鏈1、給源點s

標號[s+,q(s)=]，表示從s點有無限流出潛力2、找出與已標號節(jié)點i

相鄰的所有未標號節(jié)點j，若(1)(i,j)是前向弧且飽和，則節(jié)點j

不標號；(2)(i,j)是前向弧且未飽和，則節(jié)點j

標號為[i+,q(j)]，表示從節(jié)點i

正向流出，可增廣q(j)=min[q(i),cijfij]；(3)(j,i)是后向弧，若fji=0，則節(jié)點j

不標號；(4)(j,i)是后向弧，若fji>0，則節(jié)點j

標號為[i,q(j)]，表示從節(jié)點j

流向i，可增廣q(j)=min[q(i),fji]；運籌學-圖論

最大流最小截量的標號法步驟3、重復步驟2，可能出現(xiàn)兩種情況：(1)節(jié)點t

尚未標號，但無法繼續(xù)標記，說明網(wǎng)絡中已不存在增廣鏈，當前流v(f)就是最大流；所有獲標號的節(jié)點在V

中，未獲標號節(jié)點在V

中，V與V

間的弧即為最小截量集；算法結(jié)束(2)節(jié)點t

獲得標號，找到一條增廣鏈，由節(jié)點t

標號回溯可找出該增廣鏈；到第二步運籌學-圖論

最大流最小截量的標號法步驟第二步：增廣過程1、對增廣鏈中的前向弧，令f=f+q(t)，q(t)為節(jié)點t

的標記值2、對增廣鏈中的后向弧，令f=fq(t)3、非增廣鏈上的所有支路流量保持不變第三步：抹除圖上所有標號，回到第一步一次只找一條增廣鏈，增廣一次換一張圖最后一次用廣探法，以便找出最小截量集運籌學-圖論最大流最小截量集的標號法舉例(s+,)(s+,6)(2,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5,2)(4+,2)運籌學-圖論(s+,)(s+,3)(2,3)最小截量集運籌學-圖論§5.5最小費用最大流問題

在實際的網(wǎng)絡系統(tǒng)中，當涉及到有關流的問題的時候，我們往往不僅僅考慮的是流量，還經(jīng)常要考慮費用的問題。比如一個鐵路系統(tǒng)的運輸網(wǎng)絡流，即要考慮網(wǎng)絡流的貨運量最大，又要考慮總費用最小。最小費用最大流問題就是要解決這一類問題。運籌學-圖論

我們首先考察，在一個網(wǎng)絡D中，當沿可行流f的一條增廣鏈μ，以調(diào)整量θ=1改進f，得到的新可行流f'的流量，有v(f

)=v(f)+1，而此時總費用b(f

)比b(f)增加了

設一個網(wǎng)絡D=（V，A，C），對于每一個弧(vi,vj)∈A,給定一個單位流量的費用bij0，網(wǎng)絡系統(tǒng)的最小費用最大流問題，是指要尋求一個最大流f，并且流的總費用達到最小。運籌學-圖論結(jié)論：如果可行流f

在流量為v(f)的所有可行流中的費用最小，并且是關于f的所有增廣鏈中的費用最小的增廣鏈，那么沿增廣鏈μ調(diào)整可行流f，得到的我們將叫做這條增廣鏈的費用。運籌學-圖論新可行流f

，也是流量為v(f

)的所有可行流中的最小費用流。依次類推，當f是最大流時，就是所要求的最小費用最大流。

顯然，零流f={0}是流量為0的最小費用流。尋求最小費用流，總可以從零流f={0}開始。下面的問題是：如果已知f是流量為v(f)的最小費用流，那么就要去尋找關于f的最小費用增廣鏈。運籌學-圖論

對此，重新構(gòu)造一個賦權(quán)有向圖M(f)，其頂點是原網(wǎng)絡D的頂點，而將D中的每一條弧(vi,vj)變成兩個相反方向的弧（vi,vj）和(vj,vi)，并且定義M(f)中弧的權(quán)wij為：并且將權(quán)為+∞的弧從M(f)

中略去。運籌學-圖論

這樣，在網(wǎng)絡D中尋找關于f的最小費用增廣鏈就等于價于在M(f)中尋求從vs到vt

的最短路。

算法開始，取零流f(0)

={0}.一般地，如果在第K-1步得到最小費用流f

(K-1),則構(gòu)造圖M(f(k-1))。在圖M(f(k-1))中，尋求從vs到vt的最短路。如果存在最短路，則f(k-1)就是最小費用最大流。如果存在最短路，則在原網(wǎng)絡D中得到相對應（一一對應）的增廣鏈μ0

運籌學-圖論在增廣鏈μ上對f(k–1)進行調(diào)整，取調(diào)整量令：得到一個新的可行流f(k)，在對f(k)重復以上的步驟，直到D中找不到相對應的增廣鏈時為止。運籌學-圖論

例求圖5.5.1所示網(wǎng)絡中的最小費用最大流，弧旁的權(quán)是（bij,cij）.(bij,cij)(1,8)(3,10)(2,4)(6,2)(1,7)(4,10)(2,5)v1v2vsv3vt圖5.5.1運籌學-圖論

解：（1）取初始可行流為零流f(0)={0},構(gòu)造賦權(quán)有向圖M(f(0)),求出從vs到vt的最短路(vs,v2,v1,vt),如圖5.5.1

a

中雙箭頭所示。(1)(3)(2)(6)(1)(4)(2)M(f(0))v1vsv2v3vt圖5.5.1a運籌學-圖論

（2）在原網(wǎng)絡D中，與這條最短路相對應的增廣鏈為μ=（vs

,v2

,v1

,vt）。（3）在μ上對f(0)={0}進行調(diào)整，取θ=5，得到新可行流f(1)，如圖5.5.1b所示。按照以上的算法，依次類推，可以得到f(1)，f(2)，f(3)，f(4)，流量分別為5，7，10，11，并且分別構(gòu)造相對應的賦權(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是最小費用最大流。運籌學-圖論(8,5)(10,0)(4,0)(2,0)(7,5)(10,0)(5,5)圖5.5.1bf(1),v(f(1))=5v1vsv2v2vt運籌學-圖論M(f(1))圖5.5.1cv1(2)(-1)v3(1)(3)(6)(1)(4)(-2)(-1)vsv2vt運籌學-圖論(2,0)(5,5)(8,5)(4,0)(7,7)(10,2)(10,0)圖5.5.1df(2),v(f(2))=7v1vsv2v3vt運籌學-圖論M(f(2)

)圖5.5.1e(1)(3)(2)(6)(-1)(4)(-2)(-1)(-4)v1vsv3vtv2運籌學-圖論(8,8)(10,3)(4,3)(2,0)(7,7)(10,2)(5,5)圖5.5.1ff(3),v(f(3))=10v1vsv2v3vt運籌學-圖論(-1)(3)(2)(6)(-1)(4)(-2)(-4)M(f(3))圖5.5.1g(-2)(-3)v1vsv2v3vt運籌學-圖論(8,8)(10,4)(4,4)(2,0)(7,7)(10,3)(5,4)圖5.5.1hf(4),v(f(4))=11v1vsv2v3vt運籌學-圖論(-1)(3)(-2)(6)(-1)(4)(2)(-4)M(f(4)

)圖5.5.1i(-2)(-3)v1vsv2v3vt運籌學-圖論ApplicationsofNetworkOptimization網(wǎng)絡最優(yōu)化模型的應用網(wǎng)絡在交通、電子和通訊網(wǎng)絡遍及我們?nèi)粘Ｉ畹母鱾€方面，網(wǎng)絡規(guī)劃也廣泛用于解決不同領域中的各種問題，如生產(chǎn)、分配、項目計劃、廠址選擇、資源管理和財務策劃等等。網(wǎng)絡規(guī)劃為描述系統(tǒng)各組成部分之間的關系提供了非常有效直觀和概念上的幫助，廣泛應用于科學、社會和經(jīng)濟活動的每個領域中。運籌學-圖論Networkrepresentation網(wǎng)絡表述這種描述還有其他應用嗎？想想看！運籌學-圖論TypesofNetworkOptimizationProblem網(wǎng)絡最優(yōu)化問題類型MinimumCostNetworkFlowModel

最小費用流問題

MaximumFlowProblems

最大流問題

ShortestPathProblem

最短路問題

MinimumSpanningTreeProblem

最小支撐樹問題

運籌學-圖論MinimumCostNetworkFlowModel最小費用流問題最小費用流問題的構(gòu)成：節(jié)點(nodes)（供應點、需求點、轉(zhuǎn)運點）?。╝rcs）

目標:通過網(wǎng)絡滿足需求提供供應， 最小化流的總成本運籌學-圖論Assumptions