第七 動(dòng)態(tài)規(guī)劃

會(huì)計(jì)學(xué)1第七動(dòng)態(tài)規(guī)劃1．階段：?jiǎn)栴}要作出決策的步數(shù)，用k表示。第1頁/共42頁2．狀態(tài)：各階段開始的客觀條件。記作sk。S1={A}，S2={B1，B2，B3}第2頁/共42頁3．決策：第k階段到第k+1階段所做的選擇，

用uk(sk)表示。Dk（sk）表示第k

階段從sk出發(fā)的決策集合。在B1處，如果選擇C2，則u2(B1)=C2。D2(B1)={C1，C2，C3}每階段的決策系列構(gòu)成策略。第3頁/共42頁4．狀態(tài)轉(zhuǎn)移方程：

第k階段到第k+1階段的路徑。第4頁/共42頁5．指標(biāo)函數(shù)：決策的效益量度。

階段指標(biāo)函數(shù)：用d（sk，uk）表示。過程指標(biāo)函數(shù)：最優(yōu)指標(biāo)函數(shù)：第5頁/共42頁找出A到E的最短路徑

2．動(dòng)態(tài)規(guī)劃的基本思路第6頁/共42頁劃分階段IIVIIIII第7頁/共42頁逆序求解f4(D1)=5，f4(D2)=2

f3(C1)=8；f3(C2)=7；f3(C3)=12第8頁/共42頁

f3(C1)=8；f3(C2)=7；f3(C3)=12第9頁/共42頁f2(B1)=20；f2(B2)=14；f3(B3)=19第10頁/共42頁動(dòng)態(tài)規(guī)劃遞推方程第11頁/共42頁動(dòng)態(tài)規(guī)劃基本思想1．劃分階段，選取狀態(tài)變量、決策變量。2．從邊界條件出發(fā)，逐步推優(yōu)。3．每階段的最優(yōu)從全局考慮。過程最優(yōu)的性質(zhì)：過程的最優(yōu)策略，其以后的所有決策應(yīng)是最優(yōu)決策。4．動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)：將多階段決策問題轉(zhuǎn)化為一個(gè)連續(xù)遞推的過程，由后向前逐步計(jì)算。第12頁/共42頁動(dòng)態(tài)規(guī)劃解法

劃分階段確定狀態(tài)變量及允許狀態(tài)集合確定決策變量及決策空間確定狀態(tài)轉(zhuǎn)移方程確定轉(zhuǎn)移指標(biāo)函數(shù)并建立遞歸方程第13頁/共42頁某公司有10萬元資金，投資三個(gè)項(xiàng)目，其收益分別為：

建立模型：

連續(xù)型變量的解法第14頁/共42頁階段：k=1，2，3狀態(tài)sk:第k階段可投資資金。決策變量xk:第k個(gè)項(xiàng)目投資資金。狀態(tài)轉(zhuǎn)移方程：指標(biāo)函數(shù)：遞推方程：第15頁/共42頁第16頁/共42頁第17頁/共42頁第18頁/共42頁

有資金4萬元，投資A、B、C三個(gè)項(xiàng)目，每個(gè)項(xiàng)目的投資效益與投入該項(xiàng)目的資金有關(guān)。三個(gè)項(xiàng)目A、B、C的投資效益（萬噸）和投入資金（萬元）的關(guān)系見下表：求對(duì)三個(gè)項(xiàng)目的最優(yōu)投資分配，使總投資效益最大。

離散型變量的解法第19頁/共42頁項(xiàng)目A項(xiàng)目B項(xiàng)目C指標(biāo)值(收益)V1(s1,x1)指標(biāo)值(收益)V2(s2,x2)指標(biāo)值(收益)V3(s3,x3)s1s2s3s4x1x2x3階段k：每投資一個(gè)項(xiàng)目作為一個(gè)階段；狀態(tài)變量sk：投資第k個(gè)項(xiàng)目前的資金余額；決策變量xk：第k個(gè)項(xiàng)目的投資額；決策允許集合：Dk(sk)={0≤xk≤sk}狀態(tài)轉(zhuǎn)移方程：sk+1=sk-xk階段指標(biāo)：vk(sk,xk)見表中所示；遞推方程：fk(sk)=max{vk(sk,xk)+fk+1(sk+1)}終端條件：f4(s4)=0第20頁/共42頁k=4，f4(s4)=0;k=3，0≤x3≤s3，s4=s3-x3

第21頁/共42頁k=2，0≤x2≤s2，s3=s2-x2

第22頁/共42頁k=1，0≤x1≤s1，s2=s1-x1

最優(yōu)解為:s1=4,x1*=1,s2=s1-x1=3,x2*=0,最大效益為60萬噸s3=s2-x2*=3,x3*=3,s4=s3-x3=0第23頁/共42頁機(jī)器負(fù)荷分配問題

某種機(jī)器可以在高、低兩種負(fù)荷下生產(chǎn)。高負(fù)荷生產(chǎn)條件下機(jī)器完好率為0.7，即如果年初有u臺(tái)完好機(jī)器投入生產(chǎn)，則年末完好的機(jī)器數(shù)量為0.7u臺(tái)。系數(shù)0.7稱為完好率。年初投入高負(fù)荷運(yùn)行的u臺(tái)機(jī)器的年產(chǎn)量為8u噸。系數(shù)8稱為單臺(tái)產(chǎn)量。低負(fù)荷運(yùn)行時(shí)，機(jī)器完好率為0.9，單臺(tái)產(chǎn)量為5噸。設(shè)開始時(shí)有1000臺(tái)完好機(jī)器，要制訂五年計(jì)劃，每年年初將完好的機(jī)器一部分分配到高負(fù)荷生產(chǎn)，剩下的機(jī)器分配到低負(fù)荷生產(chǎn)，使五年的總產(chǎn)量為最高。

