交通仿真课件第三章离散仿真pt课件.ppt

1、第三章第三章 离散系统仿真离散系统仿真概述概述l离散系统的状态只是在离散系统的状态只是在离散时间点离散时间点上发生变化，上发生变化，而且这些离散时间点一般是而且这些离散时间点一般是随机随机的。的。l离散系统的数学模型通常用离散系统的数学模型通常用流程图流程图或网络图来或网络图来描述。描述。l离散仿真的目的是实体的活动以找出离散仿真的目的是实体的活动以找出(分析分析)系系统的统的(潜在潜在)行为。行为。离散仿真离散仿真l事件事件(event)时间因变量随时间因变量随(事件事件)时间离散变时间离散变化。化。因因变量变量时间时间基本概念基本概念l实体实体 构成系统的各种构成系统的各种成分成分称为实体

2、，系统的研究对象。称为实体，系统的研究对象。临时实体、永久实体。临时实体、永久实体。l属性属性 反映实体的某些反映实体的某些性质性质。l状态状态 在某一确定时间点，系统的状态是系统中所有实体属在某一确定时间点，系统的状态是系统中所有实体属性的性的集合集合。基本概念基本概念l事件事件 引起系统状态发生引起系统状态发生变化变化的行为，它是在某一时间点上的的行为，它是在某一时间点上的瞬间行为瞬间行为。l活动活动 实体在某一状态的实体在某一状态的持续过程持续过程。l进程进程 进程由和实体相关的进程由和实体相关的事件事件及若干及若干活动活动组成，一个进程描组成，一个进程描述了它所包括的事件及活动间的相互

3、述了它所包括的事件及活动间的相互逻辑逻辑关系和关系和时序时序关关系。系。车辆到达事件车辆到达事件服务开始事件服务开始事件服务结束事件服务结束事件服务活动服务活动进程进程排队活动排队活动事件、活动、进程三者之间的关系事件、活动、进程三者之间的关系基本概念基本概念l仿真时钟仿真时钟 仿真时钟用于表示仿真时间的变化，仿真时钟推进的时仿真时钟用于表示仿真时间的变化，仿真时钟推进的时间间隔称为时间步长。间间隔称为时间步长。时间步长法、事件步长法时间步长法、事件步长法l统计计数器统计计数器 离散系统的状态随事件的不断发生呈现动态变化过程，离散系统的状态随事件的不断发生呈现动态变化过程，这种动态变化过程在统

4、计意义下才有参考价值。这种动态变化过程在统计意义下才有参考价值。统计计数器用于记录仿真规程中系统性能的统计信息。统计计数器用于记录仿真规程中系统性能的统计信息。离散仿真模型建立步骤离散仿真模型建立步骤l定义系统的参变量集合，构造定义系统的参变量集合，构造系统映象系统映象；l定义事件类型及其发生时点；定义事件类型及其发生时点；l定义每一定义每一事件事件时间发生状态变化的点；时间发生状态变化的点；l描述系统中实体的描述系统中实体的活动活动；l构造状态转移函数或算法；构造状态转移函数或算法；l通过系统流图描述整个通过系统流图描述整个过程过程。构造初始映象构造初始映象l找一个尽可能简单的系统状态作为初

5、始状态；找一个尽可能简单的系统状态作为初始状态；l从一个远离平衡状态但容易构造的状态开始进从一个远离平衡状态但容易构造的状态开始进行模拟，当运行一段时间之后，系统的状态会行模拟，当运行一段时间之后，系统的状态会接近或处于稳定状态（平衡状态）。接近或处于稳定状态（平衡状态）。离散仿真中的关键问题离散仿真中的关键问题l事件取舍事件取舍：确定改变系统状态的事件集，并将它们用逻辑关系联系起来。确定改变系统状态的事件集，并将它们用逻辑关系联系起来。系统仿真就是靠系统仿真就是靠按顺序执行按顺序执行联系这些事件的逻辑来实现的。联系这些事件的逻辑来实现的。l活动扫描活动扫描：要描述系统中实体的活动，设定引起活

