畢業(yè)設(shè)計--排隊(duì)系統(tǒng)的統(tǒng)計模擬實(shí)現(xiàn)

1、<p><b>　　畢業(yè)設(shè)計(論文)</b></p><p><b>　?。?010 年）</b></p><p>　　課題名稱 排隊(duì)系統(tǒng)的統(tǒng)計模擬實(shí)現(xiàn) </p><p>　　專業(yè)名稱 信息與計算科學(xué) </p><p>　　排隊(duì)系統(tǒng)的統(tǒng)計模擬

2、實(shí)現(xiàn)</p><p><b>　　摘 要</b></p><p>　　在現(xiàn)實(shí)生活中常需要在某些條件完全隨機(jī)的情況下對一件事情作出分析和決策。由于用傳統(tǒng)實(shí)驗(yàn)驗(yàn)證這樣的隨機(jī)系統(tǒng)需要耗費(fèi)大量的人力物力且難以達(dá)到很好的效果。為節(jié)省經(jīng)費(fèi)我們考慮采用計算機(jī)來對隨機(jī)系統(tǒng)進(jìn)行模擬。排隊(duì)系統(tǒng)作為一個典型的隨機(jī)系統(tǒng)廣泛的存在于生活中。用計算機(jī)模擬排隊(duì)系統(tǒng)可以降低系統(tǒng)的研究成本，提高系統(tǒng)

3、的試驗(yàn)效率。為管理人員對實(shí)際系統(tǒng)的運(yùn)營作出決策提供可靠的試驗(yàn)依據(jù)。</p><p>　　本文首先介紹了遞推生成偽隨機(jī)數(shù)的線性同余法，在此基礎(chǔ)上經(jīng)逆變換法生成滿足具體排隊(duì)系統(tǒng)相應(yīng)條件的隨機(jī)變量。然后利用離散事件模擬法介紹排隊(duì)系統(tǒng)的一些基礎(chǔ)理論模擬排隊(duì)系統(tǒng)。最后通過在計算機(jī)上編寫程序?qū)崿F(xiàn)了單服務(wù)員和多服務(wù)員情況下的排隊(duì)系統(tǒng)的模擬和比較。</p><p>　　關(guān)鍵詞：隨機(jī)變量 排隊(duì)系統(tǒng) 離散事件

4、模擬法</p><p><b>　　Abstract</b></p><p>　　In real life,we often need in some conditions completely random cases of one thing analysis and decision making. Due to the use of traditional e

5、xperimental 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 syste

6、m，queuing system widely exists in life. Using the computer simulation system of queuing system can reduce the cost, improve the system o</p><p>　　This paper firstly introduces the recursive generate pseudo r

7、andom 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 theo

8、retical queuing system simulation queuing system. Finally, through computer programming realized in the attendant and many waiter situation of simulation and comparison queuing system.</p><p><b>　　目 錄

9、</b></p><p><b>　　摘 要I</b></p><p>　　AbstractII</p><p>　　第一章 引 言1</p><p>　　1.1隨機(jī)變量的模擬1</p><p>　　1.2排隊(duì)系統(tǒng)的隨機(jī)模擬2</p><p>　

10、　1.3本文的內(nèi)容安排2</p><p>　　第二章 隨機(jī)數(shù)的產(chǎn)生3</p><p><b>　　2.1物理方法3</b></p><p>　　2.2計算機(jī)模擬3</p><p>　　2.3偽隨機(jī)數(shù)的應(yīng)用5</p><p><b>　　2.4 小結(jié)5</b><

11、;/p><p>　　第三章 隨機(jī)變量的模擬6</p><p><b>　　3.1逆變換法6</b></p><p>　　3.2連續(xù)隨機(jī)變量6</p><p>　　3.3離散隨機(jī)變量7</p><p><b>　　3.4小結(jié)8</b></p><p&g

12、t;　　第四章 排隊(duì)系統(tǒng)的統(tǒng)計模擬9</p><p>　　4.1 排隊(duì)系統(tǒng)的理論9</p><p>　　4.2 排隊(duì)系統(tǒng)的模擬的算法10</p><p>　　4.3排隊(duì)系統(tǒng)的模擬12</p><p><b>　　4.4 小結(jié)14</b></p><p>　　第五章 總 結(jié)15&l

13、t;/p><p><b>　　參考文獻(xiàn)16</b></p><p><b>　　致 謝17</b></p><p><b>　　第一章 引 言</b></p><p>　　在現(xiàn)實(shí)生活中常需要在某些條件完全隨機(jī)的情況下對一件事情作出分析和決策。由于用傳統(tǒng)實(shí)驗(yàn)驗(yàn)證這樣的隨機(jī)系

