動(dòng)態(tài)規(guī)劃講座

1、 4 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 4.1 多階段決策問題與動(dòng)態(tài)規(guī)劃 4.2 動(dòng)態(tài)規(guī)劃的基本概念 4.3 動(dòng)態(tài)規(guī)劃的步驟 4.4 動(dòng)態(tài)規(guī)劃的應(yīng)用 1 求解靜態(tài)規(guī)劃問題 2 資源分配問題 3 不確定性采購(gòu)問題 4 排序問題 例2 機(jī)器負(fù)荷分配問題 某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u的關(guān)系為 gg(u), 這時(shí)機(jī)器的年完好率為a（0a1)在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量v的關(guān)系為hh(v), 這時(shí)機(jī)器的年完好率為b（ab1）假定開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為s1，要求制定一個(gè)五年計(jì)劃,在每年開始時(shí)決定機(jī)器在兩種不同負(fù)荷下生產(chǎn)的數(shù)

2、量,使五年內(nèi)產(chǎn)品的總產(chǎn)量最高。4.1 多階段決策問題與動(dòng)態(tài)規(guī)劃例1最短路問題以上兩個(gè)問題都可以劃分為先后多個(gè)決策階段。這類問題就稱為多階段決策問題。多階段決策問題的過程如下圖所示： 狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策決策決策狀態(tài) 多階段決策問題和我們前面遇到的決策問題不同，它是和時(shí)間有關(guān)的。與時(shí)間有關(guān)的活動(dòng)過程稱為動(dòng)態(tài)過程，其優(yōu)化方法稱為動(dòng)態(tài)規(guī)劃。而與時(shí)間無關(guān)的活動(dòng)過程稱為靜態(tài)過程，相應(yīng)的的優(yōu)化方法稱為靜態(tài)規(guī)劃。 (1)階段（stage）把所研究的決策問題，按先后順序劃分為若干相互聯(lián)系的決策步驟，以便按一定的次序進(jìn)行求解。描述階段的變量稱階段變量，常用k表示。 (2)狀態(tài)（state）狀態(tài)表示每個(gè)階段開始時(shí)

3、所處的自然狀況或客觀條件，它描述了影響決策的因素隨決策進(jìn)程的變化情況，它既是前面階段所作決策的結(jié)果，又是本階段作出決策的出發(fā)點(diǎn)和依據(jù)。描述狀態(tài)的變量稱為狀態(tài)變量，第k階段的狀態(tài)變量常用sk表示。通常，在第一階段狀態(tài)變量s1是確定的，稱初始狀態(tài)。 (3)決策（decision）決策表示在某一階段處于某種狀態(tài)時(shí)，決策者在若干種方案中作出的選擇決定。描述決策的變量稱決策變量，第k階段的決策變量常用uk表示。決策變量的取值會(huì)受到狀態(tài)變量的制約，被限制在某一范圍之內(nèi)。4.2 動(dòng)態(tài)規(guī)劃的基本概念（一） (4)策略（policy）把從第一階段開始到最后階段終止的整個(gè)決策過程，稱為問題的全過程；而把從第k階段

4、開始到最后階段終止的決策過程，或稱為k子過程。在全過程上，各階段的決策按順序排列組成的決策序列p1,n u1,u2,un 稱為全過程策略，簡(jiǎn)稱 策 略 ； 而 在 k 子 過 程 上 的 決 策 序 列 pk , n uk,uk+1,un 稱為k子過程策略，也簡(jiǎn)稱子策略。 (5)狀態(tài)轉(zhuǎn)移方程 若第k階段的狀態(tài)變量值為sk，當(dāng)決策變量uk的取值決定后，下一階段狀態(tài)變量sk+1的值也就完全確定。即sk+1的值對(duì)應(yīng)于sk和uk的值。這種對(duì)應(yīng)關(guān)系記為sk+1Tk(sk,uk)，稱為狀態(tài)轉(zhuǎn)移方程。狀態(tài)轉(zhuǎn)移方程描述了由一個(gè)階段的狀態(tài)到下一階段的狀態(tài)的演變規(guī)律。4.2 動(dòng)態(tài)規(guī)劃的基本概念（二） (6)指標(biāo)函

