圖示評審技術(shù)GERT(ppt)課件

1、圖示評審技術(shù)GERT Graphical Evaluation Review Technique 1. GERT概述隨機(jī)網(wǎng)絡(luò)，又稱圖示評審技術(shù)GERT，是指網(wǎng)絡(luò)計劃中活動與活動之間的邏輯關(guān)系具有不確定性，且活動的費用和時間參數(shù)也不確定，而按隨機(jī)變量進(jìn)行分析的網(wǎng)絡(luò)計劃技術(shù)。在GERT網(wǎng)絡(luò)中可以包含具有不同邏輯特征的節(jié)點，節(jié)點的引出端允許有多個概率分支，網(wǎng)絡(luò)中允許回路和自環(huán)存在，每個活動的費用和時間參數(shù)可選取任何類型的概率分布等等。 一句話，GERT隨機(jī)網(wǎng)絡(luò)完全立足于真實的項目進(jìn)程，允許考慮項目的返工，考慮項目及各個進(jìn)度路徑的選擇、廢棄，以及考慮通過反復(fù)重復(fù)某一過程而帶來的學(xué)習(xí)效應(yīng)等，基本上不受方

2、法本身先天局限的影響。隨機(jī)網(wǎng)絡(luò)的建模要素是活動（弧）和節(jié)點，其仿真過程可以想象成一定的時間流、費用流和性能流通過各項活動，并受到節(jié)點邏輯的控制流向相應(yīng)的活動中。每次仿真運行，就相當(dāng)于這些流從源節(jié)點出發(fā)，經(jīng)過相應(yīng)的節(jié)點和活動，執(zhí)行相應(yīng)的事件，最后到達(dá)網(wǎng)絡(luò)的終節(jié)點。由于網(wǎng)絡(luò)中可以選用具有各種邏輯功能不同的節(jié)點，可能導(dǎo)致三種流只經(jīng)過網(wǎng)絡(luò)中的部分節(jié)點和弧，并到達(dá)某個終止節(jié)點。網(wǎng)絡(luò)中活動和節(jié)點都有時間、費用和性能三種參數(shù)。每個活動上既可賦給弧本身所具有的三種參數(shù)，該項活動本身所需要的時間周期、消耗的費用及經(jīng)過本活動所產(chǎn)生的性能參數(shù)。同時，每項活動上還具有累積的三種參數(shù)。根據(jù)活動在網(wǎng)絡(luò)中的位置，從源節(jié)點開

3、始，時間流、費用流和性能流經(jīng)過一定的路徑，到達(dá)該活動時，所有途經(jīng)活動上三項參數(shù)的累計總和。例如，在網(wǎng)絡(luò)中某項活動完成時，在該活動上可以得到從軟件項目開始到此活動完成時刻的周期、累計費用和到此時已達(dá)到的性能值。從實際應(yīng)用來看，隨機(jī)網(wǎng)絡(luò)較之PERT/CPM（當(dāng)網(wǎng)絡(luò)中各節(jié)點之間的傳遞函數(shù)服從分布，則該網(wǎng)絡(luò)屬于PERT類型，如果這些傳遞參數(shù)都是肯定型的，則成為CPM網(wǎng)絡(luò)，他們都是隨機(jī)網(wǎng)絡(luò)的特例）已展現(xiàn)了巨大的潛力。從一九六九年GERT-E成功地用于美國“阿波羅”計劃之后，相繼在研究和發(fā)展性項目及生產(chǎn)過程中得到應(yīng)用，如科研計劃管理、可靠性分析、機(jī)械制造生產(chǎn)線的設(shè)計和分析、質(zhì)量控制、自動化倉庫管理、排隊問

