动态系统模拟的方法

1、 系统模拟是研究系统，特别是系统模拟是研究系统，特别是动态系统动态系统的的 重要方法，对于：重要方法，对于： 1). . 结构复杂的系统；结构复杂的系统； 2). 很难用解析方法求出变量关系的系统；很难用解析方法求出变量关系的系统； 3). 内部机理不明的内部机理不明的“黑箱黑箱”系统；系统； 4). 为验证用其他方法建立的模型及结果。为验证用其他方法建立的模型及结果。 应是较好的选择。应是较好的选择。 动态系统是随时间变化的，含有随机因素的动态系统是随时间变化的，含有随机因素的 系统，其中系统，其中排队系统排队系统是重要而常见的动态系统。是重要而常见的动态系统。 对排队系统进行模拟，首先要清

2、楚它的运行对排队系统进行模拟，首先要清楚它的运行 机制。机制。 1. 1. 排队过程的一般表示排队过程的一般表示 顾客源顾客源排队结构排队结构 服服 务务 机机 构构 顾客顾客 来到来到 顾客顾客 离去离去 排队系统排队系统 2.2.排队系统的组成和特征排队系统的组成和特征 (1) 输入过程输入过程 对于顾客逐个到达随机性输入过程对于顾客逐个到达随机性输入过程： 1) 顾客的到达是相互独立（或相互关联）的；顾客的到达是相互独立（或相互关联）的； 2) 输入过程是平稳的、对时间是齐次的输入过程是平稳的、对时间是齐次的; 指相继到达的时间间隔的分布和所含参指相继到达的时间间隔的分布和所含参 数（均

3、值、方差等）不随时间改变。数（均值、方差等）不随时间改变。 (2) 排队规则排队规则 即时制即时制或或损失制损失制（如，普通市内电话）（如，普通市内电话）。 等待制等待制 先到先服务先到先服务（FIFO） 后到先服务后到先服务（LIFO） 随机服务随机服务（KS） 有优先权的服务有优先权的服务 队列队列 单列单列 多列（各列间不能相互转移）多列（各列间不能相互转移） 不能中不能中 途退出途退出 (3)(3)服务机构服务机构 1）排队方式排队方式: 单队单队 单服务台单服务台 多服务台（串列）多服务台（串列） 1 12n 1 2 n 单队单队 多多 服务台服务台 （并列）（并列） 2) 服务时间

4、：服务时间： 确定型确定型的与的与随机型随机型的的 排队论讨论排队论讨论相继到达时间相继到达时间和和服务时间，服务时间，二者二者 中至少有一个是随机型的。中至少有一个是随机型的。 随机服务时间的分布中数学期望、方差等参随机服务时间的分布中数学期望、方差等参 数都不受时间的影响。数都不受时间的影响。 3.3.排队模型的分类排队模型的分类 三个主要特征三个主要特征 顾客相继到达间隔时间的分布顾客相继到达间隔时间的分布(X); 服务时间的分布服务时间的分布(Y) ； 服务台个数服务台个数(Z) 。 用符号用符号 X/Y/Z 表示排队模型的类别表示排队模型的类别。 M指数分布指数分布（Markov性性

5、）；）； D 确定型确定型（Deterministic）; EKK阶爱尔朗分布阶爱尔朗分布（Erlang）; GI一般相互独立一般相互独立(General Independent)的随的随 机分布；机分布； G 一般（一般（General）随机分布。随机分布。 例例1 M/M/1：到达间隔时间服从指数分布，服务时到达间隔时间服从指数分布，服务时 间服从指数分布，单服务台；间服从指数分布，单服务台； M/M/C：间隔时间和服务时间都服从指数分布，间隔时间和服务时间都服从指数分布， C个平行服务台（顾客仅一列）；个平行服务台（顾客仅一列）； CI/G/1：单服务台，有一般分布的相互独立的间单服务台

6、，有一般分布的相互独立的间 隔时间和一般随机服务时间。隔时间和一般随机服务时间。 4. 间隔时间和服务时间的分布间隔时间和服务时间的分布 三种常用的三种常用的 理论分布理论分布 5排队系统的主要研究指标排队系统的主要研究指标 1）队长队长：在系统中的顾客数（平均值记为在系统中的顾客数（平均值记为LS）; 排队长排队长（队列长）：在系统中排队等待服务（队列长）：在系统中排队等待服务 的顾客数的顾客数（LQ）。）。 例例2 一个理发店内有两位服务员一个理发店内有两位服务员 A和和 B，顾客，顾客 们随机到达店内，其中们随机到达店内，其中6060的顾客仅需剪发，的顾客仅需剪发， 每位花每位花5 5分

