數(shù)學(xué)建模中常見(jiàn)的十大模型

數(shù)學(xué)建模中常見(jiàn)的十大

模型集團(tuán)標(biāo)準(zhǔn)化工作小組#Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#

數(shù)學(xué)建模常用的十大算法==轉(zhuǎn)(2011-07-2416:13:14)蒙特卡羅算法。該算法又稱隨機(jī)性模擬算法，是通過(guò)計(jì)算機(jī)仿真來(lái)解決問(wèn)題的算法，同時(shí)可以通過(guò)模擬來(lái)檢驗(yàn)自己模型的正確性，幾乎是比賽時(shí)必用的方法。數(shù)據(jù)擬合、參數(shù)估計(jì)、插值等數(shù)據(jù)處理算法。比賽中通常會(huì)遇到大量的數(shù)據(jù)需要處理，而處理數(shù)據(jù)的關(guān)鍵就在于這些算法，通常使用MATLAB作為工具。線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類算法。建模競(jìng)賽大多數(shù)問(wèn)題屬于最優(yōu)化問(wèn)題，很多時(shí)候這些問(wèn)題可以用數(shù)學(xué)規(guī)劃算法來(lái)描述，通常使用Lindo、Lingo軟件求解。圖論算法。這類算法可以分為很多種，包括最短路、網(wǎng)絡(luò)流、二分圖等算法，涉及到圖論的問(wèn)題可以用這些方法解決，需要認(rèn)真準(zhǔn)備。動(dòng)態(tài)規(guī)劃、回溯搜索、分治算法、分支定界等計(jì)算機(jī)算法。這些算法是算法設(shè)計(jì)中比較常用的方法，競(jìng)賽中很多場(chǎng)合會(huì)用到。最優(yōu)化理論的三大非經(jīng)典算法：模擬退火算法、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法。這些問(wèn)題是用來(lái)解決一些較困難的最優(yōu)化問(wèn)題的，對(duì)于有些問(wèn)題非常有幫助，但是算法的實(shí)現(xiàn)比較困難，需慎重使用。網(wǎng)格算法和窮舉法。兩者都是暴力搜索最優(yōu)點(diǎn)的算法，在很多競(jìng)賽題中有應(yīng)用，當(dāng)重點(diǎn)討論模型本身而輕視算法的時(shí)候，可以使用這種暴力方案，最好使用一些高級(jí)語(yǔ)言作為編程工具。一些連續(xù)數(shù)據(jù)離散化方法。很多問(wèn)題都是實(shí)際來(lái)的，數(shù)據(jù)可以是連續(xù)的，而計(jì)算機(jī)只能處理離散的數(shù)據(jù)，因此將其離散化后進(jìn)行差分代替微分、求和代替積分等思想是非常重要的。數(shù)值分析算法。如果在比賽中采用高級(jí)語(yǔ)言進(jìn)行編程的話，那些數(shù)值分析中常用的算法比如方程組求解、矩陣運(yùn)算、函數(shù)積分等算法就需要額外編寫庫(kù)函數(shù)進(jìn)行調(diào)用。圖象處理算法。賽題中有一類問(wèn)題與圖形有關(guān)，即使問(wèn)題與圖形無(wú)關(guān)，論文中也會(huì)需要圖片來(lái)說(shuō)明問(wèn)題，這些圖形如何展示以及如何處理就是需要解決的問(wèn)題，通常使用MATLAB進(jìn)行處理。以下將結(jié)合歷年的競(jìng)賽題，對(duì)這十類算法進(jìn)行詳細(xì)地說(shuō)明。以下將結(jié)合歷年的競(jìng)賽題，對(duì)這十類算法進(jìn)行詳細(xì)地說(shuō)明。2十類算法的詳細(xì)說(shuō)明蒙特卡羅算法大多數(shù)建模賽題中都離不開(kāi)計(jì)算機(jī)仿真，隨機(jī)性模擬是非常常見(jiàn)的算法之一。舉個(gè)例子就是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è)最佳的。另一個(gè)例子就是去年的彩票第二問(wèn)，要求設(shè)計(jì)一種更好的方案，首先方案的優(yōu)劣取決于很多復(fù)雜的因素，同樣不可能刻畫出一個(gè)模型進(jìn)行求解，只能靠隨機(jī)仿真模擬。數(shù)據(jù)擬合、參數(shù)估計(jì)、插值等算法數(shù)據(jù)擬合在很多賽題中有應(yīng)用，與圖形處理有關(guān)的問(wèn)題很多與擬合有關(guān)系，一個(gè)例子就是98年美國(guó)賽A題，生物組織切片的三維插值處理，94年A題逢山開(kāi)路，山體海拔高度的插值計(jì)算，還有吵的沸沸揚(yáng)揚(yáng)可能會(huì)考的“非典”問(wèn)題也要用到數(shù)據(jù)擬合算法，觀察數(shù)據(jù)的走向進(jìn)行處理。此類問(wèn)題在MATLAB中有很多現(xiàn)成的函數(shù)可以調(diào)用，熟悉MATLAB，這些方法都能游刃有余的用好。規(guī)劃類問(wèn)題算法競(jìng)賽中很多問(wèn)題都和數(shù)學(xué)規(guī)劃有關(guān)，可以說(shuō)不少的模型都可以歸結(jié)為一組不等式作為約束條件、幾個(gè)函數(shù)表達(dá)式作為目標(biāo)函數(shù)的問(wèn)題，遇到這類問(wèn)題，求解就是關(guān)鍵了，比如98年B題，用很多不等式完全可以把問(wèn)題刻畫清楚，因此列舉出規(guī)劃后用Lindo、Lingo等軟件來(lái)進(jìn)行解決比較方便，所以還需要熟悉這兩個(gè)軟件。圖論問(wèn)題98年B題、00年B題、95年鎖具裝箱等問(wèn)題體現(xiàn)了圖論問(wèn)題的重要性，這類問(wèn)題算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等問(wèn)題。每一個(gè)算法都應(yīng)該實(shí)現(xiàn)一遍，否則到比賽時(shí)再寫就晚了。計(jì)算機(jī)算法設(shè)計(jì)中的問(wèn)題計(jì)算機(jī)算法設(shè)計(jì)包括很多內(nèi)容：動(dòng)態(tài)規(guī)劃、回溯搜索、分治算法、分支定界。比如92年B題用分枝定界法，97年B題是典型的動(dòng)態(tài)規(guī)劃問(wèn)題，此外98年B題體現(xiàn)了分治算法。這方面問(wèn)題和ACM程序設(shè)計(jì)競(jìng)賽中的問(wèn)題類似，推薦看一下《計(jì)算機(jī)算法設(shè)計(jì)與分析》（電子工業(yè)出版社）等與計(jì)算機(jī)算法有關(guān)的書。最優(yōu)化理論的三大非經(jīng)典算法這十幾年來(lái)最優(yōu)化理論有了飛速發(fā)展，模擬退火法、神經(jīng)網(wǎng)絡(luò)、遺傳算法這三類算法發(fā)展很快。近幾年的賽題越來(lái)越復(fù)雜，很多問(wèn)題沒(méi)有什么很好的模型可以借鑒，于是這三類算法很多時(shí)候可以派上用場(chǎng)，比如：97年A題的模擬退火算法，00年B題的神經(jīng)網(wǎng)絡(luò)分類算法，象01年B題這種難題也可以使用神經(jīng)網(wǎng)絡(luò)，還有美國(guó)競(jìng)賽89年A題也和BP算法有關(guān)系，當(dāng)時(shí)是86年剛提出BP算法，89年就考了，說(shuō)明賽題可能是當(dāng)今前沿科技的抽象體現(xiàn)。03年B題伽馬刀問(wèn)題也是目前研究的課題，目前算法最佳的是遺傳算法。網(wǎng)格算法和窮舉算法網(wǎng)格算法和窮舉法一樣，只是網(wǎng)格法是連續(xù)問(wèn)題的窮舉。比如要求在N個(gè)變量情況下的最優(yōu)化問(wèn)題，那么對(duì)這些變量可取的空間進(jìn)行采點(diǎn)，比如在[a;b]區(qū)間內(nèi)取M+1個(gè)點(diǎn)，就是a;a+(b-a)/M;a+2(b-a)/M;;b那么這樣循環(huán)就需要進(jìn)行(M+1)N次運(yùn)算，所以計(jì)算量很大。比如97年A題、99年B題都可以用網(wǎng)格法搜索，這種方法最好在運(yùn)算速度較快的計(jì)算機(jī)中進(jìn)行，還有要用高級(jí)語(yǔ)言來(lái)做，最好不要用MATLAB做網(wǎng)格，否則會(huì)算很久的。窮舉法大家都熟悉，就不說(shuō)了。一些連續(xù)數(shù)據(jù)離散化的方法大部分物理問(wèn)題的編程解決，都和這種方法有一定的聯(lián)系。物理問(wèn)題是反映我們生活在一個(gè)連續(xù)的世界中，計(jì)算機(jī)只能處理離散的量，所以需要對(duì)連續(xù)量進(jìn)行離散處理。這種方法應(yīng)用很廣，而且和上面的很多算法有關(guān)。事實(shí)上，網(wǎng)格算法、蒙特卡羅算法、模擬退火都用了這個(gè)思想。數(shù)值分析算法這類算法是針對(duì)高級(jí)語(yǔ)言而專門設(shè)的，如果你用的是MATLAB、Mathematica，大可不必準(zhǔn)備，因?yàn)橄髷?shù)值分析中有很多函數(shù)一般的數(shù)學(xué)軟件是具