14、統(tǒng)需要耗費(fèi)大量的人力物力且難以達(dá)到很好的效果。為節(jié)省經(jīng)費(fèi)我們考慮采用計算機(jī)來對隨機(jī)系統(tǒng)進(jìn)行模擬。隨機(jī)系統(tǒng)的模擬是利用計算機(jī)上編寫的計算機(jī)程序語言模擬實(shí)際系統(tǒng)的行為。通過觀察和分析計算機(jī)模型系統(tǒng)的性能，從而掌握和了解實(shí)際系統(tǒng)的大致情況，并依此對實(shí)際系統(tǒng)作出分析和決策。</p><p>　　1.1隨機(jī)變量的模擬</p><p>　　隨機(jī)變量的模擬離不開[0,1)內(nèi)均勻分布隨機(jī)數(shù)的產(chǎn)生。真正的隨

15、機(jī)數(shù)只能由物理設(shè)備產(chǎn)生，由于其產(chǎn)生的效率過低，在實(shí)際應(yīng)用中我們采用計算機(jī)遞推產(chǎn)生的偽隨機(jī)數(shù)。偽隨機(jī)數(shù)并不是真正的隨機(jī)數(shù)，它雖然符合真隨機(jī)數(shù)的統(tǒng)計特征但實(shí)際上是一個周期序列。一種常用的產(chǎn)生隨機(jī)數(shù)的方法是：從初值出發(fā)，利用公式：</p><p><b>　　(1-1)</b></p><p>　　逐步計算，，其中和是給定的正整數(shù)。稱為一個偽隨機(jī)數(shù)，它近似服從[0,1)內(nèi)的

16、均勻分布。</p><p>　　在隨機(jī)變量的模擬中最常用的方法是逆變換法，它首先產(chǎn)生[0,1)內(nèi)均勻分布隨機(jī)數(shù)，再通過計算分布函數(shù)的反函數(shù)得到所要的隨機(jī)數(shù)。設(shè)是[0,1)上均勻分布的隨機(jī)變量，可以證明對于任一分布函數(shù)，隨機(jī)變量</p><p><b>　　(1-2)</b></p><p>　　的分布函數(shù)為。逆變換法是一種很好的產(chǎn)生指數(shù)型隨機(jī)變

17、量的算法，因?yàn)槟芎芸斓贸鲋笖?shù)型變量的分布函數(shù)的反函數(shù)。但是對某些隨機(jī)變量，其分布函數(shù)的反函數(shù)很難或不可能顯式地表出，無法直接應(yīng)用逆變換法，因此我們考慮采用其他的算法。</p><p>　　假設(shè)我們希望生成一個滿足概率分布為</p><p>　　, (1-3)</p><p>　　的離散隨機(jī)變量，為此，先生成一個隨機(jī)數(shù)U，

