隨機(jī)網(wǎng)絡(luò)計(jì)劃技術(shù)課件

1、隨機(jī)網(wǎng)絡(luò)計(jì)劃技術(shù) 合肥工業(yè)大學(xué)管理學(xué)院二00八年三月內(nèi)容安排一、概述二、決策關(guān)鍵線路法(DCPM)三、圖示評(píng)審技術(shù)(GERT)四、風(fēng)險(xiǎn)評(píng)審技術(shù)(VERT)一、概述1. CPM和PERT存在的局限性應(yīng)用假設(shè)所有活動(dòng)均為獨(dú)立；關(guān)鍵線路比其它路線長(zhǎng)；關(guān)鍵路線具有足夠多的活動(dòng)，從而可以引用中心極限定理，工期視為正態(tài)分布；每項(xiàng)活動(dòng)的周期服從 分布，其平均值近似用(a+4m+b)/6 來(lái)確定，方差為 (b-a)2/36。以上假設(shè)有其合理的地方，但也存在局限性：限定在肯定型（邏輯關(guān)系）范圍內(nèi)；不允許存在任何強(qiáng)連通成分(回路、反饋)；活動(dòng)周期限定為 分布。一、概述 1. CPM和PERT存在的局限性現(xiàn)在的項(xiàng)目

2、、試制工程和生產(chǎn)服務(wù)過(guò)程中特點(diǎn)：隨機(jī)因素不可忽視；工序間存在多次反饋；工程設(shè)計(jì)、生產(chǎn)過(guò)程在一定階段上存在方案選擇；服務(wù)過(guò)程和顧客到達(dá)的過(guò)程之間存在隨機(jī)耦合。CPM和PERT很難適應(yīng)現(xiàn)實(shí)的應(yīng)用需求，在此背景下隨機(jī)網(wǎng)絡(luò)技術(shù)應(yīng)運(yùn)而生。2. 隨機(jī)網(wǎng)絡(luò)技術(shù)的產(chǎn)生與發(fā)展背景簡(jiǎn)介：1962，E.Eisner提出了帶“決策盒”的廣義網(wǎng)絡(luò)技術(shù)(GAN)具有概率分支網(wǎng)絡(luò)的初步形式；此后，經(jīng)S.E.Elmaghroby和A.A.B.Pritsker等人逐步改進(jìn)和完善，形成GERT型網(wǎng)絡(luò)技術(shù)；與此同時(shí)，利用概率論中的矩母函數(shù)和控制論中的信號(hào)流圖理論，發(fā)展了GERT網(wǎng)絡(luò)的解析算法并于1969年形成了適應(yīng)解析算法的軟件系

3、統(tǒng)GERT-E；一、概述一、概述 2. 隨機(jī)網(wǎng)絡(luò)技術(shù)的產(chǎn)生與發(fā)展70年代，隨著仿真技術(shù)的發(fā)展， A.A.B.Pritsker等人發(fā)展了隨機(jī)網(wǎng)絡(luò)仿真技術(shù)，形成GERTS仿真系統(tǒng)及其相應(yīng)的仿真軟件。隨后，具有成本優(yōu)化的GERTS -Z，具有資源分配功能的GERTSIII-R，具有初步的排隊(duì)功能的GERTSIII-Q等相繼產(chǎn)生;1977-1979，又將GERTS的主要功能與GPSS通用仿真系統(tǒng)中的實(shí)體流技術(shù)結(jié)合，形成具有綜合功能的Q- GERT網(wǎng)絡(luò)技術(shù)及其軟件系統(tǒng)。同時(shí), Pritsker等人又將離散與連續(xù)仿真系統(tǒng)GASP-與Q- GERT結(jié)合，形成既能處理離散系統(tǒng)和網(wǎng)絡(luò)系統(tǒng)仿真，又能處理連續(xù)系統(tǒng)仿

4、真的“多種建模仿真語(yǔ)言”SLAM。在70年代初期，美國(guó)人在GERT網(wǎng)絡(luò)技術(shù)的基礎(chǔ)上發(fā)展了網(wǎng)絡(luò)數(shù)學(xué)分析器MATHNET（Mathematical Network Analyzer）,它可以把離散事件活動(dòng)、活動(dòng)時(shí)間和費(fèi)用綜合起來(lái)構(gòu)成一個(gè)概率特征進(jìn)行計(jì)算和分析。隨后又開(kāi)發(fā)了網(wǎng)絡(luò)統(tǒng)計(jì)分析器STATNET（Statistical Network Analyzer）和網(wǎng)絡(luò)求解分析器（Solving Network Analyzer）等網(wǎng)絡(luò)技術(shù)。與此同時(shí)還對(duì)MATHNET進(jìn)行了修改，重新命名為風(fēng)險(xiǎn)信息系統(tǒng)費(fèi)用分析RISCA（Risk Information System Cost Analysis）。一、概

5、述 2. 隨機(jī)網(wǎng)絡(luò)技術(shù)的產(chǎn)生與發(fā)展一、概述 2. 隨機(jī)網(wǎng)絡(luò)技術(shù)的產(chǎn)生與發(fā)展同時(shí)也開(kāi)發(fā)了全面風(fēng)險(xiǎn)評(píng)估和費(fèi)用分析網(wǎng)絡(luò)TRACENET（Total Risk Accessing Cost Analysis），從而進(jìn)入了風(fēng)險(xiǎn)評(píng)估領(lǐng)域。然而這些系統(tǒng)尚不能評(píng)定與性能有關(guān)的風(fēng)險(xiǎn)度，特別是研究和開(kāi)發(fā)中技術(shù)性能指標(biāo)能否達(dá)到規(guī)定的風(fēng)險(xiǎn)度。1972年，由Gerald L.Moeller等研究開(kāi)發(fā)VERT技術(shù)，才使風(fēng)險(xiǎn)度估計(jì)成為可能。此后，經(jīng)過(guò)改進(jìn)和擴(kuò)充，形成現(xiàn)在的VERT，為實(shí)際應(yīng)用打下了基礎(chǔ)。1979年，完成VERT-2；1981年，又完成VERT-3， VERT-3網(wǎng)絡(luò)模型主要特點(diǎn)在于面向決策，統(tǒng)籌處理時(shí)間、費(fèi)

6、用、性能與風(fēng)險(xiǎn)等關(guān)鍵性參數(shù)，能有效地解決多目標(biāo)最優(yōu)化問(wèn)題。此外，還有決策關(guān)鍵線路法DCPM、循環(huán)網(wǎng)絡(luò)技術(shù)CYCLONE都是在CPM、PERT以及GERT的基礎(chǔ)上，在應(yīng)用需求的推動(dòng)下形成的網(wǎng)絡(luò)計(jì)劃技術(shù)。一、概述 2. 隨機(jī)網(wǎng)絡(luò)技術(shù)的產(chǎn)生與發(fā)展一、概述 2. 隨機(jī)網(wǎng)絡(luò)技術(shù)的產(chǎn)生與發(fā)展實(shí)際應(yīng)用情況：1969年，GERT-E成功地應(yīng)用于“阿波羅”計(jì)劃，隨后相繼在科研計(jì)劃管理、可靠性分析、機(jī)械制造生產(chǎn)線的設(shè)計(jì)與分析、質(zhì)量控制、自動(dòng)化倉(cāng)庫(kù)管理、排隊(duì)問(wèn)題等方面得到了廣泛的應(yīng)用。此外，在交通運(yùn)輸、人口動(dòng)態(tài)分析、計(jì)算機(jī)系統(tǒng)、商務(wù)合同的簽訂等方面也得到的較好的應(yīng)用；80年代初，美國(guó)國(guó)家航空和宇宙航行局(NASA)

7、 又將Q-GERT和SLAM成功的應(yīng)用于航天飛機(jī)發(fā)射及回收過(guò)程的網(wǎng)絡(luò)計(jì)劃中。隨機(jī)網(wǎng)絡(luò)技術(shù)發(fā)展過(guò)程示意圖一、概述3. 隨機(jī)網(wǎng)絡(luò)技術(shù)的主要特點(diǎn)：在網(wǎng)絡(luò)中引入項(xiàng)目(活動(dòng))的可能選擇方案與決策，如DCPM；考慮多種隨機(jī)因素的影響，例如：科研、設(shè)計(jì)與試驗(yàn)的多次反饋、方案選擇、服務(wù)過(guò)程的隨機(jī)耦合等。不僅在活動(dòng)歷時(shí)方面可取任何概率分布，而且在邏輯上可存在自環(huán)與回路，如GERT；應(yīng)用網(wǎng)絡(luò)仿真技術(shù)形成了網(wǎng)絡(luò)仿真系統(tǒng)，如GERTS；增強(qiáng)了網(wǎng)絡(luò)節(jié)點(diǎn)的功能，綜合仿真、排隊(duì)、優(yōu)化、統(tǒng)計(jì)信息、隨機(jī)循環(huán)作業(yè)以及風(fēng)險(xiǎn)分析等多種功能，如：Q-GERT，CYCLONE，VERT等。一、概述1. CPM和PERT存在的局限性2.

