运筹学基础及应用(第五版)-(第10章排队论)课件.ppt

1、2023-1-261运筹学运筹学OPERATIONS RESEARCH2023-1-2622023-1-2632023-1-2642023-1-2652023-1-2662023-1-2672023-1-2682023-1-2692023-1-26102023-1-26112023-1-26122023-1-26132023-1-26142023-1-26152023-1-26162023-1-26172023-1-26182023-1-26192023-1-26202023-1-26212023-1-2622f(t)=其中其中2023-1-2623f(t)=2023-1-26242023-1

2、-26252023-1-26262023-1-26272023-1-2628 2023-1-26292023-1-26302023-1-2631Little 公式公式ssWLqqWL/ssLW/qqLW 其中其中 是是单位时间内到达的平均顾客数；单位时间内到达的平均顾客数；是是单位时间内可以服务完的平均顾客数。单位时间内可以服务完的平均顾客数。/1qsWW单位时间内到达的平均顾客数单位时间内到达的平均顾客数/qsLL0nnsnpL1)(snnqpsnL又又如果求得如果求得Pn ,则则 即可得到。即可得到。另外另外 1-P0 是系统的忙期概率。是系统的忙期概率。qsqSWWLL,2023-1-2

3、6322023-1-26332023-1-2634一、最简单流一、最简单流1、定义、定义;在时长为 t 的时间段内，有k个顾客到达的概率 服从poisson分布：t时段内平均到达顾客数；,.2,1,0,!)()(kekttvtkk)(tvk,tE,tE单位时段内平均到达顾客数2023-1-26352、最简单流的性质、最简单流的性质（1）平稳性平稳性：在一定时间间隔内，有k个顾客到达的概率只与时长有关，与起始时刻无关；（2）无后效性无后效性：a,a+t时段内有k个顾客到达的概率与a时刻之前的客流无关；（3）普通性：普通性：在足够小的时段内有2个或个以上顾客到来的概率为零。说明：1、最简单流的性质

4、可以简化有关计算；2、假设所研究的问题都是最简单流，或近似最简单流2023-1-2636二、最简单流的有关计算二、最简单流的有关计算1、单位时间内到达的顾客数2、内没有顾客到达的概率3、恰有一个顾客到达的概率4、若顾客到达 poisson分布，则相继到达间隔时间 负指数分布 tt,t,tttttotetvt1)(1)(0ttvtv)(1)(012023-1-2637三、服务时间三、服务时间设服务时间设服务时间 负指数分布负指数分布1、单位时间内服务完毕，离去的顾客数2、内没有顾客离去的概率3、恰有一个顾客离去的概率4、若干负指数分布的最小值也是负指数分说明：服务机构中有s个并联服务台，各台 负

5、指数分布，则整个服务时间 负指数分布。,ttt,tttst1t2023-1-2638第第38页页生灭过程2023-1-2639第第39页页2、t t时刻有时刻有n-1n-1个顾客，个顾客，时刻系统中有时刻系统中有n n个顾客的个顾客的概率为概率为1、t t时刻有时刻有n n个顾客，个顾客，时刻系统中仍有时刻系统中仍有n n个顾客的个顾客的概率为概率为 时刻系统中有时刻系统中有n个顾客的概率个顾客的概率tttt)t(o tt1)t(pnnntt)t(ot)t(p1n1n3、t t时刻有时刻有n+1n+1个顾客，个顾客，时刻系统中有时刻系统中有n n个顾客的个顾客的概率为概率为tt)t(ot)t(

6、p1n1n4、t t时刻为时刻为n,n-1,n+1n,n-1,n+1个顾客之外的情况，个顾客之外的情况，时刻时刻系统中有系统中有n n个顾客的概率为个顾客的概率为tt)t(o2023-1-2640第第40页页于是于是)t(ot)t(pt)t(p tt1)t(p)t(o)t(ot)t(p)t(ot)t(p)t(o tt1)t(p)tt(p1n1n1n1nnnn1n1n1n1nnnnn特别的，特别的，n=0时时)t(ot)t(p t1)t(p)tt(p110002023-1-2641第第41页页移项求极限，得差分微分方程移项求极限，得差分微分方程)()()()()()()()(110001111t

7、PtPtPtPtPtPtPnnnnnnnnt时时,平稳状态平稳状态nntPtP)(lim0n11n0n0.11P01n01nnp.P2023-1-2642排队模型排队模型一、一、M/M/1/M/M/1/模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布；服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布；服务台数为服务台数为1 1；系统的空间为无限，允许永远排队。系统的空间为无限，允许永远排队。2023-1-26432023-1-26442023-1-26452023-1-26462023-1-26472023-1-2648/(/()=/

8、()2023-1-26492023-1-26502023-1-26512023-1-26522023-1-26532023-1-26542023-1-2655二、二、M/M/1/NM/M/1/N 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布；服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布；服务台数为服务台数为1 1；系统的空间为有限，最大容量系统的空间为有限，最大容量N N。2023-1-26561 1、稳定状态下，系统中有稳定状态下，系统中有n n个顾客的概率个顾客的概率nP012N-1N。1110111,)(NNnnnppN

9、nppppp2023-1-2657由由 及上述差分方程可解得：及上述差分方程可解得：10NnnP)1(/,1111110nNnNPP单位时间内的平均到达率单位时间内的平均到达率 )1(NeP单位时间内的平均单位时间内的平均有效到达率有效到达率 系统中有系统中有N N个顾客时，到达率为个顾客时，到达率为0 0，只有在少于，只有在少于N N个顾客时个顾客时到达率才有意义。到达率才有意义。还可验证还可验证 )1(0Pe2023-1-26582 2、系统运行指标系统运行指标1N1NN1nns1)1N(1nPL)1()1(01PLPnLSNnnq)P1(LLW0SeSs1WWsq2023-1-2659例

10、、例、单人理发店有六张椅子接待客人排队理发，当单人理发店有六张椅子接待客人排队理发，当6 6张椅张椅子坐满时，后来的顾客就不进店，随即离开，顾客平子坐满时，后来的顾客就不进店，随即离开，顾客平均到达率均到达率3 3人人/小时，理发平均需时小时，理发平均需时1515分钟，求：分钟，求：1 1、求顾客一到达就能理发的概率；、求顾客一到达就能理发的概率；2 2、求需要等待的平均顾客数；、求需要等待的平均顾客数；3 3、求有效到达率；、求有效到达率；4 4、每个顾客的平均逗留时间；、每个顾客的平均逗留时间；5 5、在可能到来的顾客中有百分之几不等待就离开？、在可能到来的顾客中有百分之几不等待就离开？2

11、023-1-2660解、解、该问题中该问题中 N=7 N=7，1 1、2 2、4/3/,4,32778.0)4/3(14/31111710NP11.2)4/3(1)17(4/314/3171771nnsnPL39.1)2778.01(11.2)1()1(071PLPnLSnnq2023-1-2661小时）人/(89.2)2778.01(4)1(0Pe3 3、4 4、5.5.损失率损失率分钟小时43.80.732.892.11eSsLW%3.73/43/414/317177）（）（P2023-1-2662三、三、M/M/s/M/M/s/模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参

12、数为 的负指数分布；的负指数分布；服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布；服务台数为服务台数为s s；系统的空间为无限系统的空间为无限2023-1-26631 1、稳定状态下，系统中有稳定状态下，系统中有n n个顾客的概率个顾客的概率nP012nn+1n)1(n。n-12nn+1ssn-1sn sn 2023-1-2664snpnppnsnpsppsppnnnnnn1,)()1(,)(111101由由 及上述差分方程可解得：及上述差分方程可解得：10nnPsnPsssnPnPskPnsnnnsksk,!1)1(/,!111!1!10011002023-1-26652

13、2、系统运行指标系统运行指标/qsLL021)1(!)()(PssPsnLssnnqSsLW qqLW 2023-1-2666例、例、某售票点有三个窗口，顾客的到达服从某售票点有三个窗口，顾客的到达服从poissonpoisson 过过程，平均到达率程，平均到达率 ，服务时间服从负，服务时间服从负指数分布，平均服务率指数分布，平均服务率 。现在假设顾客到达后排成一队，一次到空闲的窗口买现在假设顾客到达后排成一队，一次到空闲的窗口买票。分析下列各问题：票。分析下列各问题：1 1、整个售票点空闲的概率；、整个售票点空闲的概率；2 2、平均排队长；、平均排队长；3 3、平均排队时间；、平均排队时间；

14、4 4、顾客到达后必须等待的概率。、顾客到达后必须等待的概率。分钟人/9.0分钟人/4.02023-1-2667解、解、该问题中该问题中 s=3 s=3，1 1、2 2、3 3、4 4、75.0/,4.0,9.0s0748.011!1!11100skskskP)(70.1)1(!)()(021人PssPsnLssnnq)(89.19.070.1分钟qqLW57.01)3(210PPPnP2023-1-2668四、四、M/M/s/NM/M/s/N 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布；服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布；服务台数为服务台数为s s；系统的空间为有限，最多为系统的空间为有限，最多为N N2023-1-26691 1、稳定状态下，系统中有稳定状态下，系统中有n n个顾客的概率个顾客的概率nP,0,)(!1/!)(0100snPsnPsksPnnskk10snnPsP爱尔朗呼唤损失公式爱尔朗呼唤损失公式2023-1-26702 2、系统运行指标系统运行指标)1(ssPsL0qL1sW0qW2023-1-26712023-1-26722023-1-26732023-1-26742023-1-26752023-1-26762023-1-2677