第四章 系统仿真

第四章系统仿真第1页，共52页，2023年，2月20日，星期三二、系统仿真的过程系统仿真过程包括以下五步：1、描述问题，明确需要解决的问题和相关变量，建立仿真模型。2、制定仿真计划，确定需要变化的变量以及仿真运行的顺序。3、画出仿真流程图并编写仿真程序。4、验证模型，若在相同条件下，用仿真模型进行试验与实际系统工作的结果一致，则确定所选仿真模型可用。5、用仿真模型进行系统测试。第2页，共52页，2023年，2月20日，星期三三、离散事件系统仿真和连续事件系统仿真系统仿真根据被研究系统的特性可以分为离散事件系统仿真和连续事件系统仿真。1、离散事件系统。离散事件系统是状态变量只在一些离散的时间点上发生变化的系统。这些离散的时间点称为特定时刻。系统在特定时刻发生变化是因为有事件发生，在其它时间，系统状态保持不变。离散事件系统的一个主要特征是随机性。随机性是指事件的产生时刻、事件所引起的系统变化等均具有随机性。比如，每一个到达、离开超市的顾客都属于事件，而顾客到达和离开的时间是随机变量。第3页，共52页，2023年，2月20日，星期三2、连续事件系统。连续事件系统:指系统中的状态变量随时间连续变化的系统。由于连续系统的关系式要描述每一个实体属性的变化速率，所以连续事件系统的数学模型通常由微分方程组成。当系统比较复杂时，所建的数学模型经常是无法求解的，这时仿真方法成为解决这类问题的重要方法。第4页，共52页，2023年，2月20日，星期三§4-2离散事件系统仿真—排队系统一、顾客与顾客源

顾客:指任何一种需要系统对其服务的实体，顾客可以是人，也可以是零件、机器、文件和提货单等物。顾客源:又称顾客总体，是指潜在的顾客总数。分为有限和无限两类第5页，共52页，2023年，2月20日，星期三二、顾客到来方式1、到来方式是指顾客达系统的方式。是单个到达还是成批到达，用顾客相继到达的间隔时间来描述。时间间隔的分布方式主要有以下几种。（1）定长分布(D型到来方式)（2）负指数分布(M型到来方式)（3）k阶爱尔朗到来方式(Ek)（4）任意到来方式(G)第6页，共52页，2023年，2月20日，星期三2、随机变量的产生方法在排队系统中，顾客到来时间间隔和服务时间都属于随机变量，其设置合理与否直接关系到排队系统仿真结果的可靠性和真实性。随机变量的产生方法是在随机数产生的基础上，对这些数据进行相应的处理，使之符合预先假定的到来方式或时间分布函数。(1)随机数的产生第7页，共52页，2023年，2月20日，星期三线性同余法：该方法由Lehmer于1951年提出，是目前在离散系统仿真中应用最广泛的伪随机数产生方法。其递推关系式为：Xi+1=（aXi+c）modm（i=0，1，…）式中：X0为种子值；Xi为第i个中间值；a为乘数常数c为增量常数；m为模（取充分大的正整数）由上式可以产生0到m-1之间的整数序列X1，X2,…。则（0，1）区间的随机数Ri可由Ri=Xi/m得到。例如：令X0=20，a=14，c=49，m=100X1=（20╳14+49）mod100=29R1=29/100=0.29X2=（29╳14+49）mod100=55R2=55/100=0.55X3=（55╳14+49）mod100=19R3=19/100=0.19X4=（19╳14+49）mod100=15R4=15/100=0.15……运用该方法的关键是合理地选取X0、a、c及m值。第8页，共52页，2023年，2月20日，星期三(2)随机变量的产生方法常用的方法有逆变换法、直接变换法、接受­—拒绝法等。逆变换法是离散系统中获取采样值的基本方法，可处理负指数分布、均匀分布、韦泊分布等多种分布方式。①确定或计算需要产生的随机变量t的累积分布函数（到来方式和时间分布函数已给出的，就直接使用，如果给出的是概率密度分布，则要计算累积分布函数），令为F（t）。②在t的取值范围内，置F（t）=R，其中R为产生的（0，1）区间的随机数。③解方程F（t）=R，用R来表示t，即可得到所需的随机变量。第9页，共52页，2023年，2月20日，星期三负指数分布的概率密度函数为：λe-λtt≧0f（t）=0t≤0计算其累积分布函数为：1-e-λtt≧0F（t）==0t≤0令F（t）=R，当t≧0时，1-e-λt=R。t=F-1（R）=（-1/λ）ln（1-R）。ti=F-1（Ri）=（-1/λ）ln（Ri）