第24頁/共42頁第1年s1s2s3x1x2x3第2年第3年第4年第5年s4s5s6x4x5指標(biāo)值(產(chǎn)量)V1(s1,x1)指標(biāo)值(產(chǎn)量)V2(s2,x2)指標(biāo)值(產(chǎn)量)V5(s5,x5)指標(biāo)值(產(chǎn)量)V4(s4,x4)指標(biāo)值(產(chǎn)量)V3(s3,x3)第25頁/共42頁動(dòng)態(tài)規(guī)劃模型構(gòu)造階段k：運(yùn)行年份（k=1,2,3,4,5,6）；狀態(tài)變量sk：第k年初完好的機(jī)器數(shù)（k=1,2,3,4,5,6）；決策變量xk：第k年投入高負(fù)荷運(yùn)行的機(jī)器數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=0.7xk+0.9(sk-xk)決策允許集合：Dk(sk)={xk|0xksk}階段指標(biāo)：vk(sk,xk)=8xk+5(sk-xk)終端條件：f6(s6)=0遞推方程：

fk(sk)=max{vk(sk,xk)+fk+1(sk+1)}

=max{8xk+5(sk-xk)+fk+1[0.7xk+0.9(sk-xk)]} 0xksk第26頁/共42頁第5年s5s6x5指標(biāo)值(產(chǎn)量)V5(s5,x5)…+f6(s6)第27頁/共42頁第4年s4s5x4指標(biāo)值(產(chǎn)量)V4(s4,x4)…+f5(s5)第28頁/共42頁f3(s3)=max{8x3+5(s3-x3)+f4(s4)} 0x3s3=max{8x3+5(s3-x3)+13.7s4}

0x3s3=max{8d3+5(s3-d3)+13.7[0.7d3+0.9(s3-d3)]}0x3s3=max{0.28x3+17.24s3}=17.52s30x3s3

x3*=s3s3x3第3年s4指標(biāo)值(產(chǎn)量)V3(s3,x3)…+f4(s4)第29頁/共42頁f2(s2)=max{8x2+5(s2-x2)+f3(s3)} 0x2s2=max{8x2+5(s2-x2)+17.52s3} 0x2s2=max{8x2+5(s2-x2)+17.52[0.7x2+0.9(s2-x2)]} 0x2s2=max{-0.504x2+20.77s2}=20.77s2 0x2s2x2*=0s2s3x2第2年指標(biāo)值(產(chǎn)量)V2(s2,x2)…+f3(s3)第30頁/共42頁f1(s1)=max{8x1+5(s1-x1)+f2(s2)} 0x1s1=max{8x1+5(s1-x1)+20.77s2} 0x1s1=max{8x1+5(s1-x1)+20.77[0.7x1+0.9(s1-x1)]} 0x1s1=max{-0.05x1+23.69s1}=23.69s1

0x1s1x1*=0第1年s1s2x1指標(biāo)值(產(chǎn)量)V1(s1,x1)…+f2(s2)第31頁/共42頁由此可以得到：

f1(s1)=23.69s1, x1*=0

f2(s2)=20.77s2, x2*=0 f3(s3)=17.52s3, x3*=s3

f4(s4)=13.60s4, x4*=s4 f5(s5)=8s5 x5*=s5用s1=1000代入，得到五年最大產(chǎn)量為

f1(s1)=f1(1000)=23690第32頁/共42頁每年投入高負(fù)荷運(yùn)行的機(jī)器數(shù)以及每年初完好的機(jī)器數(shù)為：

s1=1000

x1*=0, s2=0.7x1+0.9(s1-x1)=900

x2*=0, s3=0.7x2+0.9(s2-x2)=810

x3*=s3=810, s4=0.7x3+0.9(s3-x3)=567

x4*=s4=567, s5=0.7x4+0.9(s4-x4)=397

x5*=s5=397, s6=0.7x5+0.9(s5-x5)=278第33頁/共42頁生產(chǎn)經(jīng)營(yíng)問題p220階段k：每個(gè)月作為一個(gè)階段；狀態(tài)變量sk：第k月初庫(kù)存；決策變量xk：第k月生產(chǎn)量；狀態(tài)轉(zhuǎn)移方程：sk+1=sk+xk-gk，階段指標(biāo)：生產(chǎn)：C（xk），存貯：E（xk）；遞推方程：fk(sk)=min{C（xk）+E（xk）+fk+1(sk+1)}終端條件：f5(s5)=0第34頁/共42頁K=4，s40123x44321f476.565.5K=3，第35頁/共42頁s30123x3234512340123012f476.565.576.565.576.565.56.565.5f312

11.5

8

8

x32

1

0

0

K=2，第36頁/共42頁s20123x23456234512340123f31211.5881211.5881211.5881211.588f21615.51513.5

x25430

K=1，第37頁/共42頁s10x12345f21615.51513.5f121x12反向推之：s1=0,x1=2,g1=2s2=0,x2=5,g2=3

s3=2,x3=0,g3=2s4=0,x4=4,g4=4第38頁/共42頁設(shè)備更新問題