8、隨機(jī)網(wǎng)絡(luò)技術(shù)的產(chǎn)生與發(fā)展3. 隨機(jī)網(wǎng)絡(luò)技術(shù)的主要特點(diǎn)隨機(jī)網(wǎng)絡(luò)計(jì)劃技術(shù)一、概述二、決策關(guān)鍵線路法(DCPM)三、圖示評(píng)審技術(shù)(GERT)四、風(fēng)險(xiǎn)評(píng)審技術(shù)(VERT)二、決策關(guān)鍵線路法DCPM 1. 概述隨著科學(xué)的發(fā)展，建筑施工規(guī)模的擴(kuò)大，人們發(fā)現(xiàn)CPM、PERT網(wǎng)絡(luò)方法在一些工程的應(yīng)用中受到了限制。例如，在一個(gè)工程中，如果有一些工序可以采用不同的施工方案施工，則整個(gè)工程就有許多不同施工方案，只有在具有不同施工方案的工序上作出正確決策，才能確定出整體最優(yōu)施工方案。顯然用CPM或PERT方法來(lái)解決這樣的問(wèn)題，就變得非常困難。再有，建筑工程施工往往存在經(jīng)濟(jì)獎(jiǎng)罰問(wèn)題，即工程提前完工給予獎(jiǎng)勵(lì)，拖后完工給予

9、懲罰，要將這一問(wèn)題與多方案一起考慮，用CPM和PERT就更加困難。二、決策關(guān)鍵線路法DCPM 1. 概述為了解決上述問(wèn)題，在CPM和PERT的基礎(chǔ)上產(chǎn)生一種新的網(wǎng)絡(luò)方法，即決策關(guān)鍵線路法(DCPM)。對(duì)于具有不同施工方案的工序，各方案所需的施工時(shí)間和費(fèi)用必然不同，所需時(shí)間越長(zhǎng)，費(fèi)用越低，DCPM將其作為決策工序，畫在同一張網(wǎng)絡(luò)圖上，一張DCPM網(wǎng)絡(luò)圖可包含多個(gè)決策工序，因此包含了該工程的所有的可行施工方案。對(duì)于經(jīng)濟(jì)獎(jiǎng)罰問(wèn)題，DCPM將時(shí)間價(jià)值，即工程提前完工的獎(jiǎng)金和拖后完工的罰金，作為總成本的一部分，以總成本最低為目標(biāo)求解。二、決策關(guān)鍵線路法DCPM 1. 概述在求解過(guò)程中，DCPM始終以總成

10、本最低為目標(biāo)，在各決策工序上進(jìn)行決策，從中選出最合理的選擇，最后確定出使總成本最低的整體最優(yōu)施工方案。DCPM具有明顯的優(yōu)點(diǎn):它不是僅僅考慮單一方案，而是把完成工程的所有方案都加以考慮；考慮了工程工期和工程費(fèi)用；考慮了工程提前完工帶來(lái)的收益和拖后完工造成的損失。二、決策關(guān)鍵線路法DCPM 1. 概述DCPM目標(biāo)：不是工期，而是把時(shí)間反映到經(jīng)濟(jì)效果上，以獲得的經(jīng)濟(jì)效果最好的為目標(biāo)，通過(guò)經(jīng)濟(jì)效果的比較來(lái)確定最優(yōu)施工方案。二、決策關(guān)鍵線路法DCPM 2. DCPM網(wǎng)絡(luò)圖繪制假設(shè)在一項(xiàng)工程中有n個(gè)工序，以集合的形式表示： J = S1,S2, ,Sn (1)其中有的工序只有一種可行的施工方案，即: S

11、i = Si,1 (2) 這樣的工序稱為非決策工序，如圖表示：IJ時(shí)間(費(fèi)用)二、決策關(guān)鍵線路法DCPM 2. DCPM網(wǎng)絡(luò)圖繪制而有些工序具有若干個(gè)可行施工方案供選擇， Si = Si,1,Si,2, ,Si,k (3) 這樣的工序稱為決策工序，如圖的形式表示:II,1I,2I,KJ.方案1方案2方案K時(shí)間(費(fèi)用)時(shí)間(費(fèi)用)時(shí)間(費(fèi)用)決策節(jié)點(diǎn)邏輯聯(lián)系決策工序的各個(gè)選擇之間存在互斥關(guān)系，即只要一個(gè)選擇完成就表示該決策工序完成，也可以說(shuō)對(duì)一個(gè)決策工序只能采用k個(gè)方案中的一個(gè)，且僅僅一個(gè)方案。用決策變量表示：(4)其中：1 第 j 個(gè)方案采用0 第 j 個(gè)方案未采用二、決策關(guān)鍵線路法DCPM

12、2. DCPM網(wǎng)絡(luò)圖繪制二、決策關(guān)鍵線路法DCPM 2. DCPM網(wǎng)絡(luò)圖繪制根據(jù)上面的定義，依照工序之間的邏輯關(guān)系，將非決策工序和決策工序用普通網(wǎng)絡(luò)節(jié)點(diǎn)(用圓圈表示)和決策點(diǎn)(用正方形表示)聯(lián)接起來(lái)，就形成雙代號(hào)DCPM網(wǎng)絡(luò)圖。在雙代號(hào)DCPM網(wǎng)絡(luò)圖中，一個(gè)決策點(diǎn)只能表示一個(gè)，決策工序的開(kāi)始，不能有兩個(gè)或多個(gè)工序的始點(diǎn)為同一決策點(diǎn)，但可以有兩個(gè)或多個(gè)工序的終點(diǎn)為同一決策點(diǎn)。除存在決策工序外，雙代號(hào)DCPM網(wǎng)絡(luò)圖與雙代號(hào)CPM及PERT網(wǎng)絡(luò)圖的形式完全相同。二、決策關(guān)鍵線路法DCPM 2. DCPM網(wǎng)絡(luò)圖繪制雙代號(hào)DCPM網(wǎng)絡(luò)圖二、決策關(guān)鍵線路法DCPM 3. 費(fèi)用計(jì)算在用決策關(guān)鍵線路法確定總體

13、最優(yōu)施工方案時(shí)，需要計(jì)算工程總費(fèi)用P，其計(jì)算公式： P = P0 + P1 + P2 式中： P0 非決策工序的費(fèi)用和； P1 決策工序的費(fèi)用和； P2 時(shí)間價(jià)值，即工程提前完工的 獎(jiǎng)金或拖后完工的罰金； 其中： 式中：Cij 非決策工序(i , j)的費(fèi)用。二、決策關(guān)鍵線路法DCPM 3. 費(fèi)用計(jì)算式中： cij 以決策點(diǎn) i 為始點(diǎn)的決策工序的第 j 個(gè)選 擇方案的費(fèi)用； dij 以決策點(diǎn) i 為始點(diǎn)的決策工序的第 j 個(gè)選 擇方案的決策變量； H 決策點(diǎn)個(gè)數(shù)； K 決策點(diǎn)具有的選擇個(gè)數(shù)(方案?jìng)€(gè)數(shù))。二、決策關(guān)鍵線路法DCPM 3. 費(fèi)用計(jì)算式中： P21 工程拖后完工的罰金； P22 工

14、程捉前完工的獎(jiǎng)金； T 計(jì)算工期； D 工程的規(guī)定工期。 P21 = ( T - D ) F P22 = ( T - D ) R式中：F 時(shí)間費(fèi)用系數(shù)，即工程拖后單位時(shí)間的罰金； R 時(shí)間費(fèi)用系數(shù)，即工程提前單位時(shí)間的獎(jiǎng)金。P2 =P21 T D P22 T D 二、決策關(guān)鍵線路法DCPM 4. DCPM問(wèn)題的求解方法 DCPM問(wèn)題的求解方法有三種:整數(shù)規(guī)劃法動(dòng)態(tài)規(guī)劃法試探法二、決策關(guān)鍵線路法DCPM1. 概述2. DCPM網(wǎng)絡(luò)圖繪制3. 費(fèi)用計(jì)算4. DCPM問(wèn)題的求解方法隨機(jī)網(wǎng)絡(luò)計(jì)劃技術(shù)一、概述二、決策關(guān)鍵線路法(DCPM)三、圖示評(píng)審技術(shù)(GERT)四、風(fēng)險(xiǎn)評(píng)審技術(shù)(VERT)三、圖示評(píng)

