《用gert方法解决两个抛硬币问题1》由会员分享，可在线阅读，更多相关《用gert方法解决两个抛硬币问题1（13页珍藏版）》请在金锄头文库上搜索。
1、用用 GERT 方法解决两个抛硬币问题方法解决两个抛硬币问题1 一、一、 GERT 方法简介方法简介 GERT 方法(Graph Evaluation and Review Technique)又称图解评审技术， 它是结合流线图理论(flow graph theory)、矩母函数(MGF，Moment Generating Function)、计划评审技术(PERT，Program Evaluation and Review Technique)来解决随机网络问题的一种方法。 1 流线图流线图 流线图是最基本的网络技术之一。 它以网络图形式表示所研究系统或问题中各变量之间的关系。流线图由节点、
2、枝线和通过枝线的流三个基本要素组成，如图 1 A、B为节点，A与B之间的关系通过它们之间的有向枝线（箭杆）连接，R为这条枝线的参数，表示A与B之间的定量关系。变量A与B之间的依存关系为BRA=，R反应了变量间的相互定量关系，也称作传递系数。这是流线图的基本特征。 (1) 流线图的线路和回路流线图的线路和回路 线路：流线图中，由一系列连接两个节点的枝线组成，且每个节点只通过一次。 在下图 2 中， 从节点 1 到节点 5 的线路有三条：1235，125，135.一条线路的值等于该线路上各传递系数的乘积。在图 2 中，线路1235的值为.ach 回路：流线图中，从一个节点开始，通过一系列依次连接的
3、枝线，又回到原开始节点的线路， 且除原开始节点外， 其他任何节点只通过一次。 在下图 2 中，有两条回路，节点 3 自身的回路及回路242. 一条回路的值等于该回路上各传递系数的乘积。图 2 中，回路242的值为e d. 1 本文第一部分引用我硕士论文中的部分内容，主要目的是：一方面向大家介绍 GERT 方法，另一方面作为阅读本文第二部分时的参考内容。 A RB图 1 最基本的网络图组成 (2) 回路的阶回路的阶 流线图的求解与流线图中回路的构成情况密切相关。关于流线图中回路的“阶”: 1 阶回路：从一个节点出发又回到本节点的回路，即上面所提到的按回路定义组成的回路。图 2 中的节点 3 自身
4、的回路及回路242都属于 1 阶回路。 2 阶回路：由两个互不接触（即没有公共节点）的 1 阶回路组成的，其值等于组成该 2 阶回路的两个互不接触的 1 阶回路值之积。 n阶回路：由n个互不接触的 1 阶回路所组成，其值等于这n个 1 阶回路值的连乘积。从定义可以看出，n（2n ）阶回路已经不是严格意义上的回路了，因为组成该n阶回路的n个 1 阶回路是互不接触的。 图 2 中存在一个 2 阶回路， 组成该 2 阶回路的 1 阶回路分别是节点 3 自身的回路及回路242，所以该 2 阶回路的值为()fe d. (3) 梅森公式（梅森公式（Masons Rule） 梅森公式是求解流线图及随机网络模
5、型的最重要也是最基本的公式之一， 通过梅森公式可以求得流线图中任意两节点间的等效传递系数。 梅森公式的表达式为： 1mkk k ijP T= =其中： ijT：流线图中从节点i到节点j的等效传递系数； kP：流线图中从节点i到节点j的第k条线路的值，它等于构成该线路的枝线的传递系数乘积； m：节点i到节点j的线路条数； 1 2354abcdefgh图 2 流线图的线路与回路 k：流线图中不与第k条线路接触的回路的特征值， 1+kkk = 不与第 条路接触的奇数阶回路的值不与第 条路接触的偶数阶回路的值；：流线图中反映回路组成的特征值， 1 = +两节点间奇数阶回路的值两节点间偶数阶回路的值.
6、为说明该公式，我们计算图 3 中节点 0 到节点 5 的等效传递系数05T.该图中各枝线上的字母表示该枝线连接的两节点间的传递系数。 第一步，找出05的所有线路，并求出不与该线路接触的回路的特征值。线路总共有两条： 0135 :1Paeg= ,11()idid = +， 045:2Phj=,21()()fdbcdfbcf = +， 第二步，计算节点 0 到节点 5 的回路特征值， 1()()()bcdfidibciifdfbcffidfibc = +， 最后求得节点 0 到节点 5 的等效传递系数05T ， 21 05(1)(1) 1 ()()()kk kPaegididhjfdbcdfbcf
7、Tbcdfidibciifdfbcffidfibc= +=+ . 2 随机网络和矩母函数随机网络和矩母函数 (1) 随机网络的逻辑节点随机网络的逻辑节点 随机网络的节点由输入端和输出端组成。输入端和输出端的具体类型分别见表 1 和表 2： 0 12345bacefgjh 图 3 梅森公式求节点 0 到节点 5 的等效传递系数 di表 1 随机网络节点输入端的类型 节点名称 符号 逻辑特征 互斥型 在给定的时间内，通向节点的活动（枝线）中 只有一个能够实现。任一活动实现，节点就实 现 兼有型 通向节点的任一活动实现，节点就实现，而节 点实现的时间是通向节点的各活动中的最短者 汇合型 通向节点的所
8、有活动都完成后，节点才实现， 节点实现时间是各活动中时间最长者。这与一 般的网络模型的输入节点相同 表 2 随机网络节点输出端的类型 节点名称 符号 逻辑特征 肯定型 如果节点实现，则由该节点开始的活动（发出 的枝线）都进行，即自该节点发出活动的概率 为 1，这与一般网络节点输出相同 随机型 如果节点实现，则由该节点开始的活动（发出 的枝线）仅有一个能进行，各活动可能开始的 情况取决于其实现概率 不同的输入端和输出端可以组成以下六种节点形式： 表 3 随机网络节点的类型 输入端 输出端 (2) 随机网络的特点随机网络的特点 随机网络主要有以下几个特点： a. 随机网络模型的枝线和节点不一定都实
9、现；互斥型输入端的枝线只能实现其中之一；随机型输出端发出的枝线也只能实现其中之一； b. 随机网络中可有回路，表示节点或某些活动可以重复出现； 汇合型 肯定型 兼有型 随机型 互斥型 c. 两节点间可以有多条枝线； d. 随机网络可以有多个目标，每个目标反映一个具体的结果； (3) 随机网络的分析方法与矩母函数随机网络的分析方法与矩母函数 随机网络模型的计算， 由于有多种不同性质的参数以及有各种不同类型的节点，因此比较复杂。目前应用数学分析方法，还仅仅局限于互斥型节点。互斥型随机网络的每一条枝线一般有两项参数：一是该枝线可能实现的概率ijp；二是完成该枝线活动所需要的时间函数( )ijft。这
10、两项参数是随机网络中实现节点转移的依据，又称为枝线的传递系数。随机网络模型中最基本的传递如下图： 随机网络模型的互斥型节点的特点：任何时刻进入该节点的枝线只有一条实现(从模型或图上看)，该活动实现导致该节点的实现；从该节点出去的所有枝线实现概率之和是1，各条枝线代表的活动互斥，即从该节点出去的活动在某时刻只有一件可以实现，实现的概率等于该枝线上的条件概率。 一般网络图中，串联活动的时间是相加的，并联活动在节点处取值。在流线图中，串联活动的传递系数相乘，并联活动传递系数相加。有回路时，按梅森公式计算。为便于理解，先考虑传递系数枝线实现的条件概率和实现的时间均为常量的情况。 在随机网络模型中，枝线
11、活动的实现时间可以是常量，也可以是符合一定概率分布的随机变量。这里有这样一个问题，比如在串联系统中，系统实现的等效概率是各条枝线实现概率相乘，而等效实现时间却是各条枝线实现时间相加。所以如何处理随机网络中这两种性质不同的参数是求解随机网络模型的关键。而且， 在求解随机网络模型时， 对每个活动必须知道在给定节点i实现条件下活动ij实现的概率ijp以及活动实现时间ijt的概率分布或概率密度函数。 由于随机网络模型中的时间都是常量或都是符合一定概率分布的随机变量，所以可以根据随机变量概率分布的矩母函数的特征， 把网络中相加性质的传递参数变成相乘性质的传递参数，然后用梅森公式计算。根据概率论中随机变量
12、概率分布矩母函数的特征：各随机变量总和的矩母函数等于各随机变量矩母函数之积。 ij( ),ijijpft图 4 互斥型节点的一枝线的传递系数 对于随机变量时间t和任意实数s，随机变量t的矩母函数为( )tM s，有 ( ), ( )()( ), st st t ste f t dttM sE ee P tt+ = 为连续随机变量；为离散随机变量.其中( )f t和( )P t分别是t为连续随机变量时的概率密度函数和t为离散随机变量时的概率分布函数。 引入了矩母函数就可将反映枝线活动特征的枝线实现的条件概率和实现时间参数综合到一起，变为枝线的传递系数( )ijW s，且有( )( )ijijij
13、W sMs p=. 具体的参数综合过程见下图： 那么以上的串联、并联和回路的情况均可以简化。 串联系统： 1 31 31 3( )( )( )ababWpMsp p Ms Ms=. 并联系统： 1 21 21 2( )( )( )()( )( )aabb abaabb abp Msp MsWpMsppp Msp Mspp+=+=+. 回路系统： 1 2( )( )aabbp MsMsp+1 2( )aap Ms( )bbp Ms1 21 23( )aap Ms( )bbp Ms( )( )ijijijWsp Ms=i j图 5 随机网络基本元素的传递系数 ( )( )ababpMs Msp2
14、1 2( )( )1( )( )( )1( )iaa aabbbbbb bbp MsWp Msp Msp Msp Msp Ms=+=?. 3 条件矩母函数条件矩母函数 对有些工程技术系统及经济管理问题的研究， 往往需要分析网络模型中局部的执行情况，以及局部与总体执行情况的关系。例如，由于计算机网络中的回路问题的存在，那么系统中有些部分就可能实现多次，这一局部实现多次就会影响到整个系统的运行。因此，需要研究随机网络中某元素的执行次数的矩母函数及特定条件下的条件矩母函数。 (1) 枝线执行次数的矩母函数枝线执行次数的矩母函数 对研究的枝线的传递系数乘以ce .注意ce等价于常量1的矩母函数。现在是
15、只考虑枝线执行次数的随机网络模型。以图6为例，研究节点2上的自回路的执行次数 利用梅森公式可以得到节点1至节点3的等效传递系数， 426221(1)32( , )( , )11162scsscsee e W s cM s c ee e = . 当0s =时，有关时间的矩母函数为1，而计数的矩母函数将被保留，即 12342 3se31 3se21 2sce e31 2se图 6 研究节点 2 上自回路的执行次数情况 1 21 2( )aap Ms( )bbp Ms( )( )1aabbp MsMsp021 33( , )( )51 62cscWe s cM c e= = , 节点2上的自回路执行
16、次数的期望值可以根据其矩母函数的一阶矩确定，即 0( )1 2cM cEc=. 表示节点1平均每到达节点3一次，节点2上的自回路平均执行0.5次。 (2) 节点执行次数的矩母函数节点执行次数的矩母函数 求通过某一已知节点的次数的矩母函数的方法与求枝线执行次数的矩母函数的方法完全相同。 只要在进入该节点的每条枝线的传递系数上增加ce， 因为导入一已知节点的所有路线传递的总和等价于这个节点的实现次数。以图7为例，求节点2实现次数随机变量的矩母函数。 首先对进入该节点的两条枝线都加上ce . 426221(1)32( , )( , )11162scssccsee e W s cM s c e ee e = ,021 33( , )( )213csce W s c