18、即U在[0,1）內(nèi)均勻分布，令：</p><p>　　，如果 ， (1-4)</p><p>　　則滿足所給隨機(jī)變量的分布。上述算法被稱為離散隨機(jī)變量的逆變換法。</p><p>　　1.2排隊(duì)系統(tǒng)的隨機(jī)模擬</p><p>　　排隊(duì)系統(tǒng)是各種隨機(jī)系統(tǒng)中最為典型的。計算機(jī)系統(tǒng)、通信系統(tǒng)和營業(yè)窗口系統(tǒng)都是典型的有形或者

19、無形的排隊(duì)系統(tǒng)。隨機(jī)模擬是求解排隊(duì)系統(tǒng)和分析排隊(duì)系統(tǒng)系能的非常有效的方法，它是用計算機(jī)程序直接建立真實(shí)系統(tǒng)的模型，通過計算機(jī)系統(tǒng)的隨機(jī)變化研究其行為的特征。</p><p>　　變量和事件是排隊(duì)系統(tǒng)最重要的因素。在模擬中我們緊盯某些變量。只要出現(xiàn)一個事件，上述變量的值就會出現(xiàn)改變或更新，我們就要找到相應(yīng)感興趣的數(shù)據(jù)作為輸出。為確定下一個事件何時出現(xiàn)，我們需要一個事件列表（此列表給出后面最近的事件和這些事件出現(xiàn)的時

20、間表）。只要出現(xiàn)一個事件我們就重置時間變量、狀態(tài)變量、計數(shù)變量和收集相應(yīng)的數(shù)據(jù)。這樣我們就可以及時追蹤隨時間而變化的系統(tǒng)。</p><p>　　1.3本文的內(nèi)容安排</p><p>　　本文將采用系統(tǒng)模擬方法對排隊(duì)系統(tǒng)進(jìn)行模擬。并統(tǒng)計不同情況下服務(wù)員人數(shù)安排及顧客排隊(duì)情況。第二章主要介紹[0,1)上均勻分布的偽隨機(jī)數(shù)產(chǎn)生方法。第三章主要介紹在產(chǎn)生了[0,1)上均勻分布的隨機(jī)數(shù)后以它為基石模

21、擬其他各種分布的隨機(jī)變量的方法。第四章主要介紹了排隊(duì)系統(tǒng)的基礎(chǔ)理論及離散事件模擬方法，并且對具體的排隊(duì)系統(tǒng)進(jìn)行模擬統(tǒng)計并討論實(shí)驗(yàn)結(jié)果。</p><p>　　第二章 隨機(jī)數(shù)的產(chǎn)生</p><p>　　當(dāng)要在計算機(jī)上模擬任何一個帶有隨機(jī)性的系統(tǒng)時，總離不開隨機(jī)數(shù)的生成，而在[0,1)上均勻分布的隨機(jī)數(shù)序列是最基本的隨機(jī)數(shù)序列，用它可以得到具有任何分布概率分布的隨機(jī)數(shù)序列。它是隨機(jī)模擬的基石。因

22、此，我們要討論如何產(chǎn)生合理的在[0,1)上均勻分布的隨機(jī)數(shù)序列。</p><p><b>　　2.1物理方法</b></p><p>　　隨機(jī)數(shù)最早是通過手工或機(jī)械的方式由手紡車擲骰子或洗紙牌的方式產(chǎn)生的。由于理論上[0,1)上有無窮多個數(shù)。這樣的物理方法并不能無窮多次的進(jìn)行下去，所以這樣的物理方法所能產(chǎn)生的隨機(jī)數(shù)其實(shí)是[0,1)上有限多個離散的有理數(shù)。因此完全精確的

23、產(chǎn)生[0,1)上均勻分布是隨機(jī)數(shù)是不可能的，在實(shí)際應(yīng)用中也是沒有意義的。設(shè)序列</p><p><b>　　(2-1)</b></p><p>　　為物理設(shè)備所能產(chǎn)生的[0,1)內(nèi)的一串等間隔分布的有理數(shù)序（即等差數(shù)列）。如果n充分大，則該數(shù)列在[0,1)內(nèi)充分“稠密”。因此，問題的本質(zhì)在生成一個等概率分布的離散隨機(jī)數(shù)集。如果這一件事能夠辦到，則它可以看作[0,1)上

24、均勻分布的隨機(jī)數(shù)的一個近似。</p><p>　　實(shí)際上，可以取，若能生成上的等概率分布，則將上述整數(shù)等概率隨機(jī)變量除以n即能得到所需[0,1)上均勻分布隨機(jī)數(shù)序。較常見的一種辦法有：取則內(nèi)的任何一個數(shù)都可以用一個相應(yīng)的m位二進(jìn)制數(shù)表示。該二進(jìn)制數(shù)每一位取0或者1。只要等概率的生成0和1就可以得到一個概率的m位2進(jìn)制數(shù)。最直接的可以用擲硬幣的方法等概率地產(chǎn)生0或1。</p><p>　　這

25、樣的方法能夠較完美的產(chǎn)生[0,1)上均勻分布的隨機(jī)數(shù)序，但由于實(shí)驗(yàn)次數(shù)過多，產(chǎn)生隨機(jī)數(shù)的效率過慢，這一方法在實(shí)際模擬應(yīng)用中是不可取也是不適用的。</p><p><b>　　2.2計算機(jī)模擬</b></p><p>　　在實(shí)際應(yīng)用中常采用計算機(jī)模擬產(chǎn)生偽隨機(jī)數(shù)。盡管作為數(shù)列的偽隨機(jī)數(shù)是由機(jī)器產(chǎn)生的，但他們具有[0,1)上均勻分布獨(dú)立隨機(jī)變量的一切特征。</p&g

26、t;<p>　　一種最常用產(chǎn)生偽隨機(jī)數(shù)的方法是：從初值(也稱為種子)出發(fā)，利用公式</p><p><b>　　(2-2)</b></p><p>　　逐步計算，，其中和是給定的正整數(shù)，上式表示為被除后的余數(shù)。于是每一個均為中的一個，稱為一個偽隨機(jī)數(shù)，它近似服從[0,1)上的均勻分布。</p><p>　　由上式產(chǎn)生隨機(jī)數(shù)的方法稱

27、為乘同余法。由于每一個均取值中的一個，故若干次后(至多次)所產(chǎn)生的隨機(jī)數(shù)必定重復(fù)，且自此之后整個序列也開始重復(fù)。于是，我們在選擇常數(shù)和時，希望對任一初值，在重復(fù)出現(xiàn)前所產(chǎn)生的隨機(jī)數(shù)序列足夠長。</p><p>　　一般的，在選取常數(shù)和時應(yīng)遵循如下原則：</p><p>　　(1) 對于任一初值，產(chǎn)生的序列具有[0,1)上均勻分布獨(dú)立隨機(jī)變量的特征。</p><p>

28、　　(2) 對已任一初值，在重復(fù)出現(xiàn)前產(chǎn)生的隨機(jī)數(shù)序列足夠長。</p><p>　　(3) 每一數(shù)值均可由計算機(jī)有效計算。</p><p>　　為滿足上述三個條件，可選一個符合計算機(jī)字長要求的較大素數(shù)作為。對于32位計算機(jī)(其中第一個字節(jié)為正負(fù)號)，已經(jīng)證明和</p><p><b>　　符合上述要求。</b></p><p

29、>　　由上述乘同余法產(chǎn)生偽隨機(jī)數(shù)時，分別取：</p><p><b>　　；；</b></p><p><b>　　所得到的序列：</b></p><p>　　從上可以看出，當(dāng)能整除時，最后的序列必定會收斂到零。當(dāng)不能整除時，則所得的序列是周期序列，且最大周期是。由此可以看出，遞推方法計算出來的偽隨機(jī)數(shù)序列實(shí)際上是周

30、期序列，而非真正的隨機(jī)序列。事實(shí)上當(dāng)取得非常大的時候在模擬中只需取其一個周期即可，這樣的偽隨機(jī)數(shù)序列滿足均勻分布獨(dú)立隨機(jī)變量的一切特征。由上述乘同余法模擬的1000個在[0,1)上服從均勻分布的偽隨機(jī)數(shù)的結(jié)果，如圖2-1所示。</p><p>　　另一個生成隨機(jī)數(shù)的方法是如下的遞推公式</p><p><b>　?。?-3）</b></p><p&

31、gt;　　由于它包含乘法和加法因此被稱為混合同余法。當(dāng)采用這種方法生成隨機(jī)數(shù)時，人們常取為計算機(jī)字長，這是由于這是因?yàn)檫@種取法易于非常有效的計算?；旌贤喾ㄊ浅送喾ê图油喾ǖ幕旌?，它產(chǎn)生的隨機(jī)數(shù)周期較大且統(tǒng)計特性較佳。</p><p>　　圖2-1 [0,1)上均勻分布的偽隨機(jī)數(shù)</p><p>　　2.3偽隨機(jī)數(shù)的應(yīng)用</p><p>　　設(shè)隨機(jī)向量(X,Y)

