建模仿真-witness-第2章

第2章离散事件系统仿真的基本知识主讲人：赵月霞zhaoyuexia@物流系统建模与仿真本章主要内容DEDS的概念DEDS的基本要素

DEDS仿真的基本步骤仿真实例物流系统建模与仿真1.DEDS的概念根据仿真的研究对象，系统仿真可以分成连续系统仿真和离散事件系统仿真（DiscreteEventDynamicSystem

）。离散事件系统的特点是：系统的状态变化只在离散点上发生，且发生的时刻往往是随机的，系统的状态变化是由随机事件驱动的。举例：排队系统生产领域和物流领域的大多数系统为离散事件系统物流系统建模与仿真2.1离散事件系统的基本要素5个基本要素：实体、属性、事件、活动、进程。实体：系统中我们感兴趣的对象。属性：实体的属性或性质。活动:具有一定时间长度的任务或工作事件:导致系统状态改变的瞬间行为。进程：在一些更确切的术语中，进程是事件、活动和延迟按时间顺序排列的表，这个表定义了一个实体经过系统时的生命周期。延迟：与活动相比，延迟的持续时间不由建模者事先指定，而是由系统条件决定的。状态：变量集，它们包含描述系统在任何时间所必需的所有信息。注：分析系统必须要首先明确仿真目的物流系统建模与仿真顾客n的进程时间到达事件开始服务结束服务事件延迟活动Dump-TruckProblem

：6辆翻斗车用于从小煤矿到铁路装卸煤。每一辆车由两台装载机之一进行装煤。装载完毕后，卡车立即开到地秤处尽可能快地称重。物流系统建模与仿真以排队系统和库存系统为例。在仓储系统中，货物是临时实体；货位、搬运机器是永久实体。属性：货物的几何物理特性、到达时间间隔、到达批量。事件：货物入库，物品出库。活动：存储。在银行排队系统中，顾客和服务员是实体，顾客到达时间间隔、服务时间是属性，事件：顾客到达和顾客离去。状态变量：队列长度和服务员忙闲程度。思考：请在下列系统中命名一些实体、属性、事件、活动和进程：零售商店，汽车总装线，医院手术室，银行储蓄所。物流系统建模与仿真仿真钟：定义：仿真模型中用来记录仿真当前时刻的变量。仿真钟的推进有两种经典方法：固定步长推进法和变步长推进法。举例物流系统建模与仿真统计累加器离散事件系统的状态变量随着事件的不断发生而呈现出动态变化的过程。由于这种变化是随机性的，某一次仿真运行得到的状态变化过程，只不过是随机过程的一次取样，它们只有在统计意义下才有参考价值。因此，需要有一个统计累加器构建，用来跟踪记录各种输出性能指标在仿真进程中的中间结果。物流系统建模与仿真2.2蒙特卡罗方法

2.2.1蒙特卡罗方法的基本思想

2.2.2蒙特卡罗方法的应用

物流系统建模与仿真102.2.1蒙特卡罗方法的基本思想

蒙特卡罗（MonteCarlo）方法，也称为随机抽样方法或统计测试方法，是一种与一般数值计算方法有本质区别的计算方法，属于实验数学的一个分支。基本思想：当实验次数充分多时，某一事件出现的频率近似等于该事件发生的概率。即：当N充分大时，有（2-1）2.2蒙特卡罗方法物流系统建模与仿真式中，p为某一事件发生的概率；

N为实验次数；

n在N次实验中该事件出现的次数。物流系统建模与仿真图2-3运用蒙特卡罗方法的随机采样来求解圆面积图2-4进行多次采样的蒙特卡罗方法计算单位圆面积的值物流系统建模与仿真132.2.2蒙特卡罗方法的应用应用蒙特卡罗方法进行仿真分析的原理利用各种不同分布随机变量的抽样序列来仿真实际系统的概率模型，给出问题数值解的渐近统计估计值。要点如下对问题建立一个简单且便于实现的概率统计模型，使要求的解恰好是所建模型的概率分布或数学期望；物流系统建模与仿真根据概率统计模型的特点和实际计算的需要，对模型进行改进，以便减小仿真结果的方差，降低成本、提高效率；建立随机变量的抽样方法，其中包括产生伪随机数及各种分布随机变量抽样序列的方法；给出问题解的统计估计值及其方差或标准差。物流系统建模与仿真15蒙特卡罗方法应用或实施过程的三个主要步骤构造或描述概率过程

