动态规划动态规划（二）动态规划的典型应用（二）动态规划的典型应用军事案例（装备分配问题）：军事案例（装备分配问题）：某部有某部有4具先进装备分配给下属具先进装备分配给下属A、B、C三个作战单位，各作战单位得到此种三个作战单位，各作战单位得到此种装备后，所增加的战斗力见下表。装备后，所增加的战斗力见下表。问怎样分配，才能使增加的战斗力最大。问怎样分配，才能使增加的战斗力最大。 单位单位数量数量ABC00001151311228293034043454515558一、资源分配问题一、资源分配问题多阶段决策模型：多阶段决策模型：把这个分配问题看成三个阶段的过程，每分配一个单位作为一个阶段。把这个分配问题看成三个阶段的过程，每分配一个单位作为一个阶段。状态转移函数：状态转移函数：阶段指标：阶段指标：基本迭代方程：基本迭代方程：边界条件：边界条件：sk+1=sk-xk一、资源分配问题一、资源分配问题状态变量状态变量sk ：决策变量决策变量xk ：f4(s4)=0rk(sk,xk)可从表中读出可从表中读出 第第k阶段初始时未分配的装备数量阶段初始时未分配的装备数量第第k阶段分配给第阶段分配给第k个单位的装备数量个单位的装备数量一、资源分配问题一、资源分配问题 单位单位数量数量ABC00001151311228293034043454515558一、资源分配问题一、资源分配问题 单位单位数量数量ABC00001151311228293034043454515558一、资源分配问题一、资源分配问题 单位单位数量数量ABC00001151311228293034043454515558最优分配方案最优分配方案: 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)=0rk(sk,xk)= c ck k(x(xk k) )第第k阶段初始时背包还可以装载的重量阶段初始时背包还可以装载的重量，s1=W第第k阶段装载第阶段装载第k种物品的件数种物品的件数二、背包问题二、背包问题决策允许集合：决策允许集合：xk|0 xk sk/wk, xk为整数为整数军事案例（飞机装载问题）军事案例（飞机装载问题）：某架飞机可装运三种物品，各种物品一件重量分别为某架飞机可装运三种物品，各种物品一件重量分别为3、5、4吨吨,装运收益每件装运收益每件分别为分别为4、5、6万元。万元。如果飞机总装运量不能超过如果飞机总装运量不能超过12吨，问每种物品应各装几件使收益最大。吨，问每种物品应各装几件使收益最大。二、背包问题二、背包问题二、背包问题二、背包问题状态转移函数：状态转移函数：阶段指标：阶段指标：基本迭代方程：基本迭代方程：边界条件：边界条件：sk+1= sk-wkxk状态变量状态变量sk ：决策变量决策变量xk ：f4(s4)=0rk(sk,xk)= c ck k(x(xk k) )， r1=4=4x1 ，r2 =5=5x2，r3 =6=6x3第第k阶段初始时飞机还可以装载的重量阶段初始时飞机还可以装载的重量，s1=12第第k阶段装载第阶段装载第k种物品的件数种物品的件数决策允许集合：决策允许集合：xk|0 xk sk/wk, xk为整数为整数, w1 =3， w2 =5， w3 =4二、背包问题二、背包问题二、背包问题二、背包问题二、背包问题二、背包问题最优方案最优方案:x1=0 s2=12x2=0 s3=12s1=12x3=3 s4=0 有三个科研小组进行项目开发，失败的概率分别为有三个科研小组进行项目开发，失败的概率分别为0.4, 0.6, 0.8。为了降低三组都失。为了降低三组都失败的概率，决定给三个小组增派两名高级科学家，加入各小组后，项目失败概率如败的概率，决定给三个小组增派两名高级科学家，加入各小组后，项目失败概率如下表所示。求一种分配方案，使得三组全部失败的概率最小。下表所示。求一种分配方案，使得三组全部失败的概率最小。三、系统可靠性问题三、系统可靠性问题高级科学家高级科学家小组小组1 12 23 30 00.40.40.60.60.80.81 10.20.20.40.40.50.52 20.150.150.20.20.30.3按项目小组划分阶段，按项目小组划分阶段，k=1,2,3状态转移函数：状态转移函数：阶段指标：阶段指标：基本迭代方程：基本迭代方程：边界条件：边界条件：sk+1= sk-xk状态变量状态变量sk ：决策变量决策变量xk ：f4(s4)=?rk(sk,xk)可从表中读可从表中读第第k阶段初始时未分配的高级科学家人数阶段初始时未分配的高级科学家人数，s1=2第第k阶段为第阶段为第k个项目组分配高级科学家人数个项目组分配高级科学家人数决策允许集合：决策允许集合：xk|0 xk sk, xk为整数为整数三、系统可靠性问题三、系统可靠性问题高级科高级科学家学家小组小组1 12 23 30 00.40.40.60.60.80.81 10.20.20.40.40.50.52 20.150.150.20.20.30.3三、系统可靠性问题三、系统可靠性问题高级科高级科学家学家小组小组1 12 23 30 00.40.40.60.60.80.81 10.20.20.40.40.50.52 20.150.150.20.20.30.3三、系统可靠性问题三、系统可靠性问题高级科高级科学家学家小组小组1 12 23 30 00.40.40.60.60.80.81 10.20.20.40.40.50.52 20.150.150.20.20.30.3三、系统可靠性问题三、系统可靠性问题高级科高级科学家学家小组小组1 12 23 30 00.40.40.60.60.80.81 10.20.20.40.40.50.52 20.150.150.20.20.30.3x1=1 s2=1x2=0 s3=1s1=2x3=1 s4=0 最优方案最优方案:动态规划的最优化原理和思想。动态规划的最优化原理和思想。哪些问题可以用动态规划方法解决。哪些问题可以用动态规划方法解决。动态规划解决问题的一般流程。动态规划解决问题的一般流程。总结总结思考和习题思考和习题习题习题1 1： 某某公公司司有有资资金金400万万元元，向向A，B，C三三个个项项目目追追加加投投资资，三三个个项项目目可可以以有有不不同同的的投投资资额额度度，效效益益值值如如下下表表所所示示（投投资资额额单单位位百百万万，效效益益值值单单位位万万），问问如如何何分配资金，才使总效益值最大？分配资金，才使总效益值最大？ 投资额投资额效益值效益值项目项目01234A051597176B052617178C070768888思考和习题思考和习题习题习题2 2：某工厂生产三种产品，各种产品的重量与利润关系如下表所示，现将三种产品某工厂生产三种产品，各种产品的重量与利润关系如下表所示，现将三种产品运往市场出售，运输能力总量不超过运往市场出售，运输能力总量不超过10t，问如何安排运输使得总利润为最大？，问如何安排运输使得总利润为最大？种类种类单件重量单件重量/t单件利润单件利润/元元121002314034180思考和习题思考和习题习题习题3 3：用动态规划方法解题用动态规划方法解题 max z=8x1+7x2+5x3 2x1+x2+8x3 20 xi0, i=1,2,3