數(shù)學建模論文蒙特卡羅的多服務臺和單服務臺排隊系統(tǒng)

1、課程名稱：數(shù)學建模與數(shù)學實驗學 院： 專 業(yè)： 姓 名：學 號: 指導老師：利用方法模擬單服務臺排隊系統(tǒng)和多服務臺排隊系統(tǒng)摘 要蒙特卡羅方法（Monte Carlo）又稱統(tǒng)計模擬法隨機抽樣技術，是一種隨機模擬方法，以概率和統(tǒng)計理論方法為基礎的一種計算方法，是使用隨機數(shù)（或更常見的偽隨機數(shù)）來解決很多計算問題的方法。將所求解的問題同一定的概率模型相聯(lián)系，用電子計算機實現(xiàn)統(tǒng)計模擬或抽樣，以獲得問題的近似解。本文通過兩個具體的服務機構為例，分別說明如何利用蒙特卡洛方法模擬單服務臺排隊系統(tǒng)和多服務臺排隊系統(tǒng)。單服務臺排隊系統(tǒng)（排隊模型之港口系統(tǒng)）：通過排隊論和蒙特卡洛方法解決了生產(chǎn)系統(tǒng)的效率問題，通過

2、對工具到達時間和服務時間的計算機擬合，將基本模型確定在排隊模型，通過對此基本模型的分析和改進，在概率論相關理論的基礎之上使用計算機模擬仿真（蒙特卡洛法）對生產(chǎn)系統(tǒng)的整個運行過程進行模擬，得出最后的結論。多服務臺排隊系統(tǒng)（開水供應模型）：為了解決水房打水時的擁擠問題。根據(jù)相關數(shù)據(jù)和假設推導，最終建立了多服務窗排隊M/G/n模型，用極大似然估計和排隊論等方法對其進行了求解，并用Matlab軟件對數(shù)據(jù)進行了處理和繪圖。用靈敏度分析對結果進行了驗證。本模型比較完美地解決了水房排隊擁擠問題，而且經(jīng)過簡單的修改，它可以用于很多類似的排隊問題。 關鍵詞：蒙特卡洛方法，排隊論，擬合優(yōu)度，泊松流，靈敏度分析。一

3、、問題重述港口排隊系統(tǒng)：一個帶有船只卸貨設備的小港口，任何時間僅能為一艘船只卸貨。船只進港是為了卸貨，響鈴兩艘船到達的時間間隔在15分鐘到145分鐘變化。一艘船只卸貨的時間有所卸貨物的類型決定，在15分鐘到90分鐘之間變化。開水供應系統(tǒng)：學院開水房的供水時間有限，水房面積有限，水管易受水垢堵塞。根據(jù)調(diào)查數(shù)據(jù)可知：通暢時幾乎無人排隊，堵塞時水房十分擁擠。由此可以看出水房設計存在問題，我們可以把開水房看成是一個隨即服務系統(tǒng)，應用排隊論的方法對系統(tǒng)運行狀態(tài)做定量的描述。二、基本假設港口排隊系統(tǒng)：通過對問題的重述，那么，每艘船只在港口的平均時間和最長時間是多少？若一艘船只的等待時間是從到達到開始卸貨的

4、時間，每艘船只的平均等待時間和最長等待時間是多少？卸貨設備空閑時間的百分比是多少？船只排隊最長的長度是多少？開水供應系統(tǒng)：假設、顧客流滿足參數(shù)為的Poisson分布，其中為單位時間到達的顧客平均數(shù)。每個顧客所需的服務時間相互獨立，顧客流是無限的，在觀測期間平穩(wěn)。假設、排隊方式為單一隊列的等候制，先到先服務。雖然水房內(nèi)有多個服務臺，每個服務臺都有自己的隊列，但同時顧客總是自由轉移到最短的隊列上，不可能出現(xiàn)有顧客排隊而服務器空閑的情況。本文最后對兩種排隊方式的比較也表明這一假設是合理的。假設、水房共有20個并聯(lián)的服務臺（水龍頭），設每個服務臺的服務時間服從某個相同的分布，t和分別是服務時間的均值和

