第4讲-排队系统仿真课件

计算机仿真清华大学自动化系2009-2010学年度秋学期ComputerSimulation第4讲排队系统建模与仿真范文慧4.0排队系统仿真基础知识4.1排队系统仿真实例4.2离散事件系统仿真原理4.3随机数发生器4.4随机变量产生4.5排队系统仿真实例4.6仿真结果输出分析4.7小结目录2（1）基本概念总体参数样本统计量随机抽取平均数标准差比例概率与数理统计知识名称样本特征值总体数字特征均值数学期望方差标准差变异系数（1）基本概念概率与数理统计知识方差：

标准差：

协方差：

相关系数：

（1）基本概念概率与数理统计知识Page6均值的方差期望值：均值的方差估计值：（1）基本概念概率与数理统计知识Page7（2）抽样分布1)样本均值抽样分布概率与数理统计知识（2）抽样分布中心极限定理：从总体均值μ，方差为σ2的总体中，抽取容量为n的随机样本，当n（≧30)充分大时，样本均值的抽样分布服从均值为μ，方差为σ2/n的正态分布当时，接近标准正态分布随机变量的分布函数，即：实际应用：概率与数理统计知识（2）抽样分布2)样本方差抽样分布总体为正态分布概率与数理统计知识（2）抽样分布概率与数理统计知识样本统计量正态分布非正态分布正态分布大样本非正态总体（小样本）正态总体或非正态总体（大样本）样本均值样本比例样本方差分布样本统计量的抽样分布（2）抽样分布3)两个样本均值差的抽样分布概率与数理统计知识Page124)两个样本方差比的抽样分布（2）抽样分布概率与数理统计知识用样本均值（）估计总体均值（μ

）(3)参数估计参数估计：（根据样本统计量来推断总体的参数）用样本方差（）估计总体方差（

）用样本比例（）估计总体比例（）用估计总体参数的统计量，称为估计量用样本统计量去估计总体的参数（θ）概率与数理统计知识无偏性：估计量抽样分布的数学期望等于被估计的总体参数点估计：用样本估计量的值，直接作为总体参数的估计值区间估计：在点估计的基础上，给出总体参数估计的一个范围，衡量点估计值的可靠性的度量置信水平：重复构造置信区间多次，包含总体参数真值的次数所占的比率（1－α）置信区间：由样本统计量所构造的总体参数的估计区间(3)参数估计概率与数理统计知识Page151)总体均值的区间估计正态总体、方差已知，或非正态总体、大样本置信区间非正态总体、大样本置信区间正态总体、方差已知总体均值μ在1－α的置信水平下的置信区间正态总体、方差未知、小样本总体均值μ在1－α的置信水平下的置信区间(3)参数估计概率与数理统计知识Page162)总体方差区间估计总体方差在1－α的置信水平下的置信区间正态总体，样本方差服从由于则即(3)参数估计概率与数理统计知识Page173）两个总体参数（均值差）的区间估计（独立样本）大样本:若总体方差未知：若总体方差已知：(3)参数估计概率与数理统计知识Page184）估计总体均值的样本容量的确定点估计值区间半长度或边际误差E(3)参数估计概率与数理统计知识Page19(4)假设检验(σ2未知)(σ2已知)P0为假设的总体比例总体的方差先对总体参数提出一个假设值，然后利用样本信息判断这一假设是否成立概率与数理统计知识排队常常是件很令人恼火的事情……

尤其是在我们这样的人口大国?4.0排队系统仿真基础知识20

排队论：1918年，Erlang提出排队论，并将它用于电话系统。

有形排队现象：

进餐馆就餐，到图书馆借书，车站等车，去医院看病，售票处售票，到工具房领物品等现象。

无形排队现象：如几个旅客同时打电话订车票，如果有一人正在通话，其他人只得在各自的电话机前等待，他们分散在不同的地方，形成一个无形的队列在等待通电话。4.0排队系统仿真基础知识随机性：

顾客到达情况与顾客接受服务的时间是随机的。排队论所研究的排队系统中，顾客相继到达时间间隔和服务时间这两个量中至少有一个是随机的。

排队论又称随机服务理论。4.0排队系统仿真基础知识排队的不一定是人，也可以是物。

如生产线上的原材料，半成品等待加工；因故障而停止运行的机器设备在等待修理；码头上的船只等待装货或卸货；要下降的飞机因跑道不空而在空中盘旋等。服务的也不一定是人，

可以是跑道，自动售货机，公共汽车等。顾客——要求服务的对象。服务员——提供服务的服务者（也称服务机构）。顾客、服务员的含义是广义的。4.0排队系统仿真基础知识服务台顾客到达服务完成后离开单服务台排队系统4.0排队系统仿真基础知识排队系统类型：排队系统类型：服务台2顾客到达服务完成后离开S个服务台，一个队列的排队系统服务台s服务台14.0排队系统仿真基础知识排队系统类型：服务台2顾客到达服务完成后离开S个服务台，S个队列的排队系统服务台s服务台1服务完成后离开服务完成后离开4.0排队系统仿真基础知识服务台1顾客到达离开多服务台串联排队系统服务台s4.0排队系统仿真基础知识排队系统类型：排队系统的描述

实际中的排队系统各不相同，但概括起来都由三个基本部分组成：。输入过程，排队及排队规则和服务机构输入过程顾客总体（顾客源）数：可能是有限，也可能是无限。

