7动态规划.ppt

1、运 筹 学 课 件,Dynamic Programming,综 述,动态规划所研究的对象是多阶段决策问题。 所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。 每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。,动态规划的基本概念与模型,最优化原理,动态规划的数学模型,第二节 离散确定性动态规划模型的求解,s1=12,s5=12,动 态 规 划 应 用,资源分配问题 最短路径问题 旅行售货员问题 生产经营问题 排序,求对三个项目

2、的最优投资分配，使总投资效益最大。,资 源 分 配 问 题,有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表：,阶段k：每投资一个项目作为一个阶段； 状态变量xk：投资第k个项目前的资金数； 决策变量dk：第k个项目的投资； 决策允许集合：0dkxk 状态转移方程：xk+1=xk-dk 阶段指标：vk(xk ,dk)见表中所示； 递推方程：fk(xk)=maxvk(xk ,dk)+fk+1(xk+1) 终端条件：f4(x4)=0,k=4，f4(x4)=0k=3，0d3x3，x4=x3-d3,k=2，

3、0d2x2，x3=x2-d2,k=1，0d1x1，x2=x1-d1,最 短 路 径 问 题,求从A到E的最短路径,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B

4、2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,

5、9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B

6、3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=21,f2(B2)=14,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3

7、,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策

8、 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2 （B2，C1） C1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,

9、8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=

10、12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E 从A到E的最短路径为19，路线为AB 2C1 D1 E,生 产 库 存 问 题,例：一个工厂生产某种产品,1- 7月份生产成本和产品需求量的变化情况如下表：,阶段k：月份，k=1,2,7,8； 状态变量xk：第k个月初（发货以前）的库存量； 决策变量dk：第k个月的生产量； 状态转移方程：xk+1=xk

11、-rk+dk； 决策允许集合： Dk(xk)=dk | dk0, rk+1xk+1H =dk | dk0, rk+1xk-rk+dkH ； 阶段指标：vk(xk ,dk)=ckdk； 终端条件：f8(x8)=0,x8=0；,递推方程：fk(xk)=minvk(xk ,dk)+fk+1(xk+1) dkDk(xk) =minckdk+fk+1(xk-rk+dk) dkDk(xk),对于k=7 因为 x8=0 递推方程为 f7(x7)=minc7d7+f8(x8)=0 d7=0,对于k=6因为d7=0，所以x7=r7=4而x6-r6+d6=x7=4因此有d6=x7+r6-x6=4+7-x6=11-

12、x6也是唯一的决策。因此递推方程为：f6(x6)=minc6d6+f7(x7) d6=11-x6=10d6=10(11-x6)=110-10 x6,对于k=5 f5(x5)=minc5d5+f6(x6) d5D5(x5) =min20d5+110-10 x6 d5D5(x5) =min20d5+110-10(x5-r5+d5) d5D5(x5) =min20d5+110-10(x5-2+d5) d5D5(x5) =min10d5-10 x5+130 d5D5(x5) D5(x5) =d5| d50, r6x5-r5+d5H =d5|d50, r6+r5-x5d5H+r5-x5 =d5| d50

13、, 9-x5d511-x5,因为x5H=9，因此9-x50，决策允许集合可以简化为 D5(x5)=d5| 9-x5d511-x5递推方程成为f5(x5)=min10d5-10 x5+130 9-x5d511-x5 =10(9-x5)-10 x5+130 =220-20 x5 d5*=9-x5,对于k=4f4(x4)=minc4d4+f5(x5) d4D4(x4) =min17d4+220-20 x5 d4D4(x4) =min17d4+220-20(x4-r4+d4) d4D4(x4) =min17d4+220-20(x4-3+d4) d4D4(x4) =min-3d4-20 x4+280 d

14、4D4(x4),D4(x4)=d4| d40, r5x4-r4+d4H=d4| d40, r5+r4-x4d4H+r4-x4=d4| d40, 5-x4d412-x4=d4| max0,5-x4d412-x4,由于 在f4(x4)的表达式中d4的系数是-3， 因此d4在决策允许集合中应取集合中的 最大值，即d4=12-x4 由此 f4(x4)=-3(12-x4)-20 x4+280 =-17x4+244,对于k=3f3(x3)=min c3d3+f4(x4)d3D3(x3)=min 13d3+244-17x4 d3D3(x3) =min 13d3+244-17(x3-r3+d3) d3D3(x

15、3) =min -4d3-17x3+329 d3D3(x3) D3(x3)=d3| d30,r4x3-r3+d3H=d3| d30,r4+r3-x3d3H+r3-x3=d3| d30,8-x3d314-x3=d3| max0,8-x3d314-x3由此 f3(x3)=-4(14-x3)-17x3+329 =-13x3+273, d3*=14-x3,对于k=2f2(x2)=minc2d2+f3(x3) d2D2(x2) =min18d2+273-13x3 d2D2(x2) =min18d2+273-13(x2-r2+d2) d2D2(x2) =min18d2+273-13(x2-8+d2) d2D2(x2) =min5d2-13x2+377 d2D2(x2) D2(x2)=d2|d20,r3x2-r2+d2H =d2|d20,r3+r2-x2d2H+r2-x2 =d2|d20,13-x2d217-x2,因为 13-x20所以 d2(x2)=d2|13-x2d217-x2由此 f2(x2)=5(13-x2)-13x2+377 =-18x2+442, d2*=13-x2,对于k=1f1(x1)=minc1d1+f2(x2) d1D1(x1) =min11d1+442-18x2 d1D1(x1)