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

动态规划（二）动态规划的典型应用,吴海佳勤务指挥系部队管理教研室,军事案例（装备分配问题）：某部有4具先进装备分配给下属A、B、C三个作战单位，各作战单位得到此种装备后，所增加的战斗力见下表。问怎样分配，才能使增加的战斗力最大。,一、资源分配问题,多阶段决策模型：把这个分配问题看成三个阶段的过程，每分配一个单位作为一个阶段。,状态转移函数：,阶段指标：,基本迭代方程：,边界条件：,sk+1=sk-xk,一、资源分配问题,状态变量sk：,决策变量xk：,f4(s4)=0,rk(sk,xk)可从表中读出,第k阶段初始时未分配的装备数量,第k阶段分配给第k个单位的装备数量,fk(sk)=xkskrk(sk,xk)+fk+1(sk+1),=,一、资源分配问题,k=3:s3=0,1,2,3,4，f3(s3)=x3s3r3(s3,x3)=r3(s3,s3)f3(0)=,x3=0f3(1)=,x3=1f3(2)=,x3=2f3(3)=,x3=3f3(4)=,x3=4,k=2:s2=0,1,2,3,4，f2(s2)=x2s2r2(s2,x2)+f3(s3)=x2s2r2(s2,x2)+f3(s2x2)f2(0)=x2s2r2(0,0)+f3(0)=,x2=0f2(1)=x2s2r2(1,0)+f3(10)r2(1,1)+f3(11)=x2s21113=,x2=1f2(2)=x2s2r2(2,0)+f3(20)r2(2,1)+f3(21)r2(2,2)+f3(22)=x2s23024=,x2=0,一、资源分配问题,k=2:s2=0,1,2,3,4，f2(s2)=r2(s2,x2)+f3(s2x2)f2(0)=,x2=0f2(1)=,x2=1f2(2)=,x2=0f2(3)=x2s2r2(3,0)+f3(30)r2(3,1)+f3(31)r2(3,2)+f3(32)r2(3,3)+f3(33)=x2s24543=,x2=0f2(4)=x2s2r2(4,0)+f3(40)r2(4,1)+f3(41)r2(4,2)+f3(42)r2(4,3)+f3(43)r2(4,4)+f3(44)=x2s25858=,x2=2,一、资源分配问题,k=1:s1=4，f1(s1)=r1(s1,x1)+f2(s1x)f1(4)=x1s1r1(4,0)+f2(40)r1(4,1)+f2(41)r1(4,2)+f2(42)r1(4,3)+f2(43)r1(4,4)+f2(44)=x2s25960=,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+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|0xksk/wk,xk为整数,军事案例（飞机装载问题）：某架飞机可装运三种物品，各种物品一件重量分别为3、5、4吨,装运收益每件分别为4、5、6万元。如果飞机总装运量不能超过12吨，问每种物品应各装几件使收益最大。,解：设第k种物品装载xk件=+.+,且为整数,二、背包问题,使用动态规划方法解该优化问题：=+.+,且为整数,二、背包问题,状态转移函数：,阶段指标：,基本迭代方程：,边界条件：,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|0xksk/wk,xk为整数,w1=3，w2=5，w3=4,二、背包问题,k=3:f3(s3)=x3s3/r3(s3,x3)=x3s3/6x3s3的状态允许集合为0,1,2,12f3(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,12f2(0)=+f3()=0;f2(1)=+f3()=0;f2(2)=+f3()=0;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)=xs1/r1(s1,x1)+f2(s2)=x/4x1+f2(3x1)1=12f1(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,状态转移函数：,阶段指标：,基本迭代方程：,边界条件：,sk+1=sk-xk,状态变量sk：,决策变量xk：,f4(s4)=?,rk(sk,xk)可从表中读,第k阶段初始时未分配的高级科学家人数，s1=2,第k阶段为第k个项目组分配高级科学家人数,fk(sk)=xkskrk(sk,xk)fk+1(sk+1),=,决策允许集合：,xk|0xksk,xk为整数,三、系统可靠性问题,K=3:f3(s3)=x3s3r3(s3,x3)s3的状态集合为0,1,2f3(0)=0.8；f3(1)=0.5；f3(2)=0.3；,三、系统可靠性问题,K=2:f2(s2)=x2s2r2(s2,x2)f3(s3)=x2s2r2(s2,x2)f3(s2x2)s2的状态集合为0,1,2f2(0)=0.6.=0.48；f2(1)=.=.；f2(2)=.=.；,三、系统可靠性问题,K=1:f1(s1)=x1s1r1(s1,x1)f2(s2)=x1sr1(s1,x1)f2(s1x1)s1的状态集合为2f1(2)=.=.；,三、系统可靠性问题,x1=1,s2=1,x2=0,s3=1,s1=2,x3=1,s4=0,最优方案:,动态规划的最优化原理和思想。哪些问题可以用动态规划方法解决。动态规划解决问题的一般流程。,总结,思考和习题,习题1：某公司有资金400万元，向A，B，C三个项目追加投资，三个项目可以有不同的投资额度，效益值如下表所示（投资额单位