河流上游流入水库的水量可认为是无限的；车间内停机待修的机器显然是有限的。到达方式：是单个到达还是成批到达。库存问题中，若把进来的货看成顾客，则为成批到达的例子。4.0排队系统仿真基础知识顾客（单个或成批）相继到达的时间间隔分布：这是刻划输入过程的最重要内容。定常分布（D）：顾客相继到达的时间间隔为确定的。如产品通过传送带进入包装箱就是定常分布。最简流（或称Poisson)（M）：顾客相继到达的时间间隔为独立的，同为负指数分布4.0排队系统仿真基础知识排队及排队规则排队有限排队——排队系统中顾客数是有限的。无限排队——顾客数是无限，队列可以排到无限长（等待制排队系统）。4.0排队系统仿真基础知识有限排队还可以分成：损失制排队系统：排队空间为零的系统，即不允许排队。（顾客到达时，服务台占满，顾客自动离开，不再回来）（电话系统）混合制排队系统：是等待制与损失制结合，即允许排队，但不允许队列无限长。4.0排队系统仿真基础知识排队规则当顾客到达时，若所有服务台都被占有且又允许排队，则该顾客将进入队列等待。服务台对顾客进行服务所遵循的规则通常有：先来先服务（FCFS）后来先服务（LCFS）具有优先权的服务（PS）4.0排队系统仿真基础知识服务机制服务员的数量及其连接方式（串联还是并联）顾客是单个还是成批接受服务服务时间的分布4.0排队系统仿真基础知识排队系统的符号表示：“Kendall”记号：X/Y/Z/W

X表示顾客到达的时间间隔分布

Y表示服务时间的分布

Z表示服务台个数

W表示系统的容量，即可容纳的最多顾客数4.0排队系统仿真基础知识M/M/1/M：表示顾客相继到达的时间间隔服从负指数分布M：表示服务时间为负指数分布1：单个服务台：系统容量为无限（等待制）的排队模型4.0排队系统仿真基础知识M/M/S/KM：表示顾客到达的时间间隔服从负指数分布M：服务时间为负指数分布S：S个服务台K：系统容量为K的排队模型。当K=S时为损失制排队模型；当K=时为等待制排队模型。排队系统的主要数量指标：系统状态：指排队系统中的顾客数（排队等待的顾客数与正在接受服务的顾客数之和）。排队长：系统中正在排队等待服务的顾客数。4.0排队系统仿真基础知识记N(t)：时刻t(t0)的系统状态；pn(t)：时刻t系统处于状态n的概率；c：排队系统中并行的服务台数；n：当系统处于状态n时，新来的顾客的平均到达率（单位时间内到达的平均顾客数）；n：当系统处于状态n时，整个系统的平均服务率（单位时间内可以服务完的平均顾客数）；4.0排队系统仿真基础知识当n为常数时记为；当每个服务台的平均服务率为常数时，记每个服务台的服务率为，则当nc时，有n=c。因此，顾客相继到达的平均时间间隔为1/，平均服务时间为1/，令=/c，则为系统的服务强度。4.0排队系统仿真基础知识pn(t)称为系统在时刻t的瞬间分布，一般不容易求得，同时，由于排队系统运行一段时间后，其状态和分布都呈现出与初始状态或分布无关的性质，称具有这种性质的状态或分布为平稳状态或平稳分布，排队论一般更注意研究系统在平稳状态下的性质。4.0排队系统仿真基础知识排队系统在平稳状态时一些基本指标有：Pn:系统中恰有n个顾客的概率；Ls：系统中顾客数的平均值，又称为平均队长；Lq：系统中正在排队的顾客数的平均值，又称为平均排队长；

T：顾客在系统中的逗留时间；Ws：顾客在系统中的平均逗留时间；Wq：顾客在系统中的排队等待时间；4.0排队系统仿真基础知识某售票所有三个窗口，顾客到达服从指数分布，平均到达率每分钟λ

