动态规划的应用

1、动态规划动态规划（二）动态规划的典型应用（二）动态规划的典型应用吴海佳吴海佳勤务指挥系部队管理教研室勤务指挥系部队管理教研室军事案例（装备分配问题）：军事案例（装备分配问题）：某部有某部有4具先进装备分配给下属具先进装备分配给下属A、B、C三个作战单位，各作战单位得到此种装三个作战单位，各作战单位得到此种装备后，所增加的战斗力见下表。备后，所增加的战斗力见下表。问怎样分配，才能使增加的战斗力最大。问怎样分配，才能使增加的战斗力最大。 单位数量ABC00001151311228293034043454515558一、资源分配问题一、资源分配问题多阶段决策模型：多阶段决策模型：把这个分配问题看成三

2、个阶段的过程，每分配一个单位作为一个阶段。把这个分配问题看成三个阶段的过程，每分配一个单位作为一个阶段。状态转移函数：阶段指标：基本迭代方程：边界条件：sk+1=sk-xk一、资源分配问题一、资源分配问题状态变量sk ：决策变量xk ：f4(s4)=0rk(sk,xk)可从表中读出可从表中读出 第k阶段初始时未分配的装备数量第k阶段分配给第k个单位的装备数量 一、资源分配问题一、资源分配问题 单位数量ABC00001151311228293034043454515558 一、资源分配问题一、资源分配问题 单位数量ABC00001151311228293034043454515558 一、资源分

3、配问题一、资源分配问题 单位数量ABC00001151311228293034043454515558 最优分配方案: x1=1, x2=0, x3=3二、背包问题二、背包问题背包问题：背包问题：背包问题是动态规划的又一类典型问题。背包问题是动态规划的又一类典型问题。背包能装载物品的重量限度为背包能装载物品的重量限度为W公斤，设有公斤，设有n类物品可供装入背包中，已知第类物品可供装入背包中，已知第i种物品单重为种物品单重为wi公斤，价值为装载数量公斤，价值为装载数量xi的函数的函数ci(xi)。问应如何装载物品（各。问应如何装载物品（各几件），使总价值最大。几件），使总价值最大。建立数学模型：

4、建立数学模型：设第设第i种物品取种物品取xi件（件（i=1,2,n，xi为非负整数为非负整数)，背包中物品的价值，背包中物品的价值为为f，则，则 ：1max()niiifc x1niiiw xWxi0 且为整数，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阶段初始时背包还可以装载的重

5、量，s1=W第k阶段装载第k种物品的件数 二、背包问题二、背包问题决策允许集合：xk|0 xk sk/wk, xk为整数为整数军事案例（飞机装载问题）军事案例（飞机装载问题）：某架飞机可装运三种物品，各种物品一件重量分别为某架飞机可装运三种物品，各种物品一件重量分别为3、5、4吨吨,装运收益每件分装运收益每件分别为别为4、5、6万元。万元。如果飞机总装运量不能超过如果飞机总装运量不能超过12吨，问每种物品应各装几件使收益最大。吨，问每种物品应各装几件使收益最大。 二、背包问题二、背包问题 二、背包问题二、背包问题状态转移函数：阶段指标：基本迭代方程：边界条件：sk+1= sk-wkxk状态变量

6、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,

7、0.8。为了降低三组都失败。为了降低三组都失败的概率，决定给三个小组增派两名高级科学家，加入各小组后，项目失败概率如下的概率，决定给三个小组增派两名高级科学家，加入各小组后，项目失败概率如下表所示。求一种分配方案，使得三组全部失败的概率最小。表所示。求一种分配方案，使得三组全部失败的概率最小。三、系统可靠性问题三、系统可靠性问题高级科学家小组12300.40.60.810.20.40.520.150.20.3按项目小组划分阶段，按项目小组划分阶段，k=1,2,3状态转移函数：阶段指标：基本迭代方程：边界条件：sk+1= sk-xk状态变量sk ：决策变量xk ：f4(s4)=?rk(sk,xk

8、)可从表中读可从表中读第k阶段初始时未分配的高级科学家人数，s1=2第k阶段为第k个项目组分配高级科学家人数 决策允许集合：xk|0 xk sk, xk为整数为整数三、系统可靠性问题三、系统可靠性问题高级科学家小组12300.40.60.810.20.40.520.150.20.3 三、系统可靠性问题三、系统可靠性问题高级科学家小组12300.40.60.810.20.40.520.150.20.3 三、系统可靠性问题三、系统可靠性问题高级科学家小组12300.40.60.810.20.40.520.150.20.3 三、系统可靠性问题三、系统可靠性问题高级科学家小组12300.40.60.8

9、10.20.40.520.150.20.3x1=1 s2=1x2=0 s3=1s1=2x3=1 s4=0 最优方案:动态规划的最优化原理和思想。动态规划的最优化原理和思想。哪些问题可以用动态规划方法解决。哪些问题可以用动态规划方法解决。动态规划解决问题的一般流程。动态规划解决问题的一般流程。总结总结思考和习题思考和习题习题习题1 1： 某公司有资金某公司有资金400万元，向万元，向A，B，C三个项目追加投资，三个项目可以有不同三个项目追加投资，三个项目可以有不同的投资额度，效益值如下表所示（投资额单位百万，效益值单位万），问如何的投资额度，效益值如下表所示（投资额单位百万，效益值单位万），问如何分配资金，才使总效益值最大？分配资金，才使总效益值最大？ 投资额效益值项目01234A051597176B052617178C070768888思考和习题思考和习题习题习题2 2：某工厂生产三种产品，各种产品的重量与利润关系如下表所示，现将三种产品某工厂生产三种产品，各种产品的重量与利润关系如下表所示，现将三种产品运往市场出售，运输能力总量不超过运往市场出售，运输能力总量不超过10t，问如何安排运输使得总利润为最大？，问如何安排运