§5.2 动态规划的基本概念和基本方程(一)基本概念(1)阶段：k(2)状态变量：Sk (3)决策变量： uk(Sk)(4)策略 (5)状态转移方程： Sk＋1 ＝T (Sk ， uk)(6)指标函数： Vk，n (Sk)(7)最优指标函数： fk (Sk) 1(二)前例1(1)阶段：k＝1，2，…，6 n=6(2)状态变量：Sk－第k阶段所处的位置状态集合 如S2 : (B1 , B2)(3)决策变量uk ：在第k段Sk状态时决定选 取的下一段的某点(4)状态转移方程 ：Sk＋1 ＝uk2(6)阶段效益：d(Sk ，uk)为第k段，采取策略uk 到下一状态的距离(5)最优指标函数： fk (Sk)：第k段，在Sk状态时到终点G的最 短距离3例1 最短路径问题AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531 3 68 7 6658 33 3 842221333552 66434k＝6， f6(F1)＝4 f6(F2)＝3k＝5d(E1 ,F1) +f6(F1)f5(E1)＝mind(E1 ,F2) +f6(F2)3+4＝min =7 u5(E1)= F1 5+3 5同理 f5(E2)＝5 u5(E2)＝ F2f5(E3)＝9 u5(E3)＝ F2 k＝4d(D1 ,E1) +f5(E1)f4(D1)＝mind(D1 ,E2) +f5(E2)2+7＝min =7 u4(D1)= E2 2+56同理 f4(D2)＝6 u4(D2)＝ E2f4(D3)＝8 u4(D3)＝ E2K=3… … 7k＝1d(A ,B1) +f2(B1)f1(A)＝mind(A ,B2) +f2(B2)5+13＝min =18 u1(A)= B1 3+168(三)基本方程fk(Sk)＝min{d(Sk , uk)+ fk+1(Sk+1)} k=6, …1f7(S7)＝0或fk(Sk)＝min{d(Sk , uk)+ fk+1(Sk+1)} k=5, …1f6(S6)＝ min{d(S6 , u6)} 9例2已知某种完好的机器1000台，高负荷时 S1=8y1 a=0.7 低负荷时 S2=5y2 b=0.9 问：每年初应如何安排分配机器，可使得5年总收益最大？10解(1)阶段：k=1,2,3,4,5 n=5(2)状态变量Sk ：第k年初始的完好设备数(3)决策变量uk：第k年初始分到高负荷下的机器数Sk- uk：第k年初始分到低负荷下的机器数11(4)状态转移方程： Sk＋1 ＝0.7 uk+0.9(Sk - uk)= 0.9Sk - 0.2 uk(5)最优指标函数：fk (Sk)—从第k-5年末采取最优策略的最大收益(6)一年收益：d(Sk , uk)=8uk+5(Sk - uk)= 3uk +5Sk 12基本方程fk(Sk)＝max{d(Sk uk)+ fk+1(Sk+1)} k=5, …1f6(S6)＝0uk即 fk(Sk)＝max{(3uk+5Sk)+ fk+1(0.9Sk- 0.2uk)} k=4, …1f5(S5)＝ max{3uk+5Sk} ukuk13K=5f5(S5)＝ max{3u5+5S5}＝8S5u5 * =S50≤u5≤S514K=4f4(S4)＝ max{3u4+5S4 + f5(S5)}＝ max{3u4+5S4 +8(0.9S4- 0.2u4)}＝ max{1.4u4+12.2S4}＝ 13.6S4 u4 * =S40 ≤ u4 ≤ S40 ≤ u4 ≤ S40 ≤ u4 ≤ S415K=3f3(S3)＝ max{3u3+5S3 + f4(S4)}＝ max{3u3+5S3 +13.6(0.9S3- 0.2u3)}＝ max{0.28u3+17.24S3}＝ 17.5S3 u3 * =S30 ≤ u3 ≤ S30 ≤ u3 ≤ S30 ≤ u3 ≤ S316K=2f2(S2)＝ max{20.7S2-0.5u2}＝ 20.7S2 u2* =00 ≤ u2 ≤ S2K=1f1(S1)＝23.7 S1 u1* =0当S1＝1000时 f1(1000)＝2370017结论第一年1000台投入低负荷S2＝ 0.9S1-0.2u1＝ 0.9S1 ＝ 900第二年900台投入低负荷S3＝ 0.9S2-0.2u2＝ 0.9S2 ＝ 810第三年810台投入高负荷S4＝ 0.9S3-0.2u3＝ 0.7S3 ＝ 56718第四年567台投入高负荷S5＝ 0.9S4-0.2u4＝ 0.7S4 ＝397第五年397台投入高负荷基本方程fk(Sk)＝OPT{d(Sk uk)+ fk+1(Sk+1)} k=n, …1fk+1(Sk+1)＝019。