动态规划的应用ppt课件

动态规划（二）动态规划的典型应用,吴海佳勤务指挥系部队管理教研室,军事案例（装备分配问题）：某部有4具先进装备分配给下属A、B、C三个作战单位，各作战单位得到此种装备后，所增加的战斗力见下表。问怎样分配，才能使增加的战斗力最大。,一、资源分配问题,多阶段决策模型：把这个分配问题看成三个阶段的过程，每分配一个单位作为一个阶段。,状态转移函数：,阶段指标：,基本迭代方程：,边界条件：,sk+1=sk-xk,一、资源分配问题,状态变量sk：,决策变量xk：,f4(s4)=0,rk(sk,xk)可从表中读出,第k阶段初始时未分配的装备数量,第k阶段分配给第k个单位的装备数量,一、资源分配问题,一、资源分配问题,一、资源分配问题,最优分配方案: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种物品的件数,二、背包问题,决策允许集合：,xk|0xksk/wk,xk为整数,军事案例（飞机装载问题）：某架飞机可装运三种物品，各种物品一件重量分别为3、5、4吨,装运收益每件分别为4、5、6万元。如果飞机总装运量不能超过12吨，问每种物品应各装几件使收益最大。,二、背包问题,二、背包问题,状态转移函数：,阶段指标：,基本迭代方程：,边界条件：,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种物品的件数,决策允许集合：,xk|0xksk/wk,xk为整数,w1=3，w2=5，w3=4,二、背包问题,二、背包问题,二、背包问题,最优方案:,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个项目组分配高级科学家人数,决策允许集合：,xk|0xksk,xk为整数,三、系统可靠性问题,三、系统可靠性问题,三、系统可靠性问题,三、系统可靠性问题,x1=1,s2=1,x2=0,s3=1,s1=2,x3=1,s4=0,最优方案:,动态规划的最优化原理和思想。哪些问题可以用动态规划方法解决。动态规划解决问题的一般流程。,总结,思考和习题,习题1：某公司有资金400万元，向A，B，C三个项目追加投资，三个项目可以有不同的投资额度，效益值如下表所示（投资额单位百万，效益值单位万），问如何分配资金，才使总效益值最大？,思考和习题,习题2：某工厂生产三种产品，各种产品的重量与利润关系如下表所示，现将三种产品运往市场出售，运输能力总量