R1=0.29t1=(-1/λ)ln（R1）=-10ln（0.29）=12R2=0.55t2=6R3=0.19t3=17R4=0.15t4=22第10页，共52页，2023年，2月20日，星期三三、服务机制包括服务台的数量及其连接形式，服务台之间是串联服务、并联服务还是网络服务；顾客是单个还是成批接受服务；服务时间的分布。1、服务台分布方式第11页，共52页，2023年，2月20日，星期三2、服务时间的分布主要有以下几种：（1）定长分布（D）：每位顾客接受服务的时间是一个确定的常数。（2）负指数分布(M)：每个顾客接受服务的时间相互独立，具有相同的负指数分布。（3）k阶爱尔郎分布(Ek)：每个顾客接受服务的时间服从k阶爱尔郎分布。（4）正态分布(T)：在多种随机因素的影响下，服务时间围绕某一常数上下波动时，可以用正态分布来描述该服务时间。（5）服务时间依赖于队长的情况：排队顾客越多，服务速度越快，服务时间越短。第12页，共52页，2023年，2月20日，星期三四、排队及排队规则排队分为有限排队与无限排队两类，若系统的空间是有限的，当系统被占满时，再来的顾客将不能进入该系统；无限排队的队列可以无限长，顾客无论何时到达系统均可进入系统队列或接受服务。排队规则为顾客接受服务的次序与规则。1、损失制：这种排队规则实际上是不允许排队，如果顾客到达系统时所有服务台均被占用，则顾客自动离去，不再回来，这部分顾客就被损失掉了。电话系统的排队规则即为损失制。第13页，共52页，2023年，2月20日，星期三2、等待制：顾客到达系统时均可以进入系统，系统服务台均非空时则该顾客进入队列等待，且队列中的顾客数可以是无限的。服务台对顾客进行服务遵循的规则一般有：（1）先入先出(FCFS)：按顾客到达先后次序接受服务，先到先接受服务，这是最常见的服务规则。（2）后入先出(LCFS)：与先进先出正好相反。后到者先接受服务。如在情报系统中，后到达的信息往往更加重要，应首先被分析和利用。（3）具有优先权的服务(PS)：服务台根据顾客的优先权进行服务，如病危的患者应优先接受治疗。另外，还有随机服务、最短处理时间先服务等服务规则。第14页，共52页，2023年，2月20日，星期三3、混合制：该规则是损失制与等待制的结合，指允许排队但队长有限。通常有以下两种情况：（1）队长有限：若系统的最大允许队长（顾客数）为N，当新顾客到达该系统时，系统中的顾客数（队长）小于N，该顾客进入队列等待服务，否则，便离开系统，不再回来。如宾馆的床位是有限的，餐馆的就餐位是有限的。（2）逗留时间（等待时间与被服务时间之和）有限：若逗留时间超过允许最长逗留时间，则顾客自动离去。第15页，共52页，2023年，2月20日，星期三五、排队系统符号表示X/Y/Z/A/B/CX表示顾客到达时间间隔的分布(到来方式)Y表示服务时间的分布Z表示服务台个数A表示系统容量,即可容纳的最大顾客量B表示顾客源的数量C表示服务规则例如:M/M/1/∞/∞/FCFS表示顾客到达时间间隔与服务时间服从负指数分布,单服务台,系统容量与顾客源无限(等待制)，排队规则为先进先出的排队模型。如果记号中省略后三项时，即表示X/Y/Z/∞/∞/FCFS的情形，则M/M/1/∞/∞/FCFS可表示为M/M/1；M/M/S/K表示到来方式与服务时间服从负指数分布，服务台为S个，系统容量为K。第16页，共52页，2023年，2月20日，星期三§4-3离散事件系统仿真建模原理一、建模原理建立仿真模型的方法，如何在仿真模型中体现真实系统的行为。事件调度法、活动扫描法和进程交互法。

