数学建模-排队论.pptx

《数学建模-排队论.pptx》由会员分享，可在线阅读，更多相关《数学建模-排队论.pptx（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、排队论的基本知识一、排队论的基本知识目录下页返回上页结束2.排队系统描述排队系统描述3.基本组成部分基本组成部分4.数量指标数量指标5.排队模型的记号排队模型的记号1.背景介绍背景介绍第1页/共70页1 背景介绍有形的队伍超市出口处排队付款餐厅排队买饭公共电话亭打电话无形的队伍114查号台等待服务网络中数据包传输报告等首长批示文件等待打印或发送某些系统也可能根本不允许排队交换机处理呼叫第2页/共70页排队论研究的内容有三部分1.性态问题：即研究排队系统中的概率分布规律2.2.最优化问题：分为静态最优化和动态最优化，即 为系统的最优设计和系统的最优运营3.排队系统的统计推断：判断一个给定的排

2、队系统符合于哪种模型，以便于根据排队理论进行分析研究 第3页/共70页2.排队系统描述排队系统描述 排队系统又称为随机服务系统，是研究服务 请求服务的人或者物顾客；排队系统的共同特征：顾客到达系统的时刻是随机的，为每一位顾客 有为顾客服务的人或者物，即服务员或服务台；目录下页返回上页结束过程和拥挤现象的随机模型.提供服务的时间是随机的，因而整个排队系统的状态也是随机的.第4页/共70页2.2.顾客是怎顾客是怎顾客是怎顾客是怎样排队的样排队的样排队的样排队的排队模型服务窗服务窗服务规则服务规则排队排队排队规则排队规则顾客源顾客源排队系统排队系统1.1.顾客是怎顾客是怎顾客是怎顾客是怎样到达的样到

3、达的样到达的样到达的3.3.顾客是怎顾客是怎顾客是怎顾客是怎样接受服务样接受服务样接受服务样接受服务第5页/共70页排队系统的几种形式排队系统的几种形式：目录下页返回上页结束第6页/共70页目录下页返回上页结束第7页/共70页目录下页返回上页结束第8页/共70页目录下页返回上页结束第9页/共70页目录下页返回上页结束第10页/共70页基本排队过程基本排队过程：从图6666可知，每个顾客由顾客源按一定方式目录下页返回上页结束到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开.第11页/共70页排队论所要研究解决的问题：排队论所要研究解

4、决的问题：面对拥挤现象，人们通常的做法是增加服务设施但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响.如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，就是随机服务系统理论排队论所要研究解决的问题。目录下页返回上页结束第12页/共70页3.排队系统的基本组成部分排队系统的基本组成部分排队系统是由输入过程、排对规则和服务机构组成.(1).输入过程输入过程 指要求服务的顾客是按怎样的规律(i)顾客总体数.又称顾客源、输入源.这是指顾客(ii)顾客到达方式

5、.这是描述顾客是怎样来到系统目录下页返回上页结束到达排队系统的过程，有时也把它称为顾客流.一般可以从3 3个方面来描述个输入过程.的来源.顾客源可以是有限的，也可以是无限的.的，是单个到达，还是成批到达.第13页/共70页 (iii)顾客流的概率分布.或称相继顾客到达的时间(2).排对规则排对规则 指服务台从队列中选取顾客进行(i)损失制 指如果顾客到达排队系统时，所有目录下页返回上页结束间隔的分布.这是求解排队系统有关运行指标问题时，首先需要确定的指标.顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种.服务的顺序.一般可以分为损失制、等待制和混合制等3 3大类

