Logistics0901v3ppt课件.ppt

9 设施布置软件 仿真与数字化工厂 对一个复杂的实际系统 人们通常采用什么方式研究 布局 大小 扩大或新建引进新设备的事先评价 瓶颈 性能 场地规划和人员配置 新的瓶颈口 效果 生产效率改善问题 投入的产品组合 设备故障 加急生产 系统 仿真的意义 Logistics0901 01主体库作业仿真 对实际系统进行真实的物理试验很困难或者跟踪记录试验数据难以实现时 仿真技术就成为必不可少的工具 由于 等原因 安全 经济 技术 时间 董邵华 物流系统仿真 北京邮电大学出版社 2008 5 顾启泰 离散事件系统建模与仿真 清华大学出版社 1999 JerryBanks Discrete EventSystemSimulation 离散事件系统模拟 清华大学出版社 1988 王红卫 建模与仿真 科学出版社 2002 利用模型对实际系统进行试验研究的过程 或通过建立和运行实际系统的仿真模型 来模仿系统的运行状态和规律 以实现在计算机上进行试验的全过程 什么是系统仿真 系统模型实验 系统仿真 系统 定义 相互联系且相互作用的对象 实体 的有机组合 生产系统 人 设备 工件等 系统特征均由一些相关的实体组合而成实体具有自身的特征 属性 状态量 系统通常是动态的 其变化过程称为活动 活动 通过消耗资源 改变实体属性 9 1仿真及示例 系统按状态变化方式分类 连续系统 系统状态量随时间连续变化 其数学模型为微分飞机速度 v 0 a t或差分方程 xn 闭室降温 Tn Tn 1 VC Tn T0 vCTn Tn 1V T0v V v 离散事件系统 系统的状态量在一些离散时间点上由于某种事件的驱动而发生变化 其数学模型很难用数学方程来表示 而用流程图或者网络图描述 哈罗德 Harrod R H 经济增长模型 设St为t期储蓄 Yt为t期国民收入 It为t期投资 s称为边际储蓄倾向 即平均储蓄倾向 0 s 1 k为加速系数 离散事件系统 排队系统 举例 仿真方法 手工仿真仿真初始条件 系统中没有顾客 即 排队的队列中没有顾客等待 服务台无服务对象 仿真开始 以第一个顾客到达时刻为仿真的起始点 服务台 排队队列 排队系统 顾客总体 服务员 等待线 模型 实体 顾客 服务员状态 系统中的顾客数 服务员忙闲事件 到达事件 离开事件 完成服务 活动 服务 事件何时出现 在仿真中 通过随机数来产生 Step1 确定输入数据的特征 到达事件 统计特性 假定 到达事件 顾客到达间隔时间为1 8分钟的均匀分布到达 产生的0 1之间的均匀分布随机数 到达事件的产生 服务事件 统计特性 服务事件 服务时间为1 6分钟 其概率为0 10 0 20 0 30 0 25 0 10 0 05 产生的0 1之间的均匀分布随机数 服务事件的产生 Step2 构造仿真表 Step3 重复运行 仿真结果计算 顾客的平均等待时间 顾客的等待概率服务员空的概率平均服务时间 医院急救室家乐福超市生产系统 判断下列系统是否属于离散事件系统 若是 指出下列系统中的实体 属性 活动 事件以及状态 9 2离散事件系统仿真 离散事件系统要素 输入 事件 实体1 资源 活动 输出 活动 活动N 实体1 资源 实体M 资源 控制1 控制1 控制1 系统 边界 改变参数 系统变量 描述系统 实体 特征的各种指标或性能 常常随时间的变化而变化 参数 表征各种系统变量的值 系统的状态 某个指定的时刻 系统中所有系统变量的值的集合 在模拟过程中 我们在不同时刻都要对系统的状态进行统计 这里系统的状态是指系统中所有变量值的全体 而不是一部分变量的值 比如 理发馆系统中系统状态应是在某一时刻系统中所有变量的值的集合 包括理发员的状态 排队长度 每一顾客的到达时间 对每一顾客的服务时间 模拟时钟的值 因此 在模拟中一提到 系统的状态 总是指某一具体时刻 在这一具体时刻 所有系统变量的值的集合就是系统在这一时刻的状态 离散系统描述 离散事件系统特点 状态仅在离散时间点上变化 且离散时间点一般不确定面向事件 反映系统各部分相互作用的一些事件 模型为反映事件状态的数集 仿真结果是产生处理这些事件的时间历程 实体 系统中与研究目的有关的人 物 设备 设施等组成系统的元素称为系统的 实体 永久实体 永久驻留在系统中 是系统处于活动的必要条件 如服务员临时实体 仅在系统中存在一段时间 按一定规律到达 如顾客关系 临时实体按一定规律不断产生 在永久实体作用下通过系统 最后离开系统 事件 在某个时刻 系统状态变化的行为 称为一个事件 不引起系统状态变化的行为是不能成为 事件 的 离散事件系统本质是由事件驱动的例 顾客到达事件使服务员状态由闲到忙 或使队列长度加1事件的发生一般与某一类实体相联系 放在事件表中管理 事件表通常记录事件类型 发生条件 时间及相关实体的有关属性 活动 指实体持续了一段时间的行为 活动的开始或结束的瞬间都是事件 导致系统状态变化活动表示两个可区分事件之间的过程 标志着系统状态的转移如顾客到达事件与顾客开始接受服务事件之间为一活动 使服务员忙及队列长度减1 进程相当于系统的子集或子系统 包含若干个事件及活动 并且描述了其所包含事件及活动间的逻辑关系和时序关系如某一顾客在系统中的全部活动为一进程 事件 活动 进程的关系图 仿真时钟 模拟模型中表示时间的变量称为 模拟时钟 模拟时钟与一般时钟是不同的 模拟时钟是给模型的模拟过程记时的 因此它走的快慢是由模型所确定的时间单位和记时办法来决定的 在离散事件系统仿真中有两种不同的时钟推进方式 面向事件的仿真时钟和面向时间间隔的仿真时钟 不是仿真运行过程所占用的计算机的CPU时间不同仿真系统的时间单位是不同的 对排队系统进行仿真时 其时间单位可能是分钟 而对宏观经济系统的仿真 随机离散事件的发生时间可能是以月或年来表示的 面向事件的仿真时钟 仿真时钟并不是连续地向前推进 而是按照下一个事件预计将要发生的时刻 以不等距的时间间隔向前推进 也就是说 模拟钟并不是一分一秒地运行的 而是以某个事件的发生来驱动的 仿真时钟每次都跳跃性的推进到下一事件发生的时刻 面向时间间隔的仿真时钟 根据模型的特点确定时间单位 仿真时钟按很小的时间区间等距推进 每次推进都要扫描所有的活动 以检查在这时间区间内是否有事件发生 若有事件发生则记录这一时间区间 从而得到有关事件的时间参数 这种推进方式要求每次推进都要扫描所有正在执行的活动 一般说来 面向事件的仿真时钟多用于离散事件系统仿真 面向时间间隔的仿真时钟既用于离散事件系统仿真 又可于连续系统仿真 它们的主要差别在于仿真效率的不同 仿真时钟特点 离散事件动态系统的状态本来就只在离散时间点上发生变化 因而不需要进行离散化处理 离散事件系统一般不以时间推动 但事件间有时序关系 仿真中仍必须有控制时间的部件由于引起状态变化的事件发生时间的随机性 仿真钟的推进步长则完全是随机的两个相邻发生的事件之间系统状态不会发生任何变化 因而仿真钟可以跨过这些 不活动 周期 仿真钟的推进呈现跳跃性 推进速度具有随机性 统计计数器因固有的随机性 某一次仿真运行得到的状态变化过程只不过是随机过程的一次取样 离散事件系统的仿真结果只有在统计意义下才有参考价值在仿真模型中 需要有一个统计计数部件 以便统计系统中的有关变量 如排队系统中的顾客等待时间 队列长度等 9 3系统仿真步骤 1 系统建模 一般用流程图描述 反映临时实体在系统内部历经的过程 永久实体对临时实体的作用及相互间逻辑关系 明确仿真目的 目的决定模型正确描述系统识别实体描述实体属性和仿真参数实体属性 加工时间及其分布 仓储能力 队列长度等仿真参数 仿真时间长度绘制流程图 反映临时实体在系统内部历经的过程 永久实体对临时实体的作用及相互间逻辑关系 例 某公司生产某种产品批量为200件 可在一天完成 生产每批产品的准备成本为1000元 每件产品每天的存储成本为1元 假设该产品每天的需求符合在区间 20 40 之间的均匀分布 最初该产品的初始库存量为90件 则用仿真的方法来分析100天内该产品的累积生产量和累积库存量的变动情况 生产的EOQ 200仓库的EOQ 150 库存系统仿真的目的 用仿真的方法一般不能直接得到使库存费用最小的订货批量和订货周期 它只能对给定的多组参数 评价哪一种更好 或采用试算和人机交互的方法求最优解 最大库存小成本小 1 库存系统的基本参数需求速率 随机库存量平均库存 最高库存 最低库存订货量订货提前期 随机库存费用 2 库存系统的要求 约束无缺货 零提前期有提前期 允许缺货非瞬时到货数量折扣等 库存系统 2 确定仿真算法确定仿真建模策略面向时间的仿真 等时间步长面向事件的仿真 事件表面向进程的仿真 为每个实体建立一个进程 反映其从开始到结束的全部活动 产生随机变量 仿真系统最常见的两类随机变量1 临时实体到达系统的时间2 永久实体的完成服务时间它们属于仿真系统的参数和实体的属性 在仿真之前必须确定它们服从哪种概率分布 常用的概率分布包括 定长分布指数分布正态分布一般随机分布 统计分布 随机变量与随机数 定长分布 到达时间 和 或 服务时间 为常数如 企业对原料供应实现准时供货 JIT 仿真系统按供应计划规定的时间和品种 产生临时实体 随机变量与随机数 当服务时间完全随机时 可以用指数分布表示 可理解为单位时间内事件发生的平均数 指数分布 指数分布的概率密度函数是累积分布函数为图中取 0 5 泊松分布 若进行n次独立试验 在每次试验中事件A发生的概率等于Pn 则在n次试验中事件A发生k次的概率 n Pn 0 nPn 趋于P k 称为泊松 Poisson 分布 在泊松分布的试验中 试验的次数n越大 则越接近泊松分布的值 正态分布 当 服务时间 近似于常数 且上下波动时 可以认为它服从正态分布 一般随机分布 如果不能用某个典型分布表示 服务时间 和 到达时间 必须用观察 统计的方法求概率分布 随机变量与随机数 一般随机分布 随机数 在 0 1 之间的随即采样值特点 均匀性和独立性常用的产生办法平方取中法线形同余法 随机数的产生 N台设备的随机选择 平方取中法 这是最早产生随机数的一种方法 一个二进制n位数X 自乘后一般得到一个2n位数X2 设平方后得到 取X0中间的n位数 设n为偶数 作出如下的二进制n位数 重复上述过程 可得二进制n为数序列 令 则 就是所需要的 0 1 均匀分布随机数序列 X0 5497 X02 54972 30217009X1 2170R 0 2170 X12 21702 4708900X1 7089R 0 7089 同余法 同余法是将一组数据通过一系列特定的数字运算 最后利用一个数字的整除求余 所得的数值就是一个伪随机数 因为这个计算过程 则称该求随机数的方法为同余法 同余法的有三种 加同余法 乘同余法和混合同余法 其中以混合同余法产生的随机数统计性质较好 因而获得了最为广泛的应用 同余法具有计算简便的优点 产生随机数的递推公式是 其中a称为乘法因子 c称为加法因子 M为模数 为随机数的周期 当a 1时 加同余法 当c 0时 乘同余法 当a 1 c 0时 混合同余法 0 1 均匀分布随机数的产生 当给定了一个初始值X0之后 就可以利用上式计算出序列X1 X2 Xn 再取于是y1 y2 yn就是所需要的 0 1 均匀分布得随机序列 三 仿真中随机数和随机变量值的产生例 x0 27 a 17 c 43 m 100 x1 17 27 43 mod100 2R1 2 100 0 02x2 17 2 43 mod100 77R2 77 100 0 77x3 17 77 43 mod100 52R3 52 100 0 52 随机变量与随机数 随机变量与随机数 非均匀的连续分布随机数及其产生 对于非均匀的连续分布的随机数 我们同样借助于 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 y 1递增 x F x 分布 0 1 指数分布 指数分布的概率密度函数是累积分布函数为生成随机数的逆函数为图中取 0 5 函数变换法 正态分布 正态分布的概率密度函数为对于此式要直接求F 1 y 是很困难的 可利用坐标变换等方法 令x x1 就可以将上式化成标准正态分布N 0 1 设u1和u2是两个独立的 0 1 均匀分布随机数 利用坐标变换及积分变换可得均值 2 方差 0 3 查表法 一般随机分布插值R f x X 三 仿真中随机数和随机变量值的产生逆变换法 指数分布设x服从指数分布 密度函数 分布函数 令 随机变量与随机数 三 仿真中随机数和随机变量值的产生查表法 一般随机分布插值R f x X 随机变量与随机数 3 建立仿真模型定义状态变量 定义系统事件及有关属性 活动及进程 设计仿真钟的推进方法等 4 仿真程序设计及运行 在没有集成的仿真工具之前 仿真系统的建模和仿真实验 都需要通过编制计算机仿真程序实现 仿真语言或高级语言长期运行或多次运行不同的仿真策略决定了如何建模 如何编程 目前所有的仿真工具也都是以这些仿真策略为基础开发出来的 仿真程序的总框图 1 输入仿真参数仿真的结束条件系统结构实体属性原发事件表 后续事件表 事件分类等 2 初始化程序仿真钟初始化系统状态初始化 终态仿真 稳态仿真 各种统计计数器置零产生第一个原发事件 3 时间控制子程序 固定增量或事件步长推进仿真时钟到下一个时刻查 原发事件 表 确定该时刻的原发事件及其类型 4 原发事件处理程序每一类事件都有相应的处理程序修改系统状态修改累计统计值判断并执行后续事件处理程序 5 仿真策略 5 1 事件调度法 以事件来控制仿真过程时间控制程序从时间表中选择最早发生的事件调用该事件相应的处理程序及后续处理程序时间控制程序再将仿真时钟推进到下一个事件发生的时刻 重复上述过程 直到仿真结束 5 2 活动扫描法 以活动来控制仿真过程列出所有实体对应的活动列出所有活动发生的条件 包括时间条件 仿真时钟按固定增量推进 同时扫描所有的活动 激活所有满足条件的活动调用所有激活活动的处理程序 改变系统状态重复直到仿真结束 5 3 进程交互法 以进程来控制仿真过程它以临时实体为对象 建立 进程表 设置 当前事件表 用于纪录当前时刻应该发生的所有事件 设置 未来事件表 纪录其余事件 推进仿真时钟 扫描 未来事件表 将该时刻所有应该发生的事件移到 当前事件表 将 当前事件表 中的事件 与 进程表 进行匹配 激活满足条件的进程 并调用相应的处理程序 将进程结束的位于 当前事件表 中的事件删除 推进时钟 重复执行直到结束 5 仿真结果分析统计结果 可信度分析等 9 4仿真数据分析与模型验证 仿真数据分析仿真模型的验证与分析 没有可信度的模型和仿真系统毫无意义 甚至会导致错误的决策 我们如何向别人证明我们的建模与仿真工作是值得信赖的 是有价值的呢 至少要在二个层面上说明我们的工作值得信赖 才可以得到认可和信任 仿真工作才可以 验收 实际系统 系统模型 仿真模型 认可 信赖 等价 可信 正确 可信 1 2 validation verification accreditation 什么是输出分析 为什么要进行输出分析 输出分析的两种状态 确定的输入激励一个确定的系统 得到的输出就是一个确定的输出 通过一次确定的仿真便可得出解 随机的输入激励一个随机的系统 得到的输出是 输出的表达形式如何 需要经过多少次的仿真才能说明输出结果 输出分析的目的在于预测一个系统的性能 或比较两个或多个不同系统设计的性能 估计系统的性能参数 以及性能参数估计的有效范围 用仿真统计得到的 作为观察值的估计量 统计得到的方差S2就是估计量的偏差范围 或确定出达到给定精度所需的观察次数 在离散事件仿真中 大多数仿真输出数据呈现出自相关的特征 即 前面的输出往往会影响到后面的输出数据 如 库存系统中的初期库存 生产系统中的初始状态 排队系统中初始排队状态和初始服务状态等 仿真数据分析 假设系统性能可用参数 或 表示 系统仿真的目的是 通过仿真 希望得到表示系统性能 或 的值 如何得到或统计得到此值 我们可以运用参数的估计方法 既要得到这个值 点估计 又要得到这个值的精度范围 区间估计 区间估计的范围 或长度 是点估计准确度的一个测度 性能测度估计的方法 点估计 离散随机变量 基于数据 Y1 Y2 Yn 的 的点估计定义为式中是基于样本量n的样本均值 如果的数学期望是 即则是 的无偏估计 称为离散仿真系统性能的平均测度 点估计 连续随机变量 基于数据 Y t 0 t T 的 的点估计定义为式中T是仿真的运行长度 称为Y t 在 0 T 上的时间平均值 称为连续仿真系统性能的平均测度 是 的无偏估计 区间估计 首先 确定在无偏估计下 估计点估计 或 的方差 令表示点估计的真实方差令表示基于数据 Y1 Y2 Yn 的方差的估计值 假设B称为在方差估计中的偏差系数 如果是近似无偏的 B 1 0 那么取统计量 根据数理统计的定理 可知 统计量 当B 1 为点估计方差的一个无偏估计 终态 terminating 仿真在模型中明确地规定了仿真开始和结束条件的仿真 这些条件是目标系统实际运行模式的反映 即仿真模型可在某个定义好的规则或是条件下终止 稳态 steady state 仿真对于数量的估计是建立在长期运行的基础上的 理论上运行时间是趋于无穷的 通常很多物流系统都是由初始状态慢慢到达一个稳定的状态 而稳态仿真所关注的就是这个稳定的状态 系统划分 终态仿真数据分析 独立重复运行法 一个终态仿真 它在仿真时间区间 0 TE 中运行 并由此得到观察值Y1 Y2 Yn 样本量n可以是固定数 也可以是随机变量 终态仿真的目的是估计 设仿真共重复R次 每次运行都利用不同的随机数流和独立选择的初始条件 也包含所有含有相同初始条件的情况 令Yri是第r次重复运行的第i次观察i 1 2 n 以及r 1 2 R 样本均值 样本偏差 样本偏差估计值 在100 1 的信赖度下 的信赖区间为 t x x 假设需要求得ATM取款机的利用率和顾客取款的时间周期 仿真5次 得到仿真结果如下 求拥有95 1 2 2 5 信心的ATM利用率和顾客平均取款周期的置信区间 经过仿真后ATM利用率的估计值为 经过仿真后ATM利用率的变异量估计值为 查表可知 2 78 拥有95 信心的ATM利用率的置信区间为 经过仿真后顾客平均等待时间的估计值为 经过仿真后顾客平均等待时间的变异量估计值为 查表可知 2 78 拥有95 信心的顾客平均等待时间的置信区间为 对非中断系统来说 为了观察系统长期的特性 考虑将仿真时间设定为0至无限长 仿真一次 产生 无限多个观察值 其期望值为 稳态仿真可以分为两个阶段 第一阶段为仿真过渡期 时间由0到 这一时期为系统由初始状态到稳定状态的过渡时期 叫预热期 这一时间段不需收集仿真数据 第二阶段为系统的稳态阶段 该阶段时间在 之间 这一阶段为仿真数据的收集阶段 假设预热期得到d个观察值 则单次仿真点估计 可定义为 仿真统计值的变异量为 在100 1 的置信度下 的置信区间为 以ATM取款机为例 假设做了10次仿真试验 每次仿真针对顾客平均等待周期收集了11个观察值 如下表所示 去除第一个观察值 顾客平均等待时间的稳态仿真结果为 3 907 0 0058 2 26 3 907 2 26 0 0058 3 907 2 26 0 0058 95 的信赖区间为 顾客平均等待时间的变异量为 查表得 两系统比较分析 以 表示不同系统的平均等待时间 其中 经过仿真后 方案一的取款人平均等待时间为 方案二的平均等待时间为 假设需要对这两个方案进行比较 常用的方法是对 的差异进行分析 也就是求得 的点估计与信赖区间 表示不同的系统设计方案 在100 1 的置信度下 的置信区间为 1 若 的信赖区间完全落在零点左方 则有充分证据说明 0 即有充分信心说明 2 若 的信赖区间完全落在零点右方 则有充分证据说明 0 即有充分信心说明 3 若 的信赖区间包括零点 则则没有充分证据表示两系统 之间有明显差异 仿真模型的验证与分析 1 VV A的基本概念2 VV A的一般原则英文关键词Verification 验证 校验 Validation 确认Accreditation 认定 验收 Certification 鉴定 1 模型X的Validation是指 对模型X的行为准确度 Accuracy 的评估 即模型X的行为足够准确地表达了对象系统 即源系统 的行为吗 所回答的问题是 是否生成了能够被认可的等价的模型X 模型X确认的参照物是源对象系统 实际系统或设计的系统 的行为 2 模型X的Verification是指 对模型X的变换准确度 Accuracy 的评估 即由模型X 变换成模型X时 这种变换准确吗 回答的问题是 是否正确地由X 生成了X 模型X验证的参照物是X的前驱X Validation和verification是在二个基本层面上的可信性证明工作 1 建立的模型和仿真系统是符合实际的 即 模型在研究目的允许的范围内等价地代表了已存在的实际系统或规划设计的未来系统 模型与要研究的系统逻辑等价 2 建立的仿真模型是正确的 即建立的仿真模型 所写的计算机程序是正确的 在一定程度上实现了本来想要建立的模型的目的 计算机建模本身正确 3 Accreditation 美国防部 DoD 的M S小组定义为 官方鉴定 一个模型 仿真或二者共同对用户的特定用途是可接受的 4 Certification 建模与仿真的确认与验证技术及方法分类 应用于贯穿整个建模与仿真过程的V V技术可粗略分为四大类 非正式方法正式方法静态方法动态方法 1非正式方法 非正式方法 在VV A中最常用 是正规的指导下的非常有效的方法 但它的缺点是严重依赖于人的推理与主观判断 如 审核法 如领域专家审核过程检查法 如程序员自查表面验证法 直观上认为合理图灵测试 判断仿真与实际系统的差别以检验仿真 图灵测试 英国数学家阿伦 图灵1950年提出了一个测试标准 来判断电脑能否被认为是 能思考 是不是具备人类智能的方法 这个测试被称为图灵测试 现在已被多数人承认 被测试的有一个人 另一个是声称自己有人类智力的机器 测试时 测试人与被测试人是分开的 测试人只有通过一些装置 如键盘 向被测试人问一些问题 这些问题随便是什么问题都可以 问过一些问题后 如果测试人能够正确地分出谁是人谁是机器 那机器就没有通过图灵测试 如果测试人没有分出谁是机器谁是人 那这个机器就是有人类智能的 图灵测试用于仿真确认与验证 图灵测试通过比较被仿真的实际系统和仿真之间的差别 判定仿真的正确性 其方法是 将两组在相同的输入条件下产生的输出数据提供给同行专家 其中一组来自仿真系统 另一组来自实际系统 请专家指出两者的差别 如果专家无法区分两者的差别 模型的可信度就增加了 如果他们能够区分两者差别 则要他们描述区别在哪里 专家的反应提供了关于仿真表示的正确性和适当性的信息 2正式方法 正式方法 是基于正确性的正式的数学证明 但由于当前的正式证明技术的局限性 在略为复杂的实际建模与仿真中还无法应用 如 归纳推理逻辑演绎正确性证明谓词运算谓词变换 3静态方法 静态方法 评估静态模型设计和源代码 不需要模型的机器执行 需要手工执行 应用广泛 静态技术可以校核验证大量信息 如模型结构 建模技术 模型中的数据 控制流和语法精度等 如 结构分析因果图数据流分析语法分析语义分析控制分析 4动态方法 动态方法 需要模型执行 大多数动态方法需要加入模型探测器 即在执行模