32、在中心為原點(diǎn)、面積為4的正方形上均勻分布，則在這個正方形里畫其內(nèi)切圓，如果我們大量的在正方形里生成隨機(jī)點(diǎn)(X,Y)?？梢宰C明這些點(diǎn)落在內(nèi)切圓內(nèi)的概率等于，即</p><p><b>　　(2-4)</b></p><p>　　設(shè)U是[0,1)上的均勻分布，則2U是在[0,2)上的均勻分布。2U-1在[-1,1)上均勻分布。因此我們生成2個隨機(jī)數(shù)令，我們可以如此估計：先

33、生成大量隨機(jī)數(shù)對，之后用滿足的隨機(jī)數(shù)對的比例來估計。以上算法由計算機(jī)模擬得到的結(jié)果是：，可以看到與準(zhǔn)確值相差不多。</p><p><b>　　2.4 小結(jié)</b></p><p>　　本章介紹了隨機(jī)數(shù)的產(chǎn)生原理和方法，并給出了隨機(jī)數(shù)的一個簡單應(yīng)用。</p><p>　　第三章 隨機(jī)變量的模擬</p><p>　　用計算

34、機(jī)模擬任何一個隨機(jī)現(xiàn)象時必然涉及一個給定概率分布的隨機(jī)變量。例如，在模擬排隊(duì)系統(tǒng)時，顧客的到達(dá)時間和服務(wù)時間都是滿足一定分布的隨機(jī)變量。一旦這些隨機(jī)變量所滿足的概率分布函數(shù)被選定，則必須有生成該給定概率分布的隨機(jī)變量的算法，才能在計算機(jī)內(nèi)得到這樣的隨機(jī)變量。而所有的這些方法都基于[0,1)上的均勻分布的隨機(jī)變量。</p><p><b>　　3.1逆變換法</b></p>&l

35、t;p>　　逆變換法（也稱反演法或變換法）是在隨機(jī)變量的模擬中最常用的方法。它首先產(chǎn)生[0,1)內(nèi)均勻分布隨機(jī)數(shù)，再通過計算分布函數(shù)的反函數(shù)得到所需要的隨機(jī)變量。</p><p>　　命題3.1 設(shè)是[0,1)上均勻分布的隨機(jī)數(shù)，則對于任一分布函數(shù)，隨機(jī)變量</p><p><b>　　(3-1)</b></p><p><b>