15、審技術(shù)(GERT) 1. GERT概述GERT是一種隨機(jī)網(wǎng)絡(luò)技術(shù)，又稱決策網(wǎng)絡(luò)技術(shù)。 它使用帶概率的有向網(wǎng)絡(luò)圖進(jìn)行分析,可以用來(lái)分析復(fù)雜多變的項(xiàng)目計(jì)劃與控制問(wèn)題；在GERT中，可以包含具有不同邏輯特征的節(jié)點(diǎn)，節(jié)點(diǎn)允許有概率分支，網(wǎng)絡(luò)中允許回路和自環(huán)存在，每項(xiàng)活動(dòng)的周期均可選取任何種類的概率分布等。即對(duì)網(wǎng)絡(luò)邏輯關(guān)系和歷時(shí)估算作概率處理；GERT使得項(xiàng)目中可能存在的許多事先難以肯定隨機(jī)因素在網(wǎng)絡(luò)圖中得以反映并計(jì)算處理。三、圖示評(píng)審技術(shù)(GERT) 1. GERT概述與CPM、PERT相比，GERT的優(yōu)越性體現(xiàn)在：節(jié)點(diǎn)和枝線不一定都實(shí)現(xiàn)，實(shí)現(xiàn)的可能性取決于節(jié)點(diǎn)的類型和枝線的概率系數(shù)；活動(dòng)時(shí)間為概率型

16、，按隨機(jī)變量分析；活動(dòng)的流向不受限制，允許環(huán)路的出現(xiàn)；節(jié)點(diǎn)間可以有一條以上的枝線；可能多個(gè)起點(diǎn)或終點(diǎn)，即允許多個(gè)目標(biāo)的存在。三、圖示評(píng)審技術(shù)(GERT) 1. GERT概述應(yīng)用情況：1966年，A.Pritsker在研究阿波羅空間系統(tǒng)的最終發(fā)射時(shí)間的過(guò)程中，提出了GERT，之后在應(yīng)用中又進(jìn)一步發(fā)展，綜合運(yùn)用網(wǎng)絡(luò)理論、概率論、信流圖理論及模擬技術(shù)，使這種方法得到進(jìn)一步完善。在此基礎(chǔ)上， GERT逐步應(yīng)用在研究開(kāi)發(fā)規(guī)劃、存貯分析飛油井鉆探、工業(yè)合同談判、費(fèi)用分析、人口動(dòng)態(tài)、維修和可靠性研究、車輛運(yùn)輸網(wǎng)絡(luò)、事故的防范及計(jì)算機(jī)算法等方面。2. 廣義活動(dòng)網(wǎng)絡(luò)GAN對(duì)于一個(gè)客觀系統(tǒng)的動(dòng)態(tài)行動(dòng)過(guò)程，可以看作

17、是系統(tǒng)狀態(tài)之間的轉(zhuǎn)移過(guò)程，即隨著時(shí)間的推移，系統(tǒng)從一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài)。隨機(jī)網(wǎng)絡(luò)中的節(jié)點(diǎn)可以表示網(wǎng)絡(luò)的狀態(tài)，而連接各節(jié)點(diǎn)之間的箭頭可以理解為狀態(tài)之間的傳遞關(guān)系。當(dāng)狀態(tài)之間的轉(zhuǎn)移具有概率性質(zhì)，而且狀態(tài)之間的傳遞關(guān)系也服從一定的概率分布時(shí)，網(wǎng)絡(luò)的運(yùn)行過(guò)程就具有隨機(jī)性質(zhì)。三、圖示評(píng)審技術(shù)(GERT)三、圖示評(píng)審技術(shù)(GERT) 2. 廣義活動(dòng)網(wǎng)絡(luò)GAN當(dāng)系統(tǒng)從一種狀態(tài)轉(zhuǎn)移到另一種或多種狀態(tài)時(shí)，可以取不同的概率。對(duì)網(wǎng)絡(luò)系統(tǒng)來(lái)說(shuō)，可以理解為從某一節(jié)點(diǎn)轉(zhuǎn)移到其它可能節(jié)點(diǎn)時(shí)具有不同的概率，即節(jié)點(diǎn)的引出箭頭允許有概率分支，這個(gè)特征使網(wǎng)絡(luò)帶有隨機(jī)性。在隨機(jī)網(wǎng)絡(luò)中，假設(shè)這種狀態(tài)轉(zhuǎn)移概率不隨時(shí)間而變化，從而保證

18、系統(tǒng)的穩(wěn)定性。然而，在隨機(jī)網(wǎng)絡(luò)中并不排除一部分節(jié)點(diǎn)之間存在肯定性的轉(zhuǎn)移關(guān)系，即轉(zhuǎn)移概率取1的轉(zhuǎn)移關(guān)系。三、圖示評(píng)審技術(shù)(GERT) 2. 廣義活動(dòng)網(wǎng)絡(luò)GAN在狀態(tài)轉(zhuǎn)移中所有的傳遞關(guān)系將表現(xiàn)為某些參數(shù)的變化，或某些資源的占用，在隨機(jī)網(wǎng)絡(luò)中，這些傳遞參數(shù)通常都服從一定的概率分布，即同樣兩個(gè)節(jié)點(diǎn)之間在兩次轉(zhuǎn)移中，其傳遞參數(shù)將按一定的概率分布取不同的數(shù)值，這是隨機(jī)網(wǎng)絡(luò)的又一特征。以上所述概率分支和傳遞參數(shù)的分布，構(gòu)成GAN網(wǎng)絡(luò)中的一般要素。這些要素可標(biāo)在網(wǎng)絡(luò)中表示活動(dòng)的箭桿上，通常用一個(gè)二維或二維以上的向量來(lái)加以描述。三、圖示評(píng)審技術(shù)(GERT) 2. 廣義活動(dòng)網(wǎng)絡(luò)GAN12u = (pu , tu

19、, cu)GAN網(wǎng)絡(luò)的一般要素，如圖示：pu 當(dāng)節(jié)點(diǎn)1實(shí)現(xiàn)時(shí)，活動(dòng)(1，2)將要實(shí)現(xiàn)的概率；tu 表示活動(dòng)(1，2)所需要的時(shí)間，它是服從一定 概率分布的隨機(jī)變量；cu 表示該活動(dòng)的費(fèi)用函數(shù)，也可能是一個(gè)隨機(jī)變量。在隨機(jī)網(wǎng)絡(luò)中，每一節(jié)點(diǎn)至少必須有一個(gè)引入箭桿和一個(gè)引出箭桿 (源節(jié)點(diǎn)和終節(jié)點(diǎn)除外)，同時(shí)允許有多個(gè)源節(jié)點(diǎn)和多個(gè)終節(jié)點(diǎn)。 三、圖示評(píng)審技術(shù)(GERT) 2. 廣義活動(dòng)網(wǎng)絡(luò)GAN在GAN網(wǎng)絡(luò)中可定義三種“輸入”類型和兩種“輸出”類型的邏輯，共可構(gòu)成六種不同邏輯功能的節(jié)點(diǎn)：“異或”型輸入凡引入此節(jié)點(diǎn)的活動(dòng)，只要有任何一個(gè)活動(dòng)完成，該節(jié)點(diǎn)即實(shí)現(xiàn)，然而，在一個(gè)給定時(shí)刻上只有一個(gè)活動(dòng)能夠完成?！?/p>

20、或”型輸入凡引入此節(jié)點(diǎn)的活動(dòng)，只要有任何一個(gè)(或一組)活動(dòng)完成，該節(jié)點(diǎn)即實(shí)現(xiàn)，即在給定時(shí)刻上允許有同時(shí)完成的活動(dòng)進(jìn)入節(jié)點(diǎn)，因此，節(jié)點(diǎn)將在所有引入活動(dòng)中的最早時(shí)刻上實(shí)現(xiàn)?！芭c”型輸入當(dāng)所有引入此節(jié)點(diǎn)的活動(dòng)都完成時(shí)，該節(jié)點(diǎn)才能實(shí)現(xiàn)。即此節(jié)點(diǎn)將在所有引入活動(dòng)中的最遲完成時(shí)刻上實(shí)現(xiàn)。三、圖示評(píng)審技術(shù)(GERT) 2. 廣義活動(dòng)網(wǎng)絡(luò)GAN概率型輸出當(dāng)此節(jié)點(diǎn)實(shí)現(xiàn)時(shí)，所有從該節(jié)點(diǎn)引出的活動(dòng)中只有一個(gè)活動(dòng)按一定的概率得以實(shí)現(xiàn)。各引出活動(dòng)實(shí)現(xiàn)概率之和必為1?？隙ㄐ洼敵鲇纱斯?jié)點(diǎn)引出的活動(dòng)遲早都要被完成，即所有引出活動(dòng)被執(zhí)行的概率均為1， PERTCPM型節(jié)點(diǎn)具有此種輸出特征。 三、圖示評(píng)審技術(shù)(GERT) 2.

