《5.2动态规划的基本概念和基本方程》由会员分享，可在线阅读，更多相关《5.2动态规划的基本概念和基本方程（19页珍藏版）》请在金锄头文库上搜索。
1、5.2 5.2 动态规划的基本概念和基本方程动态规划的基本概念和基本方程(一一)基本概念基本概念(1)阶段：阶段：k(2)状态变量：状态变量：Sk(3)决策变量：决策变量： uk(Sk)(4)策略策略(5)状态转移方程：状态转移方程： Sk1 T (Sk ， uk)(6)指标函数：指标函数： Vk，n (Sk)(7)最优指标函数：最优指标函数： fk (Sk)1(二二)前例前例1(1)阶段：阶段：k1，2，6 n=6(2)状态变量：状态变量：Sk第第k阶段所处的位置阶段所处的位置 状态集合状态集合 如如S2 : (B1 , B2)(3)决策变量决策变量uk ：在第在第k段段Sk状态时决定状态时
2、决定选选 取的下一段的某点取的下一段的某点(4)状态转移方程状态转移方程 ：Sk1 uk2(6)阶段效益：阶段效益： d(Sk ，uk)为第为第k段，采取策略段，采取策略uk 到下一到下一状状 态的距离态的距离(5)最优指标函数：最优指标函数： fk (Sk)：第：第k段，在段，在Sk状态时到终点状态时到终点G的的最最 短距离短距离3例例1 最短路径问题最短路径问题AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876658333 84222133355266434k6， f6(F1)4 f6(F2)3k5 d(E1 ,F1) +f6(F1)f5(E1)min d(E1
3、,F2) +f6(F2) 3+4 min =7 u5(E1)= F1 5+35同理同理 f5(E2)5 u5(E2) F2 f5(E3)9 u5(E3) F2k4 d(D1 ,E1) +f5(E1)f4(D1)min d(D1 ,E2) +f5(E2) 2+7 min =7 u4(D1)= E2 2+56同理同理 f4(D2)6 u4(D2) E2 f4(D3)8 u4(D3) E2K=3 7k1 d(A ,B1) +f2(B1)f1(A)min d(A ,B2) +f2(B2) 5+13 min =18 u1(A)= B1 3+168(三三)基本方程基本方程fk(Sk)mind(Sk , u
4、k)+ fk+1(Sk+1) k=6, 1f7(S7)0或或fk(Sk)mind(Sk , uk)+ fk+1(Sk+1) k=5, 1f6(S6) mind(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年
5、初始分到高负荷年初始分到高负荷下下 的机器数的机器数 Sk- uk：第：第k年初始分到低负荷下年初始分到低负荷下 的机器数的机器数11(4)状态转移方程：状态转移方程： Sk1 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)maxd(Sk uk)+ fk+1(Sk+1) k=5, 1f6(S6)0uk即即fk(Sk)max(3
6、uk+5Sk)+ fk+1(0.9Sk- 0.2uk) k=4, 1f5(S5) max3uk+5Sk ukuk13K=5f5(S5) max3u5+5S58S5 u5 * =S50u5S514K=4f4(S4) max3u4+5S4 + f5(S5) max3u4+5S4 +8(0.9S4- 0.2u4) max1.4u4+12.2S4 13.6S4 u4 * =S40 u4 S40 u4 S40 u4 S415K=3f3(S3) max3u3+5S3 + f4(S4) max3u3+5S3 +13.6(0.9S3- 0.2u3) max0.28u3+17.24S3 17.5S3 u3 *
7、=S30 u3 S30 u3 S30 u3 S316K=2f2(S2) max20.7S2-0.5u2 20.7S2 u2* =00 u2 S2K=1f1(S1)23.7 S1 u1* =0当当S11000时时 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)OPTd(Sk uk)+ fk+1(Sk+1) k=n, 1fk+1(Sk+1)019
