環(huán)境系統(tǒng)分析第3講課件

環(huán)境系統(tǒng)分析

第3講主講:李明俊教授2006.5.82005-8-31環(huán)境系統(tǒng)分析

三、圖與網(wǎng)絡(luò)方法1、圖的概念

定義：無向圖G=（V、E、φ），包含有頂點集合V，邊的集合E，以及頂點與邊之間的關(guān)系φ，有時無向圖直接寫成G=（V、E）這樣做便于將圖用數(shù)學集合形式表達出來，反之亦然。環(huán)境問題中河網(wǎng)、管網(wǎng)、工藝路線等均可通過這些圖的集合表達方式來描述，以便進一步分析處理。

2三、圖與網(wǎng)絡(luò)方法1、圖的概念2例：右圖中，G=（V、E、φ）其中：V={V1、V2、V3、V4}E={e1、e2、e3、e4、e5、e6}φ：e1=＜V1、V2＞e2=＜V1、V4＞e3=＜V2、V3＞e4=＜V3、V4＞e5=＜V1、V3＞e6=＜V2、V4＞此處＜Vi、Vj＞表示以Vi、Vj為兩端的無向邊。3例：右圖中，G=（V、E、φ）3定義：有向圖G=（V、E、ψ）,與無向圖的區(qū)別在于ψ與φψ：ek=（Vi、Vj），以Vi為起點，Vj為終點.φ：ek=＜Vi、Vj

＞

，無始終點之說。有向圖的邊帶箭頭，（對應(yīng)于實際中的河流水流方向，管道中水流方向等）

4定義：有向圖G=（V、E、ψ）,與無向圖的區(qū)別在于ψ與φ42、點與邊的關(guān)聯(lián)關(guān)系定義：設(shè)G=（V、E）是無向圖，若頂點Vk是G的一個頂點，且不存在自身回路，則Vk點的線度是G中以Vk為端點的邊數(shù)，記為d(Vk),若存在自身回路，則自身回路的頂點Vk，其線度d(Vk)也包括自身回路的邊，且記兩次。

52、點與邊的關(guān)聯(lián)關(guān)系5例：左圖中

d(V2)=3d(V3)=3d(V1)=4(存在自身回路e3)6例：左圖中6定義：對于有向圖G=（V、E、ψ），Vk為G中一個頂點，則稱以Vk為始點的有向邊數(shù)為Vk點的正線度，記為d+(Vk),稱以Vk點為終點的有向邊數(shù)為Vk點為負線度，記為d-(Vk)，Vk點的正線度與負線度之和稱為頂點Vk的線度d(Vk)。7定義：對于有向圖G=（V、E、ψ），Vk為G中一個頂點例：右圖中d+(V1)=1d-(V1)=1d(V1)=2特別對V3，有：d+(V3)=2，d-(V3)=2d(V3)=4

自身回路以V3為始點，又以V3為終點。8例：右圖中83、圖的矩陣表示法

矩陣是研究圖論的一種有力工具，特別是利用計算機來研究有關(guān)圖的算法時，首先遇到的問題是如何讓計算機來識圖，這不得不借助矩陣。

我們暫且不討論兩頂點之間存在平行的兩條邊的情況。

（1）鄰接矩陣定義：對于有向圖G=（V、E），構(gòu)造矩陣

A=(aij)nxn

93、圖的矩陣表示法9

其中：n為圖G的頂點數(shù)，稱矩陣A為圖G的鄰接矩陣。1010

1111那么，鄰接矩陣運算的含義是什么呢？先看：A2=A·A=其中a

ij(2)=∑aik·akj12那么，鄰接矩陣運算的含義是什么呢？12當且僅當aik=akj=1時，aik·

akj≠0，即從Vi到Vj有“道路”相通（Vi→Vk→

Vj），因此，a

ij(2)的值表示從V

i出發(fā)經(jīng)過某一中間站Vk然后到達Vj的路徑數(shù)目，形象地說，a

ij(2)是從Vi出發(fā)兩步到達Vj的路徑數(shù)目。