36、;　　的分布函數(shù)為。</b></p><p>　　證明：以記的分布函數(shù)，則</p><p>　　由于是一分布函數(shù)，故它是的單調(diào)遞增函數(shù)，且不等式“”等價于不等式“”。于是有</p><p>　　因?yàn)?，且在[0,1)上均勻分布。</p><p><b>　　3.2連續(xù)隨機(jī)變量</b></p>&l

37、t;p>　　由逆變換法可知，對于連續(xù)隨機(jī)變量的具體算法是：首先產(chǎn)生均勻分布的隨機(jī)數(shù)，取即可。例如X是參數(shù)為1的指數(shù)型隨機(jī)變量，其分布函數(shù)為，如果設(shè)，則</p><p><b>　　(3-2)</b></p><p>　　于是參數(shù)1的指數(shù)分布的隨機(jī)變量可由下式產(chǎn)生</p><p><b>　　(3-3)</b><

38、/p><p>　　用計算機(jī)模擬的10000個參數(shù)為1的指數(shù)分布的隨機(jī)變數(shù)，如圖3-1所示。</p><p>　　圖3-1指數(shù)型隨機(jī)變量的模擬</p><p>　　利用逆變換法可以模擬隨機(jī)變量，但由于某些隨機(jī)變量分布函數(shù)的反函數(shù)很難或不可能顯式地表出，無法直接應(yīng)用逆變換法。因此我們考慮采用其他的算法，例如拒絕法、極坐標(biāo)法等。</p><p><

39、;b>　　3.3離散隨機(jī)變量</b></p><p>　　假設(shè)我們希望生成一個概率分布函數(shù)為</p><p>　　， (3-4)</p><p>　　的離散隨機(jī)變量X。為此，首先生成一個[0,1)上均勻分布隨機(jī)數(shù)U，且令</p><p><b>　　(3-5)</b>

40、</p><p>　　對于，由于，故我們有</p><p><b>　　(3-6)</b></p><p>　　所以的值滿足分布要求。離散隨機(jī)變量模擬算法如下</p><p>　　(1)生成一個隨機(jī)數(shù);</p><p>　　(2)如果則令停止;</p><p><b&

41、gt;　　如果，則令停止;</b></p><p><b>　　如果則令停止;</b></p><p>　　說明：(1) 如果，是由小到大排列，即，且以記的分布函數(shù)，則，如果，則等于換言之，當(dāng)生成一個隨機(jī)數(shù)后，我們是通過是否落在區(qū)間來確定的值(或等價的通過求的逆)?；诖?，上述方法被稱為離散的逆變換法。</p><p>　　(2)

42、用上述方法來生成一個離散隨機(jī)變量所需的時間與我們要搜索的區(qū)間個數(shù)成正比，于是有必要以的降序排列的取值。這樣就可以大大的節(jié)省區(qū)間搜索所耗費(fèi)的時間。實(shí)際上當(dāng)所求的隨機(jī)變量為離散均勻隨機(jī)變量時，上述區(qū)間搜索時不必要的。用計算機(jī)模擬10000個參數(shù)為5的泊松分布隨機(jī)數(shù)，如圖3-2所示。</p><p>　　圖3-2泊松分布隨機(jī)數(shù)</p><p><b>　　3.4小結(jié)</b>

43、</p><p>　　本章介紹了計算機(jī)模擬隨機(jī)變量的基本原理和算法，并給出了模擬的例子。</p><p>　　第四章 排隊(duì)系統(tǒng)的統(tǒng)計模擬</p><p>　　排隊(duì)問題廣泛的存在于實(shí)際生活之中，當(dāng)一個顧客到達(dá)請求服務(wù)時，服務(wù)資源常常被其他顧客所占用，因此必須讓需要服務(wù)的顧客按一定規(guī)則進(jìn)行排隊(duì)，然后按次序?qū)︻櫩瓦M(jìn)行服務(wù)，這就構(gòu)成了一個排隊(duì)系統(tǒng)。用計算機(jī)模擬排隊(duì)系統(tǒng)可以降

44、低系統(tǒng)的研究成本，提高系統(tǒng)的試驗(yàn)效率。為管理人員對實(shí)際系統(tǒng)的運(yùn)營作出決策提供可靠的試驗(yàn)依據(jù)。</p><p>　　4.1 排隊(duì)系統(tǒng)的理論</p><p>　　一個排隊(duì)系統(tǒng)主要由這四個基本要素組成：顧客到達(dá)過程、排隊(duì)規(guī)則、服務(wù)時間、服務(wù)系統(tǒng)的結(jié)構(gòu)，如圖4-1所示。</p><p>　　圖4-1排隊(duì)系統(tǒng)的結(jié)構(gòu)</p><p>　　顧客到達(dá)過程描

