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

陳杰東

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

?

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

陳杰東

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

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

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

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

1背景闡述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下面就單服務(wù)臺(tái)排隊(duì)系統(tǒng)的模擬試驗(yàn)，引入幾個(gè)記號(hào)：

記UDR1— 第i個(gè)顧客到達(dá)時(shí)刻(x0=0)

Ti=xi-xi-1：第i-1個(gè)顧客至第i個(gè)

顧客的到達(dá)時(shí)間間隔

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

Di：第i個(gè)顧客的排隊(duì)等待時(shí)間

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

顧客到達(dá)

排隊(duì)等待

接受服務(wù)

顧客離開

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

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

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

4小結(jié)

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

參考文獻(xiàn)：

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

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

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

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

[5]徐萃薇.計(jì)算方法引論[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

中圖分類號(hào)：0026

文獻(xiàn)標(biāo)識(shí)碼：A

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

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

收稿日期：2015-12-18