數(shù)學(xué)建模常用方法介紹

1、數(shù)學(xué)建模常用方法介紹數(shù)學(xué)建模常用方法介紹l 1983年，數(shù)學(xué)建模作為一門獨立的課程進年，數(shù)學(xué)建模作為一門獨立的課程進入我國高等學(xué)校，在清華大學(xué)首次開設(shè)。入我國高等學(xué)校，在清華大學(xué)首次開設(shè)。1987年高等教育出版社出版了國內(nèi)第一本年高等教育出版社出版了國內(nèi)第一本數(shù)學(xué)模數(shù)學(xué)模型型教材。教材。20多年來，數(shù)學(xué)建模工作發(fā)展的非多年來，數(shù)學(xué)建模工作發(fā)展的非常快，許多高校相繼開設(shè)了數(shù)學(xué)建模課程，我?？?，許多高校相繼開設(shè)了數(shù)學(xué)建模課程，我國從國從1989年起參加美國數(shù)學(xué)建模競賽，年起參加美國數(shù)學(xué)建模競賽，1992年年國家教委高教司提出在全國普通高等學(xué)校開展國家教委高教司提出在全國普通高等學(xué)校開展數(shù)學(xué)建模競賽

2、，旨在數(shù)學(xué)建模競賽，旨在“培養(yǎng)學(xué)生解決實際問題培養(yǎng)學(xué)生解決實際問題的能力和創(chuàng)新精神，全面提高學(xué)生的綜合素的能力和創(chuàng)新精神，全面提高學(xué)生的綜合素質(zhì)質(zhì)”。數(shù)學(xué)建模常用方法介紹l 我校在我校在1998年之前就為數(shù)學(xué)與應(yīng)用數(shù)學(xué)專年之前就為數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)學(xué)生開設(shè)了數(shù)學(xué)建模課程（當時由葉淼林教業(yè)學(xué)生開設(shè)了數(shù)學(xué)建模課程（當時由葉淼林教授主講，后改為蘇本躍博士主講），并于授主講，后改為蘇本躍博士主講），并于1998年參加全國大學(xué)生數(shù)學(xué)建模競賽。在年參加全國大學(xué)生數(shù)學(xué)建模競賽。在2007年擴年擴大到信息與計算科學(xué)專業(yè)（劉兵兵講師主）。大到信息與計算科學(xué)專業(yè)（劉兵兵講師主）。同年，又把數(shù)學(xué)建模課增設(shè)為全校公選

3、課，授同年，又把數(shù)學(xué)建模課增設(shè)為全校公選課，授課對象為四個院系的學(xué)生課對象為四個院系的學(xué)生,即：數(shù)學(xué)與計算科學(xué)即：數(shù)學(xué)與計算科學(xué)學(xué)院、計算機與信息學(xué)院、物理與電氣工程學(xué)學(xué)院、計算機與信息學(xué)院、物理與電氣工程學(xué)院和經(jīng)濟與管理學(xué)院，授課教師共有院和經(jīng)濟與管理學(xué)院，授課教師共有4位不同位不同方向的數(shù)學(xué)教師。同時還指導(dǎo)本科生撰寫數(shù)學(xué)方向的數(shù)學(xué)教師。同時還指導(dǎo)本科生撰寫數(shù)學(xué)建模方向的畢業(yè)論文。建模方向的畢業(yè)論文。數(shù)學(xué)建模常用方法介紹 十多年來，數(shù)學(xué)建模課程的教學(xué)十多年來，數(shù)學(xué)建模課程的教學(xué)使學(xué)生在知識的滲透和交叉方面使學(xué)生在知識的滲透和交叉方面,使學(xué)使學(xué)生和教師的知識結(jié)構(gòu)得到了更新和完生和教師的知識結(jié)構(gòu)

