随机网络简介课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.1 概述,随机网络,也称计划评审技术(PERT),是一种反映多种随机因素的网络技术。与传统的网络技术不同,随机网络技术模型中的节点、箭线和流量均带有一定程度上的不确定性,不仅反映活动的各种定量参数,如时间、费用、资源消耗、效益、亏损等是随机变量,而且组成网络图的各项活动也可以是随机的,可按一定的概率发生或不发生,并且允许多个原节点或自多个汇节点的网络循环回路存在。,一、随机网络的构成和特点,1.1 概述 一、随机网络的构成和特点,1,1.1 概述,60年代,美国国防部在阿波罗空间系统研究、制造和发射过程中,首次建立了随机网络模型,并提出了分析和求解随机网络的方法,用以确定该系统的最终发射时间,协调各承包商的工作进度,取得了明显的效果。,一、随机网络的构成和特点,一、随机网络的构成和特点,2,案例一：,某钢结构工业厂房,委托一家外地企业加工,材料货源分别来源于三家不同的企业,三种材料按计划陆续供货,先交货先加工。结构件制作完后,可根据当地的运输条件选用水路航运或铁路运输运到目的地。结构构件在现场检查组装,然后开始安装。由于结构构件高大，在安装时受风的影响大，工期有一定的伸缩性。对这些活动存在的多种情况，各所需的时间及其实现概率如下表所示，根据上述条件，可绘出随机网络图，如下图所示。,一、随机网络的构成和特点,案例一：一、随机网络的构成和特点,3,序号,工作内容,状态,工作名称,参数内容,时间（d）,概率,1,交付图纸,A,90,1.00,2,材料供应,甲厂供料,B,50,0.30,乙厂供料,C,30,0.30,丙厂供料,D,40,0.40,3,结构加工制作,E,120,1.00,4,结构运输,水路,F,30,0.65,铁路,G,18,0.35,5,构件检查组装、焊接,H,50,1.00,6,结构安装,刮风,I,70,0.50,正常,J,60,0.50,一、随机网络的构成和特点,钢结构加工活动时间及概率,序号工作内容状态工作名称参数内容时间（d）概率1交付图纸A,4,一、随机网络的构成和特点,一、随机网络的构成和特点,5,1.2 随机网络图的构成,(一)节点符号表示方法:,(1)输入部分,第一种形式:互斥型,第二种形式:兼或型,第三种形式:汇合型,一、随机网络的构成和特点,一、随机网络的构成和特点,6,节点名称,互斥型,兼或型,汇合型,符号,三种节点输入形式,一、随机网络的构成和特点,节点名称互斥型兼或型汇合型符号三种节点输入形式一、随机网络的,7,(2)输出部分,第一种类型:肯定型,第二种类型:随机型,一、随机网络的构成和特点,节点名称,肯定型,随机型,符号,两种节点输入形式,(2)输出部分 一、随机网络的构成和特点节点名称,8,对于一张随机网络图既有起止节点,又有中间节点。由于中间节点有输入部分,又有输出部分,节点需同时能表达不同的输入关系和输出类型,上述不同节点的输入和输出形式可以组合成六种节点形式。,一、随机网络的构成和特点,对于一张随机网络图既有起止节点,又有中间节点。由,9,（二）箭线及传递系数的表示方法,随机网络的箭线可以表示具体的活动，也可以表明一项活动的结果，或者两项活动之间的关系。为了表达活动的时间、成本、效率,还必须进一步说明实现各项活动的有关参数,即节点之间通过箭线传递的系数。,一、随机网络的构成和特点,一、随机网络的构成和特点,10,常用的传递系数有两类:,时间或费用系数,反映活动所需的消耗,概率系数,反映活动实现的可能性及质量合格率等,一、随机网络的构成和特点,一、随机网络的构成和特点,11,时间系数可以是常数或者服从某种理论分布的密度函数，如 或 。例如某活动的时间系数被认为服从正态分布,且已知均值 和方差,则可表示为,并可作为计算时的参数依据,;,每项活动的概率系数一般假定为常数。,传递系数的表示方法如图所示：,一、随机网络的构成和特点,P,ij,f,ij,(t),j,i,j,一、随机网络的构成和特点Pij,fij(t)j,12,1.3,随机网络的特点：,与普通网络图比较,随机网络具有以下几个特点,:,(1),随机网络的箭线和节点不一定都能实现,实现的可能性取决于节点的类型和箭线的概率系数；,(2),随机网络中各项活动的时间可以是常数,也可以是服从某种概率分布的密度函数,更具有不确定性；,一、随机网络的构成和特点,一、随机网络的构成和特点,13,一、随机网络的构成和特点,1.3,随机网络的特点,：,与普通网络图比较,随机网络具有以下几个特点,:,(3),随机网络中可以有循环回路,表示节点或活动可以重复出现；,(4),随机网络中的两个中间节点之间可以有一条以上箭线；,(5),随机网络中可以有多个目标,每个目标反映一个具体的结果,即可以有多个起点或终点。,一、随机网络的构成和特点,14,随机网络所处理的是广义概率型的网络,由于有多种不同性质的参数和各种不同类型节点,需要根据不同情况对随机变量进行分析和计算，计算比较复杂。,二、随机网络的分析计算,二、随机网络的分析计算,15,2.1 传递系数-概率P,ij,和持续时间f,ij,(t)均为常量的情况,组成随机网络图的基本形式有:串联、并联和回路,如图所示:,二、随机网络的分析计算,2.1 传递系数-概率Pij和持续时间fij(t)均为常,16,(1),串联,:,串联元素的传递系数为各串联枝线上的传递系数的乘积,即,:,(2),并联,:,并联元素的传递系数为各并联枝线线路的传递系数之和,即,:,(3),回路,:,有自身回路的传递系数为节点发出线路值与,(),的乘积，即,:,二、随机网络的分析计算,二、随机网络的分析计算,17,2.2 传递系数-概率,P,ij,为常量,f,ij,(t),是符合一定概率分布的随机,变量情况,现就图所示的串联、并联和回路三种基本形式,用流线图方法求解,二、随机网络的分析计算,2.2 传递系数-概率Pij为常量,fij(t)是符合,18,(1),串联,辅助函数等价关系,:,矩母函数的等价关系,:,二、随机网络的分析计算,(1)串联二、随机网络的分析计算,19,(2),并联,辅助函数等价关系,:,矩母函数等价关系,:,二、随机网络的分析计算,(2)并联二、随机网络的分析计算,20,(3),回路,辅助函数等价关系,:,矩母函数等价关系,:,二、随机网络的分析计算,(3)回路二、随机网络的分析计算,21,随机网络的解题步骤可归纳为以下几点,:,(1),针对所研究的系统和问题,反复考虑和剖析,找出能反映计划,模型的主要因素,按照活动的逻辑关系,选择合适的节点类型,绘制出随机网络计划模型。,(2),收集有关网络图中传递系数的必要资料,并尽量使其符合实际,保证模型系数的准确性。若活动时间不能用常数表示,可以估,一个均值和方差,或者确定一个大致范围,再选择一个合适的,概率分布密度函数,做到有据可依。,三、随机网络的解题步骤,随机网络的解题步骤可归纳为以下几点:三、随机网络的解题步骤,22,随机网络的解题步骤可归纳为以下几点:,(3)应用梅森(Maso)公式,确定各项活动的辅助函数,并对网络图进行适,当归并和简化,转换成等价网络图,便于分析计算。,(4)通过计算,求出随机网络最终所需时间及实现概率。根据矩母函数,在S=0时,其值为1,即，求得特定节点的实现概率；在求得节点实现,的条件概率后,根据,求得特定节点实现的期望值。另外,根据需要,还可以求出所需成本等其他必要的参数,。,二、随机网络的分析计算,随机网络的解题步骤可归纳为以下几点:二、随机网络的分析计算,23,随机网络的解题步骤可归纳为以下几点:,(5)根据计算结果,进一步分析该网络系统,对不同方案或不同问题,进行综合评价,并进行必要的调整和修改。,三、随机网络的解题步骤,随机网络的解题步骤可归纳为以下几点:三、随机网络的解题步骤,24,某航天飞机重返大气层的防护层研制工程有三个合同需招标,每个合同均包含设计、试验与制造三部分内容,其中合同,1,是最大而又最有利的系统,其次是合同,2,最后是合同,3,。某公司准备投标,其技术能力可以设计与试验三个方案,(,即合同,),中的任何两个,但是限于时间,只具有完成一个方案的制造能力。经考虑后公司负责人决定,:,先对合同,1,与合同,2,投标,(,下称投标,1,与投标,2),如果均被拒绝,再对合同,3,投标,(,下称投标,3),；如果投标,1,与投标,2,均成功,将对方案,2,签订关于制造期限的子合同,四、随机网络应用示例,四、随机网络应用示例,25,基于过去的经验以及本公司在行业内的竞争地位,公司负责人确认对三个合同投标成功的概率如下,:,四、随机网络应用示例,合同,1,2,3,投标成功概率,0.3,0.5,0.4,此外,由于方案1的复杂性,投标1有10%的可能性既不被接受也不被,拒绝,而要对合同1作出某些修改以后再进行第二轮招标与投标。公司,负责人认为:第二轮投标结果的概率与第一轮相同。,基于过去的经验以及本公司在行业内的竞争地位,公司负,26,投标成功后即进行设计。设计后试制出的样品必须经过一系列试验。试验中出现的小问题可以及时解决,但若试验整个失败,则要对系统重新设计与试验,又要耗费同样的代价。公司负责人估计试验成功的概率如下,:,现在要求建立该任务的网络模型,并且分析计算各种最终结果的概率,合同,1,2,3,实验成功的概率,0.6,0.8,0.9,四、随机网络应用示例,投标成功后即进行设计。设计后试制出的样品必须经过,27,根据活动之间的逻辑关系和节点的不同类型,可建立该工程的随机网络,如下图：,四、随机网络应用示例,四、随机网络应用示例,28,由于网络中的许多活动具有随机性,会存在多种可能的最终结果。所以就本例而言,存在着如下五种可能的最终结果,但仅有一种实现:,(1)系统1单独被移交(即公司把根据合同1制造好的系统移交给招标部门),其概率记为P1;,(2)系统2单独被移交,其概率记为P2;,(3)系统3单独被移交,其概率记为P3;,(4)系统1与系统2共同被移交,其概率记为P4;,(5)没有系统被移交,因为该公司的投标全部被拒绝,其概率记为P5。,四、随机网络应用示例,四、随机网络应用示例,29,实现系统1单独被移交的作业路线主要是=(1,2，4，5,6,7,8,25,26),其中包括两个反馈回路。作业(1，2)即对合同1投标的概率为1:那么这一,投标被接受的概率是多少呢?并不就是作业(2,4)上标注的0.3；因为在节,点2上有一条反馈弧即技标后对合同1修改(其概率为0.1)。而合同1修改一,次后,再投标又有0.3的被接受概率,这时,投标1被接受的总概率为:,0.3+0.10.3=0.33,四、随机网络应用示例,实现系统1单独被移交的作业路线主要是=(1,2，4，5,30,但是反馈环仍然存在,合同1可以第二次修改,第二次修改的概率为：,0.10.1=0.01,第三轮投标又有0.3的被接受概率,于是投标1被接受的总概率变为：,0.3+0.10.3+0.010.3=0.333,四、随机网络应用示例,但是反馈环仍然存在,合同1可以第二次修改,第二次修改的,31,反馈环“永远”存在,对合同1可以修改“无限多次”,于是得到一个等比级数 ,其首项=0.3,其公比q=0.1,故该级数之和为：,这就是考虑了节点2上的反馈弧以后,获得的关仔投标1被接受的概率。,四、随机网络应用示例,反馈环“永远”存在,对合同1可以修改“无限多次”,于是,32,对反馈弧,(6,4),也作类似考虑,则在投标已被接受的情况下节点,7,的实现,概率为：,0.6/(1-0.4)=1,若将其结合起来考虑,则在整个网络中,节点,7,从而作业,(7,8),实现的概率为：,11/3=1/3,四、随机网络应用示例,对反馈弧(6,4)也作类似考虑,则在投标已被接受的情况,33,其余的分析计算过程请读者试行推出,其结果是：,四、随机网络应用示例,其余的分析计算过程请读者试行推出,其结果是