动态规划的应用

动态规划 二 动态规划的典型应用 吴海佳勤务指挥系部队管理教研室 军事案例 装备分配问题 某部有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 则 xi 0且为整数 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 0 xk sk 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 0 xk sk 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 0 xk sk xk为整数 三 系统可靠性问题 三 系统可靠性问题 三 系统可靠性问题 三 系统可靠性问题 x1 1 s2 1 x2 0 s3 1 s1 2 x3 1 s4 0 最优方案 动态规划的最优化原理和思想 哪些问题可以用动态规划方法解决 动态规划解决问题的一般流程 总结 思考和习题 习题1 某公司有资金400万元 向A B C三个项目追加投资 三个项目可以有不同的投资额度 效益值如下表所示 投资额单位百万 效益值单位万 问如何分配资金 才使总效益值最大 思考和习题 习题2 某工厂生产三种产品 各种产品的重量与利润关系如下表所示 现将三种产品运往市场出售 运输能力总量不超过10t 问如何安排运输使得总利润为最大 思考和习题 习题3 用