《系統(tǒng)工程 圖與網(wǎng)絡(luò)分析課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《系統(tǒng)工程 圖與網(wǎng)絡(luò)分析課件（132頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 l8.1.1 用圖來(lái)描述實(shí)際問(wèn)題用圖來(lái)描述實(shí)際問(wèn)題 l8.1.2 圖的基本概念圖的基本概念 l8.1.3 圖的矩陣表示圖的矩陣表示 l小結(jié)小結(jié)山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.1 用圖來(lái)描述實(shí)際問(wèn)題8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 例例 82 五個(gè)球隊(duì)的比賽情況：五個(gè)球隊(duì)的比賽情況：山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.1 用圖來(lái)描述實(shí)際問(wèn)題8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 圖是反映對(duì)象之間關(guān)

2、系的一種工具。圖是反映對(duì)象之間關(guān)系的一種工具。 在一般情況下，圖中點(diǎn)的相對(duì)位置如何，點(diǎn)與點(diǎn)之間連線的長(zhǎng)短曲直，在一般情況下，圖中點(diǎn)的相對(duì)位置如何，點(diǎn)與點(diǎn)之間連線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系，并不是重要的。例如上面所說(shuō)的五個(gè)球隊(duì)的比賽對(duì)于反映對(duì)象之間的關(guān)系，并不是重要的。例如上面所說(shuō)的五個(gè)球隊(duì)的比賽情況也可以用下圖表示：情況也可以用下圖表示： 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.1 用圖來(lái)描述實(shí)際問(wèn)題8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 如果人們關(guān)心的是如果人們關(guān)心的是5個(gè)球隊(duì)比賽的勝負(fù)情況，那么上面的圖就表示不出來(lái)了。個(gè)球隊(duì)比賽的勝負(fù)情況，那么

3、上面的圖就表示不出來(lái)了。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.2 圖的基本概念8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 定義定義81 圖圖 是由一些點(diǎn)及一些點(diǎn)之間的連線（不帶箭頭或帶箭頭）所組成。是由一些點(diǎn)及一些點(diǎn)之間的連線（不帶箭頭或帶箭頭）所組成。 無(wú)向圖無(wú)向圖 由點(diǎn)和邊所構(gòu)成的圖（也簡(jiǎn)稱為圖），記為由點(diǎn)和邊所構(gòu)成的圖（也簡(jiǎn)稱為圖），記為G = (V, E )，其中，其中V，E分別是分別是G的頂點(diǎn)集合和邊集合的頂點(diǎn)集合和邊集合。 有向圖有向圖 由點(diǎn)和弧所構(gòu)成的圖稱為有向圖，記為由點(diǎn)和弧所構(gòu)成的圖稱為有向圖，記為D = (V, A )，其中其中V, A

4、分別表示分別表示D的頂點(diǎn)集合和弧集合。的頂點(diǎn)集合和弧集合。 我們把兩點(diǎn)之間的不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。我們把兩點(diǎn)之間的不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。 一一條條連連接接點(diǎn)點(diǎn)iv,jvV 的的邊邊 e 記記為為 e = iv,jv 或或 e = jv,iv 。 一條方向是從一條方向是從iv指向指向jv的的弧弧 a 記為記為 a = (iv,jv )。iv稱為稱為 a 的始點(diǎn)，的始點(diǎn)，jv稱為稱為 a 的終點(diǎn)。的終點(diǎn)。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.2 圖的基本概念8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 定義定義82頂點(diǎn)數(shù)和

5、邊數(shù)頂點(diǎn)數(shù)和邊數(shù) 圖圖G = (V, E ) 中，中，V中元素的個(gè)數(shù)稱為圖中元素的個(gè)數(shù)稱為圖G的頂點(diǎn)數(shù)，記作的頂點(diǎn)數(shù)，記作p (G )或簡(jiǎn)記為或簡(jiǎn)記為p；E中元素的個(gè)數(shù)稱為圖中元素的個(gè)數(shù)稱為圖G 的邊數(shù)，記作的邊數(shù)，記作q (G )，或簡(jiǎn)記為，或簡(jiǎn)記為q。具有相同端點(diǎn)的邊稱為具有相同端點(diǎn)的邊稱為多重邊或平行邊多重邊或平行邊；兩個(gè)端點(diǎn)落在一個(gè)頂點(diǎn)的邊稱為；兩個(gè)端點(diǎn)落在一個(gè)頂點(diǎn)的邊稱為環(huán)環(huán)。含有多重邊的圖稱為含有多重邊的圖稱為多重圖多重圖；無(wú)環(huán)也無(wú)多重邊的圖稱為；無(wú)環(huán)也無(wú)多重邊的圖稱為簡(jiǎn)單圖。簡(jiǎn)單圖。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.2 圖的基本概念8.1

6、圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 p (G ) = 6 ，q (G ) = 8；e3 = 4v,3v，3v與與4v是是 e3的端點(diǎn)，的端點(diǎn)，e3是點(diǎn)是點(diǎn)3v和和4v的關(guān)聯(lián)邊；的關(guān)聯(lián)邊；2v與與5v是鄰點(diǎn)，是鄰點(diǎn)，e3與與 e2是鄰邊；是鄰邊；e7與與 e8是多重邊，是多重邊，e4是一個(gè)環(huán)是一個(gè)環(huán)。 如圖如圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.2 圖的基本概念8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 定理定理81 圖圖G = ( V , E )中，所有頂點(diǎn)的次之和是邊數(shù)的兩倍。即中，所有頂點(diǎn)的次之和是邊數(shù)的兩倍。即Vviiqvd2)(定理定理82 任一

7、圖任一圖G中，奇點(diǎn)的個(gè)數(shù)為偶數(shù)。中，奇點(diǎn)的個(gè)數(shù)為偶數(shù)。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.2 圖的基本概念8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 定義定義83若鏈若鏈中，所含的邊互不相同，則稱中，所含的邊互不相同，則稱為為簡(jiǎn)單鏈簡(jiǎn)單鏈； 若鏈若鏈中，頂點(diǎn)中，頂點(diǎn)21,iivv, , k1k,iivv都不相同，則稱都不相同，則稱為為初等鏈初等鏈。 若回路中的弧都互不相同，則稱為若回路中的弧都互不相同，則稱為簡(jiǎn)單回路簡(jiǎn)單回路；若回路中除始點(diǎn)、終；若回路中除始點(diǎn)、終點(diǎn)外的頂點(diǎn)都互不相同，則稱為點(diǎn)外的頂點(diǎn)都互不相同，則稱為初等回路初等回路。 山東理工大學(xué)管理學(xué)

8、院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.2 圖的基本概念8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 定義定義84一個(gè)圖一個(gè)圖G的任意兩個(gè)頂點(diǎn)，如果至少有一條通路將它們連接起來(lái)，的任意兩個(gè)頂點(diǎn)，如果至少有一條通路將它們連接起來(lái)，則這個(gè)圖則這個(gè)圖G就稱為就稱為連通圖連通圖，否則就稱為，否則就稱為不連通圖不連通圖。若若G是不連通圖，它的每個(gè)連通的部分稱為是不連通圖，它的每個(gè)連通的部分稱為G的一個(gè)的一個(gè)連通分圖連通分圖 (也簡(jiǎn)稱分圖也簡(jiǎn)稱分圖)。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.2 圖的基本概念8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 定義定義

9、85設(shè)設(shè) G = ( V, , E )，對(duì)任意一條邊，對(duì)任意一條邊 eE，如果相應(yīng)都有一個(gè)數(shù)值，如果相應(yīng)都有一個(gè)數(shù)值 w (e)與之對(duì)應(yīng)，則稱與之對(duì)應(yīng)，則稱 G 為為賦權(quán)圖賦權(quán)圖，w (e) 稱為邊稱為邊 e 的的權(quán)權(quán)。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.3 圖的矩陣表示8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 1關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣 0 1否則關(guān)聯(lián)與jiijevb稱矩陣稱矩陣B為圖為圖G的的關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣。 關(guān)聯(lián)矩陣描述了無(wú)向圖關(guān)聯(lián)矩陣描述了無(wú)向圖G的頂點(diǎn)與邊的關(guān)聯(lián)情況。的頂點(diǎn)與邊的關(guān)聯(lián)情況。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)

