图示评审技术GERT(ppt)课件.ppt

1、 随机网络，又称图示评审技术GERT，是指网络计划中活动与活动之间的逻辑关系逻辑关系具有不确定性，且活动的活动的费用费用和时间参数时间参数也不确定，而按随机变量进行分析的网络计划技术。在GERT网络中可以包含具有不同逻辑特征的节点，节点的引出端允许有多个概率分支，网络中允许回路和自环存在，每个活动的费用和时间参数可选取任何类型的概率分布等等。一句话，GERT随机网络完全立足于真实的项目进程，允许考虑项目的返工，考虑项目及各个进度路径的选择、废弃，以及考虑通过反复重复某一过程而带来的学习效应等，基本上不受方法本身先天局限的影响。随机网络的建模要素是活动（弧）和节点，其仿真过程可以想象成一定的时间

2、流、费用流和性能流通过各项活动，并受到节点逻辑的控制流向相应的活动中。每次仿真运行，就相当于这些流从源节点出发，经过相应的节点和活动，执行相应的事件，最后到达网络的终节点。由于网络中可以选用具有各种逻辑功能不同的节点，可能导致三种流只经过网络中的部分节点和弧，并到达某个终止节点。网络中活动和节点都有时间、费用和性能三种参数。每个活动上既可赋给弧本身所具有的三种参数，该项活动本身所需要的时间周期、消耗的费用及经过本活动所产生的性能参数。同时，每项活动上还具有累积的三种参数。根据活动在网络中的位置，从源节点开始，时间流、费用流和性能流经过一定的路径，到达该活动时，所有途经活动上三项参数的累计总和。

3、例如，在网络中某项活动完成时，在该活动上可以得到从软件项目开始到此活动完成时刻的周期、累计费用和到此时已达到的性能值。从实际应用来看，随机网络较之PERT/CPM（当网络中各节点之间的传递函数服从分布，则该网络属于PERT类型，如果这些传递参数都是肯定型的，则成为CPM网络，他们都是随机网络的特例）已展现了巨大的潜力。从一九六九年GERT-E成功地用于美国“阿波罗”计划之后，相继在研究和发展性项目及生产过程中得到应用，如科研计划管理、可靠性科研计划管理、可靠性分析、机械制造生产线的设计和分析、质量分析、机械制造生产线的设计和分析、质量控制、自动化仓库管理、排队问题控制、自动化仓库管理、排队问题

4、等等。此外，在交通运输、人口动态分析、交通运输、人口动态分析、计算机系统、商务合同签定计算机系统、商务合同签定等方面也都得到应用。八十年代初期，NASA又将Q-GERT和SLAM成功地用于航天飞机发射及回收过程的网航天飞机发射及回收过程的网络计划络计划中。因此就GERT本身来说，理论上已经发展到了一个相当成熟的阶段。GERT网络图是由枝线、节点和流3个要素组成。（1）枝线）枝线又称有向边或传输元素，它是从一个节点出发，到一个节点结束的有向线段。在随机网络中，可以表示具体的工作，也可以表示工作的结果或两工作间的相互关系。（2）节点）节点是枝线的连接点，它既表明各枝线间的相互关系，又表示了前面枝线

5、的结束和后面枝线的开始。在随机网络中，除了源节点和终结点外，每个节点必须有一个引入枝线和一个引出枝线，同时允许有多个源节点和多个终节点，即允许多个目标的存在。并且除了源节点和终节点外，每个节点都是由输入端和输出端组成。在GERT网络图中输入端有三种逻辑关系，输出端有两种逻辑关系，共同构成六种不同功能的节点，如表1所示。表表1 GERT模型节点类型模型节点类型 异或型(互斥型)输入：至该节点的任一工作实现，该节点即实现，但在给定时间上，只有一个工作能实现。或型(兼有型)输入：通向节点的任一工作实现，该节点即实现，而节点实现的时间是通向节点的各工作中时间最短者。与型(汇合型)输入：当所有引入此节点

6、的工作都实现时，该节点才实现，节点实现的时间是各工作中时间中最长者。确定型(肯定型)输出：由此节点引出的工作迟早都实现，即自该节点发出工作被完成的概率为1。概率型(随机型)输出：当节点实现时，所有从该节点引出的工作中只有一个工作按一定的概率得以实现。（3）流）流是反映网络中的各种定量参数和节点间(或枝线)的相互定量制约关系，如工作的时间、费用，消耗的各种资源，效益以及实现的概率等。在GERT网络模型中，每条枝线上通常会用三个参数表示流，如图1所示：图图1随机网络基本节点关系随机网络基本节点关系 Fig.1 Basic relationship of random networks node 图