6、动开始及结束的条件。启要描述系统中实体的活动，设定引起活动开始及结束的条件。启动或结束活动的事件不由建模者设定，而随仿真推进而自动进行。动或结束活动的事件不由建模者设定，而随仿真推进而自动进行。为保证活动得到记录，每一次推进均需要扫描活动中的实体集。为保证活动得到记录，每一次推进均需要扫描活动中的实体集。由于需要在每一次推进中扫描每一活动，这种方法的效率不太高。由于需要在每一次推进中扫描每一活动，这种方法的效率不太高。l过程定位过程定位：提供整个仿真过程中实体流的一种用仿真语言描述的方法。提供整个仿真过程中实体流的一种用仿真语言描述的方法。系统仿真的推进系统仿真的推进l时间步长法时间步长法 以

7、固定的时间间隔进行驱动；以固定的时间间隔进行驱动；l事件步长法事件步长法 按下一类最早发生事件的发生时间推进。按下一类最早发生事件的发生时间推进。t时间步长法时间步长法l在进行系统仿真的同时，把整个仿真过程分为许多在进行系统仿真的同时，把整个仿真过程分为许多相相等等的的时间间隔时间间隔，程序按此步长前进的时钟就是仿真时，程序按此步长前进的时钟就是仿真时钟。钟。l在每个时间间隔做如下处理：在每个时间间隔做如下处理：l该步内若无事件发生，则仿真时钟再推进一个单该步内若无事件发生，则仿真时钟再推进一个单位时间；位时间；若在该步内有若干个事件发生，则认为这些事件均发生若在该步内有若干个事件发生，则认为

8、这些事件均发生在这一步的结束时刻，同时必须规定当出现这种情况时在这一步的结束时刻，同时必须规定当出现这种情况时各类事件处理的优先顺序。各类事件处理的优先顺序。扫描与处理方法扫描与处理方法l对每一类事件或每一个主导实体设置一个模拟时钟，对每一类事件或每一个主导实体设置一个模拟时钟，以此记录和控制实体活动的延续时间。以此记录和控制实体活动的延续时间。l对系统实体进行扫描；对系统实体进行扫描；l对系统事件进行扫描；对系统事件进行扫描；l对事件和实体结合起来进行扫描。对事件和实体结合起来进行扫描。l改变状态，预测下一事件改变状态，预测下一事件。时间步长时间步长法流程图法流程图事件步长法事件步长法l仿真

9、时钟不断地从一个事件发生时间推进到下一个仿真时钟不断地从一个事件发生时间推进到下一个最早发生事件的发生时间。最早发生事件的发生时间。l以以事件发生的时间点相互间隔事件发生的时间点相互间隔作为步长，按照时间作为步长，按照时间的进展，一步一步地对系统的行为进行仿真，直到的进展，一步一步地对系统的行为进行仿真，直到预定的仿真时间为止。预定的仿真时间为止。l事件表按照事件发生时间事件表按照事件发生时间先后先后顺序安排事件，将仿顺序安排事件，将仿真过程看作一个事件点序列。真过程看作一个事件点序列。l事件控制部件始终从事件表中选择事件控制部件始终从事件表中选择最早发生最早发生时间的时间的事件记录，然后将仿

10、真时钟该事件发生的时刻。事件记录，然后将仿真时钟该事件发生的时刻。时钟推进举例时钟推进举例l模拟运行模拟运行150个时间单位，顾客到达事件、顾客服务个时间单位，顾客到达事件、顾客服务完毕离去事件，完毕离去事件，Ti到达时间间隔，到达时间间隔，Si第第i个顾客服务时个顾客服务时间，间，Di第第i个顾客等待时间，个顾客等待时间，Ci=Ti+Si+Di第第i个顾客离个顾客离开系统的时间开系统的时间,qi第第i个顾客排队的对长，个顾客排队的对长，bi模拟时钟推模拟时钟推进到第进到第i次的时间，次的时间，Zi第第i个事件发生时服务员的状态。个事件发生时服务员的状态。Ti=15,32,24,40,22,；

11、Si=43,36,34,28,l 初始状态：初始状态：q0=0,Z0=0l求：求：bi 、Ci、离散系统仿真程序的结构离散系统仿真程序的结构l状态变量状态变量；l时钟变量时钟变量；l事件表事件表（按时间顺序记录仿真过程中将要发生的事件）（按时间顺序记录仿真过程中将要发生的事件）l统计计数器统计计数器l初始化子程序初始化子程序l时钟推进子程序时钟推进子程序 （由事件表确定下一事件，然后将将仿真时钟推进到该事件（由事件表确定下一事件，然后将将仿真时钟推进到该事件发生的时间）发生的时间）l调度子程序调度子程序（将仿真过程中产生的未来事件插入事件表）（将仿真过程中产生的未来事件插入事件表）离散系统仿真