1、事件调度法：定义事件并确定事件发生时系统状态的变化，按时间顺序执行事件发生时有关的逻辑关系，它直接对事件加以调度，其仿真流程如下。第17页，共52页，2023年，2月20日，星期三第18页，共52页，2023年，2月20日，星期三2、仿真钟的确定：（1）仿真钟是仿真进程的时间控制部件，仿真模型则在仿真钟的时间坐标中运行。仿真钟在模型中是用正整数表示的变量，它的数值表示仿真模型运行的时刻。在真实系统中，时间有秒、分、时、天和季等多个计量单位，而仿真钟根据不同的仿真模型只设定一个计量单位，它可以表示真实系统的任何一个时间计量单位。如要仿真某售票系统从早8：00-12：00的半个工作日的系统运行过程，则半个工作日可以表示为4个小时，240分或14400秒。如果仿真模型中设定的仿真钟的计量单位为秒，则仿真时刻从0-14400，如果以分为单位，则仿真时刻从0-240。第19页，共52页，2023年，2月20日，星期三第一种推进方法为事件调度法，它以事件的发生作为仿真钟推进的依据。该方法只设立一个仿真钟，即系统仿真钟。当有事件发生时，系统仿真钟推进到该事件发生的时刻，并立即计算该事件的直接后续事件发生的时间。然后从众多后续事件中挑选一个最早发生的事件的发生时刻作为仿真钟推进的时间点。（2）仿真钟的推进在仿真模型中，仿真钟推进的时间不必一定为真实系统的时间单位。仿真钟一次可以推进执行若干条程序的时间，它比真实系统时间进程快的多，所以仿真试验也具有省时的特点。排队系统仿真模型的仿真钟推进方法有两种。第20页，共52页，2023年，2月20日，星期三第二种推进方法为步进式推进法。采用这种方法的仿真钟从开始就按某一时间单位T等距推进，每次推进时系统都要扫描所有的活动。检查在该仿真时间段内有无事件发生，若无，则继续推进仿真钟，若有，则按规定的优先顺序执行事件。二、离散事件系统（排队系统）的性能指标研究排队系统的目的是通过了解系统运行的状况，对系统进行调整和控制，合理地解决顾客等待时间与服务台空闲时间的矛盾，使系统处于最优运行状况。描述排队系统运行状况的主要性能指标有

第21页，共52页，2023年，2月20日，星期三2、队长（L（t））、排队长（Lq（t））、平均队长（L）与平均排队长（Lq）队长为系统（或某级工作站）中的顾客总数，排队长为系统（或某级工作站）中的等待服务的顾客总数，这两个指标都为随机变量，在实际应用过程中，我们经常考虑的是它们的平均值。务台的服务强度ρ：λ为单位时间内来到系统的平均顾客数，μ为单位时间内被服务的顾客数。一般情况下，ρ<1。其中，Qi为Ti-1—Ti时间内等待服务的顾客数；Pi为该时间段内接受服务的顾客数。第22页，共52页，2023年，2月20日，星期三3、等待时间（Wq（i））、逗留时间（W（i））、平均等待时间（Wq）与平均逗留时间（W）：等待时间是指从顾客到达系统到接受服务这段时间；每位顾客逗留时间是指该顾客等待时间与服务时间之和，这两个变量亦为随机变量，若n为已接受服务的顾客数，则这两个随机变量的平均值可以用下面的公式计算。第23页，共52页，2023年，2月20日，星期三4、忙期与闲期忙期是指服务台连续忙的时间，为随机变量，是服务机构最为关心的指标，它关系到服务台的服务强度。与忙期相对的是闲期，即服务台全部处于空闲状态的时间段。在排队系统中，忙期与闲期总是交替出现。除了上述性能指标外，具体的排队系统还可以根据不同的要求使用其它性能指标，如顾客损失率、最长队列等。第24页，共52页，2023年，2月20日，星期三事件：排队系统中每个顾客的到达，开始接受服务，服务结束后离开是引起系统状态变化的事件。1、单服务台排队系统是排队系统中最简单的结构形式，该系统只有一个服务台，如单人理发店、只有一台机床的加工系统、只有一个医生的诊所或只有一个打字员的文件处理系统等都属于单服务台排队系统。该系统通常假定第I个顾客服务结束时刻是第I+1个顾客服务开始的时刻。则单服务台排队系统仿真模型有两类事件：顾客到达事件和服务结束后离开事件。§4-4排队系统仿真第25页，共52页，2023年，2月20日，星期三案例1：单人修理店（M/M/1）为例，令仿真钟仿真区间为0-240，即真实系统中的半个工作日；λ=μ=0.15人/分钟。顾客到达为第一类事件，顾客离开为第二类事件。（1）采用“事件调度法”进行仿真；仿真钟的推进亦采用事件调度法。（2）确定顾客到达时间间隔及服务台服务时间随机变量。到达时间间隔：X0=36；a=47；c=45；m=100服务时间：X0=27；a=38；c=45；m=100第26页，共52页，2023年，2月20日，星期三服务时间:1062418190240310时间间隔:8310052119627118顾客12345678910顾客12345678910第27页，共52页，2023年，2月20日，星期三仿真钟事件类型顾客到达时间下一顾客服务台状态排队长系统顾客数服务开始等待时间服务时间离开时间逗留时间已服务人数闲期0————闲00—————001108闲-忙01001010100812811忙12102616801022——忙01—————111131121忙12165218711622——忙01—————21823——忙-闲00—————321142121闲-忙01210425433时间间隔83100521196271服务时间10624181902403101L=(1*8+2*2+1*1+2*5+1*2+0*3)/21=1.2人Lq=(0*8+1*2+0*1+1*5+0*2+0*3)/21=0.3人第28页，共52页，2023年，2月20日，星期三（3）仿真结果计算如下：平均队长：Lq=1.2人平均排队长：L=0.3人系统服务强度ρ=λ/μ=1平均等待时间=顾客总等待时间总和/总顾客数=7/4平均逗留时间=顾客总逗留时间/总顾客数=29/4服务台总闲期=3分闲期所占百分比=3/21=3.33%已服务人数3人2、多服务台排队系统仿真设有一个多级多服务台系统（M/M/4），λ=μ=0.1

