數學建模中常見的十大

模型集團標準化工作小組#Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#

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