淺談數(shù)學建模講義課件

我們畢業(yè)啦其實是答辯的標題地方淺談數(shù)學建模山東科技大學數(shù)學與建模協(xié)會副會長宋佳潤2016/04/24數(shù)學模型到底有哪些？分別該怎么學習？我想告訴大家，現(xiàn)實生活中的問題有哪些類，數(shù)學模型就有哪些類，因為說到底，數(shù)學模型是用來解決實際問題的，解決那些當我們?nèi)狈δ骋环矫孀銐虻慕?jīng)驗時，定量化地依靠數(shù)字來解決問題的辦法。于是我們可以想想，在現(xiàn)實生活中，我們能夠遇到哪些需要定量化解決的問題，而這些問題能否利用數(shù)學工具加以解決長江水質(zhì)的綜合評價嫦娥三號登月問題眼科病床的合理安排太陽影子定位互聯(lián)網(wǎng)時代出租車資源配置國賽題目列舉優(yōu)化類問題評價類問題預(yù)測類問題CONTANTS優(yōu)化類問題Itwasthebestoftimes,itwastheworstoftimes;itwastheageofwisdom,itwastheageoffoolishness.優(yōu)化類問題評價類問題預(yù)測類問題我們常常需要對某些行為進行決策，這些是我們可以控制的因素，這些因素一般來說會定量化地影響我們的某些目標值，比如投入決定產(chǎn)出，價格決定銷量等等。這時，如何確定我們的決策變量，進而使得我們的目標值達到最優(yōu)就是我們利用數(shù)學模型來解決的問題。有一些是標準化過了的數(shù)學規(guī)劃問題，而實際問題往往會更加復(fù)雜，這時候就需要我們憑借經(jīng)驗將這些問題化簡，進而達到我們能夠處理的地步，這中間往往沒有統(tǒng)一的處理辦法，具體問題具體分析，而這個也體現(xiàn)了一個數(shù)模人的實力“”1線性規(guī)劃2動態(tài)規(guī)劃3優(yōu)化類問題評價類問題預(yù)測類問題多目標規(guī)劃評價類問題Itwasthebestoftimes,itwastheworstoftimes;itwastheageofwisdom,itwastheageoffoolishness.優(yōu)化類問題評價類問題預(yù)測類問題每個行業(yè)都有它的評價標準和準則，那么這些標準應(yīng)該有其自身的形成機制，數(shù)學模型就是形成這一機制的方法。如何根據(jù)成分指標評價一瓶葡萄酒？如何根據(jù)員工表現(xiàn)評價年終獎評定？如何評價一名NBA球員在球場上的效率？這些問題都需要設(shè)計評價算法來對這些對象進行評價。數(shù)學模型的評價方法的一個優(yōu)勢在于，它能夠最大程度上客觀地反映被評價對象的優(yōu)劣程度以及符合評價指標的多少，能夠體現(xiàn)公平的原則。優(yōu)化類問題評價類問題預(yù)測類問題123層次分析法模糊綜合評價動態(tài)加權(quán)綜合評價預(yù)測類問題Itwasthebestoftimes,itwastheworstoftimes;itwastheageofwisdom,itwastheageoffoolishness.評價類問題預(yù)測類問題TEXT優(yōu)化類問題未來的情況往往可以根據(jù)當前的一些量予以推測和判斷，這些當前的量再加上失去發(fā)展的機制，就能夠推算出未來可能的情況。預(yù)測的方法有很多，大多是前人總結(jié)的經(jīng)典模型，可以拿來直接套用，而自己推斷事物發(fā)展的機制進行算法設(shè)計然后預(yù)測有時候能夠更加真實地反映未來的可能趨勢，當然，有的模型根據(jù)事物發(fā)展的機理，有的直接通過數(shù)據(jù)分析的手段，這些都是可行的，關(guān)鍵看你有沒有定量地把握事物的本質(zhì)。時間序列（或稱動態(tài)數(shù)列）是指將同一統(tǒng)計指標的數(shù)值按其發(fā)生的時間先后順序排列而成的數(shù)列。時間序列分析的主要目的是根據(jù)已有的歷史數(shù)據(jù)對未來進行預(yù)測。時間序列灰色預(yù)測是一種對含有不確定因素的系統(tǒng)進行預(yù)測的方法。灰色預(yù)測通過鑒別系統(tǒng)因素之間發(fā)展趨勢的相異程度，即進行關(guān)聯(lián)分析，并對原始數(shù)據(jù)進行生成處理來尋找系統(tǒng)變動的規(guī)律，生成有較強規(guī)律性的數(shù)據(jù)序列，然后建立相應(yīng)的微分方程模型，從而預(yù)測事物未來發(fā)展趨勢的狀況?；疑A(yù)測評價類問題預(yù)測類問題優(yōu)化類問題模擬退火算法算法簡介模擬退火算法得益于材料的統(tǒng)計力學的研究成果。統(tǒng)計力學表明材料中粒子的不同結(jié)構(gòu)對應(yīng)于粒子的不同能量水平。在高溫條件下，粒子的能量較高，可以自由運動和重新排列。在低溫條件下，粒子能量較低。如果從高溫開始，非常緩慢地降溫（這個過程被稱為退火），粒子就可以在每個溫度下達到熱平衡。當系統(tǒng)完全被冷卻時，最終形成處于低能狀態(tài)的晶體。如果用粒子的能量定義材料的狀態(tài)，Metropolis算法用一個簡單的數(shù)學模型描述了。退火過程。假設(shè)材料在狀態(tài)i之下的能量為E(i)，那么材料在溫度T時從狀態(tài)i進入狀態(tài)j就遵循如下規(guī)律：（1）如果E(j)≤E(i)，接受該狀態(tài)被轉(zhuǎn)換。（2）如果E(j)>E(i)，則狀態(tài)轉(zhuǎn)換以如下概率被接受：其中K是物理學中的波爾茲曼常數(shù)，T是材料溫度。在應(yīng)用時，我們將目標函數(shù)定義為能量，決策變量的可行解為狀態(tài)。算法基本步驟：

