离散事情系统的建模与仿真.ppt

《离散事情系统的建模与仿真.ppt》由会员分享，可在线阅读，更多相关《离散事情系统的建模与仿真.ppt（59页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、离散事件系统的建模与仿真,机电工程学院飞行器工程系 系统与仿真实验室 单家元 博士,11 离散事件系统建模与仿真,离散事件系统的数学描述方法 排队服务系统的数学建模 存储系统的数学建模 离散事件系统的仿真原理 随机数与随机变量的生成 排队服务系统的仿真 存储系统的仿真,11.1 离散事件系统的数学描述方法,离散事件系统的描述要素 实体：系统的具体对象 事件：引起系统状态变化的行为 活动：表示两个可以区分的事件之间的过程。标志状态的转移。 进程：描述系统所包含事件及活动间的相互逻辑和时序关系。,11.1 离散事件系统的数学描述方法,离散事件系统的数学模型 利用随机过程理论和概率理论对离散事件系统

2、诸要素的数学描述。其是一个离散的数集。 形式化描述：M=(X,Y,S,ta)。 这里：X 外部事件（输入事件）；Y输出事件，S序贯状态；状态转移函数；输出函数和ta时间推进函数。,11.1 离散事件系统的数学描述方法,进程,排队活动,服务活动,顾客到达事件,服务开始事件,服务结束事件,离散事件系统中的实体、事件、活动和进程,实体：顾客、服务台,11.2 排队服务系统的数学建模,排队服务系统的概念 定义： 由一个或多个服务台构为随机到达的顾客提供某些服务，而顾客视服务台的闲、忙，并按其排队律被服务或者等待的系统叫排队服务系统。 组成： 顾客源、排队结构、服务机构,顾客源,顾客源,顾客源,服务规则

3、,排队规则,到达模式,离去,11.2 排队服务系统的数学建模,排队服务系统的基本要素 到达模式： 描述顾客随机到达服务机构要求某种类型服务的的随机分布模式。为系统输入，用随机到达时间表示。 分布特性：定长分布、泊松分布、爱尔朗分布、指数分布 排队规则 先到先服务：FIFO 后到先服务：LIFO 优先服务律：优先级 随机律：同等机会，随机抽取 其它：到超时、超长离去,11.2 排队服务系统的数学建模,排队服务系统的基本要素 服务机构： 提供特定类型服务的一定数量的服务台之间的配置形式：并行（单对多服务）、串行（单对单服务）或其它。 服务过程 为各个顾客服务要花费时间而形成的服务过程。描述服务过程

4、的统计特性：服务时间 分布特性：定长分布(D)、爱尔朗分布(Ek)、负指数分布(M)、一般随机分布(GI),11.2 排队服务系统的数学建模,排队服务系统的模型分类和表示 分类：按照排队系统的三大组成要素（到达时间分布X、服务时间分布Y、服务台数目Z），进行分类。 表示：X/Y/Z。D/M/1 M负指数分布 D定长分布 EkK阶爱尔朗分布 GI独立的随机分布,11.2 排队服务系统的数学建模,排队服务系统的建模方法 到达模式的数学模型 定长分布：顾客在等距离时间间隔到达。,11.2 排队服务系统的数学建模,排队服务系统的建模方法 到达模式的数学模型 泊松分布：顾客在给定时间长度为t的时间内发生

5、有n个到达的概率。,11.2 排队服务系统的数学建模,排队服务系统的建模方法 到达模式的数学模型 指数分布：其累积函数为 若随机数y为均匀分布，则到达时间为,11.2 排队服务系统的数学建模,排队服务系统的建模方法 到达模式的数学模型 爱尔朗分布：其密度函数为 到达分布函数为,11.2 排队服务系统的数学建模,排队服务系统的建模方法 服务过程的数学模型 定长的服务时间。一般情况 随机分布：一般按指数分布。特殊情况可按爱尔朗分布或超指数分布。 正态分布：密度函数为,11.2 排队服务系统的数学建模,排队服务系统的建模方法 排队律的数学模型 先到先服务：服务首先提供给等待时间最长的顾客。 后到先服

