運(yùn)籌08(第八章動(dòng)態(tài)規(guī)劃)ppt課件

1、2021/1/29,1,運(yùn)籌學(xué)OPERATIONS RESEARCH,2021/1/29,2,第八章 動(dòng)態(tài)規(guī)劃,1多階段決策最優(yōu)化問題舉例 2基本概念、基本方程與最優(yōu)化原理 3離散確定性動(dòng)態(tài)規(guī)劃求解 4離散隨機(jī)性動(dòng)態(tài)規(guī)劃求解 5一般數(shù)學(xué)規(guī)劃模型的動(dòng)態(tài)規(guī)劃解法,2021/1/29,3,1多階段決策過程最優(yōu)化問題舉例,例1 最短路徑問題 下圖表示從起點(diǎn)A到終點(diǎn)E之間各點(diǎn)的距離。求A到E的最 短路徑,B,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,2,2,1,6,4,7,2,4,8,3,8,6,7,5,6,1,10,6,3,7,5,1,2021/1/29,4,用窮舉法的計(jì)

2、算量: 如果從A到E的站點(diǎn)有k個(gè)，除A、E之外每站有3個(gè)位置則 總共有3k-12條路徑； 計(jì)算各路徑長度總共要進(jìn)行 (k+1) 3k-12次加法以及 3k-12-1次比較。隨著 k 的值增加時(shí)，需要進(jìn)行的加法和比較的次數(shù)將迅速增加； 例如當(dāng) k=20時(shí)，加法次數(shù)為 4.25508339662271015 次，比較 1.37260754729771014 次。若用1億次/秒的計(jì)算機(jī)計(jì)算需要約508天,2021/1/29,5,討論： 1、求從A到E的最短路徑問題，可以轉(zhuǎn)化為四個(gè)性質(zhì)完全相同，但規(guī)模較小的子問題，即分別從Di 、Ci、Bi、A到E的最短路徑問題。 第四階段：兩個(gè)始點(diǎn)D1和D2，終點(diǎn)只

3、有一個(gè)； 分析得知：從D1和D2到E的最短路徑唯一,2021/1/29,6,第三階段：有三個(gè)始點(diǎn)C1，C2，C3，終點(diǎn)有D1，D2，對始點(diǎn) 和終點(diǎn)進(jìn)行分析和討論分別求C1，C2，C3到D1，D2 的最短路 徑問題： 表-2 分析得知：如果經(jīng)過C1，則最短路為C1-D2-E； 如果經(jīng)過C2，則最短路為C2-D2-E； 如果經(jīng)過C3，則最短路為C3-D1-E,2021/1/29,7,第二階段：有4個(gè)始點(diǎn)B1,B2,B3,B4，終點(diǎn)有C1,C2,C3。對始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求B1,B2,B3,B4到C1,C2,C3 的最短路徑問題： 表-3 分析得知：如果經(jīng)過B1，則走B1-C2-D2-E；

4、 如果經(jīng)過B2，則走B2-C3-D1-E； 如果經(jīng)過B3，則走B3-C3-D1-E； 如果經(jīng)過B4，則走B4-C3-D1-E,2021/1/29,8,第一階段：只有1個(gè)始點(diǎn)A，終點(diǎn)有B1,B2,B3,B4 。對始點(diǎn)和終 點(diǎn)進(jìn)行分析和討論分別求A到B1,B2,B3,B4的最短路徑問題： 表10-4 最后，可以得到：從A到E的最短路徑為A B4 C3 D1 E,2021/1/29,9,以上計(jì)算過程及結(jié)果，可用圖2表示，可以看到，以上方法不僅 得到了從A到D的最短路徑，同時(shí)，也得到了從圖中任一點(diǎn)到E 的最短路徑。 以上過程，僅用了22次加法，計(jì)算效率遠(yuǎn)高于窮舉法,B,C,B,D,B,C,D,E,C,

5、4,1,2,3,1,2,3,1,2,3,3,2,1,6,4,7,2,4,8,3,8,6,7,5,1,6,10,6,0,10,6,12,11,11,12,13,14,14,12,7,5,1,2,2021/1/29,10,動(dòng)態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種方法。 多階段決策：是動(dòng)態(tài)決策問題的一種特殊形式； 系統(tǒng)的動(dòng)態(tài)過程可以按照時(shí)間等進(jìn)程分為狀態(tài)相互聯(lián)系 而又相互區(qū)別的各個(gè)階段； 每個(gè)階段都要進(jìn)行決策,目的是使整個(gè)過程的決策 達(dá)到最優(yōu)效果,2021/1/29,11,動(dòng)態(tài)規(guī)劃問題具有以下基本特征,1. 問題具有多階段決策的特征。階段可以按時(shí)間劃分，也可以按空間劃分,2. 每一階段都有相應(yīng)的