4、得到了更新和完善善,同時也促進了數(shù)學(xué)學(xué)科和其它學(xué)科同時也促進了數(shù)學(xué)學(xué)科和其它學(xué)科的交流。學(xué)生應(yīng)用數(shù)學(xué)和計算機解決的交流。學(xué)生應(yīng)用數(shù)學(xué)和計算機解決實際問題的能力得到了提高。學(xué)生的實際問題的能力得到了提高。學(xué)生的綜合素質(zhì)在畢業(yè)論文、讀研究生和以綜合素質(zhì)在畢業(yè)論文、讀研究生和以后的工作中充分體現(xiàn)出來。后的工作中充分體現(xiàn)出來。數(shù)學(xué)建模常用方法介紹 我校在全國大學(xué)生數(shù)學(xué)建模競賽中我校在全國大學(xué)生數(shù)學(xué)建模競賽中取得了較好的成績，自從取得了較好的成績，自從1998年參加比賽年參加比賽以來，累計共有以來，累計共有1隊獲得國家級一等獎，隊獲得國家級一等獎，1隊獲得國家級二等獎，隊獲得國家級二等獎，2隊獲得安徽賽

5、區(qū)一隊獲得安徽賽區(qū)一等獎，等獎，16隊獲得安徽賽區(qū)二等獎，隊獲得安徽賽區(qū)二等獎，10隊獲隊獲得安徽賽區(qū)三等獎，其余均獲得成功參賽得安徽賽區(qū)三等獎，其余均獲得成功參賽獎。獎。數(shù)學(xué)建模常用方法介紹三類最基本的必備知識三類最基本的必備知識運籌學(xué)（運籌學(xué)（MATLAB or LINDNO/LINGO）多元統(tǒng)計分析（多元統(tǒng)計分析（SPSS）微分方程微分方程(MATLAB)數(shù)學(xué)建模常用方法介紹類比法類比法量綱分析法量綱分析法差分法差分法變分法變分法圖論法圖論法層次分析法層次分析法數(shù)據(jù)擬合法數(shù)據(jù)擬合法回歸分析法回歸分析法數(shù)學(xué)規(guī)劃（線性規(guī)劃，非線性規(guī)劃，整數(shù)規(guī)數(shù)學(xué)規(guī)劃（線性規(guī)劃，非線性規(guī)劃，整數(shù)規(guī)劃，動態(tài)規(guī)劃

6、，目標規(guī)劃）劃，動態(tài)規(guī)劃，目標規(guī)劃）數(shù)學(xué)建模常用方法介紹機理分析法機理分析法排隊方法排隊方法對策方法對策方法決策方法決策方法模糊評判方法模糊評判方法時間序列方法時間序列方法灰色理論方法灰色理論方法現(xiàn)代優(yōu)化算法（禁忌搜索算法，模擬退火現(xiàn)代優(yōu)化算法（禁忌搜索算法，模擬退火算法，遺傳算法，神經(jīng)網(wǎng)絡(luò)）算法，遺傳算法，神經(jīng)網(wǎng)絡(luò)）數(shù)學(xué)建模常用方法介紹優(yōu)化模型優(yōu)化模型微分方程模型微分方程模型統(tǒng)計模型統(tǒng)計模型概率模型概率模型圖論模型圖論模型決策模型決策模型數(shù)學(xué)建模常用方法介紹問題問題給定一批數(shù)據(jù)點（輸入變量與輸出變量的數(shù)據(jù)），需確定滿足特定要求的曲線或曲面插值問題插值問題要求所求曲線（面）通過所給所有數(shù)據(jù)點數(shù)

7、據(jù)擬合數(shù)據(jù)擬合不要求曲線（面）通過所有數(shù)據(jù)點，而是要求它反映對象整體的變化趨勢數(shù)學(xué)建模常用方法介紹一元函數(shù)擬合多項式擬合非線性函數(shù)擬合多元函數(shù)擬合（回歸分析）MATLAB實現(xiàn)函數(shù)的確定數(shù)學(xué)建模常用方法介紹一維插值的定義已知n個節(jié)點，求任意點處的函數(shù)值。分段線性插值多項式插值 樣條插值 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ù)學(xué)建模常用方法介紹優(yōu)化模型四要素決策變量目

