運(yùn)籌學(xué)的優(yōu)化算法

運(yùn)籌學(xué)的優(yōu)化算法1運(yùn)籌學(xué)（OperationsResearchOR）

由于運(yùn)籌學(xué)研究的廣泛性和復(fù)雜性，人們至今沒(méi)有形成一個(gè)統(tǒng)一的定義。以下給出幾種定義：運(yùn)籌學(xué)是一種科學(xué)決策的方法運(yùn)籌學(xué)是依據(jù)給定目標(biāo)和條件從眾多方案中選擇最優(yōu)方案的最優(yōu)化技術(shù)。運(yùn)籌學(xué)是一種給出壞的問(wèn)題的答案的藝術(shù)，否則的話問(wèn)題的結(jié)果會(huì)更壞。2運(yùn)籌學(xué)模型運(yùn)籌學(xué)研究的模型主要是抽象模型——數(shù)學(xué)模型。3運(yùn)籌學(xué)包含的分支數(shù)學(xué)規(guī)劃（線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃、網(wǎng)絡(luò)規(guī)劃等）圖論與網(wǎng)絡(luò)流決策分析4運(yùn)籌學(xué)包含的分支排隊(duì)論可靠性數(shù)學(xué)理論庫(kù)存論對(duì)策論搜索論計(jì)算機(jī)模擬等5數(shù)學(xué)建模競(jìng)賽中的算法(1)93A非線性交調(diào)的頻率設(shè)計(jì):擬合、規(guī)劃93B足球隊(duì)排名次:矩陣論、圖論、層次分析法、整數(shù)規(guī)劃94A逢山開(kāi)路:圖論、插值、動(dòng)態(tài)規(guī)劃94B鎖具裝箱問(wèn)題:圖論、組合數(shù)學(xué)95A飛行管理問(wèn)題

:非線性規(guī)劃、線性規(guī)劃95B天車(chē)與冶煉爐的作業(yè)調(diào)度:非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、層次分析法、PETRI方法、圖論方法、排隊(duì)論方法96A最優(yōu)捕魚(yú)策略：微分方程、積分、非線性規(guī)劃696B節(jié)水洗衣機(jī)：非線性規(guī)劃97A零件參數(shù)設(shè)計(jì)：微積分、非線性規(guī)劃、隨機(jī)模擬97B截?cái)嗲懈睿航M合優(yōu)化、幾何變換、枚舉、蒙特卡羅、遞歸、最短路98A投資收益與風(fēng)險(xiǎn)：線性規(guī)劃、非線性規(guī)劃98B災(zāi)情巡視路線：最小生成樹(shù)、Hamilton圈、旅行商問(wèn)題99A自動(dòng)化車(chē)床管理：積分、概率分布、隨機(jī)模擬、分布擬合度檢驗(yàn)數(shù)學(xué)建模競(jìng)賽中的算法(2)799B鉆井布局：幾何變換、枚舉、最大完全子圖、混合整數(shù)規(guī)劃00ADNA分類(lèi)：神經(jīng)網(wǎng)絡(luò)、最小二乘擬合、統(tǒng)計(jì)分類(lèi)00B管道訂購(gòu)和運(yùn)輸：最短路、二次規(guī)劃01A血管的三維重建：數(shù)據(jù)挖掘、曲面重建與擬合01B公交車(chē)調(diào)度：非線性規(guī)劃02A車(chē)燈光源優(yōu)化設(shè)計(jì)：最優(yōu)化02B彩票中的數(shù)學(xué)：概率與優(yōu)化數(shù)學(xué)建模競(jìng)賽中的算法(3)803A

SARS的傳播：微分方程、差分方程

03B

露天礦生產(chǎn)的車(chē)輛安排：整數(shù)規(guī)劃、運(yùn)輸問(wèn)題04A

奧運(yùn)會(huì)臨時(shí)超市網(wǎng)點(diǎn)設(shè)計(jì)：統(tǒng)計(jì)分析、數(shù)據(jù)處理、優(yōu)化

04B

電力市場(chǎng)的輸電阻塞管理：數(shù)據(jù)擬合、優(yōu)化

05A

長(zhǎng)江水質(zhì)的評(píng)價(jià)和預(yù)測(cè)：預(yù)測(cè)評(píng)價(jià)、數(shù)據(jù)處理

05B

DVD在線租賃：隨機(jī)規(guī)劃、整數(shù)規(guī)劃

06A

出版社書(shū)號(hào)問(wèn)題：整數(shù)規(guī)劃、數(shù)據(jù)處理、優(yōu)化

數(shù)學(xué)建模競(jìng)賽中的算法(4)906B

Hiv病毒問(wèn)題：線性規(guī)劃、回歸分析07A

人口問(wèn)題：微分方程、數(shù)據(jù)處理、優(yōu)化07B

公交車(chē)問(wèn)題：多目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃、圖論、0-1規(guī)劃08A

照相機(jī)問(wèn)題：非線性方程組、優(yōu)化08B

大學(xué)學(xué)費(fèi)問(wèn)題：數(shù)據(jù)收集和處理、統(tǒng)計(jì)分析、回歸分析

數(shù)學(xué)建模競(jìng)賽中的算法(5)10賽題發(fā)展的特點(diǎn)：

1.對(duì)選手的計(jì)算機(jī)能力提出了更高的要求：賽題的解決依賴(lài)計(jì)算機(jī)，題目的數(shù)據(jù)較多，手工計(jì)算不能完成，計(jì)算機(jī)模擬和以算法形式給出最終結(jié)果。

2.賽題的開(kāi)放性增大:

解法的多樣性，一道賽題可用多種解法。開(kāi)放性還表現(xiàn)在對(duì)模型假設(shè)和對(duì)數(shù)據(jù)處理上。

3.試題向大規(guī)模數(shù)據(jù)處理方向發(fā)展

4.求解算法和各類(lèi)現(xiàn)代算法的融合

111.

蒙特卡羅方法(Monte-Carlo方法,MC)數(shù)學(xué)建模競(jìng)賽常用算法(1)

該算法又稱(chēng)計(jì)算機(jī)隨機(jī)性模擬方法，也稱(chēng)統(tǒng)計(jì)試驗(yàn)方法。MC方法是一種基于“隨機(jī)數(shù)”的計(jì)算方法，能夠比較逼真地描述事物的特點(diǎn)及物理實(shí)驗(yàn)過(guò)程，解決一些數(shù)值方法難以解決的問(wèn)題。

MC方法的雛型可以追溯到十九世紀(jì)后期的蒲豐隨機(jī)投針試驗(yàn)，即著名的蒲豐問(wèn)題。MC方法通過(guò)計(jì)算機(jī)仿真(模擬)解決問(wèn)題，同時(shí)也可以通過(guò)模擬來(lái)檢驗(yàn)自己模型的正確性，是比賽中經(jīng)常使用的方法。1297年的A題每個(gè)零件都有自己的標(biāo)定值，也都有自己的容差等級(jí)，而求解最優(yōu)的組合方案將要面對(duì)著的是一個(gè)極其復(fù)雜的公式和108種容差選取方案，根本不可能去求解析解，那如何去找到最優(yōu)的方案呢？隨機(jī)性模擬搜索最優(yōu)方案就是其中的一種方法，在每個(gè)零件可行的區(qū)間中按照正態(tài)分布隨機(jī)的選取一個(gè)標(biāo)定值和選取一個(gè)容差值作為一種方案，然后通過(guò)蒙特卡羅算法仿真出大量的方案，從中選取一個(gè)最佳的。02年的B題關(guān)于彩票第二問(wèn)，要求設(shè)計(jì)一種更好的方案，首先方案的優(yōu)劣取決于很多復(fù)雜的因素，同樣不可能刻畫(huà)出一個(gè)模型進(jìn)行求解，只能靠隨機(jī)仿真模擬。數(shù)學(xué)建模競(jìng)賽常用算法1398年美國(guó)賽A題

生物組織切片的三維插值處理94年A題逢山開(kāi)路