10、分析l8.1.3 圖的矩陣表示8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 例如例如 無(wú)向圖無(wú)向圖G10000001110000001111000001110101001)( 543217654321vvvvvGBeeeeeee1關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣其關(guān)聯(lián)矩陣如下：其關(guān)聯(lián)矩陣如下：山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.3 圖的矩陣表示8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 0 1 1不關(guān)聯(lián)與的終點(diǎn)為的起點(diǎn)為jijijiijavavavb1關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.3 圖的矩陣表示8.1 圖與網(wǎng)絡(luò)的

11、基本概念圖與網(wǎng)絡(luò)的基本概念 1關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣右圖所示的有向圖右圖所示的有向圖D1101100011011000000111011001)( 43217654321vvvvDBa aaaaaa其關(guān)聯(lián)矩陣為：其關(guān)聯(lián)矩陣為：山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.1.3 圖的矩陣表示8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 2鄰接矩陣鄰接矩陣稱矩陣稱矩陣A為圖為圖G的的鄰接矩陣。鄰接矩陣。 鄰接矩陣描述了圖的頂點(diǎn)與頂點(diǎn)之間的關(guān)系。鄰接矩陣描述了圖的頂點(diǎn)與頂點(diǎn)之間的關(guān)系。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)

12、的基本概念 l8.1.3 圖的矩陣表示2鄰接矩陣鄰接矩陣0100010101010210020101110)( 5432154321vvvvvGAvvvvv如圖所示，無(wú)向圖如圖所示，無(wú)向圖G其鄰接矩陣為：其鄰接矩陣為：山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.1 圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 l8.1.3 圖的矩陣表示2鄰接矩陣鄰接矩陣如圖所示，有向圖如圖所示，有向圖D0101100101001010)( 43214321vvvvDAvvvv其鄰接矩陣為：其鄰接矩陣為：山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.2 最小支撐樹問(wèn)題 l8.2

13、.1 樹及其性質(zhì)l8.2.2 圖的支撐樹l8.2.3 最小支撐樹問(wèn)題l作業(yè)山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.2.1 樹及其性質(zhì)8.2 最小支撐樹問(wèn)題 一個(gè)無(wú)圈的連通圖稱為一個(gè)無(wú)圈的連通圖稱為樹樹，通常以，通常以T 表示。表示。 1. 樹的定義樹的定義2. 樹的性質(zhì)樹的性質(zhì)（1）具有具有n個(gè)頂點(diǎn)的樹，其邊數(shù)恰好為個(gè)頂點(diǎn)的樹，其邊數(shù)恰好為n-1條。條。（2）樹的任意兩個(gè)頂點(diǎn)之間有且僅有一條鏈。樹的任意兩個(gè)頂點(diǎn)之間有且僅有一條鏈。（3）在樹在樹T中去掉任一條邊，則中去掉任一條邊，則T成為不連通圖。成為不連通圖。（4）在樹在樹T中不相鄰的兩個(gè)頂點(diǎn)間添上一條邊，則恰好得

14、到一個(gè)圈。中不相鄰的兩個(gè)頂點(diǎn)間添上一條邊，則恰好得到一個(gè)圈。進(jìn)一步地說(shuō)，如果再?gòu)倪@個(gè)圈上任意去掉一條邊，可以得到一個(gè)樹。進(jìn)一步地說(shuō)，如果再?gòu)倪@個(gè)圈上任意去掉一條邊，可以得到一個(gè)樹。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.2.2 圖的支撐樹8.2 最小支撐樹問(wèn)題 1. 支撐樹的定義支撐樹的定義如圖如圖其支撐樹為其支撐樹為山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.2.2 圖的支撐樹8.2 最小支撐樹問(wèn)題 2. 判斷一個(gè)圖判斷一個(gè)圖G有支撐樹的充要條件有支撐樹的充要條件 定理定理 圖圖G有支撐樹的充分必要條件是圖有支撐樹的充分必要條件是圖G是連通

15、的。是連通的。 若若G含圈，從圈中任意地去掉一條邊，得到圖含圈，從圈中任意地去掉一條邊，得到圖G的一個(gè)支撐子圖的一個(gè)支撐子圖G1。如果。如果G1不含圈，那么不含圈，那么G1 是是G的一個(gè)支撐樹；如果的一個(gè)支撐樹；如果G1仍含圈，那仍含圈，那么從么從G1中任取一個(gè)圈，從圈中再任意去掉一條邊，得到圖中任取一個(gè)圈，從圈中再任意去掉一條邊，得到圖G的一個(gè)的一個(gè)支撐子圖支撐子圖G2 ，如此重復(fù)，最終可以得到，如此重復(fù)，最終可以得到G的一個(gè)支撐子圖的一個(gè)支撐子圖GK ，它，它是連通的，并且不含圈，于是是連通的，并且不含圈，于是GK是是G的一個(gè)支撐樹。的一個(gè)支撐樹。必要性必要性是顯然的。是顯然的。證明證明充

16、分性充分性設(shè)圖設(shè)圖G是連通圖是連通圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.2.2 圖的支撐樹8.2 最小支撐樹問(wèn)題 3. 尋求連通圖的支撐樹的方法尋求連通圖的支撐樹的方法（1）破圈法）破圈法 就是在圖就是在圖G中任取一個(gè)圈，從圈中去掉一邊，對(duì)余下的圖中任取一個(gè)圈，從圈中去掉一邊，對(duì)余下的圖重復(fù)這個(gè)步驟，直到不含圈時(shí)為止，即得到圖重復(fù)這個(gè)步驟，直到不含圈時(shí)為止，即得到圖G的的一個(gè)支撐樹。一個(gè)支撐樹。v1v2v3v4v5v6651572344W(T)=5+1+2+3+4=15山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.2.2 圖的支撐樹8.2

17、最小支撐樹問(wèn)題 3. 尋求連通圖的支撐樹的方法尋求連通圖的支撐樹的方法(2)避圈法避圈法 任取一條邊任取一條邊e1，找一條與，找一條與e1不構(gòu)成圈的邊不構(gòu)成圈的邊e2，再找一條與，再找一條與e1, e2不構(gòu)成圈的邊不構(gòu)成圈的邊e3，一般，設(shè)已有，一般，設(shè)已有e1, e2, eK ，找一條與，找一條與e1, e2, eK 中的任何一些邊不構(gòu)成圈的邊中的任何一些邊不構(gòu)成圈的邊eK+1。重復(fù)這個(gè)過(guò)程，。重復(fù)這個(gè)過(guò)程， 直到不能進(jìn)行直到不能進(jìn)行為止，這時(shí)即得到一個(gè)支撐樹。為止，這時(shí)即得到一個(gè)支撐樹。v2v1v3v4v5v2v1v3v4v5山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8

