数学建模排队论

1、排队论简简 介介顾客到商店购买物品病员到医院看病旅客到售票处购买车票学生去食堂就餐顾客等待出租车通讯卫星与地面若干待传递的信息码头的船只等待装卸货物要降落的飞机因跑道不空而在空中盘旋等等. 排队是日常生活和生产中经常遇到的现象。 面对拥挤现象，如果服务设施太少，顾客排队等待的时间就会很长，对顾客会带来不良影响。而随服务设施增加，人力、物力的支出就越大。 如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是排队论所要研究解决的问题。简简 介介排队论(Queuing Theory)，又称随机服务系统理论(Random Service

2、System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。 目目 录录 1 排队系统综述及常用分布4 排队系统的优化问题 2 单服务台 排队模型1/MM3 多服务台 排队模型CMM/1 排队系统综述及常用分布排队系统综述及常用分布1.1 排队系统的描述排队系统的描述 任何一个排队问题的基本排队过程都可以用图1.1表示。每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。图1.1 1.2 排队系统的组成排

3、队系统的组成 通常的排队系统可以分为3个组成部分：输入过程、排队规则和服务台.3）顾客流的概率分布或称相继顾客到达的时间间隔的分 布，相继到达的时间间隔可以是确定的也可以是随机的， 常见的分布有定长分布、二项分布和负指数分布等.输入过程：输入过程：顾客到达的规律1）顾客源 可以是有限的，也可以是无限的.2）顾客到达的方式描述顾客是怎样来到系统的，是单个 到达还是成批到达.1.2 排队系统的组成排队系统的组成1）等待制 当顾客到达时，所有的服务台均被占用，顾客 就排队等待，直到接 受完服务才离去。例如出故障的机器 排队等待维修就是这种情况.排队规则：排队规则：指从队列中挑选顾客进行服务的规律.3

4、）混合制介于损失制和等待制之间，即既有等待又有损 失.有队列长度有限和排队等待时间有限两种情况，在限度 以内就排队等待，超过一定限度就 离去.2）损失制当顾客到达时，所有的服务台均被占用，顾客 随即离去.排队方式还分为单列、多列和循环队列。 服务台：服务台： 1）服务台数量及构成形式从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，有单队列单服务台、单队多服务台并联、多队多服务台并联式、单队多服务台串联式等. 2） 服务方式指在某一时刻接受服务的顾客数，有单个服务和成批服务两种. 3）服务时间的分布在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、爱

5、尔朗分布等.1.2 排队系统的组成排队系统的组成1.3 排队系统的符号表示（排队系统的符号表示（Kendall符号）符号） 根据不同的输入过程、排队规则和服务台数量，可以形成不同的排队模型，为方便对模型的描述，通常采用如下的符号形式： 其中，X顾客到达间隔时间概率分布Y服务时间的概率分布Z服务台数A系统容量限制，即系统中允许的最多顾客数B顾客源总数C服务规则CBAZYX/1.3 排队系统的符号表示（排队系统的符号表示（Kendall符号）符号） 表示顾客相继到达间隔时间和服务时间的各种分布符号有：M表示到达过程为泊松过程或负指数分布；D表示定长输入；Ek表示k阶爱尔朗分布；G表示一般相互独立的

6、随机分布. 比如，MMcNmFCFS表示相继到达时间间隔和服务时间为负指数分布，c个服务台，系统容量为N，顾客源数目为m，采用先到先服务规则的排队模型.1.4 排队系统主要数量指标和记号排队系统主要数量指标和记号1.在系统里没有顾客的概率，即所有设施空闲的概率，记 为2.排队的平均长度，即排队的平均顾客数记为3.在系统里的平均顾客数，包括排队的顾客数和正在被服 务的顾客数，记为4.一位顾客花在排队上的平均时间，记为5.一位顾客花在系统里的平均逗留时间，包括排队时间和 被服务的时间，记为6.顾客到达系统时，得不到及时的服务，必须排队等待服 务的概率，记为7.系统里正好有 个顾客（包括排队的和正在

7、被服务的顾客 的概率记为P0LpLsWqWsnPnPw1.5 排队系统的常用分布排队系统的常用分布1）泊松分布： (1) 平稳性：在时间 内，到达个顾客的概率只与 和 的大小有关，而与时刻起点 无关 (2) 独立性：在时间 内到达 个顾客的概率与起始时刻之前到达多少个顾客无关(3) 普通性：对于充分小的时间间隔 ，在时间 内最多有一个顾客到达系统即在时间 内有2个或2个以上顾客到达的概率极小，有ttn0lim20ttPnntttttnttttt ,2, 1 ,00!)(ntenttPtnn可以证明，在长为t的时间内到达个顾客的概率为：期望为：ttEn)(泊松过程具有如下性质：1.5 排队系统的

8、常用分布排队系统的常用分布当 时，即单位时间内到达个顾客的概率为：1tenPPnnn!)1(2）负指数分布 理论上可以证明若顾客在单位时间内到达系统的个数 是服从参数为 的泊松分布，则顾客到达系统的间隔时间 服从参数为 的负指数分布，反之亦然 负指数分布的概率密度为：XT)0()(tetftT1)(TE间隔时间 的期望值：T其中 为单位时间内到达系统的顾客的期望值1.5 排队系统的常用分布排队系统的常用分布3）爱尔朗分布：分布密度函数：)0, 0()!1()()(1ktektkttkkkkf期望：1)(TE同样，对顾客服务时间常用的概率分布也是负指数分布，概率密度为：其中 表示单位时间内完成服

9、务的顾客数，也称平均服务率) 0()(tetft2 单服务台单服务台 排队模型排队模型2.1 标准的标准的 模型模型1/MM2.1.1 模型条件模型条件 模型 表示，顾客到达过程服从泊松分布，服务时间服从负指数分布，单服务台，队长和顾客来源无限.简记为 ./ 1/MM1/MM1）已知单位时间平均到达率 和平均服务率 .2）系统容量无限，顾客源总数无限.3）排队规则为单队，先到先服务)(1/MM系统在稳定情况下的状态转移如图2.1图2.1Pn 1P2P1P0PnPn 1 可以得到如下平衡方程：nnnPPP11（2.1）01PP（2.2）在图2.1中，椭圆圈中的数字表示系统的状态（顾客数），箭头表

10、示从一个状态到另一个状态的转移当系统处于稳定状态时，对于每个状态来说，转入率与转出率相等2.1.2 模型的数量指标公式模型的数量指标公式2.1 标准的标准的 模型模型1/MM由（2.1）和（2.2）可以递推求解，01PP02102)()1 (-PPPP.0)(PPnn.nnPP110式中 表示平均到达率与平均服务率之比，称为服务强度. 1）在系统里没有顾客的概率2011111LPLPnPPnLnnnnnnq10P000)1 ()1 (nqnnnnnsLkknPL2）平均排队的顾客数 3）在系统里的平均顾客数2.1 标准的标准的 模型模型1/MM模型的各数量指标参数如下：1/MM2.1 标准的标

11、准的 模型模型 4）一位顾客花在系统里的平均逗留时间（当顾客相继到达 的间隔时间服从 的负指数分布，服务时间服从 的负指数 分布时，顾客在系统中的平均逗留时间服从参数为 的 负指数分布.）1)(XEWs 5）一位顾客花在排队上的平均时间（等于逗留时间减去服 务时间） 6）顾客到达系统时，得不到及时的服务，必须等待服务的 概率 7）系统里正好有 个顾客的概率qsqLWW1wP0)(PPnnn2.2 系统容量有限的系统容量有限的 模型模型/ 1/NMM 系统容量为N，系统中排队等待的顾客数最多为N-1，所以在某一时刻某位顾客到达时，如果系统中已有N位顾客，那么这位顾客被拒绝进入系统，如图2.2N-

12、1 N0PnP1nP2P1P图2.2由状态转移图，可以建立系统概率平衡方程如下：,)(,11101NNkkkPPPPPPP1 Nk2.2 系统容量有限的系统容量有限的 模型模型/ 1/NMMNkNPNPkk,11110；于是时，当,11, 110NkkkkNPN得，又设NnnP011NkPPNkkN,11111110；，模型的各数量指标参数如下： 1）系统里没有顾客的概率11111110NPN2.2 系统容量有限的系统容量有限的 模型模型/ 1/NMM 2）系统里有n个顾客的概率NnPPnn，03）在系统里的平均顾客数 121111111NNNLNNNs4）平均排队的顾客数 1121110NN

13、NPLLsq2.2 系统容量有限的系统容量有限的 模型模型/ 1/NMM顾客到达又能进入系统的概率为 ，故系统的平均有效到达率 为：NP1e011PPNe由此，5）一位顾客花在排队上的平均时间6）一位顾客花在系统里的平均逗留时间essLWeqqLW2.3 顾客源有限的顾客源有限的 模型模型mmMM/1/0PnP1nP2P1P1nP2) 1(mm) 1(nm)(nm由状态转移图，可以建立系统概率平衡方程如下：,)() 1(,11101mmnnnPPPnmPnmPPmP11mn以机器维修问题为例：设有m台机器（顾客总体）,每台机器单位时间内发生故障的概率 相同（顾客平均到达率），等待修理及正在修理

14、的机器数为n，工人数为1（单服务台），则对系统的有效到达率 为e)(nme2.3 顾客源有限的顾客源有限的 模型模型mmMM/1/用递归方法解上述方程组得，mnPnmmPkmmPnnmkk1!1000模型中各数量指标：LmPPLLPmLeqs000111eqqesLWLW3 多多服务台服务台 排队模型排队模型CMM/单队、并列的多服务台模型可大致分为三种情况： 1）标准 模型 2）系统容量有限， 3）顾客源有限，CMM/mCMM/NCMMCMM/其中以标准 模型为例.3.2 系统的状态概率和主要运行指标系统的状态概率和主要运行指标 已知单位时间平均到达率 ，单列， 个服务台，每个服务台的工作相

15、互独立且平均服务率相同，都等于 ，顾客源无限，容量无限，排队规则为等待制CC) 1( n) 1( nn20P2P1P1nPnP1nP,)(,)1(,111101cnnnnnPcPcPPnPPnPP）（),.,2 , 1(cn ,.)2, 1(ccn3.1 模型条件模型条件(1)系统的状态概率系统的空闲概率3.2 系统的状态概率和主要运行指标系统的状态概率和主要运行指标系统内有n个顾客的概率CnPCCCnPnPnCnnn00)(!1)(!11100)(11!1)(!1CkCkCkP1C(2)系统的主要运行指标1)1( !)(02qqqqcqWLWLWLLPccL4 排队系统的优化问题排队系统的优

16、化问题对排队系统进行最优化设计可以从两个方面考虑： 其一，给出系统的某种费用（或利润）结构，要求平均总费用（或平均总利润）最低的情况下做出最优设计(经济效益) 其二，在一定服务质量指标下要求系统运行效能达到必要的水平(社会效益)下面就平均服务率 和服务台数c这两个决策变量的优化问题进行讨论4.1 模型的最优平均服务率模型的最优平均服务率1/MM费用函数 为单位时间服务成本与顾客在系统中逗留损失费用之和的期望值假定服务率 是一个连续值则费用函数可为： fbLaf)(min（4.1）其中：a当 =1时服务机构单位时间的成本费用 b每个顾客在系统中停留单位时间的损失费用L系统内平均顾客数 baf将 代入（4.1），则 ，于是L2baddf令 ，考虑 得，0ddfab（4.2）例例4.1：银行有三个窗口办理业务，顾客到达服从泊松流，到达速率为0.9人/分钟，办理业务时间服从负指数分布，每窗口的平均服务速率为0.4人/分钟，顾客到达后取得一