蒙特卡洛介紹

王健華交通運輸工程

蒙特卡洛

MonteCarlo蒙特卡洛的基本思想及產(chǎn)生蒙特卡洛的方法基礎(chǔ)用蒙特卡洛方法解∏用蒙特卡洛方法解決食堂排隊問題目錄蒙特卡洛方法的優(yōu)缺點及發(fā)展蒙特卡洛的基本思想及產(chǎn)生

MC方法亦稱為隨機模擬方法，有時也稱為隨機抽樣實驗方法。他的基本思想是，為了求解數(shù)學、物理、工程技術(shù)以及生產(chǎn)管理方面的問題，首先建立一個概率模型或隨機過程，使它的參數(shù)等于隨機問題的解；然后通過對模型或者過程的觀察或抽樣實驗來計算所求參數(shù)的統(tǒng)計特征，最后給出所求解的近似值。蒙特卡洛的基本思想及產(chǎn)生假設(shè)所要求的x是隨機變量的數(shù)學期望，那么近似確定x的方法是對進行N次重復抽樣，產(chǎn)生相互獨立的值的序列，并計算其算術(shù)平均值：根據(jù)克爾莫格羅夫加強大數(shù)定理有：因此，當N充分大時，成立的概率為1，亦即可以用作為所求量x的估計值。蒙特卡洛的基本思想及產(chǎn)生

MC理論依據(jù):均勻分布的算術(shù)平均收斂于真值(大數(shù)法則)

置信水平下的統(tǒng)計誤差(中心極限)MC方法可以解決的問題：

確定性的數(shù)學問題，如計算多重積分，求逆矩，解線性方程組等。隨機性問題，如中子在介質(zhì)中的擴散等。蒙特卡洛的基本思想及產(chǎn)生MC方法的定名和系統(tǒng)的發(fā)展約始于二十世紀四十年代，它的名字來源于摩納哥蒙特卡洛城市的名字，但如果從方法特征的角度來說，可以一直追溯到十九世紀后半葉的蒲豐隨機投針實驗，即所謂的蒲豐問題。蒙特卡洛的方法基礎(chǔ)進行計算機模擬需要大樣本的均勻分布隨機數(shù)數(shù)列，如何獲得？偽隨機數(shù)的產(chǎn)生真隨機數(shù)：由隨機物理過程來產(chǎn)生，例如：放射性衰變、電子設(shè)備的熱噪音、宇宙射線的觸發(fā)時間等等偽隨機數(shù)：由計算機按遞推公式大量產(chǎn)生蒙特卡洛的方法基礎(chǔ)設(shè)為2s個數(shù)碼，自乘后，去頭截尾，然后相應的除以或，作為[0,1]上的偽隨機數(shù)，如此重復這一過程，直至或者為0，或者與已出現(xiàn)的數(shù)字重復（周期性）時為止。公式表示如下：偽隨機數(shù)的產(chǎn)生[x]表示不超過x的最大整數(shù)X=a(modM)表示x等于a被M除的余數(shù)蒙特卡洛的方法基礎(chǔ)例：十進制2s=4,并取=6406，

則=6406，=41036836，

而

即為410368/的余數(shù)，

所以，

如此重復，則有

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

蒙特卡洛的方法基礎(chǔ)蒙特卡洛的方法基礎(chǔ)偽隨機數(shù)的產(chǎn)生自開始出現(xiàn)周期，故序列長度（從初值到發(fā)生周期或退化前，序列中的偽隨機數(shù)的個數(shù)）為20。結(jié)論蒙特卡洛的方法基礎(chǔ)偽隨機數(shù)的檢驗均勻性檢驗:[0,1]分成k個相等子區(qū)間，進行N次抽樣，投入各子區(qū)間如均勻,則各區(qū)間落入數(shù)Ni應為

Ni可視為(m，s)的一組無關(guān)樣本測量，服從則(k)蒙特卡洛的方法基礎(chǔ)獨立性檢驗:

即xi與xi+1的前后無關(guān)性[0,1]上進行2N次抽樣，分成兩個序列在XY平面內(nèi)劃分k×k方格，如獨立,則各格內(nèi)落入數(shù)應為則服從c2分布滿足以上統(tǒng)計性檢驗的遞推抽樣序列，可視為[0,1]均勻分布偽隨機數(shù)蒙特卡洛的方法基礎(chǔ)隨機變量的抽樣直接抽樣法：求分布函數(shù)則令例對指數(shù)分布的直接抽樣蒙特卡洛的方法基礎(chǔ)例對指數(shù)分布的直接抽樣積分得到分布函數(shù)令則指數(shù)分布的隨機變量抽樣為蒙特卡洛方法與Matlab結(jié)合蒙特卡洛方法與VisualBasic結(jié)合蒙特卡洛方法與Excel結(jié)合蒙特卡洛方法解∏蒲豐投針試驗