（1）令即開始退火的初始溫度，隨機生成一個初始解，并計算相應(yīng)的目標函數(shù)值。

（2）令T等于冷卻進度表中的一個值

（3）根據(jù)當前解進行擾動，產(chǎn)生一個新解，計算相應(yīng)的目標函數(shù)值，得到

（4）若，則新解被接受，作為新的當前解；若，則新解按照概率接受，為當前溫度。

（5）在溫度下，重復(fù)Markov鏈長度次的擾動和接受過程，即執(zhí)行（3）與（4）。

（6）判斷T是否已到達，是，則終止算法；否，則轉(zhuǎn)到（2）繼續(xù)執(zhí)行。

算法實質(zhì)分為兩循環(huán)，在任一溫度隨機擾動產(chǎn)生新解，并計算目標函數(shù)的變化，決定是否被接受。由于算法初始溫度比較高，這樣使得E增大的新解在初始是也可以被接受，因而能跳出局部最小值然后通過緩慢地減低溫度，算法最終可能得到全局最優(yōu)解。

新解產(chǎn)生的機制的基本要求是能夠盡量遍及解空間的各個區(qū)域，這樣在某一恒定溫度，不斷產(chǎn)生新解時，就可能跳出當前區(qū)域的極小值，以搜索其他區(qū)域，這是模擬退火算法能夠進行廣域搜索的一個重要條件?？刂坪瘮?shù)T的衰減函數(shù)有多種形式，一個常用的衰減函數(shù)是：

其中是一個常數(shù)，可以取為0.5~0.99，它的取值，決定了降溫的過程。

Markov鏈長度

Markov鏈長度的選取原則是：在控制參數(shù)T的衰減函數(shù)已選定的前提下，應(yīng)能使在控制參數(shù)T的每一取值上達到平衡。從經(jīng)驗上看，對簡單的情況可以令，n為問題規(guī)模。

旅行商問題(TSP)代表一類組合優(yōu)化問題，在物流、計算機網(wǎng)絡(luò)、電子地圖、交通疏導(dǎo)等方面都有重要的工程和理論價值，引起許多學者的關(guān)注。TSP簡單描述為：一個商人要到n個不同的地方去推銷商品，每2個城市i和j之間的距離為，如何選擇一條路徑使得商人每個城市走一遍后回到起點，所走的路徑最短。

該問題當城市數(shù)目在100以上，一般很難精確的求出其全局最優(yōu)解。

說明：工程中許多實際優(yōu)化問題的目標函數(shù)都是非凸的，存在許多局部最優(yōu)解，特別是隨著優(yōu)化規(guī)模的增大，局部最優(yōu)解的數(shù)目將迅速增加。有效地求出一般非凸目標函數(shù)的全局解至今仍是一個難題。一般確定性算法往往容易陷入局部而非全局最優(yōu)。

模擬退火算法是一種通用概率算法，用來在一個大的搜尋空間內(nèi)尋找問題的最優(yōu)解。具有高效、魯棒、通用、靈活的優(yōu)點。將模擬退火算法引入TSP求解，可以避免在求解過程中陷入TSP的局部最優(yōu)。

算法設(shè)計步驟：

1.ＴＳＰ問題的解空間和初始解

ＴＳＰ問題的解空間Ｓ是遍訪每個城市恰好一次的所有回路，是所有城市排列的集合，即

其中每一個排列表示遍訪n個城市的一個路徑，表示第i次訪問城市j.

初始解為隨機生成一個的隨機排列作為。

2.目標函數(shù)

TSP問題的目標函數(shù)即為訪問所有城市的路徑的總長度，也可以稱為代價函數(shù);

現(xiàn)在TSP問題的求解就是通過模擬退火算法求出目標函數(shù)的最小值。相應(yīng)地，即為TSP問題的最優(yōu)解。3.新解的產(chǎn)生

新解的產(chǎn)生對問題的求解非常重要。新解可通過分別或者交替使用以下兩種方法來產(chǎn)生:

(1)二變換法：任選序號u,v(設(shè)u<v<n),交換u和v之間的訪問順序

（2）三變換法：任選序號u,v，w(設(shè)u<=v<w),將u和v之間的路徑插到w之后訪問。

4.新解產(chǎn)生

計算變換前的解和變換后目標函數(shù)的差值：

5.Metropolis接受準則

以新解與當前解的目標函數(shù)差定義接受概率，即

隨溫度變化的目標函數(shù)值變化情況99度時熱平衡過程中目標函數(shù)變化情況50度時熱平衡過程