蒙特卡洛方法及其建模应用20164(2)

1、蒙特卡洛蒙特卡洛方法方法介绍及其介绍及其建模应用建模应用排队论排队论排队论的基本知识1排队论模型排队论模型21 背景介绍背景介绍 有形的队伍有形的队伍超市出口处排队付款超市出口处排队付款餐厅排队买饭餐厅排队买饭公共电话亭打电话公共电话亭打电话 无形的队伍无形的队伍114114查号台等待服务查号台等待服务网络中数据包传输网络中数据包传输报告等首长批示报告等首长批示一、排队论的基本知识一、排队论的基本知识排队论研究的内容有三部分排队论研究的内容有三部分1.1.性态问题：即研究排队系统中的概率分布规律性态问题：即研究排队系统中的概率分布规律2.2.最优化问题：分为静态最优化和动态最优化，即最优化问题

2、：分为静态最优化和动态最优化，即 为系统的最优设计和系统的最优运营为系统的最优设计和系统的最优运营3.3.排队系统的统计推断：排队系统的统计推断：判断一个给定的排队系统符合于哪种模型，以便于判断一个给定的排队系统符合于哪种模型，以便于根据排队理论进行分析研究根据排队理论进行分析研究 2.2.排队系统描述排队系统描述 排队系统又称为随机服务系统，是研究服务排队系统又称为随机服务系统，是研究服务 请求服务的人或者物请求服务的人或者物顾客；顾客；排队系统的共同特征：排队系统的共同特征： 顾客到达系统的时刻是随机的，为每一位顾客顾客到达系统的时刻是随机的，为每一位顾客 有为顾客服务的人或者物，即服务员

3、或服务台；有为顾客服务的人或者物，即服务员或服务台；过程和拥挤现象的随机模型过程和拥挤现象的随机模型. .提供服务的时间是随机的，因而整个排队系统提供服务的时间是随机的，因而整个排队系统的状态也是随机的的状态也是随机的. .排队模型服务窗服务窗服务规则服务规则排队排队排队规则排队规则顾客源顾客源排队系统排队系统排队系统的几种形式排队系统的几种形式：基本排队过程基本排队过程： 从图从图6666可知，每个顾客由顾客源按一定方式可知，每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服务，到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服然后服务台按

4、一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开务，获得服务的顾客立即离开.排队论所要研究解决的问题：排队论所要研究解决的问题： 面对拥挤现象，人们通常的做法是增加服务设施面对拥挤现象，人们通常的做法是增加服务设施但是增加的数量越多，人力、物力的支出就越大，甚但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响待的时间就会很长，这样对顾客会带来不良影响.如如何做到既保证一定的服务质量指标，又使服务设施费何做到既保证一定的服务质量指标，又使服务设施费用用经济合理

5、经济合理，恰当地解决顾客，恰当地解决顾客排队时间排队时间与与服务设施费服务设施费用大小用大小这对矛盾，就是随机服务系统理论这对矛盾，就是随机服务系统理论排队论排队论所要研究解决的问题。所要研究解决的问题。3.排队系统的基本组成部分排队系统的基本组成部分排队系统是由输入过程、排对规则和服务机构组成排队系统是由输入过程、排对规则和服务机构组成. .(1).输入过程输入过程 指要求服务的顾客是按怎样的指要求服务的顾客是按怎样的规律规律(i) 顾客总体数顾客总体数. 又称顾客源、输入源又称顾客源、输入源.这是指顾客这是指顾客(ii) 顾客到达方式顾客到达方式. 这是描述顾客是怎样来到系这是描述顾客是怎

6、样来到系统统到达排队系统的过程，有时也把它称为顾客流到达排队系统的过程，有时也把它称为顾客流. .一一般可以从般可以从3 3个方面来描述个方面来描述个输入过程个输入过程. . 的来源的来源.顾客源可以是有限的，也可以是无限的顾客源可以是有限的，也可以是无限的.的，是单个到达，还是成批到达的，是单个到达，还是成批到达. (iii) 顾客流的概率分布顾客流的概率分布. .或称相继顾客到达的时间或称相继顾客到达的时间(2).排对规则排对规则 指服务台从队列中选取顾客进行指服务台从队列中选取顾客进行 (i)损失制损失制 指如果顾客到达排队系统时，所有指如果顾客到达排队系统时，所有间隔的分布间隔的分布.