21、廣義活動(dòng)網(wǎng)絡(luò)GAN案例1 新產(chǎn)品研制成功的概率與時(shí)間問(wèn)題 研制某一新產(chǎn)品的過(guò)程為：研制，試驗(yàn)，經(jīng)試驗(yàn)后研制或成功(鑒定)，或失敗(廢品處理)，或局部修改圖紙。這三個(gè)事件的發(fā)生都具有一定的概率，設(shè)它們的概率分別為0.6、0.1、0.3。若研制成功或失敗，則研制工作結(jié)束，若需局部修改圖紙，則需進(jìn)一步研制，之后再經(jīng)過(guò)試驗(yàn)。若給出研制過(guò)程各個(gè)工序的作業(yè)時(shí)間(常數(shù)，或服從某種概率分布的均值)，要求研制過(guò)程所需的時(shí)間及研制成功的概率。三、圖示評(píng)審技術(shù)(GERT) 2. 廣義活動(dòng)網(wǎng)絡(luò)GAN2. GAN 案例1 新產(chǎn)品研制成功的概率與時(shí)間問(wèn)題如果用CPM/PERT網(wǎng)絡(luò)圖表示上述的新產(chǎn)品研制的過(guò)程，且暫不考慮各

22、工序的作業(yè)時(shí)間，其形式如圖示網(wǎng)絡(luò)圖特點(diǎn)：1. 存在回路；2. 存在隨機(jī)事件；3. 存在兩個(gè)終點(diǎn)，并分別具有一定 的概率。每條弧上賦予兩個(gè)參數(shù)： 1) 給定的結(jié)點(diǎn)實(shí)現(xiàn)時(shí)，該弧實(shí)現(xiàn)的概率為p； 2) 弧上表示的工序的作業(yè)時(shí)間為t，它是個(gè)隨機(jī)變量或者是一個(gè)常數(shù)。如果是隨機(jī)變量，應(yīng)給出概率分布的密度函數(shù)、均值和方差。在隨機(jī)網(wǎng)絡(luò)中的，用期望值(均值) 表示。GAN網(wǎng)絡(luò)圖三、圖示評(píng)審技術(shù)(GERT) 2. 廣義活動(dòng)網(wǎng)絡(luò)GAN構(gòu)造GAN網(wǎng)絡(luò)模型的目的：將一個(gè)客觀系統(tǒng)用網(wǎng)絡(luò)形式表示出來(lái)，以便給人以概括的了解;研究系統(tǒng)中各項(xiàng)要素之間的相互關(guān)系，從而使原始網(wǎng)絡(luò)得以簡(jiǎn)化，以便得到系統(tǒng)的各種特性。在三種輸入邏輯中，只

23、有“異或”型節(jié)點(diǎn)最易于用數(shù)學(xué)方法進(jìn)行處理，其它兩種節(jié)點(diǎn)邏輯，至今尚未找到適當(dāng)?shù)慕馕龇椒?。在處理這類節(jié)點(diǎn)時(shí)，可以通過(guò)適當(dāng)?shù)倪壿嬜儞Q；將“或”型和“與”型節(jié)點(diǎn)轉(zhuǎn)換為“異或” 型節(jié)點(diǎn)。三、圖示評(píng)審技術(shù)(GERT) 2. 廣義活動(dòng)網(wǎng)絡(luò)GANGAN網(wǎng)絡(luò)的形式很多，然而從網(wǎng)絡(luò)結(jié)構(gòu)的特點(diǎn)來(lái)看，可以歸納成串聯(lián)型、并聯(lián)型及自環(huán)型三種基本結(jié)構(gòu)。其中并聯(lián)結(jié)構(gòu)又可按節(jié)點(diǎn)輸入端的特點(diǎn)分為并聯(lián)“與”，并聯(lián)“或”及并聯(lián)“異或”等三種結(jié)構(gòu)。3. GAN網(wǎng)絡(luò)的結(jié)構(gòu)形式(1) 串聯(lián)箭桿情況13Pe=PaPb te = ta + tb等效為132aba=(Pa, ta)b=(Pb, tb)三、圖示評(píng)審技術(shù)(GERT) (2) 并聯(lián)

24、箭桿情況“與”關(guān)系Pe= =PaPb te= maxta, tbab3221三、圖示評(píng)審技術(shù)(GERT) 3. GAN網(wǎng)絡(luò)的結(jié)構(gòu)形式 “或”關(guān)系Pe= Pa+b =(2) 并聯(lián)箭桿情況(續(xù))ab2213Pe= te= minta, tb(2) 并聯(lián)箭桿情況(續(xù))“異或”關(guān)系Pe= -“異或”關(guān)系的兩種情況：只有a實(shí)現(xiàn)： te= ta, Pe= Pa - 只有b實(shí)現(xiàn)： te= tb, Pe= Pb -ab2213(3) 自環(huán)形情況2ae13等效為c2ab13(Pb + Pc = 1)環(huán)路重復(fù)次數(shù)n持續(xù)時(shí)間te概率Pe0tbPb1tb + tcPbPc2tb + 2tcPbPc23tb + 3tc

25、PbPc3ntb + n tcPbPcn表1 持續(xù)時(shí)間te及發(fā)生的概率Pe4. GERT求解的一般程序系統(tǒng)分析，明確問(wèn)題求解的要求 首先要對(duì)系統(tǒng)的約束條件、所要求的問(wèn)題與預(yù)期的目標(biāo)、系統(tǒng)的構(gòu)成與工序的劃分，以及各工序之間的相互關(guān)系進(jìn)行周密的分析。 繪制隨機(jī)網(wǎng)絡(luò)圖 根據(jù)系統(tǒng)分析的結(jié)果，特別是工序的合理劃分，各工序之間的相互關(guān)系，正確地選擇輸入側(cè)與輸出側(cè)結(jié)點(diǎn)的符號(hào)，繪制隨機(jī)網(wǎng)絡(luò)圖。參數(shù)的確定與估計(jì) 在繪制隨機(jī)網(wǎng)絡(luò)圖的同時(shí)，就要考慮每條弧出現(xiàn)的概率及作業(yè)時(shí)間。如果作業(yè)時(shí)間是隨機(jī)變量，還要測(cè)辨它們的概率分布與密度函數(shù)，以及期望值和方差，確保隨機(jī)網(wǎng)絡(luò)必要的精度。4. GERT求解的一般程序 (續(xù))隨機(jī)網(wǎng)

26、絡(luò)的計(jì)算或模擬 通常是在計(jì)算機(jī)上進(jìn)行計(jì)算或模擬。根據(jù)系統(tǒng)目標(biāo)的要求，對(duì)時(shí)間、資源和費(fèi)用進(jìn)行計(jì)算和優(yōu)化。綜合評(píng)價(jià)與審定 對(duì)計(jì)算的結(jié)果(常數(shù)或隨機(jī)變量)進(jìn)行分析和評(píng)價(jià)。在確認(rèn)得到令人滿意的計(jì)劃方案之后，做出決策，指導(dǎo)監(jiān)督并控制計(jì)劃的執(zhí)行。5. GERT求解的基本方法GERT求解的基本方法可以分為兩大類：解析法：用隨機(jī)網(wǎng)絡(luò)中給定的參數(shù)，把概率和隨機(jī)問(wèn)題化為確定性問(wèn)題求解?；蛘卟捎眯帕鲌D理論，用等效函數(shù)法求解。模擬法：在計(jì)算機(jī)上進(jìn)行模擬試驗(yàn)，由于這種方法能夠方便而迅速的處理概率和隨機(jī)問(wèn)題，所以被廣泛地應(yīng)用。GERT求解的基本方法解析法案例一：混凝土現(xiàn)場(chǎng)供應(yīng)方案的評(píng)審合徐高速公路某段，擬建砼拌合場(chǎng)，方案

