《排队论讲义学习.pptx》由会员分享，可在线阅读，更多相关《排队论讲义学习.pptx（99页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、概率论及随机过程回顾一、概率论及随机过程回顾随机变量离散型随机变量概率分布和概率分布图概率分布和概率分布图数学期望和方差数学期望和方差常见离散型随机变量的概率分布常见离散型随机变量的概率分布A二点分布?A二项式分布?APoisson分布?1.1、随机变量与概率分布第1页/共99页一、概率论及随机过程复习一、概率论及随机过程复习随机变量离散型随机变量概率分布和概率分布图概率分布和概率分布图数学期望和方差数学期望和方差常见离散型随机变量的概率分布常见离散型随机变量的概率分布A二点分布?A二项式分布?APoisson分布?第2页/共99页随机变量连续型随机变量概率密度函数概率密度函数概率分布函数
2、概率分布函数数学期望和方差数学期望和方差常见连续型随机变量的概率分布常见连续型随机变量的概率分布A均匀分布A指数分布？A正态分布？Ak阶爱尔朗分布？一、随机变量与概率分布 随机变量X为时间间隔，如顾客到达的时间间隔、电话呼叫的时间、产品的寿命等。密度函数第3页/共99页?爱尔朗分爱尔朗分布布 为k个相互独立的随机变量；服从相同参数 的负指数分布；设 ，则T的密度函数为 如k个服务台串联（k个服务阶段），一个顾客接受k个服务共需的服务时间T，T爱尔朗分布。第4页/共99页1.2 随机过程的有关概念n随机过程(Random process)的定义 设 ，是一族随机变量，T是一个实数集，对 是一个随
3、机变量，则称 为随机过程。T：参数集合 当T=0,1,n,时，称为随机序列 ：随机过程的一个状态 状态空间E=X(t)全体可能取值，第5页/共99页n随机过程的基本类型二阶矩过程平稳过程平稳独立增量过程常见随机过程A马尔可夫过程？APoisson过程？A生灭过程？1.2 随机过程的有关概念第6页/共99页定义：若满足如下性质：对任意非负整数 ，只要就有 则称 具有马尔可夫性，或无后效性。马尔可夫过程 马尔可夫链离散过去现在 将来 “将来”的情况与“过去”无关，只是通过“现在”与“过去”发生联系，若“现在”已知，“将来”与“过去”无关。第7页/共99页n时齐的马氏链：马氏链 若满足：则称 为时齐
4、马尔可夫链 系统由状态i经过m 个时间间隔（或m 步）转移到状态j 的转移概率第8页/共99页Poisson过程定义：设 为时间 内到达系统的顾客数，若满足下面三个条件：独立性：在任意两个不相交的区间内顾客到 达的情况相互独立；平稳性：在 内有一个顾客到达的 概率为普通性：在 内多于一个顾客到达 的率为 。则称 为Poisson过程。（1）只与区间长度与 起点无关。（2）单位时间内一个 顾客到达的概率 为 。第9页/共99页Poisson过程与Poisson分布定理1：设 为时间 内到达系统的顾客数 则 为Poisson过程的充要条件是数理统计方法容易初步判断:期望=标准差第10页/共99页P
5、oisson过程与负指数分布定理2：设 为时间 内到达系统的顾客数 则 为参数为 的Poisson过程的 充要条件是相继到达的时间间隔T服从相互 独立的参数为 的负指数分布。负指数分布的性质:马尔可夫性，或无后效性第11页/共99页Poisson过程与Poisson分布的关系：定理1：设 为时间 内到达系统的顾客数 则 为Poisson过程的充要条件是定理2：设 为时间 内到达系统的顾客数 则 为参数为 的Poisson过程的 充要条件是相继到达的时间间隔T服从相互 独立的参数为 的负指数分布。对于Poisson流：单位时间平均到达的顾客数 顾客相继到达的平均间隔时间第12页/共99页定义：设
6、 为一个随机过程，若N(t)N(t)的概率分布具有以下性质：(1)(1)假设N(t)=nN(t)=n，则从时刻到下一个顾客到达时刻止的时间服从参数为 的负指数分布；(2)(2)假设N(t)=nN(t)=n，则从时刻到下一个顾客离开时刻止的时间服从参数为 的负指数分布；(3)(3)同一时刻是只有一个 顾客到达或离去。则称 为一个生灭过程。生灭过程第13页/共99页10nn-1n+1平稳生灭过程系统状态n平衡方程：“流入=流出”系统达到平稳状态时：的分布第14页/共99页系统达到平稳状态时：其中平衡方程：当 时才有意义第15页/共99页二、排队论的基本知识二、排队论的基本知识2 2 2 2.1 1
7、 1 1 排队排队排队排队模型模型模型模型2.2 2.2 2.2 2.2 排队系统的组成和特征排队系统的组成和特征排队系统的组成和特征排队系统的组成和特征第16页/共99页排队论研究的内容性态问题:排队系统的概率规律,如队长分布,等待时间分布等.最优化问题:排队系统的最优设计.统计推断:判定排队系统的类型.第17页/共99页顾客源2.1、排队模型排队系统排队结构服务机构排队规则服务规则接受服务后离去排队系统的的一般表示第18页/共99页服务机构服务台(a)一个队列、单服务台（阶段）第19页/共99页服务台1服务台2(b)一个队列、s个服务阶段服务机构第20页/共99页服务台1服务台2服务机构(
8、c)一个队列、s个服务台 一个服务阶段第21页/共99页服务台3服务台4服务台1服务台2服务机构(d)s个队列、s个服务阶段第22页/共99页服务台3服务台4服务台1服务台2:124:243:3214服务机构(e)混合型第23页/共99页排队结构服务台(f)一个队列服务台(g)s个队列第24页/共99页 输入过程顾客总体:有限,无限.顾客到达方式:单个,成批.顾客到达间隔时间:确定的、随机的.顾客到达的独立性:独立,不独立.输入过程的平稳性:与时间无关(平稳的),与时间有关(非平稳的).2.2、排队系统的组成和特征第25页/共99页顾客到达时间间隔的分布:：第n个顾客与第n-1个顾客到达的时间
9、间隔；：第n个顾客到达的时刻；设令第26页/共99页n顾客到达时间间隔的分布:假定 是独立同分布，分布函数为 ，排队论中常用的有两种：（2）最简流（即Poisson流）（M）：顾客到达时间间隔 为独立的，服从负指数分布，其密度函数为（1）定长分布（D）：顾客到达时间间隔为确定的。因为负指数分布具有无后效性（即Markov性）第27页/共99页 排队及排队规则即时制(损失制)等待制先到先服务:FCFS后到先服务:LCFS随机服务优先权服务：PS队容量:有限,无限;有形,无形.队列数目:单列,多列.第28页/共99页 服务机构服务员数量:无,单个,多个.队列与服务台的组合服务方式:单个顾客,成批顾
10、客.服务时间:确定的,随机的.服务时间和到达间隔时间至少一个是随机的.服务时间分布是平稳的.第29页/共99页服务时间分布:设某服务台的服务时间为V，其密度函数为b（t），常见的分布有：（1）定长分布（D）：每个顾客接受服务的时间 是一个确定的常数。（2）负指数分布（M）：每个顾客接受服务时间 相互独立，具有相互的负指数分布：其中 ，为一常数。-单位时间平均服务完成的顾客数1/-每个顾客的平均服务时间第30页/共99页服务时间分布:（3）k阶爱尔朗（Erlang）分布：每个顾客接受服务 时间服从k阶爱尔朗分布，其密度函数为：第31页/共99页 符号表示:X/Y/ZX-客到达间隔时间分布Y-服务
11、时间分布Z-服务台个数X,Y 可以是:M-M-负指数分布D-D-确定性的E Ek k-k-k阶ErlangErlang分布GI-GI-一般相互独立的到达时间间隔分布G-G-一般(General)General)时间分布排队系统的分类第32页/共99页 扩展符号表示:X/Y/Z/A/B/CA-系统容量B-顾客源中顾客的数量C-服务规则:FCFS,LCFS,等等.n若省略后三项，即是指下面的情形：X/Y/Z/FCFS例：M/M/s/K表示？第33页/共99页 已知:顾客到达间隔时间分布,服务时间分布.求:队长:Ls-系统中的顾客数.排队长(队列长):Lq-队列中的顾客数.Ls=Lq +正在接受服务
12、的顾客数逗留时间:W S-顾客在系统中的停留时间 等待时间:Wq-顾客在队列中的等待时间.WS=Wq+服务时间忙期,损失率,服务强度.排队问题的求解第34页/共99页三三.单服务台负指数分布单服务台负指数分布排队系统分析排队系统分析 3.1 M/M/1模型3.2 M/M/1/N/模型(即系统的容量有限)3.3 M/M/1/m 模型（即顾客源为有限）第35页/共99页顾客源排队系统排队结构服务机构排队规则服务规则接受服务后离去 3.1 M/M/1模型无限输入过程服从参数为 的Poisson过程单队队长无限先到先服务服务时间服从参数为 的负指数分布生灭过程第36页/共99页 求解：:系统达到平稳后
13、，系统有n个顾客的概率。平衡方程：，且当时其中第37页/共99页关于 的几点说明：顾客平均到达率顾客平均服务率一个顾客服务时间一个顾客到达时间服务强度即顾客的顾客平均到达率小于顾客平均服务率时，系统才能达到统计平稳。系统中至少有一个顾客的概率；服务台处于忙的状态的概率；反映系统繁忙程度第38页/共99页 计算有关指标计算有关指标n队长第39页/共99页队列长队列长 计算有关指标第40页/共99页 逗留时间逗留时间:可以证明,Ws服从参数为-的负指数分布.则:等待时间等待时间计算有关指标第41页/共99页计算有关指标Little公式（相互关系）小结平均服务时间平均在忙的服务台数/正在接受服务的顾
14、客数有效到达率第42页/共99页平均忙期 B,忙期出现的概率平均闲期 I,闲期出现的概率(1-)n忙期 B:闲期 I=:(1-)n平均闲期 I=1/闲期的分布与顾客到达时间间隔的相同-服从参数为的负指数分布计算有关指标n忙期与闲期 WHY?1-P0=第43页/共99页平均忙期 B,忙期出现的概率 平均闲期 I,闲期出现的概率(1-)n忙期 B:闲期 I=:(1-)n平均闲期 I=1/n平均忙期 B=(/(1-)/=1/(-)计算有关指标n忙期与闲期 与逗留时间Ws相同!?第44页/共99页例：某医院手术室每小时就诊病人数和手术 时间的记录如下：到达的病人数 出现次数 n un 0 10 1 2
15、8 2 29 3 16 4 10 5 6 6 以上 1 合计 100完成手术时间 出现次数 r vr 0.00.2 38 0.20.4 25 0.40.6 17 0.60.8 9 0.81.0 6 1.01.2 5 1.2 以上 0 合计 100第45页/共99页解：到达的病人数 出现次数 n un 0 10 1 28 2 29 3 16 4 10 5 6 6 以上 1 合计 100每小时病人平均到达率（人/小时）每次手术平均时间（小时/人）每小时完成手术人数（平均服务率）（人/小时）第46页/共99页解：到达的病人数 出现次数 n un 0 10 1 28 2 29 3 16 4 10 5
16、6 6 以上 1 合计 100每小时病人平均到达率（人/小时）每次手术平均时间（小时/人）每小时完成手术人数（平均服务率）（人/小时）完成手术时间 出现次数 r vr 0.00.2 38 0.20.4 25 0.40.6 17 0.60.8 9 0.81.0 6 1.01.2 5 1.2 以上 0 合计 100第47页/共99页解：第48页/共99页3.2 3.2 系统容量有限制的情形系统容量有限制的情形 (M/M/1/N/FCFSM/M/1/N/FCFS）状态转移图状态转移方程N-1N第49页/共99页求排队系统顾客数的分布状况其中第50页/共99页 求排队系统顾客数的分布状况第51页/共9
17、9页 队长队列长 计算有关指标第52页/共99页 逗留时间 等待时间计算有关指标系统已满顾客不能到达的概率-损失率第53页/共99页 有6个椅子接待人们排队，超过6人顾客就离开，平均到达率3人/小时，理发需时平均15分钟。7为系统中的最大顾客数。平均到达率平均到达率:3 3人人/小时小时 平均服务率平均服务率:4 4人人/小时小时举例：单人理发馆排队问题第54页/共99页 顾客到达就能理发的概率 -相当于理发店内没有顾客相当于理发店内没有顾客等待顾客数的期望值第55页/共99页 求有效到达率 顾客在理发馆内逗留的期望时间小时分钟人/小时第56页/共99页 可能的顾客中有百分之几不等待就离开 -
18、求系统中有求系统中有7 7个顾客的概率个顾客的概率第57页/共99页 设：m：为顾客总体数，：每个顾客的到达率，m-Ls ：系统外顾客的平均数，e=（m-Ls）：为系统有效到达率。3.3 3.3 顾客源有限制的情形顾客源有限制的情形 (M/M/1/m/FCFSM/M/1/m/FCFS）含义与上节不同对顾客而言，而不是对系统m对系统而言,有一个顾客到达的概率第58页/共99页状态转移图01mn-1n(m-n+1)(m-n)n+1.m-1m.(m-1)2第59页/共99页状态转移方程状态转移方程F注意到 ，第60页/共99页 求解状态转移方程得求解状态转移方程得有效到达率求解顾客数概率分布第61页
19、/共99页 等待时间正常运转的平均设备台数计算有关指标第62页/共99页 队长队列长逗留时间计算有关指标例：P343#例7第63页/共99页4.1 4.1 标准的标准的 MM/MM/c/c 模型（模型（MM/MM/c/c/）4.2 4.2 标准的标准的 M/M/c M/M/c/NN/型型4.3 4.3 标准的标准的 M/M/c/M/M/c/m/m模型模型四.多服务台负指数分布排队系统分析第64页/共99页规规定：定：各服务台工作是相互独立的，且平均服务率各服务台工作是相互独立的，且平均服务率相同，均为相同，均为 。整个服务机构的平均服务率为：整个服务机构的平均服务率为：c c (当当n n c
20、)c)，n n (当当n c);n c);记记 =/,s s=/c c =/c/c 为服务系统的平均利用率为服务系统的平均利用率 当当 /c c 1 1时，不会排成无限队列。时，不会排成无限队列。4.1 标准的 M/M/c 模型（M/M/c/）第65页/共99页 1 2 c.服务台服务台C C个个系统人数n人第66页/共99页 1 2 c.服务台服务台C C个个系统人数n人n cn c第68页/共99页状态转移图01n-1nn(n+1)n+1.22n-1nccn+1.n cn c第69页/共99页状态转移方程4.1 标准的 M/M/c 模型（M/M/c/）第70页/共99页解差分方程，求得状态
21、概率为4.1 标准的 M/M/c 模型（M/M/c/）第71页/共99页 顾客等候的概率 计算有关指标n平均正接受服务的顾客数=正忙的服务台数解释?第72页/共99页 队长队列长逗留时间及等待时间计算有关指标唯一第73页/共99页 某售票所有三个窗口，顾客到达服从Poisson过程，到达 =0.9 人/分钟，服务 =0.4人/分钟。设顾客到达后依次排成一队向空闲的窗口购票，如图 a.图 a 窗口1=0.4 窗口2=0.4 窗口3=0.4 =0.9M/M/cM/M/c型系统和型系统和c c个个M/M/1M/M/1型系统的比较型系统的比较第74页/共99页图 aM/M/cM/M/c型系统和型系统和
22、c c个个M/M/1M/M/1型系统的比较型系统的比较 窗口1=0.4 窗口2=0.4 窗口3=0.4 =0.3=0.3=0.3=0.9图 b 窗口1=0.4 窗口2=0.4 窗口3=0.4 =0.9第75页/共99页属于M/M/c型系统 c=3,=/=2.25,s=/c=2.25/3 1,符合要求.整个售票所空闲概率平均队长第76页/共99页平均等待时间和逗留时间顾客到达后必须等待概率第77页/共99页 以上例说明,设顾客到达后在每个窗口前各排一队(其它条件不变),共三队,每队平均到达率为:窗口1=0.4 窗口2=0.4 窗口3=0.4 =0.3=0.3=0.3=0.9图 bM/M/cM/M
23、/c型系统和型系统和c c个个M/M/1M/M/1型系统的比较型系统的比较第78页/共99页 模模模模型型型型指标指标指标指标 M/M/3 M/M/33 3个个个个(M/M/1)M/M/1)P P0 0L Lq qL Ls sWWs sWWq q必须等待概率必须等待概率必须等待概率必须等待概率0.07480.07481.701.703.953.954.39 4.39(分钟分钟分钟分钟)1.89 1.89(分钟分钟分钟分钟)0.570.570.25 0.25(子系统子系统子系统子系统)2.25 2.25(子子子子)9.00 9.00(整整整整)10 10(分钟分钟分钟分钟)7.5 7.5(分钟分
24、钟分钟分钟)0.750.75结果比较M/M/cM/M/c型系统和型系统和c c个个M/M/1M/M/1型系统的比较型系统的比较第79页/共99页4.2 标准的 M/M/c/N/模型状态图是多服务台和容量有限的综合平衡方程你会吗?第80页/共99页4.2 标准的 M/M/c/N/模型求系统有n位顾客的概率分布第81页/共99页4.2 标准的 M/M/c/N/模型求系统的指标有效到达率平均被占用的服务台第82页/共99页4.2 标准的 M/M/c/N/模型求系统的指标第83页/共99页4.3 标准的 M/M/c/m模型自学自学第84页/共99页5.1 5.1 M/G/1 M/G/1 模型模型5.2
25、 5.2 M/M/1/1 模型模型5.3 5.3 M/M/EkEk/1/1 模型模型5.一般服务时间 M/G/1模型第85页/共99页设系统的平均到达率为设系统的平均到达率为 ，任一顾客的服务，任一顾客的服务时间为时间为 V V,且有：且有：E E(V V)=1/)=1/，D D(V V)=)=2 2 服务强度服务强度 ：=/不论不论V V服从什么分布，只要服从什么分布，只要 1 1 ,系统就会系统就会达到稳态，并有稳态概率为：达到稳态，并有稳态概率为：P P0 0=1-=1-5.1 M/G/1 模型第86页/共99页根据波拉切克（根据波拉切克（P Pollacekollacek）-欣钦欣钦（
26、K Khintchinehintchine）公式可导出：）公式可导出：其它相关结果5.1 M/G/1 模型第87页/共99页系统对各顾客的服务时间相互独立且为同一个常数 v，则有：E(v)=v=1/，D(v)=0波拉切克-欣钦公式可化简为：5.1 M/D/1 模型第88页/共99页自学5.1 M/Ek/1 模型第89页/共99页6.1 6.1 排队系统最优化问题排队系统最优化问题6.2 6.2 M/M/1M/M/1模型中最优服务率模型中最优服务率6.3 6.3 M/M/c M/M/c 模型中最优服务台数模型中最优服务台数c c6.6.经济分析经济分析_排队系统的最优化排队系统的最优化第90页/
27、共99页系统设计最优化：系统设计最优化：(静态优化问题静态优化问题)设备达到最大效益系统控制最优化：系统控制最优化：(动态优化问题动态优化问题)如何运营使某个目如何运营使某个目标函数最优。标函数最优。6.1 排队系统最优化问题服务水平总费用等待费用服务费用费用极小点第91页/共99页6.2 M/M/1模型中最优服务率单位时间的费用Cs：当 时服务机构单位时间费用Cw：每个顾客在系统停留单位时间的费用标准的标准的/M/M/1M/M/1模型模型第92页/共99页单位时间的纯利润G：每服务1人可得的收入（已知）标准的标准的/M/M/1/NM/M/1/N模型模型6.2 M/M/1模型中最优服务率第93
28、页/共99页6.2 M/M/1模型中最优服务率单位时间的纯利润G：单位时间每台机器运转可得的收入标准的标准的/M/M/1/M/M/1/m/m模模型型第94页/共99页6.3 M/M/c 模型中最优服务台数c边际分析法：因为 z(c*)最小，所以有：每服务台单位时间成本 ：顾客在系统停留单位时间的费用单位时间总成本第95页/共99页6.3 M/M/c 模型中最优服务台数c代入 z 表达式中得：依次求c 1、2、3、的L值，并作两相邻的值之差，根据这个差落在哪个不等式区间里就可定出最优 c 值。化简得：第96页/共99页Little公式（相互关系）小结平均服务时间平均在忙的服务台数/正在接受服务的顾客数有效到达率第97页/共99页小结顾客数分布稳态平衡方程第98页/共99页感谢您的观看。第99页/共99页