計算機模擬-課件

計算機模擬許志軍東華理工大學(xué)數(shù)學(xué)系

2012-7-19Part1概論

澳洲19名數(shù)學(xué)家組團賭博3年狂贏156億元人民幣俗話說“十賭九輸”，但令人驚訝的是，澳大利亞19名天才數(shù)學(xué)家竟組成了一個名為“龐特俱樂部”的“高智商”賭博集團，利用他們對數(shù)學(xué)的專業(yè)知識，在世界各國的賭場和博彩業(yè)瘋狂賭博！而在短短3年時間里，堪稱“十賭九贏”的他們竟總計贏取了超過24億澳元(約156億人民幣)，令他們?nèi)紦u身變成了超級富翁！直到不久前，當(dāng)19名數(shù)學(xué)家在賭場上的成功引起澳大利亞稅務(wù)局的注意、并指控他們逃稅高達9億澳元后，才終于令這個神秘的“高智商”賭博集團浮出水面！靠數(shù)學(xué)知識演算“逢賭必贏”秘笈令19名數(shù)學(xué)家驚喜的是，雖然他們所掌握的那些高深數(shù)學(xué)知識在現(xiàn)實生活中似乎派不上多大用場，但竟然出人意料地在賭場上顯現(xiàn)出了巨大的威力！據(jù)悉，19名數(shù)學(xué)家參與的大多是賽馬、賽狗以及21點之類的賭博項目。而每次下注之前，他們會利用自己所精通的專業(yè)數(shù)學(xué)方法對各種中獎的概率進行推理演算，從而研究出某種“逢賭必贏”的秘笈！1.

蒙特卡羅方法(Monte-Carlo方法,MC)數(shù)學(xué)建模競賽常用算法(1)

該算法又稱計算機隨機性模擬方法，也稱統(tǒng)計試驗方法。MC方法是一種基于“隨機數(shù)”的計算方法，能夠比較逼真地描述事物的特點及物理實驗過程，解決一些數(shù)值方法難以解決的問題。MC方法的雛型可以追溯到十九世紀(jì)后期的蒲豐隨機投針試驗，即著名的蒲豐問題。MC方法通過計算機仿真(模擬)解決問題，同時也可以通過模擬來檢驗自己模型的正確性，是比賽中經(jīng)常使用的方法。97年的A題每個零件都有自己的標(biāo)定值，也都有自己的容差等級，而求解最優(yōu)的組合方案將要面對著的是一個極其復(fù)雜的公式和108種容差選取方案，根本不可能去求解析解，那如何去找到最優(yōu)的方案呢？隨機性模擬搜索最優(yōu)方案就是其中的一種方法，在每個零件可行的區(qū)間中按照正態(tài)分布隨機的選取一個標(biāo)定值和選取一個容差值作為一種方案，然后通過蒙特卡羅算法仿真出大量的方案，從中選取一個最佳的。02年的B題關(guān)于彩票第二問，要求設(shè)計一種更好的方案，首先方案的優(yōu)劣取決于很多復(fù)雜的因素，同樣不可能刻畫出一個模型進行求解，只能靠隨機仿真模擬。數(shù)學(xué)建模競賽常用算法98年美國賽A題

生物組織切片的三維插值處理94年A題逢山開路

山體海拔高度的插值計算數(shù)學(xué)建模競賽常用算法(2)2.數(shù)據(jù)擬合、參數(shù)估計、插值等數(shù)據(jù)處理算法比賽中通常會遇到大量的數(shù)據(jù)需要處理，而處理數(shù)據(jù)的關(guān)鍵就在于這些算法，通常使用MATLAB作為工具。與圖形處理有關(guān)的問題很多與擬合有關(guān)系。此類問題在MATLAB中有很多函數(shù)可以調(diào)用，只有熟悉MATLAB，這些方法才能用好。92年B題用分枝定界法97年B題是典型的動態(tài)規(guī)劃問題98年B題體現(xiàn)了分治算法數(shù)學(xué)建模競賽常用算法(5)5.計算機算法設(shè)計中的問題

計算機算法設(shè)計包括很多內(nèi)容：動態(tài)規(guī)劃、回溯搜索、分治算法、分枝定界等計算機算法.