6、.服务台都被先到的顾客占用，那么他们就自动离开系统永不再来.第14页/共70页(ii)等待制 指当顾客来到系统时，所有服务台a.先到先服务FCFS FCFS 按顾客到达的先后顺序对顾客b.先到后服务LCFSLCFSc.随机服务 即当服务台空闲时，不按照排队d.优先权服务目录下页返回上页结束都不空，顾客加入排队行列等待服务.等待制中，服务台在选择顾客进行服务时常有如下四种规则：进行服务.序列而随意指定某个顾客接受服务.第15页/共70页(iii)混合制 这是等待制与损失制相结合的一种服a.队长有限.当排队等待服务的顾客人数超b.等待时间有限.即顾客在系统中的等待时c.逗留时间(等待时间与服务时间

7、之和)有限.目录下页返回上页结束务规则，一般是指允许排队，但又不允许队列无限长下去.具体说来，大致有三种：过规定数量K K时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的.间不超过某一给定的长度T T，当等待时间超过T T时，顾客将自动离去，并不再回来.第16页/共70页(3).服务机构服务机构 (i)服务台数量及构成形式.从数量上说，服务台有单(ii)服务方式.这是指在某一时刻接受服务的顾客数，(iii)服务时间的分布.在多数情况下，对每一个顾客的目录下页返回上页结束服务台和多服务台之分.从构成形式上看，服务台有：单队一-单服务台式；单队一-多服务台并联式；多队一-多服务台并联式

8、；单队一-多服务台串联式；单队一-多服务台并串联混合式，以及多队多服务台并串联混合式等等.它有单个服务和成批服务两种.服务时间是一随机变量.第17页/共70页常见顾客的服务时间分布有：常见顾客的服务时间分布有：定长分布定长分布D(Deterministic)D(Deterministic)、负指数分布负指数分布M(Markov)M(Markov)、k k阶阶ErlangErlang分布分布(E(Ek k)、一般相互独立的时间间隔分布一般相互独立的时间间隔分布GI(General Independent)GI(General Independent)、第18页/共70页n顾客到达时间间隔的分布:

9、假定假定 是独立同分布，分布函数为是独立同分布，分布函数为 ，排队论中常用的有两种：排队论中常用的有两种：（2 2）最简流（即）最简流（即PoissonPoisson流）（流）（M M）：）：顾客到达时间间隔顾客到达时间间隔 为独立的，为独立的，服从负指数分布，其密度函数为服从负指数分布，其密度函数为（1 1）定长分布（）定长分布（D D）：顾客到达时间间隔为确定的。）：顾客到达时间间隔为确定的。因为负指数分布因为负指数分布具有无后效性具有无后效性（即（即Markov性性）第19页/共70页服务时间分布:设某服务台的服务时间为设某服务台的服务时间为V V，其密度函数，其密度函数为为b b（t

10、t），常见的分布有：），常见的分布有：（1 1）定长分布（）定长分布（D D）：每个顾客接受服务的时间）：每个顾客接受服务的时间 是一个确定的常数。是一个确定的常数。（2 2）负指数分布（）负指数分布（M M）：每个顾客接受服务时间）：每个顾客接受服务时间 相互独立，具有相互的负指数分布：相互独立，具有相互的负指数分布：其中其中 ，为一常数。，为一常数。-单位时间平均服务完成的顾客数单位时间平均服务完成的顾客数1/-1/-每个顾客的平均服务时间每个顾客的平均服务时间第20页/共70页服务时间分布:（3 3）k k阶爱尔朗（阶爱尔朗（ErlangErlang）分布：每个顾客接受服务）分布：每个顾

11、客接受服务 时间服从时间服从k k阶爱尔朗分布，其密度函数为：阶爱尔朗分布，其密度函数为：第21页/共70页4.排队系统的主要数量指标排队系统的主要数量指标 排队论主要研究系统的性态，即与排队有关(1).排队系统主要数量指标等待时间、忙期、队长.目录下页返回上页结束的数量指标的概率规律性；系统的优化问题；统计推断，根据资料合理建立模型.目的是正确设计和有效运行各个服务系统，使之发挥最佳效益.所以必须确定判断系统运行优劣的基本数量指标.第22页/共70页(i).等待时间 从顾客到达时刻起到他开始接受服务止这(ii).忙期 忙期是指从顾客到达空闲着的服务机构起，到(iii).队长 队长是指系统中的

12、顾客数(排队等待的顾客数与目录下页返回上页结束段时间称为等待时间.等待时间是个随机变量.从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间，也是随机变量.服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间.这是个随机变量，是服务员最为关心的指标，因为它关系到服务员的服务强度.与忙期相对的是闲期,即服务机构连续保持空闲的时间.在排队系统中，忙期和闲期总是交替出现的.正在接受服务的顾客数之和)；排队长是指系统中正在排队等待服务的顾客数.队长和排队长一般都是随机变量.第23页/共70页(2).数量指标的常用记号(i).主要数量指标WsWs平均逗留时间，即(在任意时刻)进入目录下页返回上页结

13、束的所有顾客数的期望值；等待服务的顾客数的期望值；稳态系统的顾客逗留时间的期望值；稳态系统的顾客等待时间的期望值.Ls-Ls-平均队长，即稳态系统任一时刻平均等待时间，即(在任意时刻)进入 平均等待队长，即稳态系统任一时刻第24页/共70页(ii).其它常用数量指标s 系统中并联服务台的数目；N 稳态系统任一时刻的状态（即系统中U 任一顾客在稳态系统中的逗留时间；Q 任一顾客在稳态系统中的等待时间；目录下页返回上页结束所有顾客数）；平均到达率；平均到达间隔；平均服务率；平均服务时间；第25页/共70页有服务台全部空闲的概率；目录下页返回上页结束繁忙程度的重要尺度.服务强度，即每个服务台单位时间

14、内的平均服务时间，一般有 ，这是衡量排队系统:稳态系统任意时刻状态为n n的概率；特别当n=0n=0时(系统中顾客数为0)0)，即稳态系统所损失率：由于系统的条件限制，使顾客被拒绝服 务而使服务部门受到损失的概率。第26页/共70页 5.排队系统的描述符号排队系统的描述符号 描述符号：X/Y/Z/A/B/CX/Y/Z/A/B/CXX顾客相继到达的间隔时间的分布 ；常用下MM表示到达的过程为泊松过程或负指数分布；DD表示定长输入；GIGI表示一般相互独立的时间间隔分布.YY服务时间的分布；所用符号与表示顾客目录下页返回上页结束列符号：到达间隔时间分布相同.表示K K阶爱尔朗分布；第27页/共70

