數(shù)學(xué)建模中常用的算法和經(jīng)驗(yàn)

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

—按某種性質(zhì)對(duì)一組事物或?qū)ο笈判蚴且活惓Ｒ姷膯栴}，但是用來比較的性質(zhì)具有邊界不分明的模糊性；模糊聚類分析—根據(jù)研究對(duì)象本身的屬性構(gòu)造模糊矩陣，在此基礎(chǔ)上根據(jù)一定的隸屬度來確定其分類關(guān)系；模糊層次分析法—兩兩比較指標(biāo)的確定；模糊綜合評(píng)判—綜合評(píng)判就是對(duì)受到多個(gè)因素制約的事物或?qū)ο笞鞒鲆粋€(gè)總的評(píng)價(jià)，如產(chǎn)品質(zhì)量評(píng)定、科技成果鑒定、某種作物種植適應(yīng)性的評(píng)價(jià)等，都屬于綜合評(píng)判問題。由于從多方面對(duì)事物進(jìn)行評(píng)價(jià)難免帶有模糊性和主觀性，采用模糊數(shù)學(xué)的方法進(jìn)行綜合評(píng)判將使結(jié)果盡量客觀從而取得更好的實(shí)際效果。時(shí)間序列時(shí)間序列是按時(shí)間順序排列的、隨時(shí)間變化且相互關(guān)聯(lián)的數(shù)據(jù)序列—通過對(duì)預(yù)測目標(biāo)自身時(shí)間序列的處理，來研究其變化趨勢（長期趨勢變動(dòng)、季節(jié)變動(dòng)、循環(huán)變動(dòng)、不規(guī)則變動(dòng)）自回歸模型：一般自回歸模型AR(n)—系統(tǒng)在時(shí)刻t的響應(yīng)X(t)僅與其以前時(shí)刻的響應(yīng)X(t-1),…，X(t-n)有關(guān)，而與其以前時(shí)刻進(jìn)入系統(tǒng)的擾動(dòng)無關(guān)；移動(dòng)平均模型MA(m)—系統(tǒng)在時(shí)刻t的響應(yīng)X(t)

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