5、數(shù)和最優(yōu)值函數(shù) 指標(biāo)函數(shù)分為階段指標(biāo)函數(shù)和過程指標(biāo)函數(shù)。階段指標(biāo)函數(shù)是對(duì)某一階段的狀態(tài)和決策產(chǎn)生的效益值的度量，用vk(sk,uk)表示。過程指標(biāo)函數(shù)是指過程所包含的各階段的狀態(tài)和決策所產(chǎn)生的總的效益值，記為 Vk,nVk,n(sk,uk,sk+1,uk+1,sn,un) 動(dòng)態(tài)規(guī)劃所要求的過程指標(biāo)函數(shù)應(yīng)具有可分離性，即可表達(dá)為它所包含的各階段指標(biāo)函數(shù)的函數(shù)形式。常見的兩種過程指標(biāo)函數(shù)形式是： 各階段指標(biāo)函數(shù)的和 Vk,nvj(sj,uj)； 各階段指標(biāo)函數(shù)的積 Vk,nvj(sj,uj)。 把過程指標(biāo)函數(shù)Vk,n對(duì)k子過程策略pk,n求最優(yōu)，得到一個(gè)關(guān)于狀態(tài)sk的函數(shù)，稱為最優(yōu)值函數(shù)，記為fk

6、(sk)。即 fk(sk) opt Vk,n(sk,uk,sn,un) uk,un式中的“opt”（optimization）可根據(jù)具體問題而取min或max。 (7)基本方程 通常動(dòng)態(tài)規(guī)劃問題的最優(yōu)值函數(shù)滿足遞推關(guān)系式。設(shè)過程指標(biāo)函數(shù)為各階段指標(biāo)函數(shù)的和的形式，即Vk,nvj(sj,uj)，則有 fk(sk) opt vk(sk,uk)+fk+1(sk+1) ukDk(sk) (kn,n-1,1) 遞推方程 fn+1(sn+1)0 邊界條件遞推方程和邊界條件一起稱為動(dòng)態(tài)規(guī)劃的基本方程。 可根據(jù)邊界條件，從k=n開始，由后向前逆推，逐步求得各階段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求出f1(s1)時(shí)

7、，就得到整個(gè)問題的最優(yōu)解。 例 最 短 路 問 題此問題的基本方程為此問題的基本方程為f fk k(s(sk k) )MindMindk k(u(uk k)+f)+fk+1k+1(s(sk+1k+1) ) u uk kDDk k(s(sk k) ) k k6,5,4,3,2,16,5,4,3,2,1f f7 7(s(s7 7) )0 04.3 動(dòng)態(tài)規(guī)劃的步驟（一）動(dòng)態(tài)規(guī)劃的步驟（一）當(dāng)k=6時(shí)s s6 6 u u6 6 D D( (u u6 6) )+ +f f7 7( (s s7 7) ) F F6 6( (s s6 6) ) F F1 1 F F1 1G G 4 4+ +0 0= =4 4

8、* * 4 4 F F2 2 F F2 2G G 3 3+ +0 0= =3 3* * 3 3 按基本方程由后向前按基本方程由后向前繼續(xù)繼續(xù)遞推有遞推有:當(dāng)k=5時(shí)當(dāng)k=4時(shí)s s4 4 u u4 4 d d( (u u4 4) )+ +f f5 5( (s s5 5) ) f f4 4( (s s4 4) ) D D1 1 D D1 1E E1 1 D D1 1E E2 2 2 2+ +7 7= =9 9 2 2+ +5 5= =7 7* * 7 7 D D2 2 D D2 2E E2 2 D D2 2E E3 3 1 1+ +5 5= =6 6* * 2 2+ +9 9= =1 11 1

9、6 6 D D3 3 D D3 3E E2 2 D D3 3E E3 3 3 3+ +5 5= =8 8* * 3 3+ +9 9= =1 12 2 8 8 s s5 5 u u5 5 d d( (u u5 5) )+ +f f6 6( (s s6 6) ) f f5 5( (s s5 5) ) E E1 1 E E1 1F F1 1 E E1 1F F2 2 3 3+ +4 4= =7 7* * 5 5+ +3 3= =8 8 7 7 E E2 2 E E2 2F F1 1 E E2 2F F2 2 5 5+ +4 4= =9 9 2 2+ +3 3= =5 5* * 5 5 E E3 3

10、E E3 3F F1 1 E E3 3F F2 2 6 6+ +4 4= =1 10 0 6 6+ +3 3= =9 9* * 9 9 當(dāng)當(dāng)k=3時(shí)時(shí)s s3 3 u u3 3 d d( (u u3 3) )+ +f f4 4( (s s4 4) ) f f3 3( (s s3 3) ) C C1 1 C C1 1D D1 1 C C1 1D D2 2 6 6+ +7 7= =1 13 3* * 8 8+ +6 6= =1 14 4 1 13 3 C C2 2 C C2 2D D1 1 C C2 2D D2 2 3 3+ +7 7= =1 10 0* * 5 5+ +6 6= =1 11 1

