系統(tǒng)工程 圖與網(wǎng)絡分析課件

山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 l8.1.1 用圖來描述實際問題用圖來描述實際問題 l8.1.2 圖的基本概念圖的基本概念 l8.1.3 圖的矩陣表示圖的矩陣表示 l小結(jié)小結(jié)山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.1 用圖來描述實際問題8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 例例 82 五個球隊的比賽情況：五個球隊的比賽情況：山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.1 用圖來描述實際問題8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 圖是反映對象之間關系的一種工具。圖是反映對象之間關系的一種工具。 在一般情況下，圖中點的相對位置如何，點與點之間連線的長短曲直，在一般情況下，圖中點的相對位置如何，點與點之間連線的長短曲直，對于反映對象之間的關系，并不是重要的。例如上面所說的五個球隊的比賽對于反映對象之間的關系，并不是重要的。例如上面所說的五個球隊的比賽情況也可以用下圖表示：情況也可以用下圖表示： 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.1 用圖來描述實際問題8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 如果人們關心的是如果人們關心的是5個球隊比賽的勝負情況，那么上面的圖就表示不出來了。個球隊比賽的勝負情況，那么上面的圖就表示不出來了。 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.2 圖的基本概念8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 定義定義81 圖圖 是由一些點及一些點之間的連線（不帶箭頭或帶箭頭）所組成。是由一些點及一些點之間的連線（不帶箭頭或帶箭頭）所組成。 無向圖無向圖 由點和邊所構(gòu)成的圖（也簡稱為圖），記為由點和邊所構(gòu)成的圖（也簡稱為圖），記為G = (V, E )，其中，其中V，E分別是分別是G的頂點集合和邊集合的頂點集合和邊集合。 有向圖有向圖 由點和弧所構(gòu)成的圖稱為有向圖，記為由點和弧所構(gòu)成的圖稱為有向圖，記為D = (V, A )，其中其中V, A分別表示分別表示D的頂點集合和弧集合。的頂點集合和弧集合。 我們把兩點之間的不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。我們把兩點之間的不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。 一一條條連連接接點點iv,jvV 的的邊邊 e 記記為為 e = iv,jv 或或 e = jv,iv 。 一條方向是從一條方向是從iv指向指向jv的的弧弧 a 記為記為 a = (iv,jv )。iv稱為稱為 a 的始點，的始點，jv稱為稱為 a 的終點。的終點。 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.2 圖的基本概念8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 定義定義82頂點數(shù)和邊數(shù)頂點數(shù)和邊數(shù) 圖圖G = (V, E ) 中，中，V中元素的個數(shù)稱為圖中元素的個數(shù)稱為圖G的頂點數(shù)，記作的頂點數(shù)，記作p (G )或簡記為或簡記為p；E中元素的個數(shù)稱為圖中元素的個數(shù)稱為圖G 的邊數(shù)，記作的邊數(shù)，記作q (G )，或簡記為，或簡記為q。具有相同端點的邊稱為具有相同端點的邊稱為多重邊或平行邊多重邊或平行邊；兩個端點落在一個頂點的邊稱為；兩個端點落在一個頂點的邊稱為環(huán)環(huán)。含有多重邊的圖稱為含有多重邊的圖稱為多重圖多重圖；無環(huán)也無多重邊的圖稱為；無環(huán)也無多重邊的圖稱為簡單圖。簡單圖。 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.2 圖的基本概念8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 p (G ) = 6 ，q (G ) = 8；e3 = 4v,3v，3v與與4v是是 e3的端點，的端點，e3是點是點3v和和4v的關聯(lián)邊；的關聯(lián)邊；2v與與5v是鄰點，是鄰點，e3與與 e2是鄰邊；是鄰邊；e7與與 e8是多重邊，是多重邊，e4是一個環(huán)是一個環(huán)。 如圖如圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.2 圖的基本概念8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 定理定理81 圖圖G = ( V , E )中，所有頂點的次之和是邊數(shù)的兩倍。即中，所有頂點的次之和是邊數(shù)的兩倍。即Vviiqvd2)(定理定理82 任一圖任一圖G中，奇點的個數(shù)為偶數(shù)。中，奇點的個數(shù)為偶數(shù)。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.2 圖的基本概念8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 定義定義83若鏈若鏈中，所含的邊互不相同，則稱中，所含的邊互不相同，則稱為為簡單鏈簡單鏈； 若鏈若鏈中，頂點中，頂點21,iivv, , k1k,iivv都不相同，則稱都不相同，則稱為為初等鏈初等鏈。 若回路中的弧都互不相同，則稱為若回路中的弧都互不相同，則稱為簡單回路簡單回路；若回路中除始點、終；若回路中除始點、終點外的頂點都互不相同，則稱為點外的頂點都互不相同，則稱為初等回路初等回路。 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.2 圖的基本概念8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 定義定義84一個圖一個圖G的任意兩個頂點，如果至少有一條通路將它們連接起來，的任意兩個頂點，如果至少有一條通路將它們連接起來，則這個圖則這個圖G就稱為就稱為連通圖連通圖，否則就稱為，否則就稱為不連通圖不連通圖。若若G是不連通圖，它的每個連通的部分稱為是不連通圖，它的每個連通的部分稱為G的一個的一個連通分圖連通分圖 (也簡稱分圖也簡稱分圖)。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.2 圖的基本概念8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 定義定義85設設 G = ( V, , E )，對任意一條邊，對任意一條邊 eE，如果相應都有一個數(shù)值，如果相應都有一個數(shù)值 w (e)與之對應，則稱與之對應，則稱 G 為為賦權(quán)圖賦權(quán)圖，w (e) 稱為邊稱為邊 e 的的權(quán)權(quán)。 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.3 圖的矩陣表示8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 1關聯(lián)矩陣關聯(lián)矩陣 0 1否則關聯(lián)與jiijevb稱矩陣稱矩陣B為圖為圖G的的關聯(lián)矩陣關聯(lián)矩陣。 關聯(lián)矩陣描述了無向圖關聯(lián)矩陣描述了無向圖G的頂點與邊的關聯(lián)情況。的頂點與邊的關聯(lián)情況。 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.3 圖的矩陣表示8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 例如例如 無向圖無向圖G10000001110000001111000001110101001)( 543217654321vvvvvGBeeeeeee1關聯(lián)矩陣關聯(lián)矩陣其關聯(lián)矩陣如下：其關聯(lián)矩陣如下：山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.3 圖的矩陣表示8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 0 1 1不關聯(lián)與的終點為的起點為jijijiijavavavb1關聯(lián)矩陣關聯(lián)矩陣山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.3 圖的矩陣表示8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 1關聯(lián)矩陣關聯(lián)矩陣右圖所示的有向圖右圖所示的有向圖D1101100011011000000111011001)( 43217654321vvvvDBa aaaaaa其關聯(lián)矩陣為：其關聯(lián)矩陣為：山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.1.3 圖的矩陣表示8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 2鄰接矩陣鄰接矩陣稱矩陣稱矩陣A為圖為圖G的的鄰接矩陣。鄰接矩陣。 鄰接矩陣描述了圖的頂點與頂點之間的關系。鄰接矩陣描述了圖的頂點與頂點之間的關系。 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 l8.1.3 圖的矩陣表示2鄰接矩陣鄰接矩陣0100010101010210020101110)( 5432154321vvvvvGAvvvvv如圖所示，無向圖如圖所示，無向圖G其鄰接矩陣為：其鄰接矩陣為：山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念 l8.1.3 圖的矩陣表示2鄰接矩陣鄰接矩陣如圖所示，有向圖如圖所示，有向圖D0101100101001010)( 43214321vvvvDAvvvv其鄰接矩陣為：其鄰接矩陣為：山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.2 最小支撐樹問題 l8.2.1 樹及其性質(zhì)l8.2.2 圖的支撐樹l8.2.3 最小支撐樹問題l作業(yè)山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.2.1 樹及其性質(zhì)8.2 最小支撐樹問題 一個無圈的連通圖稱為一個無圈的連通圖稱為樹樹，通常以，通常以T 表示。表示。 1. 樹的定義樹的定義2. 樹的性質(zhì)樹的性質(zhì)（1）具有具有n個頂點的樹，其邊數(shù)恰好為個頂點的樹，其邊數(shù)恰好為n-1條。條。（2）樹的任意兩個頂點之間有且僅有一條鏈。樹的任意兩個頂點之間有且僅有一條鏈。（3）在樹在樹T中去掉任一條邊，則中去掉任一條邊，則T成為不連通圖。成為不連通圖。（4）在樹在樹T中不相鄰的兩個頂點間添上一條邊，則恰好得到一個圈。中不相鄰的兩個頂點間添上一條邊，則恰好得到一個圈。進一步地說，如果再從這個圈上任意去掉一條邊，可以得到一個樹。進一步地說，如果再從這個圈上任意去掉一條邊，可以得到一個樹。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.2.2 圖的支撐樹8.2 最小支撐樹問題 1. 支撐樹的定義支撐樹的定義如圖如圖其支撐樹為其支撐樹為山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.2.2 圖的支撐樹8.2 最小支撐樹問題 2. 判斷一個圖判斷一個圖G有支撐樹的充要條件有支撐樹的充要條件 定理定理 圖圖G有支撐樹的充分必要條件是圖有支撐樹的充分必要條件是圖G是連通的。是連通的。 若若G含圈，從圈中任意地去掉一條邊，得到圖含圈，從圈中任意地去掉一條邊，得到圖G的一個支撐子圖的一個支撐子圖G1。如果。如果G1不含圈，那么不含圈，那么G1 是是G的一個支撐樹；如果的一個支撐樹；如果G1仍含圈，那仍含圈，那么從么從G1中任取一個圈，從圈中再任意去掉一條邊，得到圖中任取一個圈，從圈中再任意去掉一條邊，得到圖G的一個的一個支撐子圖支撐子圖G2 ，如此重復，最終可以得到，如此重復，最終可以得到G的一個支撐子圖的一個支撐子圖GK ，它，它是連通的，并且不含圈，于是是連通的，并且不含圈，于是GK是是G的一個支撐樹。的一個支撐樹。必要性必要性是顯然的。是顯然的。證明證明充分性充分性設圖設圖G是連通圖是連通圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.2.2 圖的支撐樹8.2 最小支撐樹問題 3. 尋求連通圖的支撐樹的方法尋求連通圖的支撐樹的方法（1）破圈法）破圈法 就是在圖就是在圖G中任取一個圈，從圈中去掉一邊，對余下的圖中任取一個圈，從圈中去掉一邊，對余下的圖重復這個步驟，直到不含圈時為止，即得到圖重復這個步驟，直到不含圈時為止，即得到圖G的的一個支撐樹。一個支撐樹。v1v2v3v4v5v6651572344W(T)=5+1+2+3+4=15山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.2.2 圖的支撐樹8.2 最小支撐樹問題 3. 尋求連通圖的支撐樹的方法尋求連通圖的支撐樹的方法(2)避圈法避圈法 任取一條邊任取一條邊e1，找一條與，找一條與e1不構(gòu)成圈的邊不構(gòu)成圈的邊e2，再找一條與，再找一條與e1, e2不構(gòu)成圈的邊不構(gòu)成圈的邊e3，一般，設已有，一般，設已有e1, e2, eK ，找一條與，找一條與e1, e2, eK 中的任何一些邊不構(gòu)成圈的邊中的任何一些邊不構(gòu)成圈的邊eK+1。重復這個過程，。重復這個過程， 直到不能進行直到不能進行為止，這時即得到一個支撐樹。為止，這時即得到一個支撐樹。v2v1v3v4v5v2v1v3v4v5山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.2 最小支撐樹問題 l8.2.3 最小支撐樹問題(1)支撐樹的權(quán)支撐樹的權(quán) 設賦權(quán)連通圖設賦權(quán)連通圖G = (V, E，W)， 如果如果T(V, E)是是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的最小支的最小支撐樹撐樹(簡稱簡稱最小樹最小樹)。最小支撐樹問題最小支撐樹問題就是求一個賦權(quán)連通圖就是求一個賦權(quán)連通圖G的最小支撐樹。的最小支撐樹。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.2.3 最小支撐樹問題8.2 最小支撐樹問題 (3)求最小支撐樹的方法求最小支撐樹的方法第一種方法第一種方法 破圈法破圈法 在連通圖在連通圖G中，任取一個圈，從圈中去掉一條權(quán)最大的邊中，任取一個圈，從圈中去掉一條權(quán)最大的邊(如果有兩條或如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條)。在余下的圖中，重。在余下的圖中，重復這個步驟，一直得到一個不含圈的圖為止。復這個步驟，一直得到一個不含圈的圖為止。v1v2v3v4v5v6651572344W(T)=5+1+2+3+4=15山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.2.3 最小支撐樹問題8.2 最小支撐樹問題 (3)求最小支撐樹的方法求最小支撐樹的方法第二種方法第二種方法 避圈法避圈法 在連通圖在連通圖G中，開始選一條最小權(quán)的邊，以后每一步中，總從未中，開始選一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈(每每一步中，如果有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一步中，如果有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一條一條)。重復下去，直到不存在與已選邊不構(gòu)成圈的邊為止。已選邊。重復下去，直到不存在與已選邊不構(gòu)成圈的邊為止。已選邊與頂點構(gòu)成的圖與頂點構(gòu)成的圖T就是所求最小樹。就是所求最小樹。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.2 最小支撐樹問題 v1v4v3v2v62515203091012例例 如圖如圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l作業(yè)8.2 最小支撐樹問題 求下圖的最小支撐樹求下圖的最小支撐樹山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.3 最短路問題 l8.3.1 最短路問題的提出l8.3.2 最短路的算法l8.3.3 最短路問題應用舉例l作業(yè)山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.3.1 最短路問題提出8.3 最短路問題 1. 最短路問題引例最短路問題引例油油田田加加工工廠廠v1v2v3v4v5v6v9v7v8444444422266山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.3.1 最短路問題提出8.3 最短路問題 要求使管道總長最短的鋪設方案。要求使管道總長最短的鋪設方案。1. 引例引例 油田管道鋪設問題油田管道鋪設問題從圖中可以看出，可能的鋪設方案是很多的，如：從圖中可以看出，可能的鋪設方案是很多的，如： 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.3 最短路問題 l8.3.1 最短路問題提出2. 最短路問題的定義最短路問題的定義在賦權(quán)有向圖在賦權(quán)有向圖D=（V，A，W）中，指定兩點）中，指定兩點vs、vt 作為始點和終點。作為始點和終點。設設P是是D中從中從vs到到vt的一條路，的一條路，路路P的權(quán)的權(quán)是是P中所有弧的權(quán)之和。記為中所有弧的權(quán)之和。記為W(P)最短路問題最短路問題就是要在所有從就是要在所有從vs到到vt的路的路P中，求一條權(quán)最小的路中，求一條權(quán)最小的路P0。即。即PvvijjiPW),()()(min)(0PWPWP山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.3 最短路問題 l8.3.2 最短路問題的算法Dijkstra標號算法標號算法適用范圍適用范圍：0ij基本思路基本思路:從起點從起點vs出發(fā)出發(fā),逐步向外探尋，對于某一個結(jié)點逐步向外探尋，對于某一個結(jié)點vi標號：標號： 固定標號固定標號P(vi) 或或 臨時標號臨時標號T(vi) 主要步驟：開始：P(vs)=0，T(vi)=+ Step1:修改臨時標號 Step2:變臨時標號為固定標號山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.3.2 最短路問題的算法8.3 最短路問題 用用Dijkstra標號算法求下列無向圖中頂點到頂點標號算法求下列無向圖中頂點到頂點6的最短距離及其路線。的最短距離及其路線。 解解 首先給頂點首先給頂點1標上固定標標上固定標號號0，即，即P ( 1 ) = 0，其余頂點，其余頂點標上臨時標號，且標上臨時標號，且T ( j ) = ( j =2,3,6)。 （1）與頂點）與頂點1直接相連又為臨時標號的頂直接相連又為臨時標號的頂點是點是2和和3，這兩個頂點的臨時標號改為，這兩個頂點的臨時標號改為Step1T ( 2 ) = 4T ( 3 ) = 3山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.3.2 最短路問題的算法8.3 最短路問題 （2）在所有臨時標號中，最小的為）在所有臨時標號中，最小的為T ( 3 ) 3，于是令，于是令P ( 3 ) 3，即，即頂點頂點3獲得固定標號獲得固定標號3。Step2（1）與頂點）與頂點3直接相連又為臨時標號的頂點是直接相連又為臨時標號的頂點是2和和5，修改這兩個頂點，修改這兩個頂點的臨時標號為的臨時標號為T ( 2 ) = 4T ( 5 ) = 5（2）在所有臨時標號中，）在所有臨時標號中，T ( 2 ) 4最小，于是有最小，于是有P (2 ) 4，即頂點，即頂點2獲得固定標號獲得固定標號4。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.3.2 最短路問題的算法8.3 最短路問題 Step3（1）對頂點）對頂點2有有T ( 4 ) = 7T ( 5 ) = 5（2）在所有臨時標號中，）在所有臨時標號中，T ( 5 ) 5最小，于是有最小，于是有P (5 ) 5。Step4（1）對頂點）對頂點5有有T ( 4 ) = 7T ( 6 ) = 9（2）在所有臨時標號中，）在所有臨時標號中，T ( 4 ) 7 最小，令最小，令P (4 ) 7。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.3.2 最短路問題的算法8.3 最短路問題 Step5（1）對頂點）對頂點4有有T ( 6 ) =9（2）顯然有）顯然有P (6 ) 9。頂點頂點6 獲得固定標號，算法到此結(jié)束。獲得固定標號，算法到此結(jié)束。 頂點頂點1到頂點到頂點6的最短距離為的最短距離為9。從頂點從頂點6反向追蹤就可以找到最短路線：反向追蹤就可以找到最短路線：1 3 5 6 和和 1 2 5 6 ，它們的最短距離都為，它們的最短距離都為9。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.3 最短路問題 l8.3.3 最短路問題應用舉例設備更新問題設備更新問題時間第1年第2年第3年第4年第5年價格1111121213維修費用5681118如何制定使得總的支付費用最少的設備更新計劃如何制定使得總的支付費用最少的設備更新計劃 ？可以把這個問題化為最短路問題可以把這個問題化為最短路問題 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析v1 v4 v6總費用為總費用為53萬元萬元v3v6v4v2v1v5224130162216173059412331182317v1 v3 v68.3 最短路問題 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.3 最短路問題 l8.3.3 最短路問題應用舉例選址問題選址問題 已知有已知有6個村莊，各村莊間的距離如下圖所示，個村莊，各村莊間的距離如下圖所示，各村的小學生人數(shù)如下表所示?，F(xiàn)在計劃在這片各村的小學生人數(shù)如下表所示。現(xiàn)在計劃在這片區(qū)域內(nèi)建造一所醫(yī)院和一所小學，問醫(yī)院應建在區(qū)域內(nèi)建造一所醫(yī)院和一所小學，問醫(yī)院應建在哪個村莊才能使最遠村莊到醫(yī)院看病所走的總路哪個村莊才能使最遠村莊到醫(yī)院看病所走的總路程最短程最短?又問小學建在哪個村莊才能使學生上學又問小學建在哪個村莊才能使學生上學走的總路程最短。走的總路程最短。 v2 。 。v4 2 8 6 v1。 4 1 。v6 7 3 v3 。 。v5 3 1 6 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.3 最短路問題 解：解：03459113012684101575210469654021187620 654321654321vvvvvvSvvvvvv11967811故：醫(yī)院應建在第三個村莊，故：醫(yī)院應建在第三個村莊，其它村莊到該村莊的距離最遠為其它村莊到該村莊的距離最遠為6 。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.3 最短路問題 設設想想小小學學建建立立在在jv，則則其其它它村村莊莊的的小小學學生生們們所所走走的的總總路路程程就就是是 50S1j + 40S2j + 60S3j+ 20S4j+ 70S5j + 90S6j 對每一點求出這個值，它們的最小值所對應的對每一點求出這個值，它們的最小值所對應的jv這相當于將矩陣這相當于將矩陣S中每一行元素分別乘上對應村莊里小學生的人數(shù)，然后分中每一行元素分別乘上對應村莊里小學生的人數(shù)，然后分別求出各列的和，得矩陣別求出各列的和，得矩陣D 就是所要選擇的最佳位置。就是所要選擇的最佳位置。027036045081099021007014042056080200201001403001206002403603602402001600805504003503001000 654321654321vvvvvvDvvvvvv2130 1670 1070 1040 1050 1500 故：小學應建在第四個村莊。故：小學應建在第四個村莊。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l作業(yè)8.3 最短路問題 求下圖中的點求下圖中的點1到點到點7的最短距離和最短路線。的最短距離和最短路線。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.4 網(wǎng)絡最大流問題 l8.4.1 最大流問題的數(shù)學模型l8.4.2 最大流問題的解法l8.4.3 最大流問題應用舉例l作業(yè)山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.4.1 最大流問題的數(shù)學模型8.4 網(wǎng)絡最大流問題 （1）網(wǎng)絡）網(wǎng)絡 1. 基本概念基本概念山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.4.1 最大流問題的數(shù)學模型8.4 網(wǎng)絡最大流問題 （2）網(wǎng)絡的流）網(wǎng)絡的流 1. 基本概念基本概念山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.4 網(wǎng)絡最大流問題 （3）可行流）可行流 設設f 為一網(wǎng)絡流，當為一網(wǎng)絡流，當f 滿足下列條件時，稱為可行流。滿足下列條件時，稱為可行流。 容容量量限限制制條條件件 對對每每一一弧弧 (iv,jv)A，有有 0 fij cij 0),(),(AvvjiAvvijijjiff )(),(),(fvffAvvjsAvvsjsjjs )(),(),(fvffAvvjtAvvtjtjjt式中，式中，v ( f )稱為這個可行流的流量，即發(fā)點的凈輸出量或收點的凈輸入量。稱為這個可行流的流量，即發(fā)點的凈輸出量或收點的凈輸入量。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析（4）最大流最大流 網(wǎng)絡網(wǎng)絡D上流量上流量v ( f )達到最大的可行流，稱為該網(wǎng)絡的最大流。達到最大的可行流，稱為該網(wǎng)絡的最大流。最大流問題其實是一個特殊的線性規(guī)劃問題。最大流問題其實是一個特殊的線性規(guī)劃問題。 Ajvivijcijfi=t fvtsii=sfvjifijftsfvMax),( 0)()(),( 0 )( )( . .)( 2. 最大流問題的數(shù)學模型：最大流問題的數(shù)學模型：8.4 網(wǎng)絡最大流問題 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.4 網(wǎng)絡最大流問題 l8.4.2 最大流問題的解法1. 有關的概念有關的概念飽和?。猴柡突。篺ij = cij 非飽和?。悍秋柡突。?fij0 前向弧前向?。ㄕ蚧。?，記為（正向?。?，記為+ ：與鏈的方向一致的弧與鏈的方向一致的弧 后向弧后向?。ǚ聪蚧。?，記為（反向?。?，記為- ：與鏈的方向相反的弧與鏈的方向相反的弧山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.4 網(wǎng)絡最大流問題 l8.4.2 最大流問題的解法1. 有關的概念有關的概念增廣鏈增廣鏈設設f = fij是一個可行流，是一個可行流，是從是從vs到到vt的一條鏈。若的一條鏈。若滿足下列條件滿足下列條件 ： （1）前向?。┣跋蚧?中的每一弧都是非飽和弧，即中的每一弧都是非飽和弧，即 （2）后向弧）后向弧-中的每一弧都是非零流弧，即中的每一弧都是非零流弧，即ijijcf0則稱則稱是關于是關于 可行流可行流f 的一條增廣鏈。的一條增廣鏈。ijijcf 0山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.4 網(wǎng)絡最大流問題 l8.4.2 最大流問題的解法1. 有關的概念有關的概念截集截集截量截量),(),(1111),(VVvvijjicVVc山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.4.2 最大流問題的解法8.4 網(wǎng)絡最大流問題 2. 判斷一個可行流是否是最大流的條件判斷一個可行流是否是最大流的條件定理定理 可行流可行流 f 是最大流的充要條件是不存在關于是最大流的充要條件是不存在關于f 的增廣鏈。的增廣鏈。此定理為我們提供了尋求網(wǎng)絡中最大流的一個方法：此定理為我們提供了尋求網(wǎng)絡中最大流的一個方法：若給了一個可行流若給了一個可行流 f，只要去判斷，只要去判斷D中有無關于中有無關于f 的增廣鏈。如果有增廣鏈，的增廣鏈。如果有增廣鏈，則可以改進則可以改進 f，得到一個流量增大的新的可行流。如果沒有增廣鏈，則得到，得到一個流量增大的新的可行流。如果沒有增廣鏈，則得到最大流。最大流。最大流最小截量定理：最大流最小截量定理： 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.4 網(wǎng)絡最大流問題 l8.4.2 最大流問題的解法3. 求網(wǎng)絡最大流的標號算法求網(wǎng)絡最大流的標號算法FordFulkerson 算法：算法：從一個可行流從一個可行流f = fij出發(fā)，經(jīng)過出發(fā)，經(jīng)過標號過程標號過程與與調(diào)整過程調(diào)整過程。（1）標號過程）標號過程 尋找增廣鏈的過程。尋找增廣鏈的過程。（2）調(diào)整過程）調(diào)整過程 沿著增廣鏈調(diào)整可行流。沿著增廣鏈調(diào)整可行流。令調(diào)整量令調(diào)整量是是l(vt)，即，即vt的第二個標號。的第二個標號。 ),( ,),( ,),( , jiijjiijjiijijvvfvvfvvff山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.4 網(wǎng)絡最大流問題 l8.4.3 最大流問題的應用舉例例例 用標號法求如下網(wǎng)絡的最大流，弧旁的數(shù)為容量。用標號法求如下網(wǎng)絡的最大流，弧旁的數(shù)為容量。 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.4 網(wǎng)絡最大流問題 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.4 網(wǎng)絡最大流問題 （1）標號過程。針對當前可行流（）標號過程。針對當前可行流（v ( f ) = 8）尋找增廣鏈。）尋找增廣鏈。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.4 網(wǎng)絡最大流問題 （2）調(diào)整過程）調(diào)整過程經(jīng)檢查，標號過程無法進行下去，算法終止，得到最大流如上圖所示。經(jīng)檢查，標號過程無法進行下去，算法終止，得到最大流如上圖所示。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l作業(yè)8.4 網(wǎng)絡最大流問題 求如下網(wǎng)絡的最大流（弧上的數(shù)字為容量）。求如下網(wǎng)絡的最大流（弧上的數(shù)字為容量）。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.5 最小費用最大流問題 l8.5.1 問題描述l8.5.2 最小費用最大流算法l8.5.3 應用舉例山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.5.1 問題描述8.5 最小費用最大流問題 Avvijijjifbfb),()(求求b ( f ) 為最小且流量為某確定值為最小且流量為某確定值v ( f )的可行流問題，稱為最小費用流問題；的可行流問題，稱為最小費用流問題；求求b ( f ) 為最小且流量為最小且流量v ( f ) 為最大的問題，稱為為最大的問題，稱為最小費用最大流問題最小費用最大流問題。 如果把最小費用看成約束條件，和最大流問題一樣，最小費用流問題也如果把最小費用看成約束條件，和最大流問題一樣，最小費用流問題也是一個線性規(guī)劃問題，并且求最小費用流實際上是求該線性規(guī)劃問題的可行是一個線性規(guī)劃問題，并且求最小費用流實際上是求該線性規(guī)劃問題的可行解，求最小費用最大流問題實際上是求該線性規(guī)劃問題的最優(yōu)解。解，求最小費用最大流問題實際上是求該線性規(guī)劃問題的最優(yōu)解。 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.5.2 最小費用最大流的算法8.5 最小費用最大流問題 最小費用最大流的算法通常采用對偶算法，其具體算法步驟如下：最小費用最大流的算法通常采用對偶算法，其具體算法步驟如下：min),(minmin11kijkijijffc山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.5 最小費用最大流問題 ),( ,),( ,),( ,111jikijjikijjikijkijvvfvvfvvff山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l8.5.3 應用實例8.5 最小費用最大流問題 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.5 最小費用最大流問題 解解 （1）取取初初始始可可行行流流 f 0 = 0，構(gòu)構(gòu)造造相相應應的的費費用用網(wǎng)網(wǎng)絡絡 w ( f 0 )，如如下下圖圖所所示示。 圖圖 (a) 費用網(wǎng)絡圖費用網(wǎng)絡圖w ( f 0 )山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.5 最小費用最大流問題 圖圖 (b) 流量網(wǎng)絡流量網(wǎng)絡D ( f 1 ) 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.5 最小費用最大流問題 （3） 再再構(gòu)構(gòu)造造與與 D ( f 1 )相相對對應應的的費費用用網(wǎng)網(wǎng)絡絡 w ( f 1 )， 用用標標號號法法求求sv到到tv的的最最短短路路，如如圖圖中中雙雙線線所所示示：sv2v3vtv。 圖圖 (c) 費用網(wǎng)絡圖費用網(wǎng)絡圖w ( f 1 )山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.5 最小費用最大流問題 圖圖 (d) 流量網(wǎng)絡流量網(wǎng)絡D ( f 2 ) 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.5 最小費用最大流問題 （4） 再再構(gòu)構(gòu)造造與與 D ( f 2 )相相對對應應的的費費用用網(wǎng)網(wǎng)絡絡 w ( f 2 )， 用用標標號號法法求求sv到到tv的的最最短短路路，如如圖圖中中雙雙線線所所示示。 圖圖 (e) 費用網(wǎng)絡圖費用網(wǎng)絡圖 w ( f 2 )山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.5 最小費用最大流問題 在在流流量量網(wǎng)網(wǎng)絡絡 D ( f 2 )中中與與這這條條最最短短路路相相對對應應的的增增廣廣鏈鏈為為 2 = (sv, ,1v, ,4v, ,tv)，在在增增廣廣鏈鏈 2上上對對 f 2進進行行調(diào)調(diào)整整，調(diào)調(diào)整整量量 = 3，得得新新的的可可行行流流 f 3，其其流流值值 v ( f 3) = 8，如如圖圖(f )所所示示。 圖圖 ( f ) 流量網(wǎng)絡流量網(wǎng)絡D ( f 3 ) 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.5 最小費用最大流問題 （5）構(gòu)構(gòu)造造費費用用網(wǎng)網(wǎng)絡絡 w ( f 3 )，并并在在 w ( f 3 )上上求求最最短短路路，如如圖圖中中雙雙線線所所示示。 圖圖(g) 費用網(wǎng)絡圖費用網(wǎng)絡圖w ( f 3 )山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.5 最小費用最大流問題 在在 D ( f 3 )上上得得到到相相應應的的增增廣廣鏈鏈 3 = (sv, ,2v, ,3v, ,4v, ,tv)，在在增增廣廣鏈鏈 3上上對對 f 3進進行行調(diào)調(diào)整整，調(diào)調(diào)整整量量 = 4，得得新新的的可可行行流流 f 4，其其流流值值 v ( f 4) = 12，如如圖圖(h )所所示示。 圖圖 (h) 流量網(wǎng)絡流量網(wǎng)絡D ( f 4 ) 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.5 最小費用最大流問題 （6）作作 w ( f 4 )，如如圖圖所所示示，由由于于從從 w ( f 4)中中無無法法找找到到sv到到tv的的最最短短路路，說說明明在在 D ( f 4 )中中已已不不存存在在增增廣廣鏈鏈，求求解解終終止止。 故故 D ( f 4 )所所示示的的流流即即為為所所求求的的最最小小費費用用最最大大流流。此此時時 v ( f 4 ) = 12，最最小小費費用用為為 679。 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析8.6 網(wǎng)絡計劃技術(shù) l8.6.1 網(wǎng)絡圖l8.6.2 網(wǎng)絡時間與關鍵路線l8.6.3 網(wǎng)絡優(yōu)化l作業(yè)山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析(1) 又名：統(tǒng)籌方法又名：統(tǒng)籌方法 ，是一種科學的組織管理技術(shù)。，是一種科學的組織管理技術(shù)。(2) CPM (Critical Path Method，關鍵路線法) PERT （Program Evaluation and Review Technique， 計劃評審法） 借助于網(wǎng)絡表示各項工作所需要的時間及各項工作間的相互關系，從而找出編制與執(zhí)行計劃的關鍵路線；同樣應用網(wǎng)絡方法和網(wǎng)絡形式，但它注重于對各項任務安排的評價和審查。引言山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析(3) 應用：工業(yè)、農(nóng)業(yè)、政府、科研、軍事應用：工業(yè)、農(nóng)業(yè)、政府、科研、軍事 例：阿波羅載人登月計劃例：阿波羅載人登月計劃 海陸空聯(lián)合作戰(zhàn)計劃海陸空聯(lián)合作戰(zhàn)計劃 運輸問題運輸問題 設備維修設備維修 新產(chǎn)品研制新產(chǎn)品研制山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析 1、結(jié)構(gòu)12A工序工序A事項：用事項：用 表示。表示。 不需人、財、物、工時不需人、財、物、工時工序：用箭線工序：用箭線 或雙代號（或雙代號（i, j）表示。）表示。 需人、財、物、工時需人、財、物、工時工序工序(1, 2)緊前工序緊前工序 緊后工序緊后工序 虛工序虛工序8.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析(1) 從左從左右畫，只有一個右畫，只有一個，一個，一個。1234567824331212、畫法注意事項：8.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析(2) 兩事項間只有一個工序兩事項間只有一個工序Bij75A38.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析123(3) 不允許回路不允許回路8.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析(4) 虛工序的運用虛工序的運用120 解決畫法中問題解決畫法中問題 正確表達工序的前后銜接關系正確表達工序的前后銜接關系 表達平行作業(yè)表達平行作業(yè)8.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析1234657824031302018.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析124678243132018.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析ik750A3Bj8.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析例例1、有有A, B, C, D, 四道工序，四道工序，C在在 A, B完完工后開始，工后開始， D在在 B完工后開始。完工后開始。CABDABCD8.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析例例2、已知、已知ABCEA DC8.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析A BDCE8.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析3、畫圖基本步驟(1) 任務分解，工序明細表。任務分解，工序明細表。(2) 畫圖。畫圖。(3) 工時、事項編號工時、事項編號 ( (i , j)工序需工序需i j )8.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析例例1、工序工序 內(nèi)容內(nèi)容 工時工時(天天) 緊前工序緊前工序 A 初步研究初步研究 1 / B 研究選點研究選點 2 A C 準備調(diào)研方案準備調(diào)研方案 4 A D 聯(lián)系調(diào)研點聯(lián)系調(diào)研點 2 B E 培訓工作人員培訓工作人員 3 B,C F 準備表格準備表格 1 C G 實地調(diào)研實地調(diào)研 5 D,E,F H 寫調(diào)研報告寫調(diào)研報告 2 G I 開會匯總開會匯總 3 H8.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析12325FE200C413DBAGHI123456789答案答案8.6.1 網(wǎng)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析例2工序工序 緊前工序緊前工序 工時工時(天天) 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)絡圖網(wǎng)絡圖山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析123578462A5B5C3D9E2F7G6H2I工序工序 緊前工序緊前工序 工時工時(天天) 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 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析課堂練習1工序工序 緊前工序緊前工序 工時工時(天天) 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 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析 1 2 3 4 5 6 9 10 11 7 8答案：答案：A 2B 3E5C4F3D1H7G2I6J5山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析課堂練習2有有某某一一工工程程項項目目的的活活動動（工工序序）明明細細表表如如下下表表： 工工序序 A B C D E F G H I J 緊緊前前工工序序 / A A A A B E F D,G C,H,I 所所需需時時間間(周周) 4 7 14 8 3 2 2 4 4 2 要要求求：（1）畫畫出出網(wǎng)網(wǎng)絡絡圖圖； （2）計計算算各各事事項項的的最最早早、最最遲遲開開始始時時間間； （3）找找出出關關鍵鍵路路線線。 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析 1、關鍵路線356124543223312124612105613856工期為：工期為：T=12 (周周)多長時間能夠完工？多長時間能夠完工？8.6.2 網(wǎng)絡時間與關鍵路線網(wǎng)絡時間與關鍵路線山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析幾個概念：幾個概念：1、網(wǎng)絡圖：只有一個始點和一個終點的有向圖。、網(wǎng)絡圖：只有一個始點和一個終點的有向圖。2、關鍵路線：網(wǎng)絡圖中從始點到終點的最長路線。、關鍵路線：網(wǎng)絡圖中從始點到終點的最長路線。3、工期：關鍵路線的路長。、工期：關鍵路線的路長。 總時差總時差為零的工序，開始和結(jié)束的時為零的工序，開始和結(jié)束的時間沒有一點機動的余地。由這些工序所組間沒有一點機動的余地。由這些工序所組成的路線就是網(wǎng)絡中的關鍵路線。成的路線就是網(wǎng)絡中的關鍵路線。P176 8.6.2 網(wǎng)絡時間與關鍵路線網(wǎng)絡時間與關鍵路線山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析2、事項時間參數(shù)計算（已知 T(i, j)=Tij ） (1) 事項最早時間事項最早時間TE(j)= TE(1)=0TE( j )=maxTE(i)+Tij i(3) 事項時差事項時差T(i)=TL(i)-TE(i)(2) 事項最遲時間事項最遲時間TL(i)=TL(n)= TE(n)TL(i)=minTL( j )- Tij j山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析124456352333205397121299750T=122、事項時間參數(shù)計算（已知 T(i, j)=Tij ） 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析12325132004CFEDBAGHI123456789013558131518T=18181513855510例例22、事項時間參數(shù)計算（已知 T(i, j)=Tij ） 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析課堂練習1工序工序 緊前工序緊前工序 工時工時(天天) 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)絡圖；）畫出網(wǎng)絡圖；（2）計算各事項的最）計算各事項的最 早、最遲開始時早、最遲開始時 間；間；（3）找出關鍵路線。）找出關鍵路線。 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析答案：答案： 1 2 3 4 5 6 9 10 11 7 8A 2B 3E5C4F3D1H7G2I6J5要求：（要求：（2）計算各事項的最早、最遲開始時間；）計算各事項的最早、最遲開始時間； （3）找出關鍵路線。）找出關鍵路線。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析課堂練習2有有某某一一工工程程項項目目的的活活動動（工工序序）明明細細表表如如下下表表： 工工序序 A B C D E F G H I J 緊緊前前工工序序 / A A A A B E F D,G C,H,I 所所需需時時間間(周周) 4 7 14 8 3 2 2 4 4 2 要要求求：（1）畫畫出出網(wǎng)網(wǎng)絡絡圖圖； （2）計計算算各各事事項項的的最最早早、最最遲遲開開始始時時間間； （3）找找出出關關鍵鍵路路線線。 山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析ABCDEGFHAA12346785答案：答案：要求：（要求：（2）計算各事項的最早、最遲開始時間；）計算各事項的最早、最遲開始時間； （3）找出關鍵路線。）找出關鍵路線。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析(1) 工序最早開始時間工序最早開始時間 (earliest start time)(2) 工序最早完成時間工序最早完成時間 (earliest finish time)TES(1, j)=0TES(i, j)=maxTES(k, i)+Tki (3) 工序最遲完成時間工序最遲完成時間 (latest finish time)(4) 工序最遲開始時間工序最遲開始時間 (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ù)計算山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析35614543223320535935579127101212999579975074山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析(5) 工序總時差工序總時差(total floating time) 在不影響工程最早結(jié)束時間的條件下，工序最早開始（或結(jié)在不影響工程最早結(jié)束時間的條件下，工序最早開始（或結(jié)束）時間可以推遲的時間。束）時間可以推遲的時間。TF(i, j)=TLS(i, j)-TES(i, j)=TLF(i, j)-TEF(i, j)(6) 工序單時差工序單時差(free floating time) 在不影響所有緊后工序最早開始時間的條件下，工序最早結(jié)在不影響所有緊后工序最早開始時間的條件下，工序最早結(jié)束時間可以推遲推遲的時間。束時間可以推遲推遲的時間。FF(i, j)=TES(j, k)-TEF(i, j) (TES(i, j)+Tij)山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析35614543223320535935579127101212999579975074說明：說明： 總時差可以串用總時差可以串用 總時差為總時差為4135工序（工序（1,3）和（）和（3,5）共用）共用256 總時差為總時差為2工序（工序（2,5）和（）和（5,6）共用）共用山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析T=151253411252248967423340 444497699101161011126881210131315151313101312139971091287512912109440山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析l時間優(yōu)化時間優(yōu)化 l時間費用優(yōu)化時間費用優(yōu)化 l時間資源優(yōu)化時間資源優(yōu)化 8.6.3 網(wǎng)絡優(yōu)化網(wǎng)絡優(yōu)化山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析一、時間優(yōu)化 時間優(yōu)化就是不考慮人力、物力、財力資源的限制，時間優(yōu)化就是不考慮人力、物力、財力資源的限制，尋找最短工期。這種情況通常發(fā)生在任務緊急、資源尋找最短工期。這種情況通常發(fā)生在任務緊急、資源有保障的情況。時間優(yōu)化的途徑有：有保障的情況。時間優(yōu)化的途徑有：1、采取技術(shù)組織措施，縮短關鍵工序時間；、采取技術(shù)組織措施，縮短關鍵工序時間；2、抽調(diào)非關鍵路線資源去支援關鍵路線；以提、抽調(diào)非關鍵路線資源去支援關鍵路線；以提 高效率，縮短整個工程的總工期；高效率，縮短整個工程的總工期；3、采用平行或交叉作業(yè)。、采用平行或交叉作業(yè)。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析舉例 在一個緊張工作后的周五晚上，你和你的朋友正在一個緊張工作后的周五晚上，你和你的朋友正在考慮周末怎么去放松，這時電視里的天氣預報說在考慮周末怎么去放松，這時電視里的天氣預報說周六將是一個風和日麗的好天氣，因此你們兩個決周六將是一個風和日麗的好天氣，因此你們兩個決定明天早上去你們所在地附近的某一湖邊野餐。由定明天早上去你們所在地附近的某一湖邊野餐。由于你們希望能從這次野餐中得到最大的快樂，因此于你們希望能從這次野餐中得到最大的快樂，因此你們決定對這次湖邊野餐的準備工作進行很好的計你們決定對這次湖邊野餐的準備工作進行很好的計劃。劃。山東理工大學管理學院山東理工大學管理學院系統(tǒng)工程 圖與網(wǎng)絡分析活動標活動標號號活動