随机网络计划技术课件

1、随机网络计划技术 合肥工业大学管理学院二00八年三月内容安排一、概述二、决策关键线路法(DCPM)三、图示评审技术(GERT)四、风险评审技术(VERT)一、概述1. CPM和PERT存在的局限性应用假设所有活动均为独立；关键线路比其它路线长；关键路线具有足够多的活动，从而可以引用中心极限定理，工期视为正态分布；每项活动的周期服从 分布，其平均值近似用(a+4m+b)/6 来确定，方差为 (b-a)2/36。以上假设有其合理的地方，但也存在局限性：限定在肯定型（逻辑关系）范围内；不允许存在任何强连通成分(回路、反馈)；活动周期限定为 分布。一、概述 1. CPM和PERT存在的局限性现在的项目

2、、试制工程和生产服务过程中特点：随机因素不可忽视；工序间存在多次反馈；工程设计、生产过程在一定阶段上存在方案选择；服务过程和顾客到达的过程之间存在随机耦合。CPM和PERT很难适应现实的应用需求，在此背景下随机网络技术应运而生。2. 随机网络技术的产生与发展背景简介：1962，E.Eisner提出了带“决策盒”的广义网络技术(GAN)具有概率分支网络的初步形式；此后，经S.E.Elmaghroby和A.A.B.Pritsker等人逐步改进和完善，形成GERT型网络技术；与此同时，利用概率论中的矩母函数和控制论中的信号流图理论，发展了GERT网络的解析算法并于1969年形成了适应解析算法的软件系

3、统GERT-E；一、概述一、概述 2. 随机网络技术的产生与发展70年代，随着仿真技术的发展， A.A.B.Pritsker等人发展了随机网络仿真技术，形成GERTS仿真系统及其相应的仿真软件。随后，具有成本优化的GERTS -Z，具有资源分配功能的GERTSIII-R，具有初步的排队功能的GERTSIII-Q等相继产生;1977-1979，又将GERTS的主要功能与GPSS通用仿真系统中的实体流技术结合，形成具有综合功能的Q- GERT网络技术及其软件系统。同时, Pritsker等人又将离散与连续仿真系统GASP-与Q- GERT结合，形成既能处理离散系统和网络系统仿真，又能处理连续系统仿

4、真的“多种建模仿真语言”SLAM。在70年代初期，美国人在GERT网络技术的基础上发展了网络数学分析器MATHNET（Mathematical Network Analyzer）,它可以把离散事件活动、活动时间和费用综合起来构成一个概率特征进行计算和分析。随后又开发了网络统计分析器STATNET（Statistical Network Analyzer）和网络求解分析器（Solving Network Analyzer）等网络技术。与此同时还对MATHNET进行了修改，重新命名为风险信息系统费用分析RISCA（Risk Information System Cost Analysis）。一、概

5、述 2. 随机网络技术的产生与发展一、概述 2. 随机网络技术的产生与发展同时也开发了全面风险评估和费用分析网络TRACENET（Total Risk Accessing Cost Analysis），从而进入了风险评估领域。然而这些系统尚不能评定与性能有关的风险度，特别是研究和开发中技术性能指标能否达到规定的风险度。1972年，由Gerald L.Moeller等研究开发VERT技术，才使风险度估计成为可能。此后，经过改进和扩充，形成现在的VERT，为实际应用打下了基础。1979年，完成VERT-2；1981年，又完成VERT-3， VERT-3网络模型主要特点在于面向决策，统筹处理时间、费

6、用、性能与风险等关键性参数，能有效地解决多目标最优化问题。此外，还有决策关键线路法DCPM、循环网络技术CYCLONE都是在CPM、PERT以及GERT的基础上，在应用需求的推动下形成的网络计划技术。一、概述 2. 随机网络技术的产生与发展一、概述 2. 随机网络技术的产生与发展实际应用情况：1969年，GERT-E成功地应用于“阿波罗”计划，随后相继在科研计划管理、可靠性分析、机械制造生产线的设计与分析、质量控制、自动化仓库管理、排队问题等方面得到了广泛的应用。此外，在交通运输、人口动态分析、计算机系统、商务合同的签订等方面也得到的较好的应用；80年代初，美国国家航空和宇宙航行局(NASA)

7、 又将Q-GERT和SLAM成功的应用于航天飞机发射及回收过程的网络计划中。随机网络技术发展过程示意图一、概述3. 随机网络技术的主要特点：在网络中引入项目(活动)的可能选择方案与决策，如DCPM；考虑多种随机因素的影响，例如：科研、设计与试验的多次反馈、方案选择、服务过程的随机耦合等。不仅在活动历时方面可取任何概率分布，而且在逻辑上可存在自环与回路，如GERT；应用网络仿真技术形成了网络仿真系统，如GERTS；增强了网络节点的功能，综合仿真、排队、优化、统计信息、随机循环作业以及风险分析等多种功能，如：Q-GERT，CYCLONE，VERT等。一、概述1. CPM和PERT存在的局限性2.

