计算机仿真(第5章-离散事件系统仿真)

COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY第5章离散事件系统仿真•系统S=（时间基；输入集；输入段集；内部状态集；状态转移函数；输出集；输出函数（输出段集））•时间基是描述系统变化的时间坐标，T为整数则称为离散时间系统；T为实数则称为连续时间系统。•对于离散事件系统，系统中的状态只是在离散时间点上发生变化，而且这些离散时间点一般是不确定的。如理发店系统、订票系统、库存系统、交通控制系统等。本资料由-校园大学生创业网-提供在线代理提供部分资料减肥药排行榜提供部分资料COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY5.1离散事件系统仿真概述•离散事件系统示例•例：单人理发店系统，设上午9:00开门，下午5:00关门。•顾客到达时间一般是随机的，为每个顾客服务的时间长度也是随机的。•系统的状态：服务台的状态(忙或闲)、顾客排队等待的队列长度。•状态量的变化也只能在离散的随机时间点上发生。COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY5.2离散事件系统基本建模术语•离散事件系统建模中要使用一套建模术语来描述模型，本节介绍一些基本术语。•不同的建模方法也采用一些专用术语。COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY1．系统•系统：一些具有特定功能、相互之间以一定的规律联系着的物体所组成的总体．COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY2．系统边界•系统边界：为了限制所研究问题涉及的范围，用系统边界把所研究的系统与影响系统的环境区分开来。COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY3．实体•实体：系统的对象、系统的组成元素都可以称为实体，是仿真系统中可单独识别和刻划的构成要素。•如：工厂中的机器，商店中的服务员，生产线上的工件，交通道路上的车辆等。在仿真建模人员看来，实际系统就是由相互间存在一定关系的实体集合组成的，实体间的相互联系和作用产生系统特定的行为。•属性和行为相同或相近的实体可以用类来描述，这样做可以简化系统的组成和关系。如，理发店服务系统可以看成是由“服务员”和“顾客”两类实体组成，而两类实体之间存在服务与被服务的关系。•离散事件系统中的实体分为临时实体与永久实体。临时实体按照一定的规律不断地到达（产生），在永久实体作用下通过系统，最后离开系统，整个系统呈现动态过程。COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY4．属性•属性：属性反映实体的某些性质，是实体特征的描述，用特征参数或变量表示，它可以是文字型、数字型或逻辑型。选用哪些特征参数作为实体的属性与建模目的有关。•选取原则：（1）便于实体的分类。（2）便于实体行为的描述。（3）便于排队规则的确定。COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY5．活动•活动：实体在一段时间内持续进行的操作或过程。•通常用于表示两个可以区分的事件之间的过程。标志着系统状态的转移。活动反映了系统变化的规律。顾客的到达事件与该顾客开始接受服务事件之间可称为一个活动。•活动所占用的时间区段称为忙期。•在离散事件建模中，一般要给出忙期的计算公式或概率分布函数，保证实体在进入某一活动时，其忙期是可计算的。如“服务员”对“顾客”的服务，忙期可从指数分布函数抽样得到。COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY6．状态•状态：系统的状态是指在某一时刻实体及其属性值的集合。•在理发店服务系统模型中，“顾客”有“等待服务”、“接受服务”等状态，“服务员”有“忙”、“闲”等状态。•活动总是与一个或几个实体的状态相对应。COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY7．事件•事件：事件是引起离散事件系统状态发生变化的行为。•活动是指一段过程，即在一段时间内发生的情况。事件是指一个时间上的情况，系统发生变化的瞬间就发生了事件。事件的发生会导致状态的变化，而实体的活动可以与一定的状态相对应，因此可以用事件来表示活动的开始和结束。•从某种意义上说，离散事件系统是由事件驱动的。•为实现对系统中事件的管理，在仿真模型中必须建立事件表，来记录发生的事件，或将要发生的事件，以及与相应事件关联实体的有关属性。•事件表：一个有序的记录序列，每个记录包括事件发生时间、事件类型等一些内容。•“顾客到达”为一类事件：－》系统状态变化－－服务员的“状态”可能从闲变到忙（如果无人排队)，或者另一系统状态－－排队的顾客人数发生变化（队列人数加1)。•“顾客离去”为一类事件－》顾客接受服务完毕后离开系统------服务员“状态”由忙变成闲。COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY8．进程•进程：由若干个有序事件及若干有序活动组成，描述了它所包括的事件及活动间的相互逻辑关系及时序关系。•事件、活动、进程关系示意图顾客到达事件服务开始事件服务结束事件排队活动服务活动进程COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY9．仿真时钟•仿真时钟：表示仿真时间的变化。•研究系统一般是为认识其状态随时间变化的规律，所以需要一个仿真时间变量。仿真时钟的推进呈现跳跃性，推进速度具有随机性。•时间控制部件是必不可少的，以便按一定规律来控制仿真时钟的推进。•仿真时钟推进方法有两大类：（1）按照下一个最早发生事件的发生时间推进，亦称为事件调度法。（2）固定增量推进方法，选择适当的时间单位T做为仿真时钟推进时的增量。COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY5.3离散事件系统仿真中的概率分布•在离散事件系统仿真中，系统内部实体的活动是不确定的，事件的发生具有随机的性质。•对于这种随机的过程需要采用概率及统计的方法描述。•离散事件系统模型一般与概率分布有关，因此建模者要从已知的数据中选择合适的分布形式，作该分布的参数估计，然后进行检验以观察是否获得合适的拟合，最终得到离散事件系统的概率模型。COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY1．概率统计基本概念•确定事件：在给定条件下进行的试验中，一定发生或一定不发生的事件分别称为必然事件和不可能事件，这类事件是确定性的，称为确定事件。•随机事件：在给定条件下进行的试验中，可能发生也可能不发生，而在大量重复实验中却具有某种规律性的事件，称为随机事件。•随机变量：如果试验的每个结果用变量ξ的一个值来表示，即ξ的值根据试验结果来确定，因而它取什么值是随机的。而且对任意实数x，ξx是一个随机事件，这种变量称为随机变量。COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY概率•概率：如果对某项试验重复进行n次，事件A发生了m次，则称A在这n次试验中的频率为m/n。•在大量重复某项试验时，就会发现事件的频率在试验次数很大而且不断增大的过程中呈现稳定性。这种统计规律表明：事件发生的可能性大小是事件本身固有的客观属性。•称事件A发生可能性的大小为事件A的概率。记为P（A）。当试验次数n足够大时，可以用事件的频率作为概率的近似值，即P（A）≈m/n•概率是一个在区间［0，1］上取值的实数。•随机变量ξ取值小于x的可能性大小，即随机事件｛ξx｝发生的概率，介于数0和1之间：0≤P｛ξx｝≤1COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY概率分布•概率分布：对于随机变量ξ，事件｛ξx｝的概率是实变量x的函数，称之为ξ的概率分布函数，记为F（x），即F（x）＝P｛ξx｝（-∞x∞）•离散性随机变量的概率分布：离散性随机变量ξ可能取值为x1，x2，…，xn，｛ξ=xk｝为一随机事件，其发生概率记为Pk=P｛ξ=xk｝,k=1,2,…,n•Pk为离散性随机变量ξ的概率分布，Pk满足于nkkkpP110COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY2．常用的概率分布形式（1）（0－1）分布•设随机变量ξ只能取0和1二个值，它的概率分布是：•则称ξ服从（0－1）分布。)10(,101ppPpPCOMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY（2）泊松分布•泊松分布非常适合描述许多随机过程，且在数学上非常简单。•若随机变量ξ所有可能取的值为0，1，2，…，而取各个值的概率为•其中λ0为常数，则称ξ服从参数为λ的泊松（Poisson）分布，记为ξ～π（λ）。,2,1,0,!1kkkPekCOMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY（3）指数分布•若随机变量ξ具有分布密度•其中λ0为常数，则称ξ服从参数为λ的指数分布。•ξ的概率分布函数为•指数分布的均值为000)(xxxpex0001)(xxxFex1)(ECOMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY3．排队系统概率分布模型•在排队系统中，主要有两种类型的活动，即实体到达和实体接受服务。一般情况下，实体到达的时间间隔是不确定的，从而在一定时间内到达的实体数目也是一个随机变量。另一方面，实体接受服务的时间也是不确定的，从而造成队列的长短也是随机的。•实体到达的模式一般用泊松分布来描述，即在固定的时间内到达系统的实体数目服从泊松分布。这种模式的特点是：（1）在一定时间间隔内到达实体的数目仅与时间间隔的长短有关，而与这段时间间隔的起始时刻无关。（2）在某个时间间隔内，到达的实体数目与在此之前到达的实体数目无关，也不影响在此之后实体的到达。（3）不存在两个或两个以上实体同时到达的情况。（4）若在一定时间内到达系统的实体数目x服从参数为λ的泊松分布，则相邻到达的两个实体之间的到达时间间隔T也服从参数为λ的泊松分布。COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY5.4实体流图法•对系统进行仿真研究，首先要建立系统的模型。离散事件系统的时间是连续变化的，但系统的状态仅发生在一些离散的时刻，由随机事件的驱动而发生，因此，离散事件系统的模型很难用数学方程来描述。所以，逐渐形成一些与连续系统不同的建模方法。实体流图法就是其中之一。•实体流程图方法（简称实体流图法）与程序流程图类似，可以描述临时实体产生、流动、消亡及其被永久实体加工、处理的过程和逻辑关系，应用比较广泛。COMPUTERSCIENCEANDTECHNOLOGYCOMPUTERSCIENCEANDTECHNOLOGY临时实体和永久实体•在离散事件系统中，实体分为两大类：临时实体、永久实体。•临时实体：按一定规律由系统外部