計(jì)算機(jī)模擬-課件

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

2012-7-19Part1概論

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

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

該算法又稱計(jì)算機(jī)隨機(jī)性模擬方法，也稱統(tǒng)計(jì)試驗(yàn)方法。MC方法是一種基于“隨機(jī)數(shù)”的計(jì)算方法，能夠比較逼真地描述事物的特點(diǎn)及物理實(shí)驗(yàn)過(guò)程，解決一些數(shù)值方法難以解決的問(wèn)題。

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

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

山體海拔高度的插值計(jì)算數(shù)學(xué)建模競(jìng)賽常用算法(2)2.數(shù)據(jù)擬合、參數(shù)估計(jì)、插值等數(shù)據(jù)處理算法比賽中通常會(huì)遇到大量的數(shù)據(jù)需要處理，而處理數(shù)據(jù)的關(guān)鍵就在于這些算法，通常使用MATLAB作為工具。與圖形處理有關(guān)的問(wèn)題很多與擬合有關(guān)系。此類問(wèn)題在MATLAB中有很多函數(shù)可以調(diào)用，只有熟悉MATLAB，這些方法才能用好。98年B題用很多不等式完全可以把問(wèn)題刻畫(huà)清楚數(shù)學(xué)建模競(jìng)賽常用算法(3)3.規(guī)劃類問(wèn)題算法此類問(wèn)題主要有線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等。競(jìng)賽中很多問(wèn)題都和數(shù)學(xué)規(guī)劃有關(guān)，可以說(shuō)不少的模型都可以歸結(jié)為一組不等式作為約束條件、幾個(gè)函數(shù)表達(dá)式作為目標(biāo)函數(shù)的問(wèn)題，遇到這類問(wèn)題，求解就是關(guān)鍵了。因此列舉出規(guī)劃后用Lindo、Lingo等軟件來(lái)進(jìn)行解決比較方便，所以還需要熟悉這兩個(gè)軟件。98年B題、00年B題、95年鎖具裝箱等問(wèn)題體現(xiàn)了圖論問(wèn)題的重要性。數(shù)學(xué)建模競(jìng)賽常用算法(4)4.

圖論問(wèn)題

這類問(wèn)題算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等問(wèn)題。92年B題用分枝定界法97年B題是典型的動(dòng)態(tài)規(guī)劃問(wèn)題98年B題體現(xiàn)了分治算法數(shù)學(xué)建模競(jìng)賽常用算法(5)5.計(jì)算機(jī)算法設(shè)計(jì)中的問(wèn)題

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

這方面問(wèn)題和ACM程序設(shè)計(jì)競(jìng)賽中的問(wèn)題類似，可看一下與計(jì)算機(jī)算法有關(guān)的書(shū)。97年A題用模擬退火算法00年B題用神經(jīng)網(wǎng)絡(luò)分類算法01年B題這種難題也可以使用神經(jīng)網(wǎng)絡(luò)美國(guó)89年A題也和BP算法有關(guān)系美國(guó)03年B題伽馬刀問(wèn)題也是目前研究的課題，目前算法最佳的是遺傳算法。數(shù)學(xué)建模競(jìng)賽常用算法(6)6.最優(yōu)化理論的三大非經(jīng)典算法:

