新排队论——录像用.pdf

西安电子科技大学西安电子科技大学 排队论模型排队论模型 西安电子科技大学数学与统计学院西安电子科技大学数学与统计学院 李李 伟伟西安电子科技大学西安电子科技大学排队论排队论-随机服务系统随机服务系统商店、超市等收款处排队付款商店、超市等收款处排队付款车站、民航等售票处依次购买车船票车站、民航等售票处依次购买车船票各种生产系统、存储系统、运输系统等 一系列等待现象比比皆是各种生产系统、存储系统、运输系统等 一系列等待现象比比皆是西安电子科技大学西安电子科技大学排队论模型排队论模型一、排队论基本概念二、排队模型的数量指标三、排队系统中常见的分布四、排队模型的记号方案一、排队论基本概念二、排队模型的数量指标三、排队系统中常见的分布四、排队模型的记号方案五、几种排队论模型五、几种排队论模型西安电子科技大学西安电子科技大学 一、排队论基本组成一、排队论基本组成实际上排队的过程可由下面几个图理解实际上排队的过程可由下面几个图理解:西安电子科技大学西安电子科技大学 西安电子科技大学西安电子科技大学西安电子科技大学西安电子科技大学基本组成基本组成排队系统的三个基本组成部分排队系统的三个基本组成部分输入过程(顾客到达规律)输入过程(顾客到达规律)排队规则(顾客按照一定规则排队等待服务)排队规则(顾客按照一定规则排队等待服务)服务机构(服务机构的设置，服务台的数量，服务的方式，服务时间分布等)服务机构服务机构的设置，服务台的数量，服务的方式，服务时间分布等)输入来源输入来源队 列队 列服务机构服务机构排队系统排队系统顾客顾客服务完离开服务完离开西安电子科技大学西安电子科技大学基本组成 输入过程基本组成 输入过程顾客总体（顾客源）数量顾客总体（顾客源）数量有限无限有限无限顾客到来方式可能是一个一个也可能是成批顾客到来方式可能是一个一个也可能是成批顾客到达间隔时间:到下一个顾客到达的时间顾客到达间隔时间:到下一个顾客到达的时间一般是服从某一概率分布（例如：指数分布）一般是服从某一概率分布（例如：指数分布）顾客的行为假定为:顾客的行为假定为:在未服务之前不会离开；在未服务之前不会离开；当看到队列很长的时候离开；当看到队列很长的时候离开；从一个队列移到另一个队列。从一个队列移到另一个队列。西安电子科技大学西安电子科技大学基本组成排队规则基本组成排队规则队列容量队列容量有限/无限有限/无限排队规则排队规则先来先服务(FCFS)；后来先服务(LCFS)；随机服务(RSS)；有优先权的服务(PS)；排队模型中也用到服务中的“一般规则（GD）”它先来先服务(FCFS)；后来先服务(LCFS)；随机服务(RSS)；有优先权的服务(PS)；排队模型中也用到服务中的“一般规则（GD）”它包括前三种排队规则。包括前三种排队规则。西安电子科技大学西安电子科技大学基本组成服务规则基本组成服务规则服务机构可以有一个，也可以有多个；服务机构可以有一个，也可以有多个；对于多个服务台可以是并列、串列、混合排列；对于多个服务台可以是并列、串列、混合排列；服务方式可以是一个或成批；服务方式可以是一个或成批；西安电子科技大学西安电子科技大学二、排队模型的数量指标二、排队模型的数量指标平均队长：排队系统中顾客数的平均值，平均队长：排队系统中顾客数的平均值，sL平均队列长：排队系统中等待服务的顾客数平均值，平均队列长：排队系统中等待服务的顾客数平均值，qL平均逗留时间：一个顾客在系统中停留的时间平均值，平均等待时间：一个顾客在系统中排队等待的时间平 均值，平均逗留时间：一个顾客在系统中停留的时间平均值，平均等待时间：一个顾客在系统中排队等待的时间平 均值，sWqW西安电子科技大学西安电子科技大学二、排队模型的数量指标二、排队模型的数量指标平均到达率：单位时间内到达顾客的平均数平均到达率：单位时间内到达顾客的平均数平均服务率：单位时间内被服务顾客的平均数服务强度：单位时间内的服务强度平均服务率：单位时间内被服务顾客的平均数服务强度：单位时间内的服务强度时刻t系统中顾客数为n的概率,若时刻t系统中顾客数为n的概率,若lim()nntP tP称为稳态解（统计平衡状态解）称为稳态解（统计平衡状态解）西安电子科技大学西安电子科技大学三、排队系统中常见的分布三、排队系统中常见的分布1.泊松分布1.泊松分布211212()211221()0,)(,),)()(,)()()!.nnttnN ttP t tt tnttP t tP N tN tnen设表示在时间内到达的顾客数，表示在时间段内有 个顾客到达的概率，若满足以下三个条件，称顾客的到达形成参数为 的泊松流,:(1)();(2)1-();(3)();t ttttttt 在 内有有一个顾客到达的概率没有一个顾客到达的概率多于一个顾客到达的概率西安电子科技大学西安电子科技大学2.负指数分布2.负指数分布三、排队系统中常见的分布三、排队系统中常见的分布当顾客流为泊松流时，两个顾客相继到达的时间间隔服从负指数分布；同理，系统中一个顾客的服务时间 也服从负指数分布期望（均值）分布函数期望（均值）分布函数TV,:(4)();(5)1-();(6)();t ttttttt 若顾客流为泊松分布，服务时间服从于参数为 的负指数分布，则在 内有有一个顾客被服务完的概率没有一个顾客被服务完的概率多于一个顾客被服务完的概率12,1121,:()()(1)!11(),()kkkikuktkkiikv vvkTvk uktftekE TE vTkkD阶记 个顾客到达系统的时间间隔分别为独立同服从于参数为的负爱尔指数分布，则朗服且分从于布三、排队系统中常见的分布三、排队系统中常见的分布3.爱尔郎分布3.爱尔郎分布西安电子科技大学西安电子科技大学四、记号方案四、记号方案(Kendall 记号)一般形式：(Kendall 记号)一般形式：X/Y/Z/A/B/CX/Y/Z/A/B/CX顾客到达时间间隔分布/Y服务时间分布/Z服务台数目/A排队系统允许的最大顾客容量/B顾客总体数量/C排队规则X顾客到达时间间隔分布/Y服务时间分布/Z服务台数目/A排队系统允许的最大顾客容量/B顾客总体数量/C排队规则M/M/1/FCFS M/M/1/FCFS ServerQueueArrival西安电子科技大学西安电子科技大学X表示相继X表示相继到达时间间隔到达时间间隔的分布，Y表示的分布，Y表示服务时间服务时间的分布，X,Y取值有以下几种情况:M表示泊松过程或负指数分布；D表示确定型分布；的分布，X,Y取值有以下几种情况:M表示泊松过程或负指数分布；D表示确定型分布；E Ek k表示k阶爱尔朗分布；G表示一般服务时间分布;GI表示一般相互独立的时间间隔分布.表示k阶爱尔朗分布；G表示一般服务时间分布;GI表示一般相互独立的时间间隔分布.四、记号方案四、记号方案西安电子科技大学西安电子科技大学Z表示服务台(员)个数：“1”则表示单个服务台，“c”。(c1)表示多个服务台。A表示系统中容量限额，或称等待空间容量；Z表示服务台(员)个数：“1”则表示单个服务台，“c”。(c1)表示多个服务台。A表示系统中容量限额，或称等待空间容量；B表示顾客源数目，分有限与无限两种，顾客源无限，此时一般也可省略不写。C表示服务规则B表示顾客源数目，分有限与无限两种，顾客源无限，此时一般也可省略不写。C表示服务规则四、记号方案四、记号方案西安电子科技大学西安电子科技大学C C表示服务规则，常用下列符号：(1)FCFS：表示先到先服务的排队规则；(2)LCFS：表示后到先服务的排队规则；表示服务规则，常用下列符号：(1)FCFS：表示先到先服务的排队规则；(2)LCFS：表示后到先服务的排队规则；(3)PR：表示优先权服务的排队规则。(4)随机服务省略时代表的是FCFS（先到先服务）。(3)PR：表示优先权服务的排队规则。(4)随机服务省略时代表的是FCFS（先到先服务）。四记号方案四、记号方案西安电子科技大学西安电子科技大学 五、排队论模型五、排队论模型单服务台模型分为3种设系统输入过程服从泊松流,服务时间服从负指数分布,单服务台:单服务台模型分为3种设系统输入过程服从泊松流,服务时间服从负指数分布,单服务台:(1)标准型:M/M/1/（M/M/1）(2)系统容量有限型:M/M/1/N/(3)顾客源有限型:M/M/1/m(1)标准型:M/M/1/（M/M/1）(2)系统容量有限型:M/M/1/N/(3)顾客源有限型:M/M/1/m 西安电子科技大学西安电子科技大学(1)标准型:M/M/1(1)标准型:M/M/1 标准型表示顾客源为无限的，顾客的到达相互独立，到达规律服从参数为的泊松分布：单标准型表示顾客源为无限的，顾客的到达相互独立，到达规律服从参数为的泊松分布：单服务台、队长无限、先到先服务；各顾客的服务时间相互独立，且同服从于参数为的负指数分布。服务台、队长无限、先到先服务；各顾客的服务时间相互独立，且同服从于参数为的负指数分布。西安电子科技大学西安电子科技大学情况时刻t的顾客数在区间(t,t+t)到达 离去时刻(t,t+t)的顾客数Pn(t+t)An0 0nPn(t)(1-t)(1-u t)Bn+1 0 1nPn+1(t)（1-t）(u t)Cn-11 0nPn-1(t)（t）(1-u t)Dn1 1nPn(t)(t)(u t)现在考虑在t+t时刻系统中有n个顾客（即状态为n）的概率Pn(t+t)，如下表：现在考虑在t+t时刻系统中有n个顾客（即状态为n）的概率Pn(t+t)，如下表：西安电子科技大学西安电子科技大学 1111001()()(1)()()(),0,()()()()()()0()()()0nnnnnnnnnP ttP tttPttPtttttdP tPtPtP tdtdP tnP tP tdtdP ttdt 于是我们得到两端移项除以当时当时，类似地可有当时，01110()0,1nnnPPPPPn其稳态概率方程为西安电子科技大学西安电子科技大学 000001,:1111,(1),1nnnnnnPPPPPnn 令即平均到达率与平均服务率之比由概率性质即所以这就是系统状态为 的概率。nn0()P由递推关系P西安电子科技大学西安电子科技大学平均队长（包含正在被服务的那个顾客）：平均队长（包含正在被服务的那个顾客）：平均队列长（等待的平均顾客数）：平均队列长（等待的平均顾客数）：西安电子科技大学西安电子科技大学111.kkk若一个顾客到达服务系统，系统内已有 个顾客，则该顾客需要等候平均时间才能轮到被服务，他本人的平均服务时间为，所以他在系统内花费时间的平均值为0001111 1skkkkkkkWpkpp西安电子科技大学西安电子科技大学顾客逗留时间服从顾客逗留时间服从 的指数分布的指数分布平均逗留时间（即顾客在系统中的时间期望）平均逗留时间（即顾客在系统中的时间期望）平均等待时间（即顾客等待时间的期望）平均等待时间（即顾客等待时间的期望）,1,ssqqsqsqLWLWLLWW运行指标之间的关系运行指标之间的关系这些关系式称为这些关系式称为Little公式公式.01110()0,1nnnPPPPPn标准型：M/M/1西安电子科技大学西安电子科技大学10111()(11),nnnNNPPPPPnNPP(2)M/M/1/N/(2)M/M/1/N/N西安电子科技大学西安电子科技大学 001111,1,11,111,.NnnNnnNPPPnN注意到由递推关系得注:若说明达到率和服务率相等 不会出现排队现象(2)M/M/1/N/(2)M/M/1/N/西安电子科技大学西安电子科技大学 110011(1)(1),111(2)(1)(1);NNsnNnNqnsnNLnPLnPLP队长：队列长：10110(1)1:1111:(1)(1)1(4):.(1)eNNNeNNqssseNqqqseNPPLLLWPPLLWWP 有效服务强度(3)平均逗留时间有平均等待时间效到达率:,ssqqLWLW西安电子科技大学西安电子科技大学 顾客源只有m个顾客,但每个顾客来到并接受服务后,仍然回到顾客总体,即可以再次到来,所以实际上系统中顾客永远不会超过m个,即与模型M/M/1/m/m意义相同。顾客源只有m个顾客,但每个顾客来到并接受服务后,仍然回到顾客总体,即可以再次到来,所以实际上系统中顾客永远不会超过m个,即与模型M/M/1/m/m意义相同。(3)M/M/1/(3)M/M/1/mn()esmL(m-n)西安电子科技大学西安电子科技大学101110000(1)(),(11)1,:1,!()()!(),1!nnnmmmnnmiinnPm PPmnPmnPnmPPPPmmimPPnmmn注意到由递推关系可得系统状态概率西安电子科技大学西安电子科技大学 000010:(1),()(1)(1)(1).1.(1)1,msnnqnsnsqsuLnPmPPLnPmLPmWPWW系统运行指标为西安电子科技大学西安电子科技大学多服务台的排队模型多服务台的排队模型多服务台主要分为三种情况:(1)标准型：多服务台主要分为三种情况:(1)标准型：M/M/cM/M/c(2)系统容量有限型：(2)系统容量有限型：M/M/c/N/M/M/c/N/(3)顾客源为有限的：(3)顾客源为有限的：M/M/c/mM/M/c/m西安电子科技大学西安电子科技大学,()(),1,.nnccncc顾客流为泊松流 平均到达率为各个服务台的平均服务率是则整个服务机构的平均服务率是或令称为系统服务强度当时 会出现排队现象(4)多服务台:M/M/c(4)多服务台:M/M/c西安电子科技大学西安电子科技大学nc(4)多服务台:M/M/c(4)多服务台:M/M/c2 nc2n-1ncn-1nc西安电子科技大学西安电子科技大学 10111111000(1)()(1)()()111()(),!11(),!11(),.!nnnnnnckcknnnn cPPnPPnPncc PPcP nckcPncnPPncc c 0系统稳态概率方程为:解得P当当西安电子科技大学西安电子科技大学 0021110202()()()!(1)()1,!(1)().!(1)qck cqnk ckn ckkcscqqLkcLnc PkPcpPPc cccpknc WPcLcpWPc ss系统运行指标:LL其中c=西安电子科技大学西安电子科技大学 cc(5)多服务台:M/M/c/N/(5)多服务台:M/M/c/N/2(),-,.,:0;,.N NccN cnncnnccc系统最大容量为当系统客满时有 个接受服务在排队 再有顾客来被拒绝服务当系统的状态为 时每个服务台的服务率为则系统的总服务率 当时为当时为令为系统服务强度西安电子科技大学西安电子科技大学 10111110,:(1)()(1)()()1,1nnnnnnNNNnnPPnPPnPncc PPnP cnNPc PPc类似的 可以得到系统状态概率方程其中且西安电子科技大学西安电子科技大学 11001000:1()(),1!11()(1),1!1(),0!,!ccNckkcckknncncckcPccNckccpPncnPcP cnNc 由递推关系可得系统状态概率为当西安电子科技大学西安电子科技大学 01:,()()1(1)!(1)21,()1)1sqcNN cN cqNn csqqqNNcPLLcLnc PPcWWLWP 系统运行指标sqLittleLL：公式=e西安电子科技大学西安电子科技大学(6)M/M/c/(6)M/M/c/mncm.,:0;,.nncnnccc顾客流为泊松流，顾客源有限为当系统的状态为 时每个服务台的服务率为则系统的总服务率 当时为当时为令为系统服务强度西安电子科技大学西安电子科技大学 1011111:(1)(1)(),(1)(1)(),()nnnnnnmmPm PnPmnPmnnPncc PmcPmccPcnmPc P系统状态概率平衡方程为西安电子科技大学西安电子科技大学 100000111()(),!()!()!(),0,()!(),()!ccckkkknnnn cccmPmk mkmcmkmcmPncmn nPmPcnmmn c c由递推关系可得系统状态概率当当西安电子科技大学西安电子科技大学 11,(),(),().mnnmnn csqccenPnc PWWmm sqqsssqs系统运行指标为:LLLL有效到达率为L且LLL西安电子科技大学西安电子科技大学例题例题（病人候诊问题）某单位医院的一个科室有一位医生值班，经长期观察，每小时平均有4个病人，医生每小时平均可诊断5人，病人的到来服从Poisson流，诊病时间服从负指数分布，(1)试分析该科室的工作状况，(2)如要求99%以上的病人有座（病人候诊问题）某单位医院的一个科室有一位医生值班，经长期观察，每小时平均有4个病人，医生每小时平均可诊断5人，病人的到来服从Poisson流，诊病时间服从负指数分布，(1)试分析该科室的工作状况，(2)如要求99%以上的病人有座，该科室至少设多少座位?(3)如果该单位每天24小时上班，病人因看病1小时而耽误工作单位要损失30元，这样单位平均损失多少元?(4)如果该科室提高，该科室至少设多少座位?(3)如果该单位每天24小时上班，病人因看病1小时而耽误工作单位要损失30元，这样单位平均损失多少元?(4)如果该科室提高看病速度，每小时平均可诊6人，单位每天可减少损看病速度，每小时平均可诊6人，单位每天可减少损失多少?可减少多少座位?失多少?可减少多少座位?西安电子科技大学西安电子科技大学 解：解：由题意可知，则该科室平均有病人数 (人)该科室平均等待的病人数 （人)由题意可知，则该科室平均有病人数 (人)该科室平均等待的病人数 （人)看一次病平均所需的时间 （小时)看一次病平均所需的等待时间 (小时)看一次病平均所需的时间 （小时)看一次病平均所需的等待时间 (小时)8.054,5,4,2,1,08.02.0)1(npnnn2.3)1(2qL1ssWL(1)4sL0.8qqWL西安电子科技大学西安电子科技大学 为了满足99%以上的病人有座，设科室应设m个座位，即：P医务室病人数m0.99 为了满足99%以上的病人有座，设科室应设m个座位，即：P医务室病人数m0.99 故该设20个座位。该单位24小时上班，平均每天有42496人看病，看病所占的总时间为19696小时，所以因看 故该设20个座位。该单位24小时上班，平均每天有42496人看病，看病所占的总时间为19696小时，所以因看病平均每天损失30962880(元)。病平均每天损失30962880(元)。mnmnmnnp01099.01)1(201)ln01.0(lnm西安电子科技大学西安电子科技大学 若医生诊病速度提高到每小时6人，即6、23，类似于上面的计算，有以下结果：(小时)，（小时)若医生诊病速度提高到每小时6人，即6、23，类似于上面的计算，有以下结果：(小时)，（小时)这样单位每天损失：300.5961440（元），比原来减少1440元，此时只需座位：这样单位每天损失：300.5961440（元），比原来减少1440元，此时只需座位：即11个座位，比原来减少9个座位即11个座位，比原来减少9个座位。2sL 人0.51 3sqWW111)32ln01.0(lnm4 3qL 人西安电子科技大学西安电子科技大学有关参考书籍有关参考书籍韩中庚，数学建模方法及其应用，第十四章韩中庚，数学建模方法及其应用，第十四章陈东彦，陈东彦，数学建模，第十三章数学建模，第十三章张卓奎，随机过程，第六章张卓奎，随机过程，第六章西安电子科技大学西安电子科技大学作业作业请用排队论方法解决2009年大学生数模竞赛B题“眼科病床安排”的第五问。请用排队论方法解决2009年大学生数模竞赛B题“眼科病床安排”的第五问。要求：可参考网络上提供的前四问结果，第五问独立完成；以队为单位，三位队员合作完成；有合理的假设、数学符号、模型、求解、结论分析；写成数模论文形式。要求：可参考网络上提供的前四问结果，第五问独立完成；以队为单位，三位队员合作完成；有合理的假设、数学符号、模型、求解、结论分析；写成数模论文形式。