§11排队论
本章来介绍排队论（queuing theory）.
1909年，丹麦哥本哈根电话公司的A,K,Erlang对电话拥挤现象进行了研究，并发表了《概率与电话通话理论》（Probability and Theory of Telephone），开创了排队论的研究.
排队论，亦称随机服务系统理论或等待线理论，是研究因随机因素的影响而产生的排队现象，以便对随机服务系统进行最优设计和控制的理论.
关于排队，队列可能是有形的，如在火车站售票处买票，也可能是无形的，如电话订票；顾客可能是人，如在银行等待取款的顾客，也可能是物，如等待进港的船只；服务台可能是人，如售票员，也可能是物，如机场跑道；顾客数可能有限，如等待买票的人，也可能无限，如泄洪问题中的上游来水.
随机服务系统又称为排队系统.
排队系统的描述：顾客到达服务台是随机的.顾客到达服务台时，若服务台空闲，则立刻接受服务；否则，顾客应等待至服务台空闲时，再接受服务.顾客接受服务后即离开服务台.
排队系统的三要素：
（1）输入过程：指顾客到达的规律，如顾客数（有限或无限），顾客到达的方式（批量或单个），相继到达的顾客之间的时间间隔的分布.
（2）排队规则：包括服务台是否允许排队，顾客的排队意愿，服务顺序（先到先服务，后到先服务，随机服务，优先权服务）等.
（3）服务机制：服务台的数目，多服务台服务时的连结方式（串连或并连），服务时间的分布.
平稳状态：正常的，稳定的运行状态.如当储蓄所早上开门时，顾客很少，是为过渡期；此后，业务活动渐渐进入平稳状态.
显然，当排队系统处于平稳状态时，任意时刻时的顾客的数目的变化率（导数）等于0.
排队论的研究对象是平稳状态时的排队系统.
1953年，D,G,Kendall引入了排队系统的符号模型：
顾客到达的时间间隔的分布/服务时间的分布/服务台的数目/排队系统允许的最大顾客容量如排队模型//1/，其中表示顾客到达的时间间隔相互独立，且都服从指数分布，表示服务台对顾客的服务时间相互独立，且都服从指数分布，1为服务台的数目，表示排队系统允许的最大顾客数无限制.
排队系统的主要数量指标：
（1）平均排队队长：排队等待的平均顾客数；
（2）平均队长：平均顾客数；
显然，正在接受服务的顾客数.如对排队模型//1/，有.
（3）平均排队时间：顾客排队等待接受服务的平均时间；
（4）平均停留时间：顾客在排队系统内的平均时间.
显然，平均停留时间顾客接受服务的时间.
（5）平均停留时间：不同顾客的停留时间的平均值.
几个符号：
平均到达率：单位时间内到达的顾客数；
平均服务率：单位时间内接受服务的顾客数；
服务强度：平均到达率与平均服务率之比.
本章主要来研究排队模型//1/，其中表示顾客到达的时间间隔相互独立，且都服从指数分布，表示服务台对顾客的服务时间相互独立，且都服从指数分布，1为服务台的数目，表示排队系统允许的最大顾客数无限制.
设顾客到达的时间间隔相互独立，且都服从参数为的指数分布，即，则由概率论的知识不难证明，在时间内到达的顾客数服从参数为的普哇松分布，即.
由知，单位时间内到达的平均顾客数.
设服务台对顾客的服务时间服从参数为的指数分布，即，则.单位时间内接受服务的平均顾客数.
令在时刻时，排队系统内有个顾客，，
则在时刻时，排队系统内有个顾客，.
令在时刻时，排队系统内有个顾客，
在时刻时，排队系统内有个顾客，
在时刻时，排队系统内有个顾客，
在时刻时，排队系统内有个顾客，
则由的定义知，，，.
由模型假设知，顾客到达的时间间隔服从参数为的指数分布，服务时间服从参数为的指数分布，于是
在时刻时，排队系统内有个顾客|在时刻时，排队系统内有个顾客
在时间内，有1个顾客到达，无顾客接受完服务后离开
（注：；低阶无穷小量）
在时刻时，排队系统内有个顾客|在时刻时，排队系统内有个顾客
在时间内，无顾客到达，有1个顾客接受完服务后离开
在时刻时，排队系统内有个顾客|在时刻时，排队系统内有个顾客
在时间内，既无顾客到达，也无顾客接受完服务后离开
注意，此处虽不构成完备事件组，但不难证明，都是的无穷小量（），故仍采用来求解！
由全概率公式有
于是，
当时，在时刻时，排队系统内有个顾客，
在时刻时，排队系统内有个顾客，
在时刻时，排队系统内有个顾客，
在时刻时，排队系统内有个顾客，
则，，；；
在时刻时，排队系统内有个顾客|在时刻时，排队系统内有个顾客
在时间内，无顾客到达，有1个顾客接受完服务后离开
；
在时刻时，排队系统内有个顾客|在时刻时，排队系统内有个顾客
在时间内，无顾客到达（不可能有顾客接受完服务后离开！）
.
由全概率公式，有
于是，
在顾客流平稳状态时，有，即
令，代入（4），得
；
.
令，则.
于是，为等比数列，且首项为，通项为.即.
于是，
，
，
……，
，
.
将各式两边分别加和得
于是，.
.故.
这里，为排队系统中在平稳状态时的任意时刻时有个人的概率，与无关，在平稳状态时，有.
平稳状态时排队系统的若干数量指标：
（1）至少有个顾客的概率：
.
（2）平均队长：
（3）平均排队队长：
（4）平均停留时间：
由普哇松分布知，在平均停留时间内到达的平均顾客数为..于是，平均停留时间为.
（5）平均排队时间：
由普哇松分布知，在平均排队时间内到达的平均顾客数为..于是，平均排队时间为.
关系：，.（服务质量完全取决于服务强度）
（6）服务台空闲（排队系统中在顾客到达前没有顾客；顾客到达后不需排队等待即可接受服务）的概率：；
服务台繁忙（排队系统中在顾客到达前已有顾客；顾客到达后需排队等待再接受服务）的概率：.
例1在火车站某一售票口，顾客到达的时间间隔服从指数分布，且平均时间间隔为20分钟；售票口对顾客的服务时间服从指数分布，且平均服务时间为15分钟.试求此排队系统在1个小时内的下列数量指标：（1）顾客到达后，不需排队的概率；（2）顾客多于5人的概率；（3）顾客的平均人数；（4）顾客的平均排队人数；（5）顾客的平均停留时间；（6）顾客的平均排队时间.
解：显然，这是一个//1/排队模型，且，，.
（1）顾客到达后，不需等待排队系统内有0个顾客；
（2）顾客多于5人；
（3）顾客的平均人数；
（4）顾客的平均等待人数；
（5）顾客的平均停留时间；
（6）顾客的平均等待时间.▍
根据排队系统的这些数量指标，管理者就可采取措施改进服务，减少顾客的排队等待时间，以提高服务质量.
Ex.：
1.在北京大学图书馆的某一借书窗口，学生到达的时间间隔服从指数分布，且平均时间间隔为1.2分钟；窗口对学生的服务时间服从指数分布，且平均服务时间为0.75分钟.试求此排队系统在1个小时内的下列数量指标：（1）学生到达后，不需等待的概率；（2）学生的平均人数；（3）学生的平均等待人数；（4）学生的平均停留时间；（5）学生的平均等待时间.
2.某车间只有一台打磨机，单位时间内送达打磨机的工件的个数服从普哇松分布，且每小时送达5人；工件的打磨时间服从指数分布，且平均打磨时间为6分钟.试求此排队系统在1个小时内的下列数量指标：（1）工件送达后，需等待的概率；（2）等待打磨的工件的个数超过2个的概率；（3）等待打磨的工件的平均个数；（4）若此打磨机损坏，需新购一打磨机.问：新购打磨机的平均打磨时间至多为多少，才能使工件的平均等待时间不超过4分钟？（0.5，0.125，1，3）
本章来介绍排队论（queuing theory）.
1909年，丹麦哥本哈根电话公司的A,K,Erlang对电话拥挤现象进行了研究，并发表了《概率与电话通话理论》（Probability and Theory of Telephone），开创了排队论的研究.
排队论，亦称随机服务系统理论或等待线理论，是研究因随机因素的影响而产生的排队现象，以便对随机服务系统进行最优设计和控制的理论.
关于排队，队列可能是有形的，如在火车站售票处买票，也可能是无形的，如电话订票；顾客可能是人，如在银行等待取款的顾客，也可能是物，如等待进港的船只；服务台可能是人，如售票员，也可能是物，如机场跑道；顾客数可能有限，如等待买票的人，也可能无限，如泄洪问题中的上游来水.
随机服务系统又称为排队系统.
排队系统的描述：顾客到达服务台是随机的.顾客到达服务台时，若服务台空闲，则立刻接受服务；否则，顾客应等待至服务台空闲时，再接受服务.顾客接受服务后即离开服务台.
排队系统的三要素：
（1）输入过程：指顾客到达的规律，如顾客数（有限或无限），顾客到达的方式（批量或单个），相继到达的顾客之间的时间间隔的分布.
（2）排队规则：包括服务台是否允许排队，顾客的排队意愿，服务顺序（先到先服务，后到先服务，随机服务，优先权服务）等.
（3）服务机制：服务台的数目，多服务台服务时的连结方式（串连或并连），服务时间的分布.
平稳状态：正常的，稳定的运行状态.如当储蓄所早上开门时，顾客很少，是为过渡期；此后，业务活动渐渐进入平稳状态.
显然，当排队系统处于平稳状态时，任意时刻时的顾客的数目的变化率（导数）等于0.
排队论的研究对象是平稳状态时的排队系统.
1953年，D,G,Kendall引入了排队系统的符号模型：
顾客到达的时间间隔的分布/服务时间的分布/服务台的数目/排队系统允许的最大顾客容量如排队模型//1/，其中表示顾客到达的时间间隔相互独立，且都服从指数分布，表示服务台对顾客的服务时间相互独立，且都服从指数分布，1为服务台的数目，表示排队系统允许的最大顾客数无限制.
排队系统的主要数量指标：
（1）平均排队队长：排队等待的平均顾客数；
（2）平均队长：平均顾客数；
显然，正在接受服务的顾客数.如对排队模型//1/，有.
（3）平均排队时间：顾客排队等待接受服务的平均时间；
（4）平均停留时间：顾客在排队系统内的平均时间.
显然，平均停留时间顾客接受服务的时间.
（5）平均停留时间：不同顾客的停留时间的平均值.
几个符号：
平均到达率：单位时间内到达的顾客数；
平均服务率：单位时间内接受服务的顾客数；
服务强度：平均到达率与平均服务率之比.
本章主要来研究排队模型//1/，其中表示顾客到达的时间间隔相互独立，且都服从指数分布，表示服务台对顾客的服务时间相互独立，且都服从指数分布，1为服务台的数目，表示排队系统允许的最大顾客数无限制.
设顾客到达的时间间隔相互独立，且都服从参数为的指数分布，即，则由概率论的知识不难证明，在时间内到达的顾客数服从参数为的普哇松分布，即.
由知，单位时间内到达的平均顾客数.
设服务台对顾客的服务时间服从参数为的指数分布，即，则.单位时间内接受服务的平均顾客数.
令在时刻时，排队系统内有个顾客，，
则在时刻时，排队系统内有个顾客，.
令在时刻时，排队系统内有个顾客，
在时刻时，排队系统内有个顾客，
在时刻时，排队系统内有个顾客，
在时刻时，排队系统内有个顾客，
则由的定义知，，，.
由模型假设知，顾客到达的时间间隔服从参数为的指数分布，服务时间服从参数为的指数分布，于是
在时刻时，排队系统内有个顾客|在时刻时，排队系统内有个顾客
在时间内，有1个顾客到达，无顾客接受完服务后离开
（注：；低阶无穷小量）
在时刻时，排队系统内有个顾客|在时刻时，排队系统内有个顾客
在时间内，无顾客到达，有1个顾客接受完服务后离开
在时刻时，排队系统内有个顾客|在时刻时，排队系统内有个顾客
在时间内，既无顾客到达，也无顾客接受完服务后离开
注意，此处虽不构成完备事件组，但不难证明，都是的无穷小量（），故仍采用来求解！
由全概率公式有
于是，
当时，在时刻时，排队系统内有个顾客，
在时刻时，排队系统内有个顾客，
在时刻时，排队系统内有个顾客，
在时刻时，排队系统内有个顾客，
则，，；；
在时刻时，排队系统内有个顾客|在时刻时，排队系统内有个顾客
在时间内，无顾客到达，有1个顾客接受完服务后离开
；
在时刻时，排队系统内有个顾客|在时刻时，排队系统内有个顾客
在时间内，无顾客到达（不可能有顾客接受完服务后离开！）
.
由全概率公式，有
于是，
在顾客流平稳状态时，有，即
令，代入（4），得
；
.
令，则.
于是，为等比数列，且首项为，通项为.即.
于是，
，
，
……，
，
.
将各式两边分别加和得
于是，.
.故.
这里，为排队系统中在平稳状态时的任意时刻时有个人的概率，与无关，在平稳状态时，有.
平稳状态时排队系统的若干数量指标：
（1）至少有个顾客的概率：
.
（2）平均队长：
（3）平均排队队长：
（4）平均停留时间：
由普哇松分布知，在平均停留时间内到达的平均顾客数为..于是，平均停留时间为.
（5）平均排队时间：
由普哇松分布知，在平均排队时间内到达的平均顾客数为..于是，平均排队时间为.
关系：，.（服务质量完全取决于服务强度）
（6）服务台空闲（排队系统中在顾客到达前没有顾客；顾客到达后不需排队等待即可接受服务）的概率：；
服务台繁忙（排队系统中在顾客到达前已有顾客；顾客到达后需排队等待再接受服务）的概率：.
例1在火车站某一售票口，顾客到达的时间间隔服从指数分布，且平均时间间隔为20分钟；售票口对顾客的服务时间服从指数分布，且平均服务时间为15分钟.试求此排队系统在1个小时内的下列数量指标：（1）顾客到达后，不需排队的概率；（2）顾客多于5人的概率；（3）顾客的平均人数；（4）顾客的平均排队人数；（5）顾客的平均停留时间；（6）顾客的平均排队时间.
解：显然，这是一个//1/排队模型，且，，.
（1）顾客到达后，不需等待排队系统内有0个顾客；
（2）顾客多于5人；
（3）顾客的平均人数；
（4）顾客的平均等待人数；
（5）顾客的平均停留时间；
（6）顾客的平均等待时间.▍
根据排队系统的这些数量指标，管理者就可采取措施改进服务，减少顾客的排队等待时间，以提高服务质量.
Ex.：
1.在北京大学图书馆的某一借书窗口，学生到达的时间间隔服从指数分布，且平均时间间隔为1.2分钟；窗口对学生的服务时间服从指数分布，且平均服务时间为0.75分钟.试求此排队系统在1个小时内的下列数量指标：（1）学生到达后，不需等待的概率；（2）学生的平均人数；（3）学生的平均等待人数；（4）学生的平均停留时间；（5）学生的平均等待时间.
2.某车间只有一台打磨机，单位时间内送达打磨机的工件的个数服从普哇松分布，且每小时送达5人；工件的打磨时间服从指数分布，且平均打磨时间为6分钟.试求此排队系统在1个小时内的下列数量指标：（1）工件送达后，需等待的概率；（2）等待打磨的工件的个数超过2个的概率；（3）等待打磨的工件的平均个数；（4）若此打磨机损坏，需新购一打磨机.问：新购打磨机的平均打磨时间至多为多少，才能使工件的平均等待时间不超过4分钟？（0.5，0.125，1，3）