13當且僅當aik=akj=1時，aik·akj≠0同樣地，A3=A2·A=A·A2=（aij(3)）其中：（aij(3)）=∑aik(2)·akj表示從Vi出發(fā)三步到達Vj的路徑數(shù)目。一般地，aij(k)表示從Vi出發(fā)k步到達Vj的道路數(shù)目。不難理解，從Vi點出發(fā)不超過k步（包括1步、2步……k步）到達Vj點的道路數(shù)共有：B=（bij）=A+A2+A3+……+Ak=∑AL

14同樣地，A3=A2·A=A·A2=（aij(3)）14

要想弄清楚一個圖中任意兩點間有無道路相通,只須計算：Bn=（bij(n)）nxn=A+A2+A3+……+An

若bij(n)=0，則從Vi點到Vj點無路，否則有路。鄰接矩陣描述圖G中頂點與頂點的關(guān)系，而后討論的關(guān)聯(lián)矩陣將描述圖G中頂點與邊的關(guān)系。

15

要想弄清楚一個圖中任意兩點間有無道路相通,只須計算：15（2）關(guān)聯(lián)矩陣（銜接矩陣）定義：圖G=（V、E）是有向圖，其中

V={V1、V2、……、Vn},E={e1、e2、……em}

令B=(bij)nxmbij是第i個頂點與第j條邊的關(guān)系，則稱矩陣B為有向圖G的關(guān)聯(lián)矩陣。

16（2）關(guān)聯(lián)矩陣（銜接矩陣）1617171818用n個節(jié)點將河網(wǎng)分成m個河段，一般將符合下列條件之一者，可視為節(jié)點：(1)點源排放口

(2)匯流、分流點

（3）取水口

（4）人工曝氣點圖（b）所示河網(wǎng)網(wǎng)絡(luò)圖中，節(jié)點數(shù)n=8，邊（河段）數(shù)m=9，其關(guān)聯(lián)矩陣為8×9階的矩陣，即：19用n個節(jié)點將河網(wǎng)分成m個河段，一般將2020討論：①關(guān)聯(lián)矩陣表示圖的節(jié)點與邊的銜接關(guān)系，因此某一行的非零元素的數(shù)目就是與相應(yīng)的節(jié)點所銜接的邊數(shù)。②關(guān)聯(lián)矩陣中每一列只有+1和-1兩個非零元素，因此，其各個行向量總和必為零，這表明關(guān)聯(lián)矩陣B的秩小于節(jié)點數(shù)n，即B是奇異陣或者說關(guān)聯(lián)矩陣的行向量是線性相關(guān)的。

21討論：21

③關(guān)聯(lián)矩陣的任一（n-1）階方陣，其行列式的值或者為1，或者為-1，或者為0。故關(guān)聯(lián)矩陣的秩r=n-1，即關(guān)聯(lián)矩陣中的n-1個行向量是線性無關(guān)的。

④關(guān)聯(lián)矩陣去掉一行則為基本關(guān)聯(lián)矩陣記為Bf，它是滿秩的，在Bf中任取一（n-1）階方陣，若它是奇異的，則該方陣所對應(yīng)的子圖必包含回路，若它是非奇異的，則不包含回路。（全涉及樹）

22③關(guān)聯(lián)矩陣的任一（n-1）階方陣，其行列式的值或者為1，或回路：構(gòu)成閉合路徑的邊的集合。連通圖：一個圖中，任意兩節(jié)點之間至少有一條路存在，否則為不連通圖。樹：對一個連通圖來說，就是連接圖形中所有節(jié)點的最少枝路的集合，故樹中不存在回路。在樹中任意兩個節(jié)點之間，必然有一條且僅有一條路。把一個樹的任一枝邊移去，則樹變成不連通圖。具有n個節(jié)點的任何樹，其枝數(shù)恰等于n-1。

23回路：構(gòu)成閉合路徑的邊的集合。234、網(wǎng)絡(luò)分析技術(shù)

從廣義講，系統(tǒng)都是以網(wǎng)絡(luò)的形式構(gòu)成的，網(wǎng)絡(luò)理論就是撇開各種圖的具體內(nèi)容來討論這種由點、線段構(gòu)成的抽象形式的圖，從中研究其一般規(guī)律。

（1）網(wǎng)絡(luò)圖

網(wǎng)絡(luò)分析技術(shù)的基礎(chǔ)是網(wǎng)絡(luò)圖。