8、随机网络技术的产生与发展3. 随机网络技术的主要特点随机网络计划技术一、概述二、决策关键线路法(DCPM)三、图示评审技术(GERT)四、风险评审技术(VERT)二、决策关键线路法DCPM 1. 概述随着科学的发展，建筑施工规模的扩大，人们发现CPM、PERT网络方法在一些工程的应用中受到了限制。例如，在一个工程中，如果有一些工序可以采用不同的施工方案施工，则整个工程就有许多不同施工方案，只有在具有不同施工方案的工序上作出正确决策，才能确定出整体最优施工方案。显然用CPM或PERT方法来解决这样的问题，就变得非常困难。再有，建筑工程施工往往存在经济奖罚问题，即工程提前完工给予奖励，拖后完工给予

9、惩罚，要将这一问题与多方案一起考虑，用CPM和PERT就更加困难。二、决策关键线路法DCPM 1. 概述为了解决上述问题，在CPM和PERT的基础上产生一种新的网络方法，即决策关键线路法(DCPM)。对于具有不同施工方案的工序，各方案所需的施工时间和费用必然不同，所需时间越长，费用越低，DCPM将其作为决策工序，画在同一张网络图上，一张DCPM网络图可包含多个决策工序，因此包含了该工程的所有的可行施工方案。对于经济奖罚问题，DCPM将时间价值，即工程提前完工的奖金和拖后完工的罚金，作为总成本的一部分，以总成本最低为目标求解。二、决策关键线路法DCPM 1. 概述在求解过程中，DCPM始终以总成

10、本最低为目标，在各决策工序上进行决策，从中选出最合理的选择，最后确定出使总成本最低的整体最优施工方案。DCPM具有明显的优点:它不是仅仅考虑单一方案，而是把完成工程的所有方案都加以考虑；考虑了工程工期和工程费用；考虑了工程提前完工带来的收益和拖后完工造成的损失。二、决策关键线路法DCPM 1. 概述DCPM目标：不是工期，而是把时间反映到经济效果上，以获得的经济效果最好的为目标，通过经济效果的比较来确定最优施工方案。二、决策关键线路法DCPM 2. DCPM网络图绘制假设在一项工程中有n个工序，以集合的形式表示： J = S1,S2, ,Sn (1)其中有的工序只有一种可行的施工方案，即: S

11、i = Si,1 (2) 这样的工序称为非决策工序，如图表示：IJ时间(费用)二、决策关键线路法DCPM 2. DCPM网络图绘制而有些工序具有若干个可行施工方案供选择， Si = Si,1,Si,2, ,Si,k (3) 这样的工序称为决策工序，如图的形式表示:II,1I,2I,KJ.方案1方案2方案K时间(费用)时间(费用)时间(费用)决策节点逻辑联系决策工序的各个选择之间存在互斥关系，即只要一个选择完成就表示该决策工序完成，也可以说对一个决策工序只能采用k个方案中的一个，且仅仅一个方案。用决策变量表示：(4)其中：1 第 j 个方案采用0 第 j 个方案未采用二、决策关键线路法DCPM

12、2. DCPM网络图绘制二、决策关键线路法DCPM 2. DCPM网络图绘制根据上面的定义，依照工序之间的逻辑关系，将非决策工序和决策工序用普通网络节点(用圆圈表示)和决策点(用正方形表示)联接起来，就形成双代号DCPM网络图。在双代号DCPM网络图中，一个决策点只能表示一个，决策工序的开始，不能有两个或多个工序的始点为同一决策点，但可以有两个或多个工序的终点为同一决策点。除存在决策工序外，双代号DCPM网络图与双代号CPM及PERT网络图的形式完全相同。二、决策关键线路法DCPM 2. DCPM网络图绘制双代号DCPM网络图二、决策关键线路法DCPM 3. 费用计算在用决策关键线路法确定总体

13、最优施工方案时，需要计算工程总费用P，其计算公式： P = P0 + P1 + P2 式中： P0 非决策工序的费用和； P1 决策工序的费用和； P2 时间价值，即工程提前完工的 奖金或拖后完工的罚金； 其中： 式中：Cij 非决策工序(i , j)的费用。二、决策关键线路法DCPM 3. 费用计算式中： cij 以决策点 i 为始点的决策工序的第 j 个选 择方案的费用； dij 以决策点 i 为始点的决策工序的第 j 个选 择方案的决策变量； H 决策点个数； K 决策点具有的选择个数(方案个数)。二、决策关键线路法DCPM 3. 费用计算式中： P21 工程拖后完工的罚金； P22 工

14、程捉前完工的奖金； T 计算工期； D 工程的规定工期。 P21 = ( T - D ) F P22 = ( T - D ) R式中：F 时间费用系数，即工程拖后单位时间的罚金； R 时间费用系数，即工程提前单位时间的奖金。P2 =P21 T D P22 T D 二、决策关键线路法DCPM 4. DCPM问题的求解方法 DCPM问题的求解方法有三种:整数规划法动态规划法试探法二、决策关键线路法DCPM1. 概述2. DCPM网络图绘制3. 费用计算4. DCPM问题的求解方法随机网络计划技术一、概述二、决策关键线路法(DCPM)三、图示评审技术(GERT)四、风险评审技术(VERT)三、图示评