模擬退火法(SA)、神經(jīng)網(wǎng)絡(luò)(NN)、遺傳算法(GA)近幾年的賽題越來(lái)越復(fù)雜，很多問(wèn)題沒(méi)有什么很好的模型可以借鑒，于是這三類算法很多時(shí)候可以派上用場(chǎng)。97年A題、99年B題都可以用網(wǎng)格法搜索數(shù)學(xué)建模競(jìng)賽常用算法(7)網(wǎng)格算法和窮舉法一樣，只是網(wǎng)格法是連續(xù)問(wèn)題的窮舉。此類算法運(yùn)算量較大。7.網(wǎng)格算法和窮舉算法這種方法最好在運(yùn)算速度較快的計(jì)算機(jī)中進(jìn)行，還有要用高級(jí)語(yǔ)言來(lái)做，最好不要用MATLAB做網(wǎng)格，否則會(huì)算很久的。很多問(wèn)題都是實(shí)際來(lái)的，數(shù)據(jù)可以是連續(xù)的，而計(jì)算機(jī)只能處理離散的數(shù)據(jù)，因此需要將連續(xù)問(wèn)題進(jìn)行離散化處理后再用計(jì)算機(jī)求解。比如差分代替微分、求和代替積分等思想都是把連續(xù)問(wèn)題離散化的常用方法。數(shù)學(xué)建模競(jìng)賽常用算法(8)8.連續(xù)問(wèn)題離散化的方法數(shù)值分析研究各種求解數(shù)學(xué)問(wèn)題的數(shù)值計(jì)算方法，特別是適合于計(jì)算機(jī)實(shí)現(xiàn)方法與算法。數(shù)學(xué)建模競(jìng)賽常用算法(9)9.數(shù)值分析方法它的主要內(nèi)容包括函數(shù)的數(shù)值逼近、數(shù)值微分與數(shù)值積分、非線性方程的數(shù)值解法、數(shù)值代數(shù)、常微分方程數(shù)值解等。數(shù)值分析是計(jì)算數(shù)學(xué)的一個(gè)重要分支，把理論與計(jì)算緊密結(jié)合,是現(xiàn)代科學(xué)計(jì)算的基礎(chǔ)。

MATLAB等數(shù)學(xué)軟件中已經(jīng)有很多數(shù)值分析的函數(shù)可以直接調(diào)用。01年A題中需要你會(huì)讀BMP圖象98年美國(guó)A題需要你知道三維插值計(jì)算03年B題要求更高，不但需要編程計(jì)算還要進(jìn)行處理數(shù)學(xué)建模競(jìng)賽常用算法(10)10.圖象處理算法賽題中有一類問(wèn)題與圖形有關(guān)，即使問(wèn)題與圖形無(wú)關(guān)，論文中也會(huì)需要圖片來(lái)說(shuō)明問(wèn)題，這些圖形如何展示以及如何處理就是需要解決的問(wèn)題，通常使用MATLAB進(jìn)行處理。數(shù)模論文中也有很多圖片需要展示，解決這類問(wèn)題要熟悉MATLAB圖形圖像工具箱。什么是計(jì)算機(jī)模擬簡(jiǎn)單地說(shuō)：就是用計(jì)算機(jī)代替人工做事！模擬就是利用物理的、數(shù)學(xué)的模型來(lái)類比、模仿現(xiàn)實(shí)系統(tǒng)及其演變過(guò)程，以尋求過(guò)程規(guī)律的一種方法．在一定的假設(shè)條件下，運(yùn)用數(shù)學(xué)運(yùn)算模擬系統(tǒng)的運(yùn)行，稱為數(shù)學(xué)模擬．現(xiàn)代的數(shù)學(xué)模擬都是在計(jì)算機(jī)上進(jìn)行的，稱為計(jì)算機(jī)模擬．計(jì)算機(jī)模擬拋硬幣如何用計(jì)算機(jī)來(lái)模擬拋硬幣人會(huì)拋硬幣但計(jì)算機(jī)不會(huì)這中間必須架設(shè)一座橋建模分析拋硬幣的目的是什么？建模目的目的：想知道拋的結(jié)果是正面朝上，還是朝下？或者是否擊中目標(biāo)？．．．建立模型正面朝上

--1正面朝下

--0人工拋一次

--計(jì)算機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)Randi([0,1])Randi([0,1],[1,10000])模型求解A=randi([0,1],[1,10000]);Times=sum(A)Probability=Times/10000小練習(xí)若正面朝下