244、網(wǎng)絡(luò)分析技術(shù)24一項系統(tǒng)工程總是由許多工序（過程、活動、作業(yè)）組成，用箭頭“→

”來表示一道工序，把代表各個工序的各條箭頭按照工序間相互關(guān)系和相互制約的聯(lián)系，按先后次序和流程方向，從左至右按邏輯排列，并畫成圖，則為網(wǎng)絡(luò)圖。25一項系統(tǒng)工程總是由許多工序（過程、活動、作業(yè)）組例：某工程由十一道工序組成，其之間的關(guān)系為：

A工序完工后，B、C、G可同時開工；

B完工后，E、D可以同時開工；

C、D完工后，H可以開工；

G、H完工后，F(xiàn)、J可以開工；

F、E完工后，I可以開工；

I、J完工后，K可以開工。據(jù)此，網(wǎng)絡(luò)圖為：26例：某工程由十一道工序組成，其之間的關(guān)系為：26在工序交接處畫一圓圈，編上順序號，再將完成每道工序所需時間（或人力、物力、財力）標在相應(yīng)的箭桿上，利用前述圖的矩陣表示法找出所有可能的道路（從總開工事項到總完工事項），比較各條道路，可以找到所需工時（或人務(wù)、物力、財力）最多的道路（31），稱之為該網(wǎng)絡(luò)圖中的關(guān)鍵路線，或稱為主要矛盾線，常用雙線把關(guān)鍵線標出。

27在工序交接處畫一圓圈，編上順序號，再將完成每道工序所需時間（關(guān)鍵路線的完成決定著整個工程的總完工期。關(guān)鍵路線上的各個工序稱為關(guān)鍵工序，在關(guān)鍵工序中，只要其中有一個工序提前或推遲完工，則整個工期也相應(yīng)提前或推遲相同時間完工，而非關(guān)鍵工序卻沒有這樣的直接影響關(guān)系。關(guān)鍵路線可能不只一條。28關(guān)鍵路線的完成決定著整個工程的總完工期。28在非關(guān)鍵工序上可挖潛力，利用非關(guān)鍵工序的機動時間，抽調(diào)部分人力、物力去支援關(guān)鍵工序，使關(guān)鍵工序提前完工，從而縮短總完工期。

找出關(guān)鍵路徑可使執(zhí)行單位易于明確自身工作的地位和意義。29在非關(guān)鍵工序上可挖潛力，利用非關(guān)鍵工序的機動時間，抽調(diào)部分人繪制網(wǎng)絡(luò)圖應(yīng)遵守以下規(guī)定：①網(wǎng)絡(luò)圖是有向的，從左到右排列，不應(yīng)有回路（閉環(huán)）②任何兩個相關(guān)事項之間只有一支箭，即一個工序，不允許有重復情況。

30繪制網(wǎng)絡(luò)圖應(yīng)遵守以下規(guī)定：30③若幾道工序有一共同開工和完工事項，并由同一單位完成，為了簡化網(wǎng)絡(luò)圖，可以進行合并。

31③若幾道工序有一共同開工和完工事項，并由同一單位完成，為了簡虛工序：一道工序與另一道工序的依存性關(guān)系，它不消耗人力、物力和時間，只表明工序間的邏輯關(guān)系。用虛箭頭“

”表示。常見用法為：1.應(yīng)用于正確表示幾道工序之間的先后次序：

32虛工序：一道工序與另一道工序的依存性關(guān)系，它不消耗人力、物力33333434②應(yīng)用于平行作業(yè)把一道工序分成幾道工序同時平行地進行，同時完成后方能進行下一道工序。

35②應(yīng)用于平行作業(yè)35③應(yīng)用于交叉作業(yè)指相連接的幾道工序有時可以不必等待上一道工序全部作完再去作下一道工序，可交叉進行。

36③應(yīng)用于交叉作業(yè)36④應(yīng)用于外協(xié)工序

37④應(yīng)用于外協(xié)工序37關(guān)鍵路徑法（CPM）的核心就是對畫出的網(wǎng)絡(luò)草圖找出最長路徑即關(guān)鍵路徑，仔細審核各關(guān)鍵工序，盡量將串聯(lián)作業(yè)改為并聯(lián)作業(yè)（但要保證現(xiàn)實可行），以調(diào)整關(guān)鍵路徑縮短其長度，經(jīng)調(diào)整得新的網(wǎng)絡(luò)圖，重算關(guān)鍵路徑，再調(diào)整，直到滿意為止。