=0.9（人），服务时间服从负指数分布，平均服务率每分钟μ＝0.4（人），现在设顾客到达后排成一队，依次向空闲窗口购票，其中c=3;λ/μ=2.25,ρ=λ/（cμ）=2.25/3=0.75<1(服务台的利用率）符合条件，带入公式即可M/M/3与M/M/1那个好？414.0排队系统仿真基础知识窗口1μ＝0.4窗口2μ＝0.4窗口3μ＝0.4顾客到达顾客离去窗口1μ＝0.4窗口2μ＝0.4窗口3μ＝0.4顾客到达顾客离去排队λ＝0.9排队λ＝0.3排队λ＝0.3排队λ＝0.3424.0排队系统仿真基础知识服务台空闲的概率顾客必须等待的概率M/M/1M/M/1434.0排队系统仿真基础知识平均顾客数和平均队列长度平均等待时间和逗留时间M/M/1M/M/1M/M/1M/M/1444.0排队系统仿真基础知识M/M/3（一队）M/M/1（三队）服务台空闲的概率P00.07480.25(每个窗口）顾客必须等待的概率P(n>3)=0.570.75平均队列长度Lq1.702.25(每个窗口）平均顾客数Ls3.959.00(全部窗口）平均逗留时间Ws4.3910平均等待时间Wq1.897.5单队比三队有显著的优越性！c=3;λ/μ=2.25,ρ=λ/（cμ）=2.25/3=0.75<14.0排队系统仿真基础知识怎样缩短排队的等待时间？银行的排队叫号机只是有序的组织了顾客，并没有减少等待时间如果能实现知道轮到自己需要等待多少时间，再选择合适的时间来，岂不很好？4.1排队系统仿真实例（1）46输入来源队列服务机构排队系统顾客服务完离开排队系统的三个基本组成部分：输入过程(顾客按照规律到达)；排队规则(顾客按照一定规则排队等待服务)；服务机构

(服务机构的设置，服务台的数量，服务的方式，服务时间分布等)4.1排队系统仿真实例（1）474.1排队系统仿真实例（1）

由于离散事件系统固有的随机性，对这类系统的研究往往十分困难。1）为什么这类系统仿真困难？

经典的概率及数理统计理论、随机过程理论虽然为研究这类系统提供了理论基础，并能对一些简单系统提供解析解，但对工程实际中的大量系统，唯有依靠计算机仿真才能提供较为完整的结果。2）为什么传统的方法无法解决？48单服务台排队系统4.1排队系统仿真实例（2）49假设6个顾客，到达时间间隔是随机的，服务时间也是随机的，如何手工仿真单服务台排队系统。(1)假设

顾客总体（无限）顾客进入等候线或进入服务不会改变人的到达率同时只有一个顾客以随机的方式到达顾客一旦进入等候线最终将得到服务

服务时间服从某一概率分布，并分布不随时间而变化

系统的容量无限的（被服务的人数加上等候的人数）

被服务的规则服务员进行服务的次序（FCFS，先来先服务）

到达和服务描述到达间隔时间分布和服务时间分布描述的整个有效的到达率必须小于最大的服务率4.1排队系统仿真实例（1）501)顾客到达模式用到达时间间隔来描述,可分为确定性到达及随机性到达。随机性到达采用概率分布来描述,最常采用的泊松到达。2)服务模式描述服务台为顾客服务的时间：确定性的,也可能是随机的3)排队规则服务台完成当前的服务后,从队列中选择下一实体的原则

FCFS——先到先服务;LCFS——后到先服务;PS——根据实体的重要程度选择最优先服务者4)服务流程多个服务台,多个队列,如何从某一个队列中选择某一个实体服务,包括实体可否换队及换队规则等4.1排队系统仿真实例（1）（2）排队系统的描述51

一个事件是引起系统状态瞬时变化情况的集合在服务台排队系统中两个可能的事件会影响系统的状态

顾客进入系统（到达事件）

顾客离开系统（离开事件）系统中顾客数以及服务员忙闲状况。4.1排队系统仿真实例（1）5）系统状态52有另一个顾客等待?服务员开始闲从队列中移走一个顾客开始对此顾客服务否是离开事件恰好完成服务的流程服务员忙？顾客进入服务顾客入队等待服务否是到达事件顾客进入系统的流程4.1排队系统仿真实例（1）53队列状态不空空服务员状态忙进入队列进入队列闲不可能进入服务顾客到达时可能的动作队列状态不空空服务员结果忙不可能闲不可能一个服务完成后服务员的结果4.1排队系统仿真实例（1）顾客服务员54