15、审技术(GERT) 1. GERT概述GERT是一种随机网络技术，又称决策网络技术。 它使用带概率的有向网络图进行分析,可以用来分析复杂多变的项目计划与控制问题；在GERT中，可以包含具有不同逻辑特征的节点，节点允许有概率分支，网络中允许回路和自环存在，每项活动的周期均可选取任何种类的概率分布等。即对网络逻辑关系和历时估算作概率处理；GERT使得项目中可能存在的许多事先难以肯定随机因素在网络图中得以反映并计算处理。三、图示评审技术(GERT) 1. GERT概述与CPM、PERT相比，GERT的优越性体现在：节点和枝线不一定都实现，实现的可能性取决于节点的类型和枝线的概率系数；活动时间为概率型

16、，按随机变量分析；活动的流向不受限制，允许环路的出现；节点间可以有一条以上的枝线；可能多个起点或终点，即允许多个目标的存在。三、图示评审技术(GERT) 1. GERT概述应用情况：1966年，A.Pritsker在研究阿波罗空间系统的最终发射时间的过程中，提出了GERT，之后在应用中又进一步发展，综合运用网络理论、概率论、信流图理论及模拟技术，使这种方法得到进一步完善。在此基础上， GERT逐步应用在研究开发规划、存贮分析飞油井钻探、工业合同谈判、费用分析、人口动态、维修和可靠性研究、车辆运输网络、事故的防范及计算机算法等方面。2. 广义活动网络GAN对于一个客观系统的动态行动过程，可以看作

17、是系统状态之间的转移过程，即随着时间的推移，系统从一种状态转移到另一种状态。随机网络中的节点可以表示网络的状态，而连接各节点之间的箭头可以理解为状态之间的传递关系。当状态之间的转移具有概率性质，而且状态之间的传递关系也服从一定的概率分布时，网络的运行过程就具有随机性质。三、图示评审技术(GERT)三、图示评审技术(GERT) 2. 广义活动网络GAN当系统从一种状态转移到另一种或多种状态时，可以取不同的概率。对网络系统来说，可以理解为从某一节点转移到其它可能节点时具有不同的概率，即节点的引出箭头允许有概率分支，这个特征使网络带有随机性。在随机网络中，假设这种状态转移概率不随时间而变化，从而保证

18、系统的稳定性。然而，在随机网络中并不排除一部分节点之间存在肯定性的转移关系，即转移概率取1的转移关系。三、图示评审技术(GERT) 2. 广义活动网络GAN在状态转移中所有的传递关系将表现为某些参数的变化，或某些资源的占用，在随机网络中，这些传递参数通常都服从一定的概率分布，即同样两个节点之间在两次转移中，其传递参数将按一定的概率分布取不同的数值，这是随机网络的又一特征。以上所述概率分支和传递参数的分布，构成GAN网络中的一般要素。这些要素可标在网络中表示活动的箭杆上，通常用一个二维或二维以上的向量来加以描述。三、图示评审技术(GERT) 2. 广义活动网络GAN12u = (pu , tu

19、, cu)GAN网络的一般要素，如图示：pu 当节点1实现时，活动(1，2)将要实现的概率；tu 表示活动(1，2)所需要的时间，它是服从一定 概率分布的随机变量；cu 表示该活动的费用函数，也可能是一个随机变量。在随机网络中，每一节点至少必须有一个引入箭杆和一个引出箭杆 (源节点和终节点除外)，同时允许有多个源节点和多个终节点。 三、图示评审技术(GERT) 2. 广义活动网络GAN在GAN网络中可定义三种“输入”类型和两种“输出”类型的逻辑，共可构成六种不同逻辑功能的节点：“异或”型输入凡引入此节点的活动，只要有任何一个活动完成，该节点即实现，然而，在一个给定时刻上只有一个活动能够完成。“

20、或”型输入凡引入此节点的活动，只要有任何一个(或一组)活动完成，该节点即实现，即在给定时刻上允许有同时完成的活动进入节点，因此，节点将在所有引入活动中的最早时刻上实现。“与”型输入当所有引入此节点的活动都完成时，该节点才能实现。即此节点将在所有引入活动中的最迟完成时刻上实现。三、图示评审技术(GERT) 2. 广义活动网络GAN概率型输出当此节点实现时，所有从该节点引出的活动中只有一个活动按一定的概率得以实现。各引出活动实现概率之和必为1。肯定型输出由此节点引出的活动迟早都要被完成，即所有引出活动被执行的概率均为1， PERTCPM型节点具有此种输出特征。 三、图示评审技术(GERT) 2.

