运筹学基础及应用(第五版)_(第10章排队论)

1、2021-12-271运筹学运筹学OPERATIONS RESEARCH2021-12-2722021-12-2732021-12-2742021-12-2752021-12-2762021-12-2772021-12-2782021-12-2792021-12-27102021-12-27112021-12-27122021-12-27132021-12-27142021-12-27152021-12-27162021-12-27172021-12-27182021-12-27192021-12-27202021-12-27212021-12-2722f(t)=其中其中2021-12-272

2、3f(t)=2021-12-27242021-12-27252021-12-27262021-12-27272021-12-2728 2021-12-27292021-12-27302021-12-2731Little 公式公式ssWLqqWL/ssLW /qqLW 其中其中 是是单位时间内到达的平均顾客数；单位时间内到达的平均顾客数； 是是单位时间内可以服务完的平均顾客数。单位时间内可以服务完的平均顾客数。/1qsWW单位时间内到达的平均顾客数单位时间内到达的平均顾客数/qsLL0nnsnpL1)(snnqpsnL又又如果求得如果求得Pn ,则则 即可得到。即可得到。另外另外 1-P0 是系

3、统的忙期概率。是系统的忙期概率。 qsqSWWLL,2021-12-27322021-12-27332021-12-2734一、最简单流一、最简单流1、定义、定义;在时长为 t 的时间段内，有k个顾客到达的概率 服从poisson分布： t时段内平均到达顾客数； ,.2 , 1 , 0,!)()(kekttvtkk) (tvk, tE,tE单位时段内平均到达顾客数2021-12-27352、最简单流的性质、最简单流的性质（1）平稳性平稳性：在一定时间间隔内，有k个顾客到达的概率只与时长有关，与起始时刻无关；（2）无后效性无后效性：a,a+t时段内有k个顾客到达的概率与a时刻之前的客流无关；（3

4、）普通性：普通性：在足够小的时段内有2个或个以上顾客到来的概率为零。说明：1、最简单流的性质可以简化有关计算； 2、假设所研究的问题都是最简单流，或近似最简单流2021-12-2736二、最简单流的有关计算二、最简单流的有关计算1、单位时间内到达的顾客数2、 内没有顾客到达的概率3、 恰有一个顾客到达的概率4、若顾客到达 poisson分布，则相继到达间隔时间 负指数分布 tt , t ,tttttotetvt1)(1)(0ttvtv)(1)(012021-12-2737三、服务时间三、服务时间设服务时间设服务时间 负指数分布负指数分布1、单位时间内服务完毕，离去的顾客数2、 内没有顾客离去的

5、概率3、 恰有一个顾客离去的概率4、若干负指数分布的最小值也是负指数分说明： 服务机构中有s个并联服务台，各台 负指数分布，则整个服务时间 负指数分布。 ,ttt,tttst1t2021-12-2738第第38页页生灭过程2021-12-2739第第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 (p1

6、n1n3、t t时刻有时刻有n+1n+1个顾客，个顾客， 时刻系统中有时刻系统中有n n个顾客的个顾客的概率为概率为tt) t(ot) t (p1n1n4、t t时刻为时刻为n,n-1,n+1n,n-1,n+1个顾客之外的情况，个顾客之外的情况， 时刻时刻系统中有系统中有n n个顾客的概率为个顾客的概率为tt) t(o2021-12-2740第第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(

7、ot) t (p t1)t (p) tt (p110002021-12-2741第第41页页移项求极限，得差分微分方程移项求极限，得差分微分方程)()()()()()()()(110001111tPtPtPtPtPtPtPnnnnnnnnt时时,平稳状态平稳状态nntPtP)(lim0n11n0n0.11P01n01nnp.P2021-12-2742排队模型排队模型一、一、M/M/1/ M/M/1/ 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布； 服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布； 服务台数为服务台数为1 1； 系

8、统的空间为无限，允许永远排队。系统的空间为无限，允许永远排队。2021-12-27432021-12-27442021-12-27452021-12-27462021-12-27472021-12-2748/(/() )= =/() 2021-12-27492021-12-27502021-12-27512021-12-27522021-12-27532021-12-27542021-12-2755二、二、M/M/1/ NM/M/1/ N 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布； 服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数

9、分布； 服务台数为服务台数为1 1； 系统的空间为有限，最大容量系统的空间为有限，最大容量N N。2021-12-27561 1、 稳定状态下，系统中有稳定状态下，系统中有n n个顾客的概率个顾客的概率nP012N-1N。1110111,)(NNnnnppNnppppp2021-12-2757由由 及上述差分方程可解得：及上述差分方程可解得： 10NnnP) 1(/,1111110nNnNPP单位时间内的平均到达率单位时间内的平均到达率 )1 (NeP单位时间内的平均单位时间内的平均有效到达率有效到达率 系统中有系统中有N N个顾客时，到达率为个顾客时，到达率为0 0，只有在少于，只有在少于N

10、 N个顾客时个顾客时到达率才有意义。到达率才有意义。 还可验证还可验证 )1 (0Pe2021-12-27582 2、系统运行指标系统运行指标1N1NN1nns1) 1N(1nPL)1 () 1(01PLPnLSNnnq)P1 (LLW0SeSs1WWsq2021-12-2759例、例、单人理发店有六张椅子接待客人排队理发，当单人理发店有六张椅子接待客人排队理发，当6 6张椅张椅子坐满时，后来的顾客就不进店，随即离开，顾客平子坐满时，后来的顾客就不进店，随即离开，顾客平均到达率均到达率3 3人人/ /小时，理发平均需时小时，理发平均需时1515分钟，求：分钟，求： 1 1、求顾客一到达就能理发

11、的概率；、求顾客一到达就能理发的概率； 2 2、求需要等待的平均顾客数；、求需要等待的平均顾客数； 3 3、求有效到达率；、求有效到达率； 4 4、每个顾客的平均逗留时间；、每个顾客的平均逗留时间； 5 5、在可能到来的顾客中有百分之几不等待就离开？、在可能到来的顾客中有百分之几不等待就离开？2021-12-2760解、解、该问题中该问题中 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(071PLPnLSnnq

12、2021-12-2761小时）人/(89. 2)2778. 01 (4)1 (0Pe3 3、 4 4、5.5. 损失率损失率分钟小时43.80.732.892.11eSsLW%3.73/43/414/317177）（）（P2021-12-2762三、三、M/M/s/ M/M/s/ 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布； 服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布； 服务台数为服务台数为s s； 系统的空间为无限系统的空间为无限2021-12-27631 1、 稳定状态下，系统中有稳定状态下，系统中有n n个顾客的概率

13、个顾客的概率nP012nn+1n) 1( n。n-12nn+1ssn-1sn sn 2021-12-2764snpnppnsnpsppsppnnnnnn1,)() 1(,)(111101由由 及上述差分方程可解得：及上述差分方程可解得： 10nnPsnPsssnPnPskPnsnnnsksk,!1) 1(/,!111!1!10011002021-12-27652 2、系统运行指标系统运行指标/qsLL021)1 ( !)()(PssPsnLssnnqSsLW qqLW 2021-12-2766例、例、某售票点有三个窗口，顾客的到达服从某售票点有三个窗口，顾客的到达服从poissonpoisso

14、n 过过程，平均到达率程，平均到达率 ，服务时间服从负，服务时间服从负指数分布，平均服务率指数分布，平均服务率 。 现在假设顾客到达后排成一队，一次到空闲的窗口买现在假设顾客到达后排成一队，一次到空闲的窗口买票。分析下列各问题：票。分析下列各问题： 1 1、整个售票点空闲的概率；、整个售票点空闲的概率； 2 2、平均排队长；、平均排队长； 3 3、平均排队时间；、平均排队时间； 4 4、顾客到达后必须等待的概率。、顾客到达后必须等待的概率。分钟人/9 . 0分钟人/4 . 02021-12-2767解、解、该问题中该问题中 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(210PPPnP2021-12-2768四、四、M/M/s/ NM/M/s/ N 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布； 服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布； 服务台数为服务台数为s s； 系统的空间为有限，最多为系统的空间为有限，最多为N N2021-