动态规划的基本原理和基本应用.ppt

1 第9章动态规划的基本原理和基本应用 2 动态规划是解决多阶段决策过程最优化问题的一种方法 由美国数学家贝尔曼 Bellman 等人在20世纪50年代提出 他们针对多阶段决策问题的特点 提出了解决这类问题的 最优化原理 并成功地解决了生产管理 工程技术等方面的许多实际问题 3 动态规划是现代企业管理中的一种重要决策方法 可用于最优路径问题 资源分配问题 生产计划和库存问题 投资问题 装载问题 排序问题及生产过程的最优控制等 4 9 1多阶段决策过程最优化问题举例多阶段决策过程最优化多阶段决策过程是指这样一类特殊的活动过程 他们可以按时间顺序分解成若干相互联系的阶段 在每个阶段都要做出决策 全部过程的决策是一个决策序列 所以多阶段决策问题也称为序贯决策问题 5 例1多阶段资源分配问题 设有数量为x的某种资源 将它投入两种生产方式A和B中 以数量y投入生产方式A 剩下的量投入生产方式B 则可得到收入g y h x y 其中g y 和h y 是已知函数 并且g 0 h 0 0 同时假设以y与x y分别投入两种生产方式A B后可以回收再生产 回收率分别为a与b 试求进行n个阶段后的最大总收入 6 若以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个阶段的总收入最大 例1 7 因此 我们的问题就变成 求y y1 y2 yn 1 以使g y h x y g y1 h x1 y1 g yn 1 h xn 1 yn 1 达到最大 且满足条件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 例1 8 例2生产和存储控制问题 某工厂生产某种季节性商品 需要作下一年度的生产计划 假定这种商品的生产周期需要两个月 全年共有6个生产周期 需要作出各个周期中的生产计划 设已知各周期对该商品的需要量如下表所示 9 例2 假设这个工厂根据需要可以日夜两班生产或只是日班生产 当开足日班时 每一个生产周期能生产商品15个单位 每生产一个单位商品的成本为100元 当开足夜班时 每一生产周期能生产的商品也是15个 但是由于增加了辅助性生产设备和生产辅助费用 每生产一单位商品的成本为120元 由于生产能力的限制 可以在需求淡季多生产一些商品储存起来以备需求旺季使用 但存储商品是需要存储费用的 假设每单位商品存储一周期需要16元 已知开始时存储为零 年终也不存储商品备下年使用 问应该如何作生产和存储计划 才能使总的生产和存储费用最小 10 例2 设第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 为最小 其中 11 例3运输网络问题 如图1所示的运输网络 点间连线上的数字表示两地距离 也可是运费 时间等 要求从v1至v10的最短路线 这种运输网络问题也是静态决策问题 但是 按照网络中点的分布 可以把它分为4个阶段 而作为多阶段决策问题来研究 12 图1运输网络图示 13 动态规划方法导引为了说明动态规划的基本思想方法和特点 下面以图1所示为例讨论求最短路问题的方法 第一种方法称做全枚举法或穷举法 它的基本思想是列举出所有可能发生的方案和结果 再对它们一一进行比较 求出最优方案 这里从v1到v10的路程可以分为4个阶段 第一二段的走法有三种 第三段的走法有两种 第四段的走法仅一种 因此共有3 3 2 1 18条可能的路线 54次加法算出各条路线的距离 最后进行17次两两比较 可知最优路线是v1 v2 v5 v8 v10 最短距离是27 14 显然 当组成交通网络的节点很多时 用穷举法求最优路线的计算工作量将会十分庞大 而且其中包含着许多重复计算 第二种方法即所谓 局部最优路径 法 是说某人从k出发 他并不顾及全线是否最短 只是选择当前最短途径 逢近便走 错误地以为局部最优会致整体最优 在这种想法指导下 所取决策必是v1 v2 v5 v9 v10 全程长度是30 显然 这种方法的结果常是错误的 15 第三种方法是动态规划方法 动态规划方法寻求该最短路问题的基本思想是 首先将问题划分为4个阶段 每次的选择总是综合后继过程的一并最优进行考虑 在各段所有可能状态的最优后继过程都已求得的情况下 全程的最优路线便也随之得到 为了找出所有可能状态的最优后继过程 动态规划方法是从过程的最后阶段开始考虑 然后逆着实际过程发展的顺序 逐段向前递推计算直至始点 16 具体说 此问题先从v10开始 因为v10是终点 再无后继过程 故可以接着考虑第4阶段上所有可能状态v8 v9的最优后续过程 因为从v8 v9到v10的路线是唯一的 所以v8 v9的最优决策和最优后继过程就是到v10 它们的最短距离分别是10和14 接着考虑阶段3上可能的状态v5 v6 v7到v10的最优决策和最优后继过程 在状态V5上 虽然到v8是6 到v9是5 但是 10 14 17 综合考虑后继过程整体最优 取最优决策是到v8 最优后继过程是v5 v8 v10 最短距离是16 同理 状态v6的最优决策是至v8 v7的最优决策是到v9 同样 当阶段3上所有可能状态的最优后继过程都已求得后 便可以开始考虑阶段2上所有可能状态的最优决策和最优后继过程 如v2的最优决策是到v5 最优路线是 10 14 16 15 17 18 v2 v5 v8 v10 最短距离是22 依此类推 最后可以得到从初始状态v1的最优决策是到v2最优路线是v1 v2 v5 v8 v10 全程的最短距离是27 图1中红线表示最优路线 每点上圆括号内的数字表示该点到终点的最短路距离 10 14 16 15 17 22 22 21 27 19 综上所述可见 全枚举法虽可找出最优方案 但不是个好算法 局部最优法则完全是个错误方法 只有动态规划方法属较科学有效的算法 它的基本思想是 把一个比较复杂的问题分解为一系列同类型的更易求解的子问题 便于应用计算机 整个求解过程分为两个阶段 先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值 然后再顺序地求出整个问题的最优策略和最优路线 计算过程中 系统地删去了所有中间非最优的方案组合 从而使计算工作量比穷举法大为减少 20 拾火柴游戏 桌子上放30根火柴 每人一次可拾起1 3根 谁拾起最后一根火柴谁输 如果你先选择 如何保证你能赢得游戏 29 25 21 17 13 9 5 1 动态规划与倒推求解 21 动态规划是解决多阶段决策问题的一种方法 所谓多阶段 决策问题是指这样的决策问题 其过程可分为若干个相互联 系的阶段 每一阶段都对应着一组可供选择的决策 每一决 策的选定即依赖于当前面临的状态 又影响以后总体的效果 A B C D E 状态A 状态B 状态C 状态D 状态E 状态F 决策A 决策D 决策E 当每一阶段的决策选定以后 就构成一个决策序列 称为一个 决策B 决策C 策略 它对应着一个确定的效果 多阶段决策问题就是寻找使 此效果最好的策略 22 动态规划问题实例 例给定一个线路网络 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 要从A向F铺设一条输油管道 各点间连线上的数字表示距离 问应选择什么路线 可使总 距离最短 23 9 2动态规划的基本概念和基本原理 一 基本概念 阶段 是指问题需要做出决策的步数 阶段总数常记为n 相应的是n个阶段的决策问题 阶段的序号常记为k 称为阶段变量 k 1 2 n k即可以是顺序编号也可以是逆序编号 常用顺序编号 全过程 后部子过程 状态 各阶段开始时的客观条件 第k阶段的状态常用状态变量表示 状态变量取值的集合称为状态集合 用表示 例如 例中 24 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 第1阶段 第2阶段 第3阶段 第4阶段 第5阶段 状态1 状态2 状态3 状态4 状态5 状态6 25 决策 是指从某阶段的某个状态出发 在若干个不同方案中 做出的选择 表示决策的变量 称为决策变量 用表示 例如 表示走到3阶段 当处于C2路口时 下一步奔D1 时的允许决策集合记为 例如 策略 全过程策略p1n 子策略pkn 最优策略 状态转移方程 是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律 用 表示 决策变量允许的取值范围称为允许决策集合 第k阶段状态为 26 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 第1阶段 第2阶段 第3阶段 第4阶段 第5阶段 状态1 状态2 状态3 状态4 状态5 状态6 27 指标函数 分阶段指标函数和过程指标函数 阶段指标函数 是指第k阶段从状态出发 采取决策时的效益 用 表示 而过程指标函数指从第k阶段的某状态出发 采取子策略 时所得到的阶段效益之和 最优指标函数 表示从第k阶段状态为时采用最佳策略 到过程终止时的最佳效益 记为 28 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 第1阶段 第2阶段 第3阶段 第4阶段 第5阶段 状态1 状态2 状态3 状态4 状态5 状态6 29 其中opt可根据具体情况取max或min 基本方程 此为逐段递推求和的依据 一般为 式中opt可根据题意取max或min 例如 例的基本方程为 30 即确定各个变量及方程函数1 阶段变量2 状态变量 选择时要满足两个条件 能正确描述受控过程的演变特性 要满足无后效性无后效性 给定了某阶段状态 在这阶段以后过程的发展不受这阶段以前各阶段状态的影响 3 决策变量4 列出状态转移方程5 指标函数 二 模型的构成 因素 31 三 最优化原理 最优策略的任一后部子策略都是最优的 无论以前状态决策如何 从眼下直到最后的诸决策必构成最优子策略 动态规划应用举例 例1最短路线问题 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 32 逆序递推方程 1 k 5时 状态 它们到F点的距离即为 最短路 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 33 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 2 k 4时 状态 它们到F点需经过中途 点E 需一一分析从E到F的最短路 先说从D1到F的最短路 有两种选择 经过E1 E2 比较最短 34 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 这说明由D1到F的最短距离为7 其路径为 相应的决策为 35 这说明由D2到F的最短距离为5 其路径为 相应的决策为 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 36 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 即D3到F的最短距离为5 其路径为 相应的决策为 37 3 k 3时 状态 这说明由C1到F的最短距离为12 相应的决策为 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 38 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 即由C2到F的最短距离为10 相应的决策为 39 即由C3到F的最短距离为8 相应的决策为 即由C4到F的最短距离为9 相应的决策为 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 40 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 4 k 2时 状态 这说明由B1到F的最短距离为13 相应的决策为 41 即由B2到F的最短距离为15 相应的决策为 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 42 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 5 k 1时 只有一个状态点A 则 即由A到F的最短距离为17 相应的决策为 43 所以最优路线为 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 再按计算顺序反推可得最优决策序列 44 顺序递推方程 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 例1 1阶段 2阶段 3阶段 4阶段 5阶段 行走方向 第k阶段 45 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 K 1时 注意到 所以 46 K 2时 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 47 K 3时 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 48 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 或 类似地 可算出 49 最优策略 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 或 50 最短路径 最短路长 注 顺序解法与逆序解法无本质区别 一般来说 当初始状态给定时用逆序解法 当终止状态给定时用顺序解法 若问题给定了一个初始状态与一个终止状态 则两种方法均可使用 51 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 4 F 3 F 5 E1 5 E2 7 E1 12 D1 10 D2 8 D2 9 D3 13 C2 15 C3 17 B1 作业 P2355 2 双标号法 顺序逆序选一 52 9 3背包问题 一般的提法为 一旅行者携带背包去登山 已知他所能承受的背包重量的极限为a 千克 现有n种物品可供他选择装入背包 第i种物品的单位重量为 千克 其价值 可以是表明本物品对登山者的重要性指标 是携带数量的函数 i 1 2 n 问旅行者应如何选择携带物品的件数 以使总价值最大 此模型解决的是运输工具包括卫星的最优装载问题 其数学模型为 53 设为第i种