數(shù)學建模常用的十種解題方法

1、 數(shù)學建模常用的十種解題方法 摘要 當需要從定量的角度分析和研究一個實際問題時，人們就要在深入調查研究、了解對象信息、作出簡化假設、分析內在規(guī)律等工作的基礎上，用數(shù)學的符號和語言，把它表述為數(shù)學式子，也就是數(shù)學模型，然后用通過計算得到的模型結果來解釋實際問題，并接受實際的檢驗。這個建立數(shù)學模型的全過程就稱為數(shù)學建模。數(shù)學建模的十種常用方法有蒙特卡羅算法；數(shù)據(jù)擬合、參數(shù)估計、插值等數(shù)據(jù)處理算法；解決線性規(guī)劃、整數(shù)規(guī)劃、多元規(guī)劃、二次規(guī)劃等規(guī)劃類問題的數(shù)學規(guī)劃算法；圖論算法；動態(tài)規(guī)劃、回溯搜索、分治算法、分支定界等計算機算法；最優(yōu)化理論的三大非經(jīng)典算法：模擬退火法、神經(jīng)網(wǎng)絡、遺傳算法；網(wǎng)格算法和窮

2、舉法；一些連續(xù)離散化方法；數(shù)值分析算法；圖象處理算法。關鍵詞：數(shù)學建模；蒙特卡羅算法；數(shù)據(jù)處理算法；數(shù)學規(guī)劃算法；圖論算法 一、蒙特卡羅算法蒙特卡羅算法又稱隨機性模擬算法，是通過計算機仿真來解決問題的算法，同時可以通過模擬可以來檢驗自己模型的正確性，是比賽時必用的方法。在工程、通訊、金融等技術問題中, 實驗數(shù)據(jù)很難獲取, 或實驗數(shù)據(jù)的獲取需耗費很多的人力、物力, 對此, 用計算機隨機模擬就是最簡單、經(jīng)濟、實用的方法; 此外, 對一些復雜的計算問題, 如非線性議程組求解、最優(yōu)化、積分微分方程及一些偏微分方程的解, 蒙特卡羅方法也是非常有效的。一般情況下, 蒙特卜羅算法在二重積分中用均勻隨機數(shù)計算

3、積分比較簡單, 但精度不太理想。通過方差分析, 論證了利用有利隨機數(shù), 可以使積分計算的精度達到最優(yōu)。本文給出算例, 并用MA TA LA B實現(xiàn)。1蒙特卡羅計算重積分的最簡算法-均勻隨機數(shù)法二重積分的蒙特卡羅方法(均勻隨機數(shù)) 實際計算中常常要遇到如的二重積分, 也常常發(fā)現(xiàn)許多時候被積函數(shù)的原函數(shù)很難求出, 或者原函數(shù)根本就不是初等函數(shù), 對于這樣的重積分, 可以設計一種蒙特卡羅的方法計算。 定理1 設式區(qū)域D 上的有界函數(shù), 用均勻隨機數(shù)計算的方法:(l) 取一個包含D 的矩形區(qū)域,a x b, c y d , 其面積A =(b 一a) (d 一c) ;,i=1,n在上的均勻分布隨機數(shù)列,

4、不妨設, j=1，k為落在D 中的k個隨機數(shù), 則n 充分大時, 有定理2 用定理1的公式（1）作近似計算時，其方差為證略。 2 蒙特卡羅計算重積分的一般方法-任意隨機數(shù)法2.1 二重積分的蒙特卡羅算法(一般隨機數(shù))定理3 設區(qū)域D上的有界函數(shù)，用一般的隨機數(shù)計算的方法：(l) 取一個包含D 的矩形區(qū)域,a x b, c y d , 其面積A =(b 一a) (d 一c) ;取任一概率密度函數(shù)，滿足；，i=1,n,是以為概率密度的隨機數(shù)列，設，i-1,k,為落在D中的隨機數(shù)，則n充分大時，有證略。3 蒙特卡羅計算重積分的最優(yōu)算法有利隨機數(shù)法 任意隨機數(shù)都能用于積分計算, 對于不同的隨機數(shù), 計

5、算結果的方差顯然不同, 在定理3 中, 取時，計算方差為零,即方差最小，稱為有利密度函數(shù)，以為概率密度的隨機數(shù)稱為有利隨機數(shù)。這樣得到方差最優(yōu)的蒙特卡羅算法, 敘述如下:定理5 根據(jù)二重積分的最優(yōu)蒙特卡羅算法(有利隨機數(shù)), 設區(qū)域D上的有界函數(shù)，0，那么按如下步驟得到方差最優(yōu)值。(l) 取一個包含D 的矩形區(qū)域；取有利概率密度其中c=；，i=1,n,是以為概率密度的隨機數(shù)列，設，i-1,k,為落在D中的隨機數(shù)，則n充分大時，有 實際計算中, 由于c 是要計算的, 不可能事先得到, 所以只能先估算c 。二、數(shù)據(jù)處理算法 數(shù)據(jù)處理算法有數(shù)據(jù)擬合、參數(shù)估計、插值等，比賽中通常會遇到大量的數(shù)據(jù)需要處