21、广义活动网络GAN案例1 新产品研制成功的概率与时间问题 研制某一新产品的过程为：研制，试验，经试验后研制或成功(鉴定)，或失败(废品处理)，或局部修改图纸。这三个事件的发生都具有一定的概率，设它们的概率分别为0.6、0.1、0.3。若研制成功或失败，则研制工作结束，若需局部修改图纸，则需进一步研制，之后再经过试验。若给出研制过程各个工序的作业时间(常数，或服从某种概率分布的均值)，要求研制过程所需的时间及研制成功的概率。三、图示评审技术(GERT) 2. 广义活动网络GAN2. GAN 案例1 新产品研制成功的概率与时间问题如果用CPM/PERT网络图表示上述的新产品研制的过程，且暂不考虑各

22、工序的作业时间，其形式如图示网络图特点：1. 存在回路；2. 存在随机事件；3. 存在两个终点，并分别具有一定 的概率。每条弧上赋予两个参数： 1) 给定的结点实现时，该弧实现的概率为p； 2) 弧上表示的工序的作业时间为t，它是个随机变量或者是一个常数。如果是随机变量，应给出概率分布的密度函数、均值和方差。在随机网络中的，用期望值(均值) 表示。GAN网络图三、图示评审技术(GERT) 2. 广义活动网络GAN构造GAN网络模型的目的：将一个客观系统用网络形式表示出来，以便给人以概括的了解;研究系统中各项要素之间的相互关系，从而使原始网络得以简化，以便得到系统的各种特性。在三种输入逻辑中，只

23、有“异或”型节点最易于用数学方法进行处理，其它两种节点逻辑，至今尚未找到适当的解析方法。在处理这类节点时，可以通过适当的逻辑变换；将“或”型和“与”型节点转换为“异或” 型节点。三、图示评审技术(GERT) 2. 广义活动网络GANGAN网络的形式很多，然而从网络结构的特点来看，可以归纳成串联型、并联型及自环型三种基本结构。其中并联结构又可按节点输入端的特点分为并联“与”，并联“或”及并联“异或”等三种结构。3. GAN网络的结构形式(1) 串联箭杆情况13Pe=PaPb te = ta + tb等效为132aba=(Pa, ta)b=(Pb, tb)三、图示评审技术(GERT) (2) 并联

24、箭杆情况“与”关系Pe= =PaPb te= maxta, tbab3221三、图示评审技术(GERT) 3. GAN网络的结构形式 “或”关系Pe= Pa+b =(2) 并联箭杆情况(续)ab2213Pe= te= minta, tb(2) 并联箭杆情况(续)“异或”关系Pe= -“异或”关系的两种情况：只有a实现： te= ta, Pe= Pa - 只有b实现： te= tb, Pe= Pb -ab2213(3) 自环形情况2ae13等效为c2ab13(Pb + Pc = 1)环路重复次数n持续时间te概率Pe0tbPb1tb + tcPbPc2tb + 2tcPbPc23tb + 3tc

25、PbPc3ntb + n tcPbPcn表1 持续时间te及发生的概率Pe4. GERT求解的一般程序系统分析，明确问题求解的要求 首先要对系统的约束条件、所要求的问题与预期的目标、系统的构成与工序的划分，以及各工序之间的相互关系进行周密的分析。 绘制随机网络图 根据系统分析的结果，特别是工序的合理划分，各工序之间的相互关系，正确地选择输入侧与输出侧结点的符号，绘制随机网络图。参数的确定与估计 在绘制随机网络图的同时，就要考虑每条弧出现的概率及作业时间。如果作业时间是随机变量，还要测辨它们的概率分布与密度函数，以及期望值和方差，确保随机网络必要的精度。4. GERT求解的一般程序 (续)随机网

26、络的计算或模拟 通常是在计算机上进行计算或模拟。根据系统目标的要求，对时间、资源和费用进行计算和优化。综合评价与审定 对计算的结果(常数或随机变量)进行分析和评价。在确认得到令人满意的计划方案之后，做出决策，指导监督并控制计划的执行。5. GERT求解的基本方法GERT求解的基本方法可以分为两大类：解析法：用随机网络中给定的参数，把概率和随机问题化为确定性问题求解。或者采用信流图理论，用等效函数法求解。模拟法：在计算机上进行模拟试验，由于这种方法能够方便而迅速的处理概率和随机问题，所以被广泛地应用。GERT求解的基本方法解析法案例一：混凝土现场供应方案的评审合徐高速公路某段，拟建砼拌合场，方案

27、选择时考虑诸多影响因素有：临时场地、道路征地、建场安装、材料运输方式等。现需对砼供应是集中还是分散的各种方案进行评审。确定方案的限定指标为：建成砼拌和场的工期不超过55天，费用成本不超过105万元。根据网络图进行计算，结果见下表：0.08可能费用(万元)分析评审当采用集中拌和方案时: 概率P = 0.378 平均时间 t = (8.376+6.825+6.09)/0.378 = 57.3(天) 平均费用 C = (16.968+9.66+11.865)/0.378 = 101.83(万元)当采用分散拌和方案时: P = 0.08 t = 47 (天) C = 112 (万元)评审结果 根据方案

