离散事件仿真原理DES

2023-10-29

参考：SYSTEM SIMULATION AND OPTIMIZATION

1.系统仿真原理

1.1系统，模型和系统仿真

1.2系统仿真分类

1.2.1 蒙特卡洛仿真（Monte Carlo Simulation）

1.2.2 离散系统仿真（Discrete Event Simulation DES）

2.2 列表处理（list processling）

1.系统仿真原理

1.1系统，模型和系统仿真

1.2系统仿真分类

1.2.1 蒙特卡洛仿真（Monte Carlo Simulation）

又称随机抽样或者统计模拟方法，泛指所有基于统计采样进行数值计算的方法，适用于两类问题：本身具有随机性，能够转化为概率模型进行求解的确定性问题。如下图中的投针实验，假设在有多条平行线的桌子上扔一颗针，针穿过线的概率是多少，这个问题从数学角度可以通过计算面积得到概率，也可以通过蒙特卡洛仿真实验得到概率。

MCS通过设定随机过程，反复生成时间序列，计算参数估计量和统计量，进而研究其分布特征的方法。当系统过于复杂，无法通过建立精确的数学模型时，可以用随机模拟法来近似计算预计值，随着仿真次数的增加，精度也会越来越高。

1.2.2 离散系统仿真（Discrete Event Simulation DES）

离散系统属于动态类型仿真
由事件驱动（event），事件的发生（occur）是离散且随机的，即系统状态变量（state）的取值是依时间轴离散且随机分布的
此类系统无法用数学方程描述
DES使用两种事件推进机制：后续事件时间推进机制（next event time advance NETA)；固定步长时间推进机制（fixed increment time advance FITA）

1.2.3 连续系统仿真

1.3系统仿真软件

2.离散事件仿真原理

2.1离散仿真术语和概念

随机性（randomness，stochastic，uncertainty）：影响系统稳定性表现的干扰因素，也称噪音
系统（system）：由众多实体（entity）构成，例如顾客，机器和设备，实体之间相互作用，影响，系统状态随着时间变化而发生变化，往往具体某种目的和目标
模型（model）：对现实世界系统（real world system）的逻辑抽象，包含的指标和内容：系统状态，实体及其属性，集合，处理过程，事件，活动和时间延迟
系统状态（system state）：模型中所有变量的所有可能取值的集合
实体（entity）：存在于系统中，可相互区别的具体事物，如顾客，服务员等
实体属性（entity attribute）：实体具有的特征，如类型，加工时间，优先级等
列表（list）：列表有两种含义，一是清单，例如实体名单，事件列表，二是队列，例如排队顾客所形成的队列，且需要实现制定排队规则（FIFO）等
事件（event）：瞬间发生，能够改变系统状态的事情（occurrence）
事件预告（event notice）：记录事件发生时刻，事件相关数据的记录（record），例如事件类型和发生事件等
事件列表（event list）：由事件预告组成，记录将要发生事件的列表，按照事件顺序排列，也称为未来事件列表（future event list）
活动（activity）：活动是一个过程，持续时间长度大体确定，即适合于特定的统计分布和参数，如汽车加油等，会有相关的实体参与
延迟（delay）：延迟也是一个过程，与活动不同，延迟时间长度难以确定，例如顾客在队列中的等待时间，就有很大的随机性
时钟（CLOCK）：用于仿真模型及其模拟过程，具有跳跃性和不连续性，与现实世界的时钟不完全对应，采用大写以示区分
事件调度（event scheduling）：事件发生有事件顺序，事件调度是按照事件发生的事件顺序，建立未来事件列表（future event list FEL），仿真时钟（simulation clock）仅按照事件列表中的时刻推进，跳过那些没有事件和活动发生的事件段（duration）

DES中，仿真过程是面向事件的

未来事件列表（future event list FEL）

如下图为银行系统的事件调度和未来事件列表，整个过程中有3位顾客到达，2位顾客离开，共5个事件，注意事件event是瞬间发生的，与activity（在python仿真库中称为process）不一样，此处顾客A1到达后触发事件e(A1)，之后开启activity直到A2也就是顾客2到来，activity中又引入了新的事件，在FEL中只记录了接下来的两个事件而非全部。

内生事件（endogenouse event）：模型内部活动引起的状态变化而产生的事件，源于系统内部行为，不受系统外因素的影响，如顾客离去，机器故障等
外生事件（exogenous event）：事件的产生是由系统外部因素引起，系统只能承载事件的结果而不能影响事件的发生，如顾客到达，订单到达等
时间推进机制（time advanced mechanism）： DES中的时间并不是真实的时间流动，而是跳跃的，分成NETA和FITA，下图可以看到NETA是按照未来事件列表的发生时间推进的，而FITA是按照固定步长推进时间

2.2 列表处理（list processling）

列表处理有三种方式：顺序存储，索引存储，动态链接（此部分和数据结构中的顺序表，链表，循环队列等内容相似）

2.2.1 顺序存储处理方式

2.2.2 索引存储处理方式

例如顾客2的记录中第三个值即逻辑位置为4，因此排在第4个

2.2.3 动态链接存储方式

例如顾客2的记录中第三，四个值分别是5，6，表示顾客2前面是顾客5，后面是顾客6

3.excel模拟快餐店

数据如下：顾客到达间隔事件服从指数分布，顾客服务时间服从正态分布

以顾客3为例，B列顾客到达时间间隔，C列实际到达时间，D列顾客服务时间均为已经事先可以得到的数据，E列实际开始的服务时间为max（2G，3C)，F列排队等待时间为3E-3C，G列服务结束时间为3E+3D，H列顾客在系统中的总时间3G-3C，I服务台空闲时间max（3C-2G，0）

了解原理后在实现的时候还需要用到一些仿真软件或者仿真库来构建仿真环境，如matlab的simulink，python的simpy，salabim等

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)