排队问题数学建模

第九届“新秀杯”校园数学建模竞赛摘要医院有一位医生值班，经长期观察，每小时平均有4个病人，医生每小时可诊断5人，病人的到来服从Poisson流，诊断时间服从负指数分布。根据题目所给信息，可以很明显看出本题是单服务台的排队模型，因此需要用到排队理论来求解这些问题。本题需要用到排队理论中最简单的M/M/1/∞/∞模型，通过对病人到来及诊断时间的统计研究，得出这些数量指标的统计规律。针对问题一，通过分析任意时刻t内到达的病人数为n的概率，使用数学期望的方法，，可以得出平均病人数及等待的平均病人数。由题目给出条件病人的到来服从参数为λ的泊松分布，诊断时间服从参数为μ负指数分布，可以得出病人的平均看病所需时间及病人平均排队等待时间。以及分析该医院的服务强度，可以粗略的分析该科室的工作状况。针对问题二，在问题一的条件基础下，要求99%的病人有座位。可以先假设出座位个数，由于每个时刻病人到来的个数是随机且独立，不可能同时到达两批病人，考虑到来病人的个数与座位之间的关系，考虑病人数不同时，有座位的概率不同。所以用独立事件概率的加法可以得出概率需要大于等于0.99，从而反推出所需座位数。针对问题三，分析问题可得，需要求出单位平均损失可以通过题目每小时病人到来数可以得出平均每天医院到来数。根据问题一结论，可以得出平均看病所花时间，从而求出每天的平均损失。针对问题四，只需要利用问题一，问题二，问题三的结论并改变医生每小时诊断时间，嵌套进来就能求解。关键字：排队理论M/M/1/∞/∞模型数学期望Poisson流负指数分布一、问题提出某单位医院的一个科室有一位医生值班，经长期观察，每小时平均有4个病人，医生每小时可诊断5人，病人的到来服从Poisson流，诊断时间服从负指数分布。(1)试分析该科室的工作状况：(2)如要求99%以上的病人有座，该科室至少设多少座位？(3)如果该单位每天24小时上班，病人因看病1小时而耽误工作单位要损失30元，这样单位平均损失多少元？(4)如果该科室提高看病速度，每小时平均可诊断6人，单位每天可减少损失多少？可减少多少座位？二、模型的准备根据题目所给信息，可以很明显看出本题是单服务台的排队模型，日常生活中存在大量有形和无形的排队或拥挤现象，如旅客购票排队，市内电话占线等现象。该模型显著特点是：服务设施是一个或者多个，需要被服务的人是无限制的，因此被服务者需要等待一段时间，因此会出现排队现象，被服务者的到来是完全随机的。因此排队论又称为随机服务系统理论，它是通过对服务对象到来及服务时间的统计研究，得出这些数量指标(等待时间、排队长度、忙期长短等)的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。排队系统又称服务系统。服务系统由服务机构和服务对象构成。排队系统包括三个组成部分：输入过程：考察的是顾客到达服务系统的规律。它可以用一定时间内顾客到达数或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。本题是病人随机到达且服从泊松分布。排队规则：分为等待制、损失制和混合制三种。当顾客到达时，所有服务机构都被占用，则顾客排队等候，即为等待制。在等待制中，为顾客进行服务的次序可以是先到先服务，或后到先服务，或是随机服务和有优先权服务。如果顾客来到后看到服务机构没有空闲立即离去，则为损失制。有些系统因留给顾客排队等待的空间有限，因此超过所能容纳人数的顾客必须离开系统，这种排队规则就是混合制。本题中不考虑优先制，而是先到先服务，且队伍可以无限长，不考虑容量问题。服务机构：可以是一个或多个服务台。多个服务台可以是平行排列的，也可以是串连排列的。服务时间一般也分成确定型和随机型两种。而随机型服务时间v则服从一定的随机分布。本题的服务台(医生)是有限且唯一的，诊断时间是随机的，且服从负指数分布。排队论主要研究排队系统运行的效率，估计服务质量。因此，研究排队问题，首先要确定判断系统运行优劣的基本量化指标，并求出这些指标的概率分布和数学特征。要研究的系统运行指标主要有：1、排队模型的表示X/Y/Z/A/B/CX—顾客相继到达的间隔时间的分布；Y—服务时间的分布；M—负指数分布、D—确定型、Ek—k阶爱尔兰分布；Z—服务台个数；A—系统容量限制(默认为∞)；B—顾客源数目(默认为∞)；C—服务规则(默认为先到先服务FCFS)。2、排队系统的衡量指标队长Ls—系统中的顾客总数；排队长Lq—队列中的顾客数；逗留时间Ws—顾客在系统中的停留时间；等待时间Wq—顾客在队列中的等待时间；忙期—服务机构两次空闲的时间间隔；服务强度ρ；稳态—系统运行充分长时间后，初始状态的影响基本消失，系统状态不再随时间变化。3、到达间隔时间与服务时间的分布泊松分布；负指数分布；爱尔兰分布；Poisson分布，是一种统计与概率学里常见到的离散概率分布，由法国数学家西莫恩·德尼·泊松在1838年时发表。泊松分布的参数是单位时间(或单位面积)内随机事件的平均发生率。泊松分布适合于描述单位时间内随机事件发生的次数。泊松分布的期望和方差均为λ。负指数分布又称指数分布。泊松事件流的等待时间（相继两次出现之间的间隔）服从指数分布。指数函数的一个重要特征是无记忆性。这表示如果一个随机变量呈指数分布，当s,t0时有P(Tt+s|Tt)=P(Ts)。即，如果T是某一元件的寿命，已知元件使用了t小时，它总共使用至少s+t小时的条件概率，与从开始使用时算起它使用至少s小时的概率相等。如果指数分布的参数为λ，则指数分布的期望为1/λ。根据以上资料，解决本题的科室的工作状态问题，只需要运用排队论中最简单的单服务台，即M/M/1/∞/∞模型即可。下面通过对该问题进行排队论模型嵌套进行求解。三、模型假设1.首先确定医生的接待能力、病人的客源为无限大，且排除医生，病人的心理因素及插队等意外情况的发生。2.排队只排一排，根据先到先得的原则，且每次医生只看一个病人，且每个病人肯定能得出诊断。3.假设每段时间到来的病人数基本稳定，不会出现剧增和很长一段时间无人看病的问题。四、符号说明符号意义n任意时刻t内到达的病人数（个）Ls平均病人数（个）Lq等待的平均病人数（个）Ws病人的平均看病（包括等待时间）时间(h)Wq病人平均排队等待时间(h)λ单位时间内到达病人的平均数（个/h）μ单位时间内能诊断完的病人的平均数（个/h）m座位数（个）T看病耽误的时间(h)Q损失的钱(元)ρ服务强度五、模型建立与解决：问题1模型建立与解决问题1模型建立：已知病人的到来服从Poisson流，即服从参数为λ的泊松分布，其中λ表示单位时间内到达病人的平均数。医生诊断时间服从参数为μ的负指数分布，其中μ表示单位时间内能诊断完的病人的平均数。1)设任意时刻t内到达的病人数为n的概率为Pn(t)，病人的到来服从泊松分布，因此单位时间内病人的到达数服从X~P(λ)，则时间间隔△t为内病人到来的数目为G~P(λ△t)。则△t内1个病人到达的概率为P(G=1)=λ△t*e-λ△t=λ△t+o△t，反之没有病人到达的概率为P(G=0)=1-λ△t*e-λ△t=1-λ△t+o△t2)由于医生的诊断时间Y~E(μ)，故病人被诊断时，1个病人被诊断完的概率为P{Y≤Δt}=1-e-μ△t=μΔt+o(Δt)，没有被诊断完的概率为1-μΔt+o(Δt)。3)在t+△t时刻考虑n个病人到来的概率Pn(t+△t)，△t足够小的情况下，有以下4种情况：①t时刻系统中有n个病人到来，没有病人到来且没有病人诊断完毕，其概率为：[1-λ△t+o(△t)][1-μ△t+o(△t)]=(1-λ△t-μ△t)+o(△t)；②t时刻系统中有n+1个病人到来，没有病人到来且有1个病人诊断完毕，其概率为：[1-λ△t+o(△t)][μ△t+o(△t)]=μ△t+o(△t)；③t时刻系统中有n-1个病人到来，有1个病人到来且没有病人诊断完毕，其概率为：[λ△t+o(△t)][1-μ△t+o(△t)]=λ△t+o(△t)；④其他状态的概率为o(△t)。由于四种情况相互独立且不可能同时发生，所以得到系统中有n个病人到来的概率Pn(t+△t)满足：Pn(t+△t)=Pn(t)(1-λ△t-μ△t)+Pn+1(t)μ△t+Pn-1(t)λ△t+o(△t)移项整理，两边同除以△t，得：Pn(t+△t)+Pn(t)△t=λPn-1(t)+μPn+1(t)-(λ+μ)Pn(t)+o△t△t令△t→0，得:dPn(t)dt=λPn-1(t)+μPn+1(t)-(λ+μ)Pn(t)n=1，2…当n=0时，因为:P0(t+△t)=P0(t)(1-λ△t)+P1(t)(1-λ△t)μ△t+o(△t)所以有:dPn(t)dt=-λP0(t)+μP1(t)对于稳态情形，与t无关，其导数为零。因此，得到:{λP𝑛−1+μP𝑛+1−(λ+μ)P𝑛=0，𝑛1−λP0+μP1=0问题1模型求解：{λP𝑛−1+μP𝑛+1−(λ+μ)P𝑛=0，𝑛1−λP0+μP1=0这是关于Pn的差分方程，也反映出了系统状态的转移关系，即每一状态都是平衡的，求解得:P1=(λ/μ)P0，递推可得Pn=(λ/μ)nP0(n≥1)由概率的性质知∑𝑃𝑛∞𝑛=0=1，将上式代入λ/μ1时可得到P0=1-λ/μ，Pn=(1-λ/μ)(λ/μ)n因为病人到达规律服从参数为λ的泊松分布，诊断时间服从参数为μ的负指数分布，其期望值就分别为λ，1/μ。所以λ表示单位时间内平均到达的病人数，μ表示单位时间内能诊断完的病人数。如果令ρ=λ/μ，这时ρ就表示相同时间内病人到达的平均数与能被诊断的平均数之比，它是刻画诊断效率和医院利用程度的重要标志，称ρ为服务强度。上面在ρ1的条件下得到了稳定状态下的概率Pn，n=0，1，2，…其实，如果ρ1，可以证明排队长度将是无限增加的，即使ρ=1的情况下，P0(t)也是随时间而变化的，系统达不到稳定状态.因此，这里只讨论ρ1时情况，从上面的推导知：Pn=(1-ρ)ρnn=1,2…则服务系统的运行指标为：(1)队长（平均病人数）：由于系统的状态为n时即系统中有n个病人，由期望的定义得:𝐿𝑠=∑𝑛𝑃𝑛=∞𝑛=0∑𝑛(1−ρ)∞𝑛=1ρ𝑛=ρ(1−ρ)=λ/(μ−λ)(2)排队长：（等待的平均病人数）𝐿𝑞=∑(𝑛−1)𝑃𝑛=∑(𝑛−1)𝜌𝑛(1−𝜌)=𝜌2∞𝑛=1∞𝑛=1/(1−𝜌)=ρλ/(μ-λ)可以证明，病人在系统中看病时间服从参数为μ-的负指数分布。因此，有(3)系统中病人的平均看病时间：𝑊𝑠=1/(μ−λ)(4)系统中病人的平均等待时间：𝑊𝑞=𝑊𝑠−1/μ=ρ/(μ−λ)题目中每小时平均有4个病人，医生每小时可诊断5人，病人的到来服从Poisson流，诊断时间服从负指数分布。可以得到λ=4，μ=5，ρ=λμ=45医院平均病人数：𝐿𝑠=λμ−λ=45−4=4(人)医院等待的平均病人数：𝐿𝑞=𝜌21−𝜌=(45)21−(45)=3.2(人)病人的平均看病（包括等待时间）时间：𝑊𝑠=1μ−λ=1h病人平均排队等待时间：𝑊𝑞=ρμ−λ=0.8h医院当中没有病人的概率为：1-ρ=0.2病人到来不需要等待的概率即是医院中没有病人的概率问题一结论：由上结果可得，病人到来不需要等待的概率为0.2，医院平均病人数为4人，医院等待的平均病人数为3.2人，病人的平均看病（包括等待时间）时间为1h，病人平均排队等待时间为0.8h。问题2模型建立与解决问题2模型建立：要求99%以上的病人有座，设现在医院内有m个座位，则可以设P=（医院总人数=m）=0.99考虑单位时间平均人数为4人，则m=4考虑病人数为0人时，人数=m,都有座位,发生这种情况下的概率为P0考虑病人数为1人时，人数=m,都有座位,发生这种情况下的概率为P1考虑病人数为2人时，人数=m,都有座位,发生这种情况下的概率为P2...考虑病