以已知概率分布进行抽样建立各种估计量物流系统建模与仿真排队系统仿真实例（教材第二章2~5节）排队系统的关键元素是顾客和服务台。“顾客”可以指到达设施并请求服务的任何事物，“服务台”可以指能够提供所需服务的任何资源。系统顾客服务台修车厂车维修人员医院病人医生生产线箱子打包机洗衣店脏衣服洗衣机公共交通乘客公共汽车公路网络汽车交通灯.........物流系统建模与仿真1排队系统的3个基本组成部分：到达模式：顾客的到达规律服务模式：服务台的个数和服务时间排队规则：服务时对顾客的选取规则严格意义上来说，一个排队系统由拟到达总体、到达种类、服务机制、系统容量和排队规则来描述。Kendall[1953]提出了一种被广泛应用的描述并行服务台系统的符号体系。其简单版本基于A/B/c/N/K的形式。A--到达时间间隔的分布B--服务时间的分布c--并行服务台的个数N--系统的容量K--拟到达总体的大小物流系统建模与仿真2排队系统常用的输出参数平均等待时间平均通过系统的时间平均队长系统中平均滞留的实体数服务台利用率......物流系统建模与仿真3排队理论与排队仿真分析的关系在优化排队系统时，分析者通常要在服务台利用率和顾客满意度之间做出权衡。1）对于一些简单的系统，系统的性能指标可以通过数学的方法计算出来。与使用仿真模型相比，可以节省时间和费用。2）对于复杂系统的模型，通常通过先做出许多简化假设，转变为易解析处理的模型，对系统性能进行粗略评价。然后通过详细的，更接近实际的仿真模型，对这些粗略的评价进行优化。以下实例仅为较简单的说明仿真的过程，不是要真正解决系统的实际问题。物流系统建模与仿真Simulationbyhand步骤:

分析模型、画出事件流程图。确定仿真的每个输入数据（主要指概率分布）.

构造仿真表对仿真表的每一行，进行仿真。计算统计数据.

仿真完毕，累加数据，计算性能指标。物流系统建模与仿真例题：单队列排队系统顾客以1-8min分钟等概率分布到达CheckoutCounter（见Table2.6)。服务员的服务时间为1－6min(概率见Table2.7)要求：仿真6个顾客，以分析系统的性能。物流系统建模与仿真第1步：分析模型

实体：服务员、顾客

系统状态:

顾客数目、服务员状态（Busy,Idle)

事件：顾客到达事件(ArrivalEvent)

离开事件（DepartureEvent)

活动：

服务、排队等待（Delay)

仿真时钟（SimulationClock):

用来记录当前仿真的时刻。物流系统建模与仿真事件流程图（ExecutionofEvent)定义：对于每个事件，都有唯一的一个事件流程图。它表示系统如何对这个事件进行处理、执行。物流系统建模与仿真“离开事件”流程图（简化版）图4.1离开事件（服务完成）的流程图物流系统建模与仿真到达事件”流程图（简化版）图4.2顾客到达事件的流程图物流系统建模与仿真第2步：确定仿真的输入数据—顾客到达间隔、服务时间。（通过查表得到）到达间隔时间/min概率累计概率随机数区间10.1250.125001～12520.1250.250126～25030.1250.375251～37540.1250.500376～50050.1250.625501～62560.1250.750626～75070.1250.875751～87580.1251.000876～1000服务时间/min概率累计概率随机数区间10.100.1001～1020.200.3011～3030.300.6031～6040.250.8561～8550.100.9586～9560.051.0095～100表2.6表2.7物流系统建模与仿真到达时间间隔的确定customerrandomdigitstimebetweenarrivals1264131121(由112查表2.6得到)467865289368717物流系统建模与仿真服务时间的确定customerrandomdigitstimebetweenarrivals184421823875(由87查表2.7得到)48145616915物流系统建模与仿真第3步：构造仿真表。（手算仿真的本质是仿真表格）顾客到达间隔到达时间服务时间等待时间服务结束时间逗留时间服务员空闲时间10