12、程序的结构离散系统仿真程序的结构l事件子程序事件子程序 每一类事件对应一个事件子程序，相应的事件发生时就每一类事件对应一个事件子程序，相应的事件发生时就转入该事件子程序进行处理，更新系统状态，产生新的转入该事件子程序进行处理，更新系统状态，产生新的事件。事件。l统计报告子程序统计报告子程序l随机数发生器随机数发生器l主程序主程序 调用时钟推进子程序，控制转移到相应的事件子程序，调用时钟推进子程序，控制转移到相应的事件子程序，完成仿真程序的总体控制。完成仿真程序的总体控制。离散系统仿真离散系统仿真程序流程图程序流程图离散系统仿真策略离散系统仿真策略l建立描述系统行为的仿真模型建立描述系统行为的仿

13、真模型 由于系统采用伪随机数，可以得到确定的状态转移函由于系统采用伪随机数，可以得到确定的状态转移函数，模型采用流程图或网络图的形式。数，模型采用流程图或网络图的形式。l仿真策略仿真策略 仿真策略决定仿真模型的结构仿真策略决定仿真模型的结构模型描述中采用的主要术语模型描述中采用的主要术语l成分成分 相当于系统中的实体，用于构造模型中的各个部分。相当于系统中的实体，用于构造模型中的各个部分。主动成分主动成分（可以主动产生活动的成分）（可以主动产生活动的成分）被动成分被动成分（本身不激发活动，只有在主动成分作用下才能产（本身不激发活动，只有在主动成分作用下才能产生状态变化）生状态变化）l描述变量描

14、述变量 成分状态、属性的描述。成分状态、属性的描述。l成分间的相互关系成分间的相互关系 描述成分之间相互影响的规律。描述成分之间相互影响的规律。模型描述中采用的符号模型描述中采用的符号lC=a1,a2,an为成分集合；为成分集合；lCA=a1,a2,am为主动成分子集合；为主动成分子集合；lCP=a1,a2,ah为被动成分子集合；为被动成分子集合；lSa为成分为成分a的状态变量；的状态变量；lP=p1,p2,pr为参数（属性）集合；为参数（属性）集合；lta为成分为成分a的状态下一发生变化的时刻的状态下一发生变化的时刻;lDa(S)为成分为成分a在状态变量值在状态变量值S时的条件变量时的条件变

15、量;lTIME为模拟时钟的值。为模拟时钟的值。典型仿真策略典型仿真策略l事件调度法事件调度法l活动描述法活动描述法l进程交互法进程交互法事件调度法事件调度法l通过定义事件及每个事件发生对系统状态的变化，按通过定义事件及每个事件发生对系统状态的变化，按时间顺序时间顺序确定并执行每个事件发生时有关的逻辑关系。确定并执行每个事件发生时有关的逻辑关系。l所有事件均放在所有事件均放在事件表事件表中，模型中设有一个中，模型中设有一个时间控制时间控制机构机构，该机构从事件表中选取最早发生时刻的事件。，该机构从事件表中选取最早发生时刻的事件。l以以事件种类事件种类为控制依据，不同种类事件的处理进入相为控制依据

