动态规划的基本概念和基本方程.ppt

《动态规划的基本概念和基本方程.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§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，…，6n=6(2)状态变量：Sk－第k阶段所处的位置状态集合如S2:(B1,B2)(3)决策变量uk：在第k段Sk状态时决定选取的下一段的某点(4)状态转移方程：Sk＋1＝uk2(6)阶段效益：d(Sk，uk)为第k段，采取策略uk到下一状态的距离(5

2、)最优指标函数：fk(Sk)：第k段，在Sk状态时到终点G的最短距离3例1最短路径问题AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687665833384222133355266434k＝6，f6(F1)＝4f6(F2)＝3k＝5d(E1,F1)+f6(F1)f5(E1)＝mind(E1,F2)+f6(F2)3+4＝min=7u5(E1)=F15+35同理f5(E2)＝5u5(E2)＝F2f5(E3)＝9u5(E3)＝F2k＝4d(D1,E1)+f5(E1)f4(D1)＝mind(D1,E2)

3、+f5(E2)2+7＝min=7u4(D1)=E22+56同理f4(D2)＝6u4(D2)＝E2f4(D3)＝8u4(D3)＝E2K=3……7k＝1d(A,B1)+f2(B1)f1(A)＝mind(A,B2)+f2(B2)5+13＝min=18u1(A)=B13+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

4、台，高负荷时S1=8y1a=0.7低负荷时S2=5y2b=0.9问：每年初应如何安排分配机器，可使得5年总收益最大？10解(1)阶段：k=1,2,3,4,5n=5(2)状态变量Sk：第k年初始的完好设备数(3)决策变量uk：第k年初始分到高负荷下的机器数Sk-uk：第k年初始分到低负荷下的机器数11(4)状态转移方程：Sk＋1＝0.7uk+0.9(Sk-uk)=0.9Sk-0.2uk(5)最优指标函数：fk(Sk)—从第k-5年末采取最优策略的最大收益(6)一年收益：d(Sk,uk)=8uk+5(Sk-uk)=3uk

5、+5Sk12基本方程fk(Sk)＝max{d(Skuk)+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.6S4u4*=S40≤u4≤

6、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.5S3u3*=S30≤u3≤S30≤u3≤S30≤u3≤S316K=2f2(S2)＝max{20.7S2-0.5u2}＝20.7S2u2*=00≤u2≤S2K=1f1(S1)＝23.7S1u1*=0当S1＝1000时f1(1000)＝2370017结论第一年1000台投入低负荷S2＝0.9S1-0.2u1＝0.9S1

7、＝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(Skuk)+fk+1(Sk+1)}k=n,…1fk+1(Sk+1)＝019