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

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

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

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

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

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

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

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

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

9、馬爾科夫假設(shè)的“健忘性”。但是由于節(jié)點(diǎn)轉(zhuǎn)移需要一定的隨機(jī)時(shí)間，因此隨機(jī)網(wǎng)絡(luò)模型實(shí)際上是半馬爾科夫過程模型。3. 隨機(jī)網(wǎng)絡(luò)的解析法原理 在隨機(jī)網(wǎng)絡(luò)中，主要有三種邏輯輸入節(jié)點(diǎn)，“與”型、“或”型和“異或”型。但是只有“異或”型節(jié)點(diǎn)容易用數(shù)學(xué)方法進(jìn)行解析處理，所以一般情況下，需要把“與”型和“或”型節(jié)點(diǎn)用“異或”型節(jié)點(diǎn)來進(jìn)行組合以替代。在節(jié)點(diǎn)僅為互斥型輸入，而輸出為概率型的GERT網(wǎng)絡(luò)模型中，適當(dāng)?shù)匾?guī)定其活動參數(shù)的概率特征，GERT網(wǎng)絡(luò)將成為一種典型的線性系統(tǒng)，這樣可以用一種具有線性特征的“信號流圖”模型來計(jì)算隨機(jī)網(wǎng)絡(luò)中各節(jié)點(diǎn)之間的傳遞關(guān)系，并利用矩母函數(shù)的基本性質(zhì)來計(jì)算網(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ò)的分析計(jì)算，以后逐步擴(kuò)展到工程中其它線性系統(tǒng)，如電路分析、自動控制、概率與統(tǒng)計(jì)以及隨機(jī)網(wǎng)絡(luò)等。在信號流圖中，系統(tǒng)的元素用節(jié)點(diǎn)和箭頭表示。節(jié)點(diǎn)代表一定的變量，箭頭表示變量之間的關(guān)系，即節(jié)點(diǎn)之間的傳遞系數(shù)或傳遞函數(shù)。這些傳遞函數(shù)可以由一個(gè)或若干個(gè)參數(shù)組成，箭頭的方向表示所聯(lián)系節(jié)點(diǎn)之間的傳遞方向，如圖2所示。圖2信號流圖基本組成Fig.2 Basic composi

11、tion of signal flow graph 如上圖2，在任意系統(tǒng)中，對于任意兩個(gè)相鄰的節(jié)點(diǎn)i和節(jié)點(diǎn)j，如果存在一該式反映了變量之間的相乘關(guān)系，各節(jié)點(diǎn)所代表的變量之間的關(guān)系具有線性關(guān)系，只要這些線性方程組有解，即可確定信號流圖中各個(gè)節(jié)點(diǎn)上的變量值。3.2信號流圖的拓?fù)涞葍r(jià)特性根據(jù)節(jié)點(diǎn)定律，復(fù)雜信號流圖可以簡化為某種等價(jià)的信號流圖，并得到相應(yīng)的等價(jià)傳遞系數(shù)或傳遞函數(shù)，這種簡化過程，表明信號流圖的拓?fù)涞葍r(jià)特性。信號流圖的三種基本形式的等價(jià)傳遞關(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)化為以上三種形式，從而有可能得到等價(jià)的信號流圖。3.3信號流圖的拓?fù)浞匠绦盘柫鲌D的特性提供了簡化信號流圖和求解等價(jià)傳遞系數(shù)的方法。1953年，梅森提出求解信號流圖拓?fù)浞匠蹋梢郧蟪鲂盘枅D中任意兩個(gè)節(jié)點(diǎn)間的等價(jià)傳遞系數(shù)。為了說明該方程的應(yīng)用，

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

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

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

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