运筹(第十章排队论)

1、2022-4-31运筹学运筹学OPERATIONS RESEARCH2022-4-322022-4-332022-4-342022-4-352022-4-362022-4-372022-4-382022-4-392022-4-3102022-4-3112022-4-3122022-4-3132022-4-3142022-4-3152022-4-3162022-4-3172022-4-3182022-4-3192022-4-3202022-4-3212022-4-322f(t)=其中其中2022-4-323f(t)=2022-4-3242022-4-3252022-4-3262022-4-327

2、2022-4-328 2022-4-3292022-4-3302022-4-331Little 公式公式ssWLqqWL/ssLW /qqLW 其中其中 是是单位时间内到达的平均顾客数；单位时间内到达的平均顾客数； 是是单位时间内可以服务完的平均顾客数。单位时间内可以服务完的平均顾客数。/1qsWW单位时间内到达的平均顾客数单位时间内到达的平均顾客数/qsLL0nnsnpL1)(snnqpsnL又又如果求得如果求得Pn ,则则 即可得到。即可得到。另外另外 1-P0 是系统的忙期概率。是系统的忙期概率。 qsqSWWLL,2022-4-3322022-4-3332022-4-334一、最简单流

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

4、单流，或近似最简单流2022-4-336二、最简单流的有关计算二、最简单流的有关计算1、单位时间内到达的顾客数2、 内没有顾客到达的概率3、 恰有一个顾客到达的概率4、若顾客到达数 poisson分布，则相继到达间隔时 间 负指数分布 tt , t ,tttttotetvt1)(1)(0ttvtv)(1)(012022-4-337三、服务时间三、服务时间设服务时间设服务时间 负指数分布负指数分布1、单位时间内服务完毕，离去的顾客数2、 内没有顾客离去的概率3、 恰有一个顾客离去的概率4、若干负指数分布的最小值也是负指数分说明： 服务机构中有s个并联服务台，各台 负指数分布，则整个服务时间 负指

5、数分布。 ,ttt,tttst1t2022-4-338第第38页页生灭过程2022-4-339第第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 (p1n1n

6、4、t t时刻为时刻为n,n-1,n+1n,n-1,n+1个顾客之外的情况，个顾客之外的情况， 时刻时刻系统中有系统中有n n个顾客的概率为个顾客的概率为tt) t(o2022-4-340第第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 (p110002022-4-341第第41页页移项求极限，得差分微分方程移项求极限，得差分微分方程)()()()(

7、)()()()(110001111tPtPtPtPtPtPtPnnnnnnnnt时时,平稳状态平稳状态nntPtP)(lim0n11n0n0.11P01n01nnp.P推导过程见书推导过程见书P2602022-4-342排队模型排队模型一、一、M/M/1/ M/M/1/ 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布； 服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布； 服务台数为服务台数为1 1； 系统的空间为无限，允许永远排队。系统的空间为无限，允许永远排队。2022-4-3432022-4-3442022-4-3452022-

8、4-3462022-4-3472022-4-348/(/() )= =/() 2022-4-3492022-4-3502022-4-3512022-4-3522022-4-3532022-4-3542022-4-355二、二、M/M/1/ NM/M/1/ N 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布； 服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布； 服务台数为服务台数为1 1； 系统的空间为有限，最大容量系统的空间为有限，最大容量N N。2022-4-3561 1、 稳定状态下，系统中有稳定状态下，系统中有n n个顾客的概

9、率个顾客的概率nP012N-1N。1110111,)(NNnnnppNnppppp2022-4-357由由 及上述差分方程可解得：及上述差分方程可解得： 10NnnP) 1(/,1111110nNnNPP单位时间内的平均到达率单位时间内的平均到达率 )1 (NeP单位时间内的平均单位时间内的平均有效到达率有效到达率 系统中有系统中有N N个顾客时，到达率为个顾客时，到达率为0 0，只有在少于，只有在少于N N个顾客时个顾客时到达率才有意义。到达率才有意义。 还可验证还可验证 )1 (0Pe2022-4-3582 2、系统运行指标系统运行指标1N1NN1nns1) 1N(1nPL)1 () 1(

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

11、5 5、在可能到来的顾客中有百分之几不等待就离开？、在可能到来的顾客中有百分之几不等待就离开？2022-4-360解、解、该问题中该问题中 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(071PLPnLSnnq2022-4-361小时）人/(89. 2)2778. 01 (4)1 (0Pe3 3、 4 4、5.5. 损失率损失率分钟小时43.80.732.892.11eSsLW%3.73/43/414/3171

12、77）（）（P2022-4-362三、三、M/M/s/ M/M/s/ 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布； 服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布； 服务台数为服务台数为s s； 系统的空间为无限系统的空间为无限2022-4-3631 1、 稳定状态下，系统中有稳定状态下，系统中有n n个顾客的概率个顾客的概率nP012nn+1n) 1( n。n-12nn+1ssn-1sn sn 2022-4-364snpnppnsnpsppsppnnnnnn1,)() 1(,)(111101由由 及上述差分方程可解得：及上述

13、差分方程可解得： 10nnPsnPsssnPnPskPnsnnnsksk,!1) 1(/,!111!1!10011002022-4-3652 2、系统运行指标系统运行指标/qsLL021)1 ( !)()(PssPsnLssnnqSsLW qqLW 2022-4-366例、例、某售票点有三个窗口，顾客的到达服从某售票点有三个窗口，顾客的到达服从poisson poisson 过过程，平均到达率程，平均到达率 ，服务时间服从负，服务时间服从负指数分布，平均服务率指数分布，平均服务率 。 现在假设顾客到达后排成一队，一次到空闲的窗口买现在假设顾客到达后排成一队，一次到空闲的窗口买票。分析下列各问题

14、：票。分析下列各问题： 1 1、整个售票点空闲的概率；、整个售票点空闲的概率； 2 2、平均排队长；、平均排队长； 3 3、平均排队时间；、平均排队时间； 4 4、顾客到达后必须等待的概率。、顾客到达后必须等待的概率。分钟人/9 . 0分钟人/4 . 02022-4-367解、解、该问题中该问题中 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(210PPPnP2022-4-368四、四、M/M/s/ NM/M/s/ N 模型模型 ：顾客相继到达时间服从参数为顾客相继到达时间服从参数为 的负指数分布；的负指数分布； 服务时间服从参数为服务时间服从参数为 的负指数分布；的负指数分布； 服务台数为服务台数为s s； 系统的空间为有限，最多为系统的空间为有限，