數(shù)學建模賽題分析實踐方法與算法

1、第2講 數(shù)學建模賽題分析、實踐方法與算法,數(shù)學與統(tǒng)計學院 李鑫,2024/3/21,2,數(shù)學建模的賽題分析與實踐方法,1. CUMCM歷年賽題的簡析,2. 數(shù)學建模競賽的實踐方法,3. 數(shù)學建模競賽常用方法解析,4. 數(shù)學建模競賽10種常用算法,2024/3/21,3,數(shù)學建模競賽的規(guī)模越來越大,水平越來越高；　競賽的水平主要體現(xiàn)在賽題水平；　賽題的水平主要體現(xiàn)：（１）綜合性、實用性、創(chuàng)新性、即時性等；（２）多種解題方法的創(chuàng)造

2、性、靈活性、開放性等；（３）海量數(shù)據(jù)的復雜性、數(shù)學模型的多樣性、求解結果的不唯一性等。 縱覽20年的本科組40個題目(?？平M21個)，從問題的實際意義、解決問題的方法和題型三個方面作一些簡單的分析。,一、CUMCM歷年賽題的簡析,2024/3/21,4,1. CUMCM 的歷年賽題及解法,1993年:(Ａ)通訊中非線性交調(diào)的頻率設計問題(擬合、規(guī)劃 ) (Ｂ)足球甲級聯(lián)賽排名問題(圖論、層次分析、整數(shù)規(guī)劃 )1

3、994年:(Ａ)山區(qū)修建公路的設計造價問題(圖論、插值、動態(tài)規(guī)劃) (Ｂ)鎖具的制造、銷售和裝箱問題(圖論、組合數(shù)學 )1995年:(Ａ)飛機的安全飛行管理調(diào)度問題(非線性規(guī)劃、線性規(guī)劃) (Ｂ)天車與冶煉爐的作業(yè)調(diào)度問題(動態(tài)規(guī)劃、排隊論、圖論 )1996年:(A)最優(yōu)捕魚策略問題(微分方程、優(yōu)化) (B)節(jié)水洗衣機的程序設計問題(非線性規(guī)劃)1997年:(A)零件參數(shù)優(yōu)化設計問題(非線

4、性規(guī)劃) (B)金剛石截斷切割問題(隨機模擬、圖論),一、CUMCM歷年賽題的簡析,2024/3/21,5,1. CUMCM 的歷年賽題及解法,1998年:(A)投資的收益和風險問題（多目標優(yōu)化、非線性規(guī)劃 ） (B)災情的巡視路線問題（圖論、組合優(yōu)化  ）1999年:(A)自動化機床控制管理問題（隨機優(yōu)化、計算機模擬 ） (B)地質(zhì)堪探鉆井布局問題（0-1規(guī)劃、圖論  ）

5、2000年:(A)DNA序列的分類問題(模式識別、Fisher判別、人工神經(jīng)網(wǎng)絡) (B)鋼管的訂購和運輸問題（組合優(yōu)化、運輸問題）2001年:(A)三維血管的重建問題（曲線擬合、曲面重建 ） (B)公交車的優(yōu)化調(diào)度問題（多目標規(guī)劃 ）2002年:(A)汽車車燈的優(yōu)化設計問題（非線性規(guī)劃） (B)彩票中的數(shù)學問題（單目標決策 ）,一、CUMCM歷年賽題的簡析,2024/3/21,6,1.

