14 动态规划的应用ppt课件.ppt

1、动态规划（二）动态规划的典型应用,吴海佳 勤务指挥系部队管理教研室,军事案例（装备分配问题）： 某部有4具先进装备分配给下属A、B、C三个作战单位，各作战单位得到此种装备后，所增加的战斗力见下表。 问怎样分配，才能使增加的战斗力最大。,一、资源分配问题,多阶段决策模型： 把这个分配问题看成三个阶段的过程，每分配一个单位作为一个阶段。,状态转移函数：,阶段指标：,基本迭代方程：,边界条件：,sk+1=sk-xk,一、资源分配问题,状态变量sk ：,决策变量xk ：,f4(s4)=0,rk(sk,xk)可从表中读出,第k阶段初始时未分配的装备数量,第k阶段分配给第k个单位的装备数量,fk(sk)=

2、 xksk rk (sk, xk) +fk+1(sk+1) ,=,一、资源分配问题,k=3: s3=0,1,2,3,4， f3(s3)= x3s3 r3 (s3, x3) =r3 (s3, s3) f3(0)=, x3=0 f3(1)= , x3=1 f3(2)= , x3=2 f3(3)= , x3=3 f3(4)= , x3=4,k=2: s2=0,1,2,3,4， f2(s2)= x2s2 r2 (s2, x2)+f3(s3) = x2s2 r2 (s2, x2)+f3(s2x2) f2(0)= x2s2 r2 (0, 0)+f3(0) =, x2=0 f2(1)= x2s2 r2 (1

3、, 0)+f3(10) r2 (1, 1)+f3(11) = x2s2 11 13 =, x2=1 f2(2)= x2s2 r2 (2, 0)+f3(20) r2 (2, 1)+f3(21) r2 (2, 2)+f3(22) = x2s2 30 24 =, x2=0,一、资源分配问题,k=2: s2=0,1,2,3,4， f2(s2)= r2 (s2, x2)+f3(s2x2) f2(0)=, x2=0 f2(1)=, x2=1 f2(2)=, x2=0 f2(3)= x2s2 r2 (3, 0)+f3(30) r2 (3, 1)+f3(31) r2 (3, 2)+f3(32) r2 (3,

4、3)+f3(33) = x2s2 45 43 =, x2=0 f2(4)= x2s2 r2 (4, 0)+f3(40) r2 (4, 1)+f3(41) r2 (4, 2)+f3(42) r2 (4, 3)+f3(43) r2 (4, 4)+f3(44) = x2s2 58 58 =, x2=2,一、资源分配问题,k=1: s1=4， f1(s1)= r1 (s1, x1)+f2(s1x) f1(4)= x1s1 r1 (4, 0)+f2(40) r1 (4, 1)+f2(41) r1 (4, 2)+f2(42) r1 (4, 3)+f2(43) r1 (4, 4)+f2(44) = x2s2

5、 59 60 =, x1=1,最优分配方案: x1=1, x2=0, x3=3,二、背包问题,背包问题： 背包问题是动态规划的又一类典型问题。 背包能装载物品的重量限度为W公斤，设有n类物品可供装入背包中，已知第i种物品单重为wi公斤，价值为装载数量xi的函数ci(xi)。问应如何装载物品（各几件），使总价值最大。,建立数学模型：设第i种物品取xi件（i=1,2,n，xi为非负整数)，背包中物品的价值为f，则 ：,xi0 且为整数，i=1,2 ,n,二、背包问题,多阶段决策模型： 把背包装载问题按可装入物品的几种类型划分为n个阶段。,状态转移函数：,阶段指标：,基本迭代方程：,边界条件：,sk

6、+1= sk-wkxk,状态变量sk ：,决策变量xk ：,fn+1(sn+1)=0,rk(sk,xk)= ck(xk),第k阶段初始时背包还可以装载的重量，s1=W,第k阶段装载第k种物品的件数,fk(sk)= xksk/ rk (sk, xk) +fk+1(sk+1) ,=,二、背包问题,决策允许集合：,xk|0 xksk/wk, xk为整数,军事案例（飞机装载问题）： 某架飞机可装运三种物品，各种物品一件重量分别为3、5、4吨,装运收益每件分别为4、5、6万元。 如果飞机总装运量不能超过12吨，问每种物品应各装几件使收益最大。,解：设第k种物品装载xk件 = + + . + + , ,

