專題講座動態(tài)規(guī)劃與層次分析法

專題講座動態(tài)規(guī)劃與層次分析法內容說明以下內容在《數學建模與數學實驗（第二版）》（汪曉銀，周保平主編）第6章、第9章。動態(tài)規(guī)劃內容提要動態(tài)規(guī)劃的最優(yōu)化原理動態(tài)規(guī)劃的基本概念及遞推公式動態(tài)規(guī)劃模型舉例動態(tài)規(guī)劃程序例1最短路問題五十年代貝爾曼(B.E.Bellman)為代表的研究成果屬于現代控制理論的一部分以長遠利益為目標的一系列決策最優(yōu)化原理，可歸結為一個遞推公式動態(tài)規(guī)劃的最優(yōu)化原理可以枚舉出20條路徑，其中最短的路徑長度為16決策樹法動態(tài)規(guī)劃的最優(yōu)化原理最優(yōu)性原理“最優(yōu)策略的一部分也是最優(yōu)的。因此我們可以從B向回搜索最短路表現為明顯的階段性動態(tài)規(guī)劃的最優(yōu)化原理基本概念及遞推公式狀態(tài)最短路問題中，各個節(jié)點就是狀態(tài)。生產庫存問題中，庫存量是狀態(tài)。物資分配問題中，剩余的物資量是狀態(tài)控制變量(決策變量)最短路問題中，走哪條路。生產庫存問題中，各階段的產品生產量。物資分配問題中，分配給每個地區(qū)的物資量。階段的編號與遞推的方向一般采用反向遞推，所以階段的編號也是逆向的當然也可以正向遞推動態(tài)規(guī)劃的步驟1、確定問題的階段和編號2、確定狀態(tài)變量用Sk

表示第k階段的狀態(tài)變量及其值3、確定決策變量用xk表示第k階段的決策變量，并以xk*表示該階段的最優(yōu)決策4、狀態(tài)轉移方程sk-1=g(sk,xk)反向編號sk+1=g(sk,xk)正向編號5、直接效果直接一步轉移的效果dk(sk,xk)6、總效果函數指某階段某狀態(tài)下到終端狀態(tài)的總效果，它是一個遞推公式終端的邊際效果一般為f0(s0,x0)=0(2)如串聯系統可靠性問題，是連乘形式，此時有終端的邊際效果一般為f0(s0,x0)=1從第1階段開始，利用邊際效果和邊界條件，可以遞推到最后階段hk是一般表達形式，求當前階段當前狀態(tài)下的階段最優(yōu)總效果(1)如最短路問題，是累加形式，此時有動態(tài)規(guī)劃的步驟動態(tài)規(guī)劃模型舉例例1產品生產計劃安排問題

某工廠生產某種產品的月生產能力為10件，已知今后四個月的產品成本及銷售量如表所示。如果本月產量超過銷售量時，可以存儲起來備以后各月銷售，一件產品的月存儲費為2元，試安排月生產計劃并做到：1、保證滿足每月的銷售量，并規(guī)定計劃期初和期末庫存為零；2、在生產能力允許范圍內，安排每月生產量計劃使產品總成本(即生產費用加存儲費)最低。第一階段：(即第4月份)由邊界條件和狀態(tài)轉移方程s0=s1+x1-y1=s1+x1–6=0得

s1+x1=6或x1=6–s1估計第一階段，即第4月份初庫存的可能狀態(tài)：s1

[0,5]設xk為第k階段生產量，則有直接成本

dk(sk,xk)=ckxk+2sk狀態(tài)轉移公式為

sk-1=sk+xk-yk總成本遞推公式動態(tài)規(guī)劃模型舉例第一階段最優(yōu)決策表第二階段：最大可能庫存量7件由狀態(tài)轉移方程：s1=s2+x2-120及x210，可知s2[2,7]，minx2=5由階段效果遞推公式有：f2(2,10)=d2(2,10)+f1*(0,6) =22+8010+456=1260得第二階段最優(yōu)決策表，如下動態(tài)規(guī)劃模型舉例第二階段最優(yōu)決策表第三階段：最大可能庫存量4件由狀態(tài)轉移方程：s2=s3+x3-72及x310，可知s3[0,4]，minx3=5由階段效果遞推公式有：f3(1,10)=d3(1,10)+f2*(4,8) =21+7210+1104=1826得第三階段最優(yōu)決策表，如下動態(tài)規(guī)劃模型舉例第三階段最優(yōu)決策表第四階段：初始庫存量s4=0由狀態(tài)轉移方程：s3=s4+x4-60可知x46，由階段效果遞推公式有：f4(0,6)=d4(0,6)+f3*(0,10) =706+1902=2322得第四階段最優(yōu)決策表，如下回溯得此表動態(tài)規(guī)劃模型舉例解四個季度為四個階段，采用階段編號與季度順序一致。設sk