8、標函數(shù)（盡量簡單、光滑）約束條件（建模的關(guān)鍵）求解方法 （MATLAB,LINDO）數(shù)學(xué)建模常用方法介紹線性規(guī)劃模型（目標函數(shù)和約束條件都是線性函數(shù)的優(yōu)化問題）非線性規(guī)劃模型（目標函數(shù)或者約束條件是非線性的函數(shù)）整數(shù)規(guī)劃（決策變量是整數(shù)值得規(guī)劃問題）多目標規(guī)劃（具有多個目標函數(shù)的規(guī)劃問題）目標規(guī)劃（具有不同優(yōu)先級的目標和偏差的規(guī)劃問題）動態(tài)規(guī)劃（求解多階段決策問題的最優(yōu)化方法） 數(shù)學(xué)建模常用方法介紹無約束規(guī)劃fminsearchfminbnd線性規(guī)劃linprog非線性規(guī)劃fmincon多目標規(guī)劃（計算有效解）目標加權(quán)、效用函數(shù)動態(tài)規(guī)劃（倒向、正向）整數(shù)規(guī)劃（分支定界法、枚舉法、LINDO）數(shù)

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

10、beta0）（非線性回歸）數(shù)學(xué)建模常用方法介紹逐步回歸分析逐步回歸分析從一個自變量開始，視自變量作用的顯著程度，從大到地依次逐個引入回歸方程當引入的自變量由于后面變量的引入而變得不顯著時，要將其剔除掉 引入一個自變量或從回歸方程中剔除一個自變量，為逐步回歸的一步對于每一步都要進行值檢驗，以確保每次引入新的顯著性變量前回歸方程中只包含對作用顯著的變量這個過程反復(fù)進行，直至既無不顯著的變量從回歸方程中剔除，又無顯著變量可引入回歸方程時為止stepwise(x,y,inmodel,alpha)SPSS,SAS數(shù)學(xué)建模常用方法介紹聚類分析所研究的樣本或者變量之間存在程度不同的相似性，要求設(shè)法找出一些能

11、夠度量它們之間相似程度的統(tǒng)計量作為分類的依據(jù)，再利用這些量將樣本或者變量進行分類系統(tǒng)聚類分析將n個樣本或者n個指標看成n類，一類包括一個樣本或者指標，然后將性質(zhì)最接近的兩類合并成為一個新類，依此類推。最終可以按照需要來決定分多少類，每類有多少樣本（指標）數(shù)學(xué)建模常用方法介紹系統(tǒng)聚類方法步驟：計算n個樣本兩兩之間的距離構(gòu)成n個類，每類只包含一個樣品合并距離最近的兩類為一個新類計算新類與當前各類的距離（新類與當前類的距離等于當前類與組合類中包含的類的距離最小值），若類的個數(shù)等于1，轉(zhuǎn)5，否則轉(zhuǎn)3畫聚類圖1.決定類的個數(shù)和類。數(shù)學(xué)建模常用方法介紹判別分析在已知研究對象分成若干類型，并已取得各種類型的

12、一批已知樣品的觀測數(shù)據(jù)，在此基礎(chǔ)上根據(jù)某些準則建立判別式，然后對未知類型的樣品進行判別分類。距離判別法首先根據(jù)已知分類的數(shù)據(jù)，分別計算各類的重心，計算新個體到每類的距離，確定最短的距離（歐氏距離、馬氏距離）Fisher判別法利用已知類別個體的指標構(gòu)造判別式（同類差別較小、不同類差別較大），按照判別式的值判斷新個體的類別Bayes判別法計算新給樣品屬于各總體的條件概率，比較概率的大小，然后將新樣品判歸為來自概率最大的總體 數(shù)學(xué)建模常用方法介紹模糊數(shù)學(xué)研究和處理模糊性現(xiàn)象的數(shù)學(xué) （概念與其對立面之間沒有一條明確的分界線）與模糊數(shù)學(xué)相關(guān)的問題（一）模糊分類問題已知若干個相互之間不分明的模糊概念，需要