27、選擇時(shí)考慮諸多影響因素有：臨時(shí)場(chǎng)地、道路征地、建場(chǎng)安裝、材料運(yùn)輸方式等?，F(xiàn)需對(duì)砼供應(yīng)是集中還是分散的各種方案進(jìn)行評(píng)審。確定方案的限定指標(biāo)為：建成砼拌和場(chǎng)的工期不超過(guò)55天，費(fèi)用成本不超過(guò)105萬(wàn)元。根據(jù)網(wǎng)絡(luò)圖進(jìn)行計(jì)算，結(jié)果見(jiàn)下表：0.08可能費(fèi)用(萬(wàn)元)分析評(píng)審當(dāng)采用集中拌和方案時(shí): 概率P = 0.378 平均時(shí)間 t = (8.376+6.825+6.09)/0.378 = 57.3(天) 平均費(fèi)用 C = (16.968+9.66+11.865)/0.378 = 101.83(萬(wàn)元)當(dāng)采用分散拌和方案時(shí): P = 0.08 t = 47 (天) C = 112 (萬(wàn)元)評(píng)審結(jié)果 根據(jù)方案

28、確定的限定指標(biāo)，采用概率大(P=0.378)的集中拌和方案，然后比較選定1公路運(yùn)輸?shù)木唧w方案，理由是： T = 52 55 C = 101 105案例二：成批生產(chǎn)，每個(gè)成品的生產(chǎn)時(shí)間與成品率問(wèn)題。生產(chǎn)一批零件，經(jīng)加工1工序4小時(shí)完成后送檢查1工序.檢查1工序的作業(yè)時(shí)間，通過(guò)統(tǒng)計(jì)資料分析，服從指數(shù)分布，平均時(shí)間1小時(shí)，方差也是1小時(shí)檢查1工序完成后，有75%的零件合格，并轉(zhuǎn)到加工2工序；25 %的零件不合格轉(zhuǎn)到返修工序返修工序完成后轉(zhuǎn)到檢查2工序。檢查2工序完成后，有70%零件返修合格轉(zhuǎn)到加工2工序，30 %零件返修后仍不合格而報(bào)廢，加工2工序的作業(yè)時(shí)間，有60 %的零件可能要用10小時(shí)，40

29、%的零件可能要用14小時(shí).加工2工序完成后轉(zhuǎn)到檢查3工序.檢查3工序完成后，不論是由檢查1轉(zhuǎn)到加工2的，還是由檢查2轉(zhuǎn)到加工2的，均有95 %零件合格入庫(kù)，5 %零件不合格報(bào)廢.上述各道工序完成的概率,作業(yè)時(shí)間及各工序的相互關(guān)系如表所示。GERT求解的基本方法解析法試計(jì)算成批生產(chǎn)這種零件，每個(gè)成品平均需要的時(shí)間和成品率。根據(jù)已知資料和隨機(jī)網(wǎng)絡(luò)的形式，上述問(wèn)題的隨機(jī)網(wǎng)絡(luò)如圖所示。通過(guò)分析，零件加工為成品的生產(chǎn)過(guò)程可能經(jīng)過(guò)以下四條路線，其中作業(yè)時(shí)間為指數(shù)分布的按均值計(jì)算：第一條路線：12568(1,4)(0.75,1)(0.6,10)(0.95,1)路線實(shí)現(xiàn)的概率：p1 = 10.75 0.6 0

