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