專題五-圖與網(wǎng)絡(luò)分析

1專題五圖論與網(wǎng)絡(luò)計劃模型最小生成樹模型最短路模型最大流模型最小費用流模型網(wǎng)絡(luò)計劃與優(yōu)化模型2第一節(jié)圖與網(wǎng)絡(luò)基礎(chǔ)概念圖子圖和生成子圖網(wǎng)絡(luò)圖鏈、路、圈和回路連通圖簡單圖3一、圖

由有限個代表事物的點和表示事物間聯(lián)系線構(gòu)成，這些點稱為頂點。為了反映7家企業(yè)的業(yè)務(wù)來往聯(lián)系，用7個點表示7家企業(yè)，若某兩家企業(yè)之間存在業(yè)務(wù)來往，則兩點間聯(lián)線。數(shù)學(xué)表達(dá)：頂點用V={v1,v2,…,vn}表示；頂點間的連線稱為邊，用E={e1,e2,…}表示，則圖的表示方法為：G={V,E}4無向圖：對象之間具有對稱性，（甲對乙，乙對甲）。有向圖：不具有對稱性的事物。A認(rèn)識B，B一定認(rèn)識A?A到B的距離，一定等于B到A的距離？為了反映球隊之間比賽勝負(fù)關(guān)系，則球隊之間單純用一條聯(lián)線就難以表達(dá)。對策：帶箭頭的線，有向線－－－有向圖。5邊：兩點間不帶箭頭聯(lián)線稱為邊，若兩點為vi,vj,則邊記為：[vi,vj]；?。簝牲c間帶箭頭聯(lián)線稱弧,若有vi指向vj的弧，則弧記為：（vi,vj）。無向圖定義：由點和邊組成，表示G={V,E}；有向圖定義：由點和弧組成，表示D={V,A}。6二、子圖與生成子圖子圖：圖G1中的點是圖G2中點的一部分，圖G1中的邊是圖G2中的一部分。生成圖：圖G1的點與圖G2相同，邊是其中的一部分。7三、網(wǎng)絡(luò)圖各邊賦予一定的物理量，例如距離，則叫做網(wǎng)絡(luò)圖。所賦予的物理量叫做權(quán)。權(quán)可以是：距離、時間、成本、容量等。e11表示上海到北京的鐵路長度?；?，旅客從上海到北京的車票費用8四、鏈、路、圈、回路鏈：點和邊的交錯序列（vi1,ei1,vi2,…,eik-1,vik）,若有eit=[vit,vit+1]。初等鏈：頂點和邊相互交替出現(xiàn)的點不重復(fù)序列。路：在有向圖中，鏈中每條邊的方向和鏈的走向一致的鏈。圈：起點和終點相同的鏈叫做圈?；芈罚浩瘘c和終點相同的路叫做回路。v4v1v2v5v3e1e2e3e4e5e6★任意舉出一條鏈，初等鏈，路，圈和回路。9五、連通圖和簡單圖連通圖：在圖中，任意兩點之間都有一條鏈相連，叫做連通圖。否則是非連通圖。非連通圖可以由幾個連通圖構(gòu)成。環(huán)：某邊的兩個頂點相同；多重邊：兩個頂點之間多于一條邊。簡單圖：沒有環(huán)和多重邊的圖是簡單圖。10第二節(jié)樹及最小生成樹算法什么是樹？構(gòu)造生成樹的方法最小生成樹尋找最小生成樹的方法11樹：不含圈的連通圖五個城市連通電話線問題什么是連通圖：任意兩點之間都有一條鏈相連。什么是圈：起點和終點相同的鏈叫做圈。已知有五個城市，要在它們之間架設(shè)電話線，要求任何兩個城市都可以互相通話（允許通過其它城市），并且電話線的根數(shù)最少。一、樹的基本概念12樹的基本性質(zhì)任意兩點之間有且只有一條鏈；圖是樹的充要條件：任意兩個頂點之間只有一條鏈；若樹有p個頂點，則共有q=p-1條邊；圖是樹的充要條件：連通圖，邊數(shù)=頂點數(shù)－1。五個城市連通電話線問題13生成樹的概念生成圖：圖G1的點與圖G2相同，邊是其中的一部分。如果G1是樹，則稱為生成樹。五個城市連通電話線問題14二、構(gòu)造生成樹的方法法1：破圈法：無圈的連通圖，圖中無圈。起點和終點相同的鏈叫做圈。從圖中取圈，從圈中去掉一邊，重復(fù)直到無圈。15避圈法：從圖中某一點開始生長邊，選取與入樹邊不構(gòu)成圈的邊。16三、最小生成樹生成樹不唯一架設(shè)電話線鋪設(shè)水管連接邊長度最短？17設(shè)有一個連通圖，每一邊都有一個非負(fù)權(quán)，w(e)=wij.樹的權(quán)：樹中所有邊的權(quán)之和。最小生成樹：圖中，權(quán)最小的生成樹。18將圖中求最小生成樹的問題歸結(jié)為整數(shù)規(guī)劃問題，列出數(shù)學(xué)模型。3568a12a13a24a34a36a67a47a45a78a5812471920四、尋找最小生成樹的方法（1）避圈法：開始選一條最小權(quán)的邊，以后總從與已選邊不構(gòu)成圈的那些未選邊中，選一條權(quán)最小的（相同最小權(quán)的邊，任選一條）。（2）破圈法：任取一圈，從圈中去掉一條權(quán)最大的邊（相同權(quán)的邊，任去一條），在余下圖中，重復(fù)此步驟，直到得到一個不含圈的圖，即得最小樹。21分別用破圈法和避圈法

