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

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

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

3、的試驗(yàn)效率。為管理人員對(duì)實(shí)際系統(tǒng)的運(yùn)營(yíng)作出決策提供可靠的試驗(yàn)依據(jù)。</p><p>　　本文首先介紹了遞推生成偽隨機(jī)數(shù)的線性同余法，在此基礎(chǔ)上經(jīng)逆變換法生成滿足具體排隊(duì)系統(tǒng)相應(yīng)條件的隨機(jī)變量。然后利用離散事件模擬法介紹排隊(duì)系統(tǒng)的一些基礎(chǔ)理論模擬排隊(duì)系統(tǒng)。最后通過(guò)在計(jì)算機(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ì)算機(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)計(jì)模擬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ī)的情況下對(duì)一件事情作出分析和決策。由于用傳統(tǒng)實(shí)驗(yàn)驗(yàn)證這樣的隨機(jī)系

14、統(tǒng)需要耗費(fèi)大量的人力物力且難以達(dá)到很好的效果。為節(jié)省經(jīng)費(fèi)我們考慮采用計(jì)算機(jī)來(lái)對(duì)隨機(jī)系統(tǒng)進(jìn)行模擬。隨機(jī)系統(tǒng)的模擬是利用計(jì)算機(jī)上編寫的計(jì)算機(jī)程序語(yǔ)言模擬實(shí)際系統(tǒng)的行為。通過(guò)觀察和分析計(jì)算機(jī)模型系統(tǒng)的性能，從而掌握和了解實(shí)際系統(tǒng)的大致情況，并依此對(duì)實(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)生的效率過(guò)低，在實(shí)際應(yīng)用中我們采用計(jì)算機(jī)遞推產(chǎn)生的偽隨機(jī)數(shù)。偽隨機(jī)數(shù)并不是真正的隨機(jī)數(shù)，它雖然符合真隨機(jī)數(shù)的統(tǒng)計(jì)特征但實(shí)際上是一個(gè)周期序列。一種常用的產(chǎn)生隨機(jī)數(shù)的方法是：從初值出發(fā)，利用公式：</p><p><b>　　(1-1)</b></p><p>　　逐步計(jì)算，，其中和是給定的正整數(shù)。稱為一個(gè)偽隨機(jī)數(shù)，它近似服從[0,1)內(nèi)的

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

17、量的算法，因?yàn)槟芎芸斓贸鲋笖?shù)型變量的分布函數(shù)的反函數(shù)。但是對(duì)某些隨機(jī)變量，其分布函數(shù)的反函數(shù)很難或不可能顯式地表出，無(wú)法直接應(yīng)用逆變換法，因此我們考慮采用其他的算法。</p><p>　　假設(shè)我們希望生成一個(gè)滿足概率分布為</p><p>　　, (1-3)</p><p>　　的離散隨機(jī)變量，為此，先生成一個(gè)隨機(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ì)算機(jī)系統(tǒng)、通信系統(tǒng)和營(yíng)業(yè)窗口系統(tǒng)都是典型的有形或者

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

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

21、擬其他各種分布的隨機(jī)變量的方法。第四章主要介紹了排隊(duì)系統(tǒng)的基礎(chǔ)理論及離散事件模擬方法，并且對(duì)具體的排隊(duì)系統(tǒng)進(jìn)行模擬統(tǒng)計(jì)并討論實(shí)驗(yàn)結(jié)果。</p><p>　　第二章 隨機(jī)數(shù)的產(chǎn)生</p><p>　　當(dāng)要在計(jì)算機(jī)上模擬任何一個(gè)帶有隨機(jī)性的系統(tǒng)時(shí)，總離不開隨機(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ù)最早是通過(guò)手工或機(jī)械的方式由手紡車擲骰子或洗紙牌的方式產(chǎn)生的。由于理論上[0,1)上有無(wú)窮多個(gè)數(shù)。這樣的物理方法并不能無(wú)窮多次的進(jìn)行下去，所以這樣的物理方法所能產(chǎn)生的隨機(jī)數(shù)其實(shí)是[0,1)上有限多個(gè)離散的有理數(shù)。因此完全精確的

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

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