6、 CUMCM 的歷年賽題及解法,2003年:(A)SARS的傳播問題（微分方程、差分方程 ） (B)露天礦生產(chǎn)的車輛安排問題（整數(shù)規(guī)劃、運輸問題 ）2004年:(A)奧運會臨時超市網(wǎng)點設計問題(統(tǒng)計分析、數(shù)據(jù)處理、優(yōu)化) (B)電力市場的輸電阻塞管理問題(數(shù)據(jù)擬合、優(yōu)化 ）2005年:(A)長江水質(zhì)的評價與預測問題（ 預測評價、數(shù)據(jù)處理 ） (B)DVD在線租賃問題（ 隨機規(guī)劃、整數(shù)規(guī)劃&#

7、160; ）2006年:(A)出版社的資源管理問題（整數(shù)規(guī)劃、數(shù)據(jù)處理、優(yōu)化 ） (B)艾滋病療法的評價及預測問題（線性規(guī)劃、回歸分析）2007年:(A)中國人口增長預測問題（微分方程、數(shù)據(jù)處理、優(yōu)化 ） (B)“乘公交，看奧運”問題(多目標規(guī)劃、動態(tài)規(guī)劃、圖論、0-1規(guī)劃),一、CUMCM歷年賽題的簡析,2024/3/21,7,2008年:(A)照相機問題 （非線性方程組、優(yōu)化 ）

8、 (B)大學學費問題 （數(shù)據(jù)收集和處理、統(tǒng)計分析、回歸分析 ）2009年:(A)制動器試驗臺的控制方法分析 （物理原理建模、數(shù)值積分、 物理模擬、誤差分析（微分方程、模擬） ） (B)眼科病床的合理安排 （統(tǒng)計分析、排隊論、仿真、隨機優(yōu)化、 模糊綜合評價 ）2010年:(A)儲油罐的變位識別與罐容表標定 (數(shù)

9、據(jù)分析、非線性優(yōu)化、 微積分) (B)2010年上海世博會影響力的定量評估(信息收集、開放性)2011年:(A)城市表層土壤重金屬污染分析 (散亂插值擬合、聚類分析、 主成分分析、偏微分方程) (B)交巡警服務平臺的設置與調(diào)度 (最短路算法、多目標優(yōu)化、 0

10、-1規(guī)劃、啟發(fā)式算法),一、CUMCM歷年賽題的簡析,2024/3/21,8,2、從問題的解決方法上分析,涉及到的數(shù)學建模方法： 幾何理論、組合概率、統(tǒng)計（回歸）分析、優(yōu)化方法(規(guī)劃)、圖論與網(wǎng)絡優(yōu)化、層次分析、插值與擬合、差分計算、微分方程、排隊論、模糊數(shù)學、隨機決策、多目標決策、隨機模擬、灰色系統(tǒng)理論、神經(jīng)網(wǎng)絡、時間序列、綜合評價、機理分析等方法。,一、CUMCM歷年賽題的簡析,2024/3/21,9,3、從問題的題

11、型上分析,一、CUMCM歷年賽題的簡析,賽題題型結構形式有三個基本組成部分：（1）實際問題背景 涉及面寬--有社會，經(jīng)濟，管理，生活，環(huán)境，自然現(xiàn)象，工程技術，現(xiàn)代科學中出現(xiàn)的新問題等。 一般都有一個比較確切的現(xiàn)實問題。 （2）若干假設條件 有如下幾種情況： a. 只有過程、規(guī)則等定性假設，無具體定量數(shù)據(jù)； b. 給出若干實測或統(tǒng)計數(shù)據(jù)； c. 給出若干參數(shù)或圖形； d. 蘊涵著某些機動、可發(fā)揮的

12、補充假設條件，或參賽者可以根據(jù)自己收集或模擬產(chǎn)生數(shù)據(jù)。（3）要求回答的問題 往往有幾個問題（一般不是唯一的答案）: a. 比較確定性的答案（基本答案）；b. 更細致或更高層次的討論結果（往往是討論最優(yōu)方案的提法和結果）。,2024/3/21,10,3、從問題的題型上分析,(1)“即時性”較強的問題(2)理論性較強的問題(3)實用性較強的問題(4)算法要求強的問題(5)數(shù)據(jù)量大的問題,一、CUMCM歷年賽題的簡析,2

13、024/3/21,11,4、近幾年題目的特點,(1)綜合性：一題多解，方法融合，結果多樣，　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　學科交叉。(2)開放性：題意的開放性，思路的開放性，方法的開放性，結果的開放性。(3)實用性：問題和數(shù)據(jù)來自于實際，解決方法切合于

14、實際，模型和結果可以應用于實際。(4)即時性：國內(nèi)外的大事，社會的熱點，生活的焦點，近期發(fā)生和即將發(fā)生被關注的問題。(5)數(shù)據(jù)結構的復雜性：數(shù)據(jù)的真實性，數(shù)據(jù)的海量性，數(shù)據(jù)的不完備性，數(shù)據(jù)的冗余性。,一、CUMCM歷年賽題的簡析,2024/3/21,12,常用數(shù)學模型有哪些？常用數(shù)學建模方法有哪些？參加數(shù)學建模需要具備哪些知識和能力？,二、數(shù)學建模競賽的實踐方法,2024/3/21,13,優(yōu)化模型微分方程模型統(tǒng)計模型概率模

15、型圖論模型決策模型,1、數(shù)學模型分類,二、數(shù)學建模競賽的實踐方法,2024/3/21,14,類比法量綱分析法差分法變分法圖論法層次分析法數(shù)據(jù)擬合法回歸分析法數(shù)學規(guī)劃（線性規(guī)劃，非線性規(guī)劃，整數(shù)規(guī)劃，動態(tài)規(guī)劃，目標規(guī)劃）,2、數(shù)學建模常用的方法,二、數(shù)學建模競賽的實踐方法,2024/3/21,15,機理分析法排隊方法對策方法決策方法模糊評判方法時間序列方法灰色理論方法現(xiàn)代優(yōu)化算法（禁忌搜索算法，模擬退火算

16、法，遺傳算法，神經(jīng)網(wǎng)絡）,二、數(shù)學建模競賽的實踐方法,2、數(shù)學建模常用的方法,2024/3/21,16,3.數(shù)學建模所需要的知識和方法,數(shù)學建模應具備的數(shù)學知識： 高等數(shù)學、微分方程、運籌學、線性代數(shù)、概率統(tǒng)計、數(shù)值計算等。,二、數(shù)學建模競賽的實踐方法,另外還需要了解排隊論、對策論、決策論、模糊數(shù)學、時間序列、灰色理論等相關知識。,2024/3/21,17,問題—給定一批數(shù)據(jù)點（輸入變量與輸出變量的數(shù)據(jù)），確定滿足特定要求的曲線

17、或曲面。插值問題—要求所求曲線（面）通過所給所有數(shù)據(jù)點。數(shù)據(jù)擬合—不要求曲線（面）通過所有數(shù)據(jù)點，而是要求它反映對象整體的變化趨勢。,1、插值與擬合方法,三、數(shù)學建模競賽常用方法解析,2024/3/21,18,一元函數(shù)擬合多項式擬合非線性函數(shù)擬合多元函數(shù)擬合（回歸分析）函數(shù)的確定MATLAB實現(xiàn),（1）數(shù)據(jù)擬合,三、數(shù)學建模競賽常用方法解析,2024/3/21,19,一維插值的定義—已知n個節(jié)點，求任意點處的函數(shù)值。分段

18、線性插值多項式插值 樣條插值 y=interp1(x0,y0,x,'method')二維插值—節(jié)點為網(wǎng)格節(jié)點z=interp2(x0,y0,z0,x,y,'method') pp=csape({x0,y0},z0,conds,valconds) 二維插值—節(jié)點為散點z1=griddata(x,y,z,x1,y1) 散亂數(shù)據(jù)差值（一般需專用的數(shù)據(jù)處理軟件）,（2）插值方法,三、數(shù)學建模競賽

19、常用方法解析,2024/3/21,20,（1）優(yōu)化模型四要素決策變量目標函數(shù)（盡量簡單、光滑）約束條件（建模的關鍵）求解方法 （MATLAB,LINDO）,2、優(yōu)化方法,三、數(shù)學建模競賽常用方法解析,2024/3/21,21,線性規(guī)劃模型（目標函數(shù)和約束條件都是線性函數(shù)的優(yōu)化問題）非線性規(guī)劃模型（目標函數(shù)或者約束條件是非線性的函數(shù)）整數(shù)規(guī)劃（決策變量是整數(shù)值的規(guī)劃問題）多目標規(guī)劃（具有多個目標函數(shù)的規(guī)劃問題）目標規(guī)劃（具

20、有不同優(yōu)先級的目標和偏差的規(guī)劃問題）動態(tài)規(guī)劃（求解多階段決策問題的最優(yōu)化方法）,（2）優(yōu)化模型分類,三、數(shù)學建模競賽常用方法解析,2024/3/21,22,無約束規(guī)劃fminsearchfminbnd線性規(guī)劃linprog非線性規(guī)劃fmincon多目標規(guī)劃（計算有效解）目標加權、效用函數(shù)動態(tài)規(guī)劃（倒向、正向）整數(shù)規(guī)劃（分支定界法、枚舉法、LINDO）,（3）優(yōu)化模型求解,三、數(shù)學建模競賽常用方法解析,2024/3

21、/21,23,回歸分析—對具有相關關系的現(xiàn)象，根據(jù)其關系形態(tài)，選擇一個合適的數(shù)學模型，用來近似地表示變量間的平均變化關系的一種統(tǒng)計方法 （一元線性回歸、多元線性回歸、非線性回歸）回歸分析在一組數(shù)據(jù)的基礎上研究這樣幾個問題：建立因變量與自變量之間的回歸模型（經(jīng)驗公式）對回歸模型的可信度進行檢驗判斷每個自變量對因變量的影響是否顯著判斷回歸模型是否適合這組數(shù)據(jù)利用回歸模型對進行預報或控制[b, bint,r,rint,stats

22、]=regress(Y,X,alpha) （線性回歸）rstool（x，y，’model’, alpha）（多元二項式回歸）[beta,r,J]=nlinfit（x，y，’model’, beta0）（非線性回歸）,3、統(tǒng)計方法,（1）回歸分析,三、數(shù)學建模競賽常用方法解析,2024/3/21,24,逐步回歸分析—從一個自變量開始，視自變量作用的顯著程度，從大到小依次逐個引入回歸方程當引入的自變量由于后面變量的引入而變得不顯著時

23、，要將其剔除掉引入一個自變量或從回歸方程中剔除一個自變量，為逐步回歸的一步對于每一步都要進行值檢驗，以確保每次引入新的顯著性變量前回歸方程中只包含對作用顯著的變量這個過程反復進行，直至既無不顯著的變量從回歸方程中剔除，又無顯著變量可引入回歸方程時為止stepwise(x,y,inmodel,alpha)SPSS,SAS,（2）逐步回歸分析,三、數(shù)學建模競賽常用方法解析,2024/3/21,25,聚類分析—所研究的樣本或者變量之

24、間存在程度不同的相似性，要求設法找出一些能夠度量它們之間相似程度的統(tǒng)計量作為分類的依據(jù)，再利用這些量將樣本或者變量進行分類系統(tǒng)聚類分析—將n個樣本或者n個指標看成n類，一類包括一個樣本或者指標，然后將性質(zhì)最接近的兩類合并成為一個新類，依此類推。最終可以按照需要來決定分多少類，每類有多少樣本（指標）,（3）聚類分析,三、數(shù)學建模競賽常用方法解析,2024/3/21,26,系統(tǒng)聚類方法步驟：計算n個樣本兩兩之間的距離構成n個類，每類只

25、包含一個樣品合并距離最近的兩類為一個新類計算新類與當前各類的距離（新類與當前類的距離等于當前類與組合類中包含的類的距離最小值），若類的個數(shù)等于1，轉5，否則轉3畫聚類圖決定類的個數(shù)和類。,（3）聚類分析,三、數(shù)學建模競賽常用方法解析,2024/3/21,27,判別分析—在已知研究對象分成若干類型，并已取得各種類型的一批已知樣品的觀測數(shù)據(jù)，在此基礎上根據(jù)某些準則建立判別式，然后對未知類型的樣品進行判別分類。距離判別法—首先根據(jù)已

26、知分類的數(shù)據(jù)，分別計算各類的重心，計算新個體到每類的距離，確定最短的距離（歐氏距離、馬氏距離）Fisher判別法—利用已知類別個體的指標構造判別式（同類差別較小、不同類差別較大），按照判別式的值判斷新個體的類別Bayes判別法—計算新給樣品屬于各總體的條件概率，比較概率的大小，然后將新樣品判歸為來自概率最大的總體,（4）判別分析,三、數(shù)學建模競賽常用方法解析,2024/3/21,28,模糊數(shù)學—研究和處理模糊性現(xiàn)象的數(shù)學 （概念與其

27、對立面之間沒有一條明確的分界線）與模糊數(shù)學相關的問題（一）模糊分類問題—已知若干個相互之間不分明的模糊概念，需要判斷某個確定事物用哪一個模糊概念來反映更合理準確模糊相似選擇 —按某種性質(zhì)對一組事物或?qū)ο笈判蚴且活惓Ｒ姷膯栴}，但是用來比較的性質(zhì)具有邊界不分明的模糊性,4、模糊數(shù)學方法,三、數(shù)學建模競賽常用方法解析,2024/3/21,29,模糊聚類分析—根據(jù)研究對象本身的屬性構造模糊矩陣，在此基礎上根據(jù)一定的隸屬度來確定其分類關系

