建立动态规划数学模型的步骤教学内容.ppt

《建立动态规划数学模型的步骤教学内容.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、建立动态规划数学模型的步骤⒊确定决策变量uk及允许决策变量集合Dk(uk)。⒋根据状态变量之间的递推关系，写出状态转移方程：xk+1=T(xk,uk(xk))⒌建立指标函数。一般用rk(xk,uk)描写阶段效应，fk（xk）表示k—n阶段的最优子策略函数。⒍建立动态规划基本方程：fk（xk）=opt｛rk(xk,uk(xk))﹡fk+1（xk+1）｝uk∈Dk(uk)fn+1（xn+1）=Ck=n,n-1,…,1以上是建立动态规划模型的过程，这个过程是正确求解动态规划的基础。在动态规划基本方程中

2、，rk(xk,uk)，xk+1=T(xk,uk)都是已知函数，最优子策略fk（xk）与fk+1（xk+1）之间是递推关系，要求出fk（xk）及uk(xk)，需要先求出fk+1（xk+1），这就决定了应用动态规划基本方程求最优策略总是逆着阶段的顺序进行的。由后向前逐步计算，最终可以算出全过程的最优策略函数值及最优策略。另一方面，由于k+1阶段的状态xk+1=T(xk,uk)是由前面的状态xk和决策uk所形成的，在计算fk+1（xk+1）时还不能具体确定xk+1的值，所以，这就要求必须就k+1阶段的

3、各个可能状态计算fk+1（xk+1），因此动态规划方法不但能求出整个问题的最优策略和最优目标值，而且还能求出决策过程中所有可能状态的最优策略及最优目标值。下面就按上述步骤求解例2。例2（带回收的资源分配问题）某厂新购某种机床125台。据估计，这种设备5年后将被其它设备所代替。此机床如在高负荷状态下工作，年损坏率为1/2，年利润为10万元；如在低负荷状态下工作，年损坏率为1/5，年利润为6万元。问应如何安排这些机床的生产负荷，才能使5年内获得的利润最大？解：以年为阶段，k=1，2，3，4，5取k年

4、初完好的机床数为状态变量xk以k年初投入高负荷运行的机床数为决策变量uk，则低负荷运行机床数是xk-uk，于是状态转移方程为：xk+1=1/2uk+4/5（xk-uk）=0.8xk-0.3uk以利润为目标函数，则k年利润为：10uk+6（xk-uk）=4uk+6xk记fk（xk）为k年至5年末最大总利润，则动态规划基本方程为：fk（xk）=max｛4uk+6xk+fk+1（0.8xk-0.3uk）｝0≤uk≤xkf6（x6）=0k=5,4,3,2,1以上是建立动态模型的过程，下面具体求解。注意动

5、态规划基本方程为：fk（xk）=max｛4uk+6xk+fk+1（0.8xk-0.3uk）｝0≤uk≤xk所以，当k=5时，有f5（x5）=max｛4u5+6x5+f6（x6）｝=10x5u5=x50≤u5≤x5当k=4时f4（x4）=max｛4u4+6x4+f5（0.8x4-0.3u4）｝0≤u4≤x4=max｛4u4+6x4+10（0.8x4-0.3u4）｝0≤u4≤x4=max｛u4+14x4｝=15x4u4=x40≤u4≤x4当k=3时f3（x3）=max｛4u3+6x3+f4（0.8x

6、3-0.3u3）｝0≤u3≤x3=max｛4u3+6x3+15（0.8x3-0.3u3）｝0≤u3≤x3=max｛-0.5u3+18x3｝=18x3u3=00≤u3≤x3动态规划基本方程为：fk（xk）=max｛4uk+6xk+fk+1（0.8xk-0.3uk）｝0≤uk≤xk当k=2时f2（x2）=max｛4u2+6x2+f3（0.8x2-0.3u2）｝0≤u2≤x2=max｛4u2+6x2+18（0.8x2-0.3u2）｝0≤u2≤x2=max｛-1.4u2+20.4x2｝=20.4x2u2

7、=00≤u2≤x2当k=1时f1（x1）=max｛4u1+6x1+f2（0.8x1-0.3u1）｝0≤u1≤x1=max｛4u1+6x1+20.4（0.8x1-0.3u1）｝0≤u1≤x1=max｛-2.12u1+22.32x1｝=22.32x1u1=00≤u1≤x1=22.32×125=2790（万元）至此已算得最大总利润2790万元，再按与计算过程相反的顺序推回去，可得最优计划如下表所示：年份k完好机床数xk+1=0.8xk-0.3uk高负荷机床数uk低负荷机床数xk-uk第一年125012

8、5第二年1000100第三年80080第四年64640第五年32320此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