運籌學的優(yōu)化算法

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

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

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

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

03B

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

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

04B

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

05A

長江水質(zhì)的評價和預測：預測評價、數(shù)據(jù)處理

05B

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

06A

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

數(shù)學建模競賽中的算法(4)906B

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

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

公交車問題：多目標規(guī)劃、動態(tài)規(guī)劃、圖論、0-1規(guī)劃08A

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

大學學費問題：數(shù)據(jù)收集和處理、統(tǒng)計分析、回歸分析

數(shù)學建模競賽中的算法(5)10賽題發(fā)展的特點：

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

2.賽題的開放性增大:

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

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

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

111.

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

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

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

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

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

圖論問題

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

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

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

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

[xl]

或xl

[xl

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

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

3x1+4x2

124x1+2x2

9x1,x2

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

1,x1

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

3x1+4x2

124x1+2x2

9x1,x2

0，x1

1，整數(shù)用單純形法可解得相應的（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ù)用單純形法可解得相應的（P2）的最優(yōu)解（2，1/2）Z=9(1/2)29012344321x1x2再對（P1）x1

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

2（P4）x2

3P1P2P3P430（P1）兩個子問題：（P3）MaxZ=4x1+3x2s.t.

3x1+4x2

124x1+2x2

9x1,x2

0,x1

1,x2

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

3x1+4x2

124x1+2x2

9x1,x2

0,x1

1,x2

3整數(shù)用單純形法可解得相應的（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原問題的最優(yōu)解（1，2）Z=1033多階段決策過程最優(yōu)化多階段決策過程是指這樣一類特殊的活動過程，他們可以按時間順序分解成若干相互聯(lián)系的階段，在每個階段都要做出決策，全部過程的決策是一個決策序列，所以多階段決策問題也稱為序貫決策問題。動態(tài)規(guī)劃應用舉例34最優(yōu)化原理：最優(yōu)策略的任一后部子策略都是最優(yōu)的。無論以前狀態(tài)決策如何，從眼下直到最后的諸決策必構(gòu)成最優(yōu)子策略。例1最短路線問題AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143動態(tài)規(guī)劃應用舉例35例1多階段資源分配問題

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

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)，……

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

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

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

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

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

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

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

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

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

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

表14-1石油公司可能利潤收入表（單位：萬元）類型項目50萬桶

20萬桶

5萬桶

無油

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

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

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

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

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

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

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

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

通過引入一些假設來獲得問題的近似解

取初始值為1，代入得：

11.580531.577021.57705

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

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

----不同的問題需要使用不同的解法所能解決的問題是有限的

----和數(shù)學工具直接相關，若沒有解決問題的數(shù)學方法，則難以解決

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

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

遺傳算法

GeneticAlgorithm，簡稱GA模擬退火算法

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

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

算法的提出

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

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

物理退火過程

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

數(shù)學表述

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

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

數(shù)學表述

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

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

Metropolis準則（1953）——以概率接受新狀態(tài)若在溫度T，當前狀態(tài)i→新狀態(tài)j

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

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

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

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

Metropolis準則（1953）——以概率接受新狀態(tài)

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

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

相似性比較

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

基本步驟

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

RepeatRepeat

產(chǎn)生新狀態(tài)sj=Genete(s)；

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

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

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

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

RepeatRepeat

產(chǎn)生新狀態(tài)sj=Genete(s)；

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

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

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

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

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

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