1、第八章 動態(tài)規(guī)劃 Dynamic Programming,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型Mathematical Model of DP 8.2 資源分配問題 Resource Assignment Problem 8.3 生產(chǎn)與存儲問題Production and inventory problem 8.4 背包問題 Knapsack Problem 8.5 其它動態(tài)規(guī)劃模型 Other Model of DP,運籌學(xué) Operations Research,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,v2,v3,v4,v7,v5,v9,v6,v8,v10,2,8,

2、5,12,13,10,7,10,13,11,2,8,6,5,8,8,5,4,0,5,8,4,7,【例8.1】最短路徑問題 圖81表示從起點A到終點E之間各點的距離。求A到E的最短路徑。,圖81,v1,第1階段,第2階段,第3階段,第4階段,階段：,第5階段,12,17,14,20,19,2020年8月15日星期六,2,3,4,7,5,9,6,8,10,2,8,5,12,13,10,7,10,13,11,2,8,6,5,8,8,5,4,圖82,1,第1階段,第2階段,第3階段,第4階段,階段：,第5階段,用WinQSB軟件計算時,需要對狀態(tài)重新編號,如下圖所示.,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mat

3、hematical Model of DP,2020年8月15日星期六,1,2,3,4,8,5,7,6,9,10,2,8,5,12,13,10,M,10,4,13,11,11,2,8,6,5,8,8,6,4,用WinQSB軟件計算時,當(dāng)某狀態(tài)沒有路到下階段某狀態(tài)時，添加一條虛擬決策（線條），距離很大，如下圖點3到點5.,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,2020年8月15日星期六,動態(tài)規(guī)劃問題具有以下基本特征,1. 問題具有多階段決策的特征。階段可以按時間劃分，也可以按空間劃分。,2. 每一階段都有相應(yīng)的“ 狀態(tài)”與之對應(yīng)。,3. 每一階段都面臨一個決

4、策，選擇不同的決策將會導(dǎo)致下一階段不同的狀態(tài)，同時，不同的決策將會導(dǎo)致這一階段不同的目標(biāo)函數(shù)值。,4. 每一階段的最優(yōu)解問題可以遞歸地歸結(jié)為下一階段各個可能狀態(tài)的最優(yōu)解問題，各子問題與原問題具有完全相同的結(jié)構(gòu)。能否構(gòu)造這樣的遞推歸結(jié)，是解決動態(tài)規(guī)劃問題的關(guān)鍵。這種遞推歸結(jié)的過程，稱為“ 不變嵌入”。,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,2020年8月15日星期六,5 . 狀態(tài)具有無后效性 當(dāng)某階段狀態(tài)確定后，此階段以后過程的發(fā)展不受此階段以前各階段狀態(tài)的影響。如下圖所示：,C2,9,0,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of

5、 DP,2020年8月15日星期六,動態(tài)規(guī)劃基本原理是將一個問題的最優(yōu)解轉(zhuǎn)化為求子問題的最優(yōu)解，研究的對象是決策過程的最優(yōu)化，其變量是流動的時間或變動的狀態(tài)，最后到達整個系統(tǒng)最優(yōu)。,基本原理一方面說明原問題的最優(yōu)解中包含了子問題的最優(yōu)解，另一方面給出了一種求解問題的思路，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同子問題，每一個子問題只解一次，并將結(jié)果保存起來以后直接引用，避免每次碰到時都要重復(fù)計算，以便各個擊破，分而治之，即分治法，是一種解決最優(yōu)化問題的算法策略。,動態(tài)規(guī)劃求解可分為三個步驟：分解、求解與合并。,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of D

6、P,2020年8月15日星期六,（1）階段(Stage)：表示決策順序的時段序列，階段可以按時間或空間劃分，階段數(shù)k可以是確定數(shù)、不定數(shù)或無限數(shù),8.1.2基本概念,（3）決策（Decision）xk：從某一狀態(tài)向下一狀態(tài)過度時所做的選擇。決策變量記為xk，xk是所在狀態(tài)sk的函數(shù)。 在狀態(tài)sk下，允許采取決策的全體稱為決策允許集合，記為Dk(sk)。各階段所有決策組成的集合稱為決策集。,（2）狀態(tài)（State）：描述決策過程當(dāng)前特征并且具有無后效性的量。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。每一狀態(tài)可以取不同值，狀態(tài)變量記為sk。各階段所有狀態(tài)組成的集合稱為狀態(tài)

