系统工程4-2离散事件仿真.ppt

4-2 离散事件系统仿真,离散系统基本概念 排队系统仿真 库存系统(随机存储系统)仿真,本讲主要内容,离散系统的状态只在离散时间点上发生变化。如，理发店里的人员、各类售票厅。 现实世界中的许多连续系统也可以通过抽象的方法来转化为离散系统中的事件。 离散系统具有随机性，其数学推导较难、甚至不可能，因此需要计算机仿真。随机微分方程,三个基本要素：实体、事件、活动 实体 分为临时实体(顾客)和永久性实体(服务员) 临时实体按规律不断产生，在永久实体作用下通过系统，最后离开系统。 事件 引起系统状态变化的行为。如，顾客到达售票窗口。 仿真中要建立事件表 (时间表) 。,基本概念,活动 两个可以区分的事件之间的过程。 进程 若干有序事件和若干有序活动组成，描述了事件和活动间的逻辑关系。,基本概念,顾客到达事件,服务开始事件,服务结束事件,排队活动,服务活动,进程,其它概念 仿真钟：可以是定步长，也可以是变步长。 计数器。,基本概念,排队系统是离散事件系统中的一种典型系统，如火车站的售票排队系统、工厂的加工系统，主要由提供服务者和被服务者组成，系统的主要功能就是服务，随机性是其固有属性，如被服务者的到达、服务时间的长短。故称其为随机服务系统。,排队系统的仿真,排队系统示意图,排队系统的仿真,排队系统的分类 按照三个部分来分类 顾客相继到达间隔时间的分布 服务时间的分布 服务台个数，有多个服务的系统示意图,排队系统的仿真,各种排队系统,排队系统的仿真,仿真研究排队系统统计性能（略） 稳定平均延误时间，Di为第i个实体的延误时间 平均滞留时间w， Si为第i个实体接受服务时间,排队系统的仿真,仿真研究排队系统统计性能（略） 稳态平均队长Q，Q(t)为稳态时第时刻的队列长度,T为系统运行时间。 系统中稳态平均实体数,排队系统的仿真,常用分布(到达模式，顾客到达的间隔时间) 泊松分布 满足三个条件： 不相重叠的时间区间内顾客到达数是独立的; 在充分小的时间内有一个顾客到达的概率与起始时间无关而于时间间隔有关; 在充分小的时间内有两个及以上顾客到达的概率极小，可以忽略不计。 概率分布,排队系统的仿真,负指分布 在输入是泊松分布时，它必然是负指分布 概率分布 泊松分布描述到达个体的，而负指分布描述各个个体到达时间。 爱尔朗(Erlang)分布 k个相互独立，具有相同参数的负指分布的变量的分布称为Erlang分布,排队系统的仿真,排队规则 损失制：若无服务机构，顾客离去，不等待。 等待制：根据服务规则的不同，有以下几类： 先进先出(FIFO)，先到先服务 后进先出(LIFO)，后到先服务 随机服务(SIRO) sequential-in-random-out 按优先级服务(PR) 最短处理时间优先(SPT),排队系统的仿真,排队规则 混合制：损失制和等待制的综合类型 限制队长的排队规则：设最大队长为N，若队长大于N，则顾客离去 限制等待时间的排队规则：设顾客排队等待时间最长为T，则等待时间大于T时顾客离去 限制逗留时间的排队规则：逗留时间包括等待时间和服务时间，若大于最长允许逗留时间，则顾客离去,排队系统的仿真,排队系统仿真建模： （1）仿真时钟的推进 面向事件的仿真时钟(事件调度法)：当某事件发生时，将仿真时钟推进到发生该事件的时刻并计算后继事件的发生时间；处理完当前事件后，从未来将发生的事件中挑选最早发生的事件，将时钟推进到该事件。以上过程不断重复。,排队系统的仿真,面向时间间隔的仿真时钟(固定增量推进法)，每次以固定的时间向前推进，扫描是否有事件发生。若有事件发生，则记录事件的时间参数。缺点：时间间隔较难确定。,排队系统的仿真,（2）三种建模策略 事件调度法(Event Scheduling)：按时间顺序确定并执行事件的发生，模型中有事件表（包含事件及其发生时间）、时间控制模块（从事件表中选择最早发生时间事件，推进仿真时钟到该事件发生时间，并调用相应的事件处理模块，处理完再返回时间控制模块）;,排队系统的仿真,活动扫描法 有时事件无法预测开始时间和结束时间，如系统的事件由硬件产生； 设置实体仿真时钟，记录事件的发生； 设置条件处理模块，测定活动发生条件是否满足；,排队系统的仿真,事件1,进程交互法(Process Interaction) 用进程表来描述事件和活动。 当前事件表：当前时刻能够执行的事件记录，但未判断时间发生的条件满足否，current event list 未来事件表：将来某时刻发生的事件记录,future event list 处理流程：对当前事件表中的事件进行判断，如果满足条件则进入相应的进程；不断地将未来事件移至当前事件表中。只有当前事件表中的事件全部处理完后才推进时钟。,排队系统的仿真,(3) 仿真流程图 以事件调度法 仿真模型为例,排队系统的仿真,仿真开始,初始化子模块,时间控制子模块,事件i处理子模块,Y,N,结果输出子模块,（4）仿真过程,排队系统的仿真,仿真过程(事件调度法),排队系统的仿真,队长：在调整仿真时间时统计出的到达时间小于仿真时间的客户数。 一些需要计算的统计数据 平均队长、最大队长 系统中平均客户数 平均等待时间、平均逗留时间 服务台总闲期 闲期所占比例 总服务顾客数,排队系统的仿真,库存（存储）系统： 水库的蓄水 工厂的原料存货 商店的商品库存 共性： 需求：系统的输出，包括间断需求、连续需求、确定性需求和随机需求 补充：系统的输入，补充策略根据系统的目标和需求方式来确定,库存系统的仿真,评价指标： （1）费用 保管费：还包括搬运、存储、损耗、保险以及利息损失 订货费：印花税、报关费、邮电费、车费、差费、文具用品费用等。 缺货损失费：机会成本损失；对于一些企业，会造成其它部门的待料损失；,库存系统的仿真,各种费用之间的关系（略） 存储费用，单位存储费用是常数c1，R为需求速度： 订货费用：单位费用递减,排队系统的仿真,（2）影响存货量的因素 平均消耗速度：单位时间的平均消耗量； 订货提前期：从订购到入库所需的时间； 最低存货量：为了安全生产用，以备采购延误或用量突增，也成安全库存； 订货点：存货至某一库存量时应订货的基点。平均用量输补时间+最低存量； 最高存货量：特定时间存货的最高限额，订购点+购买量,排队系统的仿真,研究目标： 订货点 订货量 库存统计 （3）分类 确定性：需求量以及需求的发生时间是确定的，订货及订货时间也都是确定的，运筹学教程中有。 随机性、不确定性,库存系统的仿真,随机性：各种情况出现的情况是不能预测的，但有一个概率分布，其概率分布是可知的，或可以近似地描述的。 不确定性：各种情况是不能预测的，也不能给出其概率分布。 经济学中有明确的区分。,库存系统的仿真,适用于仿真的库存系统类型 提前订货、延期交货模型； 货物的补充速度会变化的模型； 货物的价格变化的模型：涨价、折扣、季节性波动、其它波动。,库存系统的仿真,库存系统的仿真,例：多周期提前订货有折扣的存储系统仿真 （1）状态影响因素的确定 货物需求量为随机函数，其概率分布如下：,库存系统的仿真,订货提前期的函数为： 每次订货量Q150件可获得10%的折扣，价格函数(折扣)，T 为单位货物的价格，假设为10元，V为实际价格：,库存系统的仿真,缺货损失： 总的存储费用（每次直接订货费用F=100元，每件运费为0.05T）： 订货费用C1： C1=100+0.05TQ(订货费加运输费) 保管费用C2： C2=0.01VQ（每月保管费为货值的0.01） 缺货损失C3： C3=L （随机数） 每次订货总费用： C = C1 + C2 + C3 折扣节约,以上各随机变量的产生 生成一处于区间0,1或其它区间的随机数p，根据具体的开发平台不同而不同； 如果p小于等于1/10，则D=10； 如果1/10p3/10 (1/10+1/5=3/10)，则D=20; 如果3/10p7/10 (1/10+1/5+2/5=7/10)，则D=30; 如果7/10p9/10 (7/10+1/5=9/10)，则D=40; 如果9/10p1 (9/10+1/10=1)，则D=50; 同理可得，订货提前期和缺货损失的产生方法。 u1/8 ，B=1; 1/8u7/8 (1/8+3/4=7/8), B=2; 7/8u1