山體海拔高度的插值計(jì)算數(shù)學(xué)建模競(jìng)賽常用算法(2)2.數(shù)據(jù)擬合、參數(shù)估計(jì)、插值等數(shù)據(jù)處理算法比賽中通常會(huì)遇到大量的數(shù)據(jù)需要處理，而處理數(shù)據(jù)的關(guān)鍵就在于這些算法，通常使用MATLAB作為工具。與圖形處理有關(guān)的問(wèn)題很多與擬合有關(guān)系。此類(lèi)問(wèn)題在MATLAB中有很多函數(shù)可以調(diào)用，只有熟悉MATLAB，這些方法才能用好。1498年B題用很多不等式完全可以把問(wèn)題刻畫(huà)清楚數(shù)學(xué)建模競(jìng)賽常用算法(3)3.規(guī)劃類(lèi)問(wèn)題算法此類(lèi)問(wèn)題主要有線性規(guī)劃、整數(shù)規(guī)劃、多目標(biāo)規(guī)劃、二次規(guī)劃等。競(jìng)賽中很多問(wèn)題都和數(shù)學(xué)規(guī)劃有關(guān)，可以說(shuō)不少的模型都可以歸結(jié)為一組不等式作為約束條件、幾個(gè)函數(shù)表達(dá)式作為目標(biāo)函數(shù)的問(wèn)題，遇到這類(lèi)問(wèn)題，求解就是關(guān)鍵了。因此列舉出規(guī)劃后用Lindo、Lingo等軟件來(lái)進(jìn)行解決比較方便，所以還需要熟悉這兩個(gè)軟件。1598年B題、00年B題、95年鎖具裝箱等問(wèn)題體現(xiàn)了圖論問(wèn)題的重要性。數(shù)學(xué)建模競(jìng)賽常用算法(4)4.

圖論問(wèn)題

這類(lèi)問(wèn)題算法有很多，包括：Dijkstra、Floyd、Prim、Bellman-Ford，最大流，二分匹配等問(wèn)題。1692年B題用分枝定界法97年B題是典型的動(dòng)態(tài)規(guī)劃問(wèn)題98年B題體現(xiàn)了分治算法數(shù)學(xué)建模競(jìng)賽常用算法(5)5.計(jì)算機(jī)算法設(shè)計(jì)中的問(wèn)題

計(jì)算機(jī)算法設(shè)計(jì)包括很多內(nèi)容：動(dòng)態(tài)規(guī)劃、回溯搜索、分治算法、分枝定界等計(jì)算機(jī)算法.

這方面問(wèn)題和ACM程序設(shè)計(jì)競(jìng)賽中的問(wèn)題類(lèi)似，可看一下與計(jì)算機(jī)算法有關(guān)的書(shū)。17分枝定界法原問(wèn)題的松馳問(wèn)題：任何整數(shù)規(guī)劃（IP），凡放棄某些約束條件（如整數(shù)要求）后，所得到的問(wèn)題（P）都稱(chēng)為（IP）的松馳問(wèn)題。最通常的松馳問(wèn)題是放棄變量的整數(shù)性要求后，（P）為線性規(guī)劃問(wèn)題。18去掉整數(shù)約束,用單純形法IPLPxl*

判別是否整數(shù)解xI*=xl*Yes去掉非整數(shù)域No多個(gè)LP……19分枝定界法步驟一般求解對(duì)應(yīng)的松馳問(wèn)題，可能會(huì)出現(xiàn)下面幾種情況：若所得的最優(yōu)解的各分量恰好是整數(shù)，則這個(gè)解也是原整數(shù)規(guī)劃的最優(yōu)解，計(jì)算結(jié)束。20分枝定界法步驟一般求解對(duì)應(yīng)的松馳問(wèn)題，可能會(huì)出現(xiàn)下面幾種情況：若所得的最優(yōu)解的各分量恰好是整數(shù)，則這個(gè)解也是原整數(shù)規(guī)劃的最優(yōu)解，計(jì)算結(jié)束。若松馳問(wèn)題無(wú)可行解，則原整數(shù)規(guī)劃問(wèn)題也無(wú)可行解，計(jì)算結(jié)束。21若松馳問(wèn)題有最優(yōu)解，但其各分量不全是整數(shù)，則這個(gè)解不是原整數(shù)規(guī)劃的最優(yōu)解，轉(zhuǎn)下一步。22若松馳問(wèn)題有最優(yōu)解，但其各分量不全是整數(shù)，則這個(gè)解不是原整數(shù)規(guī)劃的最優(yōu)解，轉(zhuǎn)下一步。從不滿(mǎn)足整數(shù)條件的基變量中任選一個(gè)xl進(jìn)行分枝，它必須滿(mǎn)足xl

[xl]

或xl

[xl

]+1中的一個(gè)，把這兩個(gè)約束條件加進(jìn)原問(wèn)題中，形成兩個(gè)互不相容的子問(wèn)題（兩分法）。23定界：把滿(mǎn)足整數(shù)條件各分枝的最優(yōu)目標(biāo)函數(shù)值作為上（下）界，用它來(lái)判斷分枝是保留還是剪枝。24定界：把滿(mǎn)足整數(shù)條件各分枝的最優(yōu)目標(biāo)函數(shù)值作為上（下）界，用它來(lái)判斷分枝是保留還是剪枝。剪枝：把那些子問(wèn)題的最優(yōu)值與界值比較，凡不優(yōu)或不能更優(yōu)的分枝全剪掉，直到每個(gè)分枝都查清為止。25例：

用分枝定界法求解：MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0整數(shù)用單純形法可解得相應(yīng)的松馳問(wèn)題的最優(yōu)解（6/5，21/10）Z=111/10為各分枝的上界。26012344321x1x2分枝：x1

1,x1

2P1P2（6/5，21/10）27兩個(gè)子問(wèn)題：（P1）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0，x1

1，整數(shù)用單純形法可解得相應(yīng)的（P1）的最優(yōu)解（1，9/4）Z=10(3/4)28（P2）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0，x1

2，整數(shù)用單純形法可解得相應(yīng)的（P2）的最優(yōu)解（2，1/2）Z=9(1/2)29012344321x1x2再對(duì)（P1）x1

1（1，9/4）分枝：（P3）x2

2（P4）x2

3P1P2P3P430（P1）兩個(gè)子問(wèn)題：（P3）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0,x1

1,x2

2整數(shù)用單純形法可解得相應(yīng)的（P3）的最優(yōu)解（1，2）Z=10為上界31（P1）兩個(gè)子問(wèn)題：（P4）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0,x1

1,x2

3整數(shù)用單純形法可解得相應(yīng)的（P4）的最優(yōu)解（0，3）Z=932X1

2X2

2X1

1X2

3P1:(1,9/4)Z=10(3/4)P4:(0,3)Z=9P2:(2,1/2)Z=9(1/2)P3:(1,2)Z=10P:(6/5,21/10)Z=111/10原問(wèn)題的最優(yōu)解（1，2）Z=1033多階段決策過(guò)程最優(yōu)化多階段決策過(guò)程是指這樣一類(lèi)特殊的活動(dòng)過(guò)程，他們可以按時(shí)間順序分解成若干相互聯(lián)系的階段，在每個(gè)階段都要做出決策，全部過(guò)程的決策是一個(gè)決策序列，所以多階段決策問(wèn)題也稱(chēng)為序貫決策問(wèn)題。動(dòng)態(tài)規(guī)劃應(yīng)用舉例34最優(yōu)化原理：最優(yōu)策略的任一后部子策略都是最優(yōu)的。無(wú)論以前狀態(tài)決策如何，從眼下直到最后的諸決策必構(gòu)成最優(yōu)子策略。例1最短路線問(wèn)題AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143動(dòng)態(tài)規(guī)劃應(yīng)用舉例35例1多階段資源分配問(wèn)題

設(shè)有數(shù)量為x的某種資源，將它投入兩種生產(chǎn)方式A和B中：以數(shù)量y投入生產(chǎn)方式A，剩下的量投入生產(chǎn)方式B，則可得到收入g(y)+h(x-y)，其中g(shù)(y)和h(y)是已知函數(shù)，并且g(0)=h(0)=0；同時(shí)假設(shè)以y與x-y分別投入兩種生產(chǎn)方式A，B后可以回收再生產(chǎn)，回收率分別為a與b。試求進(jìn)行n個(gè)階段后的最大總收入。

36

若以y與x-y分別投入生產(chǎn)方式A與B，在第一階段生產(chǎn)后回收的總資源為x1=ay+b(x-y)，再將x1投入生產(chǎn)方式A和B，則可得到收入g(y1)+h(x1-y1)，繼續(xù)回收資源x2=ay1+b(x1-y1)，……

若上面的過(guò)程進(jìn)行n個(gè)階段，我們希望選擇n個(gè)變量y,y1,y2,…,yn-1，使這n個(gè)階段的總收入最大。

例1續(xù)（1）37因此，我們的問(wèn)題就變成：求y,y1,y2,…,yn-1，以使g(y)+h(x-y)+g(y1)+h(x1-y1)+…+g(yn-1)+h(xn-1-yn-1)達(dá)到最大，且滿(mǎn)足條件