6、务：服务首先提供给最后到达的顾客。 优先服务律：中断或强占服务。服务提供给优先级最高的顾客。 随机律：对所有等待的顾客进行随机选择服务。 其它：到超时、超长离去,11.2 排队服务系统的数学建模,排队服务系统的建模方法 建模关键 通过大量观测数据获得概率分布函数 借助该函数描述到达模式和服务过程,11.2 排队服务系统的数学建模,排队服务系统的建模实例 防空导弹武器系统的排队问题 防空导弹具有火力的自动化指挥控制系统。自动完成发现跟踪目标、目标识别及飞行参数计算、目标威胁判断及火力分配。火力分配后，不再对各通道进行火力控制，各火力单元自行进行射击诸元计算并发射和制导导弹。 模型类型：串联服务排

7、队系统：即串联服务台：自动化指控系统、发射单元。 描述： 来袭敌机：服从最简单流（来袭敌机的逗留时间较短）。为为常数的平稳泊松分布。 服务时间的分布：指控系统和射击诸元所需时间服从指数分布规律。,11.3 存储系统的数学建模,存储系统的基本概念 需求：存储的输出。间断的或连续均匀的；确定的或随机的。 补充：存储的输入。生产或订货。但需要时间。 费用：各种消耗费用。存储费h、订货费S、生产费c、缺货费d。 存储策略 循环策略：每隔t0时间进行补充存储量Q。 (x,S)策略：每当x=S时补充存储量Q=S-x。 混合策略：每隔t0时间检查存储量，然后实行(x,S)策略,11.3 存储系统的数学建模,

8、存储系统的基本概念 需求率：单位时间内需要的物品数量。r(t) 订货点：订货的规定存储量。p 订货量：一次订货的物品数量。q 订货周期：相邻两次订货的时间间隔。Ti,11.3 存储系统的数学建模,存储系统的数学建模 存储系统建模的目标：订货与库存费用最小。问题：何时订货和订货量多少。 模型类型： 确定性存储模型： 随机性存储模型：,11.3 存储系统的数学建模,确定性存储系统的数学建模 模型1：确定性需求，不允许缺货。假定： 需求率R、订货费S、存储费h为常数； 拖后时间L=0（立即补充）； 不容许缺货； 订货周期为T，每次订货量Q为常数。 建模过程： 确定费用函数C(T)：T时间内的平均费用

9、： C(T)=C1/T+C2RT/2 C1为订货费用，C2为存储费用 最优存储策略：求T使C(T)最小。对C求导。得,11.3 存储系统的数学建模,确定性存储系统的数学建模 模型2：生产需要一定时间，确定性需求，不允许缺货。假定条件同1，但生产需要一定时间。 建模：按照上述同样方法进行。P为订货点（规定存储量）。,11.3 存储系统的数学建模,确定性存储系统的数学建模 模型3：确定性需求，允许缺货。假定：除在单位时间内短缺的单位数量的物品，需要支付短缺费d外，条件件同1。 建模：按照上述同样方法进行。C3为单位缺货费用。当C3远远大于C2时，下式变为模型1。,11.3 存储系统的数学建模,确定

10、性存储系统的数学建模 模型4：离散需求的存储模型。假定：需求时间为离散，单位时间内需求次数为n。需求量为a。 建模目标：确定一次订货的最优数量Q=Ka，使单位时间内的总存储费用C(K)最小。 建模： 单位时间总需求量：na; 最大存储量：(K-1)a; 订货周期：T=Ka/na=K/n 总存储费用： C(K)=h*a(K-1)/2+Sn/K (K为正整数),11.3 存储系统的数学建模,随机存储系统的数学建模 随机变量：需求率R、拖后时间L、订货量Q、订货周期T。 确定订货点：假定各单位时间内的需求量Ri是独立同分布的，分布函数为F(x)，分布密度函数为f(x)，正态分布N(S,)。 拖后时间

11、为已知正整数 L期间的需求量：RL=R1+R2+Ri，而Ri服从正态分布，RL为F(x)的n次卷积，则 。 风险水平为a的订货点R0:,11.3 存储系统的数学建模,随机存储系统的数学建模 确定订货量 若订货周期T为随机变量（概率分布为G(t)），则在t时间内需求次数n(t)服从泊松分布，在需求量Y(T)为：,11.3 存储系统的数学建模,随机存储系统的数学建模 单周期随机存储模型 需求量R为随机变量，F(r),f(r)。条件：一次订货。问题：确定最优订货量使总损失的期望值最小。订购费与订货量无关。订货量大于需求量，则付损失费，否则付短缺费。,11.4离散事件系统的仿真原理,基本概念 实体：临

