离散事件系统的建模与仿真强烈推荐.ppt课件.ppt

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

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

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

4、服务要花费时间而形成的服务过程。描述服务过程的统计特性：服务时间n分布特性：定长分布(D)、爱尔朗分布(Ek)、负指数分布(M)、一般随机分布(GI)0.0811.2 排队服务系统的数学建模n排队服务系统的模型分类和表示n分类：按照排队系统的三大组成要素（到达时间分布X、服务时间分布Y、服务台数目Z），进行分类。n表示：X/Y/Z。D/M/1nM负指数分布nD定长分布nEkK阶爱尔朗分布nGI独立的随机分布0.0911.2 排队服务系统的数学建模n排队服务系统的建模方法n到达模式的数学模型n定长分布：顾客在等距离时间间隔到达。atattTPtA1, 0)(00.01011.2 排队服务系统的数

5、学建模n排队服务系统的建模方法n到达模式的数学模型n泊松分布：顾客在给定时间长度为t的时间内发生有n个到达的概率。,.)2 , 1 , 0(!)()(nnetnPtn0.01111.2 排队服务系统的数学建模n排队服务系统的建模方法n到达模式的数学模型n指数分布：其累积函数为n若随机数y为均匀分布，则到达时间为teytF1)(为平均相关到达时间aaTyTyt).ln()ln(0.01211.2 排队服务系统的数学建模n排队服务系统的建模方法n到达模式的数学模型n爱尔朗分布：其密度函数为n到达分布函数为1)!1()()(ktkktkektf为大于零的正整数kntketAknntk100!)()(

6、0.01311.2 排队服务系统的数学建模n排队服务系统的建模方法n服务过程的数学模型n定长的服务时间。一般情况n随机分布：一般按指数分布。特殊情况可按爱尔朗分布或超指数分布。n正态分布：密度函数为2/2/12)2(1)(zezf0.01411.2 排队服务系统的数学建模n排队服务系统的建模方法n排队律的数学模型n先到先服务：服务首先提供给等待时间最长的顾客。n后到先服务：服务首先提供给最后到达的顾客。n优先服务律：中断或强占服务。服务提供给优先级最高的顾客。n随机律：对所有等待的顾客进行随机选择服务。n其它：到超时、超长离去0.01511.2 排队服务系统的数学建模n排队服务系统的建模方法n

7、建模关键n通过大量观测数据获得概率分布函数n借助该函数描述到达模式和服务过程0.01611.2 排队服务系统的数学建模n排队服务系统的建模实例n防空导弹武器系统的排队问题n防空导弹具有火力的自动化指挥控制系统。自动完成发现跟踪目标、目标识别及飞行参数计算、目标威胁判断及火力分配。火力分配后，不再对各通道进行火力控制，各火力单元自行进行射击诸元计算并发射和制导导弹。n模型类型：串联服务排队系统：即串联服务台：自动化指控系统、发射单元。n描述：n来袭敌机：服从最简单流（来袭敌机的逗留时间较短）。为为常数的平稳泊松分布。n服务时间的分布：指控系统和射击诸元所需时间服从指数分布规律。0.01711.3

8、 存储系统的数学建模n存储系统的基本概念n需求：存储的输出。间断的或连续均匀的；确定的或随机的。n补充：存储的输入。生产或订货。但需要时间。n费用：各种消耗费用。存储费h、订货费S、生产费c、缺货费d。n存储策略n循环策略：每隔t0时间进行补充存储量Q。n(x,S)策略：每当x=S时补充存储量Q=S-x。n混合策略：每隔t0时间检查存储量，然后实行(x,S)策略0.01811.3 存储系统的数学建模n存储系统的基本概念n需求率：单位时间内需要的物品数量。r(t)n订货点：订货的规定存储量。pn订货量：一次订货的物品数量。qn订货周期：相邻两次订货的时间间隔。Ti0.01911.3 存储系统的数

9、学建模n存储系统的数学建模n存储系统建模的目标：订货与库存费用最小。问题：何时订货和订货量多少。n模型类型：n确定性存储模型：n随机性存储模型：0.02011.3 存储系统的数学建模n确定性存储系统的数学建模n模型1：确定性需求，不允许缺货。假定：n需求率R、订货费S、存储费h为常数；n拖后时间L=0（立即补充）；n不容许缺货；n订货周期为T，每次订货量Q为常数。n建模过程：n确定费用函数C(T)：T时间内的平均费用：n C(T)=C1/T+C2RT/2 C1为订货费用，C2为存储费用n最优存储策略：求T使C(T)最小。对C求导。得212122CRCQRCCT0.0210.02211.3 存储

10、系统的数学建模n确定性存储系统的数学建模n模型2：生产需要一定时间，确定性需求，不允许缺货。假定条件同1，但生产需要一定时间。n建模：按照上述同样方法进行。P为订货点（规定存储量）。)(2)(22121RPCRPCQRPRCPCT0.02311.3 存储系统的数学建模n确定性存储系统的数学建模n模型3：确定性需求，允许缺货。假定：除在单位时间内短缺的单位数量的物品，需要支付短缺费d外，条件件同1。n建模：按照上述同样方法进行。C3为单位缺货费用。当C3远远大于C2时，下式变为模型1。3232133221222CCCCRCQCCCCCT0.0240.02511.3 存储系统的数学建模n确定性存储

11、系统的数学建模n模型4：离散需求的存储模型。假定：需求时间为离散，单位时间内需求次数为n。需求量为a。n建模目标：确定一次订货的最优数量Q=Ka，使单位时间内的总存储费用C(K)最小。n建模：n单位时间总需求量：na;n最大存储量：(K-1)a;n订货周期：T=Ka/na=K/nn总存储费用：n C(K)=h*a(K-1)/2+Sn/K (K为正整数)为最优订货量。则若为最优订货量；则若aKKCKCaKKCKCahSnxK) 1(),1()(),1()(2*0.02611.3 存储系统的数学建模n随机存储系统的数学建模n随机变量：需求率R、拖后时间L、订货量Q、订货周期T。n确定订货点：假定各

12、单位时间内的需求量Ri是独立同分布的，分布函数为F(x)，分布密度函数为f(x)，正态分布N(S,)。n拖后时间为已知正整数nL期间的需求量：RL=R1+R2+Ri，而Ri服从正态分布，RL为F(x)的n次卷积，则 。n风险水平为a的订货点R0:),(LLSNRLaZZPLLSRZZZLLSRaLaa1)(0查表，是该分布满足：根据0.02711.3 存储系统的数学建模n随机存储系统的数学建模n确定订货量n若订货周期T为随机变量（概率分布为G(t)），则在t时间内需求次数n(t)服从泊松分布，在需求量Y(T)为：。的订货量具有风险水平。即即可得到，从给定风险水平aaatnnnRaRaRHatd

13、GentyFyTYPyH 1)()(!)()()()(000.0280.02911.3 存储系统的数学建模n随机存储系统的数学建模n单周期随机存储模型n需求量R为随机变量，F(r),f(r)。条件：一次订货。问题：确定最优订货量使总损失的期望值最小。订购费与订货量无关。订货量大于需求量，则付损失费，否则付短缺费。的一分点。分布的为即，最优订货量得到：则通过使期望值最小，总费用期望值：)/()()()()()()()(*0*0*hddFQhdddrrfQFdrrfQrddrrfrQhQEQQQ0.03011.4离散事件系统的仿真原理n基本概念n实体：临时实体（某个顾客）、永久实体（服务台）n事件

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

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

16、客服务的时间长度：S1=43,S2=36,S3=34,S4=28,n系统初始状态：第i个事件发生时的队伍长度qi取q00；第i个事件发生时服务台状态zi取z0=0表示空闲。n仿真初始时钟：TIMEb0=t0。bi为第i个顾客到达事件，ti为第i个事件发生的时间。nCi为第i个顾客离开系统的时间，Di为第i个顾客排队等待的时间。0.03711.4 离散事件系统的仿真原理n单服务台排队系统(仿真时钟推进机制)t0t1t2c1t3t4c3t5A4A3A2A1b0b1b2b3b5b6b7b8D3D2S1S2S3c2tb4b事件发生时间顾客等待时间s服务处理时间A顾客到达时间间隔c顾客离去时间A5t顾客

17、到达时间q0=0z0=0q1=0z1=1q2=1z2=1q6=1z6=1q5=0z5=1q4=1z4=1q3=0z3=1q7=0z7=1q8=1z8=10.03811.5 随机数与随机变量的生成n均匀分布随机数生成n均匀分布随机数概念：n（a,b）均匀分布：概率密度函数：n（0,1）均匀分布),(01)(baUUbxaabxf其它121)(21) 1 , 0(0101)(102210dxxxdxUUxxf方差：均值：其它0.03911.5 随机数与随机变量的生成n均匀分布随机数生成n均匀分布随机数生成方法n表格法：将采用某种手段生成的随机数以表格形式存入计算机仿真时调用。消耗内存，浪费时间n物

18、理法：物理随机数发生器。无法重复n移位法：采用移位寄存器产生。n数学方法：伪随机数n按照一定算法（递推公式），自动生成。n给定种子，多次调用，生成随机数序列。0.04011.5 随机数与随机变量的生成n均匀分布随机数生成n常用随机数发生器n平方取中法n倍积取中法n同余法n加同余n二次同余n线性同余0.04111.5 随机数与随机变量的生成n均匀分布随机数生成n线性同余法n递推公式：为混合同余。，则为乘同余；，则为加同余；令则：的求余运算，即进行模数为表示对区间上的随机数。是为模数，为增量，为乘子，个随机数，为第其中：10110*)(modmod 1 , 0,.)2 , 1(/mod)(1cca

19、mxmmNNmNmNmNumcanxnmxumNcaxxnnnnnnn0.04211.5 随机数与随机变量的生成n均匀分布随机数生成n线性同余法n特点：nXn位于0,m-1区间，un位于0,1区间n适当选择m,a,c，可使xn产生循环，循环周期为T。若T=m，则称为满周期。n适当选择m,a,c，可保证xn在0,m-1区间上的均匀性。即一个周期内每个正整数只出现一次。0.04311.5 随机数与随机变量的生成n随机数发生器的性能检验n均匀性检验：频率检验， 检验法n假设H0：u1,u2,是独立同分布U0,1随机变量n将0,1区间分成m个互不相交的子区间i-1/m,i/mn落在每一个子区间上的随机

20、数个数的理论值i为n/mn统计实际落在子区间上的随机数个数nn构造统计量n判定原假设是否成立。设置信水平为a，若下式成立，则H0成立，否则，拒绝H0。2miimiimnnnmn12122)()(21 , 12am0.04411.5 随机数与随机变量的生成n随机数发生器的性能检验n独立性检验：相关系数检验法n相关系数定义n给定显著水平a，计Z1-a为N0,1上的1-a临界点。则当下式成立时，接受独立性假设。jnmjuunuuuujnjjniijnijiij统计量相关系数,.,2 , 1)(11)(1121ajZ10.04511.5 随机数与随机变量的生成n随机变量的生成n反变换法：n基本原理：由

21、反分布函数得到。x=F-1(u),u为0,1区间上的独立均匀分布随机变量。xi为随机变量，ui为随机变量抽样值n各种随机分布变量n均匀分布随机变量n指数分布随机变量uxuuuxxxexfuabaxbxaabxfxln1 1 , 01)1ln(1000)()(01)(分布，因此常取同属和由于其它随机变量概率密度函数0.04611.5 随机数与随机变量的生成n随机变量的生成n反变换法：n各种随机分布变量n正态分布随机变量（见后页）n将概率密度函数进行极坐标变换，可以得到其封闭形式，然后进行反变换，即可得到正态分布随机变量n三角分布n离散分布n伯努利分布0.04711.5 随机数与随机变量的生成)2