45、述顧客的到達(dá)規(guī)律。設(shè)在時刻顧客到達(dá)，則稱到達(dá)時點(diǎn)。隨機(jī)變量稱為到達(dá)間隔，若是獨(dú)立分布的則稱E()為平均到達(dá)間隔。通常顧客的到達(dá)規(guī)律是Poisson到達(dá)。</p><p>　　所謂的排隊(duì)規(guī)則是指從等待服務(wù)的用戶中規(guī)定用戶進(jìn)入服務(wù)的次序。常見的規(guī)則有：先來先服務(wù)、后來先服務(wù)、隨機(jī)選擇服務(wù)、優(yōu)先權(quán)服務(wù)、批量服務(wù)等。設(shè)第i個顧客等待時間為，則也是一個隨機(jī)變量序列。</p><p>　　服務(wù)時間是指

46、服務(wù)員對顧客服務(wù)所消耗的時間。設(shè)服務(wù)員對第i個顧客的服務(wù)所用時間為，則是一個隨機(jī)變量序列。若該序列是獨(dú)立分布的則它的期望E()是平均服務(wù)時間。當(dāng)獨(dú)立同分布的的概率分布同樣滿足一定的概率分布，例如Poisson分布、指數(shù)分布等。</p><p>　　服務(wù)系統(tǒng)的結(jié)構(gòu)是以服務(wù)窗口的數(shù)目而言。當(dāng)只有一個窗口時，稱為單窗口服務(wù)系統(tǒng)；有多個窗口時稱為多窗口服務(wù)系統(tǒng)；有時候在流水作業(yè)中，服務(wù)系統(tǒng)由若干個子系統(tǒng)串聯(lián)組成，這樣的系

47、統(tǒng)稱為串聯(lián)系統(tǒng)。</p><p>　　4.2 排隊(duì)系統(tǒng)的模擬的算法</p><p>　　4.2.1 離散事件模擬法</p><p>　　變量和事件是排隊(duì)系統(tǒng)最重要的因素。在模擬中我們緊盯某些變量。在模擬中有如下三種變量：</p><p>　　(1) 時間變量：表示模擬所用的時間總量；</p><p>　　(2) 計數(shù)

48、變量：這些變量表示時刻t某時間出現(xiàn)的次數(shù)；</p><p>　　(3) 系統(tǒng)狀態(tài)變量：次變量描述系統(tǒng)在時刻t的狀態(tài)。</p><p>　　只要出現(xiàn)一個事件，上述變量的值就會出現(xiàn)改變或更新，我們就要找到相應(yīng)感興趣的數(shù)據(jù)作為輸出。為確定下一個事件何時出現(xiàn)，我們需要一個事件列表（此列表給出后面最近的事件和這些事件出現(xiàn)的時間表）。只要出現(xiàn)一個事件我們就重置時間變量、狀態(tài)變量、計數(shù)變量和收集相應(yīng)的數(shù)

49、據(jù)。這樣我們就可以及時追蹤隨時間而變化的系統(tǒng)。</p><p>　　4.2.2 單服務(wù)員排隊(duì)系統(tǒng)</p><p>　　在所模擬的排隊(duì)模型中我們假設(shè)顧客到達(dá)時間服從泊松過程。當(dāng)有且僅有一個服務(wù)員時，如果服務(wù)員空閑，到達(dá)的顧客可以得到及時的服務(wù)，而當(dāng)服務(wù)員工作中時新來的顧客要排隊(duì)等候服務(wù)。另外我們還假設(shè)服務(wù)員完成以為顧客的服務(wù)后轉(zhuǎn)而服務(wù)下一個等候時間最長的顧客(這種服務(wù)稱作：“先到先得”)；如

50、果沒有顧客排隊(duì)等候他就空閑下來等候下一位顧客的到來。假設(shè)每一個顧客所需的服務(wù)時間是一個概率分布為G的隨機(jī)變量，且獨(dú)立于其他顧客的服務(wù)時間和到達(dá)時間。另外，假設(shè)時間T后下班，不再接受顧客進(jìn)入系統(tǒng)，即使服務(wù)員已經(jīng)完成了所有在T前進(jìn)入的顧客的服務(wù)，其中T是一個固定值。</p><p>　　我們將對該系統(tǒng)進(jìn)行模擬，一般情況下單個收銀系統(tǒng)滿足如下假設(shè)：</p><p>　　(a) 顧客的到達(dá)服務(wù)臺是