4、題等等。 此外，在交通運輸、人口動態(tài)分析、計算機(jī)系統(tǒng)、商務(wù)合同簽定等方面也都得到應(yīng)用。八十年代初期，NASA又將Q-GERT和SLAM成功地用于航天飛機(jī)發(fā)射及回收過程的網(wǎng)絡(luò)計劃中。因此就GERT本身來說，理論上已經(jīng)發(fā)展到了一個相當(dāng)成熟的階段。2. GERT的構(gòu)成GERT網(wǎng)絡(luò)圖是由枝線、節(jié)點和流3個要素組成。（1）枝線又稱有向邊或傳輸元素，它是從一個節(jié)點出發(fā)，到一個節(jié)點結(jié)束的有向線段。在隨機(jī)網(wǎng)絡(luò)中，可以表示具體的工作，也可以表示工作的結(jié)果或兩工作間的相互關(guān)系。（2）節(jié)點是枝線的連接點，它既表明各枝線間的相互關(guān)系，又表示了前面枝線的結(jié)束和后面枝線的開始。在隨機(jī)網(wǎng)絡(luò)中，除了源節(jié)點和終結(jié)點外，每個節(jié)點

5、必須有一個引入枝線和一個引出枝線，同時允許有多個源節(jié)點和多個終節(jié)點，即允許多個目標(biāo)的存在。并且除了源節(jié)點和終節(jié)點外，每個節(jié)點都是由輸入端和輸出端組成。在GERT網(wǎng)絡(luò)圖中輸入端有三種邏輯關(guān)系，輸出端有兩種邏輯關(guān)系，共同構(gòu)成六種不同功能的節(jié)點，如表1所示。表1 GERT模型節(jié)點類型異或型(互斥型)輸入：至該節(jié)點的任一工作實現(xiàn)，該節(jié)點即實現(xiàn)，但在給定時間上，只有一個工作能實現(xiàn)。或型(兼有型)輸入：通向節(jié)點的任一工作實現(xiàn)，該節(jié)點即實現(xiàn)，而節(jié)點實現(xiàn)的時間是通向節(jié)點的各工作中時間最短者。與型(匯合型)輸入：當(dāng)所有引入此節(jié)點的工作都實現(xiàn)時，該節(jié)點才實現(xiàn)，節(jié)點實現(xiàn)的時間是各工作中時間中最長者。確定型(肯定型)

6、輸出：由此節(jié)點引出的工作遲早都實現(xiàn)，即自該節(jié)點發(fā)出工作被完成的概率為1。概率型(隨機(jī)型)輸出：當(dāng)節(jié)點實現(xiàn)時，所有從該節(jié)點引出的工作中只有一個工作按一定的概率得以實現(xiàn)。（3）流是反映網(wǎng)絡(luò)中的各種定量參數(shù)和節(jié)點間(或枝線)的相互定量制約關(guān)系，如工作的時間、費用，消耗的各種資源，效益以及實現(xiàn)的概率等。在GERT網(wǎng)絡(luò)模型中，每條枝線上通常會用三個參數(shù)表示流，如圖1所示：圖1隨機(jī)網(wǎng)絡(luò)基本節(jié)點關(guān)系Fig.1 Basic relationship of random networks node圖1中：U-節(jié)點1到節(jié)點2的流； -當(dāng)節(jié)點1實現(xiàn)時，枝線將要實現(xiàn)的概率； -該枝線實現(xiàn)所需要的時間，它是服從一定概率

7、分布的隨機(jī)變量； -該枝線實現(xiàn)所需要的費用，它是服從一定概率分布的隨機(jī)變量。在隨機(jī)網(wǎng)絡(luò)中，各節(jié)點可以理解為工作的狀態(tài)。隨著時間的推移，系統(tǒng)從一種狀態(tài)轉(zhuǎn)移到另一種或多種狀態(tài)時，即從某一節(jié)點轉(zhuǎn)移到其它可能的節(jié)點時，可以有不同的概率（概率分布可選取任何種類），也就是說，從某一節(jié)點以一定的概率轉(zhuǎn)移到另一節(jié)點去，節(jié)點引出的枝線允許有多個概率分支。節(jié)點和枝線不一定都實現(xiàn)，實現(xiàn)的可能性取決于節(jié)點的類型和枝線的概率系數(shù)。因為工作活動狀態(tài)之間的轉(zhuǎn)移具有概率性質(zhì)，而且狀態(tài)之間的傳遞關(guān)系也服從一定的概率分布，所以網(wǎng)絡(luò)的運行過程就具有隨機(jī)性質(zhì)。在狀態(tài)轉(zhuǎn)移中，在狀態(tài)轉(zhuǎn)移中所有的傳遞關(guān)系將表現(xiàn)為某些參數(shù)(即流)的變化，或

