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

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

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

（2）令T等于冷卻進(jìn)度表中的一個(gè)值

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

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

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

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

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

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

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

Markov鏈長度

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

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

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

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

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

算法設(shè)計(jì)步驟：

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

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

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

初始解為隨機(jī)生成一個(gè)的隨機(jī)排列作為。

2.目標(biāo)函數(shù)

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

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

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

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

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

4.新解產(chǎn)生

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

5.Metropolis接受準(zhǔn)則

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

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