1777年,法國科學家蒲豐(Buffon)提出了投針試驗問題.平面上畫有等距離為a(a>0)的一些平行直線,現(xiàn)向此平面任意投擲一根長為(b<a)的針,試求針與某一平行直線相交的概率.解由投擲的任意性可知這是一個幾何概型問題.蒲豐投針試驗的應用及意義蒙特卡洛方法解∏a=1;%設(shè)置兩條平行線之間的距離b=0.6;%投針的長度counter=0;%針與平行線相交的次數(shù)n=10000000;%投擲的次數(shù)x=unifrnd(0,a/2,1,n);%產(chǎn)生n個（0，a/2）之間均勻分布的隨機數(shù)，這里a/2是投針的中點到最近的平行線的距離phi=unifrnd(0,pi,1,n);%產(chǎn)生n個（0，pi）之間均勻分布的隨機數(shù)，這里pi是投針到最近的平行線的角度fori=1:nifx(i)<b*sin(phi(i))/2%只要x小于b*sin（phi（i））/2,則相交counter=counter+1;endendfrequency=counter/n;%計算相交的頻率，即相交次數(shù)與總次數(shù)比Pi=2*b/(a*frequency)%從相交的頻率求pi使用蒙特卡洛法與Matlab結(jié)合求π的近似值蒙特卡洛方法解∏蒙特卡洛方法解∏

利用求單位正方形與內(nèi)接圓面積的比例關(guān)系來求得π的近似值。單位圓的1/4面積是一個扇形，它是邊長為1單位正方形的一部分。如果能求出扇形面積s1在正方形面積s中占的比例k=s1/s，它的值也等于π/4，從而就計算得到π的值。

怎樣求出扇形面積在正方形面積中占的比例k呢？蒙特卡洛法是在正方形中隨機投入很多點，使所投的點落在正方形中每一個位置的機會相等。有些點將落在扇形內(nèi)，而另一些點將會落在扇形外，落在扇形內(nèi)的點數(shù)m與所投點的總數(shù)n之間比m/n即為k的近似值。使用蒙特卡洛法與VB結(jié)合求π的近似值蒙特卡洛方法解∏PrivateSubCommand1_Click()DimPiAsDouble,xAsDouble,yAsDoubleDimmAsLong,nAsLongRandomizeTimer

'隨機數(shù)初始化n=Val(Text1.Text)

'讀入投放次數(shù)nIfn=0ThenMsgBox"請輸入投放次數(shù)n"ExitSubEndIfm=0ForI=1Tonx=Rnd()y=Rnd()Ifx^2+y^2<=1Thenm=m+1

'判斷是否在扇形內(nèi)NextI

Pi=4*m/n

'計算出π的近似值Text2.Text=Str(Pi)EndSub蒙特卡洛方法解∏蒙特卡洛方法解∏使用蒙特卡洛法與Excel結(jié)合求π的近似值原理：面積為1的正方形內(nèi)一內(nèi)切圓。隨機扔一點在圓內(nèi)的概率為π/4。那么用MonteCarlo求出概率使之等于π/4，則可以計算出π。

方法：使用excel的rand（）函數(shù)取隨機數(shù)，以及二維坐標圓的公式x^2+y^2=A^2。

第一步：A1代表扔一點后距正方形右邊距離，B1代表扔一點后距正方形底邊距離，在A1輸入=rand（），在B1輸入=rand（），在C1輸入=IF((A1-0.5)^2+(B1-0.5)^2<0.5^2,4,0)

第二步：用excel拖動填充功能，向下拖單元格，想做多少次montecarlo模擬，就拖多少行，越多越準確。假設(shè)拖100行。

第三部：在C101輸入=average（C1：C100),所得結(jié)果即為π。蒙特卡洛方法解∏用蒙特卡洛方法解決食堂排隊問題用蒙特卡洛法在Excel上對大學食堂的窗口服務(wù)狀態(tài)和排隊等待問題進行模擬，分別模擬了食堂在開設(shè)一個窗口和兩個窗口的情況下學生的排隊問題，通過500次模擬的統(tǒng)計分析得出，該方法具有簡便、易行、實用性強的特點，為決策者提供了參考依據(jù)。我要吃飯用蒙特卡洛方法解決食堂排隊問題

學生食堂的排隊問題是一個學生們十分關(guān)心的問題，學生希望增加窗口數(shù)，減少排隊等待時間。然而就食堂的角度來說，雖說增加窗口數(shù)量可以減少排隊等待時間，提高學生對該食堂的滿意度，從而讓更多的學生到該食堂就餐，但是同時也會增加食堂的運營成本，因此如何在這兩者之間進行權(quán)衡，找到最佳的窗口數(shù)量，對學生和食堂雙方來說都是很重要的。蒙特卡羅方法，或稱計算機隨機模擬方法，是一種基于“隨機數(shù)”的計算方法，通過建立動態(tài)模型，模擬食堂窗口的排隊問題，當只有一個窗口服務(wù)的情況下，前一個學生未被服務(wù)完畢的時候，后一個學生必須等待，直到前一個學生離開服務(wù)臺，后一個學生才能被服務(wù)。而如果有兩個窗口服務(wù)的時候，則可以節(jié)省等待時間。用蒙特卡洛方法解決食堂排隊問題在Excel下建立模擬模型，分別模擬單一窗口W1和兩個窗口W2的模擬量變化情況。通過對比兩個窗口的平均等待時間T等模擬量，做出決策是否增加窗口：