28、模糊層次分析法—兩兩比較指標的確定模糊綜合評判—綜合評判就是對受到多個因素制約的事物或?qū)ο笞鞒鲆粋€總的評價，如產(chǎn)品質(zhì)量評定、科技成果鑒定、某種作物種植適應性的評價等，都屬于綜合評判問題。由于從多方面對事物進行評價難免帶有模糊性和主觀性，采用模糊數(shù)學的方法進行綜合評判將使結果盡量客觀從而取得更好的實際效果,4、模糊數(shù)學方法,三、數(shù)學建模競賽常用方法解析,2024/3/21,30,時間序列是按時間順序排列的、隨時間變化且相互關聯(lián)的數(shù)據(jù)序

29、列—通過對預測目標自身時間序列的處理，來研究其變化趨勢（長期趨勢變動、季節(jié)變動、循環(huán)變動、不規(guī)則變動） 自回歸模型一般自回歸模型AR(n)—系統(tǒng)在時刻t的響應X(t)僅與其以前時刻的響應X(t-1),…， X(t-n)有關，而與其以前時刻進入系統(tǒng)的擾動無關 移動平均模型MA(m)—系統(tǒng)在時刻t的響應X(t) ，與其以前任何時刻的響應無關，而與其以前時刻進入系統(tǒng)的擾動a(t-1),…,a(t-m)存在著一定的相關關系 自回歸移動平