22、sin(ln2)2cos(ln2ln22, )1ln(21 ,0,2)(21)(1)()()()(21cossinsincos)sin,cos()2, 1(),(21)2, 1(,2)(exp21)(),(21221112121212222/)(212222222221uuxuuxuruurNuuuFfuerFrerffrfrerrrrfJxxfrfexxfxxxxfNrrrxx。同前理由则得到：属形式：该式可以表示成极坐标的联合概率密度函数为两个随机变量。正态分布概率密度函数0.04811.5 随机数与随机变量的生成n随机变量的生成n卷积法：n基本原理：一个随机变量可以表示成若干个独立同分布

23、的子随机变量的和，其分布函数为各子变量分布函数的卷积。nY=x1+x2+x3+x4+n各种随机分布变量n爱尔朗分布随机变量（见后页）n二项分布随机变量n泊松分布随机变量0.04911.5 随机数与随机变量的生成niiniiiiinxnuxxuxxuuuUnxenxxf11211ln13ln1.2,., 1 , 01)0, 0( ,)!1()()(、得到、用反变换法产生随机变量、生成独立均匀生成算法：阶爱尔朗分布随机变量数：爱尔朗分布概率密度函0.05011.6 排队服务系统的仿真n例：单服务排队系统n已知在单排队服务系统中，顾客到达时刻服从泊松分布，即两个顾客到达的时间间隔服从指数分布，平均5

24、分钟到一位；服务台为每位顾客服务的时间也服从指数分布，平均服务时间为4分钟。顾客按单队排队，先进先出的服务方式。要求通过仿真估计服务n个顾客的顾客平均队长及平均排队等待时间。n仿真模型建立n仿真程序设计0.05111.6 排队服务系统的仿真n仿真模型建立n随机变量抽样模型(u1,u2属U0,1)n顾客到达时间间隔Ai，服从A5 min的指数分布。A= -Alnu1n服务台服务时间Si，服从s=4 min的指数分布. S= -slnu2：n建立事件表n状态：顾客是否需要排队，队长q; 服务台是否空闲,zn事件：顾客到达事件（到达时间）；顾客接受服务后离开事件（离开时间）n性能指标估计公式个顾客等

25、待时间为第平均排队时间：时间内事件总数为个事件发生时间为第顾客平均队长：inDdTmibbbqRRTQniiniiiiimiin111/),(10.05211.6 排队服务系统的仿真n仿真程序设计n仿真模型的执行机制n基于事件表，采用基于事件的时间推进机制，进行时间扫描、事件处理的循环执行。n仿真程序结构n主模块：调用和逻辑控制n参数设置模块：模型参数和仿真参数n初始化模块：相关变量的初始化n仿真运行模块：定时、事件处理、报告生成n统计分析模块：n函数模块：随机数发生器n仿真程序设计n主要子程序：随机数发生器、顾客到达事件处理、顾客离去事件处理n辅助子程序：定时、初始化、报告生成、统计分析0.

26、05311.7 存储系统的仿真n例：随机存储系统仿真n某公司经销单类产品，顾客需求时间间隔为Dm服从均值为0.1的指数随机变量；需求量D也为随机变量，其概率质量函数为n该公司的订货策略为按月订货，每月检查库存水平。若库存水平I超过下限L，则不订货，否则订货，订货量Z为库存上限S与下限l之差。n若订货，则订货延迟时间M也是随机变量，服从U0.5,1的均匀分布。有下列9种订货策略，问哪种费用最小。L202020204040406060S4060801006080100801006/143/133/126/11概率为概率为概率为概率为D0.05411.7 存储系统的仿真n仿真工作步骤n建立费用模型：

27、订货费C1、存储费C2、缺货损失费C3。为单件缺货损失费。为月数，为单位存储费（月），为单件订货费用，为订货附加费用，其中：PnhmKndttIPdtthImZKCCCCnn00/)()()(3210.05511.7 存储系统的仿真n仿真工作步骤n建立仿真模型n随机变量仿真模型n需求时间间隔Dmn需求量Dn订货延迟时间MuMMuuuuDDuDm5 . 05 . 036/546/52/132/16/126/112ln1 . 01：、根据反变换法求得：变换求得、对任意离散型分布反、反变换法求得：0.05611.7 存储系统的仿真n仿真工作步骤n建立仿真模型n模型这事件的定义n类型1，货物入库事件：导致库存量增加n类型2，需求到达事件：导致库存量减少n类型4，订货事件：月初根据库存量和库存策略决定是否订货n确定统计变量n评价库存策略的指标为每月平均总费用C0.05711.7 存储系统的仿真n仿真工作步骤n仿真程序设计n参数输入n模型参数：n仿真参数：n仿真流程控制n子程序n初始化n定时n事件处理n统计分析0.058END0.059