28、确定的限定指标，采用概率大(P=0.378)的集中拌和方案，然后比较选定1公路运输的具体方案，理由是： T = 52 55 C = 101 105案例二：成批生产，每个成品的生产时间与成品率问题。生产一批零件，经加工1工序4小时完成后送检查1工序.检查1工序的作业时间，通过统计资料分析，服从指数分布，平均时间1小时，方差也是1小时检查1工序完成后，有75%的零件合格，并转到加工2工序；25 %的零件不合格转到返修工序返修工序完成后转到检查2工序。检查2工序完成后，有70%零件返修合格转到加工2工序，30 %零件返修后仍不合格而报废，加工2工序的作业时间，有60 %的零件可能要用10小时，40

29、%的零件可能要用14小时.加工2工序完成后转到检查3工序.检查3工序完成后，不论是由检查1转到加工2的，还是由检查2转到加工2的，均有95 %零件合格入库，5 %零件不合格报废.上述各道工序完成的概率,作业时间及各工序的相互关系如表所示。GERT求解的基本方法解析法试计算成批生产这种零件，每个成品平均需要的时间和成品率。根据已知资料和随机网络的形式，上述问题的随机网络如图所示。通过分析，零件加工为成品的生产过程可能经过以下四条路线，其中作业时间为指数分布的按均值计算：第一条路线：12568(1,4)(0.75,1)(0.6,10)(0.95,1)路线实现的概率：p1 = 10.75 0.6 0