15、页ZZ服务台个数 ；“1”1”表示单个服务台，“s”(s1)s”(s1)A A系统容量限制(默认为)；如系统有K K个等待位子，则B B顾客源数目（默认为）；分有限与无限两种，表C C服务规则；常用下列符号：FCFSFCFS：表示先到先服务的排队规则；LCFSLCFS：表示后到先服务的排队规则；PRPR：表示优先权服务的排队规则。目录下页返回上页结束表示多个服务台.0K0K1)s(s1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则.中的前3 3个符号.例如，某排队问题为M MM MS S.无限；顾客源无限，先到先服务，单个服务的等待制系统.第29页/共70页一、相关

16、知识回顾一、相关知识回顾1 1、爱尔朗分布爱尔朗分布 为为k k个相互独立的随机变量；个相互独立的随机变量；服从相同参数服从相同参数 的负指数分布；的负指数分布；设设 ，则，则T T的密度函数为的密度函数为 如如k k个服务台串联（个服务台串联（k k个服务阶段），个服务阶段），一个顾客接受一个顾客接受k k个服务共需的服务时间个服务共需的服务时间T T，T T 爱尔朗分布。爱尔朗分布。第30页/共70页2、Poisson过程定义：设 为时间 内到达系统的顾客数，若满足下面三个条件：独立性：在任意两个不相交的区间内顾客到独立性：在任意两个不相交的区间内顾客到 达的情况相互独立；达的情况相互独立

17、；平稳性：在平稳性：在 内有一个顾客内有一个顾客到达的到达的 概率为概率为普通性：在普通性：在 内多于一个顾内多于一个顾客到达客到达 的率为的率为 。则称则称 为为Poisson过程。过程。（1 1）只与区间长度与）只与区间长度与 起点无关。起点无关。（2 2）单位时间内一个）单位时间内一个 顾客到达的概率顾客到达的概率 为为 。第31页/共70页Poisson过程与Poisson分布定理定理1 1：设：设 为时间为时间 内到达系统的顾客数内到达系统的顾客数 则则 为为PoissonPoisson过程的充要条件是过程的充要条件是数理统计方法数理统计方法容易初步判断容易初步判断:期望期望=标准差

18、标准差第32页/共70页Poisson过程与负指数分布定理定理2 2：设：设 为时间为时间 内到达系统的顾客数内到达系统的顾客数 则则 为参数为为参数为 的的PoissonPoisson过程的过程的 充要条件是相继到达的时间间隔充要条件是相继到达的时间间隔T T服从相互服从相互 独立的参数为独立的参数为 的负指数分布。的负指数分布。负指数分布的性质:马尔可夫马尔可夫性，性，或或无无后效性后效性第33页/共70页Poisson过程与Poisson分布的关系：定理定理1 1：设：设 为时间为时间 内到达系统的顾客数内到达系统的顾客数 则则 为为PoissonPoisson过程的充要条件是过程的充要

19、条件是定理定理2 2：设：设 为时间为时间 内到达系统的顾客数内到达系统的顾客数 则则 为参数为为参数为 的的PoissonPoisson过程的过程的 充要条件是相继到达的时间间隔充要条件是相继到达的时间间隔T T服从相互服从相互 独立的参数为独立的参数为 的负指数分布。的负指数分布。对于对于PoissonPoisson流：流：单位时间平均到达的顾客数单位时间平均到达的顾客数 顾客相继到达的平均间隔时间顾客相继到达的平均间隔时间第34页/共70页定义：设 为一个随机过程，若N(t)N(t)的概率分布具有以下性质：(1)(1)假设N(t)=nN(t)=n，则从时刻到下一个顾客到达时刻止的时间服从

20、参数为 的负指数分布；(2)(2)假设N(t)=nN(t)=n，则从时刻到下一个顾客离开时刻止的时间服从参数为 的负指数分布；(3)(3)同一时刻是只有一个 顾客到达或离去。则称 为一个生灭过程。4、生灭过程第35页/共70页1 10 0nn-1n+1平稳生灭过程系统状态平稳生灭过程系统状态n n平衡方程：平衡方程：“流入流入=流出流出”系统达到平稳状态时：系统达到平稳状态时：的分布的分布第36页/共70页系统达到平稳状态时：系统达到平稳状态时：其中其中平衡方程：平衡方程：当当 时才有意义时才有意义第37页/共70页 已知:顾客到达间隔时间分布,服务时间分布.求:队长:Ls-系统中的顾客数.排

21、队长(队列长):Lq-队列中的顾客数.Ls=Lq +正在接受服务的顾客数逗留时间:W S-顾客在系统中的停留时间 等待时间:Wq-顾客在队列中的等待时间.WS=Wq+服务时间忙期,损失率,服务强度.排队问题的求解第38页/共70页三、几类排队论模型三、几类排队论模型1.M/M/S M/M/S 模型模型2.GI/M/n GI/M/n 模型模型目录下页返回上页结束第39页/共70页1.M/M/s M/M/s排队模型排队模型 M/M/sM/M/s排队模型是指s s个服务员的排队系统，顾客到来间隔时间是独立同分布的；服务时间也是独立同分布的；并且独立于输入过程；排队规则是等待制；目录下页返回上页结束含

22、假定：顾客到来间隔时间服从参数为 的指数分布，服务时间服从参数为 的负指数分布，且有隐第40页/共70页 按排队论的基本构成特征，来求解该排队模型(1).基本构成(i)顾客到达规律目录下页返回上页结束的主要数量指标：平均到达率.表示在 时间到达的顾客数，称为排队系统的输入过程.其平均值为 ，即单位时间内到达的顾客数为 ，并称为它服从参数为 的泊松分布，即：第41页/共70页(ii)服务时间目录下页返回上页结束服务率 .表示顾客到达间隔时间序列，其中 表示第n个顾客的到来时刻.可以证明：服从参数 为的泊松分布的充负指数分布.要条件是到达间隔时间序列 独立同分布且服从记Z Z为服务时间，Z Z服从

23、参数为 的负指数分布：则 ，即为每个顾客平均服务时间为 ，从而单位时间内被服务的顾客的平均数为 ，称为平均第42页/共70页 (iii)排队规则按顾客的到达的先后顺序服务，即先到先服务.满足以上三个条件的模型在排队论中记为模型(2).数量特征(只讨论s=1s=1情形)(i)平均队长 稳态下系统内等待服务的顾客数，其数学期目录下页返回上页结束望称为平均等待队长，即M/M/s模型，其中s s为服务员的个数.(其中称为服务强度.).)第43页/共70页(ii)平均逗留时间和平均等待时间平均逗留时间为平均等待时间为则公式称为LittleLittle公式.目录下页返回上页结束第44页/共70页(3).M

