动态规划应用举例

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,动态规划方法应用举例,学习例题的方法建议：,第一步,先看问题，充分理解问题的条件、情况及求解目标。,第二步,结合前面讲到的理论和解题过程，考虑如何确定问题的状态变量,决策变量以及指标函数等这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。,第三步,动手把建模思路数学地表达出来，或者说，把该问题作,为习题独立地来做。,第四步,把自己的求解放到一边，看书中的求解方法，要充分理,解教材中的论述.,第五步,对照自己的求解，分析成败,。,注意:,动态规划的四大要素,状态变量及其可能集合 s,k,S,k,决策变量及其允许集合 x,k,D,k,状态转移方程 s,k,+1,=,T,k,(s,k,x,k,),阶段指标 v,k,(s,k,x,k,),资 源 分 配 问 题,求对三个项目的最优投资分配，使总投资效益最大。,例1,有资金4万元，投资A、B、C三个项目，每个项目,的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（吨）和投入资金（万元）关系见下表：,项目,投入资金,A,B,C,1万元,15吨,13吨,11吨,2万元,28吨,29吨,30吨,3万元,40吨,43吨,45吨,4万元,51吨,55吨,58吨,阶段,k,：,每投资一个项目作为一个阶段；,k=1,2,3,状态变量,s,k,：,投资第,k,个项目前的资金数；,决策变量,x,k,：第,k,个项目的投资额；,决策允许集合：,0,x,k,s,k,(k=1,2),x,3,=,s,3,状态转移方程：,s,k,+1,=,s,k,-,x,k,阶段指标：,v,k,(,s,k,s,k,),见表中所示；,基本,(,递推,),方程：,f,k,(,s,k,)=,max,v,k,(,s,k,x,k,)+,f,k,+1,(,s,k,+1,),终端条件：,f,4,(,s,4,)=0,s,3,D,3,(s,3,),v,3,(s,3,x,3,),v,3,(s,3,x,3,)+f,4,(s,4,),f,3,(s,3,),x,3,*,0,0,0,0+0=0,0,0,1,11,1,1,11,11+0=11*,2,30,2,2,30,30+0=30*,3,45,3,3,45,45+0=45*,4,58,4,4,58,58+0=58*,s,2,D,2,(s,2,),s,3,v,2,(s,2,x,2,),v,2,(s,2,x,2,)+f,3,(s,3,),f,2,(s,2,),x,2,*,0,0,0,0,0+0=0,0,0,1,0,1,0,0+11=11,13,1,1,0,13,13+0=13*,2,0,2,0,0+30=30*,30,0,1,1,13,13+11=24,2,0,29,29+0=29,3,0,3,0,0+45=45*,45,0,1,2,13,13+30=43,2,1,29,29+11=40,3,0,43,43+0=43,4,0,4,0,0+58=58,59,2,1,3,13,13+45=58,2,2,29,29+30=59*,3,1,43,43+11=54,4,0,55,55+0=55,s,1,D,1,(s,1,),s,2,v,1,(s,1,x,1,),v,1,(s,1,x,1,)+f,2,(s,2,),f,1,(s,1,),x,1,*,4,0,4,0,0+59=59,60,1,1,3,15,15+45=60*,2,2,28,28+30=58,3,1,40,40+13=53,4,0,51,51+0=51,最优解为:,即项目,A,投资1万元，项目,B,投资0万元，项目,C,投资3万元，,最大效益为60万吨。,生 产 库 存 问 题,为了调节生产生产和需求，工厂设有一个产品仓库，库容量,H,=9。已知期初库存量为2，要求期末（七月低）库存量为0。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低。,例,一个工厂生产某种产品,1-7月份生产成本和产品需求量的,变化情况如下表,阶段,k,：,月份，,k,=1,2,7,；,状态变量,s,k,：,第,k,个月初（发货以前）的库存量；,决策变量,x,k,：,第,k,个月的生产量,；,状态转移方程：,s,k,+1,=,s,k,-,d,k,+,x,k,；,决策允许集合：,D,k,(,x,k,)=,x,k,|,x,k,0,d,k,+1,s,k,+1,H,=,x,k,|,x,k,0,d,k,+1,s,k,-,d,k,+,x,k,H,；,阶段指标：,v,k,(,s,k,x,k,)=,c,k,x,k,；,基本(递推)方程,：,。,由状态转移方程可得:,注意:,其中:,于是:,以及,因,所以,并且,与上述运算顺序反推，结合状态转移方程，可得最优策略为:,将以上结果总结成下表,：,练习：,某公司有资金9万元欲投资于三个项目。若投资于项目,，问应如何分配投资数额可使总盈利最大？,的投资额为,时，其盈利分别为,采购与销售问题,例,某商店在未来的4个月里，准备利用它的一个仓库来专门,经销某种商品，仓库最大容量能贮存这种商品1000单位。假定该,商店每月只能出卖仓库现有的货。当商店在某月购货时，下月初才,能到货。预测该商品未来四个月的买卖价格如表4.6所示。假定商,店在1月开始经销时，仓库贮有该商品500单位。问若不计库存费,用，该商店应如何制定1月至4月的订购与销售计划，使预期获利,最大？,表4.6,月份（k),购买单价,销售单价,1,10,12,2,9,8,3,11,13,4,15,17,解,按月份划分为4个阶段，,状态变量,为第,月初时仓库中的存货量（含上月订货）；,决策变量,为第,月卖出的货物数量；决策变量,为第,月订购的货物数量,状态转移方程为,第k段的指标为第k段的盈利,：,；,k子过程的指标函数为从第k月到4月末所获累计盈利,于是可得问题的动态规划基本方程,当,k,=4 时,对应最优决策为：,当,k,=3 时,为得到此阶段的最优指标值，需求解线性规划问题：,解得：,且,当,k,=2 时,求解线性规划问题:,解得：,当 k=1 时,则有,求解线性规划问题：,解得：,按上述运算过程，利用状态转移方程反推可得最优策略,（见下表）,月份,售出量,购进量,1,500,0,2,0,1000,3,1000,1000,4,1000,0,例,某公司有资金10万元,设投资于项目,的投资额为,时，其盈利分别为,问应如何分,配投资数额才能使总收益最大?,解,(这是一个与时间无明显关系的静态最优化问题),阶段,k,：,每投资一个项目作为一个阶段,(k=1,2,3),状态变量,s,k,：,投资第,k,个项目前的资金数；,决策变量,x,k,：第,k,个项目的投资额；,决策允许集合：,0,x,k,s,k,(k=1,2),x,3,=,s,3,状态转移方程：,s,k,+1,=,s,k,-,x,k,(,k=1,2),阶段指标：,7.,基本方程:,极大值只可能在,的端点处达到.,当,但此时,显然,在0,10的端点处达到最大.,于是,只可能,再由状态转移方程顺推,得,因,所以,又因为,所以,最优投资方案为全部资金均投于第三个项目,可得最大收益200万元.,需要指出的是，前面的讨论都基于一种前提，即过程的初始状,态是已知的。这种情况下，建立逆推形式的基本方程，进行逆推,运算，就可求得过程的最优策略和最优指标函数值。我们称这种进,行逆推运算的方法为“逆推算法”。但实际应用中，可能有些过程的,初始状态是未知的，而终止状态却是已知的。这时，我们可设想过,程的行进方向颠倒,即第k阶段的决策变量,使过程由状态,演变到状态,因此状态转移方程变为形式,同时基本方程改为形式:,或,求解方法也就变成了“顺推算法”，即从第一阶段开始，逐阶段,向后，直到最后一个阶段，以求出过程的最优策略和最优指标函数,值。,