【《GERT网络解析法求解步骤概述》2500字】

第iv页共31页GERT网络解析法求解步骤概述GERT背景介绍图示评审技术（GraphicEvaluationReviewTechnique，GERT）最早可追溯到1957年的“关键路径法”(CriticalPathMethod，简称CPM）和1958年的“计划评审技术”(ProgramEvaluationReviewTechnique，简称PERT)，GERT在这基础上添加了概率分支，并且允许回路和自环的存在等，使其构模功能和应用范围有了显著的扩展REF_Ref31024\r\h[31]。陶良彦等REF_Ref32057\r\h[32]针对GERT解析算法在网络结构较为复杂时计算量大、易出错的问题提出了GERT矩阵式解法，利用行列式求出等价传递函数，并且通过矩阵变换来简化网络结构。陶良彦等REF_Ref1\r\h[33]提出以特征函数为传递函数的GERT网络，解决了矩母函数的存在性问题，并且进一步能够得到传递变量的概率密度、累积分布函数。夏宏清等REF_Ref28175\r\h[34]构建系统任务流程GERT模型，针对资源共享引起的活动排队和上下游活动重叠引入时间因子，修正了活动执行时间，并找出关键活动，以供进一步任务优化。郭本海等REF_Ref28276\r\h[35]构建了基于创新价值流动的新能源汽车产业链功能演化GERT网络模型，并应用于知识互溢视角下，通过对比分析给出其重要意义。李亚平等REF_Ref28798\r\h[36]根据多工序间质量损失传递演化关系，提出了基于改进型GERT网络的质量损失预测方法，通过加入算子描述质量损失耦合关系和返工对质量的改善，构建了一类融合算子的改进型GERT网络。GERT原理介绍在介绍GERT网络之前，首先来介绍一类广义活动网络，即GAN网络。GAN网络是在CPM与PERT之后、先于GERT诞生的一种网络技术。当一个客观系统动态运行时，其本质是系统状态的转移过程。我们用网络节点代表状态，连接节点的箭线代表状态传递关系，就可以用网络的形式来描述系统的运行。在这基础上，对状态的转移赋上概率性质，并且对其传递关系给出指定概率分布，网络就随之变得“随机”。也就是说，从一节点转移到其他节点的概率可能不同，即从给定节点有一定的概率转移到另一节点去。如果从给定节点以1的概率转移到另一节点，则称之为肯定型转移；若网络中所有节点之间都属于肯定型转移，该网络退化为PERT/CPM的状况。箭线所描述的传递关系通常表现为一些服从一定概率分布的传递参数；若网络中所有的传递参数都唯一服从β分布，则网络退化为PERT类型；若网络中所有的传递参数都是肯定型数值，则网络退化为CPM类型。综上所述，GAN网络的一般要素为概率及传递参数及其分布，可按图2.4的形式标识与箭线上，通常用一个二维及以上的向量加以描述。以图中为例，pu代表节点1实现时，活动（1，2）实现的概率，tu代表活动（1，2）所需的时间，可能是一随机变量，图2.4GAN网络一般要素在网络中，除了源节点和终节点外，每一节点至少有以引入箭线和一引出箭线，同时允许存在多个源节点和多个终节点。任一节点存在“输入”和“输出”两端，GAN网络中定义了三种“输入”类型和两种“输出”类型，如图2.5，可组合成六种逻辑功能。图2.5GAN网络节点类型其中各节点含义如下：·“异或”型输入：节点实现，若任一引入活动完成，注意某时刻只有一个活动能完成；·“或”型输入：节点实现，若任一引入活动完成，允许某时刻有同时完成的活动；·“与”型输入：节点实现，当且仅当所有引入活动完成；·“概率”型输出：节点实现时，引出活动中只有一个按一定概率实现，各引出活动实现概率和为1；·“肯定”型输出：节点实现时，所有引出活动被执行的概率均为1，即所有活动迟早要被完成。在输入型节点中，“异或”型处理起来较为方便，因此常常通过适当逻辑变换，将“或”型和“与”型转换为“异或”型。此外，GAN网络允许自环存在，即网络中可以有反馈环节，同时需要说明的是，网络实现不代表所有节点都实现，可能只有一部分处于活动路线上的节点被实现。对GAN网络有了基本认识后，GERT就是仅含“异或”型输入节点和“概率”型输出节点的网络。下面给出GERT解析算法，主要涉及信号流图中的梅森公式和概率论中的矩母函数。信号流图是描述线性系统的图形化工具，可以对其建立模型并分析，主要应用于自动控制、电路分析、概率与统计等领域。它表示了若干个变量间的关系，节点代表变量，箭头表示节点之间的传递系数或函数。首先对信号流图的概念做一些说明。定义2.1在信号流图中，联结节点的封闭路径成为环，若开始节点与终节点完全重合；环称为一阶环，若环内每一节点可有环内任何其它节点到达；一组n个一阶环称为n阶环，若该组一阶环间不存在公共节点。定理2.1给出了求解等价传递系数的梅森公式。定理2.1设xi,x Tij=其中，∆表示信号流图的特征式，即 ∆=1−式(2.1)、(2.2)中，各参数含义如下：·i——在m阶环中的第i个环·m——图中环的阶数·Ti(Lm)·pk——由i到j第k·∆k——消去与第k为了进一步简化计算，通过简单的证明可以得到推论2.1。推论2.1对任意闭信号流图，其特征式必等于0证明：给定输入端为源节点s，输出端为终节点t，由式(2.1)，可求得s到t的等价传递系数，假设为T在图中加入一个由t到s的闭合箭头，并设其传递系数为TA,则此时的闭信号流图可以看成一个传递系数为T由传递系数的概念可知x故xt=T由式(2.2)，设此闭信号流图的特征式为∆∗∆证毕。推论2.1还可以表示为∆∗下面引入传递函数的概念，这里暂时考虑包含概率的两传递参数。定义2.2网络G=(N,A)，其中N仅包含“异或”型节点，设pij为活动集合A中第(i,j)个活动的概率，cij第(i,j)个活动的另一传递参数，则活动 Wij(s)=其中Mij(s)是cij的矩母函数，即Mij(s)=不难发现，GERT网络结构及其传递函数与信号流图的结构及其传递系数完全一致，因此，在对GERT网络进行传递函数运算时，可以直接采用信号流图中等价传递系数的方法，即定理2.1或推论2.1。根据定义2.2，可推出传递函数的性质。性质1GERT网络等价概率pE为等价传递函数WE(s)性质2GERT网络等价矩母函数为等价传递函数与等价概率之商。综