30、均模型 ARMA(n,m)—系統(tǒng)在時刻t的響應X(t)，不僅與其前n個時刻的自身值有關，而且還與其前m個時刻進入系統(tǒng)的擾動存在一定的依存關系,5、時間序列分析方法,三、數(shù)學建模競賽常用方法解析,2024/3/21,31,數(shù)據(jù)的預處理：數(shù)據(jù)的剔取及提取趨勢項取n=1，擬合ARMA(2n,2n-1)（即ARMA(2,1)）模型n=n+1，擬合ARMA(2n,2n-1)模型用F準則檢驗模型的適用性。若檢驗顯著，則轉入第2步。若檢驗不顯著

31、，轉入第5步。檢查遠端時刻的系數(shù)值的值是否很小，其置信區(qū)間是否包含零。若不是，則適用的模型就是ARMA(2n,2n-1) 。若很小，且其置信區(qū)間包含零，則擬合ARMA(2n-1,2n-2) 。,5、時間序列分析方法,時間序列建模的基本步驟：,三、數(shù)學建模競賽常用方法解析,2024/3/21,32,利用F準則檢驗模型ARMA(2n,2n-1)和ARMA(2n-1,2n-2) ，若F值不顯著，轉入第7步；若F值顯著，轉入第8步。舍棄小的