---1計(jì)算機(jī)模擬的特點(diǎn)適用于大量重復(fù)的工作搜索窮舉網(wǎng)絡(luò)法窮舉法窮舉法猜測(cè)：解為整數(shù)估計(jì)：0<x<25,0<y<25算法：列出所有的（x,y）組合，看看哪一組滿足方程。窮舉法（一）窮舉法（二）網(wǎng)格法實(shí)質(zhì)上也是窮舉法問(wèn)題不一定是整數(shù)，一般是實(shí)數(shù)連續(xù)型變量“個(gè)數(shù)”是無(wú)窮，故無(wú)法做到窮舉，但實(shí)際問(wèn)題一般允許誤差，在精度范圍內(nèi)可以近似。給定誤差，固定步長(zhǎng)，得到網(wǎng)格，進(jìn)行判斷，得到結(jié)果穩(wěn)定性差網(wǎng)格法搜索示例：三個(gè)孩子的年齡(1)兩個(gè)多年未見(jiàn)的朋友相遇，聊了很多事情?！瑼：既然你是數(shù)學(xué)教授，那你幫我算這個(gè)題，今天是個(gè)特殊日子：我三個(gè)兒子都在今天慶祝生日！那么你能算出他們都有多大嗎？B：好，但你得跟我講講他們的情況。A：好的，我給你一些提示，他們?nèi)齻€(gè)年齡之積是36.B：很好，但我還需要更多提示。三個(gè)孩子的年齡(2)A：我的大兒子的眼睛是藍(lán)色的。B考慮了一下說(shuō)，但是，我還有一點(diǎn)信息來(lái)解決你的這個(gè)難題。B：哦，夠了，B給出了正確的答案，即三個(gè)小孩的年齡。A：他們?nèi)齻€(gè)年齡之和等于那幢房子的窗戶個(gè)數(shù)。A指著對(duì)面的一幢房子說(shuō)。三個(gè)孩子的年齡(3)根據(jù)對(duì)話信息，用搜索的方法來(lái)解此問(wèn)題。信息1:三個(gè)小孩年齡之積為36只有以下8種可能，搜索范圍減少至8種情況:第一個(gè)小孩年齡36181299664第二個(gè)小孩年齡12342633第三個(gè)小孩年齡11112123三個(gè)孩子的年齡(4)信息2:三個(gè)小孩年齡之和等于窗戶數(shù)第一個(gè)小孩年齡36181299664第二個(gè)小孩年齡12342633第三個(gè)小孩年齡11112123窗戶數(shù):3821161413131110如果窗戶數(shù)為38、21、16、14、11、10即可得出答案B還需信息，即窗戶數(shù)為13.則可能為(9、2、2)或(6、6、1)信息2:大兒子眼睛是藍(lán)色的得答案：(9、2、2)Part2模擬方法方法分類確定性模擬離散時(shí)間離散事件隨機(jī)性模擬MonteCarlo方法其它方法MonteCarlo法窮舉是線性搜索（或順序搜索）MonteCarlo法是隨機(jī)取點(diǎn)解決多維、大規(guī)模、復(fù)雜問(wèn)題的通用法模擬次數(shù)要足夠多MonteCarlo法思考與練習(xí)試求解方程求函數(shù)的最小值點(diǎn)（Rastrigin’sFunction）全局最小點(diǎn)(0,0)思考與練習(xí)確定性模擬例：追擊問(wèn)題確定性模擬按時(shí)間模擬按事件模擬關(guān)鍵：f(x+1)=f(x)+else以人口問(wèn)題為例x(t+h)=x(t)+r

x(t)hMatlab求解1.定義函數(shù)Matlab求解2.求解Matlab求解3.結(jié)果Matlab求解離散化方法選取時(shí)間步長(zhǎng)將導(dǎo)數(shù)化為差商得到差分方程求解差分方程本例中：x(t+h)-x(t)=rx(t)h離散化方法離散化方法離散化方法（遞歸）離散化方法（遞歸）動(dòng)態(tài)仿真法類似于離散化方法不用建立微分方程，直接得到差分方程按時(shí)間步長(zhǎng)直接仿真，不用建模適用于大規(guī)模、高維、復(fù)雜問(wèn)題本例中：x(i+h)=x(i)+r