7、钟时间，另外的分钟时间，另外的4040顾客既要剪发又顾客既要剪发又 要洗发，每位花费时间要洗发，每位花费时间8 8分钟。分钟。 理发店是一个动态随机系统，分析系统的运理发店是一个动态随机系统，分析系统的运 行效率行效率。 结合实例介绍随机动态系统的模拟的方法结合实例介绍随机动态系统的模拟的方法 2) 逗留时间逗留时间：顾客在系统中的停留时间顾客在系统中的停留时间(WS); 等待时间等待时间：一个顾客在系统中的排队停留时间：一个顾客在系统中的排队停留时间(WQ)。 （3）忙期忙期（Busy Period）:服务机构一次连续工作服务机构一次连续工作 的时间长度（反映服务员的工作强度）。的时间长度（

8、反映服务员的工作强度）。 (1)系统状态（变量）：系统状态（变量）：在任意时刻，为描述在任意时刻，为描述 系统需要的含有全部信息的变量集合。系统需要的含有全部信息的变量集合。 例例2 2中有三个状态变量：中有三个状态变量： 1).等待服务的顾客数；等待服务的顾客数； 2). A是否正在服务（是或否）；是否正在服务（是或否）； 3). B是否正在服务。是否正在服务。 (2) 实体实体：需要明确描述的系统对象或组成部分需要明确描述的系统对象或组成部分。 实体是系统的可分离部分，或许是系统的永实体是系统的可分离部分，或许是系统的永 久部分，如服务员、设备装置等。或许可进入和久部分，如服务员、设备装置

9、等。或许可进入和 退出系统。退出系统。 1. 系统模拟的部分术语系统模拟的部分术语 例如商店的顾客，港口的轮船，或发往电力例如商店的顾客，港口的轮船，或发往电力 调度系统的一条指令。调度系统的一条指令。 本例中的实体？本例中的实体？ (3) 事件事件：使系统状态发生变化的瞬时现象。使系统状态发生变化的瞬时现象。 如如例中事件：例中事件： 一名新顾客的到达；一名新顾客的到达；A开始服务；开始服务； A A结束服务；结束服务；B B开始服务；开始服务；B B结束服务。结束服务。 (4)(4)活动：活动：两个事件间的持续时间。两个事件间的持续时间。 常数或随常数或随 机变量机变量 例中有下述活动：例

10、中有下述活动： 1) 1) 顾客排队时间，即顾客到达至接受服务的持顾客排队时间，即顾客到达至接受服务的持 续时间；续时间； 2) 2) 顾客们到达的间隔时间；顾客们到达的间隔时间； 3) 3) A的服务时间和的服务时间和B的服务时间。的服务时间。 注：注：事件在时间轴上占据一个点，而活动则占事件在时间轴上占据一个点，而活动则占 据时间轴上的一段。据时间轴上的一段。 到达间隔时间到达间隔时间 排队时间排队时间服务时间服务时间 通常是具有某种通常是具有某种 分布的随机变量分布的随机变量 (5) 特征（属性）特征（属性）：给定实体的性质。：给定实体的性质。 例如一条指令的长短，卡车是满载还是空载例如

11、一条指令的长短，卡车是满载还是空载。 在模拟中实体的特征可以保持不变，也可以改变在模拟中实体的特征可以保持不变，也可以改变; 一个实体可能有多种特征。一个实体可能有多种特征。 例中每个顾客只有一个特征：需要服务的种类。例中每个顾客只有一个特征：需要服务的种类。 还可以考虑顾客的其他特征，如性别，是否有还可以考虑顾客的其他特征，如性别，是否有 优先权等等。优先权等等。 时间步长法时间步长法 面向事件法面向事件法 （1）时间步长法（固定时间增量法）时间步长法（固定时间增量法） 人们去考察某一对象系统的状态和活动变化过程人们去考察某一对象系统的状态和活动变化过程 时，通常总是随时间的进程来逐步考察和

12、分析。时，通常总是随时间的进程来逐步考察和分析。 基本步骤基本步骤为：为： 1 1）选取对象系统的一个初始起点作为模拟时）选取对象系统的一个初始起点作为模拟时 钟的零点钟的零点； 2 2）选定一个合适的时间步长。）选定一个合适的时间步长。 2. 2. 动态系统模拟的两种方法动态系统模拟的两种方法 3) 从模拟时钟的零点开始，每推进一个时间从模拟时钟的零点开始，每推进一个时间 步长：步长： 对系统的活动和状态按照预定的规则和目的进行对系统的活动和状态按照预定的规则和目的进行 考察、考察、分析、分析、计算、计算、记录记录 直到预定模拟结束时刻为止。直到预定模拟结束时刻为止。 0 t t 结束结束

13、时刻时刻 续例续例2 一个理发店内有两位服务员一个理发店内有两位服务员 A和和 B，顾，顾 客们随机到达店内，其中客们随机到达店内，其中6060的顾客仅需剪发，的顾客仅需剪发， 每位花每位花5 5分钟时间，另外的分钟时间，另外的4040顾客既要剪发又顾客既要剪发又 要洗发，每位花费时间要洗发，每位花费时间8 8分钟。分钟。 *1 任一分钟内到达一位顾客的概率任一分钟内到达一位顾客的概率p=0.5。 模拟的假定条件：模拟的假定条件： 概率概率 p 可以是可以是 (0, 1)上的任上的任 意实数。意实数。 *2 同一分钟内不会有一个以上顾客到达同一分钟内不会有一个以上顾客到达。 如果观察到一分钟内