x1=ay+b(x-y)x2=ay1+b(x1-y1)………xn-1=ayn-2+b(xn-2-yn-2)

yi與xi均非負(fù),i=1,2,…,n-1例1續(xù)（2）38例2生產(chǎn)和存儲(chǔ)控制問(wèn)題

某工廠生產(chǎn)某種季節(jié)性商品，需要作下一年度的生產(chǎn)計(jì)劃，假定這種商品的生產(chǎn)周期需要兩個(gè)月，全年共有6個(gè)生產(chǎn)周期，需要作出各個(gè)周期中的生產(chǎn)計(jì)劃。39設(shè)已知各周期對(duì)該商品的需要量如下表所示：周期123456需求量551030508例2續(xù)（1）40例2續(xù)（2）

假設(shè)這個(gè)工廠根據(jù)需要可以日夜兩班生產(chǎn)或只是日班生產(chǎn)，當(dāng)開(kāi)足日班時(shí)，每一個(gè)生產(chǎn)周期能生產(chǎn)商品15個(gè)單位，每生產(chǎn)一個(gè)單位商品的成本為100元。當(dāng)開(kāi)足夜班時(shí)，每一生產(chǎn)周期能生產(chǎn)的商品也是15個(gè)，但是由于增加了輔助性生產(chǎn)設(shè)備和生產(chǎn)輔助費(fèi)用，每生產(chǎn)一單位商品的成本為120元。由于生產(chǎn)能力的限制，可以在需求淡季多生產(chǎn)一些商品儲(chǔ)存起來(lái)以備需求旺季使用，但存儲(chǔ)商品是需要存儲(chǔ)費(fèi)用的，假設(shè)每單位商品存儲(chǔ)一周期需要16元，已知開(kāi)始時(shí)存儲(chǔ)為零，年終也不存儲(chǔ)商品備下年使用，問(wèn)應(yīng)該如何作生產(chǎn)和存儲(chǔ)計(jì)劃，才能使總的生產(chǎn)和存儲(chǔ)費(fèi)用最?。?1例2續(xù)（3）

設(shè)第i個(gè)周期的生產(chǎn)量為xi，周期末的存儲(chǔ)量為ui，那么這個(gè)問(wèn)題用式子寫(xiě)出來(lái)就是：求x1,x2,…,x6，滿(mǎn)足條件：

x1=5+u1x2+u1=5+u2x3+u2=10+u3x4+u3=30+u4x5+u4=50+u5x6+u5=80xi30,0uj,i=1,2,…,6;j=1,2,…,5

使S==

為最小，其中42例2續(xù)（4）43逆序遞推方程：（1）k=5時(shí)，狀態(tài)它們到F點(diǎn)的距離即為最短路。AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例1：1階段2階段3階段4階段5階段44AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4時(shí)，狀態(tài)它們到F點(diǎn)需經(jīng)過(guò)中途點(diǎn)E，需一一分析從E到F的最短路：先說(shuō)從D1到F的最短路有兩種選擇：經(jīng)過(guò)E1,E2,比較最短。45AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143這說(shuō)明由D1到F的最短距離為7，其路徑為相應(yīng)的決策為：46這說(shuō)明由D2到F的最短距離為5，其路徑為相應(yīng)的決策為：AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314347AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即D3到F的最短距離為5，其路徑為相應(yīng)的決策為：48（3）k=3時(shí)，狀態(tài)這說(shuō)明由C1到F的最短距離為12，相應(yīng)的決策為AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314349AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即由C2到F的最短距離為10，相應(yīng)的決策為50即由C3到F的最短距離為8，相應(yīng)的決策為即由C4到F的最短距離為9，相應(yīng)的決策為AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314351AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2時(shí)，狀態(tài)這說(shuō)明由B1到F的最短距離為13，相應(yīng)的決策為52即由B2到F的最短距離為15，相應(yīng)的決策為AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314353AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（1）k=1時(shí)，只有一個(gè)狀態(tài)點(diǎn)A,則即由A到F的最短距離為17，相應(yīng)的決策為54所以最優(yōu)路線為：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143再按計(jì)算順序反推可得最優(yōu)決策序列：5597年A題用模擬退火算法00年B題用神經(jīng)網(wǎng)絡(luò)分類(lèi)算法01年B題這種難題也可以使用神經(jīng)網(wǎng)絡(luò)美國(guó)03年B題伽馬刀問(wèn)題也是目前研究的課題，目前算法最佳的是遺傳算法。數(shù)學(xué)建模競(jìng)賽常用算法(6)6.最優(yōu)化理論的三大非經(jīng)典算法:

模擬退火法(SA)、神經(jīng)網(wǎng)絡(luò)(NN)、遺傳算法(GA)近幾年的賽題越來(lái)越復(fù)雜，很多問(wèn)題沒(méi)有什么很好的模型可以借鑒，于是這三類(lèi)算法很多時(shí)候可以派上用場(chǎng)。5697年A題、99年B題都可以用網(wǎng)格法搜索數(shù)學(xué)建模競(jìng)賽常用算法(7)網(wǎng)格算法和窮舉法一樣，只是網(wǎng)格法是連續(xù)問(wèn)題的窮舉。此類(lèi)算法運(yùn)算量較大。7.網(wǎng)格算法和窮舉算法這種方法最好在運(yùn)算速度較快的計(jì)算機(jī)中進(jìn)行，還有要用高級(jí)語(yǔ)言來(lái)做，最好不要用MATLAB做網(wǎng)格，否則會(huì)算很久。57很多問(wèn)題都是實(shí)際來(lái)的，數(shù)據(jù)可以是連續(xù)的，而計(jì)算機(jī)只能處理離散的數(shù)據(jù)，因此需要將連續(xù)問(wèn)題進(jìn)行離散化處理后再用計(jì)算機(jī)求解。比如差分代替微分、求和代替積分等思想都是把連續(xù)問(wèn)題離散化的常用方法。數(shù)學(xué)建模競(jìng)賽常用算法(8)8.連續(xù)問(wèn)題離散化的方法58數(shù)值分析研究各種求解數(shù)學(xué)問(wèn)題的數(shù)值計(jì)算方法，特別是適合于計(jì)算機(jī)實(shí)現(xiàn)方法與算法。數(shù)學(xué)建模競(jìng)賽常用算法(9)9.數(shù)值分析方法它的主要內(nèi)容包括函數(shù)的數(shù)值逼近、數(shù)值微分與數(shù)值積分、非線性方程的數(shù)值解法、數(shù)值代數(shù)、常微分方程數(shù)值解等。數(shù)值分析是計(jì)算數(shù)學(xué)的一個(gè)重要分支，把理論與計(jì)算緊密結(jié)合,是現(xiàn)代科學(xué)計(jì)算的基礎(chǔ)。

MATLAB等數(shù)學(xué)軟件中已經(jīng)有很多數(shù)值分析的函數(shù)可以直接調(diào)用。5901年A題中需要你會(huì)讀BMP圖象98年美國(guó)A題需要你知道三維插值計(jì)算03年B題要求更高，不但需要編程計(jì)算還要進(jìn)行處理數(shù)學(xué)建模競(jìng)賽常用算法(10)10.圖象處理算法賽題中有一類(lèi)問(wèn)題與圖形有關(guān)，即使問(wèn)題與圖形無(wú)關(guān)，論文中也會(huì)需要圖片來(lái)說(shuō)明問(wèn)題，這些圖形如何展示以及如何處理就是需要解決的問(wèn)題，通常使用MATLAB進(jìn)行處理。數(shù)模論文中也有很多圖片需要展示，解決這類(lèi)問(wèn)題要熟悉MATLAB圖形圖像工具箱。60例1某公司擁有一塊可能有油的土地，根據(jù)可能出油的多少，該塊土地屬于四種類(lèi)型：可產(chǎn)油50萬(wàn)桶、20萬(wàn)桶、5萬(wàn)桶、無(wú)油。公司目前有3個(gè)方案可供選擇：自行鉆進(jìn)；無(wú)條件將該塊土地出租給其他使用者；有條件的租給其他生產(chǎn)者。若自行鉆井，打出一口有油井的費(fèi)用是10萬(wàn)元，打出一口無(wú)油井決策分析61的費(fèi)用是7.5萬(wàn)元，每一桶油的利潤(rùn)是1.5萬(wàn)。若無(wú)條件出租，不管出油多少，公司收取固定租金4.5萬(wàn)元；若有條件出租，公司不收取租金，但當(dāng)產(chǎn)量為20萬(wàn)桶至50萬(wàn)桶時(shí)，每桶公司收取0.5元。由上計(jì)算得到該公司可能的利潤(rùn)收入見(jiàn)表14-1.按過(guò)去的經(jīng)驗(yàn)，該塊土地屬于上面4種類(lèi)型的可能性分別為10%，15%，25%和50%。問(wèn)題是該公司應(yīng)選擇哪種方案，可獲得最大利潤(rùn)？62