4

物流系统建模与仿真第4步：对每个顾客进行仿真顾客到达间隔到达时间服务时间等待时间服务结束时间逗留时间服务员空闲时间1

04044

2112365031254

11

9

0

468

43

15

7

0

5311

14

16

5

0

6718

50

23

5

2

物流系统建模与仿真第5步：汇总统计数据

顾客的平均等待时间顾客必须等待的概率服务员空闲的比例平均服务时间平均到达间隔时间等待顾客的平均等待时间顾客在系统中的平均逗留时间物流系统建模与仿真平均等待时间=顾客在队列中等待的总时间/总顾客数顾客必须在队列中等待的概率=等待的顾客数/总顾客数服务台空闲的概率=服务台空闲的总时间/仿真的总运行时间平均服务时间=总服务时间/总顾客数顾客在系统中花费的平均时间=顾客在系统中花费的总时间/总顾客数物流系统建模与仿真报纸经销商问题仿真（教材第6节）问题描述：报纸的订购与销售问题是一个经典的库存问题。报摊以33美分买进每张报纸，以50美分卖出。当日结束时销售不完的报纸作为废品处理，每份卖5美分。报纸以10份为一捆订购，因此，报摊可以买50份，60份等等。有三种类型的报纸，分别是良、中和差，他们的概率是0.35,0.45和0.20。每天对于报纸需求的分布见下表2-15。要解决的问题是，计算报摊应该订购报纸的最优数量。为完成这项工作进行了20天的仿真并记录了每天的利润。利润按以下公式计算：利润=销售收入-报纸成本-额外需求的利润损失+报废报纸的回收费物流系统建模与仿真需求需求概率分布良中差400.030.100.44500.050.180.22600.150.400.16700.200.200.12800.350.080.06900.150.040.001000.070.000.00表2-15每天报纸需求量的分布报纸类型概率累计概率随机数字分配良0.350.3501～35中0.450.8036～80差0.201.0081～100表2-16报纸类型的随机数字分布物流系统建模与仿真需求需求概率分布随机数字分配良中差良中差400.030.100.4401～0301～1001～44500.080.280.6604～0811～2845～66600.230.680.8209～2329～6867～82700.430.880.9624～4369～8883～94800.780.961.0044～7889～9695～100900.931.001.0079～9397～100—1001.001.001.0094～100—

表2-17报纸需求的随机数字分布物流系统建模与仿真用仿真来解决这一问题，需要设定每天购买的报纸数量（购买策略），进行周期20天的报纸需求仿真来确定总利润。改变购买策略，重复运行仿真直至找到最佳的值。表2-18为每天订购70份报纸策略的仿真表格。物流系统建模与仿真天报纸类型的随机数字报纸类型需求的随机数字需求销售收入格外需求的利润损失废品回收收入每日利润158中9380351.7—10.2217良6380

35

1.7

—

10.2

321良3170

35

—

—

11.9

445中1950

25

—

1

2.9

543中9180

35

1.7

—

10.2

……

表2-18物流系统建模与仿真

(M,N)库存系统---上限订货库存系统的仿真（补充）订货Leadtime=0Backorder顾客需求物流系统建模与仿真库存模型库存成本:－持有成本(carryingcost):购买货物的利息、仓库的租借、人力雇佣。－订购成本：－损失成本库存模型的目的：最小化总成本。订购量=上限订货水平-盘点库存量+短缺量；订货将首先满足短缺；(M,N)库存模型的研究目的：对不同的M,N组合，哪个成本最小？物流系统建模与仿真系统模型状态：

库存水平事件：

“顾客需求”事件（出库）“库存检查”事件（清库）“订单到达”事件（入库）物流系统建模与仿真(M,N)库存系统仿真（冰箱）Example2.4库存容量M＝11.库存检查周期N=5天.仿真开始时，期初库存为3.