引起系统状态发生变化的行为事件表：管理事件的表时钟：标记事件出现的时间的时钟随机数：事件是随机出现的，为了模仿现实生活中所需的随机性，应用“随机数”来完成4.1排队系统仿真实例（1）6)事件55随机数（number)是在区间（0，1)上独立和均匀分布的；随机数字(digit)是在集合{0，1，2，3，…，9}上均匀分布的随机数字可用来产生随机数；从随机数字表上选取合适的随机数字，在选取的随机数字的左边加上十进制的小数点，可以构成随机数；当用一组过程产生随机数时，他们经常被称为伪随机数。4.1排队系统仿真实例（1）7)随机数56到达事件间隔和时钟时间由掷6个值骰子五次并记录它们的点数来产生用来计算排队系统的6个顾客的到达时间顾客123456到达间隔和时钟时间1)到达时间（3）排队系统仿真过程到达的时钟时间026791557到达间隔时间--241264.1排队系统仿真实例（1）服务时间假设有1，2，3，4个时间单位，假定所有的4个值等可能出现。把4个值预先刻在筹码上，然后，轮回随机抽取筹码，将选到的数据记录下来。排队系统到达间隔时间和服务时间必须匹配顾客123456服务时间4.1排队系统仿真实例（1）2)服务时间：58服务时间213214顾客到达时间（时钟）10223647596153)仿真表仿真表是为单服务台队列设计的。仿真表记录了每个事件出现时的时钟时间。表第2列是到达时间的时钟时间；表第5列记录了每个离开事件的时钟时间；两类事件按照时间顺序排列。强调时钟时间的仿真表4.1排队系统仿真实例（1）开始服务时间（时钟）02691115服务时间（持续）213214完成服务时间239111219597159319事件类型顾客时钟时间到达10离开12到达22离开23到达36到达47离开39到达59离开411离开512到达615离开6195)按时间次序顺序的事件系统中的顾客数612012143356时钟时间4.1排队系统仿真实例（1）4)服务顾客的规则：先进先出22451160某杂货店的收款台顾客随机地分别以1和8分钟的间隔到达，等概率分布；服务时间1至6分钟，等概率分布；模仿20个顾客到达和服务，来分析此系统。到达时间间隔概率累积概率随机数区间10.1250.125001-12520.1250.250126-25030.1250.375251-37540.1250.500376-50050.1250.625501-62560.1250.750626-75070.1250.875751-87580.1251.000876-000到达时间间隔分布(已知表）4.1排队系统仿真实例（2）1到8分均匀分布0到1分均匀分布61服务时间概率累积概率随机数区间10.100.1001-1020.200.3011-3030.300.6031-6040.250.8561-8550.100.9586-9560.051.0096-00服务时间分布(已知表）1到6分均匀分布0到1分均匀分布4.1排队系统仿真实例（2）62顾客随机数字到达间隔时间（分）顾客随机数字到达间隔时间（分）1－－－－1110912913812093137276136075401511473865948815359363093168888792281710618753718212292352194934103023205355根据上述的到达时间间隔分布表确定到达间隔时间4.1排队系统仿真实例（2）63顾客随机数字服务时间（分）顾客随机数字服务时间（分）1844113232101129453744137944533140515172157956794168447915175238674185539895193021038320503根据上述的服务时间分布表产生服务时间4.1排队系统仿真实例（2）6465顾客到达时间间隔到达时间服务时间开始服务时间（分）顾客在队列中等待时间服务时间结束顾客在系统中花费时间服务员空闲时间（分）100404402888109143614144018454115183321605823232025226326264030417834345039548741414045429243455250701034650345370111475336569012148565861130135536148651201465965166670153626654719016870714175501717175347870182737835818019477812483602058283318640826856（13）124184.1排队系统仿真实例（2）仿真结果：1顾客平均等待时间：顾客在队中总等待时间/总顾客数＝56/20=2.8分2顾客必须在队列中等待的概率：等待顾客数/顾客总数＝13/20＝0.653服务员空闲的比例：服务员总空闲时间/仿真运行总时间＝18/86=0.214平均服务时间：总服务时间/顾客总数＝68/20=3.4分4.1排队系统仿真实例（2）66

这个结果可以和服务时间分布的均值进行比较：用服务时间表求分布的期望值：期望服务时间：1(0.10)＋2(0.20)＋3(0.30)＋4(0.25)＋5(0.10)＋6(0.05)=3.2分◆期望服务时间略小于仿真的平均服务时间◆仿真时间越长越接近于E(s)总的服务时间/顾客总数＝68/20=3.4分仿真的平均服务时间:4.1排队系统仿真实例（2）675平均到达间隔时间:

所有到达间隔时间之和/(到达数－1）＝82/19=4.3分期望达到间隔时间略高于平均值，但是，在更长的仿真中，到达间隔时间的均值应接近于理论均值E(A)。分母减去1？分母减去1是因为第一个到达时间假定为出现在时间为0的时刻离散均匀分布求得的均值的期望到达间隔时间，这个均匀分布的端点是a=1和b=8，于是平均值为：E(A)=(a+b)/2=(1+8)/2=4.5分

4.1排队系统仿真实例（2）68

大多数顾客必须等待，而平均等待时间不会过大，服务员没有过多的空闲。6

在队列中等待得顾客的平均等待时间：顾客在队列中等待总时间/在队中等待顾客总数＝56/13=4.3分7顾客消耗在系统中的平均时间：顾客消耗在系统中的总时间/顾客总数＝124/20＝6.2分4.1排队系统仿真实例（2）69SimulationbyHand：Manuallytrackstatevariables,statisticalaccumulatorsUse“given”interarrival,servicetimesKeeptrackofeventcalendar“Lurch”clockfromoneeventtothenext4.1排队系统仿真实例（3）70SomeAdditionalSpecificsfortheSimpleProcessingSystemSimulationclock:variableEventcalendar:Listofeventrecords:[EntityNo.,EventTime,EventType]KeeprankedinincreasingorderonEventTimeNexteventalwaysintoprecordInitially,schedulefirstArrival,TheEnd(Dep.?)Statevariables:describecurrentstatusServerstatusB(t)=1forbusy,0foridleNumberofcustomersinqueueQ(t)Timesofarrivalofeachcustomernowinqueue(alistofrandomlength)4.1排队系统仿真实例（3）71SimulationbyHand:Setup4.1排队系统仿真实例（3）72SimulationbyHand:t=0.00,Initialize4.1排队系统仿真实例（3）73SimulationbyHand:t=0.00,ArrivalofPart114.1排队系统仿真实例（3）74SimulationbyHand:t=1.73,ArrivalofPart2124.1排队系统仿真实例（3）75SimulationbyHand:t=2.90,DepartureofPart124.1排队系统仿真实例（3）76SimulationbyHand:t=3.08,ArrivalofPart3234.1排队系统仿真实例（3）77SimulationbyHand:t=3.79,ArrivalofPart42344.1排队系统仿真实例（3）78SimulationbyHand:t=4.41,ArrivalofPart523454.1排队系统仿真实例（3）79SimulationbyHand:t=4.66,DepartureofPart23454.1排队系统仿真实例（3）80SimulationbyHand:t=8.05,DepartureofPart3454.1排队系统仿真实例（3）81SimulationbyHand:t=12.57,DepartureofPart454.1排队系统仿真实例（3）82SimulationbyHand:t=17.03,DepartureofPart54.1排队系统仿真实例（3）83SimulationbyHand:t=18.69,ArrivalofPart664.1排队系统仿真实例（3）84SimulationbyHand:t=19.39,ArrivalofPart7674.1排队系统仿真实例（3）85SimulationbyHand:t=20.00,TheEnd674.1排队系统仿真实例（3）86SimulationbyHand:FinishingUp平均等待时间：平均队列长度:服务台的利用率:4.1排队系统仿真实例（3）87CompleteRecordoftheHandSimulation生产率零件数最大队列数最大服务时间最大等待时间88Event-SchedulingLogicviaProgrammingClearlywellsuitedtostandardprogrammingOftenuse“utility”librariesfor:ListprocessingRandom-numbergenerationRandom-variategenerationStatisticscollectionEvent-listandclockmanagementSummaryandoutputMainprogramtiesittogether,executeseventsinorder4.1排队系统仿真实例（3）89SimulationDynamics:TheProcess-InteractionWorldViewIdentifycharacteristicentitiesinthesystemMultiplecopiesofentitiesco-exist,interact,compete“Code”isnon-proceduralTella“story”aboutwhathappenstoa“typical”entityMayhavemanytypesofentities,“fake”entitiesforthingslikemachinebreakdownsUsuallyrequiresspecialsimulationsoftwareUnderneath,stillexecutedasevent-scheduling4.1排队系统仿真实例（3）90RandomnessinSimulationTheabovewasjustone“replication”—asampleofsizeone(notworthmuch)Madeatotaloffivereplications:values:Ingeneral,Forexpectedtotalproduction,4.1排队系统仿真实例（3）91ComparingAlternativesUsually,simulationisusedformorethanjustasinglemodel“configuration”Oftenwanttocomparealternatives,selectorsearchforthebest(viasomecriterion)Simpleprocessingsystem:Whatwouldhappenifthearrivalrateweretodouble?CutinterarrivaltimesinhalfRerunthemodelfordouble-timearrivalsMakefivereplications4.1排队系统仿真实例（3）92Results:Originalvs.Double-TimeArrivalsOriginal–circles○Double-time–triangles△Replication1–filledinReplications2-5–hollowNotevariabilityDangerofmakingdecisionsbasedonone(first)replicationHardtoseeiftherearereallydifferencesNeed:

Statisticalanalysisofsimulationoutputdata4.1排队系统仿真实例（3）93

系统仿真是系统运行的快速拍照，是系统运行过程真实的再现。有人又叫快速摄影技术。在复杂系统中，每一时刻都有若干事件发生，有多个系统状态变量在变化，如何推进仿真钟，使仿真能完整、准确的记录这一复杂过程？4.1排队系统仿真实例（3）94（1）实体：构成系统的各种元素（不仅仅是物理单元）临时实体在系统中只存在一段时间的实体。这类实体由系统外部到达系统,通过系统，最终离开系统。永久实体永久驻留在系统中的实体。只要系统处于活动状态,这些实体就存在，或者说，永久实体是系统处于活动的必要条件。临时实体按一定规律不断地到达（产生）,在永久实体作用下通过系统，最后离开系统，整个系统呈现出动态过程。1.基本概念4.2离散事件系统仿真的一般原理95成分与实体的区别：概念相同，成分是模型的组成元素；实体是系统的组成元素主动成分：可主动产生状态变化的成分被动成分：只在主动成分作用才产生状态变化的成分仿真个体：在实体中流动，并且在各道服务工序停留接受服务的单个实体仿真资源：系统对个体提供服务的物资手段，如超市的收银员4.2离散事件系统仿真的一般原理96Page97（2）属性：实体所有的特性实体可能具有若干特征，但并不是所有的特征都被称为仿真系统的实体属性

状态变量：代表仿真模型里反映系统变化特征的变量单服务台系统可以定义两个状态变量：

服务者状态：空和闲

等候服务的个体数量：0－N4.2离散事件系统仿真的一般原理97（3）事件引起系统状态发生变化的行为，系统是由事件来驱动的。

顾客到达为一类事件，顾客到达使系统状态——服务员的“状态”可能从闲变到忙（如果无人排队)，或者另一系统状态——排队的顾客人数发生变化（队列人数加1)。

顾客离去为一类事件，顾客接受服务完毕后离开系统服务台“状态”由忙变成闲。事件表：对系统中的事件进行管理的表，表中记录每一发生了的或将要发生的事件类型，发生时间，以及与该事件相联的实体的有关属性等等。系统事件：系统中固有事件。程序事件：用于控制仿真进程。4.2离散事件系统仿真的一般原理98（4）活动

用于表示两个可以区分的事件之间的过程,它标志着系统状态的转移。顾客的到达事件与服务开始事件之间可称为一个活动（5）进程进程由若干个事件及若干活动组成,一个进程描述了它所包括的事件及活动间的相互逻辑关系及时序关系。进程排队活动服务活动顾客到达事件服务开始事件服务结束事件图10.1事件、活动、进程三者关系示意图4.2离散事件系统仿真的一般原理99（6）仿真钟离散事件动态系统的状态本来就只在离散时间点上发生变化，因而不需要进行离散化处理。由于引起状态变化的事件发生时间的随机性，仿真钟的推进步长则完全是随机的两个相邻发生的事件之间系统状态不会发生任何变化，因而仿真钟可以跨过这些“不活动”周期,仿真钟的推进呈现跳跃性，推进速度具有随机性。时间控制部件是必不可少的,以便按一定规律来控制仿真钟的推进。4.2离散事件系统仿真的一般原理100（7）统计计数器 某一次仿真运行得到的状态变化过程只不过是随机过程的一次取样,它们只有在统计意义下才有参考价值。 在仿真模型中,需要有一个统计计数部件,以便统计系统中的有关变量。4.2离散事件系统仿真的一般原理1014.2离散事件系统仿真的一般原理系统银行交通生产通讯存储实体顾客乘车的人机器信号仓库属性帐目解算起点站终点站速度，能力，故障率长度，终端容量活动存款旅行焊接，冲压传输退回事件到达到站到达故障到达终端需求状态变量等待得顾客人数在每站等待的乘车人数，在旅行的人数机器的状态（忙，空闲或故障）等待传输数目存储量，欠付需求102

仿真钟推进方法有两大类：按下一最早发生事件的发生时间推进,亦称为事件调度法，另一类是固定增量推进方法。

为第个与第个顾客到达之间的间隔时间;=服务员为第i个顾客服务的时间长度

=第i个顾客排队等待的时间长度;

为第i个顾客离去的时间;=第i个顾客到达的时间; =第i个任何一类事件发生的时间;=第i个事件发生时的队长; =第i个事件发生时服务员的状态,

其中=1表示忙,=0表示闲。例10.2单服务台排队系统,如单窗口的售票站。设2.仿真钟推进4.2离散事件系统仿真的一般原理(1)事件调度法(EventScheduling)103Page104顾客离去经过Si服务员空闲否服务完毕开始服务

是顾客到达(时间间隔)排队等待否图10.2

单服务台仿真模型4.2离散事件系统仿真的一般原理104若定义如下系统事件类型:

类型1

顾客到达事件

类型2

顾客接受服务事件

类型3

顾客服务完毕并离去事件定义程序事件为:

仿真运行到150个时间单位(分钟)结束假定已经得到到达时间间隔随机变量的样本值为:

系统初始状态:4.2离散事件系统仿真的一般原理105时间事件服务员状态排队长度0仿真开始0015顾客1到达1047顾客2到达1158顾客1服务完毕0158顾客2接受服务1071顾客3到达1194顾客2服务完毕0194顾客3接受服务10............150仿真结束4.2离散事件系统仿真的一般原理106Page1074.2离散事件系统仿真的一般原理

为第个与第个顾客到达之间的间隔时间;=服务员为第i个顾客服务的时间长度

=第i个顾客排队等待的时间长度;

为第i个顾客离去的时间;=第i个顾客到达的时间; =第i个任何一类事件发生的时间;=第i个事件发生时的队长; =第i个事件发生时服务员的状态,

其中=1表示忙,=0表示闲。

b0b1b2b3b4b5b6b7b8b9t0t1t2t3

t4

t5

150

A1A2A3A4A5S1S2S3S4D2D3D4D5153224402243363428C158C294C3128C4156112317234771111133107事件调度法仿真钟推进初始值:TIME= 1）下一个最早发生事件：为第1号顾客到达(A1),发生时刻为即： 因，仿真钟推进到,然后处理该事件。

4.2离散事件系统仿真的一般原理——仿真的发动S1b0b1t0t1

c1

150

A1154358因为是到达事件,且,立即服务,即接受服务，服务台状态由变为则其离去时间：该顾客服务时间为1082）下一个最早发生事件：仿真钟推进到，处理该到达事件：4.2离散事件系统仿真的一般原理b0b1b2t0t1t2

c1

A1A2S1D2因为从而队长该顾客开始等待时间为因

该到达顾客只好排队等待仍是到达事件(A2)435832151094.2离散事件系统仿真的一般原理其离去时间S1D2b0b1b2b3b4t0t1t2

t3

c2

A1A2A3处理第1号顾客的离去事件,包括：统计服务人数;观察队列中是否有顾客等待,目前则该顾客进入服务,同时要计算其排队等待的时间

修改队长该顾客的服务时间：

＝11943）下一个最早发生事件：是第1号顾客离去事件,

因下一个到达事件发生时间为：

从而 仿真钟推进到t3=t2+A3=47+24=71>C1153224584371S21104）下一最早发生事件：由因而下一事件应是到达事件(A3),仿真钟推进到依次下去,下到下一事件为仿真结束的程度事件为止。S1S2D2D3b0b1b2b3b4b5b6t0t1t2c1t3

c2t4

A1A2A3A4b0b1b2b3b4b5b6b7b8b9t0t1t2c1t3

c2

t4

c3t5

150

A1A2A3A4A5S1S2S3S4D2D3D4D54.2离散事件系统仿真的一般原理C2>t3111(2)固定增量时间推进

选择适当的时间单位T做为仿真钟推进时的增量,每推进一步进行如下处理:该步内若无事件发生,则仿真钟再推进一个单位时间T;若在该步内有若干个事件发生,则认为这些事件均发生在该步的结束时刻。

为便于进行各类事件处理，必须事先规定当出现这种情况时各类事件处理的优先顺序。4.2离散事件系统仿真的一般原理112缺点：仿真钟每推进一步,均要检查事件表以确定是否有事件发生,增加了执行时间;

任何事件的发生均认为发生在这一步的结束时刻,如果T选择过大,则会引入较大的误差;

要求事先确定各类事件的处理顺序,增加了建模的复杂性。

主要用于系统事件发生时间具有较强周期性的模型4.2离散事件系统仿真的一般原理113开始结束正确否正确否是是确定仿真算法输出仿真结果并分析否系统建模运行仿真程序建立仿真模型设计仿真程序否1.系统建模如何由观测数据确定随机变量的分布和参数？

如何产生所需求的随机变量？2.确定仿真算法采用什么方法仿真（仿真策略)？3.建立仿真模型建立计算机模型（变量定义及程序流程）描述系统状态转移(事件、活动和进程等）

4.设计仿真程序采用高级语言编程实现，掌握各种语句采用仿真语言编程实现，掌握各种语句5.运行仿真程序仿真发动，进行仿真

6.仿真结果输出与分析仿真结果的可信性如何?如何提高仿真结果的置信度?每次仿真运行所得到的结果仅仅是随机变量的一次取样1144.2离散事件系统仿真的一般原理随机数：随机变量的样本取样值均匀分布的随机数：随机变量x在其可能值范围中的任一区间出现的概率正比于此区间的大小与可能值范围的比值。(0，1)均匀分布随机数：在各种分布的随机数中，最常用和最重要的是在(0，1)区间上的均匀分布随机数。4.3随机数发生器4.3

随机数发生器

随机数发生器：产生[0,1]区间上均匀分布的随机变量,亦称为随机数发生器。其它各类分布，如正态分布，分布，分布，泊松分布等，可以用某种方法对这种均匀分布进行某种变换来实现1）随机性（randomness)