表14-1石油公司可能利潤(rùn)收入表（單位：萬(wàn)元）類(lèi)型項(xiàng)目50萬(wàn)桶

20萬(wàn)桶

5萬(wàn)桶

無(wú)油

自行鉆井無(wú)條件出租有條件出租654.525204.510－2.54.50－7.54.50解：各個(gè)方案的期望收益為根據(jù)期望收益最大原則，應(yīng)選擇，即自行鉆井。63效用理論一、效用概念的引入前面介紹風(fēng)險(xiǎn)型決策方法時(shí)，提到可根據(jù)期望益損值（最大或最小）作為選擇最優(yōu)方案的原則，但這樣做并不一定合理。請(qǐng)看下面的例子：例6設(shè)有兩個(gè)決策問(wèn)題：?jiǎn)栴}1：方案A1：穩(wěn)獲100元；方案B1:用擲硬幣的方法，擲出正面獲得250元，擲出反面獲得0元。64問(wèn)題2：方案A2：穩(wěn)獲1000元；方案B2:用擲硬幣的方法，直到擲出正面為止，記所擲次數(shù)為N，則當(dāng)正面出現(xiàn)時(shí)，可獲2N元.當(dāng)你遇到這兩類(lèi)問(wèn)題時(shí)，如何決策？大部分會(huì)選擇A1和A2。但不妨計(jì)算一下其期望值：Y10250P(Y1=k)1/21/2方案B1的收益為隨機(jī)變量Y1。則其期望收益為：65設(shè)方案B2的收益為隨機(jī)變量Y2。Ai=“第i次擲出正面”，則第n次擲出正面的概率為：Y222223…n…P(Y2=k)1/21/221/23…1/2n…X012…n-1…相互獨(dú)立設(shè)擲出正面前擲出反面的次數(shù)為隨機(jī)變量X,則有分布列：則方案2的平均收益為：66Y222223…n…P(Y2=k)1/21/221/23…1/2n…X012…n-1…于是，根據(jù)期望收益最大原則，應(yīng)選擇B1和B2，但這一結(jié)果很難令實(shí)際決策者接受。此乃研究效用函數(shù)的初衷。例7（賭一把）一個(gè)正常的人，遇到“賭一把”的機(jī)會(huì)。情況如下面的樹(shù)，問(wèn)此人如何決策？67正常人B賭不賭45元擲出正面P=0.5-10元P=0.50100元擲出反面45元對(duì)絕大部分人來(lái)說(shuō)，只要兜里有10元錢(qián)，又不急用的話，就選擇“賭”。因此時(shí)“賭”的平均收益為：類(lèi)似的問(wèn)題，讓一個(gè)被判刑十年且手頭僅有10元錢(qián)的罪犯做下面的決策：68罪犯B賭釋放45元擲出正面P=0.5-10元P=0.5-10元100元擲出反面45元此時(shí)罪犯可能要選擇交出10元錢(qián)，獲得釋放。以上例子說(shuō)明：⑴相同的期望益損值（以貨幣值為度量）的不同隨機(jī)事件之間其風(fēng)險(xiǎn)可能存在著很大的差異。即說(shuō)明貨幣量的期望益損值不能完全反映隨機(jī)事件的風(fēng)險(xiǎn)程度。⑵同一隨機(jī)事件對(duì)不同的決策者的吸引力可能完全不同，因此可采用不同的決策。這與決策者個(gè)人的氣質(zhì)、冒險(xiǎn)精神、69經(jīng)濟(jì)狀況、經(jīng)驗(yàn)等等主觀因素有很大的關(guān)系。⑶即使同一個(gè)人在不同情況下對(duì)同一隨機(jī)事件也會(huì)采用不同的態(tài)度。當(dāng)我們以期望益損值（以貨幣值為度量）作決策準(zhǔn)則時(shí)，實(shí)際已經(jīng)假定期望益損值相等的各個(gè)隨機(jī)事件是等價(jià)的，具有相同的風(fēng)險(xiǎn)程度，且對(duì)不同的人具有相同的吸引力。但對(duì)有些問(wèn)題這個(gè)假定是不合適的。因此不能采用貨幣度量的期望益損值作決策準(zhǔn)則，而用所謂“效用值”作決策準(zhǔn)則。70二、效用曲線的確定及分類(lèi)老王B二次抽獎(jiǎng)一次500元P=0.50元P=0.5500元1000元500元為了講清“效用”與“效用值”的概念，看下例例老王參加某電視臺(tái)綜藝節(jié)目而得獎(jiǎng)。他有兩種方式可選擇：一次獲得500元獎(jiǎng)金。分別以概率0.5與0.5的機(jī)會(huì)抽獎(jiǎng)可獲得1000元與0元。試問(wèn)老王該選擇何種方式領(lǐng)獎(jiǎng)？71事件的期望益損值都是500元，但有人認(rèn)為應(yīng)選擇他認(rèn)為的“價(jià)值”比大，有的相反。都是“主觀價(jià)值”。此時(shí)他認(rèn)為事件的效用比事件來(lái)的大。

如何來(lái)度量隨機(jī)事件的效用（或說(shuō)“價(jià)值”）？我們用“效用值”u來(lái)度量效用值的大小?！靶в弥怠笔且粋€(gè)“主觀價(jià)值”，且是一個(gè)相對(duì)大小的值。通常假定決策者最偏好、最傾向、最喜歡的事情（方案）的效用為1，而最不偏好、最不傾向、最不喜歡的事情（方案）的效用為0。一般來(lái)說(shuō)，若用r來(lái)表示期望收益值（這里收益值作廣義理解，不一定是貨幣量，也可以是某事件的結(jié)果），則r的效用72那么，當(dāng)時(shí)如何計(jì)算呢？值用來(lái)表示。因此有一般用心理測(cè)試的方法來(lái)確定，具體做法是：反復(fù)向決策者提出下面的問(wèn)題：“如果事件是以概率P得到收益為，以概率（1-P）得到收益為，事件是以100%概率得到收益為你認(rèn)為取多大值時(shí)，事件與事件是相當(dāng)?shù)模凑J(rèn)為效用值相等）？如果決策者經(jīng)過(guò)思考后，認(rèn)為時(shí)兩事件效用是相當(dāng)?shù)?，即?3當(dāng)，，已知時(shí)，則的效用值可求出。如當(dāng)

則則可求出的效用值，再在已知效用值的三點(diǎn)中的任意兩點(diǎn)，再作出同樣的問(wèn)題來(lái)問(wèn)決策者，則可在兩點(diǎn)中求出一點(diǎn)的效用值。如此繼續(xù)，可得到在及中間的一系列的效用值。再以作橫坐標(biāo)，作縱坐標(biāo)可得該決策者的效用曲線。舉例如下。例設(shè)某決策者在股票交易所購(gòu)買(mǎi)股票，現(xiàn)有兩種選擇：選擇股票01號(hào)，預(yù)計(jì)每手（100股）可能分別以概率0.5獲利200元，概率0.5損失100元。74選擇股票02號(hào)，預(yù)計(jì)每手（100股）可能以概率1.0獲利25元。試問(wèn)該決策者應(yīng)選擇何種方式購(gòu)買(mǎi)股票？用心理測(cè)試法對(duì)該決策者提問(wèn)：⑴對(duì)上述事件，問(wèn)決策者愿意選擇何種方式？決策者B01號(hào)股票02號(hào)股票0.5P=0.5-100元P=0.525元200元若決策者選擇，則降低到20元，若還選擇則再降低，若降至0元（即不賠不賺）時(shí)，決策者猶豫不定，說(shuō)明選擇股票01號(hào)，預(yù)計(jì)每手（100股）可能分別以概率0.5獲利200元，概率0.5損失100元。75此時(shí)隨機(jī)事件的效用值與相等。求出時(shí)的效益值：得到效用曲線的三點(diǎn)。0元P=1.0決策者01號(hào)股票02號(hào)股票0.5P=0.5-100元P=0.5200元B1B20.576決策者01號(hào)股票02號(hào)股票0.75P=0.50元P=0.540元200元選擇股票02號(hào)，預(yù)計(jì)每手（100股）可能以概率1.0獲利40元。試問(wèn)該決策者應(yīng)選擇何種方式購(gòu)買(mǎi)股票？⑵再求與之間某一點(diǎn)的效用值。提出如下的問(wèn)題：選擇股票01號(hào)，預(yù)計(jì)每手（100股）可能分別以概率0.5獲利200元，概率0.5損失0元。B1B2P=1.00.7577決策者01號(hào)股票02號(hào)股票0.75P=0.50元P=0.5200元B1B2P=1.00.7540元60元若決策者選擇，則提高02號(hào)股票到60元。決策者猶豫不定，說(shuō)明此時(shí)隨機(jī)事件的效用值與相等。求出時(shí)的效用值：得到效用曲線的四個(gè)點(diǎn)。78⑶提出如下的問(wèn)題，可得-100元到0元之間的某點(diǎn)效用值。