8、某些資源的占用。這些傳遞參數(shù)通常服從一定的概率分布，即節(jié)點之間的轉(zhuǎn)移，其傳遞參數(shù)將按一定的概率分布取不同的數(shù)值，這是隨機(jī)網(wǎng)絡(luò)的又一特征。然而，在隨機(jī)網(wǎng)絡(luò)中并不排除一部分節(jié)點之間存在肯定性的轉(zhuǎn)移關(guān)系，即轉(zhuǎn)移概率取1的轉(zhuǎn)移關(guān)系，即肯定性轉(zhuǎn)移關(guān)系。如果網(wǎng)絡(luò)中各節(jié)點之間的傳遞參數(shù)唯一地服從分布，則該網(wǎng)絡(luò)屬于PERT類型。如果這些傳遞參數(shù)都是肯定型的，那就成為CPM型網(wǎng)絡(luò)，即肯定型網(wǎng)絡(luò)了。在隨機(jī)網(wǎng)絡(luò)模型中，假設(shè)：各節(jié)點之間的轉(zhuǎn)移概率不隨時間而變化。這相當(dāng)于馬爾科夫過程中轉(zhuǎn)移概率不變的穩(wěn)定性假設(shè)，從而保證系統(tǒng)的穩(wěn)定性。在任何時點上，從節(jié)點i轉(zhuǎn)移到節(jié)點j，j只與節(jié)點i有關(guān)，而與如何到達(dá)節(jié)點j的過程無關(guān)，這是

9、馬爾科夫假設(shè)的“健忘性”。但是由于節(jié)點轉(zhuǎn)移需要一定的隨機(jī)時間，因此隨機(jī)網(wǎng)絡(luò)模型實際上是半馬爾科夫過程模型。3. 隨機(jī)網(wǎng)絡(luò)的解析法原理 在隨機(jī)網(wǎng)絡(luò)中，主要有三種邏輯輸入節(jié)點，“與”型、“或”型和“異或”型。但是只有“異或”型節(jié)點容易用數(shù)學(xué)方法進(jìn)行解析處理，所以一般情況下，需要把“與”型和“或”型節(jié)點用“異或”型節(jié)點來進(jìn)行組合以替代。在節(jié)點僅為互斥型輸入，而輸出為概率型的GERT網(wǎng)絡(luò)模型中，適當(dāng)?shù)匾?guī)定其活動參數(shù)的概率特征，GERT網(wǎng)絡(luò)將成為一種典型的線性系統(tǒng)，這樣可以用一種具有線性特征的“信號流圖”模型來計算隨機(jī)網(wǎng)絡(luò)中各節(jié)點之間的傳遞關(guān)系，并利用矩母函數(shù)的基本性質(zhì)來計算網(wǎng)絡(luò)的各種概率分布數(shù)字特征，

10、從而得到隨機(jī)網(wǎng)絡(luò)在平衡狀態(tài)下的解析解。下面我們從信號流圖理論入手，開始大概介紹一下隨機(jī)網(wǎng)絡(luò)的原理。3.1信號流圖理論簡介信號流圖是以網(wǎng)絡(luò)圖形式表示所研究系統(tǒng)(或問題)中各變量之間的相互關(guān)系，是一種線性系統(tǒng)的建模和分析工具。起初用于配電網(wǎng)絡(luò)的分析計算，以后逐步擴(kuò)展到工程中其它線性系統(tǒng)，如電路分析、自動控制、概率與統(tǒng)計以及隨機(jī)網(wǎng)絡(luò)等。在信號流圖中，系統(tǒng)的元素用節(jié)點和箭頭表示。節(jié)點代表一定的變量，箭頭表示變量之間的關(guān)系，即節(jié)點之間的傳遞系數(shù)或傳遞函數(shù)。這些傳遞函數(shù)可以由一個或若干個參數(shù)組成，箭頭的方向表示所聯(lián)系節(jié)點之間的傳遞方向，如圖2所示。圖2信號流圖基本組成Fig.2 Basic composi