5、均方差，=/ t為偏離系數(shù)。由于鍋爐及輸水管容量的限制，使t依賴于正在進行服務的水龍頭個數(shù)m，設此時平均服務時間t(m)。且存在一臨界值 當m<= m0 時，t(m)為常數(shù)t0;m>m0時，管道中的水便分給 m 個龍頭流出，從而 t(m)> t0,且 t(m)是 m 的單增函數(shù)。 假設、污垢的積累與時間成線性變化，設為f(x)=kT(k>0,表示污垢積累速率；T為距上次清理污垢時間間隔。假設、單位時間為 10 秒。顯然，假設、都是合理的，對假設 進行擬合優(yōu)度檢驗，得出假設也是合理的。三、符號約定開水供應系統(tǒng)用到的符號和參數(shù)：L 系統(tǒng)內(nèi)顧客數(shù)的期望值；Lq系統(tǒng)內(nèi)排隊顧客數(shù)

6、的數(shù)學期望；W 顧客在系統(tǒng)內(nèi)的平均逗留時間；Wq顧客排隊等待時間的期望；P0系統(tǒng)內(nèi)有服務臺空閑的概率；=t /n 系統(tǒng)的服務強度（即用水龍頭的程度）；n 水龍頭的個數(shù)。Wq的上限值Po的上限值四、問題分析港口排隊系統(tǒng)：排隊論：排隊論(Queuing Theory) ，是研究系統(tǒng)隨機聚散現(xiàn)象和隨機服務系統(tǒng)工作過程的數(shù)學理論和方法，又稱隨機服務系統(tǒng)理論，為運籌學的一個分支。本題研究的是生產(chǎn)系統(tǒng)的效率問題，可以將磨損的工具認為顧客，將打磨機當做服務系統(tǒng)。：較為經(jīng)典的一種排隊論模式，按照前面的Kendall記號定義，前面的M代表顧客(工具)到達時間服從泊松分布，后面的M則表示服務時間服從負指數(shù)分布，1

7、為僅有一個打磨機。排隊論研究的基本問題1.排隊系統(tǒng)的統(tǒng)計推斷:即判斷一個給定的排隊系統(tǒng)符合于哪種模型，以便根據(jù)排隊理論進行研究。 2.系統(tǒng)性態(tài)問題:即研究各種排隊系統(tǒng)的概率規(guī)律性，主要研究隊長分布、等待時間分布和忙期分布等統(tǒng)計指標,包括了瞬態(tài)和穩(wěn)態(tài)兩種情形。3.最優(yōu)化問題：即包括最優(yōu)設計(靜態(tài)優(yōu)化)，最優(yōu)運營（動態(tài)優(yōu)化）。為了得到一些合理的答案，利用計算器或可編程計算器來模擬港口的活動。假定相鄰兩艘船到達的時間間隔和每艘船只卸貨的時間區(qū)間分布，加入兩艘船到達的時間間隔可以是15到145之間的任何數(shù)，且這個區(qū)間內(nèi)的任何整數(shù)等可能的出現(xiàn)。再給出模擬這個系統(tǒng)的一般算法之間，考慮有5艘傳至的假象情況。

8、對每艘船只有以下數(shù)據(jù)：船1船2船3船4船5相鄰兩艘船到達的時間間隔20301512025卸貨時間5545607580因為船1在時鐘于t=0分鐘計時開始后20分鐘到達，所以港口卸貨設備在開始時空空閑了20分鐘。船1立即開始卸貨，卸貨用時55分，其間，船2在時鐘開始計時后t=20+30=50分中到達。在船1與t=20+55=75分鐘卸貨完畢之前，船2不能開始卸貨，這意味著船2在卸貨前必須等待75-50=25分鐘。在船2開始卸貨之前，船2于t=50+15=65分鐘到達，因為船2在t=75分鐘開始卸貨，并且卸貨需45分鐘，所以在船2與t=75+45=120分鐘卸貨完畢之前，船3不能開始卸貨。這樣，船3

9、必須等待120分鐘。船4在t=65+120=185分鐘之前沒有到達，因此船3已經(jīng)在t=120+60=180分鐘卸貨完畢，港口卸貨設備空閑185-180=5分鐘，并且，船4到達后立即卸貨。最后，在船4于t=185+75=260分鐘卸貨完畢之前，船5在t=185+25=210到達，于是船5在開始卸貨前等待260-210=50分鐘。五、模型的建立和求解港口排隊系統(tǒng)：對于問題中存在的服務系統(tǒng)，建立排隊論模型，在僅能為一艘船通過是一個標準的模型：所謂模型，就是輸入過程為泊松流時，服務時間為任意的條件之下的，服務機器只有一個得時候。對于模型，服務時間T的分布式一般的，（但是要求期望值和方差都存在），其他條

10、件和標準的型相同。為了達到穩(wěn)態(tài)還是必要的，其中有。單服務臺單隊系統(tǒng) 船只到達進入隊列服務臺接受服務船只離去單服務員的排隊模型設：（1） 船只到來間隔時間服從參數(shù)為0.1的指數(shù)分布（2） 對船只的服務時間服從，上的均勻分布（3） 排隊按先到先服務規(guī)則，隊長無限制系統(tǒng)的假設：（1） 船只源是無窮的；（2） 排隊的長度沒有限制；（3） 到達系統(tǒng)的船只按先后順序依次進入服務， 即“先到先服務”。符號說明 w：總等待時間；ci：第i個顧客的到達時刻；bi：第i個顧客開始服務時刻；ei：第i個顧客服務結束時刻；xi：第i-1個顧客與第i個顧客之間到達的間隔時間；yi：對第i個顧客的服務時間ci=ci-1+

11、 xiei=bi+yibi=max(ci,ei-1)模擬框圖初始化：令i=1，ei-1=0，w=0產(chǎn)生間隔時間隨機數(shù)xi參數(shù)為0.1的指數(shù)分布ci=xi , bi=xi 產(chǎn)生服務時間隨機數(shù)yi4,15的均勻分布ei=bi+yi累計等待時間：w=w+bi-ci準備下一次服務：i=i+1產(chǎn)生間隔時間隨機數(shù)xi參數(shù)為0.1的指數(shù)分布ci=ci-1+ xi 確定開始服務時間：bi=max(ci,ei-1)bi480YNi=i-1,t=w/i輸出結果：完成服務個數(shù)：m=i 平均等待時間：t 停止開水供應模型：由假設、可知，若 nm0時,則 n 個服務臺是相互獨立，服從相同分布，即是一個 M/G/n 型排

12、隊模型。如果n>m0則相當于服務臺之間可以相互幫助的服務系統(tǒng)，平均服務時間 t 為正在服務的服務臺數(shù) m 的函數(shù)。考慮一簡單情形：當 m £m0時，t(m)=t0;當 m0 m n 時，t(m)= mm0t0，此時 m個服務員以m0mt0的速率進行服務，但總的服務速率總是m0t0，因此多出的服務臺對系統(tǒng)運行狀態(tài)是沒有影響的，即n>m0時的系統(tǒng)實際相當于M/G/m0的排隊模型。首先得求出臨界服務臺數(shù)m0 ,設水龍頭及輸出管直徑分別為d1,d2;水的流速為v,從而由m0的含義知： 1 4m0d12v=14d22v （1-2）即m0=d22d12 。由實際估測， d1=6.5c

13、m, d2=1.3cm.于是m0>20=n,因此現(xiàn)有的水房系統(tǒng)服從M/G/20的排隊模型。 p0=i=0n-1(t)2i!+(t)2n!(1-)-1; （1-3） P0=1-1n!1-(t)np0; （1-4） Lq=1-1n!1-(t)np01+22 ; （1-5） Wq=Lq； （1-6）L=Lq+n； （1-7）Wq=L/. （1-8）另外公式中要求r<1,否則系統(tǒng)永遠不能到穩(wěn)定狀態(tài)，排隊的人越來越多，即隊長將趨于無窮大。對水房系統(tǒng)，l=2.17,n=20, 當管道通暢時，t1=7.58,1=3.45, r=0.8224<1 代入解出:Lq0.292, L=14.97,

14、 Wq=0.134,W=0.134, P0=0.945可見此時水房內(nèi)為由15人，而水龍頭有20個，面積有10平方米，幾乎無人排隊，不會產(chǎn)生擁擠現(xiàn)象。這與我觀察的實際情況相符。根據(jù)假設 ，水垢的積累與時間成線性遞增變化，f(x)=kT。隨著水垢的積累，服務時間相應增加。那么處于水房通暢和爆滿這兩個極端狀態(tài)之間的水房運營情況又如何呢?下面的模型當t2=12.10時,r>1,水房爆滿，進一步分析以了解擁擠情況，擁擠原因以及緩解的辦法。六、模型的檢驗與評價港口排隊系統(tǒng)：表1 100艘船港口和系統(tǒng)的模擬結果一艘船呆在港口的平均時間977978818599一艘船呆在港口的最長時間1741211111

15、41140159一艘船的平均等待時間238591224一艘船的最長等待時間994633646893卸貨設備空閑時間的百分比0.0670.0790.0930.070.0690.028上圖為一艘船呆在港口的平均時間上圖為一艘船呆在港口的最長時間一艘船的平均等待時間上圖為一艘船的最長等待時間上圖為一艘船的最長等待時間以上就是對港口問題的具體分析，其實港口問題還可以從船只的排隊角度出發(fā)，我們還可以對多個港口通行做相應的模擬試驗，讓船主盡量減少等待時間且港口卸貨設備的利用率達到最高，從而是港口的主人獲得更大的利潤。從排隊角度來解決問題，可以使問題的廣度增加，選秘書問題就是一個很典型的例子，可以從排隊角度

16、解決，如果用我在文章中應用的方法來解決也是可以的， 這僅僅是一個港口的小問題，甚至可以說是一個非常簡單的問題，但是已經(jīng)讓我感覺到了數(shù)學的美，在老師的引導下慢慢接近一種抽象的美，在寫論文的這幾天中，數(shù)據(jù)的整理和分析是最值得享受的時刻，在Excel里輸入自己的數(shù)據(jù)，是一種忐忑的感覺，因為在那么多的數(shù)據(jù)面前，我真的不知道將會發(fā)生什么，擬合的過程就更是有意思了，一次一次的嘗試，一次一次的比較，在這個過程中，如果有一點點的進步都會讓我興奮，數(shù)學建模在生活中處處存在，如果真的能夠掌握這個本領，生活一定會變得簡單而精彩！開水供應系統(tǒng)：一、靈敏度分析：由公式（1-3）、（1-4）、（1-5）和（1-8）知，直

17、接影響系統(tǒng)各運行指標的參數(shù)是n,，t,其中為不可控的參數(shù)，在分析中可以看成不變。 首先，我們討論Lq、Po和服務時間t之間的關系。已知服務臺數(shù)n=20,=2.17,=0.5281均是不變的。用Matlab繪出圖1.如下：圖1由上圖可以看出，當服務時間t>8時，隨服務時間的增加，系統(tǒng)的排隊顧客迅速增長，而服務臺的空閑率Po快速下降。由此可見，該水房在大部分時間不擁擠，服務臺利用率較小，與實際觀察相符合。接著，我們繼續(xù)討論服務強度與Lq、Po之間的關系。已知t=7.56,.作出圖形變化趨勢圖2，如下：圖2 服務臺數(shù)目n對Lq、Po的影響 由上圖可知，當服務臺很少時（n<m0），將會產(chǎn)生

18、擁擠現(xiàn)象。當服務臺個數(shù)足夠多時，增加服務臺數(shù)量，對于縮短平均等待隊長效果不明顯。二、系統(tǒng)的最優(yōu)化：上面我們只討論了服務時間t、服務臺數(shù)量n與系統(tǒng)內(nèi)排隊顧客數(shù)學期望Lq、系統(tǒng)內(nèi)服務臺的空閑概率Po之間的關系，但是對于固定的m0,存在Po和Lq之間的合理分配問題，顧客流大時，Po較小，Lq較大。由于沒有給出Lq和Po的相關數(shù)據(jù)，不能找到Lq和Po的最優(yōu)解?，F(xiàn)在的另外一種方法是:在兩種互相矛盾的度量（平均等待時間Wq和服務臺空閑概率P0)之間取折中值，即對Wq和P0規(guī)定上限值a和b。現(xiàn)在討論系統(tǒng)服務臺空閑率Po、顧客排隊等待時間Wq和服務臺數(shù)n之間的關系。假設a=0.6,b=0.4,服務時間t1=7