其中，

為第i個學生的等待時間。1、模型建立用蒙特卡洛方法解決食堂排隊問題令為第i個學生的到達時刻；為第i個學生的到達間隔，它通常是一個隨機數(shù)；為第i個學生的服務(wù)開始時刻；為第i個學生的服務(wù)完成時刻；為第i個學生的服務(wù)時間，它通常是一個隨機數(shù)；為第i個學生的等待時間；為第i個學生的逗留時間時間。(1)學生到達間隔，服務(wù)時間學生到達間隔及服務(wù)時間為不可控變量，用蒙特卡洛法產(chǎn)生隨機數(shù)。(2)到達時刻(3)開始服務(wù)時刻用蒙特卡洛方法解決食堂排隊問題(4)等待時間(5)完成時刻(6)總逗留時間用蒙特卡洛方法解決食堂排隊問題2、認識幾個Excel常用函數(shù)(1)產(chǎn)生按歷史數(shù)據(jù)統(tǒng)計規(guī)律分布的隨機數(shù)公式：=VLOOKUP(RAND()，表左上角地址：表右下角地址，變量所在列)公式中的表為隨機數(shù)區(qū)間表。(2)IF條件函數(shù):=IF(logical_test，value_if_true，value_if_false)公式中第一項為邏輯判斷語句，隨后分別為正確時的返回值和錯誤時的返回值。用蒙特卡洛方法解決食堂排隊問題(3)COUNTIF函數(shù):=COUNTIF(rang,criteria)該公式用于統(tǒng)計在一定判斷標準下滿足條件的個數(shù)，其中公式中第一項為數(shù)據(jù)所在范圍；第二項為判斷標準；既滿足第二項條件的第一項數(shù)據(jù)的個數(shù)。(4)其他常用函數(shù)：MAX:返回樣本的最大值；MIN:返回樣本的最小值；AVERAGE:返回樣本的均值；STDEV:返回樣本的標準方差；SUM:返回樣本的代數(shù)和。用蒙特卡洛方法解決食堂排隊問題學生序號到達間隔達到時刻服務(wù)時刻等待時間服務(wù)時間完成時間總逗留時間10.000.3010

0.000.122020.300.5530

0.120.422530.550.7350

0.420.803040.730.8570

0.800.963550.850.9490

0.961.004060.941.00110

學生到達時間間隔的分布統(tǒng)計用蒙特卡洛方法解決食堂排隊問題單一窗口模型仿真結(jié)果用蒙特卡洛方法解決食堂排隊問題兩個窗口模擬模型兩個窗口和單個窗口相比，其余各變量不變，只有開始服務(wù)時刻有所變化。在兩個窗口的情況下，判斷何時能夠開始服務(wù)要看兩個窗口的狀態(tài)。當學生到達時刻比兩個窗口的開始空閑時刻都早時，學生得排隊等待，直到至少有一個窗口達到空閑狀態(tài)才開始接受服務(wù)，所以這時的“開始服務(wù)時刻”應等于先進人空閑狀態(tài)的那個窗口的“開始空閑時刻”(即最早開始空閑時刻)；當學生到達時刻比任意一個窗口的開始空閑時刻晚時，窗口可以立刻開始服務(wù)，所以這時的“開始服務(wù)時刻”應等于學生到達時刻。綜上所述，在兩個窗口的模擬問題中，我們需要在Excel中新增兩列，分別為“窗口一的空閑時刻”和“窗口二的空閑時刻”，并且“開始服務(wù)時刻”的公式也要有所改變。用蒙特卡洛方法解決食堂排隊問題窗口一的空閑時刻：

在第一個學生被服務(wù)時，窗口二保持空閑。所以窗口一的空閑時刻等于第一個學生的完成時刻。當學生陸續(xù)到達后，如果窗口一早于窗口二到達空閑狀態(tài)，則學生來到窗口一，這時窗口一的下一個開始空閑時刻等于該學生的服務(wù)完成時刻，窗口二的開始空閑時刻不變;如果窗口二早于窗口一達到空閑時刻，則該學生將來到窗口二，這是窗口二的下一個開始空閑時刻等于該學生的服務(wù)完成時刻，而窗口一的開始空閑時刻不變。用蒙特卡洛方法解決食堂排隊問題窗口二的空閑時刻：第一個學生來