30、.95 = 0.4275所需要的時(shí)間： t1 = 4 + 1 + 10 + 1 = 16(0.25成品廢品(0.25成品廢品第二條線路：12568(1,4)(0.75,1)(0.4,14)(0.95,1)路線實(shí)現(xiàn)的概率：p2 = 10.75 0.4 0.95 = 0.285所需要的時(shí)間： t2 = 4 + 1 + 14 + 1 = 20第三條線路：路線實(shí)現(xiàn)的概率：p3 = 10.25 1 0.7 0.6 0.95 = 0.09975所需要的時(shí)間： t3 = 4 + 1 + 3 + 2 + 10 + 1 = 2112345(1,4)(0.25,1)(1,3)(0.7,2)68(0.95,1)(0

31、.6,10)(0.25成品廢品(0.25成品廢品第四條線路：12345(1,4)(0.25,1)(1,3)(0.7,2)68(0.95,1)(0.4,14)路線實(shí)現(xiàn)的概率：p4 = 10.25 1 0.7 0.4 0.95 = 0.0665所需要的時(shí)間： t4 = 4 + 1 + 3 + 2 + 14 + 1 = 25由上述四條路線可得出零件加工的成品率和每個(gè)零件需要的平均時(shí)間分別為：可以得出零件的廢品率為： Pf = 1 - PC = 0.12125(0.25成品廢品GERT求解的基本方法計(jì)算機(jī)模擬在上述的案例中，除四條成品加工路線之外，還有五條廢品加工路線。即：12567(1,4)(0.7

32、5,1)(0.6,10)(0.05,1)五12567(1,4)(0.75,1)(0.4,14)(0.05,1)六12345(1,4)(0.25,1)(1,3)(0.7,2)67(0.05,1)(0.6,10)七12345(1,4)(0.25,1)(1,3)(0.7,2)67(0.05,1)(0.4,14)八12347(1,4)(0.25,1)(1,3)(0.3,2)九每個(gè)零件經(jīng)過(guò)的加工路線是由始點(diǎn)事項(xiàng)開(kāi)始，每個(gè)工序以概率 Pi 轉(zhuǎn)移到緊后工序(直到終點(diǎn)事項(xiàng)或)。若各工序轉(zhuǎn)移到緊后工序的概率 Pi 服從(0 Pi 1)均勻分布，每個(gè)零件經(jīng)過(guò)的加工路線可以在計(jì)算機(jī)上經(jīng)隨機(jī)數(shù)來(lái)模擬。根據(jù)可能出現(xiàn)的兩

33、個(gè) (或若干個(gè)) 緊后工序的概率值將0到1的數(shù)軸分成兩個(gè) (或若干個(gè)) 區(qū)間，產(chǎn)生的隨機(jī)數(shù)落在哪個(gè)區(qū)間，就認(rèn)為那個(gè)區(qū)間對(duì)應(yīng)的工序被實(shí)現(xiàn)。GERT求解的基本方法計(jì)算機(jī)模擬例如，工序 的緊后工序?yàn)?與 ，它們的概率分別是0.7與0.3，如下圖：若產(chǎn)生的隨機(jī)數(shù)R0.6523出現(xiàn)在區(qū)間I內(nèi)，則表示工序 實(shí)現(xiàn)；若隨機(jī)數(shù)R0.9673出現(xiàn)在區(qū)間工II則表示工序 實(shí)現(xiàn)。不同的加工路線，各工序所需要的時(shí)間是服從某種分布密度函數(shù)的隨機(jī)變量。將服從(0,1)均勻分布的隨機(jī)數(shù)，通過(guò)公式逆變或者逐段逼近的方法，可以產(chǎn)生所需分布密度函數(shù)的隨機(jī)數(shù)。每個(gè)零件的加工路線與所需要的時(shí)間是隨機(jī)網(wǎng)絡(luò)的子網(wǎng)絡(luò)。在計(jì)算機(jī)上每模擬一次，

34、就得出一個(gè)子網(wǎng)。這個(gè)子網(wǎng)絡(luò)各個(gè)工序?qū)崿F(xiàn)的概率都是1，每個(gè)工序所需要的時(shí)間是個(gè)確定的量。則該子網(wǎng)絡(luò)所需要的時(shí)間也是個(gè)確定的量。因此，通過(guò)對(duì)某一零件的加工路線與所需時(shí)間的模擬，即可得出一個(gè)確定的子網(wǎng)絡(luò)(加工路線及所需時(shí)間)，并記憶該路線所經(jīng)過(guò)的工序。例如，模擬中可能出現(xiàn)以下的結(jié)果(僅舉幾例)： 第一次模擬(第一個(gè)零件加工過(guò)程) 成品112568(1,4)(1,0.9)(1,14)(1,1)t11=4+0.9+14+1=19.9第二次模擬(第二個(gè)零件加工過(guò)程) 廢品112345(1,4)(1,0.8)(1,3)(1,2.1)67(1,1)(1,10)t21=4+0.8+3+2.1+10+1=20.9

35、 出現(xiàn)的結(jié)點(diǎn)：1,2,3,4,5,6,7第三次模擬(第三個(gè)零件加工過(guò)程) 廢品212347(1,4)(1,1.2)(1,3)(1,1.9)t22=4+1.2+3+1.9=10.1 出現(xiàn)的結(jié)點(diǎn)：1,2,3,4,7繼續(xù)模擬下去，到 N 次。每次模擬所得到的加工路線，不外乎是前述的九條路線中的一條究竟是哪一條，將由工序-、-、-、-、-、-、-等八個(gè)工序出現(xiàn)的概率(隨機(jī)數(shù)出現(xiàn)在(0，1)數(shù)軸的哪一個(gè)區(qū)間)的組合而定。各條加工路線所需要的時(shí)間，取決于-、-、-、-、-等六個(gè)工序的作業(yè)時(shí)間(均為常數(shù))和-、-、-、-等四個(gè)工序的分布密度函數(shù)、均值、方差所出現(xiàn)的隨機(jī)數(shù)。第N次模擬 (加工批量為N的一批零件

36、)后，得出需要總的時(shí)間 T 和成品零件個(gè)數(shù) K ，二者之比即是每個(gè)成品零件所占用的平均時(shí)間。式中：ti 第 i 個(gè)成品零件的加工時(shí)間； tj 第 j 個(gè)廢品零件的加工時(shí)間。一批零件的成品率 Pc 等于成品零件個(gè)數(shù)與這批零件個(gè)數(shù)的百分比，即:%輸入數(shù)據(jù)一般為各工序，箭尾結(jié)點(diǎn)與箭頭結(jié)點(diǎn)的編號(hào)，各工序出現(xiàn)的概率與作業(yè)時(shí)間(隨機(jī)變量可取其均值)，以及由箭尾結(jié)點(diǎn)引出的分枝數(shù)。輸出結(jié)果一般為成品的概率，成品零件占用的平均時(shí)間及廢品零件占用的平均時(shí)間等。程序框圖如圖所示：三、圖示評(píng)審技術(shù)(GERT)1. GERT概述2. 廣義活動(dòng)網(wǎng)絡(luò)GAN3. GAN網(wǎng)絡(luò)的結(jié)構(gòu)形式4. GERT求解的一般程序5. GERT

37、求解的基本方法（1）解析法（2）模擬法隨機(jī)網(wǎng)絡(luò)計(jì)劃技術(shù)一、概述二、決策關(guān)鍵線路法(DCPM)三、圖示評(píng)審技術(shù)(GERT)四、風(fēng)險(xiǎn)評(píng)審技術(shù)(VERT)四、風(fēng)險(xiǎn)評(píng)審技術(shù)(VERT) 1. 概述VERT(Venture Evaluation and Review Technique)是在CPM和PERT的基礎(chǔ)上，經(jīng)過(guò)GERT和計(jì)算機(jī)程序模擬技術(shù)逐步加以擴(kuò)充、改進(jìn)，于1972年研制出的一種風(fēng)險(xiǎn)評(píng)審網(wǎng)絡(luò)分析方法。1979年即完成VERT-2。1981年又完成了VERT-3。 VERT-3在國(guó)外已受到普遍重視，被認(rèn)為是唯一能充分而同等地衡量處理多個(gè)關(guān)鍵性參數(shù)及其相互作用的網(wǎng)絡(luò)技術(shù)。VERT-3網(wǎng)絡(luò)模型的主

38、要特點(diǎn)在于面向決策，統(tǒng)籌處理時(shí)間、費(fèi)用、性能與風(fēng)險(xiǎn)等關(guān)鍵性參數(shù)，有效地解決多目標(biāo)最優(yōu)化問(wèn)題。因此具有較大的實(shí)用價(jià)值。2. VERT的由來(lái)與演變1958年美國(guó)海軍特種計(jì)劃局在研制北極星導(dǎo)彈的過(guò)程中首次應(yīng)用了計(jì)劃評(píng)審技術(shù)，提高了工作效率，縮短了計(jì)劃工期，使原計(jì)劃提前兩年完成。差不多與此同時(shí)，美國(guó)杜邦(Dupont)公司獨(dú)立研制了關(guān)鍵路線法，用于施工設(shè)計(jì)和維修計(jì)劃，取得了顯著效果。但是PERT與CPM都是肯定性網(wǎng)絡(luò)模型，其中每項(xiàng)活動(dòng)都必須成功完成，而現(xiàn)實(shí)中存在著風(fēng)險(xiǎn)和不確定性。因而在實(shí)施過(guò)程中可能出現(xiàn)種種偶然事件。例如，進(jìn)行某項(xiàng)測(cè)試工作可能完全成功，也可能部分成功，甚至可能失敗。當(dāng)未來(lái)局勢(shì)呈現(xiàn)“模糊

39、”或不肯定時(shí)，PERT與CPM便不能適應(yīng)這種隨機(jī)局勢(shì)。2. VERT的由來(lái)與演變(續(xù))隨著PERT與CPM應(yīng)用范圍的擴(kuò)大，于是產(chǎn)生了如何加強(qiáng)網(wǎng)絡(luò)分析的效能問(wèn)題。例如：怎樣改善資源分配，力求縮短工期，降低成本，減少風(fēng)險(xiǎn)，實(shí)現(xiàn)最優(yōu)化目標(biāo)；怎樣減少關(guān)鍵性活動(dòng)的性能而不致過(guò)多地?fù)p失經(jīng)濟(jì)效益；怎樣降低非關(guān)鍵性活動(dòng)的費(fèi)用或風(fēng)險(xiǎn)而不增加計(jì)劃總工期；怎樣改進(jìn)網(wǎng)絡(luò)技術(shù)，控制時(shí)間、費(fèi)用與性能參數(shù)的最佳組合等等。2. VERT的由來(lái)與演變(續(xù))1966年普利茨克爾(Pritsker)等提出的圖示評(píng)審技術(shù)是擴(kuò)展網(wǎng)絡(luò)模型增進(jìn)隨機(jī)適應(yīng)性的重大突破之一。但是，GERT把費(fèi)用看成是從屬于時(shí)間的變量，未能對(duì)預(yù)算費(fèi)用進(jìn)行必要的控

40、制并確定其對(duì)進(jìn)度的影響。20世紀(jì)60年代末和70年代初期，美國(guó)國(guó)防經(jīng)濟(jì)部門的許多重要項(xiàng)目出現(xiàn)了巨額費(fèi)用超支和進(jìn)度時(shí)間超限，終于使有關(guān)當(dāng)局認(rèn)清了風(fēng)險(xiǎn)分析的必要性。于是提出運(yùn)用網(wǎng)絡(luò)模擬技術(shù)解決風(fēng)險(xiǎn)決策問(wèn)題。2. VERT的由來(lái)與演變(續(xù))1970年美國(guó)陸軍研制出名為MATHNET的計(jì)算機(jī)程序模擬技術(shù)。其后，又陸續(xù)產(chǎn)生了若干改進(jìn)的計(jì)算機(jī)程序網(wǎng)絡(luò)技術(shù)。例如；風(fēng)險(xiǎn)信息系統(tǒng)費(fèi)用分析(Risk lnformation System Cost Analysis)簡(jiǎn)稱RISCA，以及網(wǎng)絡(luò)統(tǒng)計(jì)分析器STATNET(Statistical Network Analyzer)與網(wǎng)絡(luò)求解分析器SOVNET (Solvi

41、ng Network Analyzer)，全面風(fēng)險(xiǎn)評(píng)估和費(fèi)用分析網(wǎng)絡(luò)TRACENET（Total Risk Accessing Cost Analysis）等。2. VERT的由來(lái)與演變(續(xù))1972年莫埃勒爾(MoellerG.L.)在MATHNET與STATNET的基礎(chǔ)上研制出風(fēng)險(xiǎn)評(píng)審技術(shù)VERT。此法在網(wǎng)絡(luò)的節(jié)點(diǎn)邏輯與數(shù)學(xué)關(guān)系式的處理上有較大的適應(yīng)性，能統(tǒng)籌考慮“時(shí)間、費(fèi)用、性能”并給予同等重要性和處理層次。1979年依據(jù)VERT和TRACENET計(jì)算機(jī)程序網(wǎng)絡(luò)技術(shù)完成了VERT-2，在此基礎(chǔ)上，莫埃勒爾和迪格曼(Digman L.A.)又于1981年研制成一種全新的計(jì)算機(jī)，模擬決策網(wǎng)絡(luò)

42、技術(shù) VERT-3。2. VERT的由來(lái)與演變(續(xù))VERT-3不僅能分析完成計(jì)劃的程度，顯示各項(xiàng)成果的范圍、性能與費(fèi)用水平，同時(shí)，還能突出顯示關(guān)鍵最優(yōu)路線，提供成功的可能性和失敗的風(fēng)險(xiǎn)度。因而在處理風(fēng)險(xiǎn)決策問(wèn)題上有較大的價(jià)值。3. VERT的基本概念風(fēng)險(xiǎn)評(píng)審技術(shù)把網(wǎng)絡(luò)系統(tǒng)中活動(dòng)及節(jié)點(diǎn)(事件)實(shí)際情況與相應(yīng)所需的時(shí)間、費(fèi)用、運(yùn)行效果聯(lián)系起來(lái)，并用數(shù)學(xué)關(guān)系描述，應(yīng)用計(jì)算機(jī)大量模擬結(jié)果作為依據(jù)，進(jìn)行綜合分析評(píng)估，從而增強(qiáng)了描述和分析現(xiàn)實(shí)世界的能力。構(gòu)成VERT網(wǎng)絡(luò)的基本元素是節(jié)點(diǎn)和箭線(弧)。用長(zhǎng)方形符號(hào)表示節(jié)點(diǎn)，它代表事件或決策點(diǎn)；用箭線(弧)表示活動(dòng)或工作。描述活動(dòng)的基本參數(shù)有：占用的時(shí)間T，

43、所擔(dān)負(fù)的費(fèi)用C，以及完成活動(dòng)所產(chǎn)生的效能P(生產(chǎn)水平，投資效益等)。3. VERT的基本概念兩類節(jié)點(diǎn)：分離邏輯節(jié)點(diǎn)與單元邏輯節(jié)點(diǎn)。前者是最常用的節(jié)點(diǎn)，它具有分離的輸入邏輯與輸出邏輯。后者具有單元邏輯，同時(shí)包括輸入與輸出兩種作用，這類節(jié)點(diǎn)應(yīng)用較少。節(jié)點(diǎn)起約束或控制網(wǎng)絡(luò)流進(jìn)入弧的作用，而弧則可攜帶網(wǎng)絡(luò)流從輸出節(jié)點(diǎn)到輸入節(jié)點(diǎn)，通過(guò)網(wǎng)絡(luò)流表示活動(dòng)和節(jié)點(diǎn)的實(shí)際完成情況。分離節(jié)點(diǎn)的輸入邏輯共有下列四種：起始輸入邏輯：用于網(wǎng)絡(luò)流的起始輸入節(jié)點(diǎn)。與輸入邏輯：要求在合成輸入流送至輸出邏輯進(jìn)行適當(dāng)分配前所有輸入箭線都必須成功完成。部分與輸入邏輯：除要求流過(guò)該節(jié)點(diǎn)前至少有一支輸入箭線成功完成外，部分與輸入邏輯跟與輸

44、入邏輯基本相似。不過(guò)，前者在處理之前將等待所有輸入箭線都進(jìn)入網(wǎng)絡(luò)或從網(wǎng)絡(luò)中消失。或輸入邏輯：和部分與輸入邏輯十分相似。也要求流過(guò)該節(jié)點(diǎn)前至少有一支輸入箭線成功完成，但在處理前不需等待所有輸入箭線都進(jìn)入或從網(wǎng)絡(luò)消失。3. VERT的基本概念分離節(jié)點(diǎn)的輸出邏輯有以下六種：終端(TERMINAL)輸出邏輯：網(wǎng)絡(luò)終端節(jié)點(diǎn)，亦即網(wǎng)絡(luò)流的收點(diǎn)。全(ALL)輸出邏輯：同時(shí)啟動(dòng)由該節(jié)點(diǎn)引出的全部輸出箭線。蒙特卡洛(MONTE CARLO)輸出邏輯：應(yīng)用蒙特卡洛方法，每次模擬迭代僅處理一支輸出箭線。分離節(jié)點(diǎn)的輸出邏輯有以下六種(續(xù))：濾子1(FILTERl)輸出邏輯：根據(jù)節(jié)點(diǎn)輸出箭線上所加的約束條件(時(shí)間與或費(fèi)

45、用與或性能值的上、下限)為聯(lián)合滿足或單獨(dú)滿足進(jìn)行分別處理。若滿足約束條件，則該箭線將予以處理。濾子2(FILTER2)輸出邏輯：跟濾子1的的區(qū)別在于，輸出箭線只承擔(dān)一個(gè)約束條件并只能同部分與輸入邏輯共用。濾子3(FILTER 3)輸出邏輯 約束條件不是界限值而是原先處理過(guò)的其他箭線的名稱(指定前導(dǎo)活動(dòng)的成功或失敗作為觸發(fā)條件)。單元邏輯節(jié)點(diǎn)的四種形式“比較”節(jié)點(diǎn)(Compare)：傳遞全部流至輸出箭線；“偏好”節(jié)點(diǎn)(Preferred)：把經(jīng)過(guò)的流傳遞給受偏好 的輸出箭線；“排隊(duì)”節(jié)點(diǎn)(Queue)：模擬排隊(duì)功能，將經(jīng)過(guò)的流按一定的規(guī)則進(jìn)行排隊(duì)處理；“分類”節(jié)點(diǎn)(Sort)：對(duì)節(jié)點(diǎn)后的輸出箭線

46、依次編號(hào)，將通過(guò)的流依編號(hào)先后傳遞給個(gè)箭線。VERT的計(jì)算機(jī)模擬就是創(chuàng)設(shè)網(wǎng)絡(luò)流從起始節(jié)點(diǎn)通過(guò)網(wǎng)絡(luò)流向終端節(jié)點(diǎn)，產(chǎn)生模擬問(wèn)題的試驗(yàn)解。為了能取得足夠的子樣數(shù)，此模擬過(guò)程可按用戶要求重復(fù)進(jìn)行多次。節(jié)點(diǎn)的完成時(shí)間、費(fèi)用與性能信息利用下列統(tǒng)計(jì)值求得：相對(duì)分布頻率，累積分布頻率，觀測(cè)的平均值，中誤差(子樣的標(biāo)準(zhǔn)差)，中誤差系數(shù)(中誤差平均值)，眾數(shù)，中位數(shù)，峰度與偏度。這類信息可對(duì)所有節(jié)點(diǎn)予以顯示。還可按用戶要求的時(shí)限(逐年或按月份) 輸出所擔(dān)負(fù)的網(wǎng)絡(luò)總費(fèi)用與性能值。3. VERT的基本概念3. VERT的基本概念VERT網(wǎng)絡(luò)一般有一個(gè)或若干終端節(jié)點(diǎn), 用于收集完成計(jì)劃的成功次數(shù)，并有一個(gè)或若干終端節(jié)點(diǎn)

47、,用于收集未完成計(jì)劃的失敗次數(shù)。這些不同終端節(jié)點(diǎn)成功或失敗次數(shù)分別同迭代總數(shù)的相比即表明計(jì)劃成功或失敗的可能性（或風(fēng)險(xiǎn)度）。4. VERT的建模步驟VERT 采用網(wǎng)絡(luò)結(jié)構(gòu)來(lái)描述研究對(duì)象, 使問(wèn)題系統(tǒng)化、 邏輯化和具體化。具體步驟如下: (1) 確定所分析對(duì)象的情況并指出分析目標(biāo)； (2) 按所確定的情況繪制初步網(wǎng)絡(luò)圖, 使分析的問(wèn)題具體化 (3) 收集與決策過(guò)程有關(guān)的各種活動(dòng)的數(shù)據(jù), 如概率分布、 數(shù)學(xué)關(guān)系表達(dá)式等； (4) 構(gòu)成能用于仿真運(yùn)算的邏輯網(wǎng)絡(luò)圖, 進(jìn)行仿真運(yùn)算； (5) 獲得仿真結(jié)果。5.蒙特卡洛隨機(jī)模擬方法(1) 蒙特卡洛隨機(jī)模擬從經(jīng)濟(jì)上講，當(dāng)不能建立精確的數(shù)學(xué)模型或模擬太復(fù)雜問(wèn)

48、題而不能作及時(shí)評(píng)價(jià)時(shí)，可用此法作可靠性預(yù)測(cè)。蒙特卡洛隨機(jī)模擬是一種通過(guò)隨機(jī)變量統(tǒng)計(jì)試驗(yàn)，隨機(jī)模擬解決工程問(wèn)題的數(shù)值方法。其基本假定是風(fēng)險(xiǎn)因素相互獨(dú)立，隨機(jī)發(fā)生，在此前提下，進(jìn)行統(tǒng)計(jì)試驗(yàn)，從而得出目標(biāo)函數(shù)的概率分布及其統(tǒng)計(jì)特征值。模擬過(guò)程主要是通過(guò)計(jì)算機(jī)產(chǎn)生隨機(jī)數(shù)，并將此隨機(jī)數(shù)作為累計(jì)概率分布與隨機(jī)變量概率分布相對(duì)照，從而得到變量的試驗(yàn)數(shù)據(jù)，進(jìn)行足夠多的試驗(yàn)，甚至上萬(wàn)次的試驗(yàn)，使之符合大數(shù)定律的要求，便可得到變量的分布。然后求得期望值和方差。5.蒙特卡洛隨機(jī)模擬方法(1) 蒙特卡洛隨機(jī)模擬蒙特卡洛法的基本思路是運(yùn)用一連串隨機(jī)數(shù)來(lái)表示一項(xiàng)事件的概率分配。然后利用任意取得的隨機(jī)數(shù)從該項(xiàng)概率分配中獲得

49、隨機(jī)變量值。該方法的缺點(diǎn)是沒(méi)有計(jì)入風(fēng)險(xiǎn)因素之間的相互影響，使得風(fēng)險(xiǎn)估計(jì)結(jié)果可能偏小。(2) 舉例：某商店為了估算每天的平均營(yíng)業(yè)額，對(duì)商店每天接待的顧客數(shù)和每位顧客的購(gòu)物金額作了100天的統(tǒng)計(jì)。每天接待顧客人數(shù)30-3940-4950-5960-6970-79以上發(fā)生天數(shù)52540282每位顧客購(gòu)貨金額（元）10-1920-2930-3940-4950-59以上發(fā)生次數(shù)403015105表1. 每天接待的顧客數(shù)統(tǒng)計(jì)表表2. 每位顧客購(gòu)貨金額統(tǒng)計(jì)表5.蒙特卡洛隨機(jī)模擬方法根據(jù)表1和表2，可以列出相應(yīng)的概率分布：每天接待顧客人次概率30-3940-4950-5960-6970-79以上0.050.2

50、50.400.280.02每位顧客購(gòu)貨金額（元）概率10-1920-2930-3940-4950-59以上0.400.300.150.100.05表3. 每天接待顧客人次概率分布表表4. 每位顧客購(gòu)貨金額概率分布表以隨機(jī)數(shù)01，02，98，99，00來(lái)表示上述概率分布，如表所示：每天接待顧客人次概率隨機(jī)數(shù)取值30-3940-4950-5960-6970-79以上0.050.250.400.280.0201-0506-3031-7071-9899-00每位顧客購(gòu)貨金額概率隨機(jī)數(shù)取值10-1920-2930-3940-4950-59以上0.400.300.150.100.0501-4041-707

51、1-8586-9596-00任意取隨機(jī)數(shù)，如取隨機(jī)數(shù)為10，由表可知，這天來(lái)商店的顧客在40-49人次之間，可取平均數(shù)為45天，又仍取隨機(jī)數(shù)為39，則知每位顧客購(gòu)貨金額在10-19元之間，取平均數(shù)15元。設(shè)仿真延續(xù)時(shí)間定為30天，則分別任意取隨機(jī)數(shù)30次，再求得每天接待顧客平均人次乘以每位顧客購(gòu)貨金額，再除以30可得每天的平均營(yíng)業(yè)額。隨機(jī)數(shù)的產(chǎn)生方法:隨機(jī)數(shù)表(random number table)法隨機(jī)數(shù)發(fā)生器利用數(shù)學(xué)方法產(chǎn)生隨機(jī)數(shù)如：隨機(jī)數(shù)生成法、倍積取中法、同余數(shù)法等。6. VERT模擬過(guò)程風(fēng)險(xiǎn)評(píng)審技術(shù)模型建立后，按規(guī)定格式輸入計(jì)算機(jī)，進(jìn)行大量的重復(fù)的計(jì)算機(jī)模擬，并按要求格式輸出結(jié)果。

52、每次模擬就是由網(wǎng)絡(luò)的始端激發(fā)流，然后模擬執(zhí)行(即通過(guò)流)全過(guò)程。模擬的全過(guò)程如圖所示。(1) 參數(shù)的輸入 模擬前必須確定各項(xiàng)參數(shù)。通常有三類參數(shù)：控制參數(shù)、箭線(活動(dòng)參數(shù))及節(jié)點(diǎn)參數(shù)?？刂茀?shù)是整個(gè)網(wǎng)絡(luò)的參數(shù)，包括：數(shù)據(jù)的輸入和輸出方式，打印要求，計(jì)算的時(shí)間區(qū)段，確定隨機(jī)變量的控制值以及模擬次數(shù)等。箭線參數(shù)包括：箭線編號(hào)及名稱，前導(dǎo)及后繼節(jié)點(diǎn)，發(fā)生概率，延續(xù)時(shí)間，費(fèi)用，運(yùn)行效果，參數(shù)獲得方式。節(jié)點(diǎn)參數(shù)包括：節(jié)點(diǎn)編號(hào)及名稱，輸入及輸出的形式，輸出直方圖的最大值及最小值。(2) 模擬的輸出輸入?yún)?shù)后進(jìn)行模擬。執(zhí)行規(guī)定次數(shù)的模擬后，可在每個(gè)終節(jié)點(diǎn)及指定的中間節(jié)點(diǎn)輸出有關(guān)時(shí)間、費(fèi)用與運(yùn)行效果的統(tǒng)計(jì)結(jié)果