38關(guān)鍵路徑法（CPM）的核心就是對畫出的網(wǎng)絡(luò)草圖找5、計劃評審技術(shù)（PERT法）PERT法與CPM（關(guān)鍵路徑法）的主要區(qū)別在于前者對工作的歷時和工程的工期進行估計，引入了“不確定性”。如整個系統(tǒng)中各項任務(wù)所需的時間，各項任務(wù)在執(zhí)行中的實際完成情況以及整個工程在研制過程中技術(shù)上和生產(chǎn)上的變動因素等，這些大量的不確定性因素使整個計劃處于高度的非肯定狀態(tài)，因而它的處理方法與CPM有所不同。

395、計劃評審技術(shù)（PERT法）39PERT法并不著眼計劃進度的絕對準確性，而是在承認存在偏差的條件下，用概率論的觀點和數(shù)理統(tǒng)計的方法來衡量和預(yù)測，從許多非肯定型環(huán)節(jié)中找出最終完成計劃的可能性的規(guī)律。

PERT法對每個工序采用三點估計法，即最樂觀時間t0(表示一切進行順利而沒有耽誤時間的估計值)；最可能時間tm（表示最可能達到的時間估計）；最悲觀時間tp(表示幾乎一切都進行得不順利情況下的時間估計）。

40PERT法并不著眼計劃進度的絕對準確性，而是在承認存在偏差的按概率正態(tài)分布（假定）加權(quán)平均得期望平均時間t為：

t0+4tm+tp

t=--------------------6當各項工作歷時采取期望平均歷時t時，就相當于將非確定型網(wǎng)絡(luò)轉(zhuǎn)化為確定型網(wǎng)絡(luò)，從而可采取CPM相同的方法進行PERT網(wǎng)絡(luò)的時間計算。41按概率正態(tài)分布（假定）加權(quán)平均得期望平均時間t為：416、圖解評審法（GERT）

在前述的網(wǎng)絡(luò)計劃中的事項及工序之間的相互關(guān)系都是確定的，但在實踐中，有些事項及工序之間的相互關(guān)系卻是隨機的，前述的網(wǎng)絡(luò)圖只是隨機網(wǎng)絡(luò)（GERT網(wǎng)絡(luò)）當兩個節(jié)點之間各條弧中只有一條弧出現(xiàn)的概率為1，其它各條弧出現(xiàn)的概率為0的一種特殊情況。

426、圖解評審法（GERT）42四、水污染控制系統(tǒng)的組成

常見水污染控制系統(tǒng)主要分為四類，即河流或流域的水污染控制系統(tǒng)，工業(yè)水污染源控制系統(tǒng)，城市給水與污水系統(tǒng)和污水處理廠處理系統(tǒng)，這四類系統(tǒng)的組成分述如下：1、河流或流域的水污染控制系統(tǒng)。整個系統(tǒng)可看作由四個子系統(tǒng)所組成，即：污染源系統(tǒng)，輸水系統(tǒng)，處理系統(tǒng)和水體系統(tǒng)。

43四、水污染控制系統(tǒng)的組成432、城市給水與污水系統(tǒng)（即水的輸排處理系統(tǒng)）它是河流流域或區(qū)域污染控制系統(tǒng)的子系統(tǒng)。

442、城市給水與污水系統(tǒng)（即水的輸排處理系統(tǒng)）443、污水處理廠處理系統(tǒng)是城市給水與污水系統(tǒng)或污染源控制系統(tǒng)的一個子系統(tǒng)。

453、污水處理廠處理系統(tǒng)454、工業(yè)污染控制系統(tǒng)

污染物從產(chǎn)生到排放，可經(jīng)過改進管理，循環(huán)，回收，處理等過程，生產(chǎn)中所產(chǎn)生的污染物又隨工藝和設(shè)備的替換而變化。應(yīng)結(jié)合循環(huán)經(jīng)濟和清潔生產(chǎn)來進行系統(tǒng)分析和控制。

464、工業(yè)污染控制系統(tǒng)464747謝謝各位!請?zhí)釋氋F意見.48謝謝各位!481、有時候讀書是一種巧妙地避開思考的方法。12月-2212月-22Sunday,December11,20222、閱讀一切好書如同和過去最杰出的人談話。18:05:3518:05:3518:0512/11/20226:05:35PM3、越是沒有本領(lǐng)的就越加自命不凡。12月-2218:05:3518:05Dec-2211-Dec-224、越是無能的人，越喜歡挑剔別人的錯兒。18:05:3518:05:3518:05Sunday,December11,20225、知人者智，自知者明。勝人者有力，自勝者強。12月-2212月-2218:05:3518:05:35December11,20226、意志堅強的人能把世界放在手中像泥塊一樣任意揉捏。11十二月20226:05:35下午18:05:3512月-227、最具挑戰(zhàn)性的挑戰(zhàn)莫過于提升自我。。十二月226:05下午12月-2218:05December11,20228、業(yè)余生活要有意義，不要越軌。2022/12/1118:05:3518:05:3511December20229、一個人即使已登上頂峰，也仍要自強不息。6:05:35下午6:05下午18:05:3512月-2210、你要做多大的事情，就該承受多大的壓力。12/11/20226:05:35PM18:05:3511-12月-2211、自己要先看得起自己，別人才會看得起你。12/11/20226:05PM12/11/20226:05PM12月-2212月-2212、這一秒不放棄，下一秒就會有希望。11-Dec-2211December202212月-2213、無論才能知識多么卓著，如果缺乏熱情，則無異紙上畫餅充饑，無補于事。Sunday,December11,202211-Dec-2212月-2214、我只是自己不放過自己而已，現(xiàn)在我不會再逼自己眷戀了。12月-2218:05:3511December202218:05謝謝大家1、有時候讀書是一種巧妙地避開思考的方法。12月-2212月

