排队论讲义ppt课件

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