生产系统建模与仿真.ppt

电子科技大学工业工程系李海庆lihaiqing27 生产系统建模与仿真 生产系统模型 建模 仿真系统 模型 仿真 第一章序言 一 生产系统 1 1生产人们创造产品与提供服务的有组织的活动 它构成人类社会生存和发展的基础 从进行生产的过程来看 凡是将投入的生产要素转换为产出 有效产品和服务 的活动便可称为生产 狭义的生产 是指创造产品的活动广义生产 包括狭义生产与服务 1 2系统WayneC Turner Asystemcanbedefinedasasetofcomponentwhicharerelatedbysomeformsofinteraction andwhichacttogethertoachievesomeobjectiveorpurpose Introductiontoindustrialandsystemengineering 系统仿真的研究对象是具有独立行为规律的系统 所谓系统是指相互联系又相互作用着的对象的有机组合 从广义上讲 系统的概念是非常广阔的 大到无垠的宇宙世界 小到分子原子 系统的概念 对于一个系统来说 不论它是大还是小 都必然存在三个要素 即实体 属性和活动 所谓实体是指组成系统的具体对象 所谓属性是指实体所具有的每一项有效特性 所谓活动是指随着时间的推移 在系统内部由于各种原因而发生的变化过程 1 3生产系统任何系统都是由输入 输出及转换过程构成的 广义生产系统同样也是由输入 投入 输出 产出 及转换过程构成 将投入 转换及产出集成在一起 构成生产系统 生产系统是一个为了生产某一种或某一类产品 综合生产工艺 生产计划 质量控制 人员调度 设备维护 物料控制等各种技术为一体的复杂系统 投入是指生产与服务过程所要提供的各种生产要素 根据其在生产过程中所起的作用可分为 物质资源 生产活动 过程 中所用到的资金和物资 人力资源 生产过程所需要的劳动能 信息资源 生产过程中使用的信息资 管理资源 对生产过程进行的管理 产出可分为有形产出产品与无形产出 它们均应该是有效的 有形产出是指通过生产创造的实物产品 它是看得见摸得着的 汽车 电视机 手机等 无形产出是指服务作业提供的各种服务 它是不可触及的 如银行提供的金融服务 大学提供的教育等 转换过程是指将投入变成产出的过程 是企业生产与服务的主体 不同的生产与服务行业 其转换过程的特征不同 制造业主要涉及实物转换 由原材料变成成品 运输行业主要是完成位置的转移 通讯行业完成信息的转换 仓储行业完成物质的贮存和重新分配 医疗行业实现人的身体状况的转换 由病态到健康 学校实现知识的转换等 1 4系统性质自然vs 人造系统 Naturalvs Man made 静态vs 动态系统 Staticvs Dynamic 物理系统vs 抽象系统 physicsvs Abstract 开环vs 闭环系统 openvs Closed 一生产系统二模型 建模 三仿真四系统 模型 仿真 什么是模型 设备利用率 式中 设备利用率 在总时间段中 设备第i次被利用的时间 T 总时间段的时间值 设备利用率 在一个有效作业时间段中 设备的工作时间之和除以该时间段的总时间 模型 是对真实系统中那些有用的和令人感兴趣的特性的抽象化 注意 系统模型并不是对真实系统的完全复现 如果M能够用来回答关于系统 S 的问题 并且在精度范围A之内 那末M就是系统A的模型 建模的理由 减小风险了解和表示知识解释 Whatif 首先必须解 whatis 改进系统的日常运作 所要研究的系统 抽象Assumptionsaboutthenatureofthesystem Entity Entity Entity 模型 Relationships Relationships Relationships 所设想的行为 目标 性能度量 模型Models 一生产系统二模型 建模 三仿真四系统 模型 仿真 仿真的定义1961年G W Morgenthater 仿真意指在实际系统尚不存在的情况下对于系统或活动本质的实现 1978年Korn在 连续系统仿真 一述中将仿真定义为 用能代表所研究的系统的模型做实验 1984年Oren提出 仿真是一种基于模型的活动 被认为是现代仿真技术的一个重要概念 仿真是对真实世界的模拟 基本共同观点是 仿真是基于模型进行的 系统仿真的若干术语 为了了解系统仿真的基本方法 首先需要掌握与系统仿真有关的一些基本概念 1实体 指组成系统的物理单元 2事件 事件是描述系统的一个基本要素 事件是指引起系统状态变化的行为 系统的动态过程是靠事件来驱动的 事件一般分为两类 必然事件和条件事件 3成分 成分与实体是同一概念 只是根据习惯 在描述系统时用实体 而在模型描述中用成分 成分分为主动成分和被动成分 4进程 由若干事件与若干活动组成的过程称为进程 它描述了各事件活动发生的相互逻辑关系及时序关系 5仿真时钟 仿真时钟用于表示仿真事件的变化 在离散事件系统仿真中 由于系统状态变化是不连续的 在相邻两个事件发生之间 系统状态不发生变化 因而仿真时钟可以跨越这些 不活动 区域 6随机变量 复杂的现实系统常常包含有随机的因素 这些复杂的随机系统很难找到相应的解析式来描述和求解 系统仿真软件 1 AnyLogic2 Arena3 AutoMod4 eM Plant5 ExtendSim6 Flexsim7 witness8 乐龙 RaLC witness2006 一生产系统二模型 建模 三仿真四系统 模型 仿真五离散事件系统 系统 模型及仿真三者之间有着密切的关系 系统是研究对象 模型是系统抽象 仿真则是通过对模型的实验以达到研究系统的目的 根据仿真所依据的模型的不同 仿真可以分为物理仿真 数学仿真以及半实物仿真 根据仿真时钟与实际时钟的比例关系可分为 实时仿真 亚实时仿真以及超实时仿真 根据仿真所研究系统的不同 仿真可以分为连续系统仿真以及离散事件系统仿真 仿真模型还可以分为 确定性模型和随机性模型 物理仿真是按照实际系统的物理性质构造系统的物理模型 并在物理描写模型上进行实验的过程 数学仿真是在对系统进行抽象 并将其特性用数学关系式加以描述得到系统的数学模型的基础上 对数学模型进行实验的过程 数学仿真也称为计算机仿真 半实物仿真是数学仿真与物理仿真的结合甚至实物联合起来进行实验的过程 实时仿真 仿真时钟与实际时钟完全一致 也就是模型仿真的速度与实际系统运行的速度相同 当被仿真的系统中存在物理模型或实物时 必须进行实时仿真 例如各种训练仿真器就是这样 有时又称在线仿真 亚实时仿真 仿真时钟慢于实际时钟 对于仿真速度要求不苛刻的情况下均是亚实时仿真 例如大多数系统离线研究与分析 有时也称为离线仿真 超实时仿真 仿真时钟快于实际时钟 例如大气环流的仿真以及交通系统的仿真 连续系统仿真 系统状态随时间连续变化的情况 多数工程系统如机电 机械 化工 电力等系统 离散事件系统仿真 系统状态变化是离散的 多数非工程系统如管理 交通 经济等 确定型模型 在相同的输入状态下 系统所经历的任何时刻的状态都是相同的 其结果是一定的 随机型模型 在相同的输入状态下 系统所经历的任何时刻的状态都是随机的 其结果是不可预测的 仿真的目的 生产系统仿真的目的 1 优化 生产系统参数 操作工人 工作台数 缓冲区容量 2 预测 正常工作状态 3 计划与调度 4 系统性能的验证 交货期是否满足 一生产系统二模型 建模 三仿真四系统 模型 仿真五离散事件系统 5 1连续系统与离散事件系统 连续系统 其服从于物理学定律 电学 力学 热学 其数学模型可表示为传统意义上的微分方程或差分方程 其系统的状态变量随时间而发生连续变化 离散事件系统 DiscreteEventDynamicSystem DEDS DES 指系统的状态在一些离散时间点上由于某种事件的驱动而发生变化 其数学模型很难用数学方程来表示 时间离散时间连续而有离散事件 生产系统是DES系统 5 2离散事件系统基本概念 实体 构成系统的基本元素 是系统中有意义的一个物体 有些实体在整个仿真过程中始终存在 永久实体 有些实体在一部分仿真过程中存在 有进入 退出系统的情况 临时实体 属性 是指某一实体的特性 例如 在银行中 顾客是实体 其属性是帐户 事件 使系统状态发生变化的 实体的瞬间行为 注 事件还可能触发新的事件 DES中的事件具有三个特征 1 离散事件是导致DES状态发生跃变和触发新的离散事件的唯一因素 2 事件交互影响系统状态的变化 3 事件的发生时刻是异步的和不确定的 状态 系统全部实体的属性在某时刻t所取值的集合S t 定义为系统状态 即描述系统所用的变量集合 活动 活动持续一定时间 活动开始和结束将导致系统状态的变化 例如 等待活动 5 3DES系统举例 理发店 分析其实体 状态 事件 活动Answer 实体 顾客 服务员状态 服务员个数 顾客数 服务员忙闲事件 顾客到达 服务完毕活动 顾客等待 理发员服务 柔性制造系统 请分析其实体 状态 事件 Answer 实体 工件 加工中心事件 待加工工件 到达机床完成加工状态 各加工中心的繁忙程度各加工中心的等待队列活动 工件等待加工 课堂练习 1 急救室是否属于DES系统 分析其实体 状态 事件 2 银行系统是否属于DES系统 分析其实体 状态 事件 1基于框图的系统逻辑建模方法 1 框架 2 连线 3 菱形框 5 4生产系统仿真模型的建立 2基于Petri网技术的系统仿真建模方法Petri网基本构成 1 库所 2 变迁 3 流关系 有向弧 Petri网是对离散并行系统的数学表示 Petri网是1960年代由卡尔 A 佩特里发明的 适合于描述异步的 并发的计算机系统模型 Petri网既有严格的数学表述方式 也有直观的图形表达方式 既有丰富的系统描述手段和系统行为分析技术 又为计算机科学提供坚实的概念基础 由于Petri网能够表达并发的事件 被认为是自动化理论的一种 研究领域趋向认为Petri网是所有流程定义语言之母 经典Petri网经典的Petri网是简单的过程模型 由两种节点 库所和变迁 有向弧 以及令牌等元素组成的 Petri网的结构 1 Petri网的元素 库所 Place 圆形节点 变迁 Transition 方形节点 有向弧 Connection 是库所和变迁之间的有向弧 令牌 Token 是库所中的动态对象 可以从一个库所移动到另一个库所 2 Petri网的规则是 有向弧是有方向的 两个库所或变迁之间不允许有弧 库所可以拥有任意数量的令牌 3基于系统结构重现的系统仿真建模方法首先定义构成系统的基本单元模块 即系统的静态实体 如生产系统中的加工工位 检验工位 库存区域 搬运设备等 然后通过这些模块的动态实体所行进的路线进行定义 即生产系统中的生产工艺或系统中的各个模块之间的关联关系 最终形成构成系统整体的仿真模型 4 离散事件系统仿真步骤 1 问题的阐述2 设置目标及完整的项目计划 系统分析与描述 边界 约束 目标 3 建立系统的数学模型和收集数据4 编制程序 建立仿真模型 5 模型验证 verification 系统模型是否由准确地仿真模型 计算机程序 表示 方法 程序调试 程序逻辑流程图 6 模型确认 Validation 是否模型代表实际系统 试验设计生产性运行和分析文件清单和报表结果实现 仿真应用领域 生产系统 仿真应用领域 食品及服务领域 仿真应用领域 交通 仿真应用领域 化学工厂 呼叫中心 MotorolaDistributionCentre摩托罗拉分销中心 物流 第二章仿真用的概率概念 1随机变量 概率函数 随机数 2均匀的连续分布随机数及其生成 3各种离散分布随机数的产生 4非均匀的连续分布随机数及其产生 确定性活动与随机活动 确定性活动 是可以事先预言的 即在准确地重复一定的条件下 其变化的结果总是确定的 或者根据其过去的状态 相同的条件下可以预言将来的发展变化 我们把这一类活动称为确定性活动 确定性活动的主要特征是活动的运动可以用一个确定的数学形式来描述 f t 或是数学函数 或是数学图表等 随机性活动 其变化的结果是事先不可预言的 即在相同的条件下进行重复实验 每次结果未必相同 或者是知道其过去的状况 在相同的条件 未来的发展事先都不能确定 这一类活动我们称为随机性活动 随机性活动的主要特征是这类活动的描述可以通过数学统计的方法描述 对于随机性活动进行研究所利用的数学工具是概率论及数理统计对于实际系统中随机活动进行研究时 往往由于众多的随机因素使得数学描述和分析变得十分困难 这时我们往往求助于计算机仿真 仿真为这类复杂的随机系统的研究提供了一个方便有效的手段 离散型随机变量定义 定义 对于随机活动的不同结果我们可以用不同的数值与其对应 这样 就可以用一个变量来描述随机活动 变量按一定的概率取某个值对应于随机活动按一定的概率取某个结果 这类变量称为随机变量 离散型随机变量 若随机变量只取有限个数值或可列无穷多个数值 则称此类随机变量为离散型随机变量 连续型随机变量 若随机变量可以取值于某个区间中的任一数 我们称为连续型随机变量 离散型随机变量数学定义 数学定义 如果一个随机变量x的一切可能取值为x1 x2 xn 并且X取值xn的概率为Pn 则X为一个离散型随机变量 p1 p2 pn 称为X的概率函数 其中Pn必须满足下列两个条件 1 2 离散型随机变量概率分布函数 离散型随机变量X的累积分布函数定义 当X小于或等于某个给定值x的概率函数 记为P X x F x 设随机变量X可能取值x1 x2 xn 则X的累积分布函数为其中为X取值的概率 由定义可见当x y时 F x F y 即F x 是个单调增加的函数 连续型随机变量定义 定义 若存在非负函数f x 使得随机变量X取值于任一区间 a b 的概率为P a x b 则称X为连续型随机变量 f x 称为X的密度函数 对于密度函数f x 有 连续型随机变量概率密度函数 连续型随机变量的累积分布函数定义为随机变量小于或等于x的概率 它用F x 表示 即由累积分布函数定义可知 当时 累积分布函数是单调递增函数 概率密度函数 累积分布函数 随机变量X落入区间 a b 内的概率是 图中给出了一个连续随机变量的密度函数曲线和累积分布函数曲线 密度函数f x 的值不能为负 要注意的是f x 的值可以大于1 但是在任意区间 a b 上由f x 曲线围出的面积 图中阴影部分 必然 1 从图中也可以看到累积分布函数F x 的值随x值的增加而增加 而且它最终趋向极限值1 随机变量的数字特征 定义 随机变量的数字特征是与它的分布有关的某些数值 例如平均值 最大可能值等 它们反映了随机变量某些方面的特征 分类 根据随机变量的种类 分别介绍离散型随机变量的数字特征 连续型随机变量的数字特征 离散型随机变量的数字特征 平均值 设X为离散随机变量 其概率函数由下表给出 其中记 称为X的平均值 数学方差 数学方差反映了各个随机变量的采样值偏离平均值的平均程度 变化系数 标准差与平均值的比值 反映了随机数偏离平均值的变化程度 变化系数 连续型随机变量的数字特征 平均值 设X为随机变量 其概率密度函数为f x 则该随机变量的平均值m为 平均值又称为数学期望 数学方差 变化系数 标准差与平均值的比值 反映了随机数偏离平均值的变化程度 变化系数 数学方差反映了各个随机变量的采样值偏离平均值的平均程度 随机变量的其它数字特征 模值定义为随机变量的概率密度函数在某处取峰值时的x值 当有多个峰值时 取最大峰值作为模值 中间值 如果有一点Xm 随机变量有一半值将落在这一点以下 那么由此点所定义的值Xm称为中间值b中间值可以从累积分布函数曲线上求得 因为它是F x 0 5处的那个点 在x 1处时f x 均达到峰值 则x 1就是随机变量的模值 中间值 Xm 1 6783469 数理统计中的基本运算规则 X一随机变量 则E X E X X Y为两个相互独立的随机变量 则E X Y E X E Y X一随机变量 则D X 2D X X一随机变量 则D X D X X Y为两个相互独立的随机变量 则D X Y D X D Y 0 1 均匀分布随机数 随机数 所谓随机数就是随机变量的样本取样值 均匀分布的随机数 随机变量x在其可能值范围中的任一区间出现的概率正比于此区间的大小与可能值范围的比值 0 1 均匀分布随机数 在各种分布的随机数中 最常用和最重要的是在 0 1 区间上的均匀分布随机数 其他许多分布的随机数都可以由 0 1 均匀分布随机数经过变换和计算来产生 0 1 均匀分布随机数的定义 0 1 均匀分布随机变量x的概率密度函数为累积分布函数 0 1 均匀分布随机数的说明 随机变量x落入区间 X1 X2 中的概率等于图中阴影区的面积 其值为 X2 X1 正比于区间 X1 X2 的大小 需要说明的是在计算机上表示连续变量只能是近似的 因为计算机中的数字只能是有限的位数 如果变量变化的最小步长可以达到计算机表示的最小值 并且在实际需要的精度之内变量可以达到任意值 就可以把这个变量看成是连续的 0 1 均匀分布随机数的产生方法 物理过程 常用的物理装置有放射粒子计数器 电子管随机数产生器 利用电子噪声或放射源去激励一个周期为0 9的计数器 对计数器定时选行采样就可以得到所需的随机数的一位数 多次重复此过程或者利用几个计数器同时运行 就可以得到任意位数的随机数 随机数表 利用物理过程可以得到大量随机数 并将这些数制成表 在使用随机数时就可以依一定的顺序从表中取出随机数 为了适应实际需要的位数 对取出的随机数可以进行截断或拼接处理 随机数产生程序 按照一定的算法计算出具有类似于均匀分布随机变量的独立取样值性质的数 因为这些数是按照定性的算法计算出来的 会有一定的周期性 因而被称为伪随机数 由于我们的目的是利用随机数来对随机活动的统计分析 只要伪随机数的数理统计性质能够满足实际需要就可以了 这些数理统计性质包括均匀性 独立性等 一般计算机上 产生随机数的函数为 0 1 均匀分布的随机数 计算机产生随机数的算法 用计算机程序通过计算产生的随机数都是伪随机数 它具有一定的周期性 计算机产生随机数的特点 实用性强 简单易操作 产生速度快 计算机存储空间的要求低 计算机上用数字方法产生的随机数的一般要求有 1 产生的数值序列要具有分布的均匀性 抽样的随机性 试验的独立性以及前后的一致性 2 产生的随机数要有足够长的周期 以满足你真的实际需要 3 产生随机数的速度要快 占用的内存空间要小 计算机产生随机数的算法 计算机产生随机数的通常方法是利用一个递推公式 给定了k个初始值 就可以利用这个递推公式推算出第k 1个数Xk 1 递推公式有多种形式 其中最常见的有两种 平方取中法 同余法 平方取中法 这是最早产生随机数的一种方法 一个二进制n位数X 自乘后一般得到一个2n位数X2 设平方后得到 取X0中间的n位数 设n为偶数 作出如下的二进制n位数 重复上述过程 可得二进制n为数序列 令 则 就是所需要的 0 1 均匀分布随机数序列 平方取中法 步骤 任取一十进制正整数 确定一偶数位数n 将所选十进制数化为n位的二进制数 平方运算得到2n位的二进制数 取2n位二进制数的中间n位作为生成的随机数 生成的随机数 上一随机数 否 是 随机数进入循环 平方取中法 例题 任取一正整数 45表示为偶数位的二进制数 101101 共6位该数的平方为 011111101001 共6 2 12位取中间的六位 得 111101 该数的十进制表达式为61 最终可以产生的随机数 45 61 17 36 34 16 32 0 问题 应用平方取中法时 可能遇到 退化 的危险 即出现中间所取得值都为0 或形成重复循环序列的现象 平方取中法的限制 同余法 同余法是将一组数据通过一系列特定的数字运算 最后利用一个数字的整除求余 所得的数值就是一个伪随机数 因为这个计算过程 则称该求随机数的方法为同余法 同余法的有三种 加同余法 乘同余法和混合同余法 其中以混合同余法产生的随机数统计性质较好 因而获得了最为广泛的应用 同余法具有计算简便的优点 产生随机数的递推公式是 其中a称为乘法因子 c称为加法因子 M为模数 为随机数的周期 当a 1时 加同余法 当c 0时 乘同余法 当a 1 c 0时 混合同余法 0 1 均匀分布随机数的产生 当给定了一个初始值X0之后 就可以利用上式计算出序列X1 X2 Xn 再取于是y1 y2 yn就是所需要的 0 1 均匀分布得随机序列 同余法产生 0 1 均匀分布的随机数例题 设a 5 c 3 M 8 取X0 1 则循环叠代式 利用上述叠代式 可以计算得到 X1 0 X2 3 X3 2 X4 5 X5 4 X6 7 X7 6 X8 1 X9 0 y1 0 000 y2 0 375 y3 0 250 y4 0 625 y5 0 500 y6 0 875 y7 0 750 y8 0 125 X9 0 000 我们可以看到此例中 这个随机数序列的周期长度为8 即Xn 8 Xn 很明显 利用同余法产生随机数序列的周期不可能超过所取的模数M值 适当的a c和X0的值 就可以使随机数序列的周期充分地长 以满足实际的需要 若利用组合的同余法产生随机数序列 则可获得大于模数的周期 同余法产生 0 1 均匀分布的随机数产生的基本条件 c和M互质 即没有大于1的公因子 M的每个质数因子也是a 1的因子 若4是M的因子 则4也是a 1的因子 上述基本条件满足后 混合同余法所产生的随机数序列的周期达到最大值M 各种离散分布随机数的产生 在生产系统离散仿真时 我们常常使用离散分布的随机变量来描述实际系统中的某些量 例如在企业原材料管理系统中 在一定时间内 到达仓库的物料数就是一个离散随机变量 该随机变量的到达时间是一个随机数 此随机数满足一定的概率分布 我们可以利用 0 1 均匀分布随机数来产生各种离散分布的随机数 离散分布的随机数可以分为 均匀分布的离散随机数 非均匀分布的离散随机数 均匀离散分布的随机数的产生 给定N个连续整数x1 x2 xN 我们以相等的概率从中选出一个数 这样重复下去 所产生的数列就是一个离散均匀分布的随机数序列 每次取样值 式中yk是 0 1 均匀分布的随机数 产生 0 1 均匀分布的随机数 选定产生均匀分布随机数的范围 x1 xN 非均匀离散分布的随机数的产生 给定N个x1 x2 xN 我们以相对应的概率P1 P2 PN 满足 从中选出一个数作为输出 这样重复下去 所产生的数列就是一个离散非均匀分布的随机数序列 非均匀离散分布的随机数的产生方法 设所求非均匀离散分布随机数的累积概率分布函数为F x 其中 F 0 F0 0 Fk k 1 2 N 设yi是一个 0 1 均匀分布随机数 考察yi 如果 则把相应的xk选出作为此次取样的输出值 生成n个 0 1 均匀分布的随机数 若随机数yi值 Fk 1 Fk 取xk 数xk服从特定分布 例贝努利概率模型二项分布的产生 贝努利 Bernouli 概率模型是概率统计中一种最简单而又常用的概率模型 它由一系列试验组成 其中每次试验只有两种结果 我们用事件A和A 来表示这两种实验结果 若A产生的概率为P A P 0P 则认为A 事件发生 二项分布 在由n次独立试验组成的贝努利概率模型中 事件A发生的次数 是一个随机变量 它取值k k 1 2 n 的概率是当P较大而计算精度又要求较高时 我们可以在计算机上用n次贝努利试验产生二项分布的随机数 生成n个 0 1 均匀分布的随机数 统计n个随机数中数值大于某一个概率值P的个数m 数m服从贝努利分布 泊松分布 若进行n次独立试验 在每次试验中事件A发生的概率等于Pn 则在n次试验中事件A发生k次的概率 n Pn 0 nPn 趋于P k 称为泊松 Poisson 分布 在泊松分布的试验中 试验的次数n越大 则越接近泊松分布的值 非均匀的连续分布随机数及其产生 对于非均匀的连续分布的随机数 我们同样借助于 0 1 均匀分布随机数进行变换或计算来产生 一般采用的变化方法为1反函数法 逆变法 2函数变换法3卷积法 反函数法 逆变法 反函数法也称为概率积分变换法 这种方法所基于的原理是概率积分变换定理 可以简述如下 1给定 0 1 均匀分布随机数yn n 1 2 如果F 1 yn 是随机变量X的反累积分布函数 则由公式2xn F 1 yn 所计算的随机数就是随机变量X的取样值 反函数法 逆变法 的步骤 求出y F x 的反函数 x F 1 y 利用 0 1 均匀分布随机数产生程序取得yn 利用x F 1 y 可得到需要的随机数xn 指数分布 指数分布的概率密度函数是累积分布函数为生成随机数的逆函数为图中取 0 5 练习 请符合Weibull分布的随机变量 离散随机变量 练习 函数变换法 正态分布 正态分布的概率密度函数为对于此式要直接求F 1 y 是很困难的 可利用坐标变换等方法 令x x1 就可以将上式化成标准正态分布N 0 1 设u1和u2是两个独立的 0 1 均匀分布随机数 利用坐标变换及积分变换可得均值 2 方差 0 3 卷积法 convolution Forsomeintractabledistributions wecanexpresstherandomvariateasthesumoftwoormorerandomvariates 爱尔朗分布 概率密度函数为对于这种分布 不能直接利用反函数法 而是利用其一个特性 即一个平均值为T的k级爱尔朗分布的随机数等价于k个独立的并且具有平均值为T k的指数分布随机数之和 所以 k 0 9 图中取 0 5 k 1 5 k 3 计算Erlang分布 Ex m 2 1Selecttworandomnumbers u1 2 u2 4请符合该分布的随机变量x X 1 2ln 2 4 1 26 其它分布 韦伯分布 概率密度函数为分布函数为利用反变换可得其中u是 0 1 均匀分布随机数 4 2f x 4 2F x 对数正态分布 设 是具有平均值 和方差 2的正态分布的随机变量 则y ex为具有对数正态分布的随机变量 其概率分布密度函数为这一分布在经济学中得到广泛的应用 由于它和正态分布密切相关 随机数的简单算法如下 1 判断 0 否则出错 2 由标准正态分布N 0 1 取值Y 3 计算Y Y 4 计算X eY 即为一次对数正态分布的X取值 伽玛分布Gamma 伽玛分布的概率函数为 伽玛分布Gamma 伽玛分布具有一种特性 x1 x2 xn是取自G i 的一个独立随机数变量序列 则取自G 其中若 i 1 则X将是n个独立的指数随机变量之和 根据这一特性可用于生成具有伽玛分布的X 其算法如下 1 判断 0 0 否则出错 2 0 X 取整 3 从均值为1的指数分布生成V 4 X V X 5 若 1 则 X X 并作为伽玛分布的一次取值 6 1 转至第3步循环直至 1 贝塔分布Be 贝塔分布的概率函数为利用概率理论可以证明 若Y1和Y2是独立地从伽玛分布G 1 和G 1 分布中取值 则X Y1 Y1 Y2 即为Be 贝塔分布中取值 贝塔分布Be 的随机数产生 可得如下一种贝塔分布生成算法 1 判 0及 0 否则出错 2 从G 1 分布中取值Y1 3 从G 1 分布中取值Y2 4 算出X Y1 Y1 Y2 作为一次贝塔分布Be 的取值 随机数产生方法的比较 用反函数法产生随机数时 需要对给定的分布密度函数f x 进行积分求得F x 然后再对累积分布函数求反函数F 1 y 这些变换处理往往比较困难 有的还不可能做到 而舍去法只用到了密度函数f x 所以比较方便简单 舍去法的缺点是效率低 每产生所需分布的一个随机数至少要产生两个 0 1 均匀分布的随机数 而且还有相当一部分的随机点被丢弃了 丢弃的个数与接收的个数之比等于f x 之上部分的面积与f x 之下的面积之比 随机数的统计检验 用任何一种方法产生的随机数序列在把它用到实际问题中去之前都必须进行一些统计检验 看它是否能够令人满意地作为随机变量的独立取样值 显著性检验 是否有较好的独立性和均匀性 从理论上说 统计检验并不能得出完全肯定的结论 但是却可以使我们有较大的把握获得具有较好统计性质的随机数序列 数字特征检验 数字特征检验是采样平均值 方差与理论平均值 方差差异的显著性检验 在 0 1 区间上均匀分布的随机变量X和X2的平均值及方差分别为 数字特征检验 如果N个随机数x1 x2 xN是X的N个独立观测值 令则它们的平均值和方差为 数字特征检验 根据中心极限定理 渐近地服从正态N 0 1 当N足够大 故当给定显著性水平后 即可根据正态分布表确定临界值 据此判断与X的平均值E X 和与的平均值E X2 之差异是否显著 从而决定能否把x1 x2 xN看作是 0 1 均匀分布随机变量X的N个独立取样值 分布均匀性检验 分布均匀性检验又称频率检验 是对经验频率和理论频率之间的差异进行检验 把 0 1 区间划分成k等分 以 i 1 2 k 表示第i个小区间 如果xs是区间 0 1 上均匀分布的随机变量X的一个取样值 则xs值落在任一小区间的概率Pi均应等于这些小区间的长度1 k 故xsN个值落在任何一个小区间的平均数 设实际上x1 x2 xN中属于第i个小区间的数目为ni 则统计量渐近地服从自由度为K 1的分布 由的值可以衡量实际频率与理论频率的差异 也就是可以度量实际随机数分布的均匀程度 当两者完全符合时 0 问题 的值处在多大范围内可以认为的随机数抽样值是符合均匀性要求呢 首先确定一个判定标准 称为显著度 并且根据参数 的值 称为自由度 k 1 从表中查得的值 如果计算所得到的值小于 就认为符合均匀性假设 因为它符合下式 如果 0 05 则上式表示的概率为0 95 也就是说 对给定显著度 而言 可以认为这一随机数样本是均匀的 通常可取 0 05 0 1 独立性检验 一个随机数序列可以是均匀分布 但却不一定是独立的 也就是说有可能是互相关联的 两个随机变量得相关系数反映了它们之间的线性相关程度 如果它们相互独立 那么它们的相关系数应为0 反之不一定 所以其值大小可以衡量相关程度 这里对独立性检验主要是对随机数序列中相隔一定间隔的数之间的相关系数进行检验 独立性检验 设给定N个随机数x1 x2 xN 我们计算前后距离为K的样本相关系数rK k 1 2 式中为随机数的方差 为随机数的平均值 独立性检验 如果各xi相互独立 则相关系数rK应为0 在原假设rK 0之下 当N充分大 例如N K 50 时 统计量渐近地服从正态分布N 0 1 同时选定 0 05 则根据概率统计理论 当 U 196时 称为差异显著 拒绝假设rK 0 反之 则接受 第三章排队系统的建模与仿真 内容 第二节到达时间间隔和服务时间的分布 第三节排队系统的分析 第四节排队系统的仿真 第一节排队论的基本概念 仿真的目的 生产系统仿真的目的 1 优化 生产系统参数 操作工人 工作台数 缓冲区容量 2 预测 正常工作状态 3 计划与调度 4 系统性能的验证 交货期是否满足 排队系统仿真初始条件 系统中没有顾客 即 排队的队列中没有顾客等待 服务台无服务对象 仿真开始 以第一个顾客到达时刻为仿真的起始点 第一节排队论的基本概念 一般来说 当某个时刻要求服务的对象数量超过服务机构能够接受服务的容量时 就会出现需求服务对象等待服务的排队现象 随机状态一般难以用一种确定的函数关系来表述系统的特征 因此 仿真在对排队系统的分析中就可以发挥其作用 平衡状态 1提高服务质量 减少被服务对象等待服务的时间 2降低成本 在保证设备利用率的前提下减少设备的投入 3 1 1排队系统的组成 一般的排队系统都有三个基本组成部分 1 到达模式 2 服务机构 3 排队规则 排队系统的一般模型 通过已知的到达模式和服务时间的概率分布来研究排队系统的平均队列长度和服务机构的 忙 与 闲 的程度 即服务效率 这就是离散事件仿真所需要解决的问题 3 1 2到达模式 1 平均到达间隔时间考虑模型的总时间T中 共到达n个动态实体的情况下的比值 2 平均到达速度单位时间内到达的动态实体数量 平均到达速度是平均到达间隔时间的倒数 3 到达间隔时间的分布函数到达间隔时间的分布函数指到达间隔时间大于t的概率 到达间隔时间的累积分布函数F t 的定义是到达间隔时间小于t的概率 4 到达时间变化系数到达时间变化系数指到达间隔时间的标准差与平均到达间隔时间的比值 变化系数是无量纲的值 它描述了数据围绕平均值的分散程度 顾客到达系统的模式常用实体到达时间间隔的概率分布表示 一般服从泊松 possion 分布 3 1 3服务机构 1 平均服务时间考虑模型的总时间T中 服务机构共服务个动态实体的比值 2 平均服务速度单位时间内服务的动态实体数量 平均服务速度是平均服务时间的倒数 3 服务时间的分布函数服务时间的分布函数指服务时间大于t的概率 服务时间的累积分布函数的定义是服务时间小于t的概率 4 服务时间变化系数到达时间变化系数指服务时间的标准差与平均服务时间的比值 单队列单服务台SQSS系统模型单队列多服务台SQMS系统模型多队列单服务台MQSS系统模型多队列多服务台MQMS系统模型 单队列单服务台SQSS系统模型 顾客到达事件处理流程 服务完毕事件处理流程 单队列多服务台SQMS系统模型 顾客到达事件处理流程 服务完毕事件处理流程 多队列单服务台MQSS系统模型 顾客到达事件处理流程 服务完毕事件处理流程 多队列多服务台MQMS系统模型 遵守两条重要规则1 当有多个服务台空闲时 要有服务台选择算法 2 当所有队列均不为空时 才可开始服务 多队列多服务台MQMS系统模型 服务完毕事件处理流程 3 1 4排队规则 动态实体到达系统后 按照一定的次序和规则接受服务 系统处于 忙 时动态实体进入队列有三种处理方法 1 损失制 2 等待制FIFO LIFO GIRO PR 3 混合制N 队列长度阀值 q 队列实际长度时 顾客进入队列 反之顾客直接离去 或使用逗留系统时间T作阀值 T是等待时间和服务时间之和 排队系统的队列是一个不确定量 如果该队列是一个随机变量 即队列的特符合一定的统计规律 队列的特性是通过队列的统计量进行描述 服务机构的业务量强度 动态实体的到达平均速度与动态实体得到服务的平均速度之比 3 1 5队列的度量 实际业务强度 动态实体实际到达速度 即到达的动态实体都能够得到服务的数量为依据 为以及得到服务的到达速度为 此时的实际业务强度永远小于或等于1 服务设备利用率 得到服务的动态实体的到达速度与服务速度之比 多服务设备系统的设备并联环节中 对于队列的度量 通常考虑两个统计量 1 队列的长度 2 排队的时间统计这两个量 计算出其均值 方差 最大值 最小值等 3 1 5排队模型的分类 根据排队系统的三个主要特征 肯道提出一个分类方法 它只针对并列的服务设备的情形 用的标志性符号形式是 X Y Z m NX 表示动态实体相继到达系统间隔时间的分布 Y 表示服务时间的分布 z 表示并列的服务设备数量 m 顾客源总数N 系统内顾客的容量表示相继到达间隔时间和服务时间分布的典型符号有 M 负指数分布 Markov D 确定性 Deterministic K阶爱尔朗 Erlang 分布GI 一般相互独立的随机分布 GeneralIndependent 的随机分布 G 一般随机分布 General 第二节到达时间间隔和服务时间的分布 顾客到达和离开分别构成排队系统的输入与输出过程流 到达分布和离开分布确定了到达系统和离开系统的顾客数这两个随机变量的分布 求解排队系统有关数量指标问题 首先要确定顾客到达流的概率分布 即在一定的时间间隔内来个顾客的概率是多大 其次是要确定顾客离开流的概率分布 即在一定的时间内服务完个顾客的概率是多大 实际问题研究中 可根据原始资料测算顾客在单位时间平均到达流的经验分布 然后按照统计学的方法 例如 检验法 确定资料适合于哪种理论分布 并估计理论分布的参数值 这是确定排队模型的前提 3 2 1到达的规律 3 2 2服务的规律 3 2 2定长分布 每个动态实体在相同的间隔时间到达 或每个动态实体的服务时间是常数 动态实体接受服务的时间分布为 动态实体接受服务的时间分布为 3 2 3泊松分布 在排队论中 最基本的排队模型是在给定时间内到达系统的顾客数服从泊松分布 即顾客到达流是泊松流 也称最简单流 它具有如下性质 1 平稳性 在时间 t t t 内 有k个动态实体到来的概率与时刻起点t无关 而只与 t k有关 记此概率为 2 无后效性 在时间 t t t 内到达n个顾客的概率与起始时刻之前到达多少个顾客无关 3 普通性 对于充分小的时间间隔 t 在时间t t内最多有一个顾客到达系统 即在时间t t内有2个或2个以上顾客到达的概率极小 有 满足上述条件的到达分布称为泊松到达分布 其到达时间分布函数与服务时间分布函数均可满足负指数分布 其中E T I D T 1 3 2 3爱尔朗分布 爱尔朗分布比负指数分布有更大的适应性 k 1时 爱尔朗分部实际就是负指数分布 当k增大时 爱尔朗分布的图形逐渐变为对称型的 变化系数减小 也就是说 这时的爱尔朗分布曲线族表示的数据 要比用指数分布表示的曲线更接近平均值 当k 30时 爱尔朗分布近似于正态分布 例如 串行的k个服务台 每台服务时间相互独立 服从相同的负指数分布 那么以动态实体走完这k个服务台总共需要的服务时间就服从k阶爱尔朗分布 3 2 4其它随机分布 1一般相互独立随机分布2一般随机分布3正态分布 3 3排队系统的分析 排队系统运行情况的分析 就是在给定输人与服务条件下 通过求解系统状态为n 有n个顾客 的概率Pn 再进行计算其主要的运行指标 排队系统的主要数量指标 描述一个排队系统运行状况的主要数量指标有 1 队长和排队长 队列长 队长是指系统中的顾客数 排队等待的顾客数与正在接受服务的顾客数之和 排队长是指系统中正在排队等待服务的顾客数 队长和排队长一般都是随机变量 2 等待时间和逗留时间从顾客到达时刻起到他开始接受服务止这段时间称为等待时间 等待时间是个随机变量 从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间 也是随机变量 3 忙期和闲期忙期是指从顾客到达空闲着的服务机构起 到服务机构再次成为空闲止的这段时间 即服务机构连续忙的时间 这是个随机变量 是服务员最为关心的指标 因为它关系到服务员的服务强度 与忙期相对的是闲期 即服务机构连续保持空闲的时间 在排队系统中 忙期和闲期总是交替出现的 4 数量指标的常用记号 1 主要数量指标Ls 平均队长 即稳态系统任一时刻的所有顾客数的期望值 Lq 平均等待队长 即稳态系统任一时刻等待服务的顾客数的期望值 Ws 平均逗留时间 即 在任意时刻 进入稳态系统的顾客逗留时间的期望值 Wq 平均等待时间 即 在任意时刻 进入稳态系统的顾客等待时间的期望值 2 其他常用数量指标s 系统中并联服务台的数目 平均到达率 1 平均到达间隔 平均服务率 1 平均服务时间 N 稳态系统任一时刻的状态 即系统中所有顾客数 U 任一顾客在稳态系统中的逗留时间 Q 任一顾客在稳态系统中的等待时间 服务强度 即每个服务台单位时间内的平均服务时间 般有 s 这是衡量排队系统繁忙程度的重要尺度 当 趋近于0时 表明对期望服务的数量来说 服务能力相对地说是很大的 这时 等待时间一定很短 服务台有大量的空闲时间 如服务强度 趋近于1 那么服务台空闲时间较少而顾客等待时间较多 我们一般都假定平均服务率 大于平均到达率 即 1 否则排队的人数会越来越多 以后总是保持这个假设而不再声明 在系统达到稳态时 假定平均到达率为常数 平均服务时间为常数1 则有下面的李特尔公式 Ls WsLq WqWs Wq 1 Ls Lq 3 3 1M M 1模型 模型的条件是 1 输入过程 顾客源是无限的 顾客到达完全是随机的 单个到来 到达过程服从普阿松分布 且是平稳的 2 排队规则 单队 且队长没有限制 先到先服务 3 服务机构 单服务台 服务时间的长短是随机的 服从相同的指数分布 例2某医院急诊室同时只能诊治一个病人 诊治时间服从指数分布 每个病人平均需要15分钟 病人按泊松分布到达 平均每小时到达3人 试对此排队队系统进行分析 解对此排队队系统分析如下 1 先确定参数值 这是单服务台系统 有 故服务强度为 2 计算稳态概率 这就是急诊室空闲的概率 也是病人不必等待立即就能就诊的概率 而病人需要等待的概率则为 这也是急诊室繁忙的概率 3 计算系统主要工作指标 急诊室内外的病人平均数 急诊室外排队等待的病人平均数 病人在急诊室内外平均逗留时间 病人平均等候时间 4 为使病人平均逗留时间不超过半小时 那么平均服务时间应减少多少 由于代入 3 解得 5 平均服务时间为 15 12 3min即平均服务时间至少应减少3min 5 若医院希望候诊的病人90 以上都能有座位 则候诊室至少应安置多少座位 设应该安置 个座位 加上急诊室的一个座位 共有 1个 要使90 以上的候诊病人有座位 相当于使 来诊的病人数不多于 1个 的概率不少于90 即 两边取对数 x 2 lg lg0 1因 1 故所以 6即候诊室至少应安置6个座位 M M C C 2 是多服务台的等待制排队系统 它的各种特征的规定和假设与M M 1模型基本相同 并假定C个服务台并联排列 各服务台独立工作 其平均服务率相同 即 1 1 C 因此 该系统的平均服务率为C 在统计平衡状态下 服务强度 此时 系统的稳态概率为 3 3 2M M C模型 M M C模型主要指标为 平均队列长Lq 平均队长Ls Ls Lq C 患者在系统中平均逗留时间Ws 患者在队列中平均等待时间Wq 3 3 3M M c和M M 1模型的比较 3 4排队系统的仿真 排队系统的仿真模型 整个有效的到达率必须小于平均的服务速度 否则等待线将无限的增长 即 爆炸性 或不稳定 时间的发生引起系统状态的瞬时变化 在单通道排队系统中只有两个可能的时间影响系统的状态 一是动态实体达到系统事件 二是动态实体离开系统事件 这两类事件按时间顺序随机出现 为了产生到达间隔时间 一组均匀分布的随机数是必须的 随机数有如下特性 1 随机数集合在0和1之间均匀分布 2 相邻的随机数是独立的 排队系统仿真主要取决于两个独立事件 1 顾客到达系统的间隔时间 2 顾客到达系统后被服务的时间 手工仿真步骤 1 确定仿真的每个输入的特征 2 构造一个仿真表 3 对每一重复运行i 为每一组由p个输入产生一个值 并评价其功能 计算响应yi的值 事件何时出现 在仿真中 通过随机数来产生 Step1 确定输入数据的特征 到达事件 统计特性 假定 到达事件 顾客到达间隔时间为1 8分钟的均匀分布到达 产生的0 1之间的均匀分布随机数 到达事件的产生 服务事件 统计特性 服务事件 服务时间为1 6分钟 其概率为0 10 0 20 0 30 0 25 0 10 0 05 产生的0 1之间的均匀分布随机数 服务事件的产生 Step2 构造仿真表 Step3 重复运行