数学建模之排队论

杨利霞

数学建模之排队论
排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常 常要排队。此时要求服务的数量超过服务机构（服务台、服务员等）的容量。也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。这种现象不仅在个人日常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现象。
排队论（Queuing Theory）也称随机服务系统理论，就是为解决上述问题而发展 的一门学科。它研究的内容有下列三部分：
7 j2 f) d) X9 z2 x- z) Y) X, [（i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。
3 ~9 k' {+ A' D% a1 K/ i5 [2 g" `（ii）优化问题，又分静态优和动态优，前者指优设计。后者指现有排队系统的优运营。
# T, @" Q' ]) m（iii）排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行分析研究。
9 W. L5 s1 t+ {0 b
8 T1 w9 U6 e: n4 _1 基本概念
8 Y# q: ]/ e# S# \3 W3 ^% r) U
$ Q9 s% Z! L4 ?3 V; l  e6 B- |1.1 排队过程的一般表示
% l' I: r4 z# l  H
下图是排队论的一般模型:
5 b* n  P$ |* M
! J) C1 d2 a4 ~( O5 S. m图中虚线所包含的部分为排队系统。各个顾客从顾客源出发，随机地来到服务机构，按一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统。
凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员 组成服务系统。对于一个服务系统来说，如果服务机构过小，以致不能满足要求服务的 众多顾客的需要，那么就会产生拥挤现象而使服务质量降低。 因此，顾客总希望服务机构越大越好，但是，如果服务机构过大，人力和物力方面的开支也就相应增加，从而 会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权衡决策，使其达到合理的平衡。

* B) m9 ]6 W8 A/ f. h! k7 e1 g# ?8 v1.2 排队系统的组成和特征

一般的排队过程都由输入过程、排队规则、服务过程三部分组成
1 ^  _/ g: U9 r  J  _
1.2.1 输入过程

输入过程是指顾客到来时间的规律性，可能有下列不同情况：
4 I* x8 m' r: D: p（i）顾客的组成可能是有限的，也可能是无限的。
/ l! q9 p9 Y4 e7 g（ii）顾客到达的方式可能是一个—个的，也可能是成批的。
（iii）顾客到达可以是相互独立的，即以前的到达情况对以后的到达没有影响； 否则是相关的。
' T% T1 k# @' p% n$ s. j# o/ K（iv）输入过程可以是平稳的，即相继到达的间隔时间分布及其数学期望、方差等 数字特征都与时间无关，否则是非平稳的。

1.2.2 排队规则

2 K4 V/ u1 ^" k. F9 s+ h排队规则指到达排队系统的顾客按怎样的规则排队等待，可分为损失制，等待制和 混合制三种.
（i）损失制（消失制）。当顾客到达时，所有的服务台均被占用，顾客随即离去。
9 `7 }) V- L: X) `; _（ii）等待制。当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接 受完服务才离去。例如出故障的机器排队等待维修就是这种情况。
; D" @  x) a' T7 g& w排队方式还分为单列、多列和循环队列。

1.2.3 服务过程
( O  A. |0 L1 [5 U% o7 L! M
) O* v( z3 `7 v( K+ ]（i）服务机构。主要有以下几种类型：单服务台；多服务台并联（每个服务台同 时为不同顾客服务）；多服务台串联（多服务台依次为同一顾客服务）；混合型。 （ii）服务规则。按为顾客服务的次序采用以下几种规则：
①先到先服务，这是通常的情形。
②后到先服务，如情报系统中，后到的情报信息往往有价值，因而常被优先处理。 ③随机服务，服务台从等待的顾客中随机地取其一进行服务，而不管到达的先后。
  y0 V7 i& z) C0 }④优先服务，如医疗系统对病情严重的病人给予优先治疗。

  G6 c7 P4 P4 K' H0 n1.3 排队模型的符号表示
  {# l3 W* o/ h+ y; o) `+ O
" V$ P) z! h/ ]排队模型用六个符号表示，在符号之间用斜线隔开，即 X/Y/Z/A/B/C 。第一 个符号 X 表示顾客到达流或顾客到达间隔时间的分布；第二个符号Y 表示服务时间的 分布；第三个符号Z 表示服务台数目；第四个符号 A是系统容量限制；第五个符号B 是 顾客源数目；第六个符号C 是服务规则，如先到先服务 FCFS，后到先服务 LCFS 等。并 约定，如略去后三项，即指X/Y/Z/∞/∞/FCFS的情形。我们只讨论先到先服务 FCFS 的情形，所以略去第六项。
表示顾客到达间隔时间和服务时间的分布的约定符号为：
M —指数分布（M 是 Markov 的字头，因为指数分布具有无记忆性，即 Markov 性）；
' U0 r! u2 X7 d- j1 }/ tD—确定型（Deterministic）；
* f& I& ?/ k( J/ n4 B. t9 cEk —k 阶爱尔朗(Erlang)分布；
5 A! \  t9 f+ X9 C5 qG —一般（general）服务时间的分布；
8 q5 w- {: n5 _# z  e: ?GI —一般相互独立（General Independent）的时间间隔的分布。
; `" \' ^' Q. o8 S, e9 s例如，M/M/1表示相继到达间隔时间为指数分布、服务时间为指数分布、单服务台、等待制系统。
0 @8 X8 x# i  oD/M/c/表示确定的到达时间、服务时间为指数分布、c个平行服务台（但顾客是一队）的模型。
" _7 T7 p0 S) i% H& K7 T, h/ v
1.4 排队系统的运行指标

# k) j4 v. @. h7 k8 {9 A1 C为了研究排队系统运行的效率，估计其服务质量，确定系统的优参数，评价系统 的结构是否合理并研究其改进的措施，必须确定用以判断系统运行优劣的基本数量指标，这些数量指标通常是：
(i)平均队长：指系统内顾客数（包括正被服务的顾客与排队等待服务的顾客）的数学期望，记作Ls 。
(ii)平均排队长:指系统内等待服务的顾客数的数学期望，记作 Lq 。
(iii)平均逗留时间：顾客在系统内逗留时间（包括排队等待的时间和接受服务的时间）的数学期望，记作Ws 。
(iv）平均等待时间：指一个顾客在排队系统中排队等待时间的数学期望，记作Wq 。
(v）平均忙期：指服务机构连续繁忙时间（顾客到达空闲服务机构起，到服务机构再次空闲止的时间）长度的数学期望，记为 Tb
2 j. u; G. R" Q5 d
2 输入过程与服务时间的分布

排队系统中的事件流包括顾客到达流和服务时间流。由于顾客到达的间隔时间和服 务时间不可能是负值，因此，它的分布是非负随机变量的分布。常用的分布有泊松分布、确定型分布，指数分布和爱尔朗分布。
: b) z9 g+ {/ h1 _
2.1 泊松流与指数分布

5 G6 ~- h2 R% d; Z1 R

" K5 h% G$ n1 Y1 h9 n" L7 t9 M! }
# l1 c# t8 O$ }/ c9 r; v& {# y
, g* z7 l1 x8 K  f0 l/ e( Y, P
4 M/M/s等待制排队模型

' {" Y, M6 Y  B  T4.1 单服务台模型

# q& M$ z6 ?3 N' V4 N单服务台等待制模型M/M/1/∞是指：顾客的相继到达时间服从参数为λ的负指数分布，服务台个数为1，服务时间V服从参数为μ的负指数分布，系统空间无限，允许无限排队，这是一类简单的排队系统。

4.1.1 队长的分布

/ h# C8 v/ I( ^( j
) ^0 N9 U# J" ^! `. \* c" h5 X7 b公式（7）和（8）给出了在平衡条件下系统中顾客数为n的概率。由式（7）不难看出，ρ 是系统中至少有一个顾客的概率，也就是服务台处于忙的状态的概率，因而也称 ρ 为服务强度，它反映了系统繁忙的程度。此外，（8）式只有在ρ=λ/μ<=1的条件下才能得到，即要求顾客的平均到达率小于系统的平均服务率，才能使系统达到统计平衡.
. K" S# H( Q/ T% m& @* r
4.2 与排队论模型有关的 LINGO 函数
+ U1 J- I! b; ?" G1 @! w
（1）@peb(load,S) 该函数的返回值是当到达负荷为 load，服务系统中有 S 个服务台且允许排队时系 统繁忙的概率，也就是顾客等待的概率。
% J7 g2 D( v3 |' G; g& T' L% a# [（2）@pel（load,S）该函数的返回值是当到达负荷为 load，服务系统中有 S 个服务台且不允许排队时系统损失概率，也就是顾客得不到服务离开的概率。 （3）@pfs(load,S,K) 该函数的返回值是当到达负荷为 load，顾客数为 K，平行服务台数量为 S 时，有限 源的 Poisson 服务系统等待或返修顾客数的期望值
/ c  }# m# h7 Z
+ j/ k+ E9 p2 p4.3 多服务台模型（ M/M/s/∞）
* b( T; P- s* G% j0 _
4 Y* q$ }. `, _- `* N' z* i设顾客单个到达，相继到达时间间隔服从参数为λ 的负指数分布，系统中共有s个 服务台，每个服务台的服务时间相互独立，且服从参数为 μ 的负指数分布。当顾客到达时，若有空闲的服务台则马上接受服务，否则便排成一个队列等待，等待时间为无限。



! C7 b0 j8 E9 P% q
  R. ^% A/ @; g6 Y" K! z5 排队模型的计算机模拟
' M8 ?5 O3 r  K: q' @
$ y0 }9 m/ J0 A5.1 确定随机变量概率分布的常用方法
+ X; `% n2 B) \1 l$ S
- d( v# t9 ]0 l; `在模拟一个带有随机因素的实际系统时，究竟用什么样的概率分布描述问题中的随 机变量，是我们总是要碰到的一个问题，下面简单介绍确定分布的常用方法：
1. 根据一般知识和经验，可以假定其概率分布的形式，如顾客到达间隔服从指数分布Exp(λ)；产品需求量服从正态分布N(μ,σ22) ；订票后但未能按时前往机场登机的人数服从二项分布B(n,p) 。然后由实际数据估计分布的参数 σ,μ,λ 等，参数估计 可用极大似然估计、矩估计等方法。
2. 直接由大量的实际数据作直方图，得到经验分布，再通过假设检验，拟合分布 函数，可用χ22检验等方法。
( W- C0 V" M' b) j8 k3. 既缺少先验知识，又缺少数据时，对区间(a,b)内变化的随机变量，可选用Beta 分布（包括均匀分布）。先根据经验确定随机变量的均值μ和频率高时的数值（即密度函数的大值点）m ，则 Beta 分布中的参数α1,α2可由以下关系求出：

$ p& o! a8 a3 f( k# i2 P8 a2 M
% L+ o7 E9 A: U% l, c( W5.2 计算机模拟
4 Y( V- W# a# w0 Z: `
当排队系统的到达间隔时间和服务时间的概率分布很复杂时，或不能用公式给出 时，那么就不能用解析法求解。这就需用随机模拟法求解，现举例说明。
$ F8 ^9 j+ |* F3 t- h2 T% M例1:
, {3 m" Q3 v5 z$ A0 X设某仓库前有一卸货场，货车一般是夜间到达，白天卸货，每天只能卸货 2 车，若一天内到达数超过 2 车，那么就推迟到次日卸货。根据表 3 所示的数据，货车到 达数的概率分布（相对频率）平均为 1.5 车/天，求每天推迟卸货的平均车数。

, H/ _3 e' n0 x8 A解: 这是单服务台的排队系统，可验证到达车数不服从泊松分布，服务时间也不服从指数分布（这是定长服务时间）。随机模拟法首先要求事件能按历史的概率分布规律出现。模拟时产生的随机数与事件的对应关系如表4
  [6 T' a/ O* F5 ?# W: p4 G
+ r, c; r' }  |" o6 Y用 a1 表示产生的随机数，a2 表示到达的车数，a3 表示需要卸货车数，a4 表 示实际卸货车数，a5 表示推迟卸货车数。编写程序如下：
' p/ R6 D/ K8 l
: f# E3 w. N5 Wclear
. H  k. B  n# ^* |# yrand('state',sum(100*clock));
* v- O/ P) u& hn=50000;
3 b$ r) [9 f' v7 `9 S7 T1 sm=2
a1=rand(n,1);
6 m; D5 n& V+ q" K# a- [" b8 xa2=a1; %a2初始化
6 `* e, F9 h# O- U$ N5 G1 j3 Qa2(find(a1<0.23))=0;
  {* n9 \, y$ i& g! m) Ta2(find(0.23<=a1&a1<0.53))=1;
a2(find(0.53<=a1&a1<0.83))=2;
a2(find(0.83<=a1&a1<0.93),1)=3;
2 U0 U3 J, V+ E* B* Ia2(find(0.93<=a1&a1<0.98),1)=4;
0 W- d# O4 m, M3 V* pa2(find(a1>=0.98))=5;
" C. E" x4 a! M% o8 o8 S9 f: Oa3=zeros(n,1);
# y# a" E9 \0 g0 ia4=zeros(n,1);
a5=zeros(n,1); %a2初始化
3 _- M5 }/ N6 J: q* Qa3(1)=a2(1);
if a3(1)<=m   
    a4(1)=a3(1);
    a5(1)=0;
else
   a4(1)=m;
: m: l3 U# ]) I5 ~end
for i=2:n   
: T" K9 S6 o/ ^( a    a3(i)=a2(i)+a5(i-1);   
    if a3(i)<=m   
% I6 ^9 T4 }6 a# o% d7 {% L" ^        a4(i)=a3(i);
    else   
        a4(i)=m;
    end   
& A: a/ K+ p, b2 a: O; n9 Lend
a=[a1,a2,a3,a4,a5];
sum(a)/n
---------------------
) n& j% a+ F! _0 X6 o% ~/ {# K