11、tion of signal flow graph 如上圖2，在任意系統(tǒng)中，對于任意兩個相鄰的節(jié)點i和節(jié)點j，如果存在一該式反映了變量之間的相乘關(guān)系，各節(jié)點所代表的變量之間的關(guān)系具有線性關(guān)系，只要這些線性方程組有解，即可確定信號流圖中各個節(jié)點上的變量值。3.2信號流圖的拓?fù)涞葍r特性根據(jù)節(jié)點定律，復(fù)雜信號流圖可以簡化為某種等價的信號流圖，并得到相應(yīng)的等價傳遞系數(shù)或傳遞函數(shù)，這種簡化過程，表明信號流圖的拓?fù)涞葍r特性。信號流圖的三種基本形式的等價傳遞關(guān)系如下：串聯(lián)元素的傳遞關(guān)系為各串聯(lián)枝線上的傳遞系數(shù)的乘積，即如圖3所示，圖3串聯(lián)元素的傳遞關(guān)系Fig.3 Transitive relation of

12、 serial structure并聯(lián)元素的傳遞關(guān)系為各并聯(lián)枝線上的傳遞系數(shù)之和，即如圖4所示，即圖4并聯(lián)元素的傳遞關(guān)系Fig.4 Transitive relation of parallel structure如圖5，即圖5自環(huán)元素的傳遞關(guān)系Fig.5Transitive relation of loop-self structure任何信號流圖都可以轉(zhuǎn)化為以上三種形式，從而有可能得到等價的信號流圖。3.3信號流圖的拓?fù)浞匠绦盘柫鲌D的特性提供了簡化信號流圖和求解等價傳遞系數(shù)的方法。1953年，梅森提出求解信號流圖拓?fù)浞匠蹋梢郧蟪鲂盘枅D中任意兩個節(jié)點間的等價傳遞系數(shù)。為了說明該方程的應(yīng)用，

13、先對以下概念進(jìn)行說明。環(huán)在信號流圖中，當(dāng)開始節(jié)點與終節(jié)點完全重合時，連接這些節(jié)點的封閉路徑為環(huán)。閉信號流圖當(dāng)信號流圖中每個節(jié)點(或箭頭)都至少屬于一個環(huán)時，該圖稱為閉信號流圖。利用以上概念，可將梅森的拓?fù)浞匠瘫磉_(dá)式如下：4. GERT網(wǎng)絡(luò)的解析算法 從理論上說，把信號流圖原理和矩母函數(shù)的特征結(jié)合起來就形成GERT網(wǎng)絡(luò)解析算法的基礎(chǔ)。接下來，介紹矩母函數(shù)概念及其特征。4.1矩母函數(shù)令在網(wǎng)絡(luò)其中節(jié)點集合中，僅含“異或”型節(jié)點，隨機(jī)變量為工作集合中第(ij)個工作的周期。按節(jié)點邏輯，工作(ij)必須在節(jié)點i實現(xiàn)時才能執(zhí)行。因此，要知道工作(ij)的執(zhí)行情況，就需要知道在給定節(jié)點i實現(xiàn)的條件下，工作(

14、ij)被執(zhí)行的概率，以及的概率分布(離散變量)或概率密度函數(shù)(連續(xù)變量)。其中，S為任意實數(shù)。根據(jù)矩母函數(shù)的定義，可以得出幾種常用分布的矩母函數(shù)，如表2所示。由上面的敘述可知道，GERT網(wǎng)絡(luò)中串聯(lián)、并聯(lián)和自環(huán)結(jié)構(gòu)的等價傳遞函數(shù)與信號流圖中所描述的線性系統(tǒng)完全一致，而GERT網(wǎng)絡(luò)都是由這三種形式所構(gòu)成，從而在理論上奠定了求解GERT網(wǎng)絡(luò)解析解的基礎(chǔ)。以上是針對輸入端點為“異或”型的等價傳遞函數(shù)描述，另外兩種輸入節(jié)點-“與”型和“或”型在解析求解時，串、并聯(lián)及自環(huán)路結(jié)構(gòu)簡化方式匯總?cè)绫?所示。表3 GERT模型中串、并聯(lián)及自環(huán)路結(jié)構(gòu)簡化方式表在一個GERT網(wǎng)絡(luò)中，任何“與”型節(jié)點或“或”型節(jié)點，都

