建模中常用的算法和經驗常用算法和一些個人經驗（僅供參考）主要內容一、簡介建模；二、建模中常用的算法；三、組隊時應該考慮哪些；四、賽前準備；五、賽中的角色分配。一、建模簡介數學建模競賽與純數學競賽有本質上的區別。它涉及計算機、物理、化學、生物、醫學、管理等各個領域，當然基本的數學知識是必備的，但它又不受任何一門具體的學科、領域所局限。這就要求我們知識面寬廣，也是我們參加建模的目的所在，通過建模拓展我們的知識面，增加學習的技能。常用算法在數學建模中常用的方法：類比法、二分法、量綱分析法、差分法、變分法、圖論法、層次分析法、數據擬合法、回歸分析法、數學規劃（線性規劃，非線性規劃，整數規劃，動態規劃，目標規劃）、機理分析、排隊方法、對策方法、決策方法、模糊評判方法、時間序列方法、灰色理論方法、現代優化算法（禁忌搜索算法，模擬退火算法，遺傳算法，神經網絡）。用這些方法可以解下列一些模型：優化模型、微分方程模型、統計模型、概率模型、圖論模型、決策模型。二、建模中的常用算法建模中根據具體問題的不同可以采用不同的算法，一個算法可能解決一類問題，當然對于同一個問題，也可能有不同的算法求解，不同算法求解的差異可能不大也可能大相徑庭，也就是說建模時沒有最好的算法，只是適合和不適合。常用算法：1、蒙特卡羅算法：該算法又稱隨機性模擬算法，是通過計算機仿真來解決問題的算法，同時可以通過模擬可以來檢驗自己模型的正確性，是比賽時必用的方法。求解各種類型規劃。（隨機取樣法m文件lingo軟件）選址問題固定費用問題指派問題生產銷售計劃問題97年的A題，每個零件都有自己的標定值，也都有自己的容差等級，而求解最優的組合方案將要面對著的是一個極其復雜的公式和108種容差選取方案，根本不可能去求解析解，那如何去找到最優的方案呢？隨機性模擬搜索最優方案就是其中的一種方法，在每個零件可行的區間中按照正態分布隨機的選取一個標定值和選取一個容差值作為一種方案，然后通過蒙特卡羅算法仿真出大量的方案，從中選取一個最佳的。02年的B題，關于彩票第二問，要求設計一種更好的方案，首先方案的優劣取決于很多復雜的因素，同樣不可能刻畫出一個模型進行求解，只能靠隨機仿真模擬。2、數據擬合、參數估計、插值等數據處理算法比賽中通常會遇到大量的數據需要處理，而處理數據的關鍵就在于這些算法，通常使用MATLAB作為工具。與圖形處理有關的問題很多與擬合有關系。98年美國賽A題，生物組織切片的三維插值處理。94年A題逢山開路，山體海拔高度的插值計算。此類問題在MATLAB中有很多函數可以調用，只有熟悉MATLAB，這些方法才能用好。插值擬和與參數估計插值：求過已知有限個數據點的近似函數。擬合：已知有限個數據點，求近似函數，不要求過已知數據點，只要求在某種意義下它在這些點上的總偏差最小。插值和擬合都是要根據一組數據構造一個函數作為近似，由于近似的要求不同，二者的數學方法上是完全不同的。而面對一個實際問題，究竟應該用插值還是擬合，有時容易確定，有時則并不明顯。擬合與插值方法（給出一批數據點，確定滿足特定要求的曲線或者曲面，從而反映對象整體的變化趨勢）：matlab可以實現一元函數，包括多項式和非線性函數的擬合以及多元函數的擬合，即回歸分析，從而確定函數；同時也可以用matlab實現分段線性、多項式、樣條以及多維插值。3、線性規劃、整數規劃、多元規劃、二次規劃等規劃類問題此類問題主要有線性規劃、整數規劃、多元規劃、二次規劃等。競賽中很多問題都和數學規劃有關，可以說不少的模型都可以歸結為一組不等式作為約束條件、幾個函數表達式作為目標函數的問題，遇到這類問題，求解就是關鍵了。98年B題，用很多不等式完全可以把問題刻畫清楚。因此列舉出規劃后用Lindo、Lingo等軟件來進行解決比較方便，所以還需要熟悉這兩個軟件。4、圖論算法這類算法可以分為很多種，包括最短路、網絡流、二分圖等算法，涉及到圖論的問題可以用這些方法解決，需要認真準備。這類問題算法有很多，包括：Dijkstra、Floyd、PrimBellman-Ford，最大流，二分匹配等問題。98年B題、00年B題、95年鎖具裝箱等問題體現了圖論問題的重要性圖論最短路問題：兩個指定頂點之間的最短路徑—給出了一個連接若干個城鎮的鐵路網絡，在這個網絡的兩個指定城鎮間，找一條最短鐵路線（Dijkstra算法）每對頂點之間的最短路徑（Dijkstra算法、Floyd算法）。最小生成樹問題：連線問題—欲修筑連接多個城市的鐵路設計一個線路圖，使總造價最低（prim算法、Kruskal算法）。圖的匹配問題：人員分派問題：n個工作人員去做件n份工作，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？(匈牙利算法)。遍歷性問題：中國郵遞員問題—郵遞員發送郵件時，要從郵局出發，經過他投遞范圍內的每條街道至少一次，然后返回郵局，但郵遞員希望選擇一條行程最短的路線最大流問題。運輸問題：最小費用最大流問題：在運輸問題中，人們總是希望在完成運輸任務的同時，尋求一個使總的運輸費用最小的運輸方案5、動態規劃、回溯搜索、分治算法、分支定界等計算機算法對有約束條件的最優化問題（其可行解為有限數）的所有可行解空間恰當地進行系統搜索，這就是分枝與定界內容。通常，把全部可行解空間反復地分割為越來越小的子集，稱為分枝；并且對每個子集內的解集計算一個目標下界（對于最小值問題），這稱為定界。在每次分枝后，凡是界限超出已知可行解集目標值的那些子集不再進一步分枝，這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。這些算法是算法設計中比較常用的方法，很多場合可以用到競賽中。92年B題用分枝定界法97年B題是典型的動態規劃問題6、最優化理論的三大非經典算法模擬退火法、神經網絡、遺傳算法：這些問題是用來解決一些較困難的最優化問題的算法，對于有些問題非常有幫助，但是算法的實現比較困難，需慎重使用。近幾年的賽題越來越復雜，很多問題沒有什么很好的模型可以借鑒，于是這三類算法很多時候可以派上用場。97年A題用模擬退火算法00年B題用神經網絡分類算法01年B題這種難題也可以使用神經網絡美國89年A題也和BP算法有關系，當時是86年剛提出BP算法，89年就考了，說明賽題可能是當今前沿科技的抽象體現。美國03年7、數值分析算法如果在比賽中采用高級語言進行編程的話，那一些數值分析中常用的算法比如方程組求解、矩陣運算、函數積分等算法就需要額外編寫庫函數進行調用。數值分析研究各種求解數學問題的數值計算方法，特別是適合于計算機實現的方法與算法。它的主要內容包括函數的數值逼近、數值微分與數值積分、非線性方程的數值解法、數值代數、常微分方程數值解等。數值分析是計算數學的一個重要分支，把理論與計算緊密結合,是現代科學計算的基礎。MATLAB等數學軟件中已經有很多數值分析的函數可以直接調用。8、一些連續離散化方法：很多問題都是實際來的，數據可以是連續的，而計算機只能處理離散的數據，因此需要將連續問題進行離散化處理后再用計算機求解。比如差分代替微分、求和代替積分等思想都是把連續問題離散化的常用方法。9、網格算法和窮舉法網格算法和窮舉法都是暴力搜索最優點的算法，在很多競賽題中有應用，當重點討論模型本身而輕視算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具。網格算法和窮舉法一樣，只是網格法是連續問題的窮舉。比如要求在N個變量情況下的最優化問題，那么對這些變量可取的空間進行采點，比如在[ab]區間內取M+1個點，就是a，a+(b-a)/M，a+2(b-a)/M，…，b。那么這樣循環就需要進行(M+1)^N次運算，所以計算量很大。97年A題、99年B題都可以用網格法搜索這種方法最好在運算速度較快的計算機中進行，還有要用高級語言來做，最好不要用MATLAB做網格，否則會算很久的。10、圖象處理算法賽題中有一類問題與圖形有關，即使與圖形無關，論文中也應該要不乏圖片的，這些圖形如何展示以及如何處理就是需要解決的問題，通常使用Matlab進行處理。01年A題中需要你會讀BMP圖象98年美國A題需要你知道三維插值計算03年B題要求更高，不但需要編程計算還要進行處理數模論文中也有很多圖片需要展示，解決這類問題要熟悉MATLAB圖形圖像工具箱。回歸分析回歸分析：對具有相關關系的現象，根據其關系形態，選擇一個合適的數學模型，用來近似地表示變量間的平均變化關系的一種統計方法（一元線性回歸、多元線性回歸、非線性回歸），回歸分析在一組數據的基礎上研究這樣幾個問題：建立因變量與自變量之間的回歸模型（經驗公式）；對回歸模型的可信度進行檢驗；判斷每個自變量對因變量的影響是否顯著；判斷回歸模型是否適合這組數據；利用回歸模型對進行預報或控制。相對應的有線性回歸、多元二項式回歸、非線性回歸。聚類分析聚類分析：所研究的樣本或者變量之間存在程度不同的相似性，要求設法找出一些能夠度量它們之間相似程度的統計量作為分類的依據，再利用這些量將樣本或者變量進行分類。系統聚類分析—將n個樣本或者n個指標看成n類，一類包括一個樣本或者指標，然后將性質最接近的兩類合并成為一個新類，依此類推。最終可以按照需要來決定分多少類，每類有多少樣本（指標）。判別分析判別分析：在已知研究對象分成若干類型，并已取得各種類型的一批已知樣品的觀測數據，在此基礎上根據某些準則建立判別式，然后對未知類型的樣品進行判別分類。距離判別法—首先根據已知分類的數據，分別計算各類的重心，計算新個體到每類的距離，確定最短的距離（歐氏距離、馬氏距離）Fisher判別法—利用已知類別個體的指標構造判別式（同類差別較小、不同類差別較大），按照判別式的值判斷新個體的類別Bayes判別法—計算新給樣品屬于各總體的條件概率，比較概率的大小，然后將新樣品判歸為來自概率最大的總體模糊數學模糊數學：研究和處理模糊性現象的數學（概念與其對立面之間沒有一條明確的分界線）與模糊數學相關的問題：模糊分類問題—已知若干個相互之間不分明的模糊概念，需要判斷某個確定事物用哪一個模糊概念來反映更合理準確；模糊相似選擇

