《《精编》适合全国高校考研与期末考试资料》由会员分享，可在线阅读，更多相关《《精编》适合全国高校考研与期末考试资料（109页珍藏版）》请在金锄头文库上搜索。
1、运筹学课件 DynamicProgramming 综述 动态规划所研究的对象是多阶段决策问题 所谓多阶段决策问题是指一类活动过程 它可以分为若干个相互联系的阶段 在每个阶段都需要作出决策 这个决策不仅决定这一阶段的效益 而且决定下一阶段的初始状态 每个阶段的决策确定以后 就得到一个决策序列 称为策略 多阶段决策问题就是求一个策略 使各阶段的效益的总和达到最优 实际问题举例 多阶段决策问题及实例例1例2 多阶段资源分配回收利用问题 设有数量为x的某种资源 将它投入两种生产方式A和B中 以数量y投入生产方式A 剩下的量投入生产方式B 则可得到收入g y h x y 其中g y 和h y 是已知函数
2、 并且g 0 h 0 0 同时假设以y与x y分别投入两种生产方式A B后可以回收再生产 回收率分别为a与b 试求进行n个阶段后的最大总收入 续 1 若以y与x y分别投入生产方式A与B 在第一阶段生产后回收的总资源为x1 ay b x y 再将x1投入生产方式A和B 则可得到收入g y1 h x1 y1 继续回收资源x2 ay1 b x1 y1 若上面的过程进行n个阶段 我们希望选择n个变量y y1 y2 yn 1 使这n个阶段的总收入最大 因此 我们的问题就变成 求y y1 y2 yn 1 以使g y h x y g y1 h x1 y1 g yn 1 h xn 1 yn 1 达到最大 且
3、满足条件x1 ay b x y x2 ay1 b x1 y1 xn 1 ayn 2 b xn 2 yn 2 yi与xi均非负 i 1 2 n 1 续 2 生产和存储控制问题 某工厂生产某种季节性商品 需要作下一年度的生产计划 假定这种商品的生产周期需要两个月 全年共有6个生产周期 需要作出各个周期中的生产计划 设已知各周期对该商品的需要量如下表所示 续 1 续 2 假设这个工厂根据需要可以日夜两班生产或只是日班生产 当开足日班时 每一个生产周期能生产商品15个单位 每生产一个单位商品的成本为100元 当开足夜班时 每一生产周期能生产的商品也是15个 但是由于增加了辅助性生产设备和生产辅助费用
4、每生产一单位商品的成本为120元 由于生产能力的限制 可以在需求淡季多生产一些商品储存起来以备需求旺季使用 但存储商品是需要存储费用的 假设每单位商品存储一周期需要16元 已知开始时存储为零 年终也不存储商品备下年使用 问应该如何作生产和存储计划 才能使总的生产和存储费用最小 续 3 设第i个周期的生产量为xi 周期末的存储量为ui 那么这个问题用式子写出来就是 求x1 x2 x6 满足条件 x1 5 u1x2 u1 5 u2x3 u2 10 u3x4 u3 30 u4x5 u4 50 u5x6 u5 80 xi30 0uj i 1 2 6 j 1 2 5使S 为最小 其中 续 4 动态规划的
5、基本概念与模型 最优化原理 动态规划的数学模型 第二节离散确定性动态规划模型的求解 s1 12 s5 12 动态规划应用 资源分配问题最短路径问题旅行售货员问题生产经营问题排序 求对三个项目的最优投资分配 使总投资效益最大 资源分配问题 有资金4万元 投资A B C三个项目 每个项目的投资效益与投入该项目的资金有关 三个项目A B C的投资效益 万吨 和投入资金 万元 关系见下表 阶段k 每投资一个项目作为一个阶段 状态变量xk 投资第k个项目前的资金数 决策变量dk 第k个项目的投资 决策允许集合 0 dk xk状态转移方程 xk 1 xk dk阶段指标 vk xk dk 见表中所示 递推方
6、程 fk xk max vk xk dk fk 1 xk 1 终端条件 f4 x4 0 k 4 f4 x4 0k 3 0 d3 x3 x4 x3 d3 k 2 0 d2 x2 x3 x2 d2 k 1 0 d1 x1 x2 x1 d1 最短路径问题 求从A到E的最短路径 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f5 E 0 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D1
7、 5 f5 E 0 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f4 D1 5 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C1 8 f4 D1 5 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2
8、f5 E 0 f3 C2 7 f4 D1 5 f3 C1 8 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f3 C1 8 f3 C2 7 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B1 20 f3 C2 7 f3 C1 8 2 5 1 12 14
9、10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B2 14 f3 C2 7 f3 C1 8 f2 B1 21 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f2 B1 21 f2 B2 14 2 5 1 12 14 10 6 10
10、 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f1 A 19 f2 B2 14 f2 B1 21 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f1 A 19 f2 B2 14 f2 B1 21 状
11、态最优决策状态最优决策状态最优决策状态最优决策状态 A A B2 B2 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f1 A 19 f2 B2 14 f2 B1 21 状态最优决策状态最优决策状态最优决策状态最优决策状态 A A B2 B2 B2 C1 C1 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A
12、B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f1 A 19 f2 B2 14 f2 B1 21 状态最优决策状态最优决策状态最优决策状态最优决策状态 A A B2 B2 B2 C1 C1 C1 D1 D1 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f1 A 19 f2 B
13、2 14 f2 B1 21 状态最优决策状态最优决策状态最优决策状态最优决策状态 A A B2 B2 B2 C1 C1 C1 D1 D1 D1 E E从A到E的最短路径为19 路线为A B2 C1 D1 E 生产库存问题 例 一个工厂生产某种产品 1 7月份生产成本和产品需求量的变化情况如下表 阶段k 月份 k 1 2 7 8 状态变量xk 第k个月初 发货以前 的库存量 决策变量dk 第k个月的生产量 状态转移方程 xk 1 xk rk dk 决策允许集合 Dk xk dk dk 0 rk 1 xk 1 H dk dk 0 rk 1 xk rk dk H 阶段指标 vk xk dk ckdk
14、 终端条件 f8 x8 0 x8 0 递推方程 fk xk min vk xk dk fk 1 xk 1 dk Dk xk min ckdk fk 1 xk rk dk dk Dk xk 对于k 7因为x8 0递推方程为f7 x7 min c7d7 f8 x8 0d7 0 对于k 6因为d7 0 所以x7 r7 4而x6 r6 d6 x7 4因此有d6 x7 r6 x6 4 7 x6 11 x6也是唯一的决策 因此递推方程为 f6 x6 min c6d6 f7 x7 d6 11 x6 10d6 10 11 x6 110 10 x6 对于k 5f5 x5 min c5d5 f6 x6 d5 D5
15、 x5 min 20d5 110 10 x6 d5 D5 x5 min 20d5 110 10 x5 r5 d5 d5 D5 x5 min 20d5 110 10 x5 2 d5 d5 D5 x5 min 10d5 10 x5 130 d5 D5 x5 D5 x5 d5 d5 0 r6 x5 r5 d5 H d5 d5 0 r6 r5 x5 d5 H r5 x5 d5 d5 0 9 x5 d5 11 x5 因为x5 H 9 因此9 x5 0 决策允许集合可以简化为D5 x5 d5 9 x5 d5 11 x5 递推方程成为f5 x5 min 10d5 10 x5 130 9 x5 d5 11 x
16、5 10 9 x5 10 x5 130 220 20 x5d5 9 x5 对于k 4f4 x4 min c4d4 f5 x5 d4 D4 x4 min 17d4 220 20 x5 d4 D4 x4 min 17d4 220 20 x4 r4 d4 d4 D4 x4 min 17d4 220 20 x4 3 d4 d4 D4 x4 min 3d4 20 x4 280 d4 D4 x4 D4 x4 d4 d4 0 r5 x4 r4 d4 H d4 d4 0 r5 r4 x4 d4 H r4 x4 d4 d4 0 5 x4 d4 12 x4 d4 max 0 5 x4 d4 12 x4 由于在f4 x4 的表达式中d4的系数是 3 因此d4在决策允许集合中应取集合中的最大值 即d4 12 x4由此f4 x4 3 12 x4 20 x4 280 17x4 244 对于k 3f3 x3 min c3d3 f4 x4 d3 D3 x3 min 13d3 244 17x4 d3 D3 x3 min 13d3 244 17 x3 r3 d3 d3 D3 x3 min 4d3 17x3 329 d3