18、.2 最小支撐樹問(wèn)題 l8.2.3 最小支撐樹問(wèn)題(1)支撐樹的權(quán)支撐樹的權(quán) 設(shè)賦權(quán)連通圖設(shè)賦權(quán)連通圖G = (V, E，W)， 如果如果T(V, E)是是G的一個(gè)支撐樹，稱的一個(gè)支撐樹，稱E中所有邊的權(quán)之和為支撐樹中所有邊的權(quán)之和為支撐樹T的權(quán)，記為的權(quán)，記為w(T) 。(2)最小支撐樹最小支撐樹如果支撐樹如果支撐樹T*的權(quán)是的權(quán)是G的所有支撐樹的權(quán)中最小者，則稱的所有支撐樹的權(quán)中最小者，則稱T*是是G的最小支的最小支撐樹撐樹(簡(jiǎn)稱簡(jiǎn)稱最小樹最小樹)。最小支撐樹問(wèn)題最小支撐樹問(wèn)題就是求一個(gè)賦權(quán)連通圖就是求一個(gè)賦權(quán)連通圖G的最小支撐樹。的最小支撐樹。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)

19、工程 圖與網(wǎng)絡(luò)分析l8.2.3 最小支撐樹問(wèn)題8.2 最小支撐樹問(wèn)題 (3)求最小支撐樹的方法求最小支撐樹的方法第一種方法第一種方法 破圈法破圈法 在連通圖在連通圖G中，任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊中，任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊(如果有兩條或如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條)。在余下的圖中，重。在余下的圖中，重復(fù)這個(gè)步驟，一直得到一個(gè)不含圈的圖為止。復(fù)這個(gè)步驟，一直得到一個(gè)不含圈的圖為止。v1v2v3v4v5v6651572344W(T)=5+1+2+3+4=15山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系

20、統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.2.3 最小支撐樹問(wèn)題8.2 最小支撐樹問(wèn)題 (3)求最小支撐樹的方法求最小支撐樹的方法第二種方法第二種方法 避圈法避圈法 在連通圖在連通圖G中，開始選一條最小權(quán)的邊，以后每一步中，總從未中，開始選一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈(每每一步中，如果有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一步中，如果有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一條一條)。重復(fù)下去，直到不存在與已選邊不構(gòu)成圈的邊為止。已選邊。重復(fù)下去，直到不存在與已選邊不構(gòu)成圈的邊

21、為止。已選邊與頂點(diǎn)構(gòu)成的圖與頂點(diǎn)構(gòu)成的圖T就是所求最小樹。就是所求最小樹。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.2 最小支撐樹問(wèn)題 v1v4v3v2v62515203091012例例 如圖如圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l作業(yè)8.2 最小支撐樹問(wèn)題 求下圖的最小支撐樹求下圖的最小支撐樹山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.3 最短路問(wèn)題 l8.3.1 最短路問(wèn)題的提出l8.3.2 最短路的算法l8.3.3 最短路問(wèn)題應(yīng)用舉例l作業(yè)山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.3.1

22、最短路問(wèn)題提出8.3 最短路問(wèn)題 1. 最短路問(wèn)題引例最短路問(wèn)題引例油油田田加加工工廠廠v1v2v3v4v5v6v9v7v8444444422266山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.3.1 最短路問(wèn)題提出8.3 最短路問(wèn)題 要求使管道總長(zhǎng)最短的鋪設(shè)方案。要求使管道總長(zhǎng)最短的鋪設(shè)方案。1. 引例引例 油田管道鋪設(shè)問(wèn)題油田管道鋪設(shè)問(wèn)題從圖中可以看出，可能的鋪設(shè)方案是很多的，如：從圖中可以看出，可能的鋪設(shè)方案是很多的，如： 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.3 最短路問(wèn)題 l8.3.1 最短路問(wèn)題提出2. 最短路問(wèn)題的定義最短路問(wèn)題的