7、1中：U-节点1到节点2的流；-当节点1实现时，枝线将要实现的概率；-该枝线实现所需要的时间，它是服从一定概率分布的随机变量；-该枝线实现所需要的费用，它是服从一定概率分布的随机变量。0P0P0T0C 在随机网络中，各节点可以理解为工作的状态。随着时间的推移，系统从一种状态转移到另一种或多种状态时，即从某一节点转移到其它可能的节点时，可以有不同的概率（概率分布可选取任何种类），也就是说，从某一节点以一定的概率转移到另一节点去，节点引出的枝线允许有多个概率分支。节点和枝线不一定都实现，实现的可能性取决于节点的类型和枝线的概率系数。因为工作活动状态之间的转移具有概率性质，而且状态之间的传递关系也服

8、从一定的概率分布，所以网络的运行过程就具有随机性质。在状态转移中，在状态转移中所有的传递关系将表现为某些参数(即流)的变化，或某些资源的占用。这些传递参数通常服从一定的概率分布，即节点之间的转移，其传递参数将按一定的概率分布取不同的数值，这是随机网络的又一特征。然而，在随机网络中并不排除一部分节点之间存在肯定性的转移关系，即转移概率取1的转移关系，即肯定性转移关系。如果网络中各节点之间的传递参数唯一地服从分布，则该网络属于PERT类型。如果这些传递参数都是肯定型的，那就成为CPM型网络，即肯定型网络了。在随机网络模型中，假设：各节点之间的转移概率不随时间而变化。这相当于马尔科夫过程中转移概率不

9、变的稳定性假设，从而保证系统的稳定性。在任何时点上，从节点i转移到节点j，j只与节点i有关，而与如何到达节点j的过程无关，这是马尔科夫假设的“健忘性”。但是由于节点转移需要一定的随机时间，因此随机网络模型实际上是半马尔科夫过程模型。在随机网络中，主要有三种逻辑输入节点，“与”型、“或”型和“异或”型。但是只有“异或”型节点容易用数学方法进行解析处理，所以一般情况下，需要把“与”型和“或”型节点用“异或”型节点来进行组合以替代。在节点仅为互斥型输入，而输出为概率型的GERT网络模型中，适当地规定其活动参数的概率特征，GERT网络将成为一种典型的线性系统，这样可以用一种具有线性特征的“信号流图”模

10、型来计算随机网络中各节点之间的传递关系，并利用矩母函数的基本性质来计算网络的各种概率分布数字特征，从而得到随机网络在平衡状态下的解析解。下面我们从信号流图理论入手，开始大概介绍一下随机网络的原理。3.1信号流图理论简介信号流图理论简介 信号流图是以网络图形式表示所研究系统(或问题)中各变量之间的相互关系，是一种线性系统的建模和分析工具。起初用于配电网络的分析计算，以后逐步扩展到工程中其它线性系统，如电路分析、自动控制、概率与统计以及随机网络等。在信号流图中，系统的元素用节点和箭头表示。节点代表一定的变量，箭头表示变量之间的关系，即节点之间的传递系数或传递函数。这些传递函数可以由一个或若干个参数

11、组成，箭头的方向表示所联系节点之间的传递方向，如图2所示。图图2信号流图基本组成信号流图基本组成 Fig.2 Basic composition of signal flow graph 如上图2，在任意系统中，对于任意两个相邻的节点i和节点j，如果存在一 该式反映了变量之间的相乘关系，各节点所代表的变量之间的关系具有线性关系，只要这些线性方程组有解，即可确定信号流图中各个节点上的变量值。3.2信号流图的拓扑等价特性信号流图的拓扑等价特性 根据节点定律，复杂信号流图可以简化为某种等价的信号流图，并得到相应的等价传递系数或传递函数，这种简化过程，表明信号流图的拓扑等价特性。信号流图的三种基本形式

12、的等价传递关系如下：串联元素的传递关系为各串联枝线上的传串联元素的传递关系为各串联枝线上的传递系数的乘积，即递系数的乘积，即 如图3所示，图图3串联元素的传递关系串联元素的传递关系 Fig.3 Transitive relation of serial structure 并联元素的传递关系为各并联枝线上的传并联元素的传递关系为各并联枝线上的传递系数之和，即递系数之和，即 如图如图4所示，即所示，即图图4并联元素的传递关系并联元素的传递关系Fig.4 Transitive relation of parallel structure31132 23=+xxtx t31132 23=+xxtx