第29页，共52页，2023年，2月20日，星期三（1）事件类型该系统共有三类事件，事件类型1—到达系统（到达工作站1）。事件类型2—离开工作站1，进入工作站2。事件类型3—离开系统（离开工作站2）。（2）事件调度、处理规则若顾客到达系统（到达第一个工作站）的时间与顾客离开时间相同，先处理离开事件；若不同顾客离开不同工作站时间相同，则按工作站编号由小到大处理事件。若同一工作站内顾客离开不同服务台时间相同，按服务台编号由小到大处理。第30页，共52页，2023年，2月20日，星期三（3）采用“事件调度法”进行仿真；仿真钟的推进亦采用事件调度法。（4）确定顾客到达时间间隔及服务台服务时间。到达时间间隔：X0=36；a=47；c=45；m=100服务时间台1-1：X0=27；a=38；c=45；m=100服务时间台1-2：X0=29；a=17；c=43；m=100服务时间台2-1：X0=30；a=27；c=33；m=100服务时间台2-2：X0=20；a=14；c=49；m=100到来方式831005211962711835133台1-11062418190240310161512台1-2382812151741355172027台2-181372312415611511723台2-21261719530第31页，共52页，2023年，2月20日，星期三仿真钟事件类型工序号顾客到达站1时间到达站2时间下一到达时间1-1状态1-2状态站1排队长站1顾客数2-1状态2-2状态站2排队长站2顾客数服务开始时间等待时间服务时间离开站1时间离开站2时间逗留站1时间逗留站2时间已服务人数各服务台闲期0——————闲闲00闲闲00———————001110—8闲-忙闲01闲闲00001010—10—081128—11忙闲-忙02闲闲0080311—3—010221—10—忙-闲忙01闲-忙闲011008—18—8011222—11—闲忙-闲00忙闲-忙0211012—23—120第32页，共52页，2023年，2月20日，星期三§4-4蒙特卡罗法蒙特卡罗法又称为统计试验法、随机模拟法，是一种通过随机模拟试验求得问题近似解的方法。该方法的主要奠基人和代表是著名学者冯·诺依曼（VonNeumann）教授。蒙特卡罗法是以摩纳哥的MountCharles这座世界著名赌城的名字来命名的。第33页，共52页，2023年，2月20日，星期三一、基本原理设随机投点在面积为1的正方形区域内出现的机会是均等的，随机投点的总次数为N，而M表示落在阴影区的次数，当投点次数足够多时，则比值M/N就是点落在阴影区的概率p，而概率p为所求面积S与正方形面积的比值，第34页，共52页，2023年，2月20日，星期三例：某商店根据长期的记录资料统计，该商店每天接待的顾客人数（N）在25-34人、35-44人、45-54人、55-64人和65-74人的概率分别为：0.3/0.3/0.2/0.1/0.1，每位顾客的购货金额（C）为15-19元、20-24元、25-29元和30-34元的的概率分别为：0.4/0.3/0.2/0.1，试用蒙特卡罗法进行模拟，计算该商店每天的营业额。0.30.30.20.10.1（1）按随机变量的累计概率分配随机数。累计概率就是将发生概率依次累加起来,并将00-99这100个随机数按累计概率规定的范围进行分配,可得下表。第35页，共52页，2023年，2月20日，星期三N发生概率累计概率随机数C发生概率累计概率随机数25-340.30.301-3015-190.40.400-4035-440.30.631-6020-240.30.741-7045-540.20.861-8025-290.20.971-9055-640.10.981-9030-340.11.091-0065-740.11.091-00仿真天数顾客人数（N）随机数随机变量值购买金额（N）随机数随机变量值营业额15540331768024540201768032330822781045040472288057050722713506615054221100仿真6天的总营业额为5500元，平均每天的营业额为917元第36页，共52页，2023年，2月20日，星期三§4-5系统动力学一、系统动力学特点系统动力学是美国麻省理工学院教授福瑞斯特（Jay.W.Forrester）于50年代后期在福特基金会、史隆基金会的赞助下创立的。1、系统动力学作为一种连续仿真技术，主要研究影响系统稳定性和发展趋势的因素2、可以处理高阶次、非线性、多重反馈等复杂关系的系统性问题，如社会经济问题等。第37页，共52页，2023年，2月20日，星期三在公元前1400年，出现的漏壶（沙漏或者滴漏）。它根据流沙从一个容器滴漏到另一个容器的数量来计量时间．古代人设计的“五轮沙漏”通过流沙从漏斗形的沙池流到初轮边上的沙斗里，以此来驱动初轮，从而带动各级机械齿轮的依次旋转．最后一级齿轮带动在水平面上旋转的中轮，中轮的轴心上有一根指针，指针则在一个有刻线的仪器圆盘上转动，以此来显示时刻，这种古老的显示方法几乎与现代时钟的结构完全相同．

