适合全国高校考研与期末考试资料.pptx

运 筹 帷 幄 之 中;综 述 ; 动态规划所研究的对象是多阶段决策问题。 所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。 每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。;实际问题举例;多阶段资源分配回收利用问题 ; 续（1） ; 因此，我们的问题就变成：求y,y1,y2,…,yn-1，以使g(y)+h(x-y)+ g(y1)+h(x1-y1)+ …+g(yn-1)+h(xn-1-yn-1) 达到最大，且满足条件 x1=ay+b(x-y) x2=ay1+b(x1-y1) … … … xn-1=ayn-2+b(xn-2-yn-2) yi与xi均非负,i=1,2, …,n-1 ;生产和存储控制问题;设已知各周期对该商品的需要量如下表所示：; 续（2）; 续（3）;续（4）;动态规划的基本概念与模型;最优化原理;动态规划的数学模型;;第二节 离散确定性动态规划模型的求解;;x4 s4;x3 s3;x2 s2;s1=12;x1 s2;x2 s3;x3 s4;动 态 规 划 应 用;求对三个项目的最优投资分配，使总投资效益最大。;阶段k：每投资一个项目作为一个阶段； 状态变量xk：投资第k个项目前的资金数； 决策变量dk：第k个项目的投资； 决策允许集合：0≤dk≤xk 状态转移方程：xk+1=xk-dk 阶段指标：vk(xk ,dk)见表中所示； 递推方程：fk(xk)=max{vk(xk ,dk)+fk+1(xk+1)} 终端条件：f4(x4)=0;k=4，f4(x4)=0k=3，0≤d3≤x3，x4=x3-d3;k=2，0≤d2≤x2，x3=x2-d2;k=1，0≤d1≤x1，x2=x1-d1;2;2;2;2;2;2;2;2;2;2;2;2;2;2;2;生 产 库 存 问 题;例：一个工厂生产某种产品,1- 7月份生产成本和产品需求量的变化情况如下表：;阶段k：月份，k=1,2,…,7,8； 状态变量xk：第k个月初（发货以前）的库存量； 决策变量dk：第k个月的生产量； 状态转移方程：xk+1=xk-rk+dk； 决策允许集合： Dk(xk)={dk | dk?0, rk+1?xk+1?H } ={dk | dk?0, rk+1?xk-rk+dk?H }； 阶段指标：vk(xk ,dk)=ckdk； 终端条件：f8(x8)=0, x8=0； ;递推方程：fk(xk)=min{vk(xk ,dk)+fk+1(xk+1)} dk?Dk(xk) =min{ckdk+fk+1(xk-rk+dk)} dk?Dk(xk);对于k=6因为 d7=0，所以 x7=r7=4而 x6-r6+d6=x7=4因此有 d6=x7+r6-x6=4+7-x6=11-x6也是唯一的决策。因此递推方程为：f6(x6)=min{c6d6+f7(x7)}  d6=11-x6=10d6=10(11-x6)=110-10x6; 对于k=5 f5(x5)=min{c5d5+f6(x6)} d5?D5(x5) =min{20d5+110-10x6} d5?D5(x5) =min{20d5+110-10(x5-r5+d5)} d5?D5(x5) =min{20d5+110-10(x5-2+d5)} d5?D5(x5) =min{10d5-10x5+130} d5?D5(x5) D5(x5) ={d5| d5?0, r6?x5-r5+d5?H } ={d5|d5?0, r6+r5-x5?d5?H+r5-x5} ={d5| d5?0, 9-x5?d5?11-x5} ;因为x5?H=9，因此9-x5?0，决策允许集合可以简化为 D5(x5)={d5| 9-x5?d5?11-x5}递推方程成为f5(x5)=min{10d5-10x5+130} 9-x5?d5?11-x5 =10(9-x5)-10x5+1