環(huán)境系統(tǒng)分析

第3講主講:李明俊教授2006.5.82005-8-350環(huán)境系統(tǒng)分析

三、圖與網(wǎng)絡(luò)方法1、圖的概念

定義：無向圖G=（V、E、φ），包含有頂點集合V，邊的集合E，以及頂點與邊之間的關(guān)系φ，有時無向圖直接寫成G=（V、E）這樣做便于將圖用數(shù)學集合形式表達出來，反之亦然。環(huán)境問題中河網(wǎng)、管網(wǎng)、工藝路線等均可通過這些圖的集合表達方式來描述，以便進一步分析處理。

51三、圖與網(wǎng)絡(luò)方法1、圖的概念2例：右圖中，G=（V、E、φ）其中：V={V1、V2、V3、V4}E={e1、e2、e3、e4、e5、e6}φ：e1=＜V1、V2＞e2=＜V1、V4＞e3=＜V2、V3＞e4=＜V3、V4＞e5=＜V1、V3＞e6=＜V2、V4＞此處＜Vi、Vj＞表示以Vi、Vj為兩端的無向邊。52例：右圖中，G=（V、E、φ）3定義：有向圖G=（V、E、ψ）,與無向圖的區(qū)別在于ψ與φψ：ek=（Vi、Vj），以Vi為起點，Vj為終點.φ：ek=＜Vi、Vj

＞

，無始終點之說。有向圖的邊帶箭頭，（對應(yīng)于實際中的河流水流方向，管道中水流方向等）

53定義：有向圖G=（V、E、ψ）,與無向圖的區(qū)別在于ψ與φ42、點與邊的關(guān)聯(lián)關(guān)系定義：設(shè)G=（V、E）是無向圖，若頂點Vk是G的一個頂點，且不存在自身回路，則Vk點的線度是G中以Vk為端點的邊數(shù)，記為d(Vk),若存在自身回路，則自身回路的頂點Vk，其線度d(Vk)也包括自身回路的邊，且記兩次。

542、點與邊的關(guān)聯(lián)關(guān)系5例：左圖中

d(V2)=3d(V3)=3d(V1)=4(存在自身回路e3)55例：左圖中6定義：對于有向圖G=（V、E、ψ），Vk為G中一個頂點，則稱以Vk為始點的有向邊數(shù)為Vk點的正線度，記為d+(Vk),稱以Vk點為終點的有向邊數(shù)為Vk點為負線度，記為d-(Vk)，Vk點的正線度與負線度之和稱為頂點Vk的線度d(Vk)。56定義：對于有向圖G=（V、E、ψ），Vk為G中一個頂點例：右圖中d+(V1)=1d-(V1)=1d(V1)=2特別對V3，有：d+(V3)=2，d-(V3)=2d(V3)=4