24、/M/s M/M/s 排队模型(i)当s=2s=2时 服务强度平均队长平均等待时间 (ii)当s s是任意的服务强度平均队长平均等待时间 目录下页返回上页结束其中为所有服务员均空闲的概率.第45页/共70页例1.某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，每个病人平均需要1515分钟。病人按泊松分布到达，平均每小时到达3 3人。试对此排队系统进行分析.解对此排队系统分析如下：先确定参数值：这是单服务系统有，目录下页返回上页结束=3=3人/h/h=60/15=60/15 人/h=4/h=4人/h/h第46页/共70页故服务强度为：计算稳态概率：这就是急诊室空闲的概率，也是病人不必等待

25、立这就是急诊室空闲的概率，也是病人不必等待立即就能就诊的概率即就能就诊的概率.而病人需要等待的概率则为而病人需要等待的概率则为 这也是急诊室繁忙的概率这也是急诊室繁忙的概率.目录下页返回上页结束第47页/共70页 计算系统主要工作指标急诊室内外的病人平均数：急诊室内外的病人平均数：急诊室外排队等待的病人平均数：急诊室外排队等待的病人平均数：病人在急诊室内外平均逗留时间：病人在急诊室内外平均逗留时间：病人平均等候时间：病人平均等候时间：目录下页返回上页结束第48页/共70页 为使病人平均逗留时间不超过半小时，那么平均为使病人平均逗留时间不超过半小时，那么平均15-12=3min15-12=3mi