7、,且为整数,二、背包问题,使用动态规划方法解该优化问题： = + + . + + , , ,且为整数,二、背包问题,状态转移函数：,阶段指标：,基本迭代方程：,边界条件：,sk+1= sk-wkxk,状态变量sk ：,决策变量xk ：,f4(s4)=0,rk(sk,xk)= ck(xk)， r1=4x1 ，r2 =5x2，r3 =6x3,第k阶段初始时飞机还可以装载的重量，s1=12,第k阶段装载第k种物品的件数,fk(sk)= xksk/ rk (sk, xk) +fk+1(sk+1) ,=,决策允许集合：,xk|0 xksk/wk, xk为整数, w1 =3， w2 =5， w3 =4,二

8、、背包问题,k=3: f3(s3)= x3s3/ r3 (s3, x3) = x3s3/ 6x3 s3的状态允许集合为0,1,2,12 f3(0)=; f3(1)=; f3(2)=; f3(3)=; f3(4)=; f3(5)=; f3(6)=; f3(7)=; f3(8)=; f3(9)=; f3(10)=; f3(11)=; f3(12)=,二、背包问题,k=2: f2(s2)= xs2/ r2 (s2, x2)+f3(s3) = xs2/ 5x2+f3(s5x2) s2的状态允许集合为0,1,2,12 f2(0)=+f3()=0; f2(1)=+f3()=0; f2(2)=+f3()=0

9、; f2(3)=+f3()=0; f2(4)=+f3()=6; f2(5)= +f3()=6 +f3()= =; f2(6)= +f3()=6 +f3()= =; f2(7)= +f3()=6 +f3()= =;,f2(8)= +f3()=12 +f3()= =; f2(9)= +f3()=12 +f3()=11 =; f2(10)= +f3()=12 +f3(5)=11 +f3(0)=10 =; f2(11)= +f3(11)=12 +f3(6)=11 +f3(1)=10 =; f2(12)= +f3()=18 +f3(7)=11 +f3(2)=10 =;,二、背包问题,k=1: f1(s1

10、)= xs1/ r1 (s1, x1)+f2(s2) = x/ 4x1+f2(3x1) 1=12 f1(12)= +f2()=18 +f2(9)=16 +f2(6)=14 +f2(3)=12 +f3(0)=16 =;,最优方案:,x1=0,s2=12,x2=0,s3=12,s1=12,x3=3,s4=0,有三个科研小组进行项目开发，失败的概率分别为0.4, 0.6, 0.8。为了降低三组都失败的概率，决定给三个小组增派两名高级科学家，加入各小组后，项目失败概率如下表所示。求一种分配方案，使得三组全部失败的概率最小。,三、系统可靠性问题,按项目小组划分阶段，k=1,2,3,状态转移函数：,阶段指

11、标：,基本迭代方程：,边界条件：,sk+1= sk-xk,状态变量sk ：,决策变量xk ：,f4(s4)=?,rk(sk,xk)可从表中读,第k阶段初始时未分配的高级科学家人数，s1=2,第k阶段为第k个项目组分配高级科学家人数,fk(sk)= xksk rk (sk, xk) fk+1(sk+1) ,=,决策允许集合：,xk|0 xksk, xk为整数,三、系统可靠性问题,K=3: f3(s3)= x3s3 r3 (s3, x3) s3的状态集合为0,1,2 f3(0)=0.8； f3(1)=0.5； f3(2)=0.3；,三、系统可靠性问题,K=2: f2(s2)= x2s2 r2 (s

12、2, x2)f3(s3) = x2s2 r2 (s2, x2)f3(s2x2) s2的状态集合为0,1,2 f2(0)=0.6.=0.48； f2(1)= . . =. ； f2(2)= . . . =.；,三、系统可靠性问题,K=1: f1(s1)= x1s1 r1 (s1, x1)f2(s2) = x1s r1 (s1, x1)f2(s1x1) s1的状态集合为2 f1(2)= . . . =.；,三、系统可靠性问题,x1=1,s2=1,x2=0,s3=1,s1=2,x3=1,s4=0,最优方案:,动态规划的最优化原理和思想。 哪些问题可以用动态规划方法解决。 动态规划解决问题的一般流程。,总结,思考和习题,习题1： 某公司有资金400万元，向A，B，C三个项目追加投资，三个项目可以有不同的投资额