53、，包括：相對(duì)頻率分布，累積頻率分布，平均值，標(biāo)準(zhǔn)離差，變差系數(shù)，眾數(shù)，中位數(shù)， 分布的兩峰態(tài)參數(shù)，皮爾遜偏度等。輸出的費(fèi)用值有兩類：一是線路費(fèi)用，即線路上活動(dòng)的累積成本；二是總成本，即節(jié)點(diǎn)前所有活動(dòng)累積費(fèi)用。根據(jù)輸出的最終節(jié)點(diǎn)的各項(xiàng)參數(shù)的直方圖，可確定項(xiàng)目風(fēng)險(xiǎn)大小。7. VERT應(yīng)用案例案例一 更換汽車輪胎問(wèn)題假設(shè)某人駕駛一輛借用的小汽車。途中發(fā)現(xiàn)有一輪胎撒了氣。這時(shí)他便需考慮能否及時(shí)到達(dá)目的地，并需估計(jì)其可能性和風(fēng)險(xiǎn)度如何。假定此人不能保證車中存有千斤頂和備用輪胎，他也不能肯定備用輪胎是否具有充足的氣壓。有了千斤頂與完好的備胎，才能進(jìn)行更換輪胎工作。其工序?yàn)椋喝〕銎骶?千斤頂和備胎)；頂起汽