14、有一如果观察到一分钟内有一 位以上顾客来到，就应将时间位以上顾客来到，就应将时间 步长取得更短一些。步长取得更短一些。 *3 如果店里两名服务员都空闲，则由顾客随意如果店里两名服务员都空闲，则由顾客随意 选择一位服务员。选择一位服务员。 *4 先到先服务先到先服务(FIFO) 的排队规则的排队规则。 *5 顾客都会耐心等待服务，而且服务员都顾客都会耐心等待服务，而且服务员都 不能休息。不能休息。 用时间步长法对理发店系统进行模拟。用时间步长法对理发店系统进行模拟。 通过假设进一步明确理发店系统的运行，为通过假设进一步明确理发店系统的运行，为 模拟工作做好准备。模拟工作做好准备。 对理发店系统进

15、行了部分简化，是一种理想对理发店系统进行了部分简化，是一种理想 化的模拟。基于解决实际问题的目标，在模拟化的模拟。基于解决实际问题的目标，在模拟 模型中可以考虑更复杂的情形。模型中可以考虑更复杂的情形。 根据假设模拟变量处理如下根据假设模拟变量处理如下 1 1）取时间步长）取时间步长t=1(分钟分钟) )，在任一分钟内有，在任一分钟内有 一名顾客到达的概率是一名顾客到达的概率是0.5； 2 2）每位顾客服务时间取为两类顾客的平均服务）每位顾客服务时间取为两类顾客的平均服务 时间时间：50.680.4= 6.2（分）（分）。 模拟过程模拟过程 时间步长法自然易理解，时间步长法自然易理解， 但需加

16、快模拟速度。但需加快模拟速度。 （2）面向事件法（可变时间增量法）面向事件法（可变时间增量法） 采用不等时间间隔步长的，仅在人们关心的采用不等时间间隔步长的，仅在人们关心的 事件发生的时间点上考察系统的状态变化，从事件发生的时间点上考察系统的状态变化，从 而加快模拟的求解过程。而加快模拟的求解过程。 基本思想：基本思想：对对象系统的一系列不同性质的对对象系统的一系列不同性质的 事件，按照发生时间的先后顺序逐个进行考察。事件，按照发生时间的先后顺序逐个进行考察。 0 t 模拟方法模拟方法：编制计算机程序时设置一面编制计算机程序时设置一面“模拟模拟 钟钟”，当有一个事件发生时，才向前走一步，当有一

17、个事件发生时，才向前走一步， 模拟钟走过一步后，自动地寻找下一个最先使模拟钟走过一步后，自动地寻找下一个最先使 系统状态发生变化的事件。系统状态发生变化的事件。 时间是可变的时间是可变的 停止模拟过程停止模拟过程 的两种方式：的两种方式： 事先规定运行时间事先规定运行时间; 设置为某个特定事件发生设置为某个特定事件发生; 两种模拟方法的比较：两种模拟方法的比较： 1.1.如果一个系统的事件出现无明显的规律，常如果一个系统的事件出现无明显的规律，常 采用采用面向事件法面向事件法，可以节约计算机运算时间。，可以节约计算机运算时间。 2.如果对象系统中事件发生得非常频繁，而且如果对象系统中事件发生得

18、非常频繁，而且 具有一定的规律，为获取较多的信息，可采用具有一定的规律，为获取较多的信息，可采用 时间步长法。时间步长法。 模拟思路必须清晰，对模拟的系统对象的运行模拟思路必须清晰，对模拟的系统对象的运行 机制、模拟变量做到心中有数。机制、模拟变量做到心中有数。 (1) 列出实体、实体特征、状态，活动列出实体、实体特征、状态，活动： *需明确模拟的实体以及允许并行的实体个数；需明确模拟的实体以及允许并行的实体个数； *对每个活动写出初始状态，活动的持续时间；对每个活动写出初始状态，活动的持续时间； *写出模拟的初始状态和结束时间（或结束状态写出模拟的初始状态和结束时间（或结束状态 ) 例例：理

19、发店系统理发店系统,系统的有关模拟变量、因素系统的有关模拟变量、因素 如下：如下： 实体：实体： 顾客顾客( (特征特征: P(单剪单剪)=0.6；P(洗和剪洗和剪)=0.4)， 服务员服务员A，服务员服务员B。 活动：活动： 到达间隔时间到达间隔时间( (指数分布指数分布, ,均值为均值为3分钟分钟);); 队列队列（队长无限制），（队长无限制）， A的服务时间的服务时间( (剪发剪发5 5分钟；洗和剪分钟；洗和剪8 8分钟分钟) ； B的服务时间的服务时间( (剪发剪发5 5分钟；洗和剪分钟；洗和剪8 8分钟分钟) ； 事件事件： 顾客到达， 顾客到达， A开始服务，开始服务，A结束服务，结束服务， B开始服务，开始服务，B B结束服务。 结束服务。 初始状态：初始状态： 队长队长=0=0；A空闲，空