選擇股票01號(hào)，預(yù)計(jì)每手可能分別以概率0.5獲利0元，以概率0.5獲利-100元。決策者B101號(hào)股票02號(hào)股票P(pán)=0.5-100元P=0.5-30元0元B2P=1.0選擇股票02號(hào)，預(yù)計(jì)每手可能以概率1.0獲利-30元。79試問(wèn)該決策者應(yīng)選擇何種方式購(gòu)買(mǎi)股票？決策者01號(hào)股票02號(hào)股票0.25P=0.5-100元P=0.50元B1B2P=1.00.25-30元-60元80120元決策者01號(hào)股票02號(hào)股票0.875P=0.560元P=0.5200元B1B2P=1.00.875⑷同理在60元到200元之間求出某點(diǎn)的效用值。經(jīng)過(guò)幾次提問(wèn)，決策者穩(wěn)定在81對(duì)于此決策者，此時(shí)的心態(tài)，任給一個(gè)值，比如25元（橫坐標(biāo)），通過(guò)曲線，即可查出其效用值。三、效用曲線的類(lèi)型：ⅠⅡⅢ總體上講，效用曲線可分為：Ⅰ：保守型Ⅱ：中間型Ⅲ：冒險(xiǎn)型82ⅠⅡⅢ保守型的人對(duì)收益增加反映比較遲鈍，相反對(duì)損失反映比較敏感。冒險(xiǎn)型的人對(duì)損失增加反映比較遲鈍，相反對(duì)收益反映比較敏感。中間型介于兩者之間。83四、最大效用期望值決策準(zhǔn)則及其應(yīng)用最大效用期望值決策準(zhǔn)則，就是依據(jù)效用理論，通過(guò)效用函數(shù)（或效用曲線）計(jì)算出各個(gè)策略結(jié)點(diǎn)的效用期望值，以效用期望值最大的策略作為最優(yōu)策略的選優(yōu)準(zhǔn)則。即以效用期望值代替風(fēng)險(xiǎn)型決策中的期望益損值進(jìn)行決策。例某廠計(jì)劃生產(chǎn)一種新產(chǎn)品，經(jīng)預(yù)測(cè)，該新產(chǎn)品銷(xiāo)路好與差的概率各占50%，該生產(chǎn)工藝有三種。第Ⅰ、Ⅱ種為現(xiàn)有工藝，第Ⅲ種為新工藝，因此第Ⅲ種工藝的生產(chǎn)有順利與不順利兩種情況，且已知順利的概率為0.8，不順利的概率為0.2。三種工藝在銷(xiāo)路好、差狀態(tài)下的收益值見(jiàn)收益值表。又利用84心理測(cè)試法，對(duì)該廠廠長(zhǎng)在生產(chǎn)工藝決策問(wèn)題上的效用函數(shù)已測(cè)出，見(jiàn)廠長(zhǎng)效用函數(shù)表?，F(xiàn)求：⑴作出此問(wèn)題的決策樹(shù)。⑵以最大期望益損值為最優(yōu)決策準(zhǔn)則求此問(wèn)題的最優(yōu)決策

⑶以最大效用期望值為最優(yōu)決策準(zhǔn)則求此問(wèn)題的最優(yōu)決策收益值r/萬(wàn)元2001005020-10-20-50-100效用值u(r)1.00.790.660.570.460.420.290廠長(zhǎng)效用值函數(shù)85ⅠⅡⅢ順利（0.8）不順利（0.2）銷(xiāo)路概率收益銷(xiāo)路概率收益銷(xiāo)路概率收益銷(xiāo)路概率收益好差0.50.520-10好差0.50.5100-20好差0.50.5200-50好差0.50.550-100收益值表單位：萬(wàn)元解：⑴作出此問(wèn)題的決策樹(shù)。86決策者工藝Ⅰ工藝ⅡⅠⅡⅢ新工藝Ⅲ銷(xiāo)路差0.5銷(xiāo)路好0.5銷(xiāo)路差0.5銷(xiāo)路好0.5ⅣⅤ順利0.8銷(xiāo)路好0.5銷(xiāo)路差0.5銷(xiāo)路好0.5銷(xiāo)路差0.554055不順利0.275收益值20-10100-20200-50-10050-2587⑵計(jì)算各結(jié)點(diǎn)的期望益損值：結(jié)點(diǎn)Ⅰ：萬(wàn)元結(jié)點(diǎn)Ⅱ：萬(wàn)元結(jié)點(diǎn)Ⅲ：萬(wàn)元結(jié)點(diǎn)Ⅳ：萬(wàn)元結(jié)點(diǎn)Ⅴ：萬(wàn)元從期望益損值可看出，第Ⅲ種工藝方案為最優(yōu)方案。此時(shí)最優(yōu)期望收益值為55萬(wàn)元。88決策者工藝Ⅰ工藝Ⅱ0.515ⅠⅡⅢ新工藝Ⅲ銷(xiāo)路差0.5銷(xiāo)路好0.5銷(xiāo)路差0.5銷(xiāo)路好0.5ⅣⅤ順利0.8銷(xiāo)路好0.5銷(xiāo)路差0.5銷(xiāo)路好0.5銷(xiāo)路差0.55400.605550.582不順利0.2750.645收益值效用值200.57-100.461000.79-200.422001.0-500.29-1000.0500.660.33-2589⑶計(jì)算各結(jié)點(diǎn)的效用期望值：結(jié)點(diǎn)Ⅰ：萬(wàn)元結(jié)點(diǎn)Ⅱ：萬(wàn)元結(jié)點(diǎn)Ⅲ：萬(wàn)元結(jié)點(diǎn)Ⅳ：萬(wàn)元結(jié)點(diǎn)Ⅴ：萬(wàn)元從效用期望值可看出，第Ⅱ種工藝方案為最優(yōu)方案。此時(shí)最大效用期望值為0.605。90用效用期望值作標(biāo)準(zhǔn)還有一個(gè)優(yōu)點(diǎn)是：對(duì)于不同量綱的目標(biāo)，可以折算成效用值，然后相加，求各個(gè)方案的總效用值來(lái)進(jìn)行比較。例某公司欲購(gòu)置一批汽車(chē)，須考查兩項(xiàng)指標(biāo)：功率和價(jià)格。該公司決策者認(rèn)為最合適的功率為70kw，若低于55kw，則不宜使用；而最滿(mǎn)意的價(jià)格為4.0萬(wàn)元。若超過(guò)5.6萬(wàn)元，則不能接受。目前市場(chǎng)上能滿(mǎn)足該公司基本要求的汽車(chē)型號(hào)有：Ⅰ，Ⅱ，Ⅲ。它們的功率和價(jià)格分別為91指標(biāo)牌號(hào)功率/kw價(jià)格/萬(wàn)元ⅠⅡⅢ6065704.14.55.2問(wèn)該公司決策者應(yīng)作何種決策？解：這是一個(gè)涉及功率和價(jià)格的多目標(biāo)決策問(wèn)題，且兩個(gè)目標(biāo)相互矛盾，量綱也不同，無(wú)法用絕對(duì)數(shù)字進(jìn)行比較。對(duì)此可用如下的方法：應(yīng)用效用理論，把每個(gè)方案的各個(gè)指標(biāo)折合成效用值，然后加權(quán)相加，計(jì)算出每個(gè)方案的總的效用值，然后進(jìn)行比較。92首先，應(yīng)用效用理論，給出該公司決策者的功率效用曲線與價(jià)格效用曲線，然后再求出下屬各點(diǎn)的效用值，其結(jié)果為：又通過(guò)詢(xún)問(wèn)，了解到?jīng)Q策者對(duì)功率與價(jià)格這兩個(gè)目標(biāo)的權(quán)重分別為0.6,0.4。因此可作出決策樹(shù)：93決策者0.63ⅠⅡⅢ價(jià)格0.4功率0.60.780.68功率0.6功率0.6價(jià)格0.4價(jià)格0.40.750.200.906070650.451.00.804.14.55.2計(jì)算各結(jié)點(diǎn)的效用期望值：94決策者0.63ⅠⅡⅢ價(jià)格0.4功率0.60.780.68功率0.6功率0.6價(jià)格0.4價(jià)格0.4因此，按效用期望值作標(biāo)準(zhǔn)，應(yīng)選擇第Ⅱ種牌號(hào)的車(chē)型為最優(yōu)決策。0.750.200.906070650.451.00.804.14.55.295層次分析法層次分析法（AnalyticalHierarchyProcess,簡(jiǎn)稱(chēng)AHP)是美國(guó)匹茲堡大學(xué)教授A.L.Saaty于20世紀(jì)70年代提出的一種系統(tǒng)分析方法。AHP是一種將定性分析與定量分析相結(jié)合的系統(tǒng)分析方法。在進(jìn)行系統(tǒng)分析時(shí)，經(jīng)常會(huì)碰到這樣的一類(lèi)問(wèn)題：有些問(wèn)題難以甚至根本不可能建立數(shù)學(xué)模型進(jìn)行定量分析；也可能由于時(shí)間緊，對(duì)有些問(wèn)題還來(lái)不及進(jìn)行過(guò)細(xì)的定量分析，只需作出初步的選擇和大致的判定就行了。例如選擇一個(gè)新廠的廠址，購(gòu)買(mǎi)一臺(tái)重要的設(shè)備，確定到哪里去旅游等等。這時(shí)，我們?nèi)魬?yīng)用AHP進(jìn)行分析，就可以簡(jiǎn)便地解決問(wèn)題。96將AHP引入決策，是決策科學(xué)化的一大進(jìn)步。它最適宜于解決難以完全用定量方法進(jìn)行分析的決策問(wèn)題。因此，它是復(fù)雜的社會(huì)經(jīng)濟(jì)系統(tǒng)實(shí)現(xiàn)科學(xué)決策的有力工具。一、AHP的基本原理為了說(shuō)明AHP的基本原理，首先讓我們分析下面的簡(jiǎn)單事實(shí)。假定我們已知n個(gè)西瓜的總重量為1，每個(gè)西瓜的重量為