7、 .这是求解排队系统有关运行指标问这是求解排队系统有关运行指标问题题时，首先需要确定的指标时，首先需要确定的指标. .顾客流的概率分布一般顾客流的概率分布一般有定长分布、二项分布、泊松流有定长分布、二项分布、泊松流( (最简单流最简单流) )、爱尔、爱尔朗分布等若干种朗分布等若干种. .服务的顺序服务的顺序. .一般可以分为损失制、等待制和混一般可以分为损失制、等待制和混合制等合制等3 3大类大类. .服务台都被先到的顾客占用，那么他们就自动服务台都被先到的顾客占用，那么他们就自动离开系统永不再来离开系统永不再来. .(ii)等待制等待制 指当顾客来到系统时，所有服务台指当顾客来到系统时，所有

8、服务台a.先到先服务先到先服务FCFS FCFS 按顾客到达的先后顺序对顾客按顾客到达的先后顺序对顾客b.先到后服务先到后服务LCFSLCFSc.随机服务随机服务 即当服务台空闲时，不按照排队即当服务台空闲时，不按照排队d.优先权服务优先权服务都不空，顾客加入排队行列等待服务都不空，顾客加入排队行列等待服务. .等待制中，等待制中，服务台在选择顾客进行服务时常有如下四种规则：服务台在选择顾客进行服务时常有如下四种规则：进行服务进行服务. .序列而随意指定某个顾客接受服务序列而随意指定某个顾客接受服务. .(iii)混合制混合制 这是等待制与损失制相结合的一种服这是等待制与损失制相结合的一种服a

9、.队长有限队长有限. .当排队等待服务的顾客人数超当排队等待服务的顾客人数超b.等待时间有限等待时间有限. .即顾客在系统中的等待时即顾客在系统中的等待时c.逗留时间逗留时间( (等待时间与服务时间之和等待时间与服务时间之和) )有限有限. .务规则，一般是指允许排队，但又不允许队列无限务规则，一般是指允许排队，但又不允许队列无限长下去长下去.具体说来，大致有三种：具体说来，大致有三种：过规定数量过规定数量K K时，后来的顾客就自动离去，另时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的求服务，即系统的等待空间是有限的. .间不超过某一给定的长度间不超过某一给定的长度T T，当等待

10、时间超，当等待时间超过过T T时，顾客将自动离去，并不再回来时，顾客将自动离去，并不再回来. .(3). 服务机构服务机构 (i)服务台服务台数量数量及构成及构成形式形式. 从数量上说，服务台有单从数量上说，服务台有单(ii)服务方式服务方式. 这是指在某一时刻接受服务的顾客数，这是指在某一时刻接受服务的顾客数，(iii)服务时间的分布服务时间的分布.在多数情况下，对每一个顾客的在多数情况下，对每一个顾客的服务台和多服务台之分服务台和多服务台之分. 从构成形式上看，服务台有：从构成形式上看，服务台有：单队一单队一-单服务台式；单服务台式；单队一单队一-多服务台并联多服务台并联式；式；多队一多队

11、一-多服务台并联式；多服务台并联式；单队一单队一-多服多服务台串联式；务台串联式；单队一单队一-多服务台并串联混合式，多服务台并串联混合式，以及多队多服务台并串联混合式等等以及多队多服务台并串联混合式等等.它有单个服务和成批服务两种它有单个服务和成批服务两种.服务时间是一随机变量服务时间是一随机变量. .常见顾客的服务时间分布有：常见顾客的服务时间分布有： 定长分布定长分布D(DeterministicD(Deterministic) )、 负指数分布负指数分布M(MarkovM(Markov) )、 k k阶阶ErlangErlang分布分布(Ek(Ek) )、 一般相互独立的时间间隔分布一

