离散事件系统的建模与仿真PPT课件

.,离散事件系统的建模与仿真,机电工程学院飞行器工程系系统与仿真实验室单家元博士,.,11离散事件系统建模与仿真,离散事件系统的数学描述方法排队服务系统的数学建模存储系统的数学建模离散事件系统的仿真原理随机数与随机变量的生成排队服务系统的仿真存储系统的仿真,.,11.1离散事件系统的数学描述方法,离散事件系统的描述要素实体：系统的具体对象事件：引起系统状态变化的行为活动：表示两个可以区分的事件之间的过程。标志状态的转移。进程：描述系统所包含事件及活动间的相互逻辑和时序关系。,.,11.1离散事件系统的数学描述方法,离散事件系统的数学模型利用随机过程理论和概率理论对离散事件系统诸要素的数学描述。其是一个离散的数集。形式化描述：M=(X,Y,S,ta)。这里：X外部事件（输入事件）；Y输出事件，S序贯状态；状态转移函数；输出函数和ta时间推进函数。,.,11.1离散事件系统的数学描述方法,进程,排队活动,服务活动,顾客到达事件,服务开始事件,服务结束事件,离散事件系统中的实体、事件、活动和进程,实体：顾客、服务台,.,11.2排队服务系统的数学建模,排队服务系统的概念定义：由一个或多个服务台构为随机到达的顾客提供某些服务，而顾客视服务台的闲、忙，并按其排队律被服务或者等待的系统叫排队服务系统。组成：顾客源、排队结构、服务机构,顾客源,顾客源,顾客源,服务规则,排队规则,到达模式,离去,.,11.2排队服务系统的数学建模,排队服务系统的基本要素到达模式：描述顾客随机到达服务机构要求某种类型服务的的随机分布模式。为系统输入，用随机到达时间表示。分布特性：定长分布、泊松分布、爱尔朗分布、指数分布排队规则先到先服务：FIFO后到先服务：LIFO优先服务律：优先级随机律：同等机会，随机抽取其它：到超时、超长离去,.,11.2排队服务系统的数学建模,排队服务系统的基本要素服务机构：提供特定类型服务的一定数量的服务台之间的配置形式：并行（单对多服务）、串行（单对单服务）或其它。服务过程为各个顾客服务要花费时间而形成的服务过程。描述服务过程的统计特性：服务时间分布特性：定长分布(D)、爱尔朗分布(Ek)、负指数分布(M)、一般随机分布(GI),.,11.2排队服务系统的数学建模,排队服务系统的模型分类和表示分类：按照排队系统的三大组成要素（到达时间分布X、服务时间分布Y、服务台数目Z），进行分类。表示：X/Y/Z。D/M/1M负指数分布D定长分布EkK阶爱尔朗分布GI独立的随机分布,.,11.2排队服务系统的数学建模,排队服务系统的建模方法到达模式的数学模型定长分布：顾客在等距离时间间隔到达。,.,11.2排队服务系统的数学建模,排队服务系统的建模方法到达模式的数学模型泊松分布：顾客在给定时间长度为t的时间内发生有n个到达的概率。,.,11.2排队服务系统的数学建模,排队服务系统的建模方法到达模式的数学模型指数分布：其累积函数为若随机数y为均匀分布，则到达时间为,.,11.2排队服务系统的数学建模,排队服务系统的建模方法到达模式的数学模型爱尔朗分布：其密度函数为到达分布函数为,.,11.2排队服务系统的数学建模,排队服务系统的建模方法服务过程的数学模型定长的服务时间。一般情况随机分布：一般按指数分布。特殊情况可按爱尔朗分布或超指数分布。正态分布：密度函数为,.,11.2排队服务系统的数学建模,排队服务系统的建模方法排队律的数学模型先到先服务：服务首先提供给等待时间最长的顾客。后到先服务：服务首先提供给最后到达的顾客。优先服务律：中断或强占服务。服务提供给优先级最高的顾客。随机律：对所有等待的顾客进行随机选择服务。其它：到超时、超长离去,.,11.2排队服务系统的数学建模,排队服务系统的建模方法建模关键通过大量观测数据获得概率分布函数借助该函数描述到达模式和服务过程,.,11.2排队服务系统的数学建模,排队服务系统的建模实例防空导弹武器系统的排队问题防空导弹具有火力的自动化指挥控制系统。自动完成发现跟踪目标、目标识别及飞行参数计算、目标威胁判断及火力分配。火力分配后，不再对各通道进行火力控制，各火力单元自行进行射击诸元计算并发射和制导导弹。模型类型：串联服务排队系统：即串联服务台：自动化指控系统、发射单元。描述：来袭敌机：服从最简单流（来袭敌机的逗留时间较短）。为为常数的平稳泊松分布。服务时间的分布：指控系统和射击诸元所需时间服从指数分布规律。,.,11.3存储系统的数学建模,存储系统的基本概念需求：存储的输出。间断的或连续均匀的；确定的或随机的。补充：存储的输入。生产或订货。但需要时间。费用：各种消耗费用。存储费h、订货费S、生产费c、缺货费d。存储策略循环策略：每隔t0时间进行补充存储量Q。(x,S)策略：每当x=S时补充存储量Q=S-x。混合策略：每隔t0时间检查存储量，然后实行(x,S)策略,.,11.3存储系统的数学建模,存储系统的基本概念需求率：单位时间内需要的物品数量。r(t)订货点：订货的规定存储量。p订货量：一次订货的物品数量。q订货周期：相邻两次订货的时间间隔。Ti,.,11.3存储系统的数学建模,存储系统的数学建模存储系统建模的目标：订货与库存费用最小。问题：何时订货和订货量多少。模型类型：确定性存储模型：随机性存储模型：,.,11.3存储系统的数学建模,确定性存储系统的数学建模模型1：确定性需求，不允许缺货。假定：需求率R、订货费S、存储费h为常数；拖后时间L=0（立即补充）；不容许缺货；订货周期为T，每次订货量Q为常数。建模过程：确定费用函数C(T)：T时间内的平均费用：C(T)=C1/T+C2RT/2C1为订货费用，C2为存储费用最优存储策略：求T使C(T)最小。对C求导。得,.,.,11.3存储系统的数学建模,确定性存储系统的数学建模模型2：生产需要一定时间，确定性需求，不允许缺货。假定条件同1，但生产需要一定时间。建模：按照上述同样方法进行。P为订货点（规定存储量）。,.,11.3存储系统的数学建模,确定性存储系统的数学建模模型3：确定性需求，允许缺货。假定：除在单位时间内短缺的单位数量的物品，需要支付短缺费d外，条件件同1。建模：按照上述同样方法进行。C3为单位缺货费用。当C3远远大于C2时，下式变为模型1。,.,.,11.3存储系统的数学建模,确定性存储系统的数学建模模型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,)。拖后时间为已知正整数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离散事件系统的仿真原理,基本概念实体：临时实体（某个顾客）、永久实体（服务台）事件：事件表（记录事件的发射时间、事件类型、参与的实体及其相关属性）活动：状态的变化。进程：事件及活动的逻辑与时间关系。仿真时钟：随仿真进程的时间推进机制。随机性：推进步长随机跳跃性：时钟推进是跳跃的,.,11.4离散事件系统的仿真原理,基本原理仿真机制：面向事件的仿真机制事件调度法：事件安排和时间推进。在“产生事件、安排事件、时间推进、处理事件、再产生新事件”中进行循环。面向活动的仿真机制活动扫描法：对所有部件进行扫描，判断活动是否发生，要看是否满足条件，其中时间条件优先。面向进程的仿真机制进程交互法：综合了前两种仿真机制，采用了两个事件表（当前事件表和将来事件表）,.,.,.,.,11.4离散事件系统的仿真原理,仿真流程管理仿真时钟时间步长法：下一个最早发生的事时间的时间来推进。事件步长法：面向时间间隔的推进方式：以固定的时间间隔等距推进。事件表：按照事件出现的时序，列入事件表。同时事件管理同类同时事件管理。由排队规则处理该类事件混合同时事件管理。一步法：直接确定同时事件所形成的结果状态。解结法：分解为单独事件序列来处理。,.,11.4离散事件系统的仿真原理,单服务台排队系统：两种事件（顾客到达、顾客离去）第i个和第i-1个顾客到达的时间间隔：A1=15,A2=32,A3=24,A4=40,服务台为第i个顾客服务的时间长度：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服务处理时间,A顾客到达时间间隔,c顾客离去时间,A5,t顾客到达时间,q0=0z0=0,q1=0z1=1,q2=1z2=1,q6=1z6=1,q5=0z5=1,q4=1z4=1,q3=0z3=1,q7=0z7=1,q8=1z8=1,.,11.5随机数与随机变量的生成,均匀分布随机数生成均匀分布随机数概念：（a,b）均匀分布：概率密度函数：（0,1）均匀分布,.,11.5随机数与随机变量的生成,均匀分布随机数生成均匀分布随机数生成方法表格法：将采用某种手段生成的随机数以表格形式存入计算机仿真时调用。消耗内存，浪费时间物理法：物理随机数发生器。无法重复移位法：采用移位寄存器产生。数学方法：伪随机数按照一定算法（递推公式），自动生成。给定种子，多次调用，生成随机数序列。,.,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区间上的均匀性。即一个周期内每个正整数只出现一次。,.,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随机数与随机变量的生成,随机变量的生成反变换法：基本原理：由反分布函数得到。x=F-1(u),u为0,1区间上的独立均匀分布随机变量。xi为随机变量，ui为随机变量抽样值各种随机分布变量均匀分布随机变量指数分布随机变量,.,11.5随机数与随机变量的生成,随机变量的生成反变换法：各种随机分布变量正态分布随机变量（见后页）将概率密度函数进行极坐标变换，可以得到其封闭形式，然后进行反变换，即可得到正态分布随机变量三角分布离散分布伯努利分布,.,11.5随机数与随机变量的生成,.,11.5随机数与随机变量的生成,随机变量的生成卷积法：基本原理：一个随机变量可以表示成若干个独立同分布的子随机变量的和，其分布函数为各子变量分布函数的卷积。Y=x1+x2+x3+x4+各种随机分布变量爱尔朗分布随机变量（见后页）二项分布随机变量泊松分布随机变量,.,11.5随机数与随机变量的生成,.,11.6排队服务系统的仿真,例：单服务排队系统已知在单排队服务系统中，顾客到达时刻服从泊松分布，即两个顾客到达的时间间隔服从指数分布，平均5分钟到一位；服务台为每位顾客服务的时间也服从指数分布，平均服务时间为4分钟。顾客按单队排队，先进先出的服务方式。要求通过仿真估计服务n个顾客的顾客平均队长及平均排队等待时间。仿真模型建立仿真程序设计,.,11.6排队服务系统的仿真,仿真模型建立随机变量抽样模型(u1,u2属U0,1)顾客到达时间间隔Ai，服从A5min的指数分布。A=-Alnu1服务台服务时间Si，服从s=4min的指数分布.S=-slnu2：建立事件表状态：顾客是否需要排队，队长q;服务台是否空闲,z事件：顾客到达事件（到达时间）；顾客接受服务后离开事件（离开时间）性能指标估计公式,.,11.6排队服务系统的仿真,仿真程序设计仿真模型的执行机制基于事件表，采用基于事件的时间推进机制，进行时间扫描、事