問(wèn)每個(gè)西瓜相對(duì)于其他西瓜的相對(duì)重量是多重？可通過(guò)兩兩比較（相除），得到比較矩陣（以后稱(chēng)之為判斷矩陣）：97顯然矩陣A滿(mǎn)足（1）稱(chēng)滿(mǎn)足（1）式的矩陣為互反矩陣。且滿(mǎn)足（2）98即n是A的一個(gè)特征根，是A的對(duì)應(yīng)于特征根n的一個(gè)特征向量。設(shè)有99現(xiàn)在提出相反的問(wèn)題：如果事先不知道每個(gè)西瓜的重量，也沒(méi)有衡器去稱(chēng)量，如何判定每個(gè)西瓜的相對(duì)重量呢？即如何判定哪個(gè)最重，哪個(gè)次之，…哪個(gè)最輕呢？我們可以通過(guò)兩兩比較的方法，得出判斷矩陣A,然后求出A的最大特征值，進(jìn)而通過(guò)求出A的特征向量100然后通過(guò)將規(guī)范化：則即為n個(gè)西瓜的相對(duì)重量。101使用AHP，判斷矩陣的一致性是十分重要的。所謂判斷矩陣的一致性，即判斷矩陣是否滿(mǎn)足如下關(guān)系：若上式完全成立時(shí)，稱(chēng)判斷矩陣具有完全一致性?？梢宰C明，n階完全一致性矩陣具有以下的性質(zhì)：1。A的秩為1，A的唯一非零特征根為n。2。A的任一列（行）向量都是對(duì)應(yīng)于特征根n的特征向量。證明：設(shè)102是n階完全一致性矩陣，則103注意到：有104105所以106在一般情況下，可以證明判斷矩陣的最大特征值為單根，且當(dāng)判斷矩陣具有滿(mǎn)意的一致性時(shí)，稍大于矩陣階數(shù)，其余特征根接近于零。這時(shí)AHP得出的結(jié)論才基本合理。但由于客觀事物的復(fù)雜性和人們認(rèn)識(shí)上的多樣性，要求所有的判斷都有完全的一致性是不可能的，但我們要求一定程度上的判斷一致，因此對(duì)構(gòu)造的判斷矩陣需要進(jìn)行一致性檢驗(yàn)。107二、AHP的步驟用AHP分析問(wèn)題大體要經(jīng)過(guò)以下五個(gè)步驟：⑴建立層次結(jié)構(gòu)模型；⑵構(gòu)造判斷矩陣；⑶層次單排序；⑷層次總排序；⑸一致性檢驗(yàn)。其中后三個(gè)步驟在整個(gè)過(guò)程中需要逐層地進(jìn)行。108⑴建立層次結(jié)構(gòu)模型人們?cè)谌粘Ｉ钪薪?jīng)常會(huì)碰到許多決策問(wèn)題：買(mǎi)一件襯衫，你要在棉的、絲的、滌綸的、…及花邊的、白的、方格的、…之中作出抉擇；請(qǐng)朋友吃飯，要籌劃是辦家宴還是去飯店，是吃中餐還是西餐或自助餐；假期旅游，是去風(fēng)光綺麗的杭州，還是去迷人的北戴河，或者是去山水甲天下的桂林。如果你以為這些日常生活小事不必作為決策問(wèn)題認(rèn)真對(duì)待的話，那么，當(dāng)你面臨報(bào)考學(xué)校、選擇專(zhuān)業(yè)，或者抉擇工作崗位的時(shí)候，就要慎重考慮、反復(fù)考慮，盡可能地做出滿(mǎn)意的抉擇了。109從事各種職業(yè)的人也經(jīng)常面臨決策：一個(gè)廠長(zhǎng)要決定購(gòu)買(mǎi)哪種設(shè)備，上馬什么產(chǎn)品；科技人員要選擇研究課題；醫(yī)生要為疑難病例選擇治療方案；經(jīng)理要從若干應(yīng)試者中選擇秘書(shū)；各地區(qū)、各部門(mén)的官員要對(duì)人口、交通、經(jīng)濟(jì)、環(huán)境等領(lǐng)域的發(fā)展規(guī)劃作出決策。層次分析法的基本思路與人對(duì)一個(gè)復(fù)雜的決策問(wèn)題的思維、判斷過(guò)程大體上類(lèi)似。不妨用前面提到過(guò)的假期旅游為例，假如有、、三個(gè)旅游勝地供你選擇，你會(huì)根據(jù)諸如景色、費(fèi)用、居住、飲食、旅途條件等一些準(zhǔn)則去反復(fù)比較哪三個(gè)候選地點(diǎn)。首先，你會(huì)確定這些準(zhǔn)則在你心目中各占多大比重，如110果你經(jīng)濟(jì)寬綽、醉心旅游，自然特別看重景色，而平素簡(jiǎn)樸或手頭拮據(jù)的人則會(huì)優(yōu)先考慮費(fèi)用，中老年則會(huì)對(duì)居住、飲食等條件給予較大關(guān)注。其次，你會(huì)就每一準(zhǔn)則將三個(gè)地點(diǎn)進(jìn)行對(duì)比，譬如景色最好，次之；費(fèi)用最低，次之；居住條件較好等。最后，你要將這兩個(gè)層次的比較判斷進(jìn)行綜合，在，，中確定哪個(gè)作為最佳地點(diǎn)。上面的思維過(guò)程可以加工整理成以下幾個(gè)步驟：1．將決策問(wèn)題分解為3個(gè)層次，最上層為目標(biāo)層，即選擇旅游地，最下層為方案層，有，，3個(gè)供你選擇地點(diǎn)，中間層為準(zhǔn)則層，有景色、費(fèi)用、居住、飲食、旅途5個(gè)準(zhǔn)則，各層間的聯(lián)系用相連的直線表示。見(jiàn)下圖111目標(biāo)層選擇旅游地景色費(fèi)用居住飲食旅途準(zhǔn)則層方案層圖5.1選擇旅游地的層次結(jié)構(gòu)112⑵構(gòu)造判斷矩陣①通過(guò)相互比較確定各準(zhǔn)則對(duì)于目標(biāo)的權(quán)重，即構(gòu)造判斷矩陣。設(shè)準(zhǔn)則層5個(gè)準(zhǔn)則景色，費(fèi)用，居住，飲食旅途。相對(duì)于目標(biāo)層：選擇旅游地，兩兩比較打分。相對(duì)重要程度定義解釋135792，4，6，8同等重要略微重要相當(dāng)重要明顯重要絕對(duì)重要介于兩重要程度之間目標(biāo)i與j同樣重要目標(biāo)i比j略微重要目標(biāo)i比j重要目標(biāo)i比j明顯重要目標(biāo)i比j絕對(duì)重要113采用1～9的比例表度的依據(jù)是：①心理學(xué)的實(shí)驗(yàn)表明，大多數(shù)人對(duì)不同事物在相同屬性上的差別的分辨能力在5～9，采用1～9的標(biāo)度反映了大多數(shù)人的判斷能力；②大量的社會(huì)調(diào)查表明，1～9的比例標(biāo)度早已被人們所熟悉和采用；③科學(xué)考察和實(shí)踐表明，1～9的比例標(biāo)度已完全能區(qū)分引起人們感覺(jué)差別的事物的各種屬性。114選擇旅游地景色費(fèi)用居住飲食旅途115相對(duì)于景色相對(duì)于費(fèi)用相對(duì)于居住相對(duì)于飲食116相對(duì)于旅途⑶層次單排序所謂層次單排序是指，對(duì)于上一層某因素而言，本層次各因素的重要性的排序。具體計(jì)算是：對(duì)于判斷矩陣B，計(jì)算滿(mǎn)足117的特征根與特征向量，式中為的最大特征根，為對(duì)應(yīng)于的正規(guī)化的特征向量，的分量即是相應(yīng)元素單排序的權(quán)值。自上而下，先求判斷矩陣A的最大特征值與特征向量。118例如：相對(duì)于景色經(jīng)計(jì)算對(duì)應(yīng)于的正規(guī)化的特征向量為對(duì)應(yīng)于的正規(guī)化的特征向量為119同理算出的最大特征值分別為：所對(duì)應(yīng)的特征向量分別為120將5個(gè)特征向量按列依次排成一矩陣：為了檢驗(yàn)矩陣的一致性，需要計(jì)算它的一致性指標(biāo)CI，定義一般的，只要就可認(rèn)為判斷矩陣具有滿(mǎn)意的一致性。121⑷層次總排序各個(gè)方案優(yōu)先程度的排序向量為首選旅游地為，其次為，再者122一般地，若層次結(jié)構(gòu)有k個(gè)層次（目標(biāo)層算第一層），則方案的優(yōu)先程度的排序向量為123二、層次分析法的計(jì)算方法層次分析法有兩大問(wèn)題：①判斷矩陣一致性的調(diào)整；②判斷矩陣的最大特征根與特征向量的計(jì)算。對(duì)于②，精確解應(yīng)是線性代數(shù)中的計(jì)算方法。但從使用的角度看，一般采用近似方法計(jì)算。主要有三種計(jì)算方法。1、冪法冪法使我們有可能利用計(jì)算機(jī)得到任意精確解的最大特征根及其對(duì)應(yīng)的特征向量。步驟為⑴任取與判斷矩陣B同價(jià)的正規(guī)化的初始向量；⑵計(jì)算124⑶令計(jì)算⑷對(duì)于預(yù)先給定的精確度，當(dāng)對(duì)所有i=1,2,…n成立時(shí)，則為所求特征向量?？捎上率角蟮檬街校簄為矩陣的階數(shù)；為向量的第i個(gè)分量。1252、和積法為簡(jiǎn)化計(jì)算，可采用近似方法—和積法計(jì)算，它可以用計(jì)算器在保證足夠精確度的條件下運(yùn)用AHP。其具體計(jì)算步驟為：⑴將判斷矩陣每一列正規(guī)化⑵將按行相加126⑶將規(guī)范化得向量127⑷計(jì)算判斷矩陣最大特征根例用和積法求下列的判斷矩陣的最大特征值和相應(yīng)的特征向量。128列向量規(guī)一化按行求和規(guī)一化129這個(gè)方法實(shí)際上是將A的列向量規(guī)一化后取平均值，作為A的特征向量。因?yàn)楫?dāng)A為一致陣時(shí)，它的每一列向量都是特征向量，所以當(dāng)A的不一致性不嚴(yán)重時(shí)，取A的列向量（歸一化后）平均值作為近似特征向量是合理的。1303.方根法⑴將判斷矩陣每一列正規(guī)化⑵將按行相乘⑶將規(guī)范化131得向量⑷計(jì)算判斷矩陣最大特征根132例9某單位擬從3名干部中選拔一名領(lǐng)導(dǎo)，選拔的標(biāo)準(zhǔn)有政策水平、工作作風(fēng)、業(yè)務(wù)知識(shí)、口才、寫(xiě)作能力和健康狀況。下面用AHP方法對(duì)3人綜合評(píng)估、量化排序。⑴建立層次結(jié)構(gòu)模型133目標(biāo)層選一領(lǐng)導(dǎo)干部健康狀況業(yè)務(wù)知識(shí)口才寫(xiě)作能力工作作風(fēng)準(zhǔn)則層方案層政策水平134健康情況業(yè)務(wù)知識(shí)寫(xiě)作能力口才政策水平工作作風(fēng)健康情況業(yè)務(wù)知識(shí)寫(xiě)作能力口才政策水平工作作風(fēng)A的最大特征值相應(yīng)的特征向量為：135假設(shè)3人關(guān)于6個(gè)標(biāo)準(zhǔn)的判斷矩陣為：健康情況業(yè)務(wù)知識(shí)寫(xiě)作能力口才136政策水平工作作風(fēng)由此可求得各屬性的最大特征值和相應(yīng)的特征向量。特征值健康情況業(yè)務(wù)知識(shí)寫(xiě)作能力口才政策水平工作作風(fēng)