19、.58,t2=12.10得到圖3、圖4，如下：圖3圖4從上圖可知，最優(yōu)服務臺數(shù)在t1=7.58與t2=12.10兩種情況下分別為：n1 =18, n2=28。因為顧客到達率在不同時段內(nèi)是不一樣的，所以我們還得繼續(xù)討論如何安排顧客流問題， 如果假定系統(tǒng)中 n 個隊列間沒有顧客轉移，則每個隊列平均到達率為l / n ，從而成為 n 個 M/G/1 系統(tǒng)，平均服務時間 t 不變，l=0.1，仍利用原公式計算得到多隊時系統(tǒng)的運行指標。得到表 4，如下： 表4 運行指標 服務時間 排隊方式L=7.58單隊0.29416.970.1340.945多對1.43×2048.414.30.998=12

20、.10單隊32.7354.3715.30.089多對35.35（每個子系統(tǒng)）799.0（整個子系統(tǒng)）353.50.307從上表可以看出，單隊時等待隊長、等待時間都比多隊時低，而服務臺的利用率都比多隊時高因而具有明顯優(yōu)越性，因此建立一個大水房明顯優(yōu)于建立多個小水房。參考文獻：（1）運籌學教材編寫組編. 運籌學. 北京：清華大學出版社，2008（2）Jerry Banks，John S.Carson，Barry L Nelson 等著. 離散事件系統(tǒng)仿真.北京：機械工業(yè)出版社，2007（3）排隊論模型與蒙特卡洛仿真（4）茆詩松 周紀薌. 概率論與數(shù)理統(tǒng)計. 北京：中國統(tǒng)計出版社. 2007 （5）

