陳杰東

(廣東輕工職業(yè)技術(shù)學院，廣東 廣州 510300)

?

蒙特卡羅方法在求解單服務(wù)臺排隊系統(tǒng)中的應(yīng)用

陳杰東

(廣東輕工職業(yè)技術(shù)學院，廣東 廣州 510300)

摘要：隨機模擬方法是一種具有獨特風格的廣義的數(shù)值計算方法，同時也是求解實際問題近數(shù)值解的一種方法。應(yīng)用該方法來解決單服務(wù)臺排隊系統(tǒng)的實際問題，具有一定的實用性。

關(guān)鍵詞：模擬；模擬方法；蒙特卡羅方法

在實際生活中，我們經(jīng)常遇到這樣的情況：如在一個理發(fā)店中，顧客到店中時有理發(fā)師正閑著，可隨時為顧客服務(wù)，有時理發(fā)師正處于工作狀態(tài)，則顧客需要等待，由于顧客到來時間是隨機的，我們關(guān)心的不是每個顧客各需等待多少時間，而是顧客平均等待時間，這樣可以提高理發(fā)師的服務(wù)效率，我們這里研究的是這類問題中最簡單的一種，即單服臺排隊系統(tǒng)，也就是考慮只有一個服務(wù)員的情況。

1背景闡述

1777年法國學者蒲豐提出用投針試驗求圓周率π的問題。給出模型：在平面上畫一些間距均為 的平行線，向此平面隨機地投擲一枚長針l(l

由于該問題實際操作較麻煩，我們可以用統(tǒng)計模擬試驗方法來代替。

(1)產(chǎn)生隨機數(shù)，首先產(chǎn)生相互獨立的隨機變量X，φ的抽樣序列：{xi,(i=1,……,N)}，其中X～U(0, /2)，φ～U(0,π)。

由此問題可看出，用蒙特卡羅方法求實際問題的基本步驟為：

2隨機數(shù)的產(chǎn)生

用隨機模擬方法解決實際問題時，首先要解決的是隨機數(shù)的產(chǎn)生方法，或者稱隨機變量的抽樣方法，這里重點介紹[0，1] 區(qū)間上均勻分布隨機數(shù)的產(chǎn)生和檢驗方法。雖然區(qū)間[0，1] 上均勻分布是最簡單的連續(xù)分布，但產(chǎn)生大量相互獨立的U(0，1)隨機數(shù)對用隨機模擬方法解決實際問題是至關(guān)重要的；同時很多其他形式的分布(如正態(tài)分布，指數(shù)分布等)的隨機數(shù)都可以用U(0，1)隨機數(shù)經(jīng)變換得到。下面給出產(chǎn)生區(qū)間(a,b)上均勻分布的隨機數(shù)的具體算法。

若連續(xù)型隨機變量x的概率密度函數(shù)

則稱x為(a,b)上均勻分布隨機變量，其采樣值稱為滿足均勻分布的隨機數(shù)，它是這樣產(chǎn)生的：首先，由給定的初值x0，按xn+1=5xn產(chǎn)生(0，1)上的均勻分布的隨機數(shù)ξ；然后，由x=a+ξ(b-a)產(chǎn)生(a,b)上的均勻分布隨機數(shù)。

過程標識符和形式參數(shù)表UDR1(a,b,x0,n) ；a,b區(qū)間的左、右端點；x0形成隨機數(shù)的初值；n所使用機器的二進制尾數(shù)的長度。第一次調(diào)用本過程時，x0應(yīng)是小于MN=2↑(n-5)的正奇數(shù)，以后再調(diào)用時，x0置零。

例如：相繼產(chǎn)生(-1，1)區(qū)間上的500個和1000個均勻分布隨機數(shù)，取x0=312657863，計算結(jié)果是：

點數(shù)N5001000均值Mx=∑Ni=1xi/N-0.00130.0247方差Dx=∑Ni=1(x-Mx)2/N0.34550.3325

3蒙特卡羅方法求解單服務(wù)臺排隊系統(tǒng)

按照莆豐實驗的思路，應(yīng)用蒙特卡羅方法來解決引言所提出的實際問題，這里研究的是這類問題中最簡單的一種模型，即單服臺排隊系統(tǒng)，也就是考慮只有一個服務(wù)員的情況，仍以理發(fā)師這個例子來看一下此類問題，給出流程：

第一步：收集數(shù)據(jù)，在實地調(diào)查，并收集和處理調(diào)查數(shù)據(jù)，即記錄每個顧客到達時刻，等待時間及服務(wù)時間等。在這里，可以通過計算機模擬產(chǎn)生隨機數(shù)來代替這一類過程。

第二步：構(gòu)造模擬模型。在此模型中，有兩個輸入的因素：顧客的到達間隔時間和服務(wù)時間排隊規(guī)則是按先到先服務(wù)的次序接受服務(wù)，服務(wù)機構(gòu)只有一個，即一個服務(wù)員每次只能為一個顧客服務(wù)。

第三步：模擬試驗。我們模擬的模型包含時間因素，即我們要模擬的是服務(wù)系統(tǒng)在8小時工作時間內(nèi)的運行情況，這類模型也稱為動態(tài)模型。并給出記錄模擬時間當前值的變量——模擬時鐘及模擬時間的推進原則，推進原則有兩種，即下次事件推進原則和均勻間隔(模擬步長)推進原則。

下面就單服務(wù)臺排隊系統(tǒng)的模擬試驗，引入幾個記號：

記UDR1— 第i個顧客到達時刻(x0=0)

Ti=xi-xi-1：第i-1個顧客至第i個

顧客的到達時間間隔

C4：第i個顧客接受服務(wù)的時間

Di：第i個顧客的排隊等待時間

Ci=Xi+Si+Di：第i個顧客接受服務(wù)后離開的時刻。

顧客到達

排隊等待

接受服務(wù)

顧客離開

假設(shè)服務(wù)機構(gòu)上午8點開門服務(wù)(如理發(fā)店8點上班)，模擬時鐘從T=0開始。產(chǎn)生指數(shù)分布e(0,1)隨機數(shù)，比如得10，13，8，15…。T=10min時，第一個顧客到達，因沒有人排隊馬上接受服務(wù)，即 =0min；服務(wù)時間s～U(10，15)，產(chǎn)生均勻隨機數(shù)s，比如得11，13，14，12，…；第一個顧客接受服務(wù)時間為11min，計算C1=(10+11+0)min=21min，即第一個顧客于開門后21min離開(即T=21min時離開)。第二個顧客是T=23min=(10+13)min時到達，因第一位顧客已被服務(wù)完畢離開了，不必等待，D2=0min，服務(wù)時間S1=13min，第二個顧客于C2=(23+13+0)min=36min離開。第三個顧客到達時間X3=31min=(10+13+8)min，時鐘T=31min的時候，第二個顧客正在接受服務(wù)，故第三位先排隊等待時間S3=14min，第三位離開時刻C3=(31+14+5)min=50min；第四位到達時刻X4=(10+13+8+11)min=42min；等待時間D4=(50-42)min=8min，服務(wù)時間S4=12min，離開時刻C4=(42+12+8)min=62min；…表中列出模擬試驗的部分結(jié)果。

表1　單服務(wù)員系統(tǒng)的模擬過程

如果改變輸入?yún)?shù)，比如提高服務(wù)效率，服務(wù)員的提高了，服務(wù)時間s～U(5，10)，那么等待時間E(D)必然會減少，增加服務(wù)人員，同樣也可以減少等待時間。