订购只可能发生在库存检查的时刻（每个检查周期的最后一天下班）！订购数量为:

订购数量=库存容量－期末库存＋缺货数量(backorder）物流系统建模与仿真问题说明：每天需求的冰箱数量为随机数，可能为0、1、2、3、4件。其概率分别对应于0.10、0.25、0.35、0.21、0.09。如表2.19所示。订单的前置期（lead-time)可能为1、2、3天，其概率分别为0.6、0.3、0.1。如表2.20所示。仿真要求：（1）仿真开始时，有3个冰箱在库存。订购的8个冰箱将在2天后到达。（2）库存容量M=11,库存检查周期N＝5仿真目的：预测系统的期末平均库存、平均缺货数量等。物流系统建模与仿真需求概率累计概率随机数区间00.100.1001～1010.250.3511～3520.350.7036～7030.210.9171～9140.091.0092～100表2.19日需求量的随机数字分配表物流系统建模与仿真表2.20订单前置期的随机数字分配前置期概率累计概率随机数字分配区间10.60.6

1－620.30.9

7－930.11

10物流系统建模与仿真Table2.21(M,N)库存系统仿真表(冰箱）天周期期初库存随机数字－需求需求期末库存缺货数量订购数量随机数字-前置期前置期订单到达还需的天数113261

2

0

--

--

--

1

21

2

682

0

0

--

--

--

--

3

1

8

331

7

0

--

--

--

--

4

1

7

392

5

0

--

--

--

--

5

1

5

863

2

0

9

82

2

6

22

181

1

0

--

--

--

1

7

2

1

642

0

1

--

--

--

--

8

2

9

793

5

0

--

--

--

--

9

2

5

552

3

0

--

--

--

--

10

2

3

743

0

0

11

72

2

11

30

211

0

1

--

--

--

--

12

3

0

432

0

3

--

--

--

--

13

3

11

492

6

0

--

--

--

--

14

3

6

903

3

0

--

--

--

--

15

3

5

351

2

0

9

21

1物流系统建模与仿真(M,N)库存系统性能分析期末库存均值平均缺货数量物流系统建模与仿真本章学习提示明确手工仿真的目的掌握手工仿真的步骤。课下思考学习：1）执行(M,N)库存系统手工仿真表的第2个周期，理解事件流程图在仿真过程中的作用。2）图片给出了报童模型问题，请有兴趣的同学参考。物流系统建模与仿真2.3离散事件系统仿真步骤1）确定仿真目标：针对所关心的问题不同，建立的系统模型、设定的输入变量和输出变量都各不相同。确定仿真目标是是系统调研和建模的依据。2）进行系统调研：系统调研时了解系统运行状况和采集系统数据资料的过程。（将调研所获取的数据和参数整理列表，由需求方进行针对性的填写，保证资料的完整性和准确性）3）建立系统模型：系统模型由模型和模型参数两部分组成离散事件系统模型最常用的是建立系统的流程图模型。物流系统建模与仿真4）确定仿真算法仿真算法是控制仿真钟推进的方法，是系统仿真的核心。目前最常用的有事件调度法、活动扫描法和进程交互法。5）建立仿真模型6）验证与确认模型模型的验证主要检验所建立的仿真模型（包括系统组成的假设、系统结构、参数及其取值、对系统的简化和抽象）能否被准确地描述成可执行的模型。模型的确认则是考察所建立的模型及模型的运行特征能否代表所要研究的实际系统物流系统建模与仿真验证主要是检验所建立的仿真模型是否被准确的描述为可执行的模型。（计算机程序可以正常运行吗？模型的输入参数和逻辑结构被计算机正确表达了吗？）方法1）仿真低速运行时，观看动画和仿真钟是否同步运行。方法2）通过交互命令窗口，显示动态图，询问资源和流动项目的属性和状态。方法3）输入多组仿真参数值，验证仿真结果是否合理。物流系统建模与仿真确认模型是考察所建立的模型及模型的运行特征是否能够代表所