排队系统的统计模拟实现.doc

摘 要毕业设计(论文)（2010 年） 课题名称 排队系统的统计模拟实现 专业名称 信息与计算科学 学生姓名 周 华 学 号 2003060129 指导教师 孙大飞 南京工业大学理学院17摘 要排队系统的统计模拟实现摘 要在现实生活中常需要在某些条件完全随机的情况下对一件事情作出分析和决策。由于用传统实验验证这样的随机系统需要耗费大量的人力物力且难以达到很好的效果。为节省经费我们考虑采用计算机来对随机系统进行模拟。排队系统作为一个典型的随机系统广泛的存在于生活中。用计算机模拟排队系统可以降低系统的研究成本，提高系统的试验效率。为管理人员对实际系统的运营作出决策提供可靠的试验依据。本文首先介绍了递推生成伪随机数的线性同余法，在此基础上经逆变换法生成满足具体排队系统相应条件的随机变量。然后利用离散事件模拟法介绍排队系统的一些基础理论模拟排队系统。最后通过在计算机上编写程序实现了单服务员和多服务员情况下的排队系统的模拟和比较。关键词：随机变量 排队系统 离散事件模拟法AbstractAbstractIn real life,we often need in some conditions completely random cases of one thing analysis and decision making. Due to the use of traditional experimental results verify that the stochastic system requires a lot of manpower and difficult to achieve good results. To save money, we consider using a computer to simulate random system. As a typical stochastic system，queuing system widely exists in life. Using the computer simulation system of queuing system can reduce the cost, improve the system of study efficiency. For managers to make decisions of the practical system provides reliable operation.This paper firstly introduces the recursive generate pseudo random by the linear congruence method, based on the substitution method of generating meet specific conditions in the corresponding random variables. Then using discrete event simulation method introduced some basic theoretical queuing system simulation queuing system. Finally, through computer programming realized in the attendant and many waiter situation of simulation and comparison queuing system.目 录目 录摘 要IAbstractII第一章 引 言11.1随机变量的模拟11.2排队系统的随机模拟21.3本文的内容安排2第二章 随机数的产生32.1物理方法32.2计算机模拟32.3伪随机数的应用52.4 小结5第三章 随机变量的模拟63.1逆变换法63.2连续随机变量63.3离散随机变量73.4小结8第四章 排队系统的统计模拟94.1 排队系统的理论94.2 排队系统的模拟的算法104.3排队系统的模拟124.4 小结14第五章 总 结15参考文献16致 谢17南京工业大学本科生毕业设计（论文）第一章 引 言在现实生活中常需要在某些条件完全随机的情况下对一件事情作出分析和决策。由于用传统实验验证这样的随机系统需要耗费大量的人力物力且难以达到很好的效果。为节省经费我们考虑采用计算机来对随机系统进行模拟。随机系统的模拟是利用计算机上编写的计算机程序语言模拟实际系统的行为。通过观察和分析计算机模型系统的性能，从而掌握和了解实际系统的大致情况，并依此对实际系统作出分析和决策。1.1随机变量的模拟随机变量的模拟离不开0,1)内均匀分布随机数的产生。真正的随机数只能由物理设备产生，由于其产生的效率过低，在实际应用中我们采用计算机递推产生的伪随机数。伪随机数并不是真正的随机数，它虽然符合真随机数的统计特征但实际上是一个周期序列。一种常用的产生随机数的方法是：从初值出发，利用公式： (1-1)逐步计算，其中和是给定的正整数。称为一个伪随机数，它近似服从0,1)内的均匀分布。在随机变量的模拟中最常用的方法是逆变换法，它首先产生0,1)内均匀分布随机数，再通过计算分布函数的反函数得到所要的随机数。设是0,1)上均匀分布的随机变量，可以证明对于任一分布函数，随机变量 (1-2)的分布函数为。逆变换法是一种很好的产生指数型随机变量的算法，因为能很快得出指数型变量的分布函数的反函数。但是对某些随机变量，其分布函数的反函数很难或不可能显式地表出，无法直接应用逆变换法，因此我们考虑采用其他的算法。假设我们希望生成一个满足概率分布为, (1-3)的离散随机变量，为此，先生成一个随机数U，即U在0,1）内均匀分布，令：，如果 ， (1-4)则满足所给随机变量的分布。上述算法被称为离散随机变量的逆变换法。1.2排队系统的随机模拟排队系统是各种随机系统中最为典型的。计算机系统、通信系统和营业窗口系统都是典型的有形或者无形的排队系统。随机模拟是求解排队系统和分析排队系统系能的非常有效的方法，它是用计算机程序直接建立真实系统的模型，通过计算机系统的随机变化研究其行为的特征。变量和事件是排队系统最重要的因素。在模拟中我们紧盯某些变量。只要出现一个事件，上述变量的值就会出现改变或更新，我们就要找到相应感兴趣的数据作为输出。为确定下一个事件何时出现，我们需要一个事件列表（此列表给出后面最近的事件和这些事件出现的时间表）。只要出现一个事件我们就重置时间变量、状态变量、计数变量和收集相应的数据。这样我们就可以及时追踪随时间而变化的系统。1.3本文的内容安排本文将采用系统模拟方法对排队系统进行模拟。并统计不同情况下服务员人数安排及顾客排队情况。第二章主要介绍0,1)上均匀分布的伪随机数产生方法。第三章主要介绍在产生了0,1)上均匀分布的随机数后以它为基石模拟其他各种分布的随机变量的方法。第四章主要介绍了排队系统的基础理论及离散事件模拟方法，并且对具体的排队系统进行模拟统计并讨论实验结果。南京工业大学本科生毕业设计（论文）第二章 随机数的产生当要在计算机上模拟任何一个带有随机性的系统时，总离不开随机数的生成，而在0,1)上均匀分布的随机数序列是最基本的随机数序列，用它可以得到具有任何分布概率分布的随机数序列。它是随机模拟的基石。因此，我们要讨论如何产生合理的在0,1)上均匀分布的随机数序列。2.1物理方法随机数最早是通过手工或机械的方式由手纺车掷骰子或洗纸牌的方式产生的。由于理论上0,1)上有无穷多个数。这样的物理方法并不能无穷多次的进行下去，所以这样的物理方法所能产生的随机数其实是0,1)上有限多个离散的有理数。因此完全精确的产生0,1)上均匀分布是随机数是不可能的，在实际应用中也是没有意义的。设序列 (2-1)为物理设备所能产生的0,1)内的一串等间隔分布的有理数序（即等差数列）。如果n充分大，则该数列在0,1)内充分“稠密”。因此，问题的本质在生成一个等概率分布的离散随机数集。如果这一件事能够办到，则它可以看作0,1)上均匀分布的随机数的一个近似。实际上，可以取，若能生成上的等概率分布，则将上述整数等概率随机变量除以n即能得到所需0,1)上均匀分布随机数序。较常见的一种办法有：取则内的任何一个数都可以用一个相应的m位二进制数表示。该二进制数每一位取0或者1。只要等概率的生成0和1就可以得到一个概率的m位2进制数。最直接的可以用掷硬币的方法等概率地产生0或1。这样的方法能够较完美的产生0,1)上均匀分布的随机数序，但由于实验次数过多，产生随机数的效率过慢，这一方法在实际模拟应用中是不可取也是不适用的。2.2计算机模拟在实际应用中常采用计算机模拟产生伪随机数。尽管作为数列的伪随机数是由机器产生的，但他们具有0,1)上均匀分布独立随机变量的一切特征。一种最常用产生伪随机数的方法是：从初值(也称为种子)出发，利用公式 (2-2)逐步计算，其中和是给定的正整数，上式表示为被除后的余数。于是每一个均为中的一个，称为一个伪随机数，它近似服从0,1)上的均匀分布。由上式产生随机数的方法称为乘同余法。由于每一个均取值中的一个，故若干次后(至多次)所产生的随机数必定重复，且自此之后整个序列也开始重复。于是，我们在选择常数和时，希望对任一初值，在重复出现前所产生的随机数序列足够长。一般的，在选取常数和时应遵循如下原则：(1) 对于任一初值，产生的序列具有0,1)上均匀分布独立随机变量的特征。(2) 对已任一初值，在重复出现前产生的随机数序列足够长。(3) 每一数值均可由计算机有效计算。为满足上述三个条件，可选一个符合计算机字长要求的较大素数作为。对于32位计算机(其中第一个字节为正负号)，已经证明和符合上述要求。由上述乘同余法产生伪随机数时，分别取：；所得到的序列：从上可以看出，当能整除时，最后的序列必定会收敛到零。当不能整除时，则所得的序列是周期序列，且最大周期是。由此可以看出，递推方法计算出来的伪随机数序列实际上是周期序列，而非真正的随机序列。事实上当取得非常大的时候在模拟中只需取其一个周期即可，这样的伪随机数序列满足均匀分布独立随机变量的一切特征。由上述乘同余法模拟的1000个在0,1)上服从均匀分布的伪随机数的结果，如图2-1所示。另一个生成随机数的方法是如下的递推公式 （2-3）由于它包含乘法和加法因此被称为混合同余法。当采用这种方法生成随机数时，人们常取为计算机字长，这是由于这是因为这种取法易于非常有效的计算。混合同余法是乘同余法和加同余法的混合，它产生的随机数周期较大且统计特性较佳。图2-1 0,1)上均匀分布的伪随机数2.3伪随机数的应用设随机向量(X,Y)在中心为原点、面积为4的正方形上均匀分布，则在这个正方形里画其内切圆，如果我们大量的在正方形里生成随机点(X,Y)。可以证明这些点落在内切圆内的概率等于，即 (2-4)设U是0,1)上的均匀分布，则2U是在0,2)上的均匀分布。2U-1在-1,1)上均匀分布。因此我们生成2个随机数令，我们可以如此估计：先生成大量随机数对，之后用满足的随机数对的比例来估计。以上算法由计算机模拟得到的结果是：，可以看到与准确值相差不多。2.4 小结本章介绍了随机数的产生原理和方法，并给出了随机数的一个简单应用。第三章 随机变量的模拟第三章 随机变量的模拟用计算机模拟任何一个随机现象时必然涉及一个给定概率分布的随机变量。例如，在模拟排队系统时，顾客的到达时间和服务时间都是满足一定分布的随机变量。一旦这些随机变量所满足的概率分布函数被选定，则必须有生成该给定概率分布的随机变量的算法，才能在计算机内得到这样的随机变量。而所有的这些方法都基于0,1)上的均匀分布的随机变量。3.1逆变换法逆变换法（也称反演法或变换法）是在随机变量的模拟中最常用的方法。它首先产生0,1)内均匀分布随机数，再通过计算分布函数的反函数得到所需要的随机变量。命题3.1 设是0,1)上均匀分布的随机数，则对于任一分布函数，随机变量 (3-1)的分布函数为。证明：以记的分布函数，则由于是一分布函数，故它是的单调递增函数，且不等式“”等价于不等式“”。于是有因为，且在0,1)上均匀分布。3.2连续随机变量由逆变换法可知，对于连续随机变量的具体算法是：首先产生均匀分布的随机数，取即可。例如X是参数为1的指数型随机变量，其分布函数为，如果设，则 (3-2)于是参数1的指数分布的随机变量可由下式产生 (3-3)用计算机模拟的10000个参数为1的指数分布的随机变数，如图3-1所示。图3-1指数型随机变量的模拟利用逆变换法可以模拟随机变量，但由于某些随机变量分布函数的反函数很难或不可能显式地表出，无法直接应用逆变换法。因此我们考虑采用其他的算法，例如拒绝法、极坐标法等。3.3离散随机变量假设我们希望生成一个概率分布函数为， (3-4)的离散随机变量X。为此，首先生成一个0,1)上均匀分布随机数U，且令 (3-5)对于，由于，故我们有 (3-6)所以的值满足分布要求。离散随机变量模拟算法如下(1)生成一个随机数;(2)如果则令停止;如果，则令停止;如果则令停止;说明：(1) 如果，是由小到大排列，即，且以记的分布函数，则，如果，则等于换言之，当生成一个随机数后，我们是通过是否落在区间来确定的值(或等价的通过求的逆)。基于此，上述方法被称为离散的逆变换法。(2) 用上述方法来生成一个离散随机变量所需的时间与我们要搜索的区间个数成正比，于是有必要以的降序排列的取值。这样就可以大大的节省区间搜索所耗费的时间。实际上当所求的随机变量为离散均匀随机变量时，上述区间搜索时不必要的。用计算机模拟10000个参数为5的泊松分布随机数，如图3-2所示。图3-2泊松分布随机数3.4小结本章介绍了计算机模拟随机变量的基本原理和算法，并给出了模拟的例子。南京工业大学本科生毕业设计（论文）第四章 排队系统的统计模拟排队问题广泛的存在于实际生活之中，当一个顾客到达请求服务时，服务资源常常被其他顾客所占用，因此必须让需要服务的顾客按一定规则进行排队，然后按次序对顾客进行服务，这就构成了一个排队系统。用计算机模拟排队系统可以降低系统的研究成本，提高系统的试验效率。为管理人员对实际系统的运营作出决策提供可靠的试验依据。4.1 排队系统的理论一个排队系统主要由这四个基本要素组成：顾客到达过程、排队规则、服务时间、服务系统的结构，如图4-1所示。图4-1排队系统的结构顾客到达过程描述顾客的到达规律。设在时刻顾客到达，则称到达时点。随机变量称为到达间隔，若是独立分布的则称E()为平均到达间隔。通常顾客的到达规律是Poisson到达。所谓的排队规则是指从等待服务的用户中规定用户进入服务的次序。常见的规则有：先来先服务、后来先服务、随机选择服务、优先权服务、批量服务等。设第i个顾客等待时间为，则也是一个随机变量序列。服务时间是指服务员对顾客服务所消耗的时间。设服务员对第i个顾客的服务所用时间为，则是一个随机变量序列。若该序列是独立分布的则它的期望E()是平均服务时间。当独立同分布的的概率分布同样满足一定的概率分布，例如Poisson分布、指数分布等。服务系统的结构是以服务窗口的数目而言。当只有一个窗口时，称为单窗口服务系统；有多个窗口时称为多窗口服务系统；有时候在流水作业中，服务系统由若干个子系统串联组成，这样的系统称为串联系统。4.2 排队系统的模拟的算法4.2.1 离散事件模拟法变量和事件是排队系统最重要的因素。在模拟中我们紧盯某些变量。在模拟中有如下三种变量：(1) 时间变量：表示模拟所用的时间总量；(2) 计数变量：这些变量表示时刻t某时间出现的次数；(3) 系统状态变量：次变量描述系统在时刻t的状态。只要出现一个事件，上述变量的值就会出现改变或更新，我们就要找到相应感兴趣的数据作为输出。为确定下一个事件何时出现，我们需要一个事件列表（此列表给出后面最近的事件和这些事件出现的时间表）。只要出现一个事件我们就重置时间变量、状态变量、计数变量和收集相应的数据。这样我们就可以及时追踪随时间而变化的系统。4.2.2 单服务员排队系统在所模拟的排队模型中我们假设顾客到达时间服从泊松过程。当有且仅有一个服务员时，如果服务员空闲，到达的顾客可以得到及时的服务，而当服务员工作中时新来的顾客要排队等候服务。另外我们还假设服务员完成以为顾客的服务后转而服务下一个等候时间最长的顾客(这种服务称作：“先到先得”)；如果没有顾客排队等候他就空闲下来等候下一位顾客的到来。假设每一个顾客所需的服务时间是一个概率分布为G的随机变量，且独立于其他顾客的服务时间和到达时间。另外，假设时间T后下班，不再接受顾客进入系统，即使服务员已经完成了所有在T前进入的顾客的服务，其中T是一个固定值。我们将对该系统进行模拟，一般情况下单个收银系统满足如下假设：(a) 顾客的到达服务台是随机的，间隔时间服从泊松分布。(b) 对不同的顾客收款和装袋的时间服从泊松分布。系统变量和参数如下：(1)时间变量：t；(2)计数变量：，时间t到达的顾客数；，时间t离开的顾客数；(3)系统状态变量：n，时刻t时服务系统中的顾客数；(4)事件列表：，其中是时间是时间后下一个顾客的到达时间，是正在接受服务的顾客的离开时间。单服务员排队系统的模拟算法，见表4-1。表4-1单服务员排队系统的模拟算法1、当时生成，重新获取若,2、当时3、当如果,则重新取4、当4.2.2两个服务员排队系统现在考虑有两个服务员的排队系统。如果两个服务员均忙碌，则到达的顾客排队等候。如果服务员1空闲，则顾客接受服务员1的服务；如果服务员2空闲，则顾客接受服务员2的服务。当顾客得到服务后（无论是服务员1或者服务员2），则离开系统，且下一个等候时间最久的顾客接受服务。(1)时间变量：t(2)系统状态变量：，n表示系统中顾客人数，表示正在接受服务员1、2服务的顾客数。当系统为空时，若唯一的顾客j接受服务员1或2的服务时，相应的或(3)计数变量：，到时刻t到达的顾客数；，到时刻t由服务员j服务的顾客数（j=1,2）(4)输出变量：，顾客n的到达时间；，顾客n的离开时间(5)事件列表：表示下一个顾客的到达时间，表示服务员i对正在接受服务的顾客的服务时间(i=1,2)。如果服务员i空闲，则取。两服务员排队系统的模拟算法，见表4-2。表4-2两服务员排队系统的模拟算法初始化：取。取。生成并取情形1:,取取生成取收集输出数据如果：重新取生成，取如果：重新取生成并重新取如果重新取生成，取如果：重新取情形2：重新取重新取收集输出数据如果：重新取重新取如果：重新取重新取如果：记且重新取情形3：重新取重新取收集输出数据如果：重新取重新取如果：重新取重新取如果：记且重新取利用上述方法模拟此系统，且在某一事先给定的时间点停止模拟，则由输出变量和，的最终值可以得到每位顾客的到达和离开时间及每个服务员的服务人数。4.3排队系统的模拟4.3.1 单服务员排队系统在一个单服务员的服务站，顾客到达时间服从参数为的泊松分布，顾客所需的服务时间服从参数=10(分钟)的泊松分布。当的时候，该服务站一天(480分钟)每位顾客的在系统中的逗留时间如图4-2所示。该服务站一天的系统中的人数和等待时间如图4-3所示。图4-2 顾客的逗留时间图4-3 顾客的排队情况由于排队系统含有较大的随机性，为了降低这样的随机性给模拟带来的误差，我们采用多次模拟取平均值的方法。当分别取6、8、10、12、14(分钟)的时候，我们分别对各系统进行50次模拟实验并对相应结果去平均值。系统50次模拟的均值情况如表4-3所示。4.3.2 两服务员排队系统当系统有两个服务员(并联)时，我们假定当顾客到达而两个服务员都空闲的时候，固定由1号服务员提供服务。当到达时间取不同值的时候，系统各个变量又会如何改变呢。当分别取3、4、6、8、10分钟的时候，各个变量的变化如表4-4所示。表4-3 50次模拟均值对照表 顾客到达时间统计数据68101214顾客总人数79.359.747.239.633.8系统中人数16.87.52.71.61.3等待时间153.060.813.12.60.8顾客逗留时间163.0127.923.212.610.7加班时间318.270.824.37.04.2表4-4 50次模拟两服务员排队系统情况 顾客到达时间统计数据346810顾客总人数159.8119.580.659.647.8系统中人数22.29.22.11.41.1等待时间157.961.62.30.20.1加班时间326.8129.89.55.55.4顾客逗留时间167.971.712.310.210.14.4 小结本章主要介绍了单服务员排队系统和多服务员排队系统的模拟原理及算法。并给出了具体的模拟实验。第五章 总 结排队系统作为一种最典型的随机系统广泛的存在于实际生活之中。由于用传统实验验证这样的随机系统需要耗费大量的人力物力且难以达到很好的效果，我们就需要对相应的排队系统进行计算机模拟。无论是模拟什么样的排队系统都离不开各种随机变量的生成，例如顾客的到达时间和服务时间都是满足一定分布的随机变量。而所有的这些随机变量都基于0,1)上的均匀分布的随机数，它是整个随机模拟的基石。本文重点研究了伪随机数的模拟以及各种随机变量的生成，然后以此为基础利用离散事件模拟法在计算机平台上模拟了单服务员和两服务员的排队系统，并统计分析了模拟的结果。当然，本文模拟的排队系统还存在一些不足，如未能做出服务员人数大于二时的实验。这些都是要在今后的学习工作中不断改进的地方。南京工业大学本科生毕业设计（论文）参考文献1 盛骤,谢式千.概率论与数理统计M(第四版).北京:高等教育出版社,20082 祝东进.概率论与数理统计M. 北京：国防工业出版社,20103 陈明.信息与通信工程中的随机过程(第二版)M.北京：科学出版社,2005.4 Edward P.C.Kao.随机过程导论(英文版)M.北京：机械工业出版社,2003.5 Sheldon M.Ross.统计模拟M. 北京：人民邮电出版社，20