11、1 10 0 C C3 3 C C3 3D D2 2 C C3 3D D3 3 3 3+ +6 6= =9 9* * 3 3+ +8 8= =1 11 1 9 9 C C4 4 C C4 4D D2 2 C C4 4D D3 3 8 8+ +6 6= =1 14 4 4 4+ +8 8= =1 12 2* * 1 12 2 當(dāng)當(dāng)k=2時(shí)時(shí)當(dāng)當(dāng)k=1時(shí)時(shí)s s2 2 u u2 2 d d( (u u2 2) )+ +f f3 3( (s s3 3) ) f f2 2( (s s2 2) ) B B1 1 B B1 1C C1 1 B B1 1C C2 2 B B1 1C C3 3 1 1+ +1

12、 13 3= =1 14 4 3 3+ +1 10 0= =1 13 3* * 6 6+ +9 9= =1 15 5 1 13 3 B B2 2 B B2 2C C2 2 B B2 2C C3 3 B B2 2C C4 4 8 8+ +9 9= =1 17 7 7 7+ +9 9= =1 16 6* * 6 6+ +1 12 2= =1 18 8 1 16 6 s s1 1 u u1 1 d d( (u u1 1) )+ +f f2 2( (s s2 2) ) f f1 1( (s s1 1) ) A A A AB B1 1 A AB B2 2 5 5+ +1 13 3= =1 18 8* *

13、 3 3+ +1 16 6= =1 19 9 1 18 8 由此可以看出，由此可以看出，A到到G的最短路長(zhǎng)為的最短路長(zhǎng)為18，路徑為：，路徑為： AB1C2D1E2F2G現(xiàn)在把動(dòng)態(tài)規(guī)劃法的步驟歸納如下：現(xiàn)在把動(dòng)態(tài)規(guī)劃法的步驟歸納如下：(1) (1) 將所研究問題的過程劃分為將所研究問題的過程劃分為n n個(gè)恰當(dāng)?shù)碾A段，個(gè)恰當(dāng)?shù)碾A段， k k 1,2,n 1,2,n；(2) (2) 正確地選擇狀態(tài)變量正確地選擇狀態(tài)變量S Sk k，并確定初始狀態(tài)并確定初始狀態(tài)S S1 1的值；的值；(3) (3) 確定決策變量確定決策變量u uk k以及各階段的允許決策集以及各階段的允許決策集D Dk k(S(S

14、k k) )；(4) (4) 給出狀態(tài)轉(zhuǎn)移方程；給出狀態(tài)轉(zhuǎn)移方程；(5) (5) 給出滿足要求的過程指標(biāo)函數(shù)給出滿足要求的過程指標(biāo)函數(shù)V Vk,nk,n及相應(yīng)的最優(yōu)及相應(yīng)的最優(yōu) 值函數(shù)；值函數(shù)；(6) (6) 寫出遞推方程和邊界條件，建立基本方程；寫出遞推方程和邊界條件，建立基本方程；(7) (7) 按照基本方程遞推求解。按照基本方程遞推求解。 以上步驟是動(dòng)態(tài)規(guī)劃法處理問題的基本步驟，其以上步驟是動(dòng)態(tài)規(guī)劃法處理問題的基本步驟，其中的前六步是建立動(dòng)態(tài)規(guī)劃模型的步驟。中的前六步是建立動(dòng)態(tài)規(guī)劃模型的步驟。4.3 動(dòng)態(tài)規(guī)劃的步驟（二）動(dòng)態(tài)規(guī)劃的步驟（二）例：機(jī)器負(fù)荷問題例：機(jī)器負(fù)荷問題 某種機(jī)器可以在

15、高低兩種某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)在高負(fù)荷下進(jìn)行生產(chǎn)不同的負(fù)荷下進(jìn)行生產(chǎn)在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量時(shí)，產(chǎn)品的年產(chǎn)量g g和投入生產(chǎn)的機(jī)器數(shù)量和投入生產(chǎn)的機(jī)器數(shù)量u u的的關(guān)系為關(guān)系為 g g8u, 8u, 這時(shí)機(jī)器的年完好率為這時(shí)機(jī)器的年完好率為a=0.7a=0.7在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量h h和和投入生產(chǎn)的機(jī)器數(shù)量投入生產(chǎn)的機(jī)器數(shù)量v v的關(guān)系為的關(guān)系為h h5v, 5v, 這時(shí)機(jī)這時(shí)機(jī)器的年完好率為器的年完好率為b=0.9b=0.9假定開始生產(chǎn)時(shí)完好假定開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為的機(jī)器數(shù)量為s s1 1，要求制定一個(gè)五年計(jì)劃要求制

