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

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

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

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

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

[0,5]設(shè)xk為第k階段生產(chǎn)量，則有直接成本

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

sk-1=sk+xk-yk總成本遞推公式動(dòng)態(tài)規(guī)劃模型舉例第一階段最優(yōu)決策表第二階段：最大可能庫(kù)存量7件由狀態(tài)轉(zhuǎn)移方程：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)決策表，如下動(dòng)態(tài)規(guī)劃模型舉例第二階段最優(yōu)決策表第三階段：最大可能庫(kù)存量4件由狀態(tài)轉(zhuǎn)移方程：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)決策表，如下動(dòng)態(tài)規(guī)劃模型舉例第三階段最優(yōu)決策表第四階段：初始庫(kù)存量s4=0由狀態(tài)轉(zhuǎn)移方程：s3=s4+x4-60可知x46，由階段效果遞推公式有：f4(0,6)=d4(0,6)+f3*(0,10) =706+1902=2322得第四階段最優(yōu)決策表，如下回溯得此表動(dòng)態(tài)規(guī)劃模型舉例解四個(gè)季度為四個(gè)階段，采用階段編號(hào)與季度順序一致。設(shè)sk

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

為第k季的生產(chǎn)量，設(shè)yk

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

目標(biāo)函數(shù)為例2生產(chǎn)–庫(kù)存管理問(wèn)題設(shè)某廠計(jì)劃全年生產(chǎn)某種產(chǎn)品A。其四個(gè)季度的訂貨量分別為600公斤，700公斤，500公斤和1200公斤。已知生產(chǎn)產(chǎn)品A的生產(chǎn)費(fèi)用與產(chǎn)品的平方成正比，系數(shù)為0.005。廠內(nèi)有倉(cāng)庫(kù)可存放產(chǎn)品，存儲(chǔ)費(fèi)為每公斤每季度1元。求最佳的生產(chǎn)安排使年總成本最小。動(dòng)態(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)得：動(dòng)態(tài)規(guī)劃模型舉例第三步：(第二、三、四季度)總效果

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

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

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

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

資源分配問(wèn)題某公司有9個(gè)推銷員在全國(guó)三個(gè)不同市場(chǎng)推銷貨物，這三個(gè)市場(chǎng)里推銷人員數(shù)與收益的關(guān)系如下表，試作出使總收益最大的分配方案。解：設(shè)分配人員的順序?yàn)槭袌?chǎng)1,2,3，采用反向階段編號(hào)。設(shè)sk

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

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

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

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

日常工作、生活中的決策問(wèn)題

涉及經(jīng)濟(jì)、社會(huì)等方面的因素

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

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

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

將決策問(wèn)題分為3個(gè)層次：目標(biāo)層O，準(zhǔn)則層C，方案層P；每層有若干元素，

各層元素間的關(guān)系用相連的直線表示。

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

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

A的任一列向量是對(duì)應(yīng)于n的特征向量

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

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

取值1,2,…,9及其互反數(shù)1,1/2,…,1/9尺度13579相同稍強(qiáng)強(qiáng)明顯強(qiáng)絕對(duì)強(qiáng)aij=1,1/2,,…1/9的重要性與上面相反

便于定性到定量的轉(zhuǎn)化：成對(duì)比較陣和權(quán)向量層次分析法的基本步驟

心理學(xué)家認(rèn)為成對(duì)比較的因素不宜超過(guò)9個(gè)用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種比較尺度對(duì)若干實(shí)例構(gòu)造成對(duì)比較陣，算出權(quán)向量，與實(shí)際對(duì)比發(fā)現(xiàn)，1~9尺度較優(yōu)。層次分析法的基本步驟一致性檢驗(yàn)對(duì)A確定不一致的允許范圍已知：n階一致陣的唯一非零特征根為n可證：n階正互反陣最大特征根

n,且

=n時(shí)為一致陣定義一致性指標(biāo):CI越大，不一致越嚴(yán)重層次分析法的基本步驟RI000.580.901.121.241.321.411.451.491.51

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

2

…

n

權(quán)向量w1(3)w2(3)…

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

CIk

均可通過(guò)一致性檢驗(yàn)w(2)

方案P1對(duì)目標(biāo)的組合權(quán)重為方案層對(duì)目標(biāo)的組合權(quán)向量為(0.300,0.246,0.456)T層次分析法的基本步驟組合權(quán)向量第1層O第2層C1,…Cn第3層P1,…Pm第2層對(duì)第1層的權(quán)向量第3層對(duì)第2層各元素的權(quán)向量構(gòu)造矩陣則第3層對(duì)第1層的組合權(quán)向量第s層對(duì)第1層的組合權(quán)向量其中W(p)是由第p層對(duì)第p-1層權(quán)向量組成的矩陣層次分析法的基本步驟1）建立層次分析結(jié)構(gòu)模型深入分析實(shí)際問(wèn)題，將有關(guān)因素自上而下分層（目標(biāo)—準(zhǔn)則或指標(biāo)—方案或?qū)ο螅?，上層受下層影響，而層?nèi)各因素基本上相對(duì)獨(dú)立。2）構(gòu)造成對(duì)比較陣用成對(duì)比較法和1~9尺度，構(gòu)造各層對(duì)上一層每一因素的成對(duì)比較陣。3）計(jì)算權(quán)向量并作一致性檢驗(yàn)對(duì)每一成對(duì)比較陣計(jì)算最大特征根和特征向量，作一致性檢驗(yàn)，若通過(guò)，則特征向量為權(quán)向量。4）計(jì)算組合權(quán)向量（作組合一致性檢驗(yàn)*）組合權(quán)向量可作為決策的定量依據(jù)。層次分析法的基本步驟

應(yīng)用領(lǐng)域：經(jīng)濟(jì)計(jì)劃和管理，能源政策和分配，人才選拔和評(píng)價(jià)，生產(chǎn)決策，交通運(yùn)輸，科研選題，產(chǎn)業(yè)結(jié)構(gòu)，教育，醫(yī)療，環(huán)境，軍事等。