這方面問題和ACM程序設(shè)計競賽中的問題類似，可看一下與計算機算法有關(guān)的書。97年A題用模擬退火算法00年B題用神經(jīng)網(wǎng)絡(luò)分類算法01年B題這種難題也可以使用神經(jīng)網(wǎng)絡(luò)美國89年A題也和BP算法有關(guān)系美國03年B題伽馬刀問題也是目前研究的課題，目前算法最佳的是遺傳算法。數(shù)學(xué)建模競賽常用算法(6)6.最優(yōu)化理論的三大非經(jīng)典算法:模擬退火法(SA)、神經(jīng)網(wǎng)絡(luò)(NN)、遺傳算法(GA)近幾年的賽題越來越復(fù)雜，很多問題沒有什么很好的模型可以借鑒，于是這三類算法很多時候可以派上用場。97年A題、99年B題都可以用網(wǎng)格法搜索數(shù)學(xué)建模競賽常用算法(7)網(wǎng)格算法和窮舉法一樣，只是網(wǎng)格法是連續(xù)問題的窮舉。此類算法運算量較大。7.網(wǎng)格算法和窮舉算法這種方法最好在運算速度較快的計算機中進行，還有要用高級語言來做，最好不要用MATLAB做網(wǎng)格，否則會算很久的。什么是計算機模擬簡單地說：就是用計算機代替人工做事！模擬就是利用物理的、數(shù)學(xué)的模型來類比、模仿現(xiàn)實系統(tǒng)及其演變過程，以尋求過程規(guī)律的一種方法．在一定的假設(shè)條件下，運用數(shù)學(xué)運算模擬系統(tǒng)的運行，稱為數(shù)學(xué)模擬．現(xiàn)代的數(shù)學(xué)模擬都是在計算機上進行的，稱為計算機模擬．計算機模擬拋硬幣如何用計算機來模擬拋硬幣人會拋硬幣但計算機不會這中間必須架設(shè)一座橋建模分析拋硬幣的目的是什么？建模目的目的：想知道拋的結(jié)果是正面朝上，還是朝下？或者是否擊中目標(biāo)？．．．窮舉法窮舉法猜測：解為整數(shù)估計：0<x<25,0<y<25算法：列出所有的（x,y）組合，看看哪一組滿足方程。窮舉法（一）窮舉法（二）網(wǎng)格法實質(zhì)上也是窮舉法問題不一定是整數(shù)，一般是實數(shù)連續(xù)型變量“個數(shù)”是無窮，故無法做到窮舉，但實際問題一般允許誤差，在精度范圍內(nèi)可以近似。給定誤差，固定步長，得到網(wǎng)格，進行判斷，得到結(jié)果穩(wěn)定性差網(wǎng)格法搜索示例：三個孩子的年齡(1)兩個多年未見的朋友相遇，聊了很多事情?！瑼：既然你是數(shù)學(xué)教授，那你幫我算這個題，今天是個特殊日子：我三個兒子都在今天慶祝生日！那么你能算出他們都有多大嗎？B：好，但你得跟我講講他們的情況。A：好的，我給你一些提示，他們?nèi)齻€年齡之積是36.B：很好，但我還需要更多提示。三個孩子的年齡(2)A：我的大兒子的眼睛是藍色的。B考慮了一下說，但是，我還有一點信息來解決你的這個難題。B：哦，夠了，B給出了正確的答案，即三個小孩的年齡。A：他們?nèi)齻€年齡之和等于那幢房子的窗戶個數(shù)。A指著對面的一幢房子說。三個孩子的年齡(3)根據(jù)對話信息，用搜索的方法來解此問題。信息1:三個小孩年齡之積為36只有以下8種可能，搜索范圍減少至8種情況:第一個小孩年齡36181299664第二個小孩年齡12342633第三個小孩年齡11112123方法分類確定性模擬離散時間離散事件隨機性模擬MonteCarlo方法其它方法MonteCarlo法窮舉是線性搜索（或順序搜索）MonteCarlo法是隨機取點解決多維、大規(guī)模、復(fù)雜問題的通用法模擬次數(shù)要足夠多MonteCarlo法思考與練習(xí)試求解方程求函數(shù)的最小值點（Rastrigin’sFunction）全局最小點(0,0)思考與練習(xí)確定性模擬例：追擊問題確定性模擬按時間模擬按事件模擬關(guān)鍵：f(x+1)=f(x)+else以人口問題為例x(t+h)=x(t)+r