23、定義在賦權(quán)有向圖在賦權(quán)有向圖D=（V，A，W）中，指定兩點(diǎn)）中，指定兩點(diǎn)vs、vt 作為始點(diǎn)和終點(diǎn)。作為始點(diǎn)和終點(diǎn)。設(shè)設(shè)P是是D中從中從vs到到vt的一條路，的一條路，路路P的權(quán)的權(quán)是是P中所有弧的權(quán)之和。記為中所有弧的權(quán)之和。記為W(P)最短路問(wèn)題最短路問(wèn)題就是要在所有從就是要在所有從vs到到vt的路的路P中，求一條權(quán)最小的路中，求一條權(quán)最小的路P0。即。即PvvijjiPW),()()(min)(0PWPWP山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.3 最短路問(wèn)題 l8.3.2 最短路問(wèn)題的算法Dijkstra標(biāo)號(hào)算法標(biāo)號(hào)算法適用范圍適用范圍：0ij基本思路基本思路

24、:從起點(diǎn)從起點(diǎn)vs出發(fā)出發(fā),逐步向外探尋，對(duì)于某一個(gè)結(jié)點(diǎn)逐步向外探尋，對(duì)于某一個(gè)結(jié)點(diǎn)vi標(biāo)號(hào)：標(biāo)號(hào)： 固定標(biāo)號(hào)固定標(biāo)號(hào)P(vi) 或或 臨時(shí)標(biāo)號(hào)臨時(shí)標(biāo)號(hào)T(vi) 主要步驟：開始：P(vs)=0，T(vi)=+ Step1:修改臨時(shí)標(biāo)號(hào) Step2:變臨時(shí)標(biāo)號(hào)為固定標(biāo)號(hào)山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.3.2 最短路問(wèn)題的算法8.3 最短路問(wèn)題 用用Dijkstra標(biāo)號(hào)算法求下列無(wú)向圖中頂點(diǎn)到頂點(diǎn)標(biāo)號(hào)算法求下列無(wú)向圖中頂點(diǎn)到頂點(diǎn)6的最短距離及其路線。的最短距離及其路線。 解解 首先給頂點(diǎn)首先給頂點(diǎn)1標(biāo)上固定標(biāo)標(biāo)上固定標(biāo)號(hào)號(hào)0，即，即P ( 1 ) = 0，其余

25、頂點(diǎn)，其余頂點(diǎn)標(biāo)上臨時(shí)標(biāo)號(hào)，且標(biāo)上臨時(shí)標(biāo)號(hào)，且T ( j ) = ( j =2,3,6)。 （1）與頂點(diǎn)）與頂點(diǎn)1直接相連又為臨時(shí)標(biāo)號(hào)的頂直接相連又為臨時(shí)標(biāo)號(hào)的頂點(diǎn)是點(diǎn)是2和和3，這兩個(gè)頂點(diǎn)的臨時(shí)標(biāo)號(hào)改為，這兩個(gè)頂點(diǎn)的臨時(shí)標(biāo)號(hào)改為Step1T ( 2 ) = 4T ( 3 ) = 3山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.3.2 最短路問(wèn)題的算法8.3 最短路問(wèn)題 （2）在所有臨時(shí)標(biāo)號(hào)中，最小的為）在所有臨時(shí)標(biāo)號(hào)中，最小的為T ( 3 ) 3，于是令，于是令P ( 3 ) 3，即，即頂點(diǎn)頂點(diǎn)3獲得固定標(biāo)號(hào)獲得固定標(biāo)號(hào)3。Step2（1）與頂點(diǎn)）與頂點(diǎn)3直接相連又為臨

26、時(shí)標(biāo)號(hào)的頂點(diǎn)是直接相連又為臨時(shí)標(biāo)號(hào)的頂點(diǎn)是2和和5，修改這兩個(gè)頂點(diǎn)，修改這兩個(gè)頂點(diǎn)的臨時(shí)標(biāo)號(hào)為的臨時(shí)標(biāo)號(hào)為T ( 2 ) = 4T ( 5 ) = 5（2）在所有臨時(shí)標(biāo)號(hào)中，）在所有臨時(shí)標(biāo)號(hào)中，T ( 2 ) 4最小，于是有最小，于是有P (2 ) 4，即頂點(diǎn)，即頂點(diǎn)2獲得固定標(biāo)號(hào)獲得固定標(biāo)號(hào)4。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.3.2 最短路問(wèn)題的算法8.3 最短路問(wèn)題 Step3（1）對(duì)頂點(diǎn)）對(duì)頂點(diǎn)2有有T ( 4 ) = 7T ( 5 ) = 5（2）在所有臨時(shí)標(biāo)號(hào)中，）在所有臨時(shí)標(biāo)號(hào)中，T ( 5 ) 5最小，于是有最小，于是有P (5 ) 5。Ste

27、p4（1）對(duì)頂點(diǎn)）對(duì)頂點(diǎn)5有有T ( 4 ) = 7T ( 6 ) = 9（2）在所有臨時(shí)標(biāo)號(hào)中，）在所有臨時(shí)標(biāo)號(hào)中，T ( 4 ) 7 最小，令最小，令P (4 ) 7。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.3.2 最短路問(wèn)題的算法8.3 最短路問(wèn)題 Step5（1）對(duì)頂點(diǎn)）對(duì)頂點(diǎn)4有有T ( 6 ) =9（2）顯然有）顯然有P (6 ) 9。頂點(diǎn)頂點(diǎn)6 獲得固定標(biāo)號(hào)，算法到此結(jié)束。獲得固定標(biāo)號(hào)，算法到此結(jié)束。 頂點(diǎn)頂點(diǎn)1到頂點(diǎn)到頂點(diǎn)6的最短距離為的最短距離為9。從頂點(diǎn)從頂點(diǎn)6反向追蹤就可以找到最短路線：反向追蹤就可以找到最短路線：1 3 5 6 和和 1 2

28、5 6 ，它們的最短距離都為，它們的最短距離都為9。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.3 最短路問(wèn)題 l8.3.3 最短路問(wèn)題應(yīng)用舉例設(shè)備更新問(wèn)題設(shè)備更新問(wèn)題時(shí)間第1年第2年第3年第4年第5年價(jià)格1111121213維修費(fèi)用5681118如何制定使得總的支付費(fèi)用最少的設(shè)備更新計(jì)劃如何制定使得總的支付費(fèi)用最少的設(shè)備更新計(jì)劃 ？可以把這個(gè)問(wèn)題化為最短路問(wèn)題可以把這個(gè)問(wèn)題化為最短路問(wèn)題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析v1 v4 v6總費(fèi)用為總費(fèi)用為53萬(wàn)元萬(wàn)元v3v6v4v2v1v5224130162216173059412331182

29、317v1 v3 v68.3 最短路問(wèn)題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.3 最短路問(wèn)題 l8.3.3 最短路問(wèn)題應(yīng)用舉例選址問(wèn)題選址問(wèn)題 已知有已知有6個(gè)村莊，各村莊間的距離如下圖所示，個(gè)村莊，各村莊間的距離如下圖所示，各村的小學(xué)生人數(shù)如下表所示?，F(xiàn)在計(jì)劃在這片各村的小學(xué)生人數(shù)如下表所示?，F(xiàn)在計(jì)劃在這片區(qū)域內(nèi)建造一所醫(yī)院和一所小學(xué)，問(wèn)醫(yī)院應(yīng)建在區(qū)域內(nèi)建造一所醫(yī)院和一所小學(xué)，問(wèn)醫(yī)院應(yīng)建在哪個(gè)村莊才能使最遠(yuǎn)村莊到醫(yī)院看病所走的總路哪個(gè)村莊才能使最遠(yuǎn)村莊到醫(yī)院看病所走的總路程最短程最短?又問(wèn)小學(xué)建在哪個(gè)村莊才能使學(xué)生上學(xué)又問(wèn)小學(xué)建在哪個(gè)村莊才能使學(xué)生上學(xué)走的總路程

30、最短。走的總路程最短。 v2 。 。v4 2 8 6 v1。 4 1 。v6 7 3 v3 。 。v5 3 1 6 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.3 最短路問(wèn)題 解：解：03459113012684101575210469654021187620 654321654321vvvvvvSvvvvvv11967811故：醫(yī)院應(yīng)建在第三個(gè)村莊，故：醫(yī)院應(yīng)建在第三個(gè)村莊，其它村莊到該村莊的距離最遠(yuǎn)為其它村莊到該村莊的距離最遠(yuǎn)為6 。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.3 最短路問(wèn)題 設(shè)設(shè)想想小小學(xué)學(xué)建建立立在在jv，則則其其它它村村莊莊

31、的的小小學(xué)學(xué)生生們們所所走走的的總總路路程程就就是是 50S1j + 40S2j + 60S3j+ 20S4j+ 70S5j + 90S6j 對(duì)每一點(diǎn)求出這個(gè)值，它們的最小值所對(duì)應(yīng)的對(duì)每一點(diǎn)求出這個(gè)值，它們的最小值所對(duì)應(yīng)的jv這相當(dāng)于將矩陣這相當(dāng)于將矩陣S中每一行元素分別乘上對(duì)應(yīng)村莊里小學(xué)生的人數(shù)，然后分中每一行元素分別乘上對(duì)應(yīng)村莊里小學(xué)生的人數(shù)，然后分別求出各列的和，得矩陣別求出各列的和，得矩陣D 就是所要選擇的最佳位置。就是所要選擇的最佳位置。02703604508109902100701404205608020020100140300120600240360360240200160080

32、5504003503001000 654321654321vvvvvvDvvvvvv2130 1670 1070 1040 1050 1500 故：小學(xué)應(yīng)建在第四個(gè)村莊。故：小學(xué)應(yīng)建在第四個(gè)村莊。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l作業(yè)8.3 最短路問(wèn)題 求下圖中的點(diǎn)求下圖中的點(diǎn)1到點(diǎn)到點(diǎn)7的最短距離和最短路線。的最短距離和最短路線。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.4 網(wǎng)絡(luò)最大流問(wèn)題 l8.4.1 最大流問(wèn)題的數(shù)學(xué)模型l8.4.2 最大流問(wèn)題的解法l8.4.3 最大流問(wèn)題應(yīng)用舉例l作業(yè)山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程

33、 圖與網(wǎng)絡(luò)分析l8.4.1 最大流問(wèn)題的數(shù)學(xué)模型8.4 網(wǎng)絡(luò)最大流問(wèn)題 （1）網(wǎng)絡(luò)）網(wǎng)絡(luò) 1. 基本概念基本概念山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.4.1 最大流問(wèn)題的數(shù)學(xué)模型8.4 網(wǎng)絡(luò)最大流問(wèn)題 （2）網(wǎng)絡(luò)的流）網(wǎng)絡(luò)的流 1. 基本概念基本概念山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.4 網(wǎng)絡(luò)最大流問(wèn)題 （3）可行流）可行流 設(shè)設(shè)f 為一網(wǎng)絡(luò)流，當(dāng)為一網(wǎng)絡(luò)流，當(dāng)f 滿足下列條件時(shí)，稱為可行流。滿足下列條件時(shí)，稱為可行流。 容容量量限限制制條條件件 對(duì)對(duì)每每一一弧弧 (iv,jv)A，有有 0 fij cij 0),(),(AvvjiA

34、vvijijjiff )(),(),(fvffAvvjsAvvsjsjjs )(),(),(fvffAvvjtAvvtjtjjt式中，式中，v ( f )稱為這個(gè)可行流的流量，即發(fā)點(diǎn)的凈輸出量或收點(diǎn)的凈輸入量。稱為這個(gè)可行流的流量，即發(fā)點(diǎn)的凈輸出量或收點(diǎn)的凈輸入量。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析（4）最大流最大流 網(wǎng)絡(luò)網(wǎng)絡(luò)D上流量上流量v ( f )達(dá)到最大的可行流，稱為該網(wǎng)絡(luò)的最大流。達(dá)到最大的可行流，稱為該網(wǎng)絡(luò)的最大流。最大流問(wèn)題其實(shí)是一個(gè)特殊的線性規(guī)劃問(wèn)題。最大流問(wèn)題其實(shí)是一個(gè)特殊的線性規(guī)劃問(wèn)題。 Ajvivijcijfi=t fvtsii=sfvjifi

35、jftsfvMax),( 0)()(),( 0 )( )( . .)( 2. 最大流問(wèn)題的數(shù)學(xué)模型：最大流問(wèn)題的數(shù)學(xué)模型：8.4 網(wǎng)絡(luò)最大流問(wèn)題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.4 網(wǎng)絡(luò)最大流問(wèn)題 l8.4.2 最大流問(wèn)題的解法1. 有關(guān)的概念有關(guān)的概念飽和?。猴柡突。篺ij = cij 非飽和?。悍秋柡突。?fij0 前向弧前向?。ㄕ蚧。洖椋ㄕ蚧。?，記為+ ：與鏈的方向一致的弧與鏈的方向一致的弧 后向弧后向弧（反向?。?，記為（反向?。?，記為- ：與鏈的方向相反的弧與鏈的方向相反的弧山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.4

36、網(wǎng)絡(luò)最大流問(wèn)題 l8.4.2 最大流問(wèn)題的解法1. 有關(guān)的概念有關(guān)的概念增廣鏈增廣鏈設(shè)設(shè)f = fij是一個(gè)可行流，是一個(gè)可行流，是從是從vs到到vt的一條鏈。若的一條鏈。若滿足下列條件滿足下列條件 ： （1）前向?。┣跋蚧?中的每一弧都是非飽和弧，即中的每一弧都是非飽和弧，即 （2）后向?。┖笙蚧?中的每一弧都是非零流弧，即中的每一弧都是非零流弧，即ijijcf0則稱則稱是關(guān)于是關(guān)于 可行流可行流f 的一條增廣鏈。的一條增廣鏈。ijijcf 0山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.4 網(wǎng)絡(luò)最大流問(wèn)題 l8.4.2 最大流問(wèn)題的解法1. 有關(guān)的概念有關(guān)的概念截集截集

37、截量截量),(),(1111),(VVvvijjicVVc山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.4.2 最大流問(wèn)題的解法8.4 網(wǎng)絡(luò)最大流問(wèn)題 2. 判斷一個(gè)可行流是否是最大流的條件判斷一個(gè)可行流是否是最大流的條件定理定理 可行流可行流 f 是最大流的充要條件是不存在關(guān)于是最大流的充要條件是不存在關(guān)于f 的增廣鏈。的增廣鏈。此定理為我們提供了尋求網(wǎng)絡(luò)中最大流的一個(gè)方法：此定理為我們提供了尋求網(wǎng)絡(luò)中最大流的一個(gè)方法：若給了一個(gè)可行流若給了一個(gè)可行流 f，只要去判斷，只要去判斷D中有無(wú)關(guān)于中有無(wú)關(guān)于f 的增廣鏈。如果有增廣鏈，的增廣鏈。如果有增廣鏈，則可以改進(jìn)則可以改

38、進(jìn) f，得到一個(gè)流量增大的新的可行流。如果沒有增廣鏈，則得到，得到一個(gè)流量增大的新的可行流。如果沒有增廣鏈，則得到最大流。最大流。最大流最小截量定理：最大流最小截量定理： 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.4 網(wǎng)絡(luò)最大流問(wèn)題 l8.4.2 最大流問(wèn)題的解法3. 求網(wǎng)絡(luò)最大流的標(biāo)號(hào)算法求網(wǎng)絡(luò)最大流的標(biāo)號(hào)算法FordFulkerson 算法：算法：從一個(gè)可行流從一個(gè)可行流f = fij出發(fā)，經(jīng)過(guò)出發(fā)，經(jīng)過(guò)標(biāo)號(hào)過(guò)程標(biāo)號(hào)過(guò)程與與調(diào)整過(guò)程調(diào)整過(guò)程。（1）標(biāo)號(hào)過(guò)程）標(biāo)號(hào)過(guò)程 尋找增廣鏈的過(guò)程。尋找增廣鏈的過(guò)程。（2）調(diào)整過(guò)程）調(diào)整過(guò)程 沿著增廣鏈調(diào)整可行流。沿著增廣鏈調(diào)整可

39、行流。令調(diào)整量令調(diào)整量是是l(vt)，即，即vt的第二個(gè)標(biāo)號(hào)。的第二個(gè)標(biāo)號(hào)。 ),( ,),( ,),( , jiijjiijjiijijvvfvvfvvff山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.4 網(wǎng)絡(luò)最大流問(wèn)題 l8.4.3 最大流問(wèn)題的應(yīng)用舉例例例 用標(biāo)號(hào)法求如下網(wǎng)絡(luò)的最大流，弧旁的數(shù)為容量。用標(biāo)號(hào)法求如下網(wǎng)絡(luò)的最大流，弧旁的數(shù)為容量。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.4 網(wǎng)絡(luò)最大流問(wèn)題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.4 網(wǎng)絡(luò)最大流問(wèn)題 （1）標(biāo)號(hào)過(guò)程。針對(duì)當(dāng)前可行流（）標(biāo)號(hào)過(guò)程。針對(duì)當(dāng)前可

40、行流（v ( f ) = 8）尋找增廣鏈。）尋找增廣鏈。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.4 網(wǎng)絡(luò)最大流問(wèn)題 （2）調(diào)整過(guò)程）調(diào)整過(guò)程經(jīng)檢查，標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，算法終止，得到最大流如上圖所示。經(jīng)檢查，標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，算法終止，得到最大流如上圖所示。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l作業(yè)8.4 網(wǎng)絡(luò)最大流問(wèn)題 求如下網(wǎng)絡(luò)的最大流（弧上的數(shù)字為容量）。求如下網(wǎng)絡(luò)的最大流（弧上的數(shù)字為容量）。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.5 最小費(fèi)用最大流問(wèn)題 l8.5.1 問(wèn)題描述l8.5.2 最小費(fèi)用最大

41、流算法l8.5.3 應(yīng)用舉例山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.5.1 問(wèn)題描述8.5 最小費(fèi)用最大流問(wèn)題 Avvijijjifbfb),()(求求b ( f ) 為最小且流量為某確定值為最小且流量為某確定值v ( f )的可行流問(wèn)題，稱為最小費(fèi)用流問(wèn)題；的可行流問(wèn)題，稱為最小費(fèi)用流問(wèn)題；求求b ( f ) 為最小且流量為最小且流量v ( f ) 為最大的問(wèn)題，稱為為最大的問(wèn)題，稱為最小費(fèi)用最大流問(wèn)題最小費(fèi)用最大流問(wèn)題。 如果把最小費(fèi)用看成約束條件，和最大流問(wèn)題一樣，最小費(fèi)用流問(wèn)題也如果把最小費(fèi)用看成約束條件，和最大流問(wèn)題一樣，最小費(fèi)用流問(wèn)題也是一個(gè)線性規(guī)劃問(wèn)題

42、，并且求最小費(fèi)用流實(shí)際上是求該線性規(guī)劃問(wèn)題的可行是一個(gè)線性規(guī)劃問(wèn)題，并且求最小費(fèi)用流實(shí)際上是求該線性規(guī)劃問(wèn)題的可行解，求最小費(fèi)用最大流問(wèn)題實(shí)際上是求該線性規(guī)劃問(wèn)題的最優(yōu)解。解，求最小費(fèi)用最大流問(wèn)題實(shí)際上是求該線性規(guī)劃問(wèn)題的最優(yōu)解。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.5.2 最小費(fèi)用最大流的算法8.5 最小費(fèi)用最大流問(wèn)題 最小費(fèi)用最大流的算法通常采用對(duì)偶算法，其具體算法步驟如下：最小費(fèi)用最大流的算法通常采用對(duì)偶算法，其具體算法步驟如下：min),(minmin11kijkijijffc山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.5 最小費(fèi)用

43、最大流問(wèn)題 ),( ,),( ,),( ,111jikijjikijjikijkijvvfvvfvvff山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l8.5.3 應(yīng)用實(shí)例8.5 最小費(fèi)用最大流問(wèn)題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.5 最小費(fèi)用最大流問(wèn)題 解解 （1）取取初初始始可可行行流流 f 0 = 0，構(gòu)構(gòu)造造相相應(yīng)應(yīng)的的費(fèi)費(fèi)用用網(wǎng)網(wǎng)絡(luò)絡(luò) w ( f 0 )，如如下下圖圖所所示示。 圖圖 (a) 費(fèi)用網(wǎng)絡(luò)圖費(fèi)用網(wǎng)絡(luò)圖w ( f 0 )山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.5 最小費(fèi)用最大流問(wèn)題 圖圖 (b) 流

44、量網(wǎng)絡(luò)流量網(wǎng)絡(luò)D ( f 1 ) 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.5 最小費(fèi)用最大流問(wèn)題 （3） 再再構(gòu)構(gòu)造造與與 D ( f 1 )相相對(duì)對(duì)應(yīng)應(yīng)的的費(fèi)費(fèi)用用網(wǎng)網(wǎng)絡(luò)絡(luò) w ( f 1 )， 用用標(biāo)標(biāo)號(hào)號(hào)法法求求sv到到tv的的最最短短路路，如如圖圖中中雙雙線線所所示示：sv2v3vtv。 圖圖 (c) 費(fèi)用網(wǎng)絡(luò)圖費(fèi)用網(wǎng)絡(luò)圖w ( f 1 )山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.5 最小費(fèi)用最大流問(wèn)題 圖圖 (d) 流量網(wǎng)絡(luò)流量網(wǎng)絡(luò)D ( f 2 ) 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.5 最小費(fèi)用最大流

45、問(wèn)題 （4） 再再構(gòu)構(gòu)造造與與 D ( f 2 )相相對(duì)對(duì)應(yīng)應(yīng)的的費(fèi)費(fèi)用用網(wǎng)網(wǎng)絡(luò)絡(luò) w ( f 2 )， 用用標(biāo)標(biāo)號(hào)號(hào)法法求求sv到到tv的的最最短短路路，如如圖圖中中雙雙線線所所示示。 圖圖 (e) 費(fèi)用網(wǎng)絡(luò)圖費(fèi)用網(wǎng)絡(luò)圖 w ( f 2 )山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.5 最小費(fèi)用最大流問(wèn)題 在在流流量量網(wǎng)網(wǎng)絡(luò)絡(luò) D ( f 2 )中中與與這這條條最最短短路路相相對(duì)對(duì)應(yīng)應(yīng)的的增增廣廣鏈鏈為為 2 = (sv, ,1v, ,4v, ,tv)，在在增增廣廣鏈鏈 2上上對(duì)對(duì) f 2進(jìn)進(jìn)行行調(diào)調(diào)整整，調(diào)調(diào)整整量量 = 3，得得新新的的可可行行流流 f 3，其其流流

46、值值 v ( f 3) = 8，如如圖圖(f )所所示示。 圖圖 ( f ) 流量網(wǎng)絡(luò)流量網(wǎng)絡(luò)D ( f 3 ) 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.5 最小費(fèi)用最大流問(wèn)題 （5）構(gòu)構(gòu)造造費(fèi)費(fèi)用用網(wǎng)網(wǎng)絡(luò)絡(luò) w ( f 3 )，并并在在 w ( f 3 )上上求求最最短短路路，如如圖圖中中雙雙線線所所示示。 圖圖(g) 費(fèi)用網(wǎng)絡(luò)圖費(fèi)用網(wǎng)絡(luò)圖w ( f 3 )山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.5 最小費(fèi)用最大流問(wèn)題 在在 D ( f 3 )上上得得到到相相應(yīng)應(yīng)的的增增廣廣鏈鏈 3 = (sv, ,2v, ,3v, ,4v, ,tv)，在

47、在增增廣廣鏈鏈 3上上對(duì)對(duì) f 3進(jìn)進(jìn)行行調(diào)調(diào)整整，調(diào)調(diào)整整量量 = 4，得得新新的的可可行行流流 f 4，其其流流值值 v ( f 4) = 12，如如圖圖(h )所所示示。 圖圖 (h) 流量網(wǎng)絡(luò)流量網(wǎng)絡(luò)D ( f 4 ) 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.5 最小費(fèi)用最大流問(wèn)題 （6）作作 w ( f 4 )，如如圖圖所所示示，由由于于從從 w ( f 4)中中無(wú)無(wú)法法找找到到sv到到tv的的最最短短路路，說(shuō)說(shuō)明明在在 D ( f 4 )中中已已不不存存在在增增廣廣鏈鏈，求求解解終終止止。 故故 D ( f 4 )所所示示的的流流即即為為所所求求的的最最小

48、小費(fèi)費(fèi)用用最最大大流流。此此時(shí)時(shí) v ( f 4 ) = 12，最最小小費(fèi)費(fèi)用用為為 679。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析8.6 網(wǎng)絡(luò)計(jì)劃技術(shù) l8.6.1 網(wǎng)絡(luò)圖l8.6.2 網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線l8.6.3 網(wǎng)絡(luò)優(yōu)化l作業(yè)山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析(1) 又名：統(tǒng)籌方法又名：統(tǒng)籌方法 ，是一種科學(xué)的組織管理技術(shù)。，是一種科學(xué)的組織管理技術(shù)。(2) CPM (Critical Path Method，關(guān)鍵路線法) PERT （Program Evaluation and Review Technique， 計(jì)劃評(píng)審法） 借

49、助于網(wǎng)絡(luò)表示各項(xiàng)工作所需要的時(shí)間及各項(xiàng)工作間的相互關(guān)系，從而找出編制與執(zhí)行計(jì)劃的關(guān)鍵路線；同樣應(yīng)用網(wǎng)絡(luò)方法和網(wǎng)絡(luò)形式，但它注重于對(duì)各項(xiàng)任務(wù)安排的評(píng)價(jià)和審查。引言山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析(3) 應(yīng)用：工業(yè)、農(nóng)業(yè)、政府、科研、軍事應(yīng)用：工業(yè)、農(nóng)業(yè)、政府、科研、軍事 例：阿波羅載人登月計(jì)劃例：阿波羅載人登月計(jì)劃 海陸空聯(lián)合作戰(zhàn)計(jì)劃海陸空聯(lián)合作戰(zhàn)計(jì)劃 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 設(shè)備維修設(shè)備維修 新產(chǎn)品研制新產(chǎn)品研制山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析 1、結(jié)構(gòu)12A工序工序A事項(xiàng)：用事項(xiàng)：用 表示。表示。 不需人、財(cái)、物、工時(shí)不需人、財(cái)、物、工時(shí)

50、工序：用箭線工序：用箭線 或雙代號(hào)（或雙代號(hào)（i, j）表示。）表示。 需人、財(cái)、物、工時(shí)需人、財(cái)、物、工時(shí)工序工序(1, 2)緊前工序緊前工序 緊后工序緊后工序 虛工序虛工序8.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析(1) 從左從左右畫，只有一個(gè)右畫，只有一個(gè)，一個(gè)，一個(gè)。1234567824331212、畫法注意事項(xiàng)：8.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析(2) 兩事項(xiàng)間只有一個(gè)工序兩事項(xiàng)間只有一個(gè)工序Bij75A38.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分

51、析123(3) 不允許回路不允許回路8.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析(4) 虛工序的運(yùn)用虛工序的運(yùn)用120 解決畫法中問(wèn)題解決畫法中問(wèn)題 正確表達(dá)工序的前后銜接關(guān)系正確表達(dá)工序的前后銜接關(guān)系 表達(dá)平行作業(yè)表達(dá)平行作業(yè)8.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析1234657824031302018.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析124678243132018.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析ik75

52、0A3Bj8.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析例例1、有有A, B, C, D, 四道工序，四道工序，C在在 A, B完完工后開始，工后開始， D在在 B完工后開始。完工后開始。CABDABCD8.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析例例2、已知、已知ABCEA DC8.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析A BDCE8.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析3、畫圖基本步驟(1) 任務(wù)分解，工序明細(xì)表。任務(wù)分

53、解，工序明細(xì)表。(2) 畫圖。畫圖。(3) 工時(shí)、事項(xiàng)編號(hào)工時(shí)、事項(xiàng)編號(hào) ( (i , j)工序需工序需i j )8.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析例例1、工序工序 內(nèi)容內(nèi)容 工時(shí)工時(shí)(天天) 緊前工序緊前工序 A 初步研究初步研究 1 / B 研究選點(diǎn)研究選點(diǎn) 2 A C 準(zhǔn)備調(diào)研方案準(zhǔn)備調(diào)研方案 4 A D 聯(lián)系調(diào)研點(diǎn)聯(lián)系調(diào)研點(diǎn) 2 B E 培訓(xùn)工作人員培訓(xùn)工作人員 3 B,C F 準(zhǔn)備表格準(zhǔn)備表格 1 C G 實(shí)地調(diào)研實(shí)地調(diào)研 5 D,E,F H 寫調(diào)研報(bào)告寫調(diào)研報(bào)告 2 G I 開會(huì)匯總開會(huì)匯總 3 H8.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工

54、大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析12325FE200C413DBAGHI123456789答案答案8.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析例2工序工序 緊前工序緊前工序 工時(shí)工時(shí)(天天) A / 2 B / 5 C A 5 D B 3 E C,D 9 F C ,D 2 G E 7 H E,F 6 I H 2 8.6.1 網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析123578462A5B5C3D9E2F7G6H2I工序工序 緊前工序緊前工序 工時(shí)工時(shí)(天天) A / 2 B / 5 C A 5 D

55、 B 3 E C,D 9 F C ,D 2 G E 7 H E,F 6 I H 2 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析課堂練習(xí)1工序工序 緊前工序緊前工序 工時(shí)工時(shí)(天天) A / 2 B / 3 C A,B 4 D B 1 E A 5 F C 3 G E,F 2 H D,F 7 I G,H 6 J I 5 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析 1 2 3 4 5 6 9 10 11 7 8答案：答案：A 2B 3E5C4F3D1H7G2I6J5山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析課堂練習(xí)2有有某某一一工工程程項(xiàng)項(xiàng)

56、目目的的活活動(dòng)動(dòng)（工工序序）明明細(xì)細(xì)表表如如下下表表： 工工序序 A B C D E F G H I J 緊緊前前工工序序 / A A A A B E F D,G C,H,I 所所需需時(shí)時(shí)間間(周周) 4 7 14 8 3 2 2 4 4 2 要要求求：（1）畫畫出出網(wǎng)網(wǎng)絡(luò)絡(luò)圖圖； （2）計(jì)計(jì)算算各各事事項(xiàng)項(xiàng)的的最最早早、最最遲遲開開始始時(shí)時(shí)間間； （3）找找出出關(guān)關(guān)鍵鍵路路線線。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析 1、關(guān)鍵路線356124543223312124612105613856工期為：工期為：T=12 (周周)多長(zhǎng)時(shí)間能夠完工？多長(zhǎng)時(shí)間能夠完工？8.6.

57、2 網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析幾個(gè)概念：幾個(gè)概念：1、網(wǎng)絡(luò)圖：只有一個(gè)始點(diǎn)和一個(gè)終點(diǎn)的有向圖。、網(wǎng)絡(luò)圖：只有一個(gè)始點(diǎn)和一個(gè)終點(diǎn)的有向圖。2、關(guān)鍵路線：網(wǎng)絡(luò)圖中從始點(diǎn)到終點(diǎn)的最長(zhǎng)路線。、關(guān)鍵路線：網(wǎng)絡(luò)圖中從始點(diǎn)到終點(diǎn)的最長(zhǎng)路線。3、工期：關(guān)鍵路線的路長(zhǎng)。、工期：關(guān)鍵路線的路長(zhǎng)。 總時(shí)差總時(shí)差為零的工序，開始和結(jié)束的時(shí)為零的工序，開始和結(jié)束的時(shí)間沒有一點(diǎn)機(jī)動(dòng)的余地。由這些工序所組間沒有一點(diǎn)機(jī)動(dòng)的余地。由這些工序所組成的路線就是網(wǎng)絡(luò)中的關(guān)鍵路線。成的路線就是網(wǎng)絡(luò)中的關(guān)鍵路線。P176 8.6.2 網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線網(wǎng)絡(luò)時(shí)間與關(guān)鍵

58、路線山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析2、事項(xiàng)時(shí)間參數(shù)計(jì)算（已知 T(i, j)=Tij ） (1) 事項(xiàng)最早時(shí)間事項(xiàng)最早時(shí)間TE(j)= TE(1)=0TE( j )=maxTE(i)+Tij i(3) 事項(xiàng)時(shí)差事項(xiàng)時(shí)差T(i)=TL(i)-TE(i)(2) 事項(xiàng)最遲時(shí)間事項(xiàng)最遲時(shí)間TL(i)=TL(n)= TE(n)TL(i)=minTL( j )- Tij j山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析124456352333205397121299750T=122、事項(xiàng)時(shí)間參數(shù)計(jì)算（已知 T(i, j)=Tij ） 山東理工大學(xué)管理學(xué)院山東

59、理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析12325132004CFEDBAGHI123456789013558131518T=18181513855510例例22、事項(xiàng)時(shí)間參數(shù)計(jì)算（已知 T(i, j)=Tij ） 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析課堂練習(xí)1工序工序 緊前工序緊前工序 工時(shí)工時(shí)(天天) A / 2 B / 3 C A,B 4 D B 1 E A 5 F C 3 G E,F 2 H D,F 7 I G,H 6 J I 5 （1）畫出網(wǎng)絡(luò)圖；）畫出網(wǎng)絡(luò)圖；（2）計(jì)算各事項(xiàng)的最）計(jì)算各事項(xiàng)的最 早、最遲開始時(shí)早、最遲開始時(shí) 間；間；（3）找出關(guān)鍵路線。）找

60、出關(guān)鍵路線。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析答案：答案： 1 2 3 4 5 6 9 10 11 7 8A 2B 3E5C4F3D1H7G2I6J5要求：（要求：（2）計(jì)算各事項(xiàng)的最早、最遲開始時(shí)間；）計(jì)算各事項(xiàng)的最早、最遲開始時(shí)間； （3）找出關(guān)鍵路線。）找出關(guān)鍵路線。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析課堂練習(xí)2有有某某一一工工程程項(xiàng)項(xiàng)目目的的活活動(dòng)動(dòng)（工工序序）明明細(xì)細(xì)表表如如下下表表： 工工序序 A B C D E F G H I J 緊緊前前工工序序 / A A A A B E F D,G C,H,I 所所需需時(shí)時(shí)間間(周周)

61、 4 7 14 8 3 2 2 4 4 2 要要求求：（1）畫畫出出網(wǎng)網(wǎng)絡(luò)絡(luò)圖圖； （2）計(jì)計(jì)算算各各事事項(xiàng)項(xiàng)的的最最早早、最最遲遲開開始始時(shí)時(shí)間間； （3）找找出出關(guān)關(guān)鍵鍵路路線線。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析ABCDEGFHAA12346785答案：答案：要求：（要求：（2）計(jì)算各事項(xiàng)的最早、最遲開始時(shí)間；）計(jì)算各事項(xiàng)的最早、最遲開始時(shí)間； （3）找出關(guān)鍵路線。）找出關(guān)鍵路線。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析(1) 工序最早開始時(shí)間工序最早開始時(shí)間 (earliest start time)(2) 工序最早完成時(shí)間工序最早完

62、成時(shí)間 (earliest finish time)TES(1, j)=0TES(i, j)=maxTES(k, i)+Tki (3) 工序最遲完成時(shí)間工序最遲完成時(shí)間 (latest finish time)(4) 工序最遲開始時(shí)間工序最遲開始時(shí)間 (latest start time) TEF(i, j)=TES(i, j)+TijTLS(i, j) = TLF(i, j)-TijTES(i, j)= TE (i)TLF(i, n)= TL(n)或指定或指定TLF(i, j)= TL (j)3、工序時(shí)間參數(shù)計(jì)算山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析356145432

63、23320535935579127101212999579975074山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析(5) 工序總時(shí)差工序總時(shí)差(total floating time) 在不影響工程最早結(jié)束時(shí)間的條件下，工序最早開始（或結(jié)在不影響工程最早結(jié)束時(shí)間的條件下，工序最早開始（或結(jié)束）時(shí)間可以推遲的時(shí)間。束）時(shí)間可以推遲的時(shí)間。TF(i, j)=TLS(i, j)-TES(i, j)=TLF(i, j)-TEF(i, j)(6) 工序單時(shí)差工序單時(shí)差(free floating time) 在不影響所有緊后工序最早開始時(shí)間的條件下，工序最早結(jié)在不影響所有緊后工序最早開

64、始時(shí)間的條件下，工序最早結(jié)束時(shí)間可以推遲推遲的時(shí)間。束時(shí)間可以推遲推遲的時(shí)間。FF(i, j)=TES(j, k)-TEF(i, j) (TES(i, j)+Tij)山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析35614543223320535935579127101212999579975074說(shuō)明：說(shuō)明： 總時(shí)差可以串用總時(shí)差可以串用 總時(shí)差為總時(shí)差為4135工序（工序（1,3）和（）和（3,5）共用）共用256 總時(shí)差為總時(shí)差為2工序（工序（2,5）和（）和（5,6）共用）共用山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析T=15125341125224

65、8967423340 444497699101161011126881210131315151313101312139971091287512912109440山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析l時(shí)間優(yōu)化時(shí)間優(yōu)化 l時(shí)間費(fèi)用優(yōu)化時(shí)間費(fèi)用優(yōu)化 l時(shí)間資源優(yōu)化時(shí)間資源優(yōu)化 8.6.3 網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)優(yōu)化山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析一、時(shí)間優(yōu)化 時(shí)間優(yōu)化就是不考慮人力、物力、財(cái)力資源的限制，時(shí)間優(yōu)化就是不考慮人力、物力、財(cái)力資源的限制，尋找最短工期。這種情況通常發(fā)生在任務(wù)緊急、資源尋找最短工期。這種情況通常發(fā)生在任務(wù)緊急、資源有保障的情況。