26、n即平均服务时间至少应减少即平均服务时间至少应减少3min.3min.3min.3min.目录下页返回上页结束服务时间应减少多少？服务时间应减少多少？由于代入 解得：平均服务时间为：第49页/共70页 若医院希望候诊的病人若医院希望候诊的病人90%90%90%90%以上都能有座位以上都能有座位,则则候诊室至少应安置多少座位候诊室至少应安置多少座位?设应该安置设应该安置个座位个座位,加上急诊室的一个座位加上急诊室的一个座位,目录下页返回上页结束共有共有+1+1+1+1个。要使个。要使90%90%90%90%以上的候诊病人有座位，以上的候诊病人有座位，相当于使相当于使“来诊的病人数不多于来诊的病人

27、数不多于+1+1+1+1个个”的概率的概率不少于不少于90%90%90%90%，即，即第50页/共70页上式两边取对数即候诊室至少应安置即候诊室至少应安置6 6 6 6个座位个座位.目录下页返回上页结束因为故所以第51页/共70页例例2 2 承接例承接例1 1 1 1，假设医院增强急诊室的服务能力，使，假设医院增强急诊室的服务能力，使其同时能诊治两个病人，且平均服务率相同，试分析其同时能诊治两个病人，且平均服务率相同，试分析该系统工作情况，并且，例该系统工作情况，并且，例1 1 1 1、例、例2 2 2 2的结果进行比较。的结果进行比较。解 这相当于增加了一个服务台，故有:目录下页返回上页结束