x(t)hMatlab求解1.定義函數(shù)Matlab求解2.求解Matlab求解3.結(jié)果Matlab求解離散化方法選取時間步長將導(dǎo)數(shù)化為差商得到差分方程求解差分方程本例中：x(t+h)-x(t)=rx(t)h離散化方法離散化方法離散化方法（遞歸）離散化方法（遞歸）動態(tài)仿真法類似于離散化方法不用建立微分方程，直接得到差分方程按時間步長直接仿真，不用建模適用于大規(guī)模、高維、復(fù)雜問題本例中：x(i+h)=x(i)+rx(i)h動態(tài)仿真法動態(tài)仿真法結(jié)合其它方法--插值與擬合已有數(shù)據(jù)觀察數(shù)據(jù)圖選擇適合的模型進行擬合擬合擬合隨機性模擬蒙特卡羅（MonteCarlo）方法是一種應(yīng)用隨機數(shù)來進行計算機模擬的方法．此方法對研究的系統(tǒng)進行隨機觀察抽樣，通過對樣本值的觀察統(tǒng)計，求得所研究系統(tǒng)的某些參數(shù)．常用命令1．產(chǎn)生m×n階［a，b］上均勻分布U（a，b）的隨機數(shù)矩陣：unifrnd(a,b,m,n)產(chǎn)生一個［a，b］均勻分布的隨機數(shù)：unifrnd(a,b)2．產(chǎn)生m×n階［０，１］均勻分布的隨機數(shù)矩陣：rand(m,n)產(chǎn)生一個［０，１］均勻分布的隨機數(shù)：randNormrndExprndChi2rndTrndpoissrndMonteCarlo解決確定性問題將確定性結(jié)果用隨機表示即：a=Ex或a=隨機事件發(fā)生的概率產(chǎn)生大量的隨機數(shù)（表示隨機變量的試驗結(jié)果）計算平均值（a=Ex情形）統(tǒng)計頻率（a=概率情形）頻率方法例：求單位圓的面積面積=所占比例=概率=頻率向正方體內(nèi)隨機投點，落在單位圓內(nèi)的頻率建模建立坐標(biāo)單位圓：正方形：模擬投點：x=-1+2*randy=-1+2*rand判斷ifx^2+y^2<1模擬期望方法例：求定積分定積分幾何意義：求面積分割，求和：上式右邊是平均值（或期望），x可看成均勻分布。模擬用蒙特卡羅法解非線性規(guī)劃問題基本假設(shè)試驗點的第j個分量xj服從[aj,bj]內(nèi)的均勻分布．符號假設(shè)求解過程先產(chǎn)生一個隨機數(shù)作為初始試驗點,以后則將上一個試驗點的第j個分量隨機產(chǎn)生，其他分量不變而產(chǎn)生一新的試驗點．這樣，每產(chǎn)生一個新試驗點只需一個新的隨機數(shù)分量．當(dāng)K>MAXK或P>MAXP時停止迭代．

在MATLAB軟件包中編程，共需3個Ｍ文件:randlp.m,mylp.m,

lpconst.m.主程序為randlp.m.%mylp.mfunctionz=mylp(x)%目標(biāo)函數(shù)z=2*x(1)^2+x(2)^2-x(1)*x(2)-8*x(1)-3*x(2);%轉(zhuǎn)化為求最小值問題%randlp.m

function[sol,r1,r2]=randlp(a,b,n)%隨機模擬解非線性規(guī)劃debug=1;a=0;%試驗點下界b=10;%試驗點上界n=1000;%試驗點個數(shù)r1=unifrnd(a,b,n,1);%n1階的［a,b］均勻分布隨機數(shù)矩陣r2=unifrnd(a,b,n,1);sol=[r1(1)r2(1)];z0=inf;fori=1:nx1=r1(i);x2=r2(i);lpc=lpconst([x1x2])；

iflpc==1z=mylp([x1x2])；

ifz<z0z0=z；sol=[x1x2]；

end

endendPart6思考與練習(xí)連續(xù)系統(tǒng)模擬實例:追逐問題狀態(tài)隨時間連續(xù)變化的系統(tǒng)稱為連續(xù)系統(tǒng)．對連續(xù)系統(tǒng)的計算機模擬只能是近似的，只要這種近似達到一定的精度，也就可以滿足要求．例追逐問題:

如圖,正方形ABCD的4個頂點各有1人.在某一時刻,4人同時出發(fā)以勻速v=1m/s按順時針方向追逐下一人,如果他們始終保持對準(zhǔn)目標(biāo),則最終按螺旋狀曲線于中心點O.試求出這種情況下每個人的行進軌跡.OBCDA1.建立平面直角坐標(biāo)系:A(x1,y1),B(x2,y2),C(x3,y3),D(x4,y4).2.取時間間隔為Δt,計算每一點在各個時刻的坐標(biāo).4.對每一個點，連接它在各時刻的位置,即得所求運動軌跡.求解過程:v=1;dt=0.05;x=[001010];y=[010100];fori=1:4plot(x(i),y(i),'.'),holdonendd=20;while(d>0.1)