随机网络简介.ppt

随机网络技术 1 1概述随机网络 也称计划评审技术 PERT 是一种反映多种随机因素的网络技术 与传统的网络技术不同 随机网络技术模型中的节点 箭线和流量均带有一定程度上的不确定性 不仅反映活动的各种定量参数 如时间 费用 资源消耗 效益 亏损等是随机变量 而且组成网络图的各项活动也可以是随机的 可按一定的概率发生或不发生 并且允许多个原节点或自多个汇节点的网络循环回路存在 一 随机网络的构成和特点 1 1概述60年代 美国国防部在阿波罗空间系统研究 制造和发射过程中 首次建立了随机网络模型 并提出了分析和求解随机网络的方法 用以确定该系统的最终发射时间 协调各承包商的工作进度 取得了明显的效果 一 随机网络的构成和特点 案例一 某钢结构工业厂房 委托一家外地企业加工 材料货源分别来源于三家不同的企业 三种材料按计划陆续供货 先交货先加工 结构件制作完后 可根据当地的运输条件选用水路航运或铁路运输运到目的地 结构构件在现场检查组装 然后开始安装 由于结构构件高大 在安装时受风的影响大 工期有一定的伸缩性 对这些活动存在的多种情况 各所需的时间及其实现概率如下表所示 根据上述条件 可绘出随机网络图 如下图所示 一 随机网络的构成和特点 一 随机网络的构成和特点 钢结构加工活动时间及概率 一 随机网络的构成和特点 1 2随机网络图的构成 一 节点符号表示方法 1 输入部分第一种形式 互斥型第二种形式 兼或型第三种形式 汇合型 一 随机网络的构成和特点 三种节点输入形式 一 随机网络的构成和特点 2 输出部分第一种类型 肯定型第二种类型 随机型 一 随机网络的构成和特点 两种节点输入形式 对于一张随机网络图既有起止节点 又有中间节点 由于中间节点有输入部分 又有输出部分 节点需同时能表达不同的输入关系和输出类型 上述不同节点的输入和输出形式可以组合成六种节点形式 一 随机网络的构成和特点 二 箭线及传递系数的表示方法随机网络的箭线可以表示具体的活动 也可以表明一项活动的结果 或者两项活动之间的关系 为了表达活动的时间 成本 效率 还必须进一步说明实现各项活动的有关参数 即节点之间通过箭线传递的系数 一 随机网络的构成和特点 常用的传递系数有两类 时间或费用系数 反映活动所需的消耗概率系数 反映活动实现的可能性及质量合格率等 一 随机网络的构成和特点 时间系数可以是常数或者服从某种理论分布的密度函数 如或 例如某活动的时间系数被认为服从正态分布 且已知均值和方差 则可表示为 并可作为计算时的参数依据 每项活动的概率系数一般假定为常数 传递系数的表示方法如图所示 一 随机网络的构成和特点 Pij fij t j ij 1 3随机网络的特点 与普通网络图比较 随机网络具有以下几个特点 1 随机网络的箭线和节点不一定都能实现 实现的可能性取决于节点的类型和箭线的概率系数 2 随机网络中各项活动的时间可以是常数 也可以是服从某种概率分布的密度函数 更具有不确定性 一 随机网络的构成和特点 一 随机网络的构成和特点 1 3随机网络的特点 与普通网络图比较 随机网络具有以下几个特点 3 随机网络中可以有循环回路 表示节点或活动可以重复出现 4 随机网络中的两个中间节点之间可以有一条以上箭线 5 随机网络中可以有多个目标 每个目标反映一个具体的结果 即可以有多个起点或终点 随机网络所处理的是广义概率型的网络 由于有多种不同性质的参数和各种不同类型节点 需要根据不同情况对随机变量进行分析和计算 计算比较复杂 二 随机网络的分析计算 2 1传递系数 概率Pij和持续时间fij t 均为常量的情况组成随机网络图的基本形式有 串联 并联和回路 如图所示 二 随机网络的分析计算 1 串联 串联元素的传递系数为各串联枝线上的传递系数的乘积 即 2 并联 并联元素的传递系数为各并联枝线线路的传递系数之和 即 3 回路 有自身回路的传递系数为节点发出线路值与 的乘积 即 二 随机网络的分析计算 2 2传递系数 概率Pij为常量 fij t 是符合一定概率分布的随机变量情况现就图所示的串联 并联和回路三种基本形式 用流线图方法求解 二 随机网络的分析计算 1 串联辅助函数等价关系 矩母函数的等价关系 二 随机网络的分析计算 2 并联辅助函数等价关系 矩母函数等价关系 二 随机网络的分析计算 3 回路辅助函数等价关系 矩母函数等价关系 二 随机网络的分析计算 随机网络的解题步骤可归纳为以下几点 1 针对所研究的系统和问题 反复考虑和剖析 找出能反映计划模型的主要因素 按照活动的逻辑关系 选择合适的节点类型 绘制出随机网络计划模型 2 收集有关网络图中传递系数的必要资料 并尽量使其符合实际 保证模型系数的准确性 若活动时间不能用常数表示 可以估一个均值和方差 或者确定一个大致范围 再选择一个合适的概率分布密度函数 做到有据可依 三 随机网络的解题步骤 随机网络的解题步骤可归纳为以下几点 3 应用梅森 Maso 公式 确定各项活动的辅助函数 并对网络图进行适当归并和简化 转换成等价网络图 便于分析计算 4 通过计算 求出随机网络最终所需时间及实现概率 根据矩母函数 在S 0时 其值为1 即 求得特定节点的实现概率 在求得节点实现的条件概率后 根据 求得特定节点实现的期望值 另外 根据需要 还可以求出所需成本等其他必要的参数 二 随机网络的分析计算 随机网络的解题步骤可归纳为以下几点 5 根据计算结果 进一步分析该网络系统 对不同方案或不同问题进行综合评价 并进行必要的调整和修改 三 随机网络的解题步骤 某航天飞机重返大气层的防护层研制工程有三个合同需招标 每个合同均包含设计 试验与制造三部分内容 其中合同1是最大而又最有利的系统 其次是合同2 最后是合同3 某公司准备投标 其技术能力可以设计与试验三个方案 即合同 中的任何两个 但是限于时间 只具有完成一个方案的制造能力 经考虑后公司负责人决定 先对合同1与合同2投标 下称投标1与投标2 如果均被拒绝 再对合同3投标 下称投标3 如果投标1与投标2均成功 将对方案2签订关于制造期限的子合同 四 随机网络应用示例 基于过去的经验以及本公司在行业内的竞争地位 公司负责人确认对三个合同投标成功的概率如下 四 随机网络应用示例 此外 由于方案1的复杂性 投标1有10 的可能性既不被接受也不被拒绝 而要对合同1作出某些修改以后再进行第二轮招标与投标 公司负责人认为 第二轮投标结果的概率与第一轮相同 投标成功后即进行设计 设计后试制出的样品必须经过一系列试验 试验中出现的小问题可以及时解决 但若试验整个失败 则要对系统重新设计与试验 又要耗费同样的代价 公司负责人估计试验成功的概率如下 现在要求建立该任务的网络模型 并且分析计算各种最终结果的概率 四 随机网络应用示例 根据活动之间的逻辑关系和节点的不同类型 可建立该工程的随机网络 如下图 四 随机网络应用示例 由于网络中的许多活动具有随机性 会存在多种可能的最终结果 所以就本例而言 存在着如下五种可能的最终结果 但仅有一种实现 1 系统1单独被移交 即公司把根据合同1制造好的系统移交给招标部门 其概率记为P1 2 系统2单独被移交 其概率记为P2 3 系统3单独被移交 其概率记为P3 4 系统1与系统2共同被移交 其概率记为P4 5 没有系统被移交 因为该公司的投标全部被拒绝 其概率记为P5 四 随机网络应用示例 实现系统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 1 0 3 0 33 四 随机网络应用示例 但是反馈环仍然存在 合同1可以第二次修改 第二次修改的概率为 0 1 0 1 0 01第三轮投标又有0 3的被接受概率 于是投标1被接受的总概率变为 0 3 0 1 0 3 0 01 0 3 0 333 四 随机网络应用示例 反馈环 永远 存在 对合同1可以修改 无限多次 于是得到一个等比级数 其首项 0 3 其公比q 0 1 故该级数之和为