《动态规划应用举例.ppt》由会员分享,可在线阅读,更多相关《动态规划应用举例.ppt(38页珍藏版)》请在三一文库上搜索。
1、动态规划方法应用举例,学习例题的方法建议:,第一步 先看问题,充分理解问题的条件、情况及求解目标。,第二步 结合前面讲到的理论和解题过程,考虑如何确定问题的状态变量,决策变量以及指标函数等这一步在开始时会感到困难,但是一定要下决心去思考,在思考过程中深入理解前文讲到的概念和理论。,第三步 动手把建模思路数学地表达出来,或者说,把该问题作 为习题独立地来做。,第四步 把自己的求解放到一边,看书中的求解方法,要充分理 解教材中的论述.,第五步 对照自己的求解,分析成败。,注意:动态规划的四大要素 状态变量及其可能集合 skSk 决策变量及其允许集合 xk Dk 状态转移方程 sk+1= Tk (s
2、k ,xk ) 阶段指标 vk ( sk ,xk ),资 源 分 配 问 题,求对三个项目的最优投资分配,使总投资效益最大。,例1 有资金4万元,投资A、B、C三个项目,每个项目 的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益(吨)和投入资金(万元)关系见下表:,阶段k:每投资一个项目作为一个阶段;k=1,2,3 状态变量sk:投资第k个项目前的资金数; 决策变量xk:第k个项目的投资额; 决策允许集合:0xksk (k=1,2), x3=s3 状态转移方程:sk+1=sk-xk 阶段指标:vk(sk ,sk)见表中所示; 基本(递推)方程:fk(sk)=maxvk(sk ,x
3、k)+fk+1(sk+1) 终端条件:f4(s4)=0,最优解为:,即项目A投资1万元,项目B投资0万元,项目C投资3万元, 最大效益为60万吨。,生 产 库 存 问 题,为了调节生产生产和需求,工厂设有一个产品仓库,库容量H=9。已知期初库存量为2,要求期末(七月低)库存量为0。每个月生产的产品在月末入库,月初根据当月需求发货。求七个月的生产量,能满足各月的需求,并使生产成本最低。,例 一个工厂生产某种产品,1-7月份生产成本和产品需求量的 变化情况如下表,阶段k:月份,k=1,2,7,; 状态变量sk:第k个月初(发货以前)的库存量; 决策变量xk:第k个月的生产量; 状态转移方程:sk+
4、1=sk-dk+xk; 决策允许集合: Dk(xk)=xk | xk0, dk+1sk+1H =xk | xk0, dk+1sk-dk+xkH ; 阶段指标:vk(sk ,xk)=ckxk;,基本(递推)方程:,。,由状态转移方程可得:,注意:,其中:,于是:,以及,因,所以,并且,与上述运算顺序反推,结合状态转移方程,可得最优策略为:,将以上结果总结成下表:,练习:某公司有资金9万元欲投资于三个项目。若投资于项目,,问应如何分配投资数额可使总盈利最大?,的投资额为,时,其盈利分别为,采购与销售问题,例 某商店在未来的4个月里,准备利用它的一个仓库来专门 经销某种商品,仓库最大容量能贮存这种商
5、品1000单位。假定该 商店每月只能出卖仓库现有的货。当商店在某月购货时,下月初才 能到货。预测该商品未来四个月的买卖价格如表4.6所示。假定商 店在1月开始经销时,仓库贮有该商品500单位。问若不计库存费 用,该商店应如何制定1月至4月的订购与销售计划,使预期获利 最大?,表4.6,解 按月份划分为4个阶段,,状态变量,为第,月初时仓库中的存货量(含上月订货);,决策变量,为第,月卖出的货物数量;决策变量,为第,月订购的货物数量,状态转移方程为,第k段的指标为第k段的盈利:,;,k子过程的指标函数为从第k月到4月末所获累计盈利,于是可得问题的动态规划基本方程,当 k=4 时,对应最优决策为:
6、,当 k=3 时,为得到此阶段的最优指标值,需求解线性规划问题:,解得:,且,当 k=2 时,求解线性规划问题:,解得:,当 k=1 时,则有,求解线性规划问题:,解得:,按上述运算过程,利用状态转移方程反推可得最优策略 (见下表),例 某公司有资金10万元,设投资于项目,的投资额为,时,其盈利分别为,问应如何分,配投资数额才能使总收益最大?,解 (这是一个与时间无明显关系的静态最优化问题),阶段k:每投资一个项目作为一个阶段(k=1,2,3) 状态变量sk:投资第k个项目前的资金数; 决策变量xk:第k个项目的投资额; 决策允许集合:0xksk (k=1,2), x3=s3 状态转移方程:s
7、k+1=sk-xk ( k=1,2) 阶段指标:,7. 基本方程:,极大值只可能在,的端点处达到.,当,但此时,显然,在0,10的端点处达到最大.,于是,只可能,再由状态转移方程顺推,得,因,所以,又因为,所以,最优投资方案为全部资金均投于第三个项目,可得最大收益200万元.,需要指出的是,前面的讨论都基于一种前提,即过程的初始状 态是已知的。这种情况下,建立逆推形式的基本方程,进行逆推 运算,就可求得过程的最优策略和最优指标函数值。我们称这种进 行逆推运算的方法为“逆推算法”。但实际应用中,可能有些过程的 初始状态是未知的,而终止状态却是已知的。这时,我们可设想过 程的行进方向颠倒, 即第k阶段的决策变量,使过程由状态,演变到状态,因此状态转移方程变为形式,同时基本方程改为形式:,或,求解方法也就变成了“顺推算法”,即从第一阶段开始,逐阶段 向后,直到最后一个阶段,以求出过程的最优策略和最优指标函数 值。,
链接地址:https://www.31doc.com/p-3112440.html