12、般相互独立的时间间隔分布 GI(GeneralGI(General Independent). Independent).n顾客到达时间间隔的分布顾客到达时间间隔的分布:假定假定 是独立同分布，分布函数为是独立同分布，分布函数为 ，排队论中常用的有两种：排队论中常用的有两种：nX)(tAnX（2 2）最简流（即）最简流（即PoissonPoisson流）（流）（M M）：）： 顾客到达时间间隔顾客到达时间间隔 为独立的，为独立的， 服从负指数分布，其密度函数为服从负指数分布，其密度函数为（1 1）定长分布（）定长分布（D D） 顾客到达时间间隔为确定的。顾客到达时间间隔为确定的。 000)(t

13、tetat 服务时间分布服务时间分布: 设某服务台的服务时间为设某服务台的服务时间为V V，其密，其密度函数为度函数为b b（t t），常见的分布有：），常见的分布有：（1 1）定长分布（）定长分布（D D）：每个顾客接受服务的）：每个顾客接受服务的时间是一个确定的常数。时间是一个确定的常数。（2 2）负指数分布（）负指数分布（M M）：每个顾客接受服务）：每个顾客接受服务时间相互独立，具有相互的负指数分布：时间相互独立，具有相互的负指数分布： 其中其中 ，为一常数。，为一常数。 000)(ttetbt 0 （3 3）k k阶爱尔朗（阶爱尔朗（ErlangErlang）分布：每个顾客）分布：每

14、个顾客接受服务时间服从接受服务时间服从k k阶爱尔朗分布，其密度函阶爱尔朗分布，其密度函数为：数为：tkkektkktb )!1()()(1- - 单位时间平均服务完成的顾客数单位时间平均服务完成的顾客数1/1/ - - 每个顾客的平均服务时间每个顾客的平均服务时间4. 排队系统的主要数量指标排队系统的主要数量指标 排队论主要研究系统的性态，即与排队有关排队论主要研究系统的性态，即与排队有关(1).排队系统主要数量指标排队系统主要数量指标等待时间、等待时间、 忙期、忙期、 队长队长.的数量指标的概率规律性；系统的优化问题；统的数量指标的概率规律性；系统的优化问题；统计推断，根据资料合理建立模型

15、计推断，根据资料合理建立模型. .目的是正确设目的是正确设计和有效运行各个服务系统，使之发挥最佳效益计和有效运行各个服务系统，使之发挥最佳效益. .所以必须确定判断系统运行优劣的基本数量指标所以必须确定判断系统运行优劣的基本数量指标. .(i).等待时间等待时间 从顾客到达时刻起到他从顾客到达时刻起到他开始开始接受服务止这接受服务止这(ii).忙期忙期 忙期忙期是指从顾客到达空闲着的服务机构起，到是指从顾客到达空闲着的服务机构起，到(iii).队长队长 队长队长是指系统中的顾客数是指系统中的顾客数(排队等待的顾客数与排队等待的顾客数与段时间称为等待时间段时间称为等待时间.等待时间是个随机变量等

16、待时间是个随机变量.从顾客从顾客到达时刻起到他接受服务到达时刻起到他接受服务完成完成止这段时间称为逗留时止这段时间称为逗留时间，也是随机变量间，也是随机变量.服务机构再次成为空闲止的这段时间，即服务机构服务机构再次成为空闲止的这段时间，即服务机构连续忙连续忙的时间的时间. .这是个随机变量，是服务员最为关心的指标，因这是个随机变量，是服务员最为关心的指标，因为它关系到服务员的为它关系到服务员的服务强度服务强度. .与忙期相对的是与忙期相对的是闲期闲期, ,即即服务机构连续保持空闲的时间服务机构连续保持空闲的时间. .在排队系统中，忙期和闲在排队系统中，忙期和闲期总是期总是交替交替出现的出现的.

17、 .正在接受服务的顾客数之和正在接受服务的顾客数之和)；排队长排队长是指系统中正在排队是指系统中正在排队等待服务的顾客数等待服务的顾客数.队长和排队长一般都是随机变量队长和排队长一般都是随机变量.(2).数量指标的常用记号数量指标的常用记号(i).主要数量指标主要数量指标WsWs平均逗留时间，即平均逗留时间，即( (在任意时刻在任意时刻) )进入进入的所有顾客数的期望值；的所有顾客数的期望值；等待服务的顾客数的期望值；等待服务的顾客数的期望值；稳态系统的顾客逗留时间的期望值；稳态系统的顾客逗留时间的期望值；稳态系统的顾客等待时间的期望值稳态系统的顾客等待时间的期望值. .Ls-Ls-平均队长，

18、平均队长， 即稳态系统任一时刻即稳态系统任一时刻平均等待时间，即平均等待时间，即( (在任意时刻在任意时刻) )进入进入qW 平均等待队长，即稳态系统任一时刻平均等待队长，即稳态系统任一时刻qL(ii).其它常用数量指标其它常用数量指标s 系统中并联服务台的数目系统中并联服务台的数目；N 稳态系统任一时刻的状态（即系统中稳态系统任一时刻的状态（即系统中U 任一顾客在稳态系统中的逗留时间；任一顾客在稳态系统中的逗留时间；Q 任一顾客在稳态系统中的等待时间；任一顾客在稳态系统中的等待时间；所有顾客数）；所有顾客数）；平均到达率；平均到达率； 平均到达间隔；平均到达间隔；1 平均服务率；平均服务率；

19、平均服务时间；平均服务时间；1 有服务台全部空闲的概率；有服务台全部空闲的概率；繁忙程度的重要尺度繁忙程度的重要尺度. .服务强度，即每个服务台单位时间内的平服务强度，即每个服务台单位时间内的平均服务时间，一般有均服务时间，一般有 ，这是衡量排队系统，这是衡量排队系统 s : :稳态系统任意时刻状态为稳态系统任意时刻状态为n n的概率；的概率；nPP Nn特别当特别当n=0n=0时时( (系统中顾客数为系统中顾客数为0)0)， 即稳态系统所即稳态系统所0P损失率：由于系统的条件限制，使顾客被拒绝服损失率：由于系统的条件限制，使顾客被拒绝服 务而使服务部门受到损失的概率。务而使服务部门受到损失的

20、概率。 5. 排队系统的描述符号排队系统的描述符号 描述符号：描述符号：X/Y/Z/A/B/CX/Y/Z/A/B/CXX顾客相继到达的间隔时间的分布顾客相继到达的间隔时间的分布 ；常用下；常用下MM表示到达的过程为泊松过程或负指数分布；表示到达的过程为泊松过程或负指数分布；DD表示定长输入；表示定长输入；GIGI表示一般相互独立的时间间隔分布表示一般相互独立的时间间隔分布. .YY服务时间的分布；所用符号与表示顾客服务时间的分布；所用符号与表示顾客列符号：列符号：到达间隔时间分布相同到达间隔时间分布相同. . 表示表示K K阶爱尔朗分布；阶爱尔朗分布；kEZZ服务台个数服务台个数 ； “ “1

21、”1”表示单个服务台，表示单个服务台，“s” (s1)s” (s1)A A系统容量限制系统容量限制( (默认为默认为)；如系统有；如系统有K K个等待位子，则个等待位子，则B B顾客源数目（默认为顾客源数目（默认为）；分有限与无限两种，）；分有限与无限两种，表表C C服务规则；服务规则； 常用下列符号：常用下列符号：FCFSFCFS：表示先到先服务的排队规则；：表示先到先服务的排队规则；LCFSLCFS：表示后到先服务的排队规则；：表示后到先服务的排队规则；PRPR： 表示优先权服务的排队规则表示优先权服务的排队规则。表示多个服务台表示多个服务台.0K0K1)s (s1)个服务台；系个服务台；

22、系统等待空间容量无限统等待空间容量无限( (等待制等待制) )；顾客源无限，采；顾客源无限，采用先到先服务规则用先到先服务规则. .中的前中的前3 3个符号个符号. .例如，某排队问题为例如，某排队问题为M MM MS S.无限；顾客源无限，先到先服务，单个服务的等无限；顾客源无限，先到先服务，单个服务的等待制系统待制系统. 已知已知: 顾客到达间隔时间分布顾客到达间隔时间分布, 服务时间分布服务时间分布. 求求: 队长队长: Ls - 系统中的顾客数系统中的顾客数. 排队长排队长(队列长队列长): Lq - 队列中的顾客数队列中的顾客数. Ls = Lq + 正在接受服务的顾客数正在接受服务

23、的顾客数 逗留时间逗留时间: W S- 顾客在系统中的停留时间顾客在系统中的停留时间 等待时间等待时间: Wq - 顾客在队列中的等待时间顾客在队列中的等待时间. WS = Wq + 服务时间服务时间 忙期忙期, 损失率损失率, 服务强度服务强度.排队问题的求解排队问题的求解二、二、M/M/sM/M/s排队模型排队模型 M/M/sM/M/s排队模型是指排队模型是指s s个服务员的排队系统，个服务员的排队系统，顾客到来间隔时间是独立同分布的；顾客到来间隔时间是独立同分布的；服务时间也是独立同分布的；服务时间也是独立同分布的；并且独立于输入过程；并且独立于输入过程；排队规则是等待制；排队规则是等待

24、制；含假定：含假定：顾客到来间隔时间服从参数为顾客到来间隔时间服从参数为 的指数分布，的指数分布，服务时间服从参数为服务时间服从参数为 的负指数分布，且有隐的负指数分布，且有隐 按排队论的基本构成特征，来求解该排队模型按排队论的基本构成特征，来求解该排队模型(1).基本构成基本构成(i) 顾客到达规律顾客到达规律()( ),0,1,2!kttP X tkekk 的主要数量指标：的主要数量指标：平均到达率平均到达率.表示在表示在 时间到达的顾客数，称为排队系统的输入过程时间到达的顾客数，称为排队系统的输入过程.()Xt( ,)t tt 其平均值为其平均值为 ，即单位时间内到达的顾客数为，即单位时

25、间内到达的顾客数为 ，并称为，并称为t它服从参数为它服从参数为 的泊松分布，即的泊松分布，即：t(ii) 服务时间服务时间服务率服务率 . .表示顾客到达间隔时间序列，其表示顾客到达间隔时间序列，其1|nnnnss 中中 表示第表示第n个顾客的到来时刻个顾客的到来时刻. .n 可以证明可以证明： 服从参数服从参数 为的泊松分布的充为的泊松分布的充( )X tt负指数分布负指数分布. .要条件是到要条件是到达间隔时间序列达间隔时间序列 独立同分布且服从独立同分布且服从ns记记Z Z为服务时间，为服务时间，Z Z服从参数为服从参数为 的负指数分布的负指数分布：01()00tteP Ztt 则则 ，

26、即为每个顾客平均服务时间为，即为每个顾客平均服务时间为 ，从，从1EZ 1 而单位时间内被服务的顾客的平均数为而单位时间内被服务的顾客的平均数为 ，称为平均，称为平均 (iii) 排队规则排队规则按顾客的到达的先后顺序服务，即先到先服务按顾客的到达的先后顺序服务，即先到先服务. . 满足以上三个条件的模型在排队论中记为模型满足以上三个条件的模型在排队论中记为模型(2).数量特征数量特征( (只讨论只讨论s=1s=1情形情形) )(i) 平均队长平均队长 稳态下系统内等待服务的顾客数，其数学期稳态下系统内等待服务的顾客数，其数学期望称为平均等待队长，即望称为平均等待队长，即M/M/s模模型，其中

27、型，其中s s为服务员的个数为服务员的个数. .1L( (其中其中称为服务强度称为服务强度.).)21qL (1)(ii)平均逗留时间和平均等待时间平均逗留时间和平均等待时间平均逗留时间为平均逗留时间为平均等待时间为平均等待时间为则公式则公式称为称为LittleLittle公式公式. .1LW 11()qW LW qqLW qLL1qWW(3). M/M/s M/M/s 排队模型排队模型(i) 当当s=2s=2时时 服务强度服务强度平均队长平均队长平均等待时间平均等待时间 (ii) 当当s s是任意的是任意的服务强度服务强度平均队长平均队长平均等待时间平均等待时间 212222221L 22222(1)LW s 02()!(1)sssLsps ssLW 其中其中为所有服务员均空闲的