13、t 如图5，即图图5自环元素的传递关系自环元素的传递关系Fig.5Transitive relation of loop-self structure任何信号流图都可以转化为以上三种形式，从而有可能得到等价的信号流图。3.3信号流图的拓扑方程信号流图的拓扑方程 信号流图的特性提供了简化信号流图和求解等价传递系数的方法。1953年，梅森提出求解信号流图拓扑方程，可以求出信号图中任意两个节点间的等价传递系数。为了说明该方程的应用，先对以下概念进行说明。环在信号流图中，当开始节点与终节点完全重合时，连接这些节点的封闭路径为环。闭信号流图当信号流图中每个节点(或箭头)都至少属于一个环时，该图称为闭信号

14、流图。利用以上概念，可将梅森的拓扑方程表达式如下：从理论上说，把信号流图原理和矩母函数的特征结合起来就形成GERT网络解析算法的基础。接下来，介绍矩母函数概念及其特征。4.1矩母函数矩母函数 令在网络其中节点集合中，仅含“异或”型节点，随机变量为工作集合中第(ij)个工作的周期。按节点逻辑，工作(ij)必须在节点i实现时才能执行。因此，要知道工作(ij)的执行情况，就需要知道在给定节点i实现的条件下，工作(ij)被执行的概率，以及的概率分布(离散变量)或概率密度函数(连续变量)。其中，S为任意实数。根据矩母函数的定义，可以得出几种常用分布的矩母函数，如表2所示。由上面的叙述可知道，GERT网络

15、中串联、并联和自环结构的等价传递函数与信号流图中所描述的线性系统完全一致，而GERT网络都是由这三种形式所构成，从而在理论上奠定了求解GERT网络解析解的基础。以上是针对输入端点为“异或”型的等价传递函数描述，另外两种输入节点-“与”型和“或”型在解析求解时，串、并联及自环路结构简化方式汇总如表3所示。表表3 GERT模型中串、并联及自环路结构简化方式表模型中串、并联及自环路结构简化方式表 在一个GERT网络中，任何“与”型节点或“或”型节点，都可以通过一定的网络逻辑变换，使之转化为“异或”型节点，即可以转化为仅含单一“异或”型节点的随机网络，从而使GERT网络的解析求解成为可能。此外，以上解

16、析法过程，不仅限于求解GERT网络由源节点到终节点之间的传递函数和网络参数，而且，由网络中任意一个节点到另一节点之间，也可通过引入闭合反馈活动，求得相应的等价传递函数和其它概率参数。对于具有多个源节点和多个终节点的GERT网络，也同样是适用的。5 例题例题 算例算例1：某物流企业根据实际情况对其即将进行的自动化立体仓库检修作了一个GERT随机网络图，见图1，各检修程序的概率及时间分布见表，其中假设各检修程序完成的时间均服从正态分布。试讨论该自动化立体仓库的维修风险。图1 表表1 该网络中，有3个一阶环（W3，W4，W5）、（W7，W8）、（W2，W3，W4，W6，W7，W9，W11）和1个二阶

17、环（W3，W4，W5，W7，W8）由19有一条路径（1，2，3，4，5，6，7，8，9）则该网络的特征式为：代入梅森公式 由计算结果看出，节点9肯定会实现，这是合乎情理的，因为无论如何，该检修项目是必定会完成的。本次自动化立体仓库检修需22.1327天，离散程度，即风险为7.337天，风险度为33.15%，由此可见，该维修项目完成的时间变化范围较大。算例算例2：某发电厂按年初计划将进行检修，检修任务由各专业组负责，经费包干，并定于20天之后进行整体验收。该厂的热工专业维修组分配到维修经费32万元，试分析该组能否按时完成检修任务，参加机组整体验收，费用是否超支？该热工专业维修组根据实际情况，将此

18、次检修任务时间与费用安排如下：首先制定此次检修的具体措施，包括外请专家的联络、带实习学生以及新技术工人的培训以及购置一些设备仪器等等；然后进行仪器校验检修；仪器校验检修之后进行现场调试，但是现场调试如不成功，还需返回重新进行仪表校验检修，估计返回的概率为20%；现场调试通过后就可以进行准备整体验收了。各个阶段的时间费用见表3：表3 根据上述安排，构造热工专业检修的GERT网络图如下：结果分析：从计算结果看出，完成该维修项目的时间预计需17.75天，可能发生的变动，即风险度为36.997%，所以该热工专业组通过努力应该能保证20天后按时参加整体验收；在费用方面，预计会发生32.5万元的维修费用，风险度为33.88%，可见在维修过程中，随机因素对造成维修费用变化的影响较大，很可能造成维修费用超支，所以在维修过程中要严格控制概率型输出节点4的变化，尽量减少环路发生的可能，节约维修费用。