自身回路以V3為始點，又以V3為終點。57例：右圖中83、圖的矩陣表示法

矩陣是研究圖論的一種有力工具，特別是利用計算機來研究有關(guān)圖的算法時，首先遇到的問題是如何讓計算機來識圖，這不得不借助矩陣。

我們暫且不討論兩頂點之間存在平行的兩條邊的情況。

（1）鄰接矩陣定義：對于有向圖G=（V、E），構(gòu)造矩陣

A=(aij)nxn

583、圖的矩陣表示法9

其中：n為圖G的頂點數(shù)，稱矩陣A為圖G的鄰接矩陣。5910

6011那么，鄰接矩陣運算的含義是什么呢？先看：A2=A·A=其中a

ij(2)=∑aik·akj61那么，鄰接矩陣運算的含義是什么呢？12當且僅當aik=akj=1時，aik·

akj≠0，即從Vi到Vj有“道路”相通（Vi→Vk→

Vj），因此，a

ij(2)的值表示從V

i出發(fā)經(jīng)過某一中間站Vk然后到達Vj的路徑數(shù)目，形象地說，a

ij(2)是從Vi出發(fā)兩步到達Vj的路徑數(shù)目。

62當且僅當aik=akj=1時，aik·akj≠0同樣地，A3=A2·A=A·A2=（aij(3)）其中：（aij(3)）=∑aik(2)·akj表示從Vi出發(fā)三步到達Vj的路徑數(shù)目。一般地，aij(k)表示從Vi出發(fā)k步到達Vj的道路數(shù)目。不難理解，從Vi點出發(fā)不超過k步（包括1步、2步……k步）到達Vj點的道路數(shù)共有：B=（bij）=A+A2+A3+……+Ak=∑AL

63同樣地，A3=A2·A=A·A2=（aij(3)）14

要想弄清楚一個圖中任意兩點間有無道路相通,只須計算：Bn=（bij(n)）nxn=A+A2+A3+……+An

若bij(n)=0，則從Vi點到Vj點無路，否則有路。鄰接矩陣描述圖G中頂點與頂點的關(guān)系，而后討論的關(guān)聯(lián)矩陣將描述圖G中頂點與邊的關(guān)系。

64

要想弄清楚一個圖中任意兩點間有無道路相通,只須計算：15（2）關(guān)聯(lián)矩陣（銜接矩陣）定義：圖G=（V、E）是有向圖，其中

V={V1、V2、……、Vn},E={e1、e2、……em}

令B=(bij)nxmbij是第i個頂點與第j條邊的關(guān)系，則稱矩陣B為有向圖G的關(guān)聯(lián)矩陣。

65（2）關(guān)聯(lián)矩陣（銜接矩陣）1666176718用n個節(jié)點將河網(wǎng)分成m個河段，一般將符合下列條件之一者，可視為節(jié)點：(1)點源排放口

(2)匯流、分流點

（3）取水口

（4）人工曝氣點圖（b）所示河網(wǎng)網(wǎng)絡(luò)圖中，節(jié)點數(shù)n=8，邊（河段）數(shù)m=9，其關(guān)聯(lián)矩陣為8×9階的矩陣，即：68用n個節(jié)點將河網(wǎng)分成m個河段，一般將6920討論：①關(guān)聯(lián)矩陣表示圖的節(jié)點與邊的銜接關(guān)系，因此某一行的非零元素的數(shù)目就是與相應(yīng)的節(jié)點所銜接的邊數(shù)。②關(guān)聯(lián)矩陣中每一列只有+1和-1兩個非零元素，因此，其各個行向量總和必為零，這表明關(guān)聯(lián)矩陣B的秩小于節(jié)點數(shù)n，即B是奇異陣或者說關(guān)聯(lián)矩陣的行向量是線性相關(guān)的。

70討論：21

③關(guān)聯(lián)矩陣的任一（n-1）階方陣，其行列式的值或者為1，或者為-1，或者為0。故關(guān)聯(lián)矩陣的秩r=n-1，即關(guān)聯(lián)矩陣中的n-1個行向量是線性無關(guān)的。

