动态规划应用举例

《动态规划应用举例》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划方法应用举例学习例题的方法建议：第一步先看问题，充分理解问题的条件、情况及求解目标。第二步结合前面讲到的理论和解题过程，考虑如何确定问题的状态变量,决策变量以及指标函数等——这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。第三步动手把建模思路数学地表达出来，或者说，把该问题作为习题独立地来做。第四步把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述.第五步对照自己的求解，分析成败。注意:动态规划的四大要素①状态变量及其可能集合skSk②决

2、策变量及其允许集合xkDk③状态转移方程sk+1=Tk(sk,xk)④阶段指标vk(sk,xk)资源分配问题求对三个项目的最优投资分配，使总投资效益最大。例1有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（吨）和投入资金（万元）关系见下表：项目投入资金ABC1万元15吨13吨11吨2万元28吨29吨30吨3万元40吨43吨45吨4万元51吨55吨58吨阶段k：每投资一个项目作为一个阶段；k=1,2,3状态变量sk：投资第k个项目前的资金数；

3、决策变量xk：第k个项目的投资额；决策允许集合：0≤xk≤sk(k=1,2),x3=s3状态转移方程：sk+1=sk-xk阶段指标：vk(sk,sk)见表中所示；基本(递推)方程：fk(sk)=max{vk(sk,xk)+fk+1(sk+1)}终端条件：f4(s4)=0s3D3(s3)v3(s3,x3)v3(s3,x3)+f4(s4)f3(s3)x3*0000+0=000111111111+0=11*230223030+0=30*345334545+0=45*458445858+0=58*s2D2(s2

4、)s3v2(s2,x2)v2(s2,x2)+f3(s3)f2(s2)x2*00000+0=00010100+11=11131101313+0=13*20200+30=30*300111313+11=24202929+0=2930300+45=45*450121313+30=43212929+11=40304343+0=4340400+58=58592131313+45=58222929+30=59*314343+11=54405555+0=55s1D1(s1)s2v1(s1,x1)v1(s1,x1)+f

5、2(s2)f1(s1)x1*40400+59=59601131515+45=60*222828+30=58314040+13=53405151+0=51最优解为:即项目A投资1万元，项目B投资0万元，项目C投资3万元，最大效益为60万吨。生产库存问题为了调节生产生产和需求，工厂设有一个产品仓库，库容量H=9。已知期初库存量为2，要求期末（七月低）库存量为0。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低。例２一个工厂生产某种产品,1-7月份生产成本

6、和产品需求量的变化情况如下表阶段k：月份，k=1,2,…,7,；状态变量sk：第k个月初（发货以前）的库存量；决策变量xk：第k个月的生产量；状态转移方程：sk+1=sk-dk+xk；决策允许集合：Dk(xk)={xk

7、xk0,dk+1sk+1H}={xk

8、xk0,dk+1sk-dk+xkH}；阶段指标：vk(sk,xk)=ckxk；基本(递推)方程：。由状态转移方程可得:注意:其中:于是:以及,因所以并且与上述运算顺序反推，结合状态转移方程，可得最优策略为:将以上结果总结成下表：练习：某公

9、司有资金9万元欲投资于三个项目。若投资于项目，问应如何分配投资数额可使总盈利最大？的投资额为时，其盈利分别为采购与销售问题例３某商店在未来的4个月里，准备利用它的一个仓库来专门经销某种商品，仓库最大容量能贮存这种商品1000单位。假定该商店每月只能出卖仓库现有的货。当商店在某月购货时，下月初才能到货。预测该商品未来四个月的买卖价格如表4.6所示。假定商店在1月开始经销时，仓库贮有该商品500单位。问若不计库存费用，该商店应如何制定1月至4月的订购与销售计划，使预期获利最大？表4.6月份（k)购买单价销售

10、单价110122983111341517解按月份划分为4个阶段，状态变量为第月初时仓库中的存货量（含上月订货）；决策变量为第月卖出的货物数量；决策变量为第月订购的货物数量．状态转移方程为第k段的指标为第k段的盈利：；k子过程的指标函数为从第k月到4月末所获累计盈利于是可得问题的动态规划基本方程当k=4时对应最优决策为：当k=3时为得到此阶段的最优指标值，需求解线性规划问题：解得：且当k=2时求解线性规划问题:解得：当k=1时则有求解线性规划