為第k季初的庫存量，則邊界條件為s1=s5=0設xk

為第k季的生產量，設yk

為第k季的訂貨量；sk，xk，yk都取實數，狀態(tài)轉移方程為sk+1=sk+xk-yk仍采用反向遞推，但注意階段編號是正向的

目標函數為例2生產–庫存管理問題設某廠計劃全年生產某種產品A。其四個季度的訂貨量分別為600公斤，700公斤，500公斤和1200公斤。已知生產產品A的生產費用與產品的平方成正比，系數為0.005。廠內有倉庫可存放產品，存儲費為每公斤每季度1元。求最佳的生產安排使年總成本最小。動態(tài)規(guī)劃模型舉例第一步：(第四季度)總效果f4(s4,x4)=0.005x42+s4

由邊界條件有：s5=s4+x4–y4=0，解得：x4*=1200–s4

將x4*代入f4(s4,x4)得：

f4*(s4)=0.005(1200–s4)2+s4=7200–11s4+0.005s42第二步：(第三、四季度)總效果f3(s3,x3)=0.005x32+s3+f4*(s4)將s4=s3+x3–500代入f3(s3,x3)得：動態(tài)規(guī)劃模型舉例第三步：(第二、三、四季度)總效果

f2(s2,x2)=0.005x22+s2+f3*(s3)將s3=s2+x2-700代入f2(s2,x2)得：

注意：最優(yōu)階段總效果僅是當前狀態(tài)的函數，與其后的決策無關動態(tài)規(guī)劃模型舉例第四步：(第一、二、三、四季度)總效果

f1(s1,x1)=0.005x12+s1+f2*(s2)將s2=s1+x1–600=x1–600代入f1(s1,x1)得：由此回溯：得最優(yōu)生產–庫存方案

x1*=600，s2*=0；x2*=700，s3*=0；x3*=800，s4*=300；x4*=900。動態(tài)規(guī)劃模型舉例例3

資源分配問題某公司有9個推銷員在全國三個不同市場推銷貨物，這三個市場里推銷人員數與收益的關系如下表，試作出使總收益最大的分配方案。解：設分配人員的順序為市場1,2,3，采用反向階段編號。設sk

為第k階段尚未分配的人員數，邊界條件為s3=9設xk

為第k階段分配的推銷人員數；仍采用反向遞推，狀態(tài)轉移方程為sk–1=sk–xk

目標函數為動態(tài)規(guī)劃模型舉例s1有0~9種可能，第一階段（第三市場）最優(yōu)決策表如下：為什么與例1的第一階段的表有差別？動態(tài)規(guī)劃模型舉例s2有0~9種可能，第二階段最優(yōu)決策表如下：動態(tài)規(guī)劃模型舉例

由邊界條件s3=9，第三階段最優(yōu)決策表如下：得決策過程：x3*=2,x2*=0,x1*=7,f3*=218即市場1分配2人，市場2不分配，市場3分配7人最優(yōu)解與分配的順序有關嗎？動態(tài)規(guī)劃模型舉例層次分析法背景層次分析法的基本步驟層次分析法的廣泛應用層次分析法內容提要

日常工作、生活中的決策問題

涉及經濟、社會等方面的因素

作比較判斷時人的主觀選擇起相當大的作用，各因素的重要性難以量化

Saaty于1970年代提出層次分析法AHP(AnalyticHierarchyProcess)

AHP——一種定性與定量相結合的、系統化、層次化的分析方法背景目標層O(選擇旅游地)P2黃山P1桂林P3北戴河準則層方案層C3居住C1景色C2費用C4飲食C5旅途層次分析法的基本步驟例.選擇旅游地如何在3個目的地中按照景色、費用、居住條件等因素選擇.“選擇旅游地”思維過程的歸納

將決策問題分為3個層次：目標層O，準則層C，方案層P；每層有若干元素，

各層元素間的關系用相連的直線表示。