x(i)h動(dòng)態(tài)仿真法動(dòng)態(tài)仿真法結(jié)合其它方法--插值與擬合已有數(shù)據(jù)觀察數(shù)據(jù)圖選擇適合的模型進(jìn)行擬合擬合擬合隨機(jī)性模擬蒙特卡羅（MonteCarlo）方法是一種應(yīng)用隨機(jī)數(shù)來(lái)進(jìn)行計(jì)算機(jī)模擬的方法．此方法對(duì)研究的系統(tǒng)進(jìn)行隨機(jī)觀察抽樣，通過(guò)對(duì)樣本值的觀察統(tǒng)計(jì)，求得所研究系統(tǒng)的某些參數(shù)．常用命令1．產(chǎn)生m×n階［a，b］上均勻分布U（a，b）的隨機(jī)數(shù)矩陣：unifrnd(a,b,m,n)

產(chǎn)生一個(gè)［a，b］均勻分布的隨機(jī)數(shù)：unifrnd(a,b)2．產(chǎn)生m×n階［０，１］均勻分布的隨機(jī)數(shù)矩陣：rand(m,n)

產(chǎn)生一個(gè)［０，１］均勻分布的隨機(jī)數(shù)：randNormrndExprndChi2rndTrndpoissrndMonteCarlo解決確定性問(wèn)題將確定性結(jié)果用隨機(jī)表示即：a=Ex或a=隨機(jī)事件發(fā)生的概率產(chǎn)生大量的隨機(jī)數(shù)（表示隨機(jī)變量的試驗(yàn)結(jié)果）計(jì)算平均值（a=Ex情形）統(tǒng)計(jì)頻率（a=概率情形）頻率方法例：求單位圓的面積面積=所占比例=概率=頻率向正方體內(nèi)隨機(jī)投點(diǎn)，落在單位圓內(nèi)的頻率建模建立坐標(biāo)單位圓：正方形：模擬投點(diǎn)：

x=-1+2*randy=-1+2*rand判斷

ifx^2+y^2<1模擬期望方法例：求定積分定積分幾何意義：求面積分割，求和：上式右邊是平均值（或期望），x可看成均勻分布。模擬用蒙特卡羅法解非線性規(guī)劃問(wèn)題基本假設(shè)試驗(yàn)點(diǎn)的第j個(gè)分量xj服從[aj,bj]內(nèi)的均勻分布．符號(hào)假設(shè)求解過(guò)程先產(chǎn)生一個(gè)隨機(jī)數(shù)作為初始試驗(yàn)點(diǎn),以后則將上一個(gè)試驗(yàn)點(diǎn)的第j個(gè)分量隨機(jī)產(chǎn)生，其他分量不變而產(chǎn)生一新的試驗(yàn)點(diǎn)．這樣，每產(chǎn)生一個(gè)新試驗(yàn)點(diǎn)只需一個(gè)新的隨機(jī)數(shù)分量．當(dāng)K>MAXK或P>MAXP時(shí)停止迭代．

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

lpconst.m.主程序?yàn)閞andlp.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)化為求最小值問(wèn)題%randlp.m

function[sol,r1,r2]=randlp(a,b,n)

%隨機(jī)模擬解非線性規(guī)劃debug=1;a=0;

%試驗(yàn)點(diǎn)下界b=10;

%試驗(yàn)點(diǎn)上界n=1000;

%試驗(yàn)點(diǎn)個(gè)數(shù)r1=unifrnd(a,b,n,1);

%n

1階的［a,b］均勻分布隨機(jī)數(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])；

if

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

ifz<z0z0=z；

sol=[x1x2]；

end

endendPart6思考與練習(xí)連續(xù)系統(tǒng)模擬實(shí)例:追逐問(wèn)題狀態(tài)隨時(shí)間連續(xù)變化的系統(tǒng)稱為連續(xù)系統(tǒng)．對(duì)連續(xù)系統(tǒng)