51、隨機(jī)的，間隔時間服從泊松分布。</p><p>　　(b) 對不同的顧客收款和裝袋的時間服從泊松分布。</p><p>　　系統(tǒng)變量和參數(shù)如下：</p><p>　　(1)時間變量：t；</p><p>　　(2)計數(shù)變量：，時間t到達(dá)的顧客數(shù)；，時間t離開的顧客數(shù)；</p><p>　　(3)系統(tǒng)狀態(tài)變量：n，時刻t

52、時服務(wù)系統(tǒng)中的顧客數(shù)；</p><p>　　(4)事件列表：，，其中是時間是時間后下一個顧客的到達(dá)時間，是正在接受服務(wù)的顧客的離開時間。</p><p>　　單服務(wù)員排隊(duì)系統(tǒng)的模擬算法，見表4-1。</p><p>　　表4-1單服務(wù)員排隊(duì)系統(tǒng)的模擬算法</p><p>　　4.2.2兩個服務(wù)員排隊(duì)系統(tǒng)</p><p>

53、;　　現(xiàn)在考慮有兩個服務(wù)員的排隊(duì)系統(tǒng)。如果兩個服務(wù)員均忙碌，則到達(dá)的顧客排隊(duì)等候。如果服務(wù)員1空閑，則顧客接受服務(wù)員1的服務(wù)；如果服務(wù)員2空閑，則顧客接受服務(wù)員2的服務(wù)。當(dāng)顧客得到服務(wù)后（無論是服務(wù)員1或者服務(wù)員2），則離開系統(tǒng)，且下一個等候時間最久的顧客接受服務(wù)。</p><p><b>　　(1)時間變量：t</b></p><p>　　(2)系統(tǒng)狀態(tài)變量：，n表

54、示系統(tǒng)中顧客人數(shù)，表示正在接受服務(wù)員1、2服務(wù)的顧客數(shù)。當(dāng)系統(tǒng)為空時，，若唯一的顧客j接受服務(wù)員1或2的服務(wù)時，相應(yīng)的或</p><p>　　(3)計數(shù)變量：，到時刻t到達(dá)的顧客數(shù)；，到時刻t由服務(wù)員j服務(wù)的顧客數(shù)（j=1,2）</p><p>　　(4)輸出變量：，顧客n的到達(dá)時間；，顧客n的離開時間</p><p>　　(5)事件列表：表示下一個顧客的到達(dá)時間，

55、表示服務(wù)員i對正在接受服務(wù)的顧客的服務(wù)時間(i=1,2)。如果服務(wù)員i空閑，則取。</p><p>　　兩服務(wù)員排隊(duì)系統(tǒng)的模擬算法，見表4-2。</p><p>　　表4-2兩服務(wù)員排隊(duì)系統(tǒng)的模擬算法</p><p>　　利用上述方法模擬此系統(tǒng)，且在某一事先給定的時間點(diǎn)停止模擬，則由輸出變量和，的最終值可以得到每位顧客的到達(dá)和離開時間及每個服務(wù)員的服務(wù)人數(shù)。<

56、/p><p>　　4.3排隊(duì)系統(tǒng)的模擬</p><p>　　4.3.1 單服務(wù)員排隊(duì)系統(tǒng)</p><p>　　在一個單服務(wù)員的服務(wù)站，顧客到達(dá)時間服從參數(shù)為的泊松分布，顧客所需的服務(wù)時間服從參數(shù)=10(分鐘)的泊松分布。當(dāng)?shù)臅r候，該服務(wù)站一天(480分鐘)每位顧客的在系統(tǒng)中的逗留時間如圖4-2所示。該服務(wù)站一天的系統(tǒng)中的人數(shù)和等待時間如圖4-3所示。</p>

57、<p>　　圖4-2 顧客的逗留時間</p><p>　　圖4-3 顧客的排隊(duì)情況</p><p>　　由于排隊(duì)系統(tǒng)含有較大的隨機(jī)性，為了降低這樣的隨機(jī)性給模擬帶來的誤差，我們采用多次模擬取平均值的方法。當(dāng)分別取6、8、10、12、14(分鐘)的時候，我們分別對各系統(tǒng)進(jìn)行50次模擬實(shí)驗(yàn)并對相應(yīng)結(jié)果去平均值。系統(tǒng)50次模擬的均值情況如表4-3所示。</p><

58、;p>　　4.3.2 兩服務(wù)員排隊(duì)系統(tǒng)</p><p>　　當(dāng)系統(tǒng)有兩個服務(wù)員(并聯(lián))時，我們假定當(dāng)顧客到達(dá)而兩個服務(wù)員都空閑的時候，固定由1號服務(wù)員提供服務(wù)。當(dāng)?shù)竭_(dá)時間取不同值的時候，系統(tǒng)各個變量又會如何改變呢。當(dāng)分別取3、4、6、8、10分鐘的時候，各個變量的變化如表4-4所示。</p><p>　　表4-3 50次模擬均值對照表</p><p>　　表4