通過相互比較確定各準則對目標的權重，及各方案對每一準則的權重。將上述兩組權重進行綜合，確定各方案對目標的權重。層次分析法將定性分析與定量分析結合起來完成以上步驟，給出決策問題的定量結果。層次分析法的基本步驟成對比較陣和權向量元素之間兩兩對比，對比采用相對尺度設要比較各準則C1,C2,…,Cn對目標O的重要性A~成對比較陣A是正互反陣要由A確定C1,…,Cn對O的權向量選擇旅游地層次分析法的基本步驟成對比較的不一致情況一致比較不一致允許不一致，但要確定不一致的允許范圍成對比較陣和權向量層次分析法的基本步驟考察完全一致的情況層次分析法的基本步驟成對比較完全一致的情況滿足的正互反陣A稱一致陣，如成對比較陣和權向量層次分析法的基本步驟

A的秩為1，A的唯一非零特征根為n

A的任一列向量是對應于n的特征向量

A的歸一化特征向量可作為權向量對于不一致(但在允許范圍內)的成對比較陣A，建議用對應于最大特征根的特征向量作為權向量w，即一致陣性質層次分析法的基本步驟2468比較尺度aij

Saaty等人提出1~9尺度——aij

取值1,2,…,9及其互反數1,1/2,…,1/9尺度13579相同稍強強明顯強絕對強aij=1,1/2,,…1/9的重要性與上面相反

便于定性到定量的轉化：成對比較陣和權向量層次分析法的基本步驟

心理學家認為成對比較的因素不宜超過9個用1~3,1~5,…1~17,…,1p~9p

(p=2,3,4,5),d+0.1~d+0.9(d=1,2,3,4)等27種比較尺度對若干實例構造成對比較陣，算出權向量，與實際對比發(fā)現，1~9尺度較優(yōu)。層次分析法的基本步驟一致性檢驗對A確定不一致的允許范圍已知：n階一致陣的唯一非零特征根為n可證：n階正互反陣最大特征根

n,且

=n時為一致陣定義一致性指標:CI越大，不一致越嚴重層次分析法的基本步驟RI000.580.901.121.241.321.411.451.491.51

n1234567891110為衡量CI的大小，引入隨機一致性指標RI——隨機模擬得到aij,形成A，計算CI即得RI。定義一致性比率CR=CI/RI當CR<0.1時，通過一致性檢驗Saaty的結果如下層次分析法的基本步驟“選擇旅游地”中準則層對目標的權向量及一致性檢驗準則層對目標的成對比較陣最大特征根權向量(特征向量)w=(0.263,0.475,0.055,0.090,0.110)T一致性指標隨機一致性指標RI=1.12(查表)一致性比率CR通過一致性檢驗層次分析法的基本步驟組合權向量記第2層（準則）對第1層（目標）的權向量為同樣求第3層(方案)對第2層每一元素(準則)的權向量方案層對C1(景色)的成對比較陣方案層對C2(費用)的成對比較陣…Cn…Bn最大特征根1

2

…

n

權向量w1(3)w2(3)…

wn(3)層次分析法的基本步驟第3層對第2層的計算結果k10.5950.2770.1293.0050.0030.00100.00503.0020.6820.2360.082230.1420.4290.42933.0090.1750.1930.633430.6680.1660.1665組合權向量RI=0.58(n=3),

CIk

均可通過一致性檢驗w(2)

方案P1對目標的組合權重為方案層對目標的組合權向量為(0.300,0.246,0.456)T層次分析法的基本步驟組合權向量第1層O第2層C1,…Cn第3層P1,…Pm第2層對第1層的權向量第3層對第2層各元素的權向量構造矩陣則第3層對第1層的組合權向量第s層對第1層的組合權向量其中W(p)是由第p層對第p-1層權向量組成的矩陣層次分析法的基本步驟1）建立層次分析結構模型深入分析實際問題，將有關因素自上而下分層（目標—準則或指標—方案或對象），上層受下層影響，而層內各因素基本上相對獨立。2）構造成對比較陣用成對比較法和1~9尺度，構造各層對上一層每一因素的成對比較陣。3）計算權向量并作一致性檢驗對每一成對比較陣計算最大特征根和特征向量，作一致性檢驗，若通過，則特征向量為權向量。4）計算組合權向量（作組合一致性檢驗*）組合權向量可作為決策的定量依據。層次分析法的基本步驟

應用領域：經濟計劃和管理，能源政策和分配，人才選拔和評價，生產決策，交通運輸，科研選題，產業(yè)結構，教育，醫(yī)療，環(huán)境，軍事等。