求圖中的最小生成樹3926331447392633144722(3)矩陣求解算法步驟1：構(gòu)造一個矩陣，651572344v1v2v3v4v5v623T651572344v1v2v3v4v5v624步驟2：從矩陣中任一行開始，用T表明節(jié)點入樹，劃去該節(jié)點所在的列。T25步驟3：在標(biāo)T的行中選取最小元素，用方框表示，將對應(yīng)的邊入樹，將新得到節(jié)點標(biāo)T，劃去所在列。TT26步驟4：重復(fù)步驟3。TTT27矩陣計算方法TTTT28矩陣計算方法TTTTT29矩陣計算方法TTTTTT30矩陣計算結(jié)果3168357234832第三節(jié)最短路問題及算法什么是最短路問題？求解最短路問題的基本思路Dijstra算法：標(biāo)號法33一、什么是最短路問題？91344372858始點終點v1v2v3v42v5v6v734二、求解最短路問題的基本思路

對于在始點到終點的總體最短路徑上的任意一點，從始點到該點的最短路在總體最短路徑上。動態(tài)規(guī)劃的思路35三、Dijkstra算法對每個節(jié)點，用兩種標(biāo)號：T和P，表示從始點到該節(jié)點的距離，P是最短距離，T是目前路徑的距離。通過不斷改進T值，當(dāng)其最小時，將其改為P標(biāo)號。開始時，令始點有P=0，P標(biāo)號，其它節(jié)點T=M（無窮大）。36P(V1)=0,T(V2)=M,…第一步：T(V2)=min(T(V2),P(V1)+W12)=0+8=8T(V3)=min(T(V3),P(V1)+W13)=0+6=6T(V4)=min(T(V4),P(V1)+W14)=0+2=2Min(T(V2),T(V3),T(V4))=2★斷言：V1到V4的最短距離為2?P(V4)=237第二步：T(V3)=min(T(V3),P(V4)+W43)=min(6,2+3)=5T(V6)=min(T(V6),P(V4)+W46)=min(M,2+2)=4T(V2)=min(T(V2),P(V1)+W12)=0+8=8T(V3)=min(T(V3),P(V1)+W13)=0+6=6Min(T(V2),T(V3),T(V6))=4斷言：V1到V6的距離最短：4。P(V6)=438第一步：假定vi是新產(chǎn)生的P標(biāo)號點，考查以vi為開始點的所有弧段vivj。如果vj是P標(biāo)號點，則對vj點不再進行標(biāo)號；如果vj是T標(biāo)號點，則計算第二步：產(chǎn)生新的P標(biāo)號點，在現(xiàn)有所有的T標(biāo)號中將值最小的T標(biāo)號改為P標(biāo)號。重復(fù)上述步驟,直到?jīng)]有點可標(biāo)號。39第三步：T(V5)=min(T(V5),P(V6)+W65)=min(M,4+3)=7T(V7)=min(T(V7),P(V6)+W67)=min(M,4+9)=13T(V2)=min(T(V2),P(V1)+W12)=0+8=8T(V3)=min(T(V3),P(V4)+W43)=min(6,2+3)=5Min(T(V2),T(V3),T(V5),T(V7))=5斷言：V1到V3的距離最短：5。P(V3)=5404142問：從V1到V6的最短距離為多少？從V1到V3的距離為多少？從V3到V5的最短距離為多少？43練習(xí)：求V1到V9點的最短距離。v1v2v3v4v5v6v7v8v92349135115651246344無向圖（取消箭頭）計算方法?8623415192123456745v1v2v3v4v5v6v7v8v92349135115651246346四、Ford算法Dijkstra算法不適用于負(fù)權(quán)網(wǎng)絡(luò)具有負(fù)權(quán)的網(wǎng)絡(luò)，應(yīng)當(dāng)用Ford算法（修正標(biāo)號法）修正標(biāo)號法特點是：不但最小T標(biāo)號應(yīng)改為P標(biāo)號，P標(biāo)號也可修改，修改后P標(biāo)號再次改為T標(biāo)號。25-464472v1v3v4v98-588545St748五、尋找最短路徑的方法使用雙標(biāo)號49已知有6個村莊，相互間道路距離如下圖，擬建一所小學(xué)。A處有學(xué)生50人，B處有40人，C處有60人，D處有20人，E處有70人，F(xiàn)處有90人。問小學(xué)應(yīng)建在哪個村莊，使學(xué)生上學(xué)走的路程最短？ABDCFE266418313750第四節(jié)最大流問題網(wǎng)絡(luò)流的基本概念求解網(wǎng)絡(luò)最大流的基本原理尋找網(wǎng)絡(luò)最大流的標(biāo)號法確定網(wǎng)絡(luò)中最大流的方法51