30、.95 = 0.4275所需要的时间： t1 = 4 + 1 + 10 + 1 = 16(0.25成品废品(0.25成品废品第二条线路：12568(1,4)(0.75,1)(0.4,14)(0.95,1)路线实现的概率：p2 = 10.75 0.4 0.95 = 0.285所需要的时间： t2 = 4 + 1 + 14 + 1 = 20第三条线路：路线实现的概率：p3 = 10.25 1 0.7 0.6 0.95 = 0.09975所需要的时间： 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)路线实现的概率：p4 = 10.25 1 0.7 0.4 0.95 = 0.0665所需要的时间： t4 = 4 + 1 + 3 + 2 + 14 + 1 = 25由上述四条路线可得出零件加工的成品率和每个零件需要的平均时间分别为：可以得出零件的废品率为： Pf = 1 - PC = 0.12125(0.25成品废品GERT求解的基本方法计算机模拟在上述的案例中，除四条成品加工路线之外，还有五条废品加工路线。即：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)九每个零件经过的加工路线是由始点事项开始，每个工序以概率 Pi 转移到紧后工序(直到终点事项或)。若各工序转移到紧后工序的概率 Pi 服从(0 Pi 1)均匀分布，每个零件经过的加工路线可以在计算机上经随机数来模拟。根据可能出现的两

33、个 (或若干个) 紧后工序的概率值将0到1的数轴分成两个 (或若干个) 区间，产生的随机数落在哪个区间，就认为那个区间对应的工序被实现。GERT求解的基本方法计算机模拟例如，工序 的紧后工序为 与 ，它们的概率分别是0.7与0.3，如下图：若产生的随机数R0.6523出现在区间I内，则表示工序 实现；若随机数R0.9673出现在区间工II则表示工序 实现。不同的加工路线，各工序所需要的时间是服从某种分布密度函数的随机变量。将服从(0,1)均匀分布的随机数，通过公式逆变或者逐段逼近的方法，可以产生所需分布密度函数的随机数。每个零件的加工路线与所需要的时间是随机网络的子网络。在计算机上每模拟一次，

34、就得出一个子网。这个子网络各个工序实现的概率都是1，每个工序所需要的时间是个确定的量。则该子网络所需要的时间也是个确定的量。因此，通过对某一零件的加工路线与所需时间的模拟，即可得出一个确定的子网络(加工路线及所需时间)，并记忆该路线所经过的工序。例如，模拟中可能出现以下的结果(仅举几例)： 第一次模拟(第一个零件加工过程) 成品112568(1,4)(1,0.9)(1,14)(1,1)t11=4+0.9+14+1=19.9第二次模拟(第二个零件加工过程) 废品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、 出现的结点：1,2,3,4,5,6,7第三次模拟(第三个零件加工过程) 废品212347(1,4)(1,1.2)(1,3)(1,1.9)t22=4+1.2+3+1.9=10.1 出现的结点：1,2,3,4,7继续模拟下去，到 N 次。每次模拟所得到的加工路线，不外乎是前述的九条路线中的一条究竟是哪一条，将由工序-、-、-、-、-、-、-等八个工序出现的概率(随机数出现在(0，1)数轴的哪一个区间)的组合而定。各条加工路线所需要的时间，取决于-、-、-、-、-等六个工序的作业时间(均为常数)和-、-、-、-等四个工序的分布密度函数、均值、方差所出现的随机数。第N次模拟 (加工批量为N的一批零件

36、)后，得出需要总的时间 T 和成品零件个数 K ，二者之比即是每个成品零件所占用的平均时间。式中：ti 第 i 个成品零件的加工时间； tj 第 j 个废品零件的加工时间。一批零件的成品率 Pc 等于成品零件个数与这批零件个数的百分比，即:%输入数据一般为各工序，箭尾结点与箭头结点的编号，各工序出现的概率与作业时间(随机变量可取其均值)，以及由箭尾结点引出的分枝数。输出结果一般为成品的概率，成品零件占用的平均时间及废品零件占用的平均时间等。程序框图如图所示：三、图示评审技术(GERT)1. GERT概述2. 广义活动网络GAN3. GAN网络的结构形式4. GERT求解的一般程序5. GERT

37、求解的基本方法（1）解析法（2）模拟法随机网络计划技术一、概述二、决策关键线路法(DCPM)三、图示评审技术(GERT)四、风险评审技术(VERT)四、风险评审技术(VERT) 1. 概述VERT(Venture Evaluation and Review Technique)是在CPM和PERT的基础上，经过GERT和计算机程序模拟技术逐步加以扩充、改进，于1972年研制出的一种风险评审网络分析方法。1979年即完成VERT-2。1981年又完成了VERT-3。 VERT-3在国外已受到普遍重视，被认为是唯一能充分而同等地衡量处理多个关键性参数及其相互作用的网络技术。VERT-3网络模型的主

38、要特点在于面向决策，统筹处理时间、费用、性能与风险等关键性参数，有效地解决多目标最优化问题。因此具有较大的实用价值。2. VERT的由来与演变1958年美国海军特种计划局在研制北极星导弹的过程中首次应用了计划评审技术，提高了工作效率，缩短了计划工期，使原计划提前两年完成。差不多与此同时，美国杜邦(Dupont)公司独立研制了关键路线法，用于施工设计和维修计划，取得了显著效果。但是PERT与CPM都是肯定性网络模型，其中每项活动都必须成功完成，而现实中存在着风险和不确定性。因而在实施过程中可能出现种种偶然事件。例如，进行某项测试工作可能完全成功，也可能部分成功，甚至可能失败。当未来局势呈现“模糊

39、”或不肯定时，PERT与CPM便不能适应这种随机局势。2. VERT的由来与演变(续)随着PERT与CPM应用范围的扩大，于是产生了如何加强网络分析的效能问题。例如：怎样改善资源分配，力求缩短工期，降低成本，减少风险，实现最优化目标；怎样减少关键性活动的性能而不致过多地损失经济效益；怎样降低非关键性活动的费用或风险而不增加计划总工期；怎样改进网络技术，控制时间、费用与性能参数的最佳组合等等。2. VERT的由来与演变(续)1966年普利茨克尔(Pritsker)等提出的图示评审技术是扩展网络模型增进随机适应性的重大突破之一。但是，GERT把费用看成是从属于时间的变量，未能对预算费用进行必要的控

40、制并确定其对进度的影响。20世纪60年代末和70年代初期，美国国防经济部门的许多重要项目出现了巨额费用超支和进度时间超限，终于使有关当局认清了风险分析的必要性。于是提出运用网络模拟技术解决风险决策问题。2. VERT的由来与演变(续)1970年美国陆军研制出名为MATHNET的计算机程序模拟技术。其后，又陆续产生了若干改进的计算机程序网络技术。例如；风险信息系统费用分析(Risk lnformation System Cost Analysis)简称RISCA，以及网络统计分析器STATNET(Statistical Network Analyzer)与网络求解分析器SOVNET (Solvi

41、ng Network Analyzer)，全面风险评估和费用分析网络TRACENET（Total Risk Accessing Cost Analysis）等。2. VERT的由来与演变(续)1972年莫埃勒尔(MoellerG.L.)在MATHNET与STATNET的基础上研制出风险评审技术VERT。此法在网络的节点逻辑与数学关系式的处理上有较大的适应性，能统筹考虑“时间、费用、性能”并给予同等重要性和处理层次。1979年依据VERT和TRACENET计算机程序网络技术完成了VERT-2，在此基础上，莫埃勒尔和迪格曼(Digman L.A.)又于1981年研制成一种全新的计算机，模拟决策网络

42、技术 VERT-3。2. VERT的由来与演变(续)VERT-3不仅能分析完成计划的程度，显示各项成果的范围、性能与费用水平，同时，还能突出显示关键最优路线，提供成功的可能性和失败的风险度。因而在处理风险决策问题上有较大的价值。3. VERT的基本概念风险评审技术把网络系统中活动及节点(事件)实际情况与相应所需的时间、费用、运行效果联系起来，并用数学关系描述，应用计算机大量模拟结果作为依据，进行综合分析评估，从而增强了描述和分析现实世界的能力。构成VERT网络的基本元素是节点和箭线(弧)。用长方形符号表示节点，它代表事件或决策点；用箭线(弧)表示活动或工作。描述活动的基本参数有：占用的时间T，

43、所担负的费用C，以及完成活动所产生的效能P(生产水平，投资效益等)。3. VERT的基本概念两类节点：分离逻辑节点与单元逻辑节点。前者是最常用的节点，它具有分离的输入逻辑与输出逻辑。后者具有单元逻辑，同时包括输入与输出两种作用，这类节点应用较少。节点起约束或控制网络流进入弧的作用，而弧则可携带网络流从输出节点到输入节点，通过网络流表示活动和节点的实际完成情况。分离节点的输入逻辑共有下列四种：起始输入逻辑：用于网络流的起始输入节点。与输入逻辑：要求在合成输入流送至输出逻辑进行适当分配前所有输入箭线都必须成功完成。部分与输入逻辑：除要求流过该节点前至少有一支输入箭线成功完成外，部分与输入逻辑跟与输

44、入逻辑基本相似。不过，前者在处理之前将等待所有输入箭线都进入网络或从网络中消失。或输入逻辑：和部分与输入逻辑十分相似。也要求流过该节点前至少有一支输入箭线成功完成，但在处理前不需等待所有输入箭线都进入或从网络消失。3. VERT的基本概念分离节点的输出逻辑有以下六种：终端(TERMINAL)输出逻辑：网络终端节点，亦即网络流的收点。全(ALL)输出逻辑：同时启动由该节点引出的全部输出箭线。蒙特卡洛(MONTE CARLO)输出逻辑：应用蒙特卡洛方法，每次模拟迭代仅处理一支输出箭线。分离节点的输出逻辑有以下六种(续)：滤子1(FILTERl)输出逻辑：根据节点输出箭线上所加的约束条件(时间与或费

45、用与或性能值的上、下限)为联合满足或单独满足进行分别处理。若满足约束条件，则该箭线将予以处理。滤子2(FILTER2)输出逻辑：跟滤子1的的区别在于，输出箭线只承担一个约束条件并只能同部分与输入逻辑共用。滤子3(FILTER 3)输出逻辑 约束条件不是界限值而是原先处理过的其他箭线的名称(指定前导活动的成功或失败作为触发条件)。单元逻辑节点的四种形式“比较”节点(Compare)：传递全部流至输出箭线；“偏好”节点(Preferred)：把经过的流传递给受偏好 的输出箭线；“排队”节点(Queue)：模拟排队功能，将经过的流按一定的规则进行排队处理；“分类”节点(Sort)：对节点后的输出箭线

46、依次编号，将通过的流依编号先后传递给个箭线。VERT的计算机模拟就是创设网络流从起始节点通过网络流向终端节点，产生模拟问题的试验解。为了能取得足够的子样数，此模拟过程可按用户要求重复进行多次。节点的完成时间、费用与性能信息利用下列统计值求得：相对分布频率，累积分布频率，观测的平均值，中误差(子样的标准差)，中误差系数(中误差平均值)，众数，中位数，峰度与偏度。这类信息可对所有节点予以显示。还可按用户要求的时限(逐年或按月份) 输出所担负的网络总费用与性能值。3. VERT的基本概念3. VERT的基本概念VERT网络一般有一个或若干终端节点, 用于收集完成计划的成功次数，并有一个或若干终端节点

47、,用于收集未完成计划的失败次数。这些不同终端节点成功或失败次数分别同迭代总数的相比即表明计划成功或失败的可能性（或风险度）。4. VERT的建模步骤VERT 采用网络结构来描述研究对象, 使问题系统化、 逻辑化和具体化。具体步骤如下: (1) 确定所分析对象的情况并指出分析目标； (2) 按所确定的情况绘制初步网络图, 使分析的问题具体化 (3) 收集与决策过程有关的各种活动的数据, 如概率分布、 数学关系表达式等； (4) 构成能用于仿真运算的逻辑网络图, 进行仿真运算； (5) 获得仿真结果。5.蒙特卡洛随机模拟方法(1) 蒙特卡洛随机模拟从经济上讲，当不能建立精确的数学模型或模拟太复杂问

48、题而不能作及时评价时，可用此法作可靠性预测。蒙特卡洛随机模拟是一种通过随机变量统计试验，随机模拟解决工程问题的数值方法。其基本假定是风险因素相互独立，随机发生，在此前提下，进行统计试验，从而得出目标函数的概率分布及其统计特征值。模拟过程主要是通过计算机产生随机数，并将此随机数作为累计概率分布与随机变量概率分布相对照，从而得到变量的试验数据，进行足够多的试验，甚至上万次的试验，使之符合大数定律的要求，便可得到变量的分布。然后求得期望值和方差。5.蒙特卡洛随机模拟方法(1) 蒙特卡洛随机模拟蒙特卡洛法的基本思路是运用一连串随机数来表示一项事件的概率分配。然后利用任意取得的随机数从该项概率分配中获得

49、随机变量值。该方法的缺点是没有计入风险因素之间的相互影响，使得风险估计结果可能偏小。(2) 举例：某商店为了估算每天的平均营业额，对商店每天接待的顾客数和每位顾客的购物金额作了100天的统计。每天接待顾客人数30-3940-4950-5960-6970-79以上发生天数52540282每位顾客购货金额（元）10-1920-2930-3940-4950-59以上发生次数403015105表1. 每天接待的顾客数统计表表2. 每位顾客购货金额统计表5.蒙特卡洛随机模拟方法根据表1和表2，可以列出相应的概率分布：每天接待顾客人次概率30-3940-4950-5960-6970-79以上0.050.2

50、50.400.280.02每位顾客购货金额（元）概率10-1920-2930-3940-4950-59以上0.400.300.150.100.05表3. 每天接待顾客人次概率分布表表4. 每位顾客购货金额概率分布表以随机数01，02，98，99，00来表示上述概率分布，如表所示：每天接待顾客人次概率随机数取值30-3940-4950-5960-6970-79以上0.050.250.400.280.0201-0506-3031-7071-9899-00每位顾客购货金额概率随机数取值10-1920-2930-3940-4950-59以上0.400.300.150.100.0501-4041-707

51、1-8586-9596-00任意取随机数，如取随机数为10，由表可知，这天来商店的顾客在40-49人次之间，可取平均数为45天，又仍取随机数为39，则知每位顾客购货金额在10-19元之间，取平均数15元。设仿真延续时间定为30天，则分别任意取随机数30次，再求得每天接待顾客平均人次乘以每位顾客购货金额，再除以30可得每天的平均营业额。随机数的产生方法:随机数表(random number table)法随机数发生器利用数学方法产生随机数如：随机数生成法、倍积取中法、同余数法等。6. VERT模拟过程风险评审技术模型建立后，按规定格式输入计算机，进行大量的重复的计算机模拟，并按要求格式输出结果。

52、每次模拟就是由网络的始端激发流，然后模拟执行(即通过流)全过程。模拟的全过程如图所示。(1) 参数的输入 模拟前必须确定各项参数。通常有三类参数：控制参数、箭线(活动参数)及节点参数。控制参数是整个网络的参数，包括：数据的输入和输出方式，打印要求，计算的时间区段，确定随机变量的控制值以及模拟次数等。箭线参数包括：箭线编号及名称，前导及后继节点，发生概率，延续时间，费用，运行效果，参数获得方式。节点参数包括：节点编号及名称，输入及输出的形式，输出直方图的最大值及最小值。(2) 模拟的输出输入参数后进行模拟。执行规定次数的模拟后，可在每个终节点及指定的中间节点输出有关时间、费用与运行效果的统计结果

53、，包括：相对频率分布，累积频率分布，平均值，标准离差，变差系数，众数，中位数， 分布的两峰态参数，皮尔逊偏度等。输出的费用值有两类：一是线路费用，即线路上活动的累积成本；二是总成本，即节点前所有活动累积费用。根据输出的最终节点的各项参数的直方图，可确定项目风险大小。7. VERT应用案例案例一 更换汽车轮胎问题假设某人驾驶一辆借用的小汽车。途中发现有一轮胎撒了气。这时他便需考虑能否及时到达目的地，并需估计其可能性和风险度如何。假定此人不能保证车中存有千斤顶和备用轮胎，他也不能肯定备用轮胎是否具有充足的气压。有了千斤顶与完好的备胎，才能进行更换轮胎工作。其工序为：取出器具(千斤顶和备胎)；顶起汽

54、车，更换轮胎，放下汽车，装好器具(旧胎与千斤顶)。但是，存在着没有千斤顶，没有备胎以及有了备胎而气压不足的可能性，并且各工序的必要操作时间也互不相同。起始节点：全输出逻辑表示从该节点引出的每一箭线都要进行处理。蒙特卡洛输出逻辑：表示网络流将依概率分别随机地送至各引出箭线。与输入逻辑：要求N2和N3都成功完成。然后继续传至节点N9 (FINISH) 。或输入逻辑：三种不利情况无论发生哪一种都会触发此事件。更换汽车轮胎问题的VERT网络图在进行模拟时，节点N3的蒙特卡洛输出逻辑即依概率随机地输出三种可能的箭线之一。如，节点N3同备胎的情况有关，其概率分别如下： 备胎完好的概率：0.75 无备胎的概率：0.05 备胎撒了气的概率：0.20同理，对节点N2亦然。如： 无千斤顶的概率为0.15， 千斤顶完好的概率为0.85经多次模拟后，即可分别取成功结果与失败结果的百分数作对比进行风险分析，从而确定能及时到达目的地的可能性和存在的风险度。案例二、研制新型汽车问题某公司为了竞争必须在短期内迅速投产一种新型汽车。为此，要求在20个月内完成新产品的设计与测试。同时限定预算费用不超过三千万美元。系统测试项目的理想值与合格标准值规定如表所示。系统测试时上述任一性能项目不合格即为失败。新产品的设计与测试