16、，不同种类事件的处理进入相应的事件处理模块，并在时间处理完毕返回时间控制应的事件处理模块，并在时间处理完毕返回时间控制机构。机构。事件调度法模型的基本结构事件调度法模型的基本结构事件调度算法事件调度算法l初始时间初始时间t=t0、事件表初始化、置系统初始事件、事件表初始化、置系统初始事件;l成分表初始化成分表初始化S=(Sa1,ta1),(Sam,tam),Sam+1,San);l操作事件表，取出操作事件表，取出t=min ta|aCA，修改事件表，修改事件表;l推进时钟推进时钟 TIME=t(s);lWhile(TIMETIMElFRESENT(S)=a|ta=TIMElPAST(S)=a|

17、taTIMElTIME=min(ta|a FUTURE(S)活动扫描法的算法活动扫描法的算法l初始时间初始时间t=t0、设置主动成分的模拟时钟、设置主动成分的模拟时钟ta(i);l成分状态初始化成分状态初始化S=(Sa1,ta1),(Sam,tam),Sam+1,San);l设置系统时钟设置系统时钟 TIME=t0;lWhile(TIME=t)，执行扫描，执行扫描 for j=最高优先数到最低优先数最高优先数到最低优先数 将优先数为将优先数为j的成分置成的成分置成i if（tai(i)=TIME 且且 Dai(S)=true）执行活动子例程执行活动子例程 endif endfor TIME=m

18、in(ta|aFUTURE(S)l endwhile按活动扫描法建立的排对系统模型按活动扫描法建立的排对系统模型进程交互法进程交互法l进程由事件的时间序列及若干活动组成进程由事件的时间序列及若干活动组成l具有上述两种方法的特点，接近具有上述两种方法的特点，接近实际实际系统，编系统，编程实现非常程实现非常复杂复杂l采用进程描述系统，将模型的采用进程描述系统，将模型的主动成分主动成分所发生所发生的事件及活动按照时间顺序进行组合形成的事件及活动按照时间顺序进行组合形成进程进程表表，一个成分一旦进入进程，它将完成进程的，一个成分一旦进入进程，它将完成进程的全部活动。全部活动。进程交互法进程交互法l采用

19、两张事件表，采用两张事件表，当前事件表当前事件表、将来事件表将来事件表；l当仿真时钟推进，满足条件的所有事件记录从将当仿真时钟推进，满足条件的所有事件记录从将来事件表移到当前事件表，取出每个事件记录，来事件表移到当前事件表，取出每个事件记录，判断所属判断所属进程进程与与位置位置，当发生条件真，发生包含，当发生条件真，发生包含该事件的该事件的活动活动，并让该进程尽可能地推进，直至，并让该进程尽可能地推进，直至结束。结束。l时间控制以主导实体进入该进程的的时间序列及时间控制以主导实体进入该进程的的时间序列及其经历该进程的各项活动的时间顺序，走向控制其经历该进程的各项活动的时间顺序，走向控制主要以主

20、要以断点断点为依据。为依据。以进程为基础的排队系统模型以进程为基础的排队系统模型几种仿真策略的比较几种仿真策略的比较l系统描述系统描述事件调度法中，只有主动成分才能施加作用；事件调度法中，只有主动成分才能施加作用；事件调度法中，系统的动态特性表现为主动成事件调度法中，系统的动态特性表现为主动成分不断产生事件；分不断产生事件；活动扫描法中表现为主动成分产生活动；活动扫描法中表现为主动成分产生活动；进程交互法中则是通过成分在其进程中一步一进程交互法中则是通过成分在其进程中一步一步地推进描述。步地推进描述。几种仿真策略的比较几种仿真策略的比较l建模要点建模要点u事件调度法中，用户要对所定义的全部事件

21、进行建事件调度法中，用户要对所定义的全部事件进行建 模，条件测试只能在事件处理子程序中进行；模，条件测试只能在事件处理子程序中进行；u 活动扫描法设置了一个条件子例程用于条件测试，活动扫描法设置了一个条件子例程用于条件测试，还设置了一个活动扫描模块，该模块对所定义的活还设置了一个活动扫描模块，该模块对所定义的活动进行建模；动进行建模；u 进程交互法将一个进程分成若干步，每一步包括进程交互法将一个进程分成若干步，每一步包括条件测试及执行活动两部分。条件测试及执行活动两部分。几种仿真策略的比较几种仿真策略的比较l时钟推进时钟推进u事件调度法中，控制机构从事件表中取出事件调度法中，控制机构从事件表中

22、取出最早发生最早发生时间的事件时间的事件记录，将时钟推进到该时刻，执行该事件处理子程序；记录，将时钟推进到该时刻，执行该事件处理子程序；u 活动扫描法除系统时钟外，每一个主动成分还有活动扫描法除系统时钟外，每一个主动成分还有成分模拟子时成分模拟子时钟钟，控制机构选取那些，控制机构选取那些大于大于当前系统时钟且所有成分模拟时钟当前系统时钟且所有成分模拟时钟最小最小的那个成分模拟时钟，将系统时钟推进到该时钟；的那个成分模拟时钟，将系统时钟推进到该时钟；u 进程交互法中，一旦某个进程被执行，要求尽可能走下去，但进程交互法中，一旦某个进程被执行，要求尽可能走下去，但并并不改变不改变系统时钟。如果该进程

23、未完成，记录中断时间及事件系统时钟。如果该进程未完成，记录中断时间及事件类型放入将来事件表。类型放入将来事件表。几种仿真策略的比较几种仿真策略的比较l执行控制执行控制u事件调度法按下一最早发生时间选择事件记录；事件调度法按下一最早发生时间选择事件记录；u 活动扫描法对全部活动扫描，只有活动扫描法对全部活动扫描，只有Dai(S)=true且且taiTIME的活动才能被执行；的活动才能被执行；u 进程交互法对当前事件表中所有的记录扫描，根进程交互法对当前事件表中所有的记录扫描，根据该事件在其进程中的指针进行条件判断。当据该事件在其进程中的指针进行条件判断。当Dai(S)=true 执行该进程，并一

24、直执行下去，否则记执行该进程，并一直执行下去，否则记下断点。下断点。几种仿真策略的比较几种仿真策略的比较l事件调度法建模灵活，建模工作量大；事件调度法建模灵活，建模工作量大；l活动扫描法对于各成分相关性很强的系统来说活动扫描法对于各成分相关性很强的系统来说模型效率较高，但执行程序结构复杂；模型效率较高，但执行程序结构复杂；l进程交互法建模最直观，模型表示接近实际系进程交互法建模最直观，模型表示接近实际系统特别适用于可以预测、顺序比较确定的系统，统特别适用于可以预测、顺序比较确定的系统，但流程控制复杂，建模灵活性不好。但流程控制复杂，建模灵活性不好。适用性适用性l系统中的各个成分相关性较少，宜采

25、用事件调系统中的各个成分相关性较少，宜采用事件调度法，反之宜采用活动扫描法；度法，反之宜采用活动扫描法；l系统成分的活动比较规则，宜采用进程交互法。系统成分的活动比较规则，宜采用进程交互法。排队系统仿真排队系统仿真l某个时刻要求服务的的数量超过服务机构的容量。某个时刻要求服务的的数量超过服务机构的容量。l到达模式：顾客按怎样的规律到达；到达模式：顾客按怎样的规律到达；l服务机构：同一时刻有多少服务台可接纳顾客；服务机构：同一时刻有多少服务台可接纳顾客；l排队规则：服务台完成当前的服务后，从对列选择下排队规则：服务台完成当前的服务后，从对列选择下一个实体服务的原则。一个实体服务的原则。到达模式到

26、达模式l平均到达间隔时间平均到达间隔时间Ta=T/n；l平均到达率平均到达率 =1/Ta；l到达间隔时间分布函数；到达间隔时间分布函数；1-F(t)l到达时间变化系数到达时间变化系数Sa/Ta；服务机构服务机构l一个或多个服务员，没有服务员；一个或多个服务员，没有服务员；l多个服务台，并列、串列、混合；多个服务台，并列、串列、混合；l单独服务，成批服务；单独服务，成批服务；l服务时间，确定、随机；服务时间，确定、随机；排队规则排队规则l先到先服务先到先服务FIFO；l后到先服务后到先服务LIFO；l随机服务随机服务SIRO；l优先权服务优先权服务PR；l最短处理时间先服务最短处理时间先服务SP

27、T。系统容量系统容量l有限；有限；l无限无限。排队模型分类排队模型分类lA/B/C/D/E A:到达模式；到达模式；B:服务模式；服务模式；C:并行服务员的数目；并行服务员的数目；D:系统容量；系统容量；E:排队规则。排队规则。l常见的到达和服务间隔时间分布：常见的到达和服务间隔时间分布：M(指数分指数分布布)、G(确定型分布确定型分布)、M(一般随机分布一般随机分布)；lM/M/1/FIFO排队系统的特征量排队系统的特征量l服务员利用率服务员利用率P=平均服务时间平均服务时间/平均到达间隔时间；平均到达间隔时间；l系统中平均顾客数系统中平均顾客数P/1-P；l系统内排队等待的顾客数系统内排队

28、等待的顾客数P2/1-P；l顾客在系统内的停留时间；顾客在系统内的停留时间；l平均等待时间；平均等待时间；l系统出现大于系统出现大于n个顾客的概率。个顾客的概率。研讨研讨l多队多服务台排队系统模拟多队多服务台排队系统模拟 以多出纳台银行系统为例（换对原则）以多出纳台银行系统为例（换对原则）l系统中的成分系统中的成分l成分状态变量成分状态变量l系统中的初始状态系统中的初始状态l顾客到达间隔时间服从的分布顾客到达间隔时间服从的分布 l服务时间服从的分布服务时间服从的分布 事件事件l顾客到达银行顾客到达银行l顾客完成服务后离开顾客完成服务后离开l顾客换对顾客换对l银行关闭银行关闭系统指标系统指标l平

29、均等待时间平均等待时间l平均对长平均对长l最大等待时间最大等待时间l最大对长最大对长多级串联封闭式排队系统模拟多级串联封闭式排队系统模拟l基于主导实体活动扫描法的模拟模型基于主导实体活动扫描法的模拟模型l从一种称为主导实体的模拟子时钟中，找出具有最小从一种称为主导实体的模拟子时钟中，找出具有最小时钟值的主导实体，处理该主导实体的活动。时钟值的主导实体，处理该主导实体的活动。l主导实体的活动或状态改变时，子时钟便更新一次时主导实体的活动或状态改变时，子时钟便更新一次时钟值。钟值。港口装运模拟系统港口装运模拟系统l某海港共有某海港共有N个仓库，个仓库，1个码头，个码头，m辆起重车从辆起重车从仓库运

30、向码头装船。仓库运向码头装船。lN=2,m=12,14,16,18,20;lN=3,m=15,20,25,30;lN=4,m=25,30,35;确定起重车和仓库的合理数量关系。确定起重车和仓库的合理数量关系。系统分析系统分析l实体实体 起重车起重车、仓库、码头、道路、货物等。、仓库、码头、道路、货物等。l四级活动四级活动 仓库装车、重载运行、仓库装车、重载运行、码头卸车装船、空载返回码头卸车装船、空载返回l可控变量可控变量 仓库数目、起重车数目仓库数目、起重车数目系统模型系统模型lC(I)=0 重载运行；重载运行；C(I)=1 卸车装船；卸车装船；lC(I)=2 空载返回；空载返回；C(I)=

31、3 装车。装车。lA(I)每辆起重车的模拟子时钟每辆起重车的模拟子时钟 I=1,2,m；lL(J)每个仓库的模拟子时钟每个仓库的模拟子时钟 J=1,2,n；初始状态初始状态l开始时，每辆起重车都在仓库排队等待装车，开始时，每辆起重车都在仓库排队等待装车，并假设所有起重车都进行装车，它们的重车并假设所有起重车都进行装车，它们的重车时间赋给时间赋给A(I)l起重车均位于处于装完车准备出发状态，此起重车均位于处于装完车准备出发状态，此时时C(I)=0，重载运行。，重载运行。l从所有重车的子时钟钟找出最小子时钟值，并取出对从所有重车的子时钟钟找出最小子时钟值，并取出对应的车号应的车号J2。l若若C(J

32、2)=0，重载运行，产生重载运行时间，赋值，重载运行，产生重载运行时间，赋值A(J2)，C(J2)=1；l若若C(J2)=1，卸货，若码头空闲，将它改为工作状态，卸货，若码头空闲，将它改为工作状态，累计空闲时间，产生起重车卸车时间；否则不改变码累计空闲时间，产生起重车卸车时间；否则不改变码头状态，让起重车排队，计算排队时间；头状态，让起重车排队，计算排队时间；C(J2)=2；l若若C(J2)=2，空载返回，产生空载返回时间，赋值，空载返回，产生空载返回时间，赋值A(J2)，C(J2)=3；l若若C(J2)=3，装车，找出模拟子时钟最小的仓库，若仓，装车，找出模拟子时钟最小的仓库，若仓库不空闲，让起重车排队，计算等待时间；否则，累库不空闲，让起重车排队，计算等待时间；否则，累计空闲时间，产生装车时间，仓库装车，装车完毕后，计空闲时间，产生装车时间，仓库装车，装车完毕后，C(J2)=0。