下载文档原格式
数学建模排队论
排队论是一种数学理论，它研究的是人们排队等待服务或交通等系统的行为模式。
在排队论中，数学建模被广泛应用于分析和优化这些系统的性能和效率。
排队系统的基本构成包括到达过程、服务过程和队列规则。
到达过程指的是顾客或流量进入系统的过程，它可以用概率分布来描述。
服务过程指的是系统为每个顾客提供服务的时间，同样也可以用概率分布来描述。
队列规则则规定了顾客在等待队列中的顺序以及他们被服务的顺序。
在排队系统中，我们通常关注两个主要的性能指标：平均等待时间和平均队列长度。
平均等待时间指的是顾客在进入系统后需要等待多长时间才能接受服务的时间平均值，而平均队列长度则指的是在某个时间点等待服务的顾客数量的平均值。
为了分析和优化排队系统的性能，我们可以使用数学模型进行建模。
其中最常用的模型包括M/M/1模型、M/M/c模型、M/G/1模型等。
这些模型分别描述了不同的到达过程、服务过程和队列规则，并且可以计算出各种性能指标。
例如，M/M/1模型表示到达过程和服务过程都是泊松分布，并且只有一个服务窗口。
在这种情况下，我们可以使用该模型计算出平均等待时间和平均队列长度，并比较不同服务率下的性能指标。
M/M/c模型则表示到达过程和服务过程都是泊松分布，但是有c个服
务窗口。
在这种情况下，我们可以研究如何合理分配服务窗口的数量以优化系统的性能。
数学建模排队论是一种非常有用的工具，它可以用来分析和优化人们排队等待服务或交通等系统的行为模式。
通过建立数学模型，我们可以更好地理解这些系统的性能和效率，从而为实际应用提供指导。
数学建模排队论模型排队论模型是一种数学建模方法，用于研究排队系统中的等待时间、服务效率和资源利用率等问题。
排队论模型可以应用于各种领域，如交通运输、医疗服务、银行业务等。
本文将介绍排队论模型的基本概念和应用。
一、排队论模型的基本概念排队论模型的基本概念包括：顾客到达率、服务率、队列长度、等待时间、系统利用率等。
顾客到达率是指单位时间内到达系统的顾客数量，通常用λ表示。
服务率是指单位时间内一个服务员能够完成服务的顾客数量，通常用μ表示。
队列长度是指系统中正在等待服务的顾客数量。
等待时间是指顾客在队列中等待服务的时间。
系统利用率是指系统中所有服务员的利用率之和。
排队论模型可以分为单队列模型和多队列模型。
单队列模型是指系统中只有一个队列，多个服务员依次为顾客提供服务。
多队列模型是指系统中有多个队列，每个队列对应一个服务员，顾客可以选择任意一个队列等待服务。
二、排队论模型的应用排队论模型可以应用于各种领域，如交通运输、医疗服务、银行业务等。
下面以银行业务为例，介绍排队论模型的应用。
在银行业务中，顾客到达率和服务率是两个重要的参数。
顾客到达率受到银行营业时间、银行位置、顾客数量等因素的影响。
服务率受到银行服务员数量、服务质量、服务时间等因素的影响。
为了提高银行的服务效率和资源利用率，可以采用排队论模型进行优化。
首先需要确定银行的顾客到达率和服务率，然后根据排队论模型计算出等待时间、队列长度、系统利用率等指标。
根据这些指标，可以制定相应的服务策略，如增加服务员数量、优化服务流程、提高服务质量等。
例如，如果银行的顾客到达率较高，服务员数量较少，导致顾客等待时间较长，可以考虑增加服务员数量或优化服务流程，以缩短顾客等待时间。
如果银行的服务率较低，导致服务员利用率较低，可以考虑提高服务质量或增加服务时间，以提高服务员利用率。
三、排队论模型的局限性排队论模型虽然可以应用于各种领域，但也存在一些局限性。
首先，排队论模型假设顾客到达率和服务率是稳定的，但实际情况中这些参数可能会发生变化。
第九届“新秀杯”校园数学建模竞赛摘要医院有一位医生值班，经长期观察，每小时平均有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人，单位每天可减少损失多少？可减少多少座位？二、模型的准备根据题目所给信息，可以很明显看出本题是单服务台的排队模型，日常生活中存在大量有形和无形的排队或拥挤现象，如旅客购票排队，市内电话占线等现象。
（- 数学建模）排队论模型第五讲排队论模型【修理工录用问题】工厂平均每天有一台机器发生故障而需要修理，机器的故障数服从泊松分布。
修理一台机器平均花费20元。
现有技术水平不同的修理工人A 和B，A种修理工平均每天能修理1.2台机器，每天工资3元；B种修理工平均每天能修理1.5台机器，每天工资5元，两种修理工修理机器的时间为负指数分布。
问工厂录用哪种工人较合算？本讲主要内容1. 排队论的基本概念2. 单服务台的排队模型3. 多服务台的排队模型4. 排队系统的最优化问题5. 数学建模实例：校园网的设计和调节收费问题5.1 排队论的基本概念5.1.1 什么是排队系统排队论也称随机服务系统理论，它是20世纪初由丹麦数学家Erlang应用数学方法在研究电话话务理论过程中而发展起来的一门学科，在实际中有广泛的应用。
它涉及的是建立一些数学模型，藉以对随机发生的需求提供服务的系统预测其行为。
现实世界中排队的现象比比皆是，如到商店购货、轮船进港、病人就诊、机器等待修理等等。
排队的内容虽然不同，但有如下共同特征：（1）有请求服务的人或物，如候诊的病人、请求着陆的飞机等，我们将此称为“顾客”。
（2）有为顾客提供服务的人或物，如医生、飞机跑道等，我们称此为“服务员”。
由顾客和服务员就组成服务系统。
（3）顾客随机地一个一个（或者一批一批）来到服务系统，每位顾客需要服务的时间不一定是确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时候服务员又空闲无事。
为了叙述一个给定的排队系统，必须规定系统的下列组成部分：1.输入过程即顾客来到服务台的概率分布。
排队问题首先要根据原始资料，由顾客到达的规律、作出经验分布，然后按照统计学的方法（如卡方检验法）确定服从哪种理论分布，并估计它的参数值。
我们主要讨论顾客来到服务台的概率分布服从泊松分布，且顾客的达到是相互独立的、平稳的输入过程。
所谓“平稳”是指分布的期望值和方差参数都不受时间的影响。
（- 数学建模）排队论模型第五讲排队论模型【修理工录用问题】工厂平均每天有一台机器发生故障而需要修理，机器的故障数服从泊松分布。
修理一台机器平均花费20元。
现有技术水平不同的修理工人A 和B，A种修理工平均每天能修理1.2台机器，每天工资3元；B种修理工平均每天能修理1.5台机器，每天工资5元，两种修理工修理机器的时间为负指数分布。
问工厂录用哪种工人较合算？本讲主要内容1. 排队论的基本概念2. 单服务台的排队模型3. 多服务台的排队模型4. 排队系统的最优化问题5. 数学建模实例：校园网的设计和调节收费问题5.1 排队论的基本概念5.1.1 什么是排队系统排队论也称随机服务系统理论，它是20世纪初由丹麦数学家Erlang应用数学方法在研究电话话务理论过程中而发展起来的一门学科，在实际中有广泛的应用。
它涉及的是建立一些数学模型，藉以对随机发生的需求提供服务的系统预测其行为。
现实世界中排队的现象比比皆是，如到商店购货、轮船进港、病人就诊、机器等待修理等等。
排队的内容虽然不同，但有如下共同特征：（1）有请求服务的人或物，如候诊的病人、请求着陆的飞机等，我们将此称为“顾客”。
（2）有为顾客提供服务的人或物，如医生、飞机跑道等，我们称此为“服务员”。
由顾客和服务员就组成服务系统。
（3）顾客随机地一个一个（或者一批一批）来到服务系统，每位顾客需要服务的时间不一定是确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时候服务员又空闲无事。
为了叙述一个给定的排队系统，必须规定系统的下列组成部分：1.输入过程即顾客来到服务台的概率分布。
排队问题首先要根据原始资料，由顾客到达的规律、作出经验分布，然后按照统计学的方法（如卡方检验法）确定服从哪种理论分布，并估计它的参数值。
我们主要讨论顾客来到服务台的概率分布服从泊松分布，且顾客的达到是相互独立的、平稳的输入过程。
所谓“平稳”是指分布的期望值和方差参数都不受时间的影响。
2.排队规则即顾客排队和等待的规则。
排队规则一般有即时制和等待制两种。
所谓即时制就是服务台被占用时顾客便随即离去；等待制就是服务台被占用时，顾客便排队等候服务。
等待制服务的次序规则有先到先服务、随机服务、有优先权的先服务等，我们主要讨论先到先服务的系统3.服务机构服务机构可以是没有服务员的，也可以是一个或多个服务员的；可以对单独顾客进行服务，也可以对成批顾客进行服务。
和输入过程一样，多数的服务时间都是随机的，且我们总是假定服务时间的分布是平稳的。
若以ξn表示服务员为第n个顾客提供服务所需的时间，则服务时间所构成的序列{ξn}，n=1，2，…所服从的概率分布表达了排队系统的服务机制，一般假定，相继的服务时间ξ1，ξ2，…是独立同分布的，并且任意两个顾客到来的时间间隔序列{Tn}也是独立的。
如果按服务系统的以上三个特征的各种可能情形来对服务系统进行分类，那么分类就太多了。
因此，现在已被广泛采用的是按顾客相继到达时间间隔的分布、服务时间的分布和服务台的个数进行分类。
排队论主要是对服务系统建立数学模型，研究如下内容：（1）排队系统的概率分布问题，主要是研究队长分布、等待时间分布和忙期分布等；（2）最优化问题：分为静态最优化和动态最优化，即为系统的最优设计和系统的最优运行问题；（3）排队系统的统计推断：判断一个给定的排队系统符合哪种模型，以便于根据排队理论进行分析研究。
5.1.2 排队模型的标准形式排队模型的标准形式为X/Y/Z/A/B/C，其中：X 表示顾客来到时间间隔的分布类型；Y 表示服务时间的分布类型；Z 表示服务员个数；A 系统容量;B 顾客源个数;C 服务规则.例如先来先服务的等待排队模型主要由三参数法即X/Y/Z，“M/M/1/k/∞/FCFS”表示顾客到达间隔时间和服务时间均服从负指数分布，一个服务台，系统至多容纳k个顾客潜在的顾客数不限，先来先服务的排队系统。
“M/M/c”即Poisson输入，负指数服务时间分布，c个服务台的等待制排队模型。
“M/G/1”即Poisson输入，一般服务时间分布，单个服务台的等待制排队模型。
5.1.3 排队系统的运行指标研究排队问题的目的，是研究排队系统的运行效率，估计服务质量，确定系统参数的最优值，以决定系统的结构是否合理，设计改进措施等。
所以，必须确定用来判断系统运行优劣的基本数量指标，这些数量指标通常是：（1）队长指排队系统中的顾客数，它的期望值记为Ls；排队长，指在排队系统中排队等待服务的顾客数，其期望值记为Lq。
系统中的顾客数= 等待服务的顾客数+ 正被服务的顾客数所以Lq（或Ls）越大，说明服务效率越低。
（2）逗留时间指一个顾客在排队系统中的停留时间，即顾客从进入服务系统到服务完毕的整个时间。
其期望值记为Ws。
等待时间，指一个顾客在排队系统中等待服务的时间，其期望值记为Wq。
逗留时间= 等待时间+ 服务时间（3）忙期指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度，即服务机构连续工作的时间长度。
它关系到服务员的工作长度，即服务机构连续工作的时间长度。
它关系到服务员的工作强度、忙期的长度和一个忙期中平均完成服务的顾客数，这些都是衡量服务效率的指标。
要计算以上这些指标必须知道系统状态的概率，所谓系统状态即时刻t时排队系统中的顾客数。
如果时刻t时排队系统中有n个顾客，就说系统的状态是n，其概率一般用Pn(t)表示。
求Pn(t)的方法，首先要建立含Pn(t)的关系式，因t为连续变量而n只取非负整数，所以建立的Pn(t)的关系式一般是微分差分方程，这时要求方程的解是不容易的，有时即使求出也很难利用。
因此，往往只求稳态解Pn，求Pn并不一定求t→∞时的Pn(t)极限，而只需由Pn'(t)=0，用Pn代替Pn(t)即可。
5.2 单服务台的排队模型设系统的输入过程服从泊松分布，服务时间服从负指数分布，单服务台的排队系统有以下三种情形：（1）标准型：M/M/1(M/M/1/∞/∞);（2）系统容量有限制：M/M/1/N/∞;（3）顾客源为有限的：M/M/1/∞/m.5.2.1标准型：M/M/1M/M/1模型是指顾客源为无限，顾客到达相互独立，到达过程是平稳的，到达率数服从参数为λ 的泊松分布：单服务台、队长无限、先到先服务；各顾客的服务时间服从参数为μ的负指数分布，且相互独立。
首先求出排队系统在任意时刻t的、状态为n的概率Pn(t)，已知顾客到达率服从参数为λ的泊松分布，服务时间服从参数为μ的负指数分布，由此决定了[t，t +△t]时间间隔内：（1）有1个顾客到达的概率为λ△t+o(△t)，没有顾客到达的概率是1-λ△t+o(△t)。
（2）当有顾客在接受服务时，1个顾客被服务完了的概率是μ /3 △t+o(△t)，没有服务完的概率是1-μ△t+o(△t)。
（3）多于一个顾客到达或服务完的概率为o(△t)，均可忽略。
注1：因为单位时间内顾客到达数X～P（λ），所以Δt时间间隔内顾客到达数Y～P（λλΔΔt），因而在Δt时间间隔内有1个顾客到达的概率为：P{ Y=1 } =λΔt·e-t=λΔt + o(ΔλΔt)，没有顾客到达的概率为P{Y=0}= e-t=1-λΔt + o(Δt)。
注2：由于服务时间T～E（μ），故在有顾客接受服务时，1个顾客被服务完的概率为μΔP{T≤Δt }=1 -e-t=μΔt + o(Δt)，没有被服务完的概率为1-μΔt + o(Δt)。
在t+△t时刻，系统中有n个顾客的状态由t时刻的以下状态转化而来：①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)。
因此，在t+△t时刻，系统中有n个顾客的概率Pn(t+△t)满足：Pn(t+ t)=Pn(t)(1 λ t µ t)+Pn+1(t)µ t+Pn 1(t)λ t+ο( t).移项整理，两边同除以△t，得Pn(t+ t) Pn(t)ο( t)=λPn 1(t)+µPn+1(t) (λ+µ)Pn(t)+. t t令△t→0，得dPn(t)=λPn 1(t)+µPn+1(t) (λ+µ)Pn(t)dt当n=0时，因为n=1,2L.P0(t+ t)=P0(t)(1 λ t)+P1(t)(1 λ t)µ t+ο( t)所以有dP0(t)=λP0(t)+µP1(t). dt对于稳态情形，与t无关，其导数为零。
因此，得到λPn 1+µPn+1 (λ+µ)Pn=0,n>1 λP0+µP1=0这是关于Pn的差分方程，也反映出了系统状态的转移关系，即每一状态都是平衡的，求解得P1=(λ/µ)P0，递推可得Pn=(λ/µ)P0(n≥1). n由概率的性质知∑Pn=0∞n=1，将上式代入λ / μ <1时可得到P0=1 λ/µPn=(1λ/µ)(λ/µ). n因为顾客到达规律服从参数为λ的泊松分布，服务时间服从参数为μ的负指数分布，其期望值就分别为λ，1/μ。
所以λ表示单位时间内平均到达的顾客数，μ表示单位时间内能服务完的顾客数。
如果令ρ=λ/μ，这时ρ就表示相同时间内顾客到达的平均数与能被服务的平均数之比，它是刻画服务效率和服务机构利用程度的重要标志，称ρ为服务强度。
上面在ρ<1的条件下得到了稳定状态下的概率Pn，n=0，1，2，…。
其实，如果ρ>1，可以证明排队长度将是无限增加的，即使ρ=1的情况下，P0(t)也是随时间而变化的，系统达不到稳定状态.因此，这里只讨论ρ<1时情况，从上面的推导知Pn=(1-ρ) ρn n=0,1,2,….下面计算出系统的运行指标.(1) 队长（平均顾客数）：由于系统的状态为n时即系统中有n个顾客，由期望的定义得Ls=∑npn=∑n(1 ρ)ρn=ρ/(1ρ)=λ/(µ λ).n=0n=1∞∞(2) 排队长：（等待的平均顾客数）Lq=∑(n 1)pn=∑(n 1)ρn(1 ρ)n=1n=1∞∞=ρ2/(1 ρ)=ρλ/(µ λ).可以证明，顾客在系统中逗留时间服从参数为μ-λ的负指数分布。