6、理，而處理數(shù)據(jù)的關鍵就在于這些算法，通常使用Matlab作為工具。1數(shù)據(jù)擬合在實驗中，實驗和戡測常常會產(chǎn)生大量的數(shù)據(jù)。為了解釋這些數(shù)據(jù)或者根據(jù)這些數(shù)據(jù)做出預測、判斷，給決策者提供重要的依據(jù)。需要對測量數(shù)據(jù)進行擬合，尋找一個反映數(shù)據(jù)變化規(guī)律的函數(shù)。它所處理的數(shù)據(jù)量大而且不能保證每一個數(shù)據(jù)沒有誤差，所以要求一個函數(shù)嚴格通過每一個數(shù)據(jù)點是不合理的。數(shù)據(jù)擬合方法求擬合函數(shù)。例：在某化學反應中，測得生成物的質量濃度y(10/cm)與時間t（min）的關系如表所示 顯然，連續(xù)函數(shù)關系y(t)是客觀存在的。但是通過表中的數(shù)據(jù)不可能確切地得到這種關系。何況，由于儀器和環(huán)境的影響，測量數(shù)據(jù)難免有誤差。因此只能尋

7、求一個近擬表達式 y=(t)尋求合理的近擬表達式，以反映數(shù)據(jù)變化的規(guī)律，這種方法就是數(shù)據(jù)擬合方法。數(shù)據(jù)擬合需要解決兩個問題：第一，選擇什么類型的函數(shù)(t)作為擬合函數(shù)（數(shù)學模型）；第二，對于選定的擬合函數(shù)，如何確定擬合函數(shù)中的參數(shù)。 數(shù)學模型應建立在合理假設的基礎上，假設的合理性首先體現(xiàn)在選擇某種類型的擬合函數(shù)使之符合數(shù)據(jù)變化的趨勢（總體的變化規(guī)律）。擬合函數(shù)的選擇比較靈活，可以選擇線性函數(shù)、多項式函數(shù)、指數(shù)函數(shù)、三角函數(shù)或其它函數(shù)，這應根據(jù)數(shù)據(jù)分布的趨勢作出選擇。為了問題敘述的方便，將例1的數(shù)據(jù)表寫成一般的形式 （1）線性擬合（線性模型）假設擬合函數(shù)是線性函數(shù)，即擬合函數(shù)的圖形是一條平面上的

8、直線。而表中的數(shù)據(jù)點未能精確地落在一條直線上的原因是實驗數(shù)據(jù)的誤差。則下一步是確定函數(shù) y= a + b x 中系數(shù)a和b各等于多少？從幾何背景來考慮，就是要以a和b作為待定系數(shù)，確定一條平面直線使得表中數(shù)據(jù)所對應的10個點盡可能地靠近這條直線。一般來講，數(shù)據(jù)點將不會全部落在這條直線上，如果第k個點的數(shù)據(jù)恰好落在這條直線上，則這個點的坐標滿足直線的方程，即 a+bx=y如果這個點不在直線上，則它的坐標不滿足直線方程，有一個絕對值為|a+bx-y|的差異（殘差）。于是全部點處的總誤差是|a+bx-y|這是關于a和b的一個二元函數(shù)，合理的做法是選取a和b，使得這個函數(shù)取最小值。但是在實際求解問題時

9、為了操作上的方便，常常是求a和b使得函數(shù) F=（a+bx-y）達到極小。為了求該函數(shù)的極小值點，令 得求解這個二元線性方程組便得待定系數(shù)a和b，從而得線性擬合函數(shù)y=a+bx。下圖中直線是數(shù)據(jù)的線性擬合的結果。（2）二次函數(shù)擬合（二次多項式模型）假設擬合函數(shù)不是線性函數(shù)，而是一個二次多項式函數(shù)。即擬合函數(shù)的圖形是一條平面上的拋物線，而表中的數(shù)據(jù)點未能精確地落在這條拋物線上的原因是實驗數(shù)據(jù)的誤差。則下一步是確定函數(shù) y=a+ax+ax中系數(shù)a,a和a各等于多少？從幾何背景來考慮，就是要以a,a和a為待定系數(shù)，確定二次曲線使得表中數(shù)據(jù)所對應的10個點盡可能地靠近這條曲線。一般來講，數(shù)據(jù)點將不會全部

10、落在這條曲線上，如果第k個點的數(shù)據(jù)恰好落在曲線上，則這個點的坐標滿足二次曲線的方程，即 a+ax+ax=y這是關于a,a和a的一個三元函數(shù)，合理的做法是選取a,a和a，使得這個函數(shù)取最小值。為了求該函數(shù)的極小值點，令 得 這是關于待定系數(shù)a,a和a的線性方程組，寫成等價的形式為 這就是法方程，求解這一方程組可得二次擬合函數(shù)中的三個待定系數(shù)。下圖反映了例題所給數(shù)據(jù)的二次曲線擬合的結果（3） 數(shù)據(jù)的n次多項式擬合（略）2. 參數(shù)估計 數(shù)學建模的一個重要工作是建立變量間的數(shù)學關系式，但公式中總是涉及一些參數(shù)。 求模型中的參數(shù)的估計值有三種常用的方法：圖解法，統(tǒng)計法，機理分析法 。（1） 圖解法：對經(jīng)驗模型的精度不高，只需對參數(shù)做出粗略估計時刻采用圖解法。（2） 統(tǒng)計法：參數(shù)估計的統(tǒng)計處理，往往用最小二乘法估計。（3） 機理分析法：統(tǒng)計分析法應用于變量間