3.023.023.563.053.003.21各屬性的最大特征值137從而有138即在3人中應(yīng)選擇A擔(dān)任領(lǐng)導(dǎo)職務(wù)。139現(xiàn)代優(yōu)化算法140現(xiàn)代優(yōu)化算法的重要性141現(xiàn)代優(yōu)化算法禁忌搜索算法模擬退火算法遺傳算法人工神經(jīng)網(wǎng)絡(luò)蟻群算法粒子群算法混合算法特點(diǎn)：基于客觀世界中的一些自然現(xiàn)象；建立在計(jì)算機(jī)迭代計(jì)算的基礎(chǔ)上；具有普適性，可解決實(shí)際應(yīng)用問(wèn)題。142如何解決問(wèn)題？經(jīng)典數(shù)學(xué)理論的解法：Viete

定理：由公理、定理形成的演繹邏輯體系優(yōu)點(diǎn)：準(zhǔn)確、快速、有明確數(shù)學(xué)意義不足：只能解決有限問(wèn)題、解法是特定的無(wú)法解決高次問(wèn)題及更復(fù)雜問(wèn)題?？紤]一個(gè)一元方程：143數(shù)值解法：

通過(guò)引入一些假設(shè)來(lái)獲得問(wèn)題的近似解

取初始值為1，代入得：

11.580531.577021.57705

優(yōu)點(diǎn)：可求解問(wèn)題的范圍比較廣泛

不足：解法的特殊性，要求迭代收斂如何解決問(wèn)題？（1）144傳統(tǒng)算法的局限解法是特定的

----不同的問(wèn)題需要使用不同的解法所能解決的問(wèn)題是有限的

----和數(shù)學(xué)工具直接相關(guān)，若沒(méi)有解決問(wèn)題的數(shù)學(xué)方法，則難以解決

145現(xiàn)代優(yōu)化算法

現(xiàn)代優(yōu)化算法又稱(chēng)智能優(yōu)化算法或現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)、且適合于并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù),而不是單純憑借專(zhuān)家經(jīng)驗(yàn)，理論上可以在一定的時(shí)間內(nèi)找到最優(yōu)解或近似最優(yōu)解。146現(xiàn)代優(yōu)化算法的特點(diǎn)它們的共同特點(diǎn)：都是從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個(gè)求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴(kuò)展到整個(gè)問(wèn)題空間，因而具有全局優(yōu)化性能。147全局優(yōu)化Rastrigin’sFunction全局最小點(diǎn)(0,0)148現(xiàn)代優(yōu)化算法特點(diǎn)：1)不依賴(lài)于初始條件；2)不與求解空間有緊密關(guān)系,對(duì)解域無(wú)可微或連續(xù)的要求;容易實(shí)現(xiàn)，求解穩(wěn)健。3)能獲得全局最優(yōu);適合于求解空間不知的情況。4)SA,GA可應(yīng)用于大規(guī)模、多峰多態(tài)函數(shù)、含離散變量等全局優(yōu)化問(wèn)題;求解速度和質(zhì)量遠(yuǎn)超過(guò)常規(guī)方法。149常用的現(xiàn)代優(yōu)化算法