6、“狀態(tài)”與之對應(yīng),3. 每一階段都面臨一個(gè)決策，選擇不同的決策將會(huì)導(dǎo)致下一階段不同的狀態(tài)，同時(shí)，不同的決策將會(huì)導(dǎo)致這一階段不同的目標(biāo)函數(shù)值,4. 每一階段的最優(yōu)解問題可以遞歸地歸結(jié)為下一階段各個(gè)可能狀態(tài)的最優(yōu)解問題，各子問題與原問題具有完全相同的結(jié)構(gòu)。能否構(gòu)造這樣的遞推歸結(jié)，是解決動(dòng)態(tài)規(guī)劃問題的關(guān)鍵。這種遞推歸結(jié)的過程，稱為“ 不變嵌入,2021/1/29,12,5 . 狀態(tài)具有無后效性 當(dāng)某階段狀態(tài)確定后，此階段以后過程的發(fā)展不受此階段以前各階段狀態(tài)的影響,動(dòng)態(tài)規(guī)劃基本原理是將一個(gè)問題的最優(yōu)解轉(zhuǎn)化為求子問題的最優(yōu)解，研究的對象是決策過程的最優(yōu)化，其變量是流動(dòng)的時(shí)間或變動(dòng)的狀態(tài)，最后到達(dá)整個(gè)系

7、統(tǒng)最優(yōu),基本原理一方面說明原問題的最優(yōu)解中包含了子問題的最優(yōu)解，另一方面給出了一種求解問題的思路，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同子問題，每一個(gè)子問題只解一次，并將結(jié)果保存起來以后直接引用，避免每次碰到時(shí)都要重復(fù)計(jì)算，以便各個(gè)擊破，分而治之，即分治法，是一種解決最優(yōu)化問題的算法策略,動(dòng)態(tài)規(guī)劃求解可分為三個(gè)步驟：分解、求解與合并,2021/1/29,13,例2 資源分配問題 設(shè)有某種機(jī)器數(shù)臺(tái)，用于完成兩類工作A，B。由于機(jī)器使用后有一定的損壞率，所以每年初的機(jī)器數(shù)量是變化的；A、B兩項(xiàng)工作產(chǎn)生的收益也不同。如何合理的分配機(jī)器的使用，可使得三年的總收益最大? 假設(shè)第k年年初完好