13、判斷某個確定事物用哪一個模糊概念來反映更合理準確模糊相似選擇 按某種性質(zhì)對一組事物或?qū)ο笈判蚴且活惓Ｒ姷膯栴}，但是用來比較的性質(zhì)具有邊界不分明的模糊性數(shù)學(xué)建模常用方法介紹模糊聚類分析根據(jù)研究對象本身的屬性構(gòu)造模糊矩陣，在此基礎(chǔ)上根據(jù)一定的隸屬度來確定其分類關(guān)系 模糊層次分析法兩兩比較指標的確定模糊綜合評判綜合評判就是對受到多個因素制約的事物或?qū)ο笞鞒鲆粋€總的評價，如產(chǎn)品質(zhì)量評定、科技成果鑒定、某種作物種植適應(yīng)性的評價等，都屬于綜合評判問題。由于從多方面對事物進行評價難免帶有模糊性和主觀性，采用模糊數(shù)學(xué)的方法進行綜合評判將使結(jié)果盡量客觀從而取得更好的實際效果 數(shù)學(xué)建模常用方法介紹最短路問題兩個指

14、定頂點之間的最短路徑給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個網(wǎng)絡(luò)的兩個指定城鎮(zhèn)間，找一條最短鐵路線 （Dijkstra算法 ）每對頂點之間的最短路徑 （Dijkstra算法、Floyd算法 ）最小生成樹問題連線問題欲修筑連接多個城市的鐵路設(shè)計一個線路圖，使總造價最低（prim算法、Kruskal算法 ）圖的匹配問題人員分派問題：n個工作人員去做件n份工作，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？(匈牙利算法)數(shù)學(xué)建模常用方法介紹遍歷性問題中國郵遞員問題郵遞員發(fā)送郵件時，要從郵局出發(fā)，經(jīng)過他投遞范圍內(nèi)的每條街道至少一次，然后返回郵局，但郵遞員

15、希望選擇一條行程最短的路線最大流問題運輸問題最小費用最大流問題在運輸問題中，人們總是希望在完成運輸任務(wù)的同時，尋求一個使總的運輸費用最小的運輸方案 數(shù)學(xué)建模常用方法介紹 80年代初開始興起的啟發(fā)式算法，包括年代初開始興起的啟發(fā)式算法，包括禁忌搜索（禁忌搜索（tabu search），），模擬退火模擬退火（simulated annealing, SA），），遺傳算法遺傳算法（genetic algorithm, GA），蟻群算法），蟻群算法（ant colony algorithm, ANA），人工神經(jīng)），人工神經(jīng)網(wǎng)絡(luò)（網(wǎng)絡(luò)（neural network, NN）等等，用于解）等等，用于解決大

16、量的實際應(yīng)用問題。決大量的實際應(yīng)用問題。數(shù)學(xué)建模常用方法介紹 基于生物遺傳學(xué)和進化論所構(gòu)造的一基于生物遺傳學(xué)和進化論所構(gòu)造的一類搜索算法。對生物進化過程進行了數(shù)學(xué)類搜索算法。對生物進化過程進行了數(shù)學(xué)仿真，體現(xiàn)了自然界中仿真，體現(xiàn)了自然界中“物競天擇、適者物競天擇、適者生生存存”的進化過程。的進化過程。數(shù)學(xué)建模常用方法介紹l遺傳算法把問題的解表示成個體（遺傳算法把問題的解表示成個體（染色染色體體），并基于適應(yīng)值來選擇染色體，使），并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機會。適應(yīng)性好的染色體有更多的繁殖機會。通過染色體群一代一代的進化，獲得適通過染色體群一代一代的進化，獲得適應(yīng)環(huán)

17、境的最優(yōu)解。應(yīng)環(huán)境的最優(yōu)解。Holland, Adaptation in Natural and Artificial Systems, 1975 數(shù)學(xué)建模常用方法介紹l個體個體（individual） 問題的解問題的解 染色體染色體（chromosome）：解的編碼）：解的編碼 基因基因（gene）：解中各分量的值）：解中各分量的值l適應(yīng)性適應(yīng)性（fitness） 適應(yīng)函數(shù)值適應(yīng)函數(shù)值l群體群體（population） 選定的一組解選定的一組解數(shù)學(xué)建模常用方法介紹l種群種群（reproduction） 根據(jù)適應(yīng)函數(shù)值選取的一組解根據(jù)適應(yīng)函數(shù)值選取的一組解l交配交配（crossover） 通過