28、人/h/h人/h/h第52页/共70页病人必须等候的概率,即系统状态N2N2的概率：目录下页返回上页结束第53页/共70页表6-1 6-1 两个系统的比较目录下页返回上页结束第54页/共70页2.GI/M/n GI/M/n排队模型满足下述三个条件的随机服务系统称为GI/M/nGI/M/n排队模型(1).GI/M/sGI/M/s系统的构成b.服务系统由n n个并联的服务台所组成.c.各顾客的服务时间之间是相互独立同分布的，服目录下页返回上页结束是相互独立同分布的随机变量.务时间与到达间隔时间相互独立,且服务时间的分a.顾客到达时刻的间隔布服从参数为 的负指数分布 .第55页/共70页(2).数量

29、特征存在且与初始条件无关，其表达式为：(i)队长目录下页返回上页结束定理6.1 设 为第m m个乘客到达时系统的队长，当时，队长的分布极限 其中 为方程的唯一解，而第56页/共70页目录下页返回上页结束第57页/共70页a.该系统的平稳分布下的平均队长为b.系统的平均队长为c.系统服务台平均占有数目录下页返回上页结束其中第58页/共70页(ii)等待时间存在且与初始条件无关，其表达式为 目录下页返回上页结束令第m m个顾客的等待时间为 ，其分布为定理6.2 对GI/M/nGI/M/n系统，当 时，队长的分布极限其中 都与定理(6.1)(6.1)中的一致.第59页/共70页定理6.3 在GI/M

30、/n系统中，设各顾客服务的时间相互独在平衡状态下，顾客到达是不需要等待的概率为平均等待时间为目录下页返回上页结束等待的时间内，每台服务设施的输出过程（即服务完成离开服务机构的顾客）是一个以 为强度的泊松过程.立且具有公共的以 为参数的负指数分布，则在该顾客第60页/共70页四、模型建立与求解四、模型建立与求解目录下页返回上页结束1.问题分析问题分析 2.基本假设基本假设3.模型的建立与求解模型的建立与求解第61页/共70页 1.问题分析问题分析 将公交车的运行看作是提供服务，即服务机构；将乘客看作顾客，乘客乘坐公交车看作是接受公交的服务.公交车运行中乘客的数目描述了系统的状 态，随着时间的变化

31、，一些乘客得到服务后离去，又有一些新的顾客到来，在人数较多时就要排队等目录下页返回上页结束第62页/共70页服务系统，这里拟用排队论来解决该问题.按排队论的要求，将公交车看作服务机构，乘客看作顾客.候，而且，顾客到来的时间具有随机性，对顾客的服务时间也有随机性，所以公交车运行系统是一个随时间变化的随机动态系统，可以看作一个随机目录下页返回上页结束第63页/共70页 2.基本假设基本假设(i).某站旅客到达为泊松过程某站旅客到达为泊松过程(ii).公交车对每批乘客服务时间为相互独立的负公交车对每批乘客服务时间为相互独立的负目录下页返回上页结束指数分布，指数分布，每批服务时间是指公交车从起始站出

32、乘客到达时间间隔服从参数为 的k k阶爱尔兰分布：发再返回起始站所需的时间为 .第64页/共70页目录下页返回上页结束服从参数 为的负指数分布.与 的关系为：其中 表示运行一个程序的平均时间.第65页/共70页3.模型的建立与求解模型的建立与求解 k阶爱尔朗分布的概率密度为：到达间隔的期望值目录下页返回上页结束第66页/共70页公交车服务系统的服务强度为：以平均等待队长衡量乘客的满意度，系统 以乘客的等待时间在非高峰期不超过10分目录下页返回上页结束服务台的平均占有数衡量公交车公司的利益作为规划模型的目标；钟，高峰期不超过5分钟，以及车容量在区间(50,120)作为约束条件，建立随机规划模型:第67页/共70页约束条件为：对上述模型求解即可得到公交车调度的一个目录下页返回上页结束完整方案.至此，利用排队论来建立调度问题的一个明确、完整的随机规划数学模型，可以利用一般规划模型的求解方法进行求解.第68页/共70页再见目录下页返回上页结束第69页/共70页谢谢您的观看！第70页/共70页