16、定一個(gè)五年計(jì)劃, ,在在每年開始時(shí)決定機(jī)器在兩種不同負(fù)荷下生產(chǎn)的每年開始時(shí)決定機(jī)器在兩種不同負(fù)荷下生產(chǎn)的數(shù)量數(shù)量, ,使五年內(nèi)產(chǎn)品的總產(chǎn)量最高。使五年內(nèi)產(chǎn)品的總產(chǎn)量最高。(1)按年數(shù)劃分為5個(gè)階段，k=1,2,3,4,5(2)取第k年初完好的機(jī)器數(shù)sk為狀態(tài)變量, s1=1000(3)取第k年投入高負(fù)荷的機(jī)器數(shù)xk為決策變量, 0 xksk(4)狀態(tài)轉(zhuǎn)移方程為 sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk(5)指標(biāo)函數(shù)為Vk,5=8xj+5(sj-xj)=(5sj+3xj)(6)基本方程為 fk(sk) max 5sj+3xj +fk+1(sk+1) k=5,4,3,2,

17、1 0 xksk f6(s6)0解:當(dāng)k=5時(shí)f5(s5) max5s5+3x5+f6(s6)= max5s5+3x5=8s5 (x5*=s5) 0 x5s5 0 x5s5當(dāng)k=4時(shí)f4(s4)max5s4+3x4+8s5=max5s4+3x4+8(0.9s4-0.2x4) 0 x4s4 0 x4s4 = max12.2s4+1.4x4=13.6s4 (x4*=s4) 0 x4s4當(dāng)k=3時(shí)f3(s3)max5s3+3x3+13.6s4=max5s3+3x3+13.6(0.9s3-0.2x3) 0 x3s3 0 x3s3 = max17.24s3+0.28x3=17.5s3 (x3*=s3)

18、0 x3s3當(dāng)k=2時(shí)f2(s2)=max5s2+3x2+17.52s3=max5s2+3x2+17.52(0.9s2-0.2x2) 0 x2s2 0 x2s2 = max20.77s2-0.504x2=20.7s4 (x2*=0) 0 x2s2當(dāng)k=1時(shí)f1(s1)=23.7s1 (x1*=0)f1(1000)=23700s1=1000, x1*=0s2=900, x2*=0s3=810, x3*=810s4=576, x4*=576s5=397, x5*=397 某些靜態(tài)規(guī)劃問題可用動(dòng)態(tài)規(guī)劃法來求解。某些靜態(tài)規(guī)劃問題可用動(dòng)態(tài)規(guī)劃法來求解。 例例 用動(dòng)態(tài)規(guī)劃法求解用動(dòng)態(tài)規(guī)劃法求解 max z

19、=x12.x22.x3 x1+x2+x3=c xi0 i=1,2,34.4 動(dòng)態(tài)規(guī)劃的應(yīng)用動(dòng)態(tài)規(guī)劃的應(yīng)用(一一) 1 求解靜態(tài)規(guī)劃問題求解靜態(tài)規(guī)劃問題 資源分配問題可描述如下：設(shè)有某種原料，資源分配問題可描述如下：設(shè)有某種原料，總數(shù)量為總數(shù)量為a，分配給分配給n個(gè)使用者。已知第個(gè)使用者。已知第i個(gè)使用個(gè)使用者得到數(shù)量者得到數(shù)量xi的資源，可創(chuàng)造的收益為的資源，可創(chuàng)造的收益為gi（xi）。）。問應(yīng)如何分配該資源，才能使總收益最大。問應(yīng)如何分配該資源，才能使總收益最大。4.4 動(dòng)態(tài)規(guī)劃的應(yīng)用動(dòng)態(tài)規(guī)劃的應(yīng)用(二二) 用動(dòng)態(tài)規(guī)劃法處理這種問題時(shí)，通常把給一用動(dòng)態(tài)規(guī)劃法處理這種問題時(shí)，通常把給一個(gè)使用者