15、可以通過一定的網(wǎng)絡(luò)邏輯變換，使之轉(zhuǎn)化為“異或”型節(jié)點，即可以轉(zhuǎn)化為僅含單一“異或”型節(jié)點的隨機(jī)網(wǎng)絡(luò)，從而使GERT網(wǎng)絡(luò)的解析求解成為可能。此外，以上解析法過程，不僅限于求解GERT網(wǎng)絡(luò)由源節(jié)點到終節(jié)點之間的傳遞函數(shù)和網(wǎng)絡(luò)參數(shù)，而且，由網(wǎng)絡(luò)中任意一個節(jié)點到另一節(jié)點之間，也可通過引入閉合反饋活動，求得相應(yīng)的等價傳遞函數(shù)和其它概率參數(shù)。對于具有多個源節(jié)點和多個終節(jié)點的GERT網(wǎng)絡(luò)，也同樣是適用的。5 例題算例1：某物流企業(yè)根據(jù)實際情況對其即將進(jìn)行的自動化立體倉庫檢修作了一個GERT隨機(jī)網(wǎng)絡(luò)圖，見圖1，各檢修程序的概率及時間分布見表，其中假設(shè)各檢修程序完成的時間均服從正態(tài)分布。試討論該自動化立體倉庫的

16、維修風(fēng)險。圖1表1該網(wǎng)絡(luò)中，有3個一階環(huán)（W3，W4，W5）、（W7，W8）、（W2，W3，W4，W6，W7，W9，W11）和1個二階環(huán)（W3，W4，W5，W7，W8）由19有一條路徑（1，2，3，4，5，6，7，8，9）則該網(wǎng)絡(luò)的特征式為：代入梅森公式 由計算結(jié)果看出，節(jié)點9肯定會實現(xiàn)，這是合乎情理的，因為無論如何，該檢修項目是必定會完成的。本次自動化立體倉庫檢修需22.1327天，離散程度，即風(fēng)險為7.337天，風(fēng)險度為33.15%，由此可見，該維修項目完成的時間變化范圍較大。算例2：某發(fā)電廠按年初計劃將進(jìn)行檢修，檢修任務(wù)由各專業(yè)組負(fù)責(zé)，經(jīng)費包干，并定于20天之后進(jìn)行整體驗收。該廠的熱工專業(yè)維修組分配到維修經(jīng)費32萬元，試分析該組能否按時完成檢修任務(wù)，參加機(jī)組整體驗收，費用是否超支？該熱工專業(yè)維修組根據(jù)實際情況，將此次檢修任務(wù)時間與費用安排如下：首先制定此次檢修的具體措施，包括外請專家的聯(lián)絡(luò)、帶實習(xí)學(xué)生以及新技術(shù)工人的培訓(xùn)以及購置一些設(shè)備儀器等等；然后進(jìn)行儀器校驗檢修；儀器校驗檢修之后進(jìn)行現(xiàn)場調(diào)試，但是現(xiàn)場調(diào)試如不成功，還需返回重新進(jìn)行儀表校驗檢修，估計返回的概率為20%；現(xiàn)