32、MA參數(shù)，擬合m<2n-2的模型ARMA(2n-1,m) ，并用F準則進行檢驗。重復這一過程，直到得出具有最小參數(shù)的適用模型為止舍棄小的MA參數(shù)，擬合m<2n-1的模型ARMA(2n,m) ，并用F準則進行檢驗。重復這一過程，直到得出具有最小參數(shù)的適用模型為止。,時間序列建模的基本步驟：,三、數(shù)學建模競賽常用方法解析,2024/3/21,33,最短路問題兩個指定頂點之間的最短路徑—給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡，在這

33、個網(wǎng)絡的兩個指定城鎮(zhèn)間，找一條最短鐵路線 （Dijkstra算法 ）每對頂點之間的最短路徑 （Dijkstra算法、Floyd算法 ）最小生成樹問題連線問題—欲修筑連接多個城市的鐵路設計一個線路圖，使總造價最低（prim算法、Kruskal算法 ）圖的匹配問題人員分派問題：n個工作人員去做件n份工作，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？(匈牙利算法),6、圖論方法,三、數(shù)

34、學建模競賽常用方法解析,2024/3/21,34,遍歷性問題中國郵遞員問題—郵遞員發(fā)送郵件時，要從郵局出發(fā)，經(jīng)過他投遞范圍內(nèi)的每條街道至少一次，然后返回郵局，但郵遞員希望選擇一條行程最短的路線最大流問題運輸問題最小費用最大流問題在運輸問題中，人們總是希望在完成運輸任務的同時，尋求一個使總的運輸費用最小的運輸方案,6、圖論方法,三、數(shù)學建模競賽常用方法解析,2024/3/21,35,（1）蒙特卡羅算法 大多數(shù)建模賽題