伪随机数序列应当具有独立性、均匀性，并具有与真实随机数具有相同的数字特征，如期望、方差等。4.3随机数发生器1.随机数特点或者性质？2）长周期（LargePeriod)

由于随机发生器都是基于准确的、确定性的公式而设计的，所以产生的随机数序列最终不可避免得回到它的起点，并且重复以前出现过的序列，其中无重复随机数序列的长度称为周期。希望随机数发生器生成的随机数序列具有较长的周期，从实用角度来看，不能在短期内出现重复，即仿真系统运行期间尽量不出现随机序列重复的现象。4.3随机数发生器3）可重现性（Reproducibility)再现同样的随机数序列当我们调试一个仿真系统时，随机数发生器要求能准确地多次再现同样的随机数序列。生成不同以往的随机序列根据分析人员的需要，随机数发生器既要能再次生成同样的随机序列，又要能生成不同以往的随机序列。4.3随机数发生器4）计算效率高（computationalefficiency)

时间尽量的少由于有时仿真系统在短期内需要大量的随机数，所以随机数发生器要求生成每个随机数所花费时间尽量的少。占用计算机内存尽量少不会占用过多的计算机内存，特别是可视化仿真系统的运行时，有限的内存是非常宝贵的。4.3随机数发生器Entertainment