54、車，更換輪胎，放下汽車，裝好器具(舊胎與千斤頂)。但是，存在著沒(méi)有千斤頂，沒(méi)有備胎以及有了備胎而氣壓不足的可能性，并且各工序的必要操作時(shí)間也互不相同。起始節(jié)點(diǎn)：全輸出邏輯表示從該節(jié)點(diǎn)引出的每一箭線都要進(jìn)行處理。蒙特卡洛輸出邏輯：表示網(wǎng)絡(luò)流將依概率分別隨機(jī)地送至各引出箭線。與輸入邏輯：要求N2和N3都成功完成。然后繼續(xù)傳至節(jié)點(diǎn)N9 (FINISH) ?；蜉斎脒壿嫞喝N不利情況無(wú)論發(fā)生哪一種都會(huì)觸發(fā)此事件。更換汽車輪胎問(wèn)題的VERT網(wǎng)絡(luò)圖在進(jìn)行模擬時(shí)，節(jié)點(diǎn)N3的蒙特卡洛輸出邏輯即依概率隨機(jī)地輸出三種可能的箭線之一。如，節(jié)點(diǎn)N3同備胎的情況有關(guān)，其概率分別如下： 備胎完好的概率：0.75 無(wú)備胎的概率：0.05 備胎撒了氣的概率：0.20同理，對(duì)節(jié)點(diǎn)N2亦然。如： 無(wú)千斤頂?shù)母怕蕿?.15， 千斤頂完好的概率為0.85經(jīng)多次模擬后，即可分別取成功結(jié)果與失敗結(jié)果的百分?jǐn)?shù)作對(duì)比進(jìn)行風(fēng)險(xiǎn)分析，從而確定能及時(shí)到達(dá)目的地的可能性和存在的風(fēng)險(xiǎn)度。案例二、研制新型汽車問(wèn)題某公司為了競(jìng)爭(zhēng)必須在短期內(nèi)迅速投產(chǎn)一種新型汽車。為此，要求在20個(gè)月內(nèi)完成新產(chǎn)品的設(shè)計(jì)與測(cè)試。同時(shí)限定預(yù)算費(fèi)用不超過(guò)三千萬(wàn)美元。系統(tǒng)測(cè)試項(xiàng)目的理想值與合格標(biāo)準(zhǔn)值規(guī)定如表所示。系統(tǒng)測(cè)試時(shí)上述任一性能項(xiàng)目不合格即為失敗。新產(chǎn)品的設(shè)計(jì)與測(cè)試