如圖是聯(lián)接某石油銷地和產(chǎn)地的交通網(wǎng)（管道），弧旁數(shù)字表示此運輸管道的最大通過能力。產(chǎn)品從V1送到V7．現(xiàn)在要求制定一個運輸方案，使從V1到V7的產(chǎn)品運輸最多。91344372858始點終點v1v2v3v42v5v6v752一、網(wǎng)絡(luò)流的基本概念流量：某時間內(nèi)通過弧(vivj)的物質(zhì)數(shù)量fij。容量：弧的最大允許流通量。始點（發(fā)點），終點（收點），中間點91344372858始點終點v1v2v3v42v5v6v753可行流f：節(jié)點和邊的限制條件（1）容量限制條件：通過每條弧的流量不超過弧的容量。（2）平衡條件：網(wǎng)絡(luò)中的總流量等于始點凈輸出量；網(wǎng)絡(luò)中的總流量等于終點凈輸入量；流進中間點的流量等于流出該點的流量。41341231223始點終點v1v2v3v41v5v6v7網(wǎng)絡(luò)中的總流量54如何判斷流分配是否可行？41341231223始點終點v1v2v3v41v5v6v791344372858始點終點v1v2v3v42v5v6v755飽和弧：網(wǎng)絡(luò)中流量等于容量的?。环秋柡突。毫髁啃∮谌萘康幕?；正向?。憾x從始點到終點的一條鏈，與鏈方向一致的弧，為正向弧，反之為反向弧。12345691344372858始點終點v1v2v3v42v5v6v7零流?。毫髁?0的弧56增廣鏈：對于一可行流，網(wǎng)絡(luò)一條鏈滿足BDCFE10，55，211，64，15，13，26，33，317，28，3非飽和弧非零流弧57二、求解網(wǎng)絡(luò)最大流的基本原理數(shù)學(xué)模型58列出下述問題的數(shù)學(xué)模型：從三口油井1，2，3經(jīng)管道將油輸送到脫水處理廠7，8，中間經(jīng)4，5，6三個泵站。圖中弧旁數(shù)字為各管道通過的最大能力，求從油井每小時輸送到處理廠的最大流量。2010101050203015205020123456783059定理：可行流f為最大流的充分必要條件是當(dāng)且僅當(dāng)網(wǎng)絡(luò)不存在增廣鏈。若f是最大流，則不存在增廣鏈；若不存在增廣鏈，則f是最大流。60給出一初始可行流，尋找增廣鏈，若存在，則通過該增廣鏈調(diào)整、增加網(wǎng)絡(luò)流。若不存在增廣鏈，則網(wǎng)絡(luò)流不可再增加。求得最大流。流量調(diào)整多少？61三、尋找網(wǎng)絡(luò)最大流的標(biāo)號法Ford-Fulkson標(biāo)號算法：尋增廣鏈。給每個節(jié)點以一對標(biāo)號，第一個標(biāo)號表示箭尾節(jié)點，第二個標(biāo)號表示可調(diào)整量，若終點有了標(biāo)號，則找到一條增廣鏈，否則不存在增廣鏈。增廣鏈判定：vivjvivj62調(diào)整過程：在增廣鏈上，正向弧加上調(diào)整量，反向弧減去調(diào)整量。經(jīng)過調(diào)整網(wǎng)絡(luò)流v(f)增加一個調(diào)整量：4，43，05，33，36，4按上述調(diào)整，得網(wǎng)絡(luò)流是否可行？流量是否增加了？4，43，15，23，36，363646566從三口油井1，2，3經(jīng)管道將油輸送到脫水處理廠7，8，中間經(jīng)4，5，6三個泵站。圖中弧旁數(shù)字為各管道通過的最大能力，求從油井每小時輸送到處理廠的最大流量。2010101050203015205020123456783067第五節(jié)最小費用最大流問題什么是最小費用流問題？求解最小費用流的賦權(quán)圖法68一、什么是最小費用流354123152最大流分配是否唯一？引入每條流的成本！69給定網(wǎng)絡(luò)N=(V,A,c,b)和經(jīng)過網(wǎng)絡(luò)的流量v，求流在網(wǎng)絡(luò)上的最佳分布，使總費用最小。70二、求解最小費用流的賦權(quán)圖法增廣鏈費用，最小費用增廣鏈。當(dāng)沿著一條關(guān)于可行流f的增廣鏈，以調(diào)整f，得到的可行流f’，流量增加，費用變化：稱之為增廣鏈的費用。多條增廣鏈,費用不同.71對于可行流，沿最小費用增廣鏈調(diào)整流，可使流增加，并保持流費用最小。給定初始可行流（若該流量下費用最?。笞钚≠M用增廣鏈，若存在，則沿該增廣鏈調(diào)整網(wǎng)絡(luò)流；再尋求最小費用增廣鏈，直到給定的網(wǎng)絡(luò)流不存在增廣鏈為止，即為最小費用最大流。72如何求最小費用增廣鏈？增廣鏈的條件73賦權(quán)網(wǎng)絡(luò)：將飽和弧反向?qū)⒎秋柡汀⒎橇懔骰〖右环聪蚧×懔骰〔蛔兯姓蚧〉臋?quán)為該弧的費用，反向弧的權(quán)為該弧費用的相反數(shù)如此變化后，有何特點？賦權(quán)圖中，從始點到終點每條通路都是當(dāng)前可行流的增廣鏈。最小費用增廣鏈對應(yīng)賦權(quán)網(wǎng)絡(luò)的最短路。74最小費用流的實例7576777879-28081賦權(quán)網(wǎng)絡(luò)已不存在最短路（增廣鏈）82第六節(jié)網(wǎng)絡(luò)計劃技術(shù)網(wǎng)絡(luò)圖的繪制與識別網(wǎng)絡(luò)圖的時間參數(shù)計算網(wǎng)絡(luò)優(yōu)化的基本方法83甘特圖不易表現(xiàn)工程全貌不便于對各項工作的安排進行籌劃和推敲不能識別影響進度的關(guān)鍵工作不能反映一項工作不能按進度完成時對工程進度影響項目有幾項工作?能否體現(xiàn)工作之間先后關(guān)系?能否反映工作開工和完工的時間?84一、網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖的構(gòu)成作業(yè)（工作、工序、活動），箭頭表示，箭頭之上表示工作名稱，之下表示工作時間。需要消耗一定的人力、物力，經(jīng)過一定的時間完成。事項，節(jié)點表示，表示某個工作的結(jié)束和另一工作的開始。虛工作85一個基建項目網(wǎng)絡(luò)圖特點：工作數(shù)；先后時間。有了工作和事項，可按照作業(yè)的先后次序繪制網(wǎng)絡(luò)圖。86路線：從開始節(jié)點到結(jié)束節(jié)點的一條路經(jīng)，一個網(wǎng)絡(luò)圖有多條路線，每條路線有一個總時間。關(guān)鍵路線：總時間最長的路線。工期：關(guān)鍵路線的總時間87網(wǎng)絡(luò)圖的路線路線有幾條？關(guān)鍵路線是哪條？工期有多長？88以上網(wǎng)絡(luò)圖共有8條路線可以計算出這8條路線的總時間，最長的是16天。關(guān)鍵路線是當(dāng)某些工作的時間調(diào)整后，可能引起關(guān)鍵路線的變化和工期的變化。例如將工作E的時間縮短為4天，則工期縮短為13天，關(guān)鍵路線將變?yōu)?346BEG5651356BFH55389二、網(wǎng)絡(luò)圖的畫法作業(yè)的串聯(lián)：先行作業(yè)；緊前作業(yè)；緊后作業(yè)作業(yè)的并聯(lián)兩事項間只能有一項作業(yè)90網(wǎng)絡(luò)圖應(yīng)從左向右延伸，編號應(yīng)從小到大，且不重復(fù)。箭頭事項編號大于箭尾事項編號。網(wǎng)絡(luò)圖只能一個開始節(jié)點，一個終止節(jié)點。不能出現(xiàn)循環(huán)路線。盡量少交叉，采用暗橋；有層次性。始工作和結(jié)束工作繪制網(wǎng)絡(luò)圖的基本原則9192一項工作有兩個緊后工作一項工作有兩個緊前工作9394修改95三、網(wǎng)絡(luò)圖時間參數(shù)計算事項時間參數(shù)的計算作業(yè)時間參數(shù)的計算關(guān)鍵路線的尋找方法96作業(yè)時間的確定對具有標(biāo)準(zhǔn)的作業(yè)，采用單一時間估計法對一般性作業(yè)，采用三點時間估計法最樂觀時間：a最可能時間：m最悲觀時間：b計算時間期望值和方差97作業(yè)時間計算方法數(shù)學(xué)期望；方差98事項參數(shù)計算事項最早時間：以節(jié)點j為開始的各項作業(yè)最早可開工的時間。事項最遲時間：以此節(jié)點為結(jié)束的各項作業(yè)最遲必須完成時間。ijiiijj99圖上計算法1）從始節(jié)點開始（始節(jié)點最早為零），用方括號表示某節(jié)點的最早時間。2）從終節(jié)點開始（終節(jié)點最遲為工期），用三角表示某節(jié)點最遲時間。12345ABCDEHFG67841078127540411141426313501441414263135100作業(yè)時間參數(shù)的計算作業(yè)最早開始時間作業(yè)最早結(jié)束時間作業(yè)最遲開始時間作業(yè)最遲結(jié)束時間總時差單時差101作業(yè)最早時間ijii最早開始最早結(jié)束102作業(yè)最遲時間ijj最遲開始最遲結(jié)束103作業(yè)時間參數(shù)計算12345ABCDEHFG67841078127540411141426313501441414263135作業(yè)D的時間參數(shù)作業(yè)G的時間參數(shù)104總時差：在不影響總工程完工工期情況下，作業(yè)完工期可推遲的時間。單時差：不影響下一作業(yè)最早開工的情況下，一項作業(yè)完工期可推遲的時間。最早開始，最早結(jié)束最遲開始，最遲結(jié)束ijEF105時差12345ABCDEHFG67841078127540411141426313501441414263135106最早時間：由上到下；先定開始作業(yè)A的最早開始時間（0），加上作業(yè)時間得到作業(yè)的最早結(jié)束時間。凡是先行作業(yè)（B，C）只有一個為A，則，作業(yè)A的最早結(jié)束時間為該作業(yè)（B，C）的最早開始時間。若有多項先行作業(yè)，則為先行作業(yè)最早結(jié)束時間最長的為該作業(yè)的最早開始時間。107最遲時間：由下到上；最后一個作業(yè)的最早結(jié)束時間為最遲結(jié)束時間，減去作業(yè)時間為最遲開始時間；查看該作業(yè)的先行作業(yè)，先行作業(yè)的最遲結(jié)束時間為該作業(yè)的最遲開始時間。若某作業(yè)是兩個以上作業(yè)的先行作業(yè)，取小的為該作業(yè)的最遲開始時間。108關(guān)鍵路線的確定方法總時差為零的作業(yè)即是關(guān)鍵作業(yè)；關(guān)鍵作業(yè)構(gòu)成關(guān)鍵路線。109已知下表所列資料：要求(1)繪制網(wǎng)絡(luò)圖；(2)計算各工序的最早開工、最早完工，最遲開工，最遲完工時間，總時差，并指出關(guān)鍵工序；(3)若要求工程完工時間縮短2天，縮短哪些工序的時間為好。工序緊前工序工序時間工序緊前工序工序時間工序緊前工序工序時間ag,m3ec5ia,l2bh4fa,e5kf,i1c-7gb,c2lb,c7dl3h-5mc3110四、網(wǎng)絡(luò)優(yōu)化工程進度計劃編制：工期，費用，資源從工程進度角度編制，考慮工作時間關(guān)系；考慮資源條件限制，包括人員和物質(zhì)條件，如設(shè)備工時，器材，工具，廠房，運輸工具，原材料，動力，燃料。111工期限定，資源需要平衡問題：多項工作同時展開，可能導(dǎo)致資源使用不均衡，延誤關(guān)鍵工作，不能保證工期。解決措施：工期不變，就是關(guān)鍵工作時間不能調(diào)整。調(diào)整非關(guān)鍵路線上工作的開始時間，使資源實現(xiàn)平衡。112箭線下面的數(shù)字