66、時(shí)間優(yōu)化的途徑有：有保障的情況。時(shí)間優(yōu)化的途徑有：1、采取技術(shù)組織措施，縮短關(guān)鍵工序時(shí)間；、采取技術(shù)組織措施，縮短關(guān)鍵工序時(shí)間；2、抽調(diào)非關(guān)鍵路線資源去支援關(guān)鍵路線；以提、抽調(diào)非關(guān)鍵路線資源去支援關(guān)鍵路線；以提 高效率，縮短整個(gè)工程的總工期；高效率，縮短整個(gè)工程的總工期；3、采用平行或交叉作業(yè)。、采用平行或交叉作業(yè)。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析舉例 在一個(gè)緊張工作后的周五晚上，你和你的朋友正在一個(gè)緊張工作后的周五晚上，你和你的朋友正在考慮周末怎么去放松，這時(shí)電視里的天氣預(yù)報(bào)說(shuō)在考慮周末怎么去放松，這時(shí)電視里的天氣預(yù)報(bào)說(shuō)周六將是一個(gè)風(fēng)和日麗的好天氣，因此你們兩個(gè)決周六將是一個(gè)風(fēng)和日麗的好天氣，因此你們兩個(gè)決定明天早上去你們所在地附近的某一湖邊野餐。由定明天早上去你們所在地附近的某一湖邊野餐。由于你們希望能從這次野餐中得到最大的快樂，因此于你們希望能從這次野餐中得到最大的快樂，因此你們決定對(duì)這次湖邊野餐的準(zhǔn)備工作進(jìn)行很好的計(jì)你們決定對(duì)這次湖邊野餐的準(zhǔn)備工作進(jìn)行很好的計(jì)劃。劃。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院系統(tǒng)工程 圖與網(wǎng)絡(luò)分析活動(dòng)標(biāo)活動(dòng)標(biāo)號(hào)號(hào)活動(dòng)