7、集。,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,2020年8月15日星期六,(4) 策略(Strategy)：從第1階段開始到最后階段全過程的決策構(gòu)成的序列稱為策略，第k階段到最后階段的決策序列稱為子策略。,（5）狀態(tài)轉(zhuǎn)移方程(State transformation function)：某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系，記為 sk+1=T(sk,xk),（6）指標(biāo)函數(shù)或收益函數(shù)(Return function)：是衡量對決策過程進行控制的效果的數(shù)量指標(biāo)，具體可以是收益、成本、距離等指標(biāo)。分為k階段指標(biāo)函數(shù)、k子過程指標(biāo)函數(shù)及最優(yōu)指標(biāo)函數(shù)。

8、,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,2020年8月15日星期六,k階段指標(biāo)函數(shù),從k階段狀態(tài)sk出發(fā)，選擇決策xk所產(chǎn)生的第k階段指標(biāo)，稱為k階段指標(biāo)函數(shù),記為vk(sk,xk)。,從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”或“mi

9、n”,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,2020年8月15日星期六,動態(tài)規(guī)劃要求過程指標(biāo)滿足遞推關(guān)系 ，即,(8.2),8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,2020年8月15日星期六,動態(tài)規(guī)劃數(shù)學(xué)模型由式(8.4)或(8.6)、邊界條件及狀態(tài)轉(zhuǎn)移方程構(gòu)成。如連和形式的數(shù)學(xué)模型,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,2020年8月15日星期六,對于可加性指標(biāo)函數(shù)，上式可以寫為,上式中“ opt”表示“ max”或“ min”。對于可乘性指標(biāo)函數(shù)，上式可以寫為,上式稱為動態(tài)規(guī)劃最

10、優(yōu)指標(biāo)的遞推方程，是動態(tài)規(guī)劃的基本方程。,終端條件：為了使以上的遞推方程有遞推的起點，必須要設(shè)定最優(yōu)指標(biāo)的終端條件，即確定最后一個狀態(tài)n下最優(yōu)指標(biāo)fn(sn)的值。,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,2020年8月15日星期六,用逆序法列表求解例8.1,k=n=5 時，f5(v10)0,k=4，遞推方程為,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,2020年8月15日星期六,k=3，遞推方程為,表8-2,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,2020年8月15日星期六,k=2，遞推

11、方程為,表8-3,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,2020年8月15日星期六,k=1，遞推方程為,表8-4,最優(yōu)值是表8-4中f1(s1)的值，從v1到v10的最短路長為19。最短路線從表8-4到表8-1回朔，查看最后一列最優(yōu)決策，得到最短路徑為：,v1 v2 v5 v7 v10,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,2020年8月15日星期六,作業(yè)：教材P188 T2,下一節(jié)：資源分配問題,8.1 動態(tài)規(guī)劃數(shù)學(xué)模型 Mathematical Model of DP,8.2 資源分配問題 Resource Ass

12、ignment Problem,2020年8月15日星期六,【例8.2】公司有資金8萬元，投資A、B、C三個項目，一個單位投資為2萬元。每個項目的投資效益率與投入該項目的資金有關(guān)。三個項目A、B、C的投資效益(萬元)和投入資金（萬元）的關(guān)系見表8-5。求對三個項目的最優(yōu)投資分配，使總投資效益最大。,8.2 資源分配問題 Resource Assignment Problem,表8-5,【解】設(shè)xk為第k個項目的投資，該問題的靜態(tài)規(guī)劃模型為,2020年8月15日星期六,階段k：每投資一個項目作為一個階段，k=1,2,3,4。k=4為虛設(shè)的階段 狀態(tài)變量sk：投資第k個項目前的資金數(shù) 決策變量xk

13、：第k個項目的投資額 決策允許集合：0 xksk 狀態(tài)轉(zhuǎn)移方程：sk+1=skxk 階段指標(biāo)：vk(sk，xk)見表8-5中的數(shù)據(jù),遞推方程：,終端條件：f4(s4)=0 數(shù)學(xué)模型為,8.2 資源分配問題 Resource Assignment Problem,2020年8月15日星期六,k=4，終端條件f4(s4)=0。 k=3，0 x3s3，s4=s3x3,8.2 資源分配問題 Resource Assignment Problem,2020年8月15日星期六,k=2，0 x2s2，s3=s2x2,8.2 資源分配問題 Resource Assignment Problem,2020年8月