18、交配原則產(chǎn)生一組新解的過程通過交配原則產(chǎn)生一組新解的過程l變異變異（mutation） 編碼的某一個分量發(fā)生變化的過程編碼的某一個分量發(fā)生變化的過程l適者生存適者生存 算法停止時，最有可能存活的是最優(yōu)解算法停止時，最有可能存活的是最優(yōu)解數(shù)學(xué)建模常用方法介紹1.1.編碼與譯碼編碼與譯碼編碼編碼：將問題結(jié)構(gòu)變換為位串形式編碼表示的：將問題結(jié)構(gòu)變換為位串形式編碼表示的 染色體染色體 譯碼譯碼：將染色體表示變換為原問題結(jié)構(gòu)。：將染色體表示變換為原問題結(jié)構(gòu)。2.2.適應(yīng)度函數(shù)適應(yīng)度函數(shù)對染色體對染色體適應(yīng)性適應(yīng)性進行度量的函數(shù)。通過適應(yīng)度進行度量的函數(shù)。通過適應(yīng)度函數(shù)來決定染色體的優(yōu)劣程度，體現(xiàn)了自然進

19、函數(shù)來決定染色體的優(yōu)劣程度，體現(xiàn)了自然進化中的化中的優(yōu)勝劣汰原則優(yōu)勝劣汰原則。適應(yīng)度函數(shù)的取值大小。適應(yīng)度函數(shù)的取值大小與求解問題對象的意義有很大的關(guān)系。對優(yōu)化與求解問題對象的意義有很大的關(guān)系。對優(yōu)化問題，適應(yīng)度函數(shù)就是目標函數(shù)。問題，適應(yīng)度函數(shù)就是目標函數(shù)。數(shù)學(xué)建模常用方法介紹3. 遺傳操作遺傳操作 簡單遺傳算法簡單遺傳算法的遺傳操作主要有三種的遺傳操作主要有三種:選擇選擇(selection)、交叉、交叉(crossover)、變異、變異(mutation)。 改進的遺傳算法改進的遺傳算法大量擴充了遺傳操作大量擴充了遺傳操作。(1) 選擇，也叫復(fù)制選擇，也叫復(fù)制 從群體中按個體的適應(yīng)度函數(shù)

20、值選擇出較適應(yīng)環(huán)境的個體，從群體中按個體的適應(yīng)度函數(shù)值選擇出較適應(yīng)環(huán)境的個體，使適應(yīng)度高的個體繁殖下一代的數(shù)目較多，而適應(yīng)度較小的個使適應(yīng)度高的個體繁殖下一代的數(shù)目較多，而適應(yīng)度較小的個體，繁殖下一代的數(shù)目較少體，繁殖下一代的數(shù)目較少,甚至被淘汰。甚至被淘汰。 輪盤賭輪盤賭(roulette wheel)模型模型：個體被選擇的概率等于其適應(yīng)度值與群體總適應(yīng)：個體被選擇的概率等于其適應(yīng)度值與群體總適應(yīng)度值之比。度值之比。 例：例： Fitness 值：值： 2200 1800 1200 950 400 100數(shù)學(xué)建模常用方法介紹（2）交叉）交叉(Crossover) 將被選中的兩個個體的基因鏈按一定概率進行交將被選中的兩個個體的基因鏈按一定概率進行交叉，生成兩個新的個體，交叉位置是隨機的。叉，生成兩個新的個體，交叉位置是隨機的。 分分為單點交叉、雙點交叉、均勻交叉為單點交叉、雙點交叉、均勻交叉.單點交叉單點交叉操作的簡單方式是將兩個個體作為父母個操作的簡單方式是將兩個個體作為父母個體，將兩者的部分基因碼值進行交換。體，將兩者的部分基因碼值進行交換。例例: 數(shù)學(xué)建模常用方法介紹(3) 變異變異(Mutation) 在在被選中被選中的個體中，將其基因鏈的各位按概的個體中，將其基因鏈的各位按概率進行異向轉(zhuǎn)化，得到新的個體