④關(guān)聯(lián)矩陣去掉一行則為基本關(guān)聯(lián)矩陣記為Bf，它是滿秩的，在Bf中任取一（n-1）階方陣，若它是奇異的，則該方陣所對應(yīng)的子圖必包含回路，若它是非奇異的，則不包含回路。（全涉及樹）

71③關(guān)聯(lián)矩陣的任一（n-1）階方陣，其行列式的值或者為1，或回路：構(gòu)成閉合路徑的邊的集合。連通圖：一個圖中，任意兩節(jié)點之間至少有一條路存在，否則為不連通圖。樹：對一個連通圖來說，就是連接圖形中所有節(jié)點的最少枝路的集合，故樹中不存在回路。在樹中任意兩個節(jié)點之間，必然有一條且僅有一條路。把一個樹的任一枝邊移去，則樹變成不連通圖。具有n個節(jié)點的任何樹，其枝數(shù)恰等于n-1。

72回路：構(gòu)成閉合路徑的邊的集合。234、網(wǎng)絡(luò)分析技術(shù)

從廣義講，系統(tǒng)都是以網(wǎng)絡(luò)的形式構(gòu)成的，網(wǎng)絡(luò)理論就是撇開各種圖的具體內(nèi)容來討論這種由點、線段構(gòu)成的抽象形式的圖，從中研究其一般規(guī)律。

（1）網(wǎng)絡(luò)圖

網(wǎng)絡(luò)分析技術(shù)的基礎(chǔ)是網(wǎng)絡(luò)圖。

734、網(wǎng)絡(luò)分析技術(shù)24一項系統(tǒng)工程總是由許多工序（過程、活動、作業(yè)）組成，用箭頭“→

”來表示一道工序，把代表各個工序的各條箭頭按照工序間相互關(guān)系和相互制約的聯(lián)系，按先后次序和流程方向，從左至右按邏輯排列，并畫成圖，則為網(wǎng)絡(luò)圖。74一項系統(tǒng)工程總是由許多工序（過程、活動、作業(yè)）組例：某工程由十一道工序組成，其之間的關(guān)系為：

A工序完工后，B、C、G可同時開工；

B完工后，E、D可以同時開工；

C、D完工后，H可以開工；

G、H完工后，F(xiàn)、J可以開工；

F、E完工后，I可以開工；

I、J完工后，K可以開工。據(jù)此，網(wǎng)絡(luò)圖為：75例：某工程由十一道工序組成，其之間的關(guān)系為：26在工序交接處畫一圓圈，編上順序號，再將完成每道工序所需時間（或人力、物力、財力）標在相應(yīng)的箭桿上，利用前述圖的矩陣表示法找出所有可能的道路（從總開工事項到總完工事項），比較各條道路，可以找到所需工時（或人務(wù)、物力、財力）最多的道路（31），稱之為該網(wǎng)絡(luò)圖中的關(guān)鍵路線，或稱為主要矛盾線，常用雙線把關(guān)鍵線標出。

76在工序交接處畫一圓圈，編上順序號，再將完成每道工序所需時間（關(guān)鍵路線的完成決定著整個工程的總完工期。關(guān)鍵路線上的各個工序稱為關(guān)鍵工序，在關(guān)鍵工序中，只要其中有一個工序提前或推遲完工，則整個工期也相應(yīng)提前或推遲相同時間完工，而非關(guān)鍵工序卻沒有這樣的直接影響關(guān)系。關(guān)鍵路線可能不只一條。77關(guān)鍵路線的完成決定著整個工程的總完工期。28在非關(guān)鍵工序上可挖潛力，利用非關(guān)鍵工序的機動時間，抽調(diào)部分人力、物力去支援關(guān)鍵工序，使關(guān)鍵工序提前完工，從而縮短總完工期。

找出關(guān)鍵路徑可使執(zhí)行單位易于明確自身工作的地位和意義。78在非關(guān)鍵工序上可挖潛力，利用非關(guān)鍵工序的機動時間，抽調(diào)部分人繪制網(wǎng)絡(luò)圖應(yīng)遵守以下規(guī)定：①網(wǎng)絡(luò)圖是有向的，從左到右排列，不應(yīng)有回路（閉環(huán)）②任何兩個相關(guān)事項之間只有一支箭，即一個工序，不允許有重復情況。