第38页，共52页，2023年，2月20日，星期三三、系统动力学仿真过程1、明确系统目标2、结构分析3、建立模型4、计算机仿真5、结果分析6、修正模型7、重复实验第39页，共52页，2023年，2月20日，星期三四、因果关系1、因果关系图可以表示系统的构成要素及其相互间的关系，分析描述系统的结构和子系统之间的反馈机构，构造定性思考模型。2、复杂系统中存在的反馈回路往往不止一个，系统的行为状态通常是若干正、负反馈回路相互作用的结果，由两个或两个以上的反馈回路组成的因果反馈回路称为多重反馈回路（或多重反馈环）。在多重反馈环结构的系统中，不同反馈环的相互作用决定了系统的状态特征。当多重反馈环中的负反馈环的自我调节功能大于正反馈环的自我强化功能时，系统状态趋于稳定；而当正反馈环的自我强化功能强于负反馈环的自我调节功能时，系统呈现出无限增长或无限衰退的状态。第40页，共52页，2023年，2月20日，星期三（1）某一生物种群数量变化的因果关系图第41页，共52页，2023年，2月20日，星期三（2）流行性疾病模型（传染病）模型第42页，共52页，2023年，2月20日，星期三§4-7系统动力学模型的建立因果分析通过因果反馈回路简明清晰地描述系统动态反馈机制，但它只是定性地反映系统中各要素的相互关系，没有明确各要素的数学定义及定量的反馈机理。系统动力学模型首先利用系统动力学特有的语言和符号将因果反馈回路中的各要素进行定义，并用系统流程图的形式反映要素之间的关系，然后利用专用的连续仿真语言（DYNAMO语言）进行定量分析。一、系统流程图1、符号及其含义：对于因果反馈回路来说，构成要素分为变量要素与关联要素两类。变量要素由状态变量、决策变量、辅助变量和常数组成，关联要素包括物质流和信息流。第43页，共52页，2023年，2月20日，星期三（1）状态变量（LEVEL）：描述系统的积累效应的变量，称为状态变量，或流位变量。是系统从初始时刻到某一时刻物质或信息的堆积。如生物的种群数、自然资源量、患病人数等。L(t2)=L(t1)+其中：L(t2)状态变量在t2时刻的值；L(t1)状态变量在t1时刻的值；RI为输入的决策变量值；RO为输出的决策变量值。状态变量具有累积性，系统停止运行时,系统的状态变量不会因为系统停止运行而消失。