12、时实体（某个顾客）、永久实体（服务台） 事件：事件表（记录事件的发射时间、事件类型、参与的实体及其相关属性） 活动：状态的变化。 进程：事件及活动的逻辑与时间关系。 仿真时钟：随仿真进程的时间推进机制。 随机性：推进步长随机 跳跃性：时钟推进是跳跃的,11.4 离散事件系统的仿真原理,基本原理 仿真机制： 面向事件的仿真机制事件调度法：事件安排和时间推进。在“产生事件、安排事件、时间推进、处理事件、再产生新事件”中进行循环。 面向活动的仿真机制活动扫描法：对所有部件进行扫描，判断活动是否发生，要看是否满足条件，其中时间条件优先。 面向进程的仿真机制进程交互法：综合了前两种仿真机制，采用了两个事

13、件表（当前事件表和将来事件表）,11.4 离散事件系统的仿真原理,仿真流程管理 仿真时钟 时间步长法：下一个最早发生的事时间的时间来推进。 事件步长法：面向时间间隔的推进方式：以固定的时间间隔等距推进。 事件表：按照事件出现的时序，列入事件表。 同时事件管理 同类同时事件管理。由排队规则处理该类事件 混合同时事件管理。 一步法：直接确定同时事件所形成的结果状态。 解结法：分解为单独事件序列来处理。,11.4 离散事件系统的仿真原理,单服务台排队系统：两种事件（顾客到达、顾客离去） 第i个和第i-1个顾客到达的时间间隔：A1=15,A2=32,A3=24,A4=40, 服务台为第i个顾客服务的时

14、间长度：S1=43,S2=36,S3=34,S4=28, 系统初始状态：第i个事件发生时的队伍长度qi取q00；第i个事件发生时服务台状态zi取z0=0表示空闲。 仿真初始时钟：TIMEb0=t0。bi为第i个顾客到达事件，ti为第i个事件发生的时间。 Ci为第i个顾客离开系统的时间，Di为第i个顾客排队等待的时间。,11.4 离散事件系统的仿真原理,单服务台排队系统(仿真时钟推进机制),t0,t1,t2,c1,t3,t4,c3,t5,A4,A3,A2,A1,b0,b1,b2,b3,b5,b6,b7,b8,D3,D2,S1,S2,S3,c2,t,b4,b事件发 生时间,顾客等待时间,s服务处理

15、时间,A顾客到达时间间隔,c顾客离去时间,A5,t顾客到达时间,q0=0 z0=0,q1=0 z1=1,q2=1 z2=1,q6=1 z6=1,q5=0 z5=1,q4=1 z4=1,q3=0 z3=1,q7=0 z7=1,q8=1 z8=1,11.5 随机数与随机变量的生成,均匀分布随机数生成 均匀分布随机数概念： （a,b）均匀分布：概率密度函数： （0,1）均匀分布,11.5 随机数与随机变量的生成,均匀分布随机数生成 均匀分布随机数生成方法 表格法：将采用某种手段生成的随机数以表格形式存入计算机仿真时调用。消耗内存，浪费时间 物理法：物理随机数发生器。无法重复 移位法：采用移位寄存器产

16、生。 数学方法：伪随机数 按照一定算法（递推公式），自动生成。 给定种子，多次调用，生成随机数序列。,11.5 随机数与随机变量的生成,均匀分布随机数生成 常用随机数发生器 平方取中法 倍积取中法 同余法 加同余 二次同余 线性同余,11.5 随机数与随机变量的生成,均匀分布随机数生成 线性同余法 递推公式：,11.5 随机数与随机变量的生成,均匀分布随机数生成 线性同余法 特点： Xn位于0,m-1区间，un位于0,1区间 适当选择m,a,c，可使xn产生循环，循环周期为T。若T=m，则称为满周期。 适当选择m,a,c，可保证xn在0,m-1区间上的均匀性。即一个周期内每个正整数只出现一次。