35、中都離不開計算機仿真，隨機性模擬是非常常見的算法之一。 舉個例子就是97 年的A 題，每個零件都有自己的標定值，也都有自己的容差等級，而求解最優(yōu)的組合方案將要面對著的是一個極其復雜的公式和108 種容差選取方案，根本不可能去求解析解，那如何去找到最優(yōu)的方案呢？隨機性模擬搜索最優(yōu)方案就是其中的一種方法，在每個零件可行的區(qū)間中按照正態(tài)分布隨機的選取一個標定值和選取一個容差值作為一種方案，然后通過蒙特卡羅算法仿真出大量的方案，從中

36、選取一個最佳的。另一個例子就是2002年的彩票第二問，要求設計一種更好的方案，首先方案的優(yōu)劣取決于很多復雜的因素，同樣不可能刻畫出一個模型進行求解，只能靠隨機仿真模擬。,四、數(shù)學建模競賽10種常用算法,2024/3/21,36,（2）數(shù)據(jù)擬合、參數(shù)估計、插值等數(shù)據(jù)處理算法 比賽中通常會遇到大量的數(shù)據(jù)需要處理，而處理數(shù)據(jù)的關鍵就在于這些算法，通常使用Matlab作為工具 數(shù)據(jù)擬合在很多賽題中有應用，與

37、圖形處理有關的問題很多與擬合有關系，一個例子就是98 年美國賽A 題，生物組織切片的三維插值處理，94 年A 題逢山開路，山體海拔高度的插值計算，還有吵的沸沸揚揚可能會考的“非典”問題也要用到數(shù)據(jù)擬合算法，觀察數(shù)據(jù)的走向進行處理。此類問題在MATLAB中有很多現(xiàn)成的函數(shù)可以調(diào)用，熟悉MATLAB，這些方法都能游刃有余的用好。,四、數(shù)學建模競賽10種常用算法,2024/3/21,37,（3）線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類問

38、題 建模競賽大多數(shù)問題屬于最優(yōu)化問題，很多時候這些問題可以用數(shù)學規(guī)劃算法來描述，通常使用Lindo、Lingo軟件實現(xiàn) 競賽中很多問題都和數(shù)學規(guī)劃有關，可以說不少的模型都可以歸結為一組不等式作為約束條件、幾個函數(shù)表達式作為目標函數(shù)的問題，遇到這類問題，求解就是關鍵了，比如98年B 題，用很多不等式完全可以把問題刻畫清楚，因此列舉出規(guī)劃后用Lindo、Lingo 等軟件來進行解決比較方便，所以還需要熟

39、悉這兩個軟件。,四、數(shù)學建模競賽10種常用算法,2024/3/21,38,（4）圖論算法 這類算法可以分為很多種，包括最短路、網(wǎng)絡流、二分圖等算法，涉及到圖論的問題可以用這些方法解決，需要認真準備 98 年B 題、00 年B 題、95 年鎖具裝箱等問題體現(xiàn)了圖論問題的重要性，這類問題算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等問題。每一個算法

40、都應實現(xiàn)一遍，否則到比賽時再寫就晚了。,四、數(shù)學建模競賽10種常用算法,2024/3/21,39,（5）動態(tài)規(guī)劃、回溯搜索、分治算法、分支定界等計算機算法 這些算法是算法設計中比較常用的方法，很多場合可以用到競賽中。 比如92 年B 題用分枝定界法，97 年B 題是典型的動態(tài)規(guī)劃問題，此外98 年B 題體現(xiàn)了分治算法。這方面問題和ACM 程序設計競賽中的問題類似，推薦看一下《計算機算法設計與分析》（電子工業(yè)出版社）等