25、樣的方法能夠較完美的產(chǎn)生[0,1)上均勻分布的隨機(jī)數(shù)序，但由于實(shí)驗(yàn)次數(shù)過(guò)多，產(chǎn)生隨機(jī)數(shù)的效率過(guò)慢，這一方法在實(shí)際模擬應(yīng)用中是不可取也是不適用的。</p><p><b>　　2.2計(jì)算機(jī)模擬</b></p><p>　　在實(shí)際應(yīng)用中常采用計(jì)算機(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>　　逐步計(jì)算，，其中和是給定的正整數(shù)，上式表示為被除后的余數(shù)。于是每一個(gè)均為中的一個(gè)，稱為一個(gè)偽隨機(jī)數(shù)，它近似服從[0,1)上的均勻分布。</p><p>　　由上式產(chǎn)生隨機(jī)數(shù)的方法稱

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

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

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

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

31、gt;　　由于它包含乘法和加法因此被稱為混合同余法。當(dāng)采用這種方法生成隨機(jī)數(shù)時(shí)，人們常取為計(jì)算機(jī)字長(zhǎng)，這是由于這是因?yàn)檫@種取法易于非常有效的計(jì)算?；旌贤喾ㄊ浅送喾ê图油喾ǖ幕旌?，它產(chǎn)生的隨機(jī)數(shù)周期較大且統(tǒng)計(jì)特性較佳。</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的正方形上均勻分布，則在這個(gè)正方形里畫其內(nèi)切圓，如果我們大量的在正方形里生成隨機(jī)點(diǎn)(X,Y)。可以證明這些點(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個(gè)隨機(jī)數(shù)令，我們可以如此估計(jì)：先

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

34、機(jī)模擬任何一個(gè)隨機(jī)現(xiàn)象時(shí)必然涉及一個(gè)給定概率分布的隨機(jī)變量。例如，在模擬排隊(duì)系統(tǒng)時(shí)，顧客的到達(dá)時(shí)間和服務(wù)時(shí)間都是滿足一定分布的隨機(jī)變量。一旦這些隨機(jī)變量所滿足的概率分布函數(shù)被選定，則必須有生成該給定概率分布的隨機(jī)變量的算法，才能在計(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ù)，再通過(guò)計(jì)算分布函數(shù)的反函數(shù)得到所需要的隨機(jī)變量。</p><p>　　命題3.1 設(shè)是[0,1)上均勻分布的隨機(jī)數(shù)，則對(duì)于任一分布函數(shù)，隨機(jī)變量</p><p><b>　　(3-1)</b></p><p><b>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

55、表示服務(wù)員i對(duì)正在接受服務(wù)的顧客的服務(wù)時(shí)間(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)，且在某一事先給定的時(shí)間點(diǎn)停止模擬，則由輸出變量和，的最終值可以得到每位顧客的到達(dá)和離開時(shí)間及每個(gè)服務(wù)員的服務(wù)人數(shù)。<

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

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

58、;p>　　4.3.2 兩服務(wù)員排隊(duì)系統(tǒng)</p><p>　　當(dāng)系統(tǒng)有兩個(gè)服務(wù)員(并聯(lián))時(shí)，我們假定當(dāng)顧客到達(dá)而兩個(gè)服務(wù)員都空閑的時(shí)候，固定由1號(hào)服務(wù)員提供服務(wù)。當(dāng)?shù)竭_(dá)時(shí)間取不同值的時(shí)候，系統(tǒng)各個(gè)變量又會(huì)如何改變呢。當(dāng)分別取3、4、6、8、10分鐘的時(shí)候，各個(gè)變量的變化如表4-4所示。</p><p>　　表4-3 50次模擬均值對(duì)照表</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á)到很好的效果，我們就需要對(duì)相應(yīng)的排隊(duì)系統(tǒng)進(jìn)行計(jì)算機(jī)模擬。無(wú)論是模擬什么樣的排隊(duì)系統(tǒng)都離不開各種隨機(jī)變量的生成，例如顧客的到達(dá)時(shí)間和服務(wù)時(shí)間都是滿足一定分布的隨機(jī)變量。而所有的這些隨機(jī)變量都基于[0,1)上的均勻分布的隨機(jī)數(shù)，它是整個(gè)隨機(jī)模擬的基石。</p><p>　　本文重點(diǎn)研究了偽隨機(jī)數(shù)的模擬以及各種隨機(jī)變量的生成，

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

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

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

64、95</p><p>　　[8] 方德斌,等,服務(wù)系統(tǒng)中的排隊(duì)問(wèn)題[J].科技創(chuàng)業(yè),2008,02(5),56~60</p><p>　　[9] 何建東,等,排隊(duì)系統(tǒng)的計(jì)算機(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] 連宏,等,離散時(shí)間排隊(duì)系統(tǒng)的計(jì)算機(jī)仿真[J] .儀器儀表用戶,2007,14(2),92~93</p><p>　　[12] 李重.一類復(fù)雜循環(huán)排隊(duì)系統(tǒng)的計(jì)算機(jī)模擬及其在進(jìn)程調(diào)度中的應(yīng)用[J].浙江大學(xué)學(xué)報(bào),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/