79繪制網(wǎng)絡(luò)圖應(yīng)遵守以下規(guī)定：30③若幾道工序有一共同開工和完工事項，并由同一單位完成，為了簡化網(wǎng)絡(luò)圖，可以進行合并。

80③若幾道工序有一共同開工和完工事項，并由同一單位完成，為了簡虛工序：一道工序與另一道工序的依存性關(guān)系，它不消耗人力、物力和時間，只表明工序間的邏輯關(guān)系。用虛箭頭“

”表示。常見用法為：1.應(yīng)用于正確表示幾道工序之間的先后次序：

81虛工序：一道工序與另一道工序的依存性關(guān)系，它不消耗人力、物力82338334②應(yīng)用于平行作業(yè)把一道工序分成幾道工序同時平行地進行，同時完成后方能進行下一道工序。

84②應(yīng)用于平行作業(yè)35③應(yīng)用于交叉作業(yè)指相連接的幾道工序有時可以不必等待上一道工序全部作完再去作下一道工序，可交叉進行。

85③應(yīng)用于交叉作業(yè)36④應(yīng)用于外協(xié)工序

86④應(yīng)用于外協(xié)工序37關(guān)鍵路徑法（CPM）的核心就是對畫出的網(wǎng)絡(luò)草圖找出最長路徑即關(guān)鍵路徑，仔細審核各關(guān)鍵工序，盡量將串聯(lián)作業(yè)改為并聯(lián)作業(yè)（但要保證現(xiàn)實可行），以調(diào)整關(guān)鍵路徑縮短其長度，經(jīng)調(diào)整得新的網(wǎng)絡(luò)圖，重算關(guān)鍵路徑，再調(diào)整，直到滿意為止。

87關(guān)鍵路徑法（CPM）的核心就是對畫出的網(wǎng)絡(luò)草圖找5、計劃評審技術(shù)（PERT法）PERT法與CPM（關(guān)鍵路徑法）的主要區(qū)別在于前者對工作的歷時和工程的工期進行估計，引入了“不確定性”。如整個系統(tǒng)中各項任務(wù)所需的時間，各項任務(wù)在執(zhí)行中的實際完成情況以及整個工程在研制過程中技術(shù)上和生產(chǎn)上的變動因素等，這些大量的不確定性因素使整個計劃處于高度的非肯定狀態(tài)，因而它的處理方法與CPM有所不同。

885、計劃評審技術(shù)（PERT法）39PERT法并不著眼計劃進度的絕對準確性，而是在承認存在偏差的條件下，用概率論的觀點和數(shù)理統(tǒng)計的方法來衡量和預(yù)測，從許多非肯定型環(huán)節(jié)中找出最終完成計劃的可能性的規(guī)律。

PERT法對每個工序采用三點估計法，即最樂觀時間t0(表示一切進行順利而沒有耽誤時間的估計值)；最可能時間tm（表示最可能達到的時間估計）；最悲觀時間tp(表示幾乎一切都進行得不順利情況下的時間估計）。

89PERT法并不著眼計劃進度的絕對準確性，而是在承認存在偏差的按概率正態(tài)分布（假定）加權(quán)平均得期望平均時間t為：

t0+4tm+tp

t=--------------------6當各項工作歷時采取期望平均歷時t時，就相當于將非確定型網(wǎng)絡(luò)轉(zhuǎn)化為確定型網(wǎng)絡(luò)，從而可采取CPM相同的方法進行PERT網(wǎng)絡(luò)的時間計算。90按概率正態(tài)分布（假定）加權(quán)平均得期望平均時間t為：416、圖解評審法（GERT）

在前述的網(wǎng)絡(luò)計劃中的事項及工序之間的相互關(guān)系都是確定的，但在實踐中，有些事項及工序之間的相互關(guān)系卻是隨機的，前述的網(wǎng)絡(luò)圖只是隨機網(wǎng)絡(luò)（GERT網(wǎng)絡(luò)）當兩個節(jié)點之間各條弧中只有一條弧出現(xiàn)的概率為1，其它各條弧出現(xiàn)的概率為0的一種特殊情況。

916、圖解評