41、與計算機算法有關的書。,四、數(shù)學建模競賽10種常用算法,2024/3/21,40,（6）最優(yōu)化理論的三大非經(jīng)典算法：模擬退火法、神經(jīng)網(wǎng)絡、遺傳算法 這些問題是用來解決一些較困難的最優(yōu)化問題的算法，對于有些問題非常有幫助，但是算法的實現(xiàn)比較困難，需慎重使用。 比如：97 年A 題的模擬退火算法，00 年B 題的神經(jīng)網(wǎng)絡分類算法，象01 年B 題這種難題也可以使用神經(jīng)網(wǎng)絡，還有美國競賽89 年A 題也和BP 算法有關系，

42、當時是86 年剛提出BP 算法，89 年就考了，說明賽題可能是當今前沿科技的抽象體現(xiàn)。03 年B 題伽馬刀問題也是目前研究的課題，目前算法最佳的是遺傳算法。,四、數(shù)學建模競賽10種常用算法,2024/3/21,41,（7）數(shù)值分析算法 如果在比賽中采用高級語言進行編程的話，那一些數(shù)值分析中常用的算法比如方程組求解、矩陣運算、函數(shù)積分等算法就需要額外編寫庫函數(shù)進行調(diào)用 這類算法是針對高級語言而專門設的，如果你用

43、的是MATLAB、Mathematica，大可不必準備，因為象數(shù)值分析中有很多函數(shù)一般的數(shù)學軟件是具備的。,四、數(shù)學建模競賽10種常用算法,2024/3/21,42,（8）一些連續(xù)離散化方法 很多問題都是實際來的，數(shù)據(jù)可以是連續(xù)的，而計算機只認的是離散的數(shù)據(jù)，因此將其離散化后運用差分代替微分、求和代替積分等思想是非常重要的 大部分物理問題的編程解決，都和這種方法有一定的聯(lián)系。物理問題是反映我們生活在一個連續(xù)的世

44、界中，計算機只能處理離散的量，所以需要對連續(xù)量進行離散處理。這種方法應用很廣，而且和上面的很多算法有關。事實上，網(wǎng)格算法、蒙特卡羅算法、模擬退火都用了這個思想。,四、數(shù)學建模競賽10種常用算法,2024/3/21,43,（9）網(wǎng)格算法和窮舉法 網(wǎng)格算法和窮舉法都是暴力搜索最優(yōu)點的算法，在很多競賽題中有應用，當重點討論模型本身而輕視算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具 網(wǎng)格算法和窮舉

45、法一樣，只是網(wǎng)格法是連續(xù)問題的窮舉。比如要求在N 個變量情況下的最優(yōu)化問題，那么對這些變量可取的空間進行采點。 比如97 年A 題、99 年B 題都可以用網(wǎng)格法搜索，這種方法最好在運算速度較快的計算機中進行，還有要用高級語言來做，最好不要用MATLAB 做網(wǎng)格，否則會算很久的。,四、數(shù)學建模競賽10種常用算法,2024/3/21,44,（10）圖象處理算法 賽題中有一類問題與圖形有關，即使與圖形無關，論文中也應該

46、要不乏圖片的，這些圖形如何展示以及如何處理就是需要解決的問題，通常使用Matlab進行處理 01年A 題中需要你會讀BMP 圖象、美國賽98 年A 題需要你知道三維插值計算，03 年B 題要求更高，不但需要編程計算還要進行處理，而數(shù)模論文中也有很多圖片需要展示，因此圖象處理就是關鍵。做好這類問題，重要的是把MATLAB 學好，特別是圖象處理的部分。,四、數(shù)學建模競賽10種常用算法,2024/3/21,45,平等地位、相互尊重、

47、充分交流杜絕武斷評價不要回避責任不要對交流失去信心,競賽中的群體思維方法,2024/3/21,46,借助于一系列問題來展開思路這個問題與什么問題相似？如果將問題分解成兩個或幾個部分會怎樣？極限情形（或理想狀態(tài)）如何？綜合問題的條件可得到什么結果？要實現(xiàn)問題的目標需要什么條件？借助于下意識的聯(lián)想（靈感）來展開思路抓住問題的個別條件或關鍵詞展開聯(lián)想或猜想綜合所得到的聯(lián)想和猜想，得到一些結論進一步思考找出新思路和方法,