14、15日星期六,k=1，0 x1s1，s2=s1x1,最優(yōu)解為: s1=8, x1*=0, s2=s1x1=8, x2*=4, s3=s2x2*=4, x3=4, s4=s3x3=0。投資的最優(yōu)策略是，項目A不投資，項目B投資4萬元，項目C投資4萬元，最大效益為48萬元,8.2 資源分配問題 Resource Assignment Problem,2020年8月15日星期六,【例8.3】某種設(shè)備可在高低兩種不同的負荷下進行生產(chǎn)，設(shè)在高負荷下投入生產(chǎn)的設(shè)備數(shù)量為x,產(chǎn)量為g=10 x，設(shè)備年完好率為a=0.75；在低負荷下投入生產(chǎn)的設(shè)備數(shù)量為y，產(chǎn)量為h=8y，年完好率為b=0.9。假定開始生產(chǎn)時

15、完好的設(shè)備數(shù)量s1=100。 制定一個五年計劃，確定每年投入高、低兩種負荷下生產(chǎn)的設(shè)備數(shù)量，使五年內(nèi)產(chǎn)品的總產(chǎn)量達到最大。,階段k：運行年份（k=1,2,3,4,5,6），k=1表示第一年初，k=6表示第五年末（即第六年初）； 狀態(tài)變量sk：第k年初完好的機器數(shù)（k=1,2,3,4,5,6），也是第k1年末完好的機器數(shù)，其中s6表示第五年末（即第六年初）的完好機器數(shù)，s1100。 決策變量xk：第k年初投入高負荷運行的機器數(shù)； 狀態(tài)轉(zhuǎn)移方程：sk+1=0.75xk+0.9(skxk),8.2 資源分配問題 Resource Assignment Problem,2020年8月15日星期六,決策

16、允許集合：Dk(sk)=xk|0 xksk 階段指標(biāo)：vk(sk，xk)=10 xk+8(skxk) 終端條件：f6(s6)=0 遞推方程：,8.2 資源分配問題 Resource Assignment Problem,2020年8月15日星期六,8.2 資源分配問題 Resource Assignment Problem,2020年8月15日星期六,8.2 資源分配問題 Resource Assignment Problem,2020年8月15日星期六,因為s1=100，五年的最大總產(chǎn)量為f1(s1)=25.75251003443.75。 由x1*= x2*= x3*=0，x4*s4，x5*

17、s5，設(shè)備的最優(yōu)分配策略是，第一年至第三年將設(shè)備全部用于低負荷運行，第四年和第五年將設(shè)備全部用于高負荷運行。每年投入高負荷運行的機器數(shù)以及每年初完好的機器數(shù)為：,s1=100 x1*=0,s2=0.75x1+0.9(s1x1)=90 x2*=0,s3=0.75x2+0.9(s2x2)=81 x3*= 0， s4=0.75x3+0.9(s3x3)=73 x4*= s4=73， s5=0.75x4+0.9(s4x4)=55 x5*= s5=55， s6=0.75x5+0.9(s5x5)=41 第五年末還有41臺完好設(shè)備。,8.2 資源分配問題 Resource Assignment Problem

18、,2020年8月15日星期六,一般地，設(shè)一個周期為n年，高負荷生產(chǎn)時設(shè)備的完好率為a，單臺產(chǎn)量為g；低負荷完好率為b，單臺產(chǎn)量為h。若有t滿足,則最優(yōu)設(shè)備分配策略是：從1t1年，年初將全部完好設(shè)備投入低負荷運行，從tn年，年初將全部完好設(shè)備投入高負荷運行，總產(chǎn)量達到最大 .,在例8.3中， n=5，a=0.75，b=0.9，g=10，h=8，(g-h)/g(b-a)=1.3333 式(8.7)的求和式是完好率a的i次方累加. 由a0=11.3333a0+a11.75知，nt10，t=4，則13年低負荷運行，45年為高負荷運行,8.2 資源分配問題 Resource Assignment Problem,(8.7),2020年8月15日星期六,作業(yè)：教材P188 T1，6，8，9,8.2 資源分配問題 Resource Assignment Problem,下一節(jié)：生產(chǎn)與存儲問題,8.3 生產(chǎn)與存儲問題 Production and inventory problem,2020年8月15日星期六,8.3 生產(chǎn)與存儲問題 Production and inventory problem,【8.4】一個工廠生產(chǎn)某種產(chǎn)品，16