8、機(jī)器數(shù)是SK，用于A生產(chǎn)的機(jī)器數(shù)是XK，則用于B生產(chǎn)的機(jī)器數(shù)是（SK- XK）； 用于A工作的設(shè)備的完好率是：a%，用于B工作的設(shè)備的完好率是：b%。則下一年初的完好機(jī)器數(shù)是 SK+1= a% XK+ b% （SK- XK） 第k年的收益： h(XK)+ g(SK- XK,2021/1/29,14,例3 背包問題 設(shè)有n種物品，每一種物品數(shù)量無限。第i種物品每件 重量為wi公斤，每件價(jià)值ci元?，F(xiàn)有一只可裝載重量為W 公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背 包中物品的價(jià)值最高。 這個(gè)問題可以用整數(shù)規(guī)劃模型來描述。設(shè)xi為第i種 物品裝入背包的件數(shù)（i =1, 2, , n），背包中物

9、品的總 價(jià)值為z，則 Max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnW x1, x2, , xn0 且為整數(shù),2021/1/29,15,一、基本概念： 1、階段(stage)k：表示決策順序的離散的量，階段可以按時(shí)間或空間劃分。(順序編號法、逆序編號法） 2、狀態(tài)(state)sk：反應(yīng)前一階段決策的結(jié)果，又是本階段組作決策的依據(jù)和出發(fā)點(diǎn)（能確定地表示決策過程當(dāng)前特征的量）。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。 3、決策(decision)xk：從某一狀態(tài)向下一狀態(tài)過渡時(shí)所做的選擇。決策是所在狀態(tài)的函數(shù)，記為xk(sk)

10、。 決策允許集合Dk(sk)：在狀態(tài)sk下，允許采取決策的全體 xk(sk)Dk(sk,2基本概念、基本方程與最優(yōu)化原理,2021/1/29,16,4、策略Pk,n(sk)：從第k階段開始到最后第n階段的決策序列，稱k子策略。P1,n(s1)即為全過程策略。 5、狀態(tài)轉(zhuǎn)移方程 Sk+1=Tk(Sk, Xk)：某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系,6、指標(biāo)函數(shù)或收益函數(shù)(Return function)：是衡量對決策過程進(jìn)行控制的效果的數(shù)量指標(biāo)，具體可以是收益、成本、距離等指標(biāo)。分為k階段指標(biāo)函數(shù)、k子過程指標(biāo)函數(shù)及最優(yōu)指標(biāo)函數(shù),k階段指標(biāo)函數(shù),從k階段狀態(tài)sk出發(fā)，選擇決策xk

11、所產(chǎn)生的第k階段指標(biāo)，稱為k階段指標(biāo)函數(shù),記為vk(sk,xk,2021/1/29,17,從k階段狀態(tài)sk出發(fā)，選擇決策xk,xk+1,xn所產(chǎn)生的過程指標(biāo)，稱為k子過程指標(biāo)函數(shù)或簡稱過程指標(biāo)函數(shù)，記為 Vk(sk,xk,xk+1,xn)或Vk，n為階段數(shù),過程指標(biāo)函數(shù),最優(yōu)指標(biāo)函數(shù),從k階段狀態(tài)sk出發(fā)，對所有的子策略，最優(yōu)的過程指標(biāo)函數(shù)稱為最優(yōu)指標(biāo)函數(shù)，記為fk(sk)，通常取Vk的最大值或最小值,Optoptimization 表示“max”或“min,2021/1/29,18,動(dòng)態(tài)規(guī)劃要求過程指標(biāo)滿足遞推關(guān)系 ，即,8-2,2021/1/29,19,動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型由式(8-4)或(8

12、-6)、邊界條件及狀態(tài)轉(zhuǎn)移方程構(gòu)成。如連和形式的數(shù)學(xué)模型,2021/1/29,20,對于可加性指標(biāo)函數(shù)，上式可以寫為,上式中“ opt”表示“ max”或“ min”。對于可乘性指標(biāo)函數(shù)，上式可以寫為,上式稱為動(dòng)態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動(dòng)態(tài)規(guī)劃的基本方程,終端條件：為了使以上的遞推方程有遞推的起點(diǎn)，必須要設(shè)定最優(yōu)指標(biāo)的終端條件，即確定最后一個(gè)狀態(tài)n下最優(yōu)指標(biāo)fn(sn)的值,2021/1/29,21,三、最優(yōu)化原理 作為整個(gè)過程的最優(yōu)策略具有如下性質(zhì)： 不管在此最優(yōu)策略上的某個(gè)狀態(tài)以前的狀 態(tài)和決策如何，對該狀態(tài)來說，以后的所有決 策必定構(gòu)成最優(yōu)子策略。就是說，最優(yōu)策略的 任意子策略都是最

13、優(yōu)的,2021/1/29,22,用逆序法列表,k=n=5 時(shí)，f5(v10)0,k=4，遞推方程為,2021/1/29,23,k=3，遞推方程為,表8-2,2021/1/29,24,k=2，遞推方程為,表8-3,2021/1/29,25,k=1，遞推方程為,表8-4,最優(yōu)值是表8-4中f1(s1)的值，從v1到v10的最短路長為19。最短路線從表8-4到表8-1回朔，查看最后一列最優(yōu)決策，得到最短路徑為,v1 v2 v5 v7 v10,2021/1/29,26,例4.有9支巡邏隊(duì)負(fù)責(zé)3個(gè)要害部門A、B、C的巡邏，每部位可派2-4支巡邏隊(duì)，隊(duì)數(shù)不同各部位可能損失有差別，如表，問各部位應(yīng)各派多少隊(duì)

14、，使總預(yù)期損失最小,3離散確定性動(dòng)態(tài)規(guī)劃模型求解,2021/1/29,27,解：設(shè)將向三個(gè)部位A，B，C派巡邏隊(duì)作為三個(gè)階段，K=1，2，3,決策變量 表示向第K個(gè)部位派遣的巡邏隊(duì)數(shù),狀態(tài)變量 表示第K個(gè)階段時(shí)可供派遣的巡邏隊(duì)數(shù)量,狀態(tài)轉(zhuǎn)移方程,階段指標(biāo)函數(shù)： 派遣 支巡邏隊(duì)時(shí)第K階段產(chǎn)生的預(yù)期損失,過程指標(biāo)函數(shù)： 第K階段到第3階段的預(yù)期損失,最優(yōu)指標(biāo)函數(shù),決策允許集合Dk(sk)=xk|2xk4,(k=1,2,3,4,2021/1/29,28,逆序解法： 邊界條件,當(dāng)K=3時(shí)，給C派巡邏隊(duì),2 3 4,3,2,4,5,24,24,2,24 22,22,3,24 22 21,21,4,24

15、22 21,21,4,2021/1/29,29,當(dāng)K=2時(shí)，給B派巡邏隊(duì)，,38+22 35+24,59,3,38+21 35+22 31+24,55,4,38+21 35+21 31+22,53,4,2021/1/29,30,當(dāng)K=1時(shí)，給A派巡邏隊(duì)，,最優(yōu)方案：A派3支巡邏隊(duì)，B派4支巡邏隊(duì)，C派2支巡邏隊(duì)； 或：A派4支巡邏隊(duì)，B派3支巡邏隊(duì)，C派2支巡邏隊(duì),18+53 14+55 10+59,69,3,4,2021/1/29,31,例5 資源分配問題 設(shè)有某種機(jī)器100，用于完成兩類工作A，B。由于機(jī)器使用后有一定的損壞率，所以每年初的機(jī)器數(shù)量是變化的，設(shè)用于A工作的設(shè)備的完好率是：2

16、/3，用于B工作的設(shè)備的完好率是：9/10；A、B兩項(xiàng)工作產(chǎn)生的收益與機(jī)器臺(tái)數(shù)有關(guān)且分別為g(x)=10 x(萬元)，h(x)=7x (萬元) 。如何合理的分配機(jī)器的使用，可使得三年的總收益最大,2021/1/29,32,解：按年份分為三個(gè)階段，K=1，2，3,決策變量xk表示用于生產(chǎn)產(chǎn)品A的機(jī)器數(shù),狀態(tài)變量sk表示第K年初完好機(jī)器數(shù),狀態(tài)轉(zhuǎn)移方程,階段指標(biāo)函數(shù),過程指標(biāo)函數(shù)： 第K階段到第3階段的最大收益為,最優(yōu)指標(biāo)函數(shù),決策允許集合Dk(sk)=xk|0 xksk,(k=1,2,3,sK+1=2/3 xK+0.9（sK- XK,Vk(sk,xk)=10 xk+7(sk-xk)表示第k年的收

17、益,2021/1/29,33,逆序解法： 邊界條件f4 (s4)=0,當(dāng)K=3時(shí),第三年初分配機(jī)器x3臺(tái)生產(chǎn)A,s3-x3臺(tái)生產(chǎn)B,顯然當(dāng)x3=s3時(shí)達(dá)到最大值， 因而此階段的最優(yōu)決策為x3*=s3,2021/1/29,34,當(dāng)K=2時(shí),第二年初分配機(jī)器x2臺(tái)生產(chǎn)A,s2-x2臺(tái)生產(chǎn)B,顯然s3是關(guān)于s2,x2的狀態(tài)轉(zhuǎn)移，因而有,2021/1/29,35,最優(yōu)方案：s1=100, x1*=0,s1x1=100,s2=90,x2*=90, s2x2*=0, s3=60, x3*=60, s3x3*=0。 第一年所有機(jī)器100臺(tái)用于生產(chǎn)B， 第二年初完好機(jī)器90臺(tái)； 第二年所有機(jī)器90臺(tái)用于生產(chǎn)A

18、， 第三年初完好機(jī)器60臺(tái)； 第三年所有機(jī)器60臺(tái)用于生產(chǎn)A， 第四年初完好機(jī)器40臺(tái),當(dāng)K=1時(shí),第二年初分配機(jī)器x1臺(tái)生產(chǎn)A,s1-x1臺(tái)生產(chǎn)B, s1 =100,2021/1/29,36,例】公司有資金6萬元，投資A、B、C三個(gè)項(xiàng)目，一個(gè)單位投資為2萬元。每個(gè)項(xiàng)目的投資效益率與投入該項(xiàng)目的資金有關(guān)。三個(gè)項(xiàng)目A、B、C的投資效益(萬元)和投入資金（萬元）的關(guān)系見表8-5。求對三個(gè)項(xiàng)目的最優(yōu)投資分配，使總投資效益最大,解】設(shè)xk為第k個(gè)項(xiàng)目的投資,2021/1/29,37,階段k：每投資一個(gè)項(xiàng)目作為一個(gè)階段，k=1,2,3,4。k=4為虛設(shè)的階段 狀態(tài)變量sk：投資第k個(gè)項(xiàng)目前的資金數(shù) 決策

19、變量xk：第k個(gè)項(xiàng)目的投資額 決策允許集合：0 xksk 狀態(tài)轉(zhuǎn)移方程：sk+1=skxk 階段指標(biāo)：vk(sk，xk)見表8-5中的數(shù)據(jù),遞推方程,終端條件：f4(s4)=0 數(shù)學(xué)模型為,2021/1/29,38,k=4，終端條件f4(s4)=0。 k=3，0 x3s3，s4=s3x3 ，s3=0，2，4，6,0 2 4 6,0 0 0 0+0=0* 0 0,2 0 10 10+0=10* 10 2,4 0 28 28+0=28* 28 4,6 0 35 35+0=35* 35 6,2021/1/29,39,k=2，0 x2s2，s3=s2x2 ，s2=0，2，4，6,0 2 4 6,0 0

20、 0 0 0+0=0* 0 0,0 2 0 10 0+10=10,2 0 9 0 9+0=9,10 0,0 4 0 28 0+28=28,2 2 9 10 9+10=19,4 0 20 0 20+0=20,28 0,0 6 0 35 0+35=35,2 4 9 28 9+28=37,4 2 20 10 20+10=30,6 0 35 0 35+0=35,37 2,2021/1/29,40,k=1，0 x1s1，s2=s1x1，s1=6,最優(yōu)解為: s1=6, x1*=0, s2=s1x1=6, x2*=2, s3=s2x2*=4, x3*=4, s4=s3x3=0。投資的最優(yōu)策略是，項(xiàng)目A不投

21、資，項(xiàng)目B投資2萬元，項(xiàng)目C投資4萬元，最大效益為37萬元,0 6 0 37 0+37=37,2 4 8 28 8+28=36,4 2 15 10 15+10=25,6 0 30 0 30+0=30,37 0,2021/1/29,41,4離散隨機(jī)動(dòng)態(tài)規(guī)劃模型求解,隨機(jī)動(dòng)態(tài)規(guī)劃：狀態(tài)轉(zhuǎn)移規(guī)律不定，在給定的狀態(tài)和決策 下，下一階段到達(dá)的狀態(tài)是具有確定概率分布的隨機(jī)變量,第k+1階段 可能狀態(tài),Pi：在決策Xk下出現(xiàn)狀態(tài)i的概率,Ci：在決策Xk下出現(xiàn)狀態(tài)i時(shí)的指標(biāo)函數(shù),2021/1/29,42,由于下一階段的狀態(tài)和階段的效益值不確定，因而隨機(jī)動(dòng)態(tài)規(guī)劃中，對指標(biāo)函數(shù)進(jìn)行優(yōu)化時(shí)，要根據(jù)各階段的期望效益

22、進(jìn)行優(yōu)化。 基本方程改寫為,其中E（）表示期望值，邊界條件fn+1(sn+1)的應(yīng)根據(jù)問題的具體情況確定,2021/1/29,43,2021/1/29,44,決策變量xk：表示第K個(gè)階段決定投產(chǎn)的數(shù)量,狀態(tài)轉(zhuǎn)移律,階段指標(biāo)函數(shù)：第k階段的費(fèi)用支出,最優(yōu)指標(biāo)函數(shù) fk(sk) ：表示第K階段在 Sk 狀態(tài)下，做決策 xk時(shí)，到最后一個(gè)階段的最小期望費(fèi)用,允許決策集合Dk (sk)： Dk (sk)=1,2,N(當(dāng)sk=1,Dk (sk)=0(當(dāng)sk=0,2021/1/29,45,易知,2021/1/29,46,逆序解法： 邊界條件 當(dāng)K=3時(shí)，第三階段之后的最小期望費(fèi)用,0 1,0 0 1500,1 1350,2 1117,3 994,4 946,5 948,0 946,0 4,2021/1/29,47,當(dāng)K=2時(shí)，第二階段之后的最小期望費(fèi)用,0 1,0 0 946,1 981,2 870,3 830,4 837,0 830,0 3,2021/1/29,48,當(dāng)K=1時(shí)，第一階段之后的最小期望費(fèi)用，s1=1,最優(yōu)方案：第一期投產(chǎn)3臺(tái)；第二期投產(chǎn)3臺(tái)；第三期投產(chǎn)4臺(tái)。最小期望費(fèi)用796,1,0 830,1 903,2 819,3 796,4 814,796,3,2021/1