—按某種性質對一組事物或對象排序是一類常見的問題，但是用來比較的性質具有邊界不分明的模糊性；模糊聚類分析—根據研究對象本身的屬性構造模糊矩陣，在此基礎上根據一定的隸屬度來確定其分類關系；模糊層次分析法—兩兩比較指標的確定；模糊綜合評判—綜合評判就是對受到多個因素制約的事物或對象作出一個總的評價，如產品質量評定、科技成果鑒定、某種作物種植適應性的評價等，都屬于綜合評判問題。由于從多方面對事物進行評價難免帶有模糊性和主觀性，采用模糊數學的方法進行綜合評判將使結果盡量客觀從而取得更好的實際效果。時間序列時間序列是按時間順序排列的、隨時間變化且相互關聯的數據序列—通過對預測目標自身時間序列的處理，來研究其變化趨勢（長期趨勢變動、季節變動、循環變動、不規則變動）自回歸模型：一般自回歸模型AR(n)—系統在時刻t的響應X(t)僅與其以前時刻的響應X(t-1),…，X(t-n)有關，而與其以前時刻進入系統的擾動無關；移動平均模型MA(m)—系統在時刻t的響應X(t)

，與其以前任何時刻的響應無關，而與其以前時刻進入系統的擾動a(t-1),…,a(t-m)存在著一定的相關關系；自回歸移動平均模型ARMA(n,m)—系統在時刻t的響應X(t)，不僅與其前n個時刻的自身值有關，而且還與其前m個時刻進入系統的擾動存在一定的依存關系。組隊時應注意的問題通常情況下每隊三個人，（這個大家應該都知道），既然是數學建模，隊員中理論上應該有一位同學是學數學的，另外建模涉及大量的編程計算問題，幾乎每道題都需要編程計算，當然也存在特例是直接用其它軟件導出來的，像今年的國賽題葡萄酒的綜合評價大部分使用spss軟件計算的，但數據預處理中要用到某些編程。所以，最好能有一位具有良好編程能力的隊員，在一個就是思想，這個可以是物理系或其他系的，公認最好的組隊方式是數學+計算機+物理，但其它的方式組隊也可以，（例）這個主要看個隊友之間的磨合了。四、賽前準備一、專業課基礎知識二、建模書籍：數學模型、matlab在數學建模中應用三、軟件：matlab、lingo、lindo、spss、mathtype、DPS等軟件。另外像word、excel等一些計算機基礎課程中的軟件最好能有一些掌握。（從比賽的角度來說一個隊友一名同學精通word