21、張德豐 等. MATLAB概率與數(shù)理統(tǒng)計分析. 北京：機械工業(yè)出版社. 2010（6）姜啟源 謝金星. 數(shù)學建模案例選集. 北京：高等教育出版社. 2006（7）楊啟帆.數(shù)學建模案例集. 北京：高等教育出版社. 2006附錄：港口排隊模型：編程如下：clearcs=100;for j=1:cs w(j)=0; i=1;x(i)=exprnd(10);c(i)=x(i);b(i)=x(i);while b(i)<=480 y(i)=unifrnd(4,15); e(i)=b(i)+y(i); w(j)=w(j)+b(i)-c(i); i=i+1; x(i)=exprnd(10); c(i)

22、=c(i-1)+x(i); b(i)=max(c(i),e(i-1); endi=i-1;t(j)=w(j)/i;m(j)=i;endpt=0;pm=0;for j=1:cs pt=pt+t(j); pm=pm+m(j);endpt=pt/cspm=pm/cs附錄二排隊論中一個感興趣的問題時，當輸入過程是Possion流時，顧客相繼到達的間隔時間T服從什么規(guī)律。定理：設是具有參數(shù)的泊松過程，即是對應的時間間隔序列，則隨機變量是獨立同分布的，且服從均值為的負指數(shù)分布，即 。證明 因為是Possion過程中第一個顧客到達的時間，所以時間等價于內(nèi)沒有顧客到達。故，進而可得所以是服從均值為的負指數(shù)分布

23、。1、利用Possion過程的獨立、平穩(wěn)增量性質(zhì)，得即，故也是服從均值為的負指數(shù)分布。2、 對于任意的和有即 ，所以對任一，它都服從均值為的負指數(shù)分布。證畢。開水供應系統(tǒng)：MATLAB程序：1: 顧客到達率 l的極大似然估計程序：x0=zeros(1,66); x1=ones(1,132); x2=2.*ones(1,131); x3=3.*ones(1,110); x4=4.*ones(1,50); x5=5.*ones(1,22); x6=6.*ones(1,10); x7=7.*ones(1,4); x8=8.*ones(1,3); x=x0,x1,x2,x3,x4,x5,x6,x7,x

24、8; Lambdahat,Lambdaci=poissfit(x,0.05)結果為 ：Lambdahat =2.1705 Lambdaci = 2.0448，2.2961 即：l =2.172: 在管道暢通時，服務時間的均值和樣本標準差程序：clear all;x=30 35 35 40 40 40 45 45 50 50 55 60 60 60 . 65 65 65 65 65 65 65 65 65 70 70 70 70 . 75 75 75 75 75 80 80 80 85 85 85 85 85 95 95 95 95 105 105 . 125 125 155 245; x1=m

25、ean(x) x2=std(x)結果為 ：x1 =75.8000， x2 =34.48403: 在管道堵塞時，服務時間的均值和樣本標準差程序：clear all;x=30 30 40 45 45 45 55 55 55 65 65 70 70 70 75 75 . 75 75 80 85 90 95 95 95 95 100 105 105 110 110 . 125 130 130 130 135 135 140 140 145 145 155 155 . 160 175 185 185 190 200 205 205 215 240 255 . 265 300;x3=mean(x) x4=

26、std(x)結果為 ：x3 = 120.9091， x4 = 63.85814：Lq、Po和服務時間t之間的關系的程序：t=0:0.1:10;c=20; s1=1; s2=0; b=0.5281;x=2.17*t;p=x./c ; %p為服務強度。x為(t)d=1; for m=1:19 d=m*d; s1=x.2/d+s1;end c1=20*d; s2=x.2/c1/(1-p); s=s1+s2; p0=1./s ;x1=x.20; %(t22) x2=p0.*x1 ;n=1/c1./(1-p); P0=(1-n.*x2); %P0的表達式；j1=1./(1-p); j2=p.*j1; b

27、1=(1+b2)/2;Lq=j2.*n.*x2*b1;plot(x,P0),axis(0,14,0,1)hold on;plot(x,Lq,'*'),axis(0,14,0,1.3)legend('Lq和服務時間t的關系','P0和服務時間t的關系',0)5：t1=7.58時系統(tǒng)服務臺空閑率Po、顧客排隊等待時間Wq和服務臺數(shù)n的關系的程序：clear all;x=16.445; a=2.17;c=16:1:25 ;s1=1; s2=0; b=0.5281; for i=1:10 p(i)=x/c(i); end for i=1:10 s1(i)=1; d(