20、分配資源的過程看成一個(gè)階段，按個(gè)使用者分配資源的過程看成一個(gè)階段，按n n個(gè)使用者分成先后個(gè)使用者分成先后n n個(gè)決策階段。即先給第個(gè)決策階段。即先給第1 1個(gè)個(gè)使用者分配資源，為第一階段；再給第使用者分配資源，為第一階段；再給第2 2個(gè)使個(gè)使用者分配，為第用者分配，為第2 2階段；依此類推，最后給第階段；依此類推，最后給第n n個(gè)使用者分配，為第個(gè)使用者分配，為第n n階段。階段。 2 資源分配問題資源分配問題 例例 某工業(yè)部門根據(jù)國(guó)家計(jì)劃安排，擬將某工業(yè)部門根據(jù)國(guó)家計(jì)劃安排，擬將五臺(tái)某種高效率的機(jī)器分配給所屬的甲、五臺(tái)某種高效率的機(jī)器分配給所屬的甲、乙、丙三個(gè)工廠，各工廠得到不同數(shù)量的乙、

21、丙三個(gè)工廠，各工廠得到不同數(shù)量的機(jī)器可獲得的收益如下表。問應(yīng)如何分配機(jī)器可獲得的收益如下表。問應(yīng)如何分配機(jī)器，才能使各廠的總效益最大。機(jī)器，才能使各廠的總效益最大。 工工廠廠機(jī)機(jī)器器數(shù)數(shù) 甲甲 乙乙 丙丙0 01 12 23 34 45 50 0 0 0 0 03 3 5 5 4 4 7 7 1 10 0 6 6 9 9 1 11 1 1 11 1 1 12 2 1 11 1 1 12 2 1 13 3 1 11 1 1 12 2 某單位準(zhǔn)備在以后的某單位準(zhǔn)備在以后的n n個(gè)時(shí)期內(nèi)采購(gòu)一批物資。各個(gè)時(shí)期內(nèi)采購(gòu)一批物資。各時(shí)期的價(jià)格不是確定的，而是按照某種已知的概率分時(shí)期的價(jià)格不是確定的，而是按

22、照某種已知的概率分布取值。試制定采購(gòu)策略，確定在哪一時(shí)期以什么價(jià)布取值。試制定采購(gòu)策略，確定在哪一時(shí)期以什么價(jià)格采購(gòu)，能使采購(gòu)價(jià)的數(shù)學(xué)期望值最低。這類問題也格采購(gòu)，能使采購(gòu)價(jià)的數(shù)學(xué)期望值最低。這類問題也適合用動(dòng)態(tài)規(guī)劃法進(jìn)行處理。下面通過實(shí)例加以說明。適合用動(dòng)態(tài)規(guī)劃法進(jìn)行處理。下面通過實(shí)例加以說明。例例7 7 某廠生產(chǎn)上需要在近五周某廠生產(chǎn)上需要在近五周內(nèi)采購(gòu)一批原料，而估計(jì)在未內(nèi)采購(gòu)一批原料，而估計(jì)在未來五周的價(jià)格有波動(dòng)，其浮動(dòng)來五周的價(jià)格有波動(dòng)，其浮動(dòng)價(jià)格和概率策得如下表。試確價(jià)格和概率策得如下表。試確定該廠應(yīng)在哪一周以什么價(jià)格定該廠應(yīng)在哪一周以什么價(jià)格購(gòu)入，能使其采購(gòu)價(jià)的數(shù)學(xué)期購(gòu)入，能使其

23、采購(gòu)價(jià)的數(shù)學(xué)期望值最小，并求出期望值。望值最小，并求出期望值。價(jià)價(jià) 格格 概概 率率 5 50 00 0 6 60 00 0 7 70 00 00 0. . 3 30 0. . 3 30 0. .4 44.4 動(dòng)態(tài)規(guī)劃的應(yīng)用(三) 3 不確定性采購(gòu)問題 設(shè)有n個(gè)工件需要在機(jī)床A、B上加工，每個(gè)工件都必須先經(jīng)過A而后B兩道加工工序。以ai、bi分別表示工件i(1in)在A、B上的加工時(shí)間。問應(yīng)如何在兩機(jī)床上安排各工件的加工順序，使在機(jī)床A上加工第一個(gè)工件開始到在機(jī)床B上加工完最后一個(gè)工件為止，所用的加工總時(shí)間最少？ 加工工件在機(jī)床A上有加工順序問題，在機(jī)床B上也有加工順序問題?？梢宰C明：最優(yōu)加工順序在兩臺(tái)機(jī)床上可同時(shí)實(shí)現(xiàn)。因此，最優(yōu)排序方案可以只在機(jī)床A、B上加工順序相同的排序中尋找。即使如此，所有