遺傳算法

GeneticAlgorithm，簡(jiǎn)稱(chēng)GA模擬退火算法

SimulatedAnnealing，簡(jiǎn)稱(chēng)SA禁忌搜索算法神經(jīng)網(wǎng)絡(luò)算法群智能算法，包括蟻群算法、粒子群算法微分進(jìn)化算法（DifferentialEvolution）……150搜索示例：三個(gè)孩子的年齡(1)兩個(gè)多年未見(jiàn)的朋友相遇，聊了很多事情?！瑼：既然你是數(shù)學(xué)教授，那你幫我算這個(gè)題，今天是個(gè)特殊日子：我三個(gè)兒子都在今天慶祝生日！那么你能算出他們都有多大嗎？B：好，但你得跟我講講他們的情況。A：好的，我給你一些提示，他們?nèi)齻€(gè)年齡之積是36.B：很好，但我還需要更多提示。151三個(gè)孩子的年齡(2)A：我的大兒子的眼睛是藍(lán)色的。B考慮了一下說(shuō)，但是，我還有一點(diǎn)信息來(lái)解決你的這個(gè)難題。B：哦，夠了，B給出了正確的答案，即三個(gè)小孩的年齡。A：他們?nèi)齻€(gè)年齡之和等于那幢房子的窗戶(hù)個(gè)數(shù)。A指著對(duì)面的一幢房子說(shuō)。152三個(gè)孩子的年齡(3)根據(jù)對(duì)話信息，用搜索的方法來(lái)解此問(wèn)題。信息1:三個(gè)小孩年齡之積為36只有以下8種可能，搜索范圍減少至8種情況:第一個(gè)小孩年齡36181299664第二個(gè)小孩年齡12342633第三個(gè)小孩年齡11112123153三個(gè)孩子的年齡(4)信息2:三個(gè)小孩年齡之和等于窗戶(hù)數(shù)第一個(gè)小孩年齡36181299664第二個(gè)小孩年齡12342633第三個(gè)小孩年齡11112123窗戶(hù)數(shù):3821161413131110如果窗戶(hù)數(shù)為38、21、16、14、11、10即可得出答案B還需信息，即窗戶(hù)數(shù)為13.則可能為(9、2、2)或(6、6、1)信息2:大兒子眼睛是藍(lán)色的得答案：(9、2、2)154典型問(wèn)題——旅行商問(wèn)題（Travelingsalesmanproblem,TSP）給定n個(gè)城市和兩兩城市之間的距離，要求確定一條經(jīng)過(guò)各城市當(dāng)且僅當(dāng)一次的最短路線。123412181032搜索示例：TSP問(wèn)題155典型問(wèn)題——旅行商問(wèn)題（Travelingsalesmanproblem,TSP）計(jì)算復(fù)雜度：指數(shù)災(zāi)難

城市數(shù)2425262728293031計(jì)算時(shí)間1sec24sec10min4.3hour4.9day136.5day10.8year325yearTSP的搜索的困難156模擬退火法157模擬退火算法及模型

算法的提出

模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的解決NP復(fù)雜性問(wèn)題；克服優(yōu)化過(guò)程陷入局部極??；克服初值依賴(lài)性。物理退火過(guò)程158物理退火過(guò)程

什么是退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。物理退火過(guò)程159模擬退火算法及模型

物理退火過(guò)程

加溫過(guò)程——增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可能存在的非均勻態(tài)；等溫過(guò)程——對(duì)于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)；冷卻過(guò)程——使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。物理退火過(guò)程160161模擬退火算法及模型

數(shù)學(xué)表述

在溫度T，分子停留在狀態(tài)r滿(mǎn)足Boltzmann概率分布物理退火過(guò)程162模擬退火算法及模型

數(shù)學(xué)表述在同一個(gè)溫度T，選定兩個(gè)能量E1<E2，有在同一個(gè)溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。物理退火過(guò)程<1>0163模擬退火算法及模型

數(shù)學(xué)表述

若|D|為狀態(tài)空間D中狀態(tài)的個(gè)數(shù)，D0是具有最低能量的狀態(tài)集合：當(dāng)溫度很高時(shí)，每個(gè)狀態(tài)概率基本相同，接近平均值1/|D|；狀態(tài)空間存在超過(guò)兩個(gè)不同能量時(shí)，具有最低能量狀態(tài)的概率超出平均值1/|D|；當(dāng)溫度趨于0時(shí)，分子停留在最低能量狀態(tài)的概率趨于1。物理退火過(guò)程能量最低狀態(tài)非能量最低狀態(tài)164模擬退火算法及模型

Metropolis準(zhǔn)則（1953）——以概率接受新?tīng)顟B(tài)固體在恒定溫度下達(dá)到熱平衡的過(guò)程可以用MonteCarlo方法（計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。物理退火過(guò)程165模擬退火算法及模型

Metropolis準(zhǔn)則（1953）——以概率接受新?tīng)顟B(tài)若在溫度T，當(dāng)前狀態(tài)i→新?tīng)顟B(tài)j

若Ej<Ei，則接受j為當(dāng)前狀態(tài)；否則，若概率p=exp[-(Ej-Ei)/kBT]

大于[0,1)區(qū)間的隨機(jī)數(shù)，則仍接受狀態(tài)j

為當(dāng)前狀態(tài)；若不成立則保留狀態(tài)i

為當(dāng)前狀態(tài)。物理退火過(guò)程166模擬退火算法及模型

Metropolis準(zhǔn)則（1953）——以概率接受新?tīng)顟B(tài)

p=exp[-(Ej-Ei)/kBT]

在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新?tīng)顟B(tài)；在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新?tīng)顟B(tài)。物理退火過(guò)程167模擬退火算法及模型

相似性比較

組合優(yōu)化與物理退火的相似性組合優(yōu)化問(wèn)題金屬物體解粒子狀態(tài)最優(yōu)解能量最低的狀態(tài)設(shè)定初溫熔解過(guò)程Metropolis抽樣過(guò)程等溫過(guò)程控制參數(shù)的下降冷卻目標(biāo)函數(shù)能量168算法描述169案例講解已知敵方100個(gè)目標(biāo)的經(jīng)度、緯度我方有一個(gè)基地，經(jīng)度和緯度為（70,40）。假設(shè)我方飛機(jī)的速度為1000公里/小時(shí)。我方派一架飛機(jī)從基地出發(fā)，偵察完敵方所有目標(biāo)，再返回原來(lái)的基地。在敵方每一目標(biāo)點(diǎn)的偵察時(shí)間不計(jì)，求該架飛機(jī)所花費(fèi)的時(shí)間（假設(shè)我方飛機(jī)巡航時(shí)間可以充分長(zhǎng)）。170模擬退火算法及模型

基本步驟

給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)s=s0，令k=0；

RepeatRepeat

產(chǎn)生新?tīng)顟B(tài)sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽樣穩(wěn)定準(zhǔn)則滿(mǎn)足；退溫tk+1=update(tk)并令k=k+1；

Until算法終止準(zhǔn)則滿(mǎn)足；輸出算法搜索結(jié)果。模擬退火算法的基本思想和步驟171模擬退火算法及模型

影響優(yōu)化結(jié)果的主要因素

給定初溫t=t0，隨機(jī)產(chǎn)生初始狀態(tài)s=s0，令k=0；

RepeatRepeat

產(chǎn)生新?tīng)顟B(tài)sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽樣穩(wěn)定準(zhǔn)則滿(mǎn)足；退溫tk+1=update(tk)并令k=k+1；

Until算法終止準(zhǔn)則滿(mǎn)足；輸出算法搜索結(jié)果。模擬退火算法的基本思想和步驟三函數(shù)兩準(zhǔn)則初始溫度172173174175模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)原則

(1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率；

(2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減??；

(3)當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)下降的解。方法

具體形式對(duì)算法影響不大一般采用min[1,exp(-?C/t)]狀態(tài)接受函數(shù)176模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)收斂性分析