4小結(jié)

以上介紹了用隨機模擬方法解決單服務(wù)臺排隊系統(tǒng)問題的方法。從解決此類問題的過程中我們可以看到隨機模擬方法具有應(yīng)用面廣，適用性強，算法簡單等優(yōu)點，尤其用于處理計算量較大的問題，更可以發(fā)揮隨機模擬方法的優(yōu)勢。但因為模擬結(jié)果具有隨機性，且進精度較低，所以在求解精度較高的近似計算中就不宜采用隨機模擬方法。

參考文獻：

[1]R.Y．Rubinstein.SimulationandtheMonteCarlomethod[M].Wiley，1981.

[2]W.Metropolis,S.Ulam.MonteCarlomethod[M].J.Amer.Statass,1949.

[3]徐仲濟.蒙特卡羅方法[M].上海：上?？茖W出版社,1985.

[4]吳國富.實用數(shù)據(jù)分析方法[M].北京：中國統(tǒng)計出版社,1992.

[5]徐萃薇.計算方法引論[M].廣州：高等教育出版社,1985.

Application of Monte Carlo Method to Solving the Problem of Single-server Queuing System

CHEN Jiedong

(Guangdong Industry Technical College，Guangzhou 510300，China)

Abstract:Stochastic Simulation is a unique style of broad numerical calculation method ,it is also practical problems for nearly a numerical solution method. Using the method to resolve single-server queuing system problems has a certain practicality.

Key words:simulation; analogy method; Monte Carlo method

中圖分類號：0026

文獻標識碼：A

文章編號：1672-1950(2016)01-0009-03

作者簡介：陳杰東(1980—)，男，碩士，講師。

收稿日期：2015-12-18