17、,11.5 随机数与随机变量的生成,随机数发生器的性能检验 均匀性检验：频率检验， 检验法 假设H0：u1,u2,是独立同分布U0,1随机变量 将0,1区间分成m个互不相交的子区间i-1/m,i/m 落在每一个子区间上的随机数个数的理论值i为n/m 统计实际落在子区间上的随机数个数n 构造统计量 判定原假设是否成立。设置信水平为a，若下式成立，则H0成立，否则，拒绝H0。,11.5 随机数与随机变量的生成,随机数发生器的性能检验 独立性检验：相关系数检验法 相关系数定义 给定显著水平a，计Z1-a为N0,1上的1-a临界点。则当下式成立时，接受独立性假设。,11.5 随机数与随机变量的生成,随

18、机变量的生成 反变换法： 基本原理：由反分布函数得到。x=F-1(u),u为0,1区间上的独立均匀分布随机变量。xi为随机变量，ui为随机变量抽样值 各种随机分布变量 均匀分布随机变量 指数分布随机变量,11.5 随机数与随机变量的生成,随机变量的生成 反变换法： 各种随机分布变量 正态分布随机变量（见后页） 将概率密度函数进行极坐标变换，可以得到其封闭形式，然后进行反变换，即可得到正态分布随机变量 三角分布 离散分布 伯努利分布,11.5 随机数与随机变量的生成,11.5 随机数与随机变量的生成,随机变量的生成 卷积法： 基本原理：一个随机变量可以表示成若干个独立同分布的子随机变量的和，其分

19、布函数为各子变量分布函数的卷积。 Y=x1+x2+x3+x4+ 各种随机分布变量 爱尔朗分布随机变量（见后页） 二项分布随机变量 泊松分布随机变量,11.5 随机数与随机变量的生成,11.6 排队服务系统的仿真,例：单服务排队系统 已知在单排队服务系统中，顾客到达时刻服从泊松分布，即两个顾客到达的时间间隔服从指数分布，平均5分钟到一位；服务台为每位顾客服务的时间也服从指数分布，平均服务时间为4分钟。顾客按单队排队，先进先出的服务方式。要求通过仿真估计服务n个顾客的顾客平均队长及平均排队等待时间。 仿真模型建立 仿真程序设计,11.6 排队服务系统的仿真,仿真模型建立 随机变量抽样模型(u1,u

20、2属U0,1) 顾客到达时间间隔Ai，服从A5 min的指数分布。A= -Alnu1 服务台服务时间Si，服从s=4 min的指数分布. S= -slnu2： 建立事件表 状态：顾客是否需要排队，队长q; 服务台是否空闲,z 事件：顾客到达事件（到达时间）；顾客接受服务后离开事件（离开时间） 性能指标估计公式,11.6 排队服务系统的仿真,仿真程序设计 仿真模型的执行机制 基于事件表，采用基于事件的时间推进机制，进行时间扫描、事件处理的循环执行。 仿真程序结构 主模块：调用和逻辑控制 参数设置模块：模型参数和仿真参数 初始化模块：相关变量的初始化 仿真运行模块：定时、事件处理、报告生成 统计分

21、析模块： 函数模块：随机数发生器 仿真程序设计 主要子程序：随机数发生器、顾客到达事件处理、顾客离去事件处理 辅助子程序：定时、初始化、报告生成、统计分析,11.7 存储系统的仿真,例：随机存储系统仿真 某公司经销单类产品，顾客需求时间间隔为Dm服从均值为0.1的指数随机变量；需求量D也为随机变量，其概率质量函数为 该公司的订货策略为按月订货，每月检查库存水平。若库存水平I超过下限L，则不订货，否则订货，订货量Z为库存上限S与下限l之差。 若订货，则订货延迟时间M也是随机变量，服从U0.5,1的均匀分布。有下列9种订货策略，问哪种费用最小。,11.7 存储系统的仿真,仿真工作步骤 建立费用模型：订货费C1、存储费C2、缺货损失费C3。,11.7 存储系统的仿真,仿真工作步骤 建立仿真模型 随机变量仿真模型 需求时间间隔Dm 需求量D 订货延迟时间M,11.7 存储系统的仿真,仿真工作步骤 建立仿真模型 模型这事件的定义 类型1，货物入库事件：导致库存量增加 类型2，需求到达事件：导致库存量减少 类型4，订货事件：月初根据库存量和库存策略决定是否订货 确定统计变量 评价库存策略的指标为每月平均总费用C,11.7 存储系统的仿真,仿真工作步骤 仿真程序设计 参数输入 模型参数： 仿真参数： 仿真流程控制 子程序 初始化 定时 事件处理 统计分析,END,