娱乐Gambling赌博

Lottery,luckydraw抽奖Games游戏Cryptography密码学KeygenerationComputersimulation仿真Softwaretesting软件测试GeneratingtestingdataRandomizedalgorithms随机化算法

Avoidingworstcases2、随机数发生器的应用4.3随机数发生器1)手工方法抽签、掷骰子、旋转圆盘等优点：简单；缺点：效率低。4.3随机数发生器3、随机数的生成方法1222)表格法利用某种手段生成的随机数序列以表格形式存入计算机，供给仿真时调用。优点：直观、简单；缺点：准备表格不方便，每次对随机数进行一次读操作非常浪费时间，浪费存储空间。4.3随机数发生器4.3随机数发生器3)物理方法将物理随机发生器安装在计算机上，把具有随机性质的物理过程变换为随机数。缺点：不能重复生成与原来完全相同的随机数，故无法核对计算结果，且生成过程复杂。1244)数学方法按照一定的算法（递推公式）来生成“随机”序列。只要给定一个初始值（称为种子值），当调用该算法时，即可以按确定的关系计算出下一个“随机”数，多次调用该算法，就可以生成一个“随机”序列。4.3随机数发生器（1）中值平方法第一个随机数发生器，20实际40年代由VonNeumann和Metropolis提出的。

