數(shù)學建模競賽中應(yīng)課件

1、數(shù)學建模競賽中應(yīng)當掌握的十類算法1. 蒙特卡羅算法。該算法又稱隨機性模擬算法，是通過計算機仿真來解決問題的算法，同時可以通過模擬來檢驗自己模型的正確性，幾乎是比賽時必用的方法。2. 數(shù)據(jù)擬合、參數(shù)估計、插值等數(shù)據(jù)處理算法。比賽中通常會遇到大量的數(shù)據(jù)需要處理，而處理數(shù)據(jù)的關(guān)鍵就在于這些算法，通常使用MATLAB 作為工具。3. 線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類算法。建模競賽大多數(shù)問題屬于最優(yōu)化問題，很多時候這些問題可以用數(shù)學規(guī)劃算法來描述，通常使用Lindo、Lingo 軟件求解。4. 圖論算法。這類算法可以分為很多種，包括最短路、網(wǎng)絡(luò)流、二分圖等算法，涉及到圖論的問題可以用這些方

2、法解決，需要認真準備。5. 動態(tài)規(guī)劃、回溯搜索、分治算法、分支定界等計算機算法。這些算法是算法設(shè)計中比較常用的方法，競賽中很多場合會用到。6. 最優(yōu)化理論的三大非經(jīng)典算法：模擬退火算法、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法。這些問題是用來解決一些較困難的最優(yōu)化問題的，對于有些問題非常有幫助，但是算法的實現(xiàn)比較困難，需慎重使用。7. 網(wǎng)格算法和窮舉法。兩者都是暴力搜索最優(yōu)點的算法，在很多競賽題中有應(yīng)用，當重點討論模型本身而輕視算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具。8. 一些連續(xù)數(shù)據(jù)離散化方法。很多問題都是實際來的，數(shù)據(jù)可以是連續(xù)的，而計算機只能處理離散的數(shù)據(jù)，因此將其離散化后進行

3、差分代替微分、求和代替積分等思想是非常重要的。9. 數(shù)值分析算法。如果在比賽中采用高級語言進行編程的話，那些數(shù)值分析中常用的算法比如方程組求解、矩陣運算、函數(shù)積分等算法就需要額外編寫庫函數(shù)進行調(diào)用。10. 圖象處理算法。賽題中有一類問題與圖形有關(guān)，即使問題與圖形無關(guān)，論文中也會需要圖片來說明問題，這些圖形如何展示以及如何處理就是需要解決的問題，通常使用MATLAB 進行處理。 2以下將結(jié)合歷年的競賽題，對這十類算法進行詳細地說明 2.1 蒙特卡羅算法 大多數(shù)建模賽題中都離不開計算機仿真，隨機性模擬是非常常見的算法之一。 舉個例子就是97 年的A 題，每個零件都有自己的標定值，也都有自己的容差等

4、級，而求解最優(yōu)的組合方案將要面對著的是一個極其復(fù)雜的公式和108 種容差選取方案，根本不可能去求解析解，那如何去找到最優(yōu)的方案呢？隨機性模擬搜索最優(yōu)方案就是其中的一種方法，在每個零件可行的區(qū)間中按照正 態(tài)分布隨機的選取一個標定值和選取一個容差值作為一種方案，然后通過蒙特卡羅算法仿真出大量的方案，從中選取一個最佳的。另一個例子就是去年的彩票第二問，要求設(shè)計一種更好的方案，首先方案的優(yōu)劣取決于很多復(fù)雜的因素，同樣不可能刻畫出一個模型進行求解，只能靠隨機仿真模擬。 2.7 網(wǎng)格算法和窮舉算法 網(wǎng)格算法和窮舉法一樣，只是網(wǎng)格法是連續(xù)問題的窮舉。比如要求在N 個變量情況下的最優(yōu)化問題，那么對這些變量可取

5、的空間進行采點，比如在a, b 區(qū)間內(nèi)取M + 1 個點，就是a , a + (b -a)/M , a +2*(b - a)/M , , b 那么這樣循環(huán)就需要進行(M + 1)N 次運算，所以計算量很大。 比如97 年A 題、99 年B 題都可以用網(wǎng)格法搜索，這種方法最好在運算速度較快的計算機中進行，還有要用高級語言來做，最好不要用MATLAB 做網(wǎng)格，否則會算很久的。 窮舉法大家都熟悉，就不說了。 2.8 一些連續(xù)數(shù)據(jù)離散化的方法 大部分物理問題的編程解決，都和這種方法有一定的聯(lián)系。物理問題是反映我們生活在一個連續(xù)的世界中，計算機只能處理離散的量，所以需要對連續(xù)量進行離散處理。這種方法應(yīng)用很廣，而且和上面的很多算法有關(guān)。事實上，網(wǎng)格算法、蒙特卡羅算法、模擬退火都用了這個思想。 2.9 數(shù)值分析算法 這類算法是針對高級語言而專門設(shè)的，如果你用的是MATLAB、Mathematica，大可不必準備，因為象數(shù)值分析中有很多函數(shù)一般的數(shù)學軟件是具備的。 2.10 圖象處理算法 01 年A 題中需要你會讀BMP圖象、美國賽98 年A 題需要你知道三維插值計算，03 年B