59、-4 50次模擬兩服務(wù)員排隊(duì)系統(tǒng)情況</p><p><b>　　4.4 小結(jié)</b></p><p>　　本章主要介紹了單服務(wù)員排隊(duì)系統(tǒng)和多服務(wù)員排隊(duì)系統(tǒng)的模擬原理及算法。并給出了具體的模擬實(shí)驗(yàn)。</p><p><b>　　第五章 總 結(jié)</b></p><p>　　排隊(duì)系統(tǒng)作為一種最典型的隨

60、機(jī)系統(tǒng)廣泛的存在于實(shí)際生活之中。由于用傳統(tǒng)實(shí)驗(yàn)驗(yàn)證這樣的隨機(jī)系統(tǒng)需要耗費(fèi)大量的人力物力且難以達(dá)到很好的效果，我們就需要對相應(yīng)的排隊(duì)系統(tǒng)進(jìn)行計算機(jī)模擬。無論是模擬什么樣的排隊(duì)系統(tǒng)都離不開各種隨機(jī)變量的生成，例如顧客的到達(dá)時間和服務(wù)時間都是滿足一定分布的隨機(jī)變量。而所有的這些隨機(jī)變量都基于[0,1)上的均勻分布的隨機(jī)數(shù)，它是整個隨機(jī)模擬的基石。</p><p>　　本文重點(diǎn)研究了偽隨機(jī)數(shù)的模擬以及各種隨機(jī)變量的生成，

61、然后以此為基礎(chǔ)利用離散事件模擬法在計算機(jī)平臺上模擬了單服務(wù)員和兩服務(wù)員的排隊(duì)系統(tǒng)，并統(tǒng)計分析了模擬的結(jié)果。</p><p>　　當(dāng)然，本文模擬的排隊(duì)系統(tǒng)還存在一些不足，如未能做出服務(wù)員人數(shù)大于二時的實(shí)驗(yàn)。這些都是要在今后的學(xué)習(xí)工作中不斷改進(jìn)的地方。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 盛驟,謝式千.概率論與

62、數(shù)理統(tǒng)計[M](第四版).北京:高等教育出版社,2008</p><p>　　[2] 祝東進(jìn).概率論與數(shù)理統(tǒng)計[M]. 北京：國防工業(yè)出版社,2010</p><p>　　[3] 陳明.信息與通信工程中的隨機(jī)過程(第二版)[M].北京：科學(xué)出版社,2005.</p><p>　　[4] Edward P.C.Kao.隨機(jī)過程導(dǎo)論(英文版)[M].北京：機(jī)械工業(yè)出版社

63、,2003.</p><p>　　[5] Sheldon M.Ross.統(tǒng)計模擬[M]. 北京：人民郵電出版社，2007.</p><p>　　[6] 林國順,等.模擬隨機(jī)數(shù)統(tǒng)計性質(zhì)比較[J]. 數(shù)理統(tǒng)計與管理,2000,02,08-11</p><p>　　[7] 朱林生,等,單人服務(wù)排隊(duì)系統(tǒng)的模擬結(jié)果分析[J]. 東北電力學(xué)院學(xué)報, 1999,19(1),91~

64、95</p><p>　　[8] 方德斌,等,服務(wù)系統(tǒng)中的排隊(duì)問題[J].科技創(chuàng)業(yè),2008,02(5),56~60</p><p>　　[9] 何建東,等,排隊(duì)系統(tǒng)的計算機(jī)模擬[J]. 科技信息,2010(2),88~90</p><p>　　[10] 朱軍,等.排隊(duì)系統(tǒng)的仿真及應(yīng)用[J] .微機(jī)發(fā)展,2002(3),46~48</p><p&

65、gt;　　[11] 連宏,等,離散時間排隊(duì)系統(tǒng)的計算機(jī)仿真[J] .儀器儀表用戶,2007,14(2),92~93</p><p>　　[12] 李重.一類復(fù)雜循環(huán)排隊(duì)系統(tǒng)的計算機(jī)模擬及其在進(jìn)程調(diào)度中的應(yīng)用[J].浙江大學(xué)學(xué)報,2004,31(2),143~147</p><p>　　[13] Haahr, Mads. "Introduction to Randomness an

66、d Random Numbers". http://random.org/randomness/. Retrieved 2009-04-08.</p><p>　　[14] Halprin, Ran; Naor, Moni (PDF). Games for Extracting Randomness. Department of Computer Science and Applied Mathemat

67、ics, Weizmann Institute of Science. http://www.neko.co.il/games4rand.pdf. Retrieved 2009-06-27.</p><p>　　[15] http://en.wikipedia.org/wiki/Queueing_theory.</p><p>　　[16] http://en.wikipedia.org/