1）从一个四位正整数Z0开始，将Z0平方得到一个八位数（如果需要，在它的左边附加几个零使之成为八位数），

2）取这个八位数的中间四位数作为下一个四位数Z13）同样，求得Z2，Z3，…，Zi4）在每个Zi个的左边加上小数点，从而得到一个[0,1]的均匀的随机数序列U1，U2，…,Ui，4.3随机数发生器JohnvonNeumann1903-19574、随机数发生器1261)一旦退化为零，该序列将永远停留在零上2)不可避免的具有周期性iZiUiZi20342311716929171690.716951394561239450.394515563025356300.563031696900469690.696948566961556690.566932137561例：取Z0＝34234.3随机数发生器obsolete!缺点：127（2）线性同余发生器(linearCongruentialgenerator)是第个随机数为乘子C为增量,为模数称为随机数源或种子,均为非负整数。满足:为了得到[0,1]区间上所需要的随机数可令:莱默尔（Lehmer）在1951年提出4.3随机数发生器最简单,最常用a=0，为加同余C=0，为乘同余其余为混合同余128例:

观察的线性同余发生器。

iZiUiiZiUi071090.563160.3751100.000210.0631230.188380.5001320.1254110.68814130.8135100.6251540.250650.3131670.4387120.7501760.3758150.9381810.0639140.8751980.5004.3随机数发生器1294.3随机数发生器1）缺点：设则…1304.3随机数发生器(modm)确定,则就完全确定下来了。一旦只要谨慎选取还是可以达到近似[0,1]均匀随机数的效果实质上完全不是随机的由于

不随机1314.3随机数发生器132是区间上的整数,那么由得到的

因此，线性同余随机发生器中模数m一般非常大，如109或者更大，这样可以使[0,1]中的取值点变得非常密集。线性同余随机发生器常常取m≥109仅仅是有限个数,即为0,而不可能位于这些数值之外，也不能取介于两个数值之间的数。由于4.3

随机数发生器

取值有限性

(modm)1334.3随机数发生器仅仅是有限个数,即为0,而不可能位于这些数值之外，也不能取介于两个数值之间的数。所以，随机数序列不可避免出现相同的元素

取值周期性

不安全公式容易从输出中反求出来134c)由计算机运行时本身带有的随机性事件来生成2）如何选择种子？数值多少为好？人工设置，随机性基本保证了,效率太低 a)b)由计算机系统时钟生成，因为系统时钟是不断推进的，所以总能取到不同的种子，目前的开发语言大都可以读取系统时钟，精确到毫秒，我们从年、月、日、时、分、秒和毫秒中抽取几位数，拼凑一起。人们对线性同余发生器进行了大量深入的研究，并在它的基础上扩展出多种改进的发生器4.3随机数发生器1353）特点:

4.3随机数发生器值确位于[0,m-1]区间上，位于[0,1]区间内a)取值有限性适当选择,可使循环产生,取何值,其循环顺序是相同的。如果则称该发生器具有满周期。循环一次称为发生器的一个周期,记为,无论b)周期性iZiUiiZiUi071090.563160.3751100.000210.0631230.188380.5001320.1254110.68814130.8135100.6251540.250650.3131670.4387120.7501760.3758150.9381810.0639140.8751980.500M=16;P=161364.3随机数发生器,可保证在[0,m-1]区间上一个周期内每个适当地选择整数正好出现一次,从而保证了均匀性;c)均匀性的均匀性,要求加大，为提高足够大,且发生器具有满足周期,这就足够近似于真正的[0,1]区间上的均匀分布U(0,1)。那么可以预计,所得到的在[0,1]区间上是均匀分布的,且取值是相当密的。d)[0,1]区间上的均匀分布U(0,1)1374.3

随机数发生器

（1）随机数发生器都采用递推算法。（2）计算机是具有完全确定性的机器，通过某种固定不变近似地生成随机数。其实这些数值并非真正的“随机”。

为什么随机数发生器是伪随机数？

伪随机数表现出某种程度的“随机性”，满足仿真系统能够对随机变量统计特性的要求，所以，在实际应用中假定这些数值是随机数。如果算法选择得合适,由这种算法得到的数据统计检验后能具有较好的统计特性(如均匀性,独立性等),则将这种伪随机数用于仿真仍然是可行的。4.3随机数发生器为什么伪随机数可以用来仿真？（pseudorandomnumber)139

随机数发生器的设计方法，也就是如何生成具有良好统计特性的[0,1]均匀分布随机数。

[0,1]均匀分布随机数是生成其它分布类型的随机变量的基本要素。因此，统计上可靠的[0,1]均匀分布随机数发生器非常重要。4.4随机变量产生的原理140如何符合分布的随机变量？设随机变量x的分布函数为1.反变换法（inversetransformmethod）先产生在[0,1]区间上均匀分布的独立随机变量即为所需要的随机变量:4.4随机变量产生的原理连续随机变量的反变换法由反分布函数得到的值141的取值范围为[0,1]；原理说明：F(x)为连续单调增的函数F(x)为X的分布函数f(x)为X的概率密度函数证明：x服从符合原来给定的密度分布函数4.4随机变量产生的原理142？在[0,1]上均匀分布的独立随机变量作为的取值规律；从而随机变量x在区间内出现的概率密度函数当趋于0时,其概率密度函数就等于即符合原来给定的密度分布函数,满足正确性要求内的样本个数的概率就是落在4.4随机变量产生的原理需要的随机变量143的平均值为例12.1

设随机变量x是[a,b]上均匀分布的随机变量,即概率密度函数：

由可得到的分布函数:

用随机数发生器产生U(0,1)随机变量令 可得:4.4随机变量产生的原理144

在使用之前必须先求出分布函数的反函数，但是，有些分布函数（如正态分布、分布等）的解析的反函数表达式是求不出来的。4.4随机变量产生的原理连续随机变量的反变换法缺点?

可以利用数值计算的方法求得F-1的近似值，或者用幂级数展开来求得F-1的近似表达式的方法来使用反变换法。1452.舍选法（acceptance-rejectionmethod)直接法：直接面向分布函数，以反变换法为基础舍选法：当反变换法难于使用时(随机变量的分布函数不存在封闭形式)。舍选法的实质：实际是提出一定的检验条件，从许多均匀分布的随机数中选出一部分，使其具有给定分布的随机变量，它可以用于产生任意有界的随机变量

用舍选法产生服从密度函数为r(x)的随机变量，因此，定义t(x)的时候，最好是能够使密度函数r(x)的随机变量容易用反变换法求取。4.4随机变量产生的原理因为

首先，定义一个与原分布密度函数f(x)有相同取值域的函数t(x),使之覆盖原分布函数，即对于所有f(x)取值域的x，都有t(x)≥f(x)。所以，通常t(x)不是一个密度函数，但是，显然函数是一个密度函数，（1）若独立地产生两个[0,1]区间内均匀分布的随机变量,即,否则舍弃直观意义：的取值范围为[0,1]。的密度函数为的最大值为C,设随机机变量是在[0,C]区间内均匀分布的随机变量（2）则成立,则选取为所需要的随机变量若:求的值,（3）以4.4随机变量产生的原理产生随机变量的步骤如下：舍选法的解释：若该点位于曲线下面,则认为抽样成功。若x取值仅在（0，1）区间，则该积分值可视为分布函数值，就是所需产生的随机变量。的纵坐标为,横坐标为在1×C这块矩形上任投一点下的面积可视为在（0，1）区