第四章动态规划整理.ppt

《第四章动态规划整理.ppt》由会员分享，可在线阅读，更多相关《第四章动态规划整理.ppt（105页珍藏版）》请在金锄头文库上搜索。

1、2020 5 23 第5章动态规划 2020 5 23 1 多阶段决策问题多阶段决策过程 问题的活动过程分为若干相互联系的阶段 任一阶段i以后的行为仅依赖于i阶段的过程状态 而与i阶段之前的过程如何达到这种状态的方式无关 在每一个阶段都要做出决策 这一系列的决策称为多阶段决策过程 multistepdecisionprocess 最优化问题 问题的每一阶段可能有多种可供选择的决策 必须从中选择一种决策 各阶段的决策构成一个决策序列 决策序列不同 所导致的问题的结果可能不同 多阶段决策的最优化问题就是 求能够获得问题最优解的决策序列 最优决策序列 5 1一般方法 2020 5 23 2 多阶段决

2、策过程的求解策略1 枚举法 穷举可能的决策序列 从中选取可以获得最优解的决策序列2 动态规划20世纪50年代初美国数学家R E Bellman等人在研究多阶段决策过程的优化问题时 提出了著名的最优化原理 principleofoptimality 把多阶段过程转化为一系列单阶段问题 创立了解决这类过程优化问题的新方法 动态规划 动态规划 dynamicprogramming 是运筹学的一个分支 是求解决策过程 decisionprocess 最优化的数学方法 应用领域 动态规划问世以来 在经济管理 生产调度 工程技术和最优控制等方面得到了广泛的应用 例如最短路线 库存管理 资源分配 设备更新

3、排序 装载等问题 用动态规划方法比用其它方法求解更为方便 2020 5 23 3 最优性原理 PrincipleofOptimality 过程的最优决策序列具有如下性质 无论过程的初始状态和初始决策是什么 其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列 利用动态规划求解问题的前提1 证明问题满足最优性原理如果对所求解问题证明满足最优性原理 则说明用动态规划方法有可能解决该问题2 获得问题状态的递推关系式获得各阶段间的递推关系式是解决问题的关键 2020 5 23 例5 1 多段图问题 多段图G V E 是一个有向图 且具有特性 结点 结点集V被分成k 2个不相交的集合Vi 1

4、i k 其中V1和Vk分别只有一个结点s 源点 和t 汇点 每一集合Vi定义图中的一段 边 所有的边 u v 均具有如下性质 若 E 则该边将是从某段i指向i 1段 即若u Vi 则v Vi 1 1 i k 1 每条边 u v 均附有成本c u v s到t的路径 从第1段开始 至第2段 第3段 最后在第k段终止 路径的成本是这条路径上边的成本和 多段图问题 求由s到t的最小成本路径 2020 5 23 2020 5 23 多段图问题的多阶段决策过程 生成从s到t的最小成本路径是在k 2个阶段 除s和t外 进行某种决策的过程 从s开始 第i次决策决定Vi 1 1 i k 2 中的哪个结点在从s到

5、t的最短路径上 最优性原理对多段图问题成立假设s v2 v3 vk 1 t是一条由s到t的最短路径 初始状态 s 初始决策 s v2 v2 V2 初始决策产生的状态 v2则 其余的决策 v3 vk 1相对于v2将构成一个最优决策序列 最优性原理成立 反证 若不然 设v2 q3 qk 1 t是一条由v2到t的更短的路径 则s v2 q3 qk 1 t将是比s v2 v3 vk 1 t更短的从s到t的路径 与假设矛盾 故 最优性原理成立 2020 5 23 例5 2 0 1背包问题 KNAP l j X 目标函数 约束条件 0 1背包问题 KNAP 1 n M 2020 5 23 最优性原理对0

6、1背包问题成立 设y1 y2 yn是x1 x2 xn的0 1值最优序列 若y1 0 KNAP 2 n M 是初始决策产生的状态 则y2 yn相对于KNAP 2 n M 将构成一个最优序列 否则 y1 y2 yn将不是KNAP 1 n M 的最优解若y1 1 KNAP 2 n M w1 是初始决策产生的状态 则y2 yn相对于KNAP 2 n M w1 将构成一个最优序列 否则 设存在另一0 1序列z1 z2 zn 使得且则序列y1 z2 zn将是一个对于KNAP 1 n M 具有更大效益值的序列 与假设矛盾故 最优性原理成立 2020 5 23 4 动态规划模型的基本要素一个多阶段决策过程最优

7、化问题的动态规划模型通常包含以下要素 1 阶段阶段 step 是对整个过程的自然划分 通常根据时间顺序或空间特征来划分阶段 以便按阶段的次序解优化问题 阶段变量一般用k 1 2 n表示 2020 5 23 2 状态状态 state 表示每个阶段开始时过程所处的自然状况 它应该能够描述过程的特征并且具有无后向性 即当某阶段的状态给定时 这个阶段以后过程的演变与该阶段以前各阶段的状态无关 即每个状态都是过去历史的一个完整总结 通常还要求状态是直接或间接可以观测的 描述状态的变量称状态变量 statevariable 变量允许取值的范围称允许状态集合 setofadmissiblestates 用x

8、k表示第k阶段的状态变量 它可以是一个数或一个向量 用Xk表示第k阶段的允许状态集合 状态变量简称为状态 2020 5 23 3 决策当一个阶段的状态确定后 可以作出各种选择从而演变到下一阶段的某个状态 这种选择手段称为决策 decision 描述决策的变量称决策变量 decisionvariable 变量允许取值的范围称允许决策集合 setofadmissibledecisions 用uk xk 表示第k阶段处于状态xk时的决策变量 它是xk的函数 用Uk xk 表示了xk的允许决策集合 决策变量简称决策 2020 5 23 4 策略决策组成的序列称为策略 policy 由初始状态x1开始的

9、全过程的策略记作p1 n x1 即p1 n x1 u1 x1 u2 x2 un xn 由第k阶段的状态xk开始到终止状态的后部子过程的策略记作pk n xk 即pk n xk uk xk uk 1 xk 1 un xn 类似地 由第k到第j阶段的子过程的策略记作pk j xk uk xk uk 1 xk 1 uj xj 对于每一个阶段k的某一给定的状态xk 可供选择的策略pk j xk 有一定的范围 称为允许策略集合 setofadmissiblepolicies 2020 5 23 5 状态转移方程在确定性过程中 一旦某阶段的状态和决策为已知 下阶段的状态便完全确定 用状态转移方程 equa

10、tionofstate 表示这种演变规律 写作 2020 5 23 6 指标函数和最优值函数指标函数 objectivefunction 是衡量过程优劣的数量指标 它是关于策略的数量函数 从阶段k到阶段n的指标函数用Vk n xk pk n xk 表示 k 1 2 n 能够用动态规划解决的问题的指标函数应具有可分离性 即Vk n可表为xk uk Vk 1 n的函数 记为 2020 5 23 7 最优策略和最优轨线使指标函数Vk n达到最优值的策略是从k开始的后部子过程的最优策略 记作pk n uk un p1 n 又是全过程的最优策略 简称最优策略 optimalpolicy 从初始状态x1

11、x1 出发 过程按照p1 n 和状态转移方程演变所经历的状态序列 x1 x2 xn 1 称最优轨线 optimaltrajectory 2020 5 23 5 递推策略1 向前处理法列出根据xi 1 xn的最优决策序列求取xi决策值的关系式 从最后一个阶段 逐步向前递推求出各阶段的决策值 决策序列x1 x2 xn就是问题的最优解 xn 1 1 xn 1 pn 1 xn 2020 5 23 例5 3利用向前处理法求解0 1背包问题设gi x 是KNAP i 1 n X 的最优解 g0 M KNAP 1 n M 的最优解 由于x1的取值等于1或0 可得 g0 M max g1 M g1 M w1

12、p1 对于某个xi xi等于1或0 则有 gi X max gi 1 X gi 1 X wi 1 pi 1 初始值 0X 0gn X X 0 2020 5 23 例5 4利用向前处理法求解k段图问题设 V2 1 j2 p2 V2 p2 是由到t的最短路径 则s到t的最短路径是 s V2 1 j2 p2 中最短的那条路径 若s v2 v3 vi vk 1 t是s到t的一条最短路径 vi是其中的一个中间点 则s v2 v3 vi和vi vk 1 t分别是由s到vi和vi到t的最短路径 最优性原理 从Vi中的结点ji到t的最短路径将是 min Vi 1 1 ji 1 pi 1 2020 5 23 2

13、 向后处理法列出根据x1 xi 1的最优决策序列求取xi决策值的关系式 从第一个阶段 逐步向后递推求出各阶段的决策值 决策序列x1 x2 xn就是问题的最优解 2020 5 23 例5 50 1背包问题 向后处理策略 设fi x 是KNAP 1 i X 的最优解 则 fn M KNAP 1 n M 向后递推关系式 fi X max fi 1 X fi 1 X wi pi 初始值 0X 0f0 X X 0 2020 5 23 例5 6k段图问题 向后处理策略 设 Vk 1 1 jk 1 pk 1 Vk 1 pk 1 是由s到的最短路径 则s到t的最短路径是 t Vk 1 1 jk 1 pk 1

14、中最短的那条路径 若s v2 v3 vi vk 1 t是s到t的一条最短路径 vi是其中的一个中间点 则s v2 v3 vi和vi vk 1 t分别是由s到vi和vi到t的最短路径 最优性原理 从s到Vi中的结点ji的最短路径将是 min Vi 1 ji pi 2020 5 23 动态规划的基本思想 1 动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件 要做到这一点 必须将问题的过程分成几个相互联系的阶段 恰当选择状态变量 决策变量和定义最优值函数 从而把一个大问题化成一簇同类型的子问题 然后逐个求解 即从边界条件开始 逐段递推寻优 在每一个子问题的求解中 均利用了它前面的子问题

15、的最优化结果 依次进行 最后一个子问题的最优解 就是整个问题的最优解 2 在多阶段决策过程中 动态规划方法是既把当前一段和未来各段分开 又把当前的效益和未来效益综合起来考虑的一种最优化方法 因此 每段决策的选取是从全局来考虑的 与该段的最优选择答案一般是不同的 3 在求整个问题的最优策略时 由于初始状态是已知的 而每段的决策都是该段状态的函数 故最优策略所经的各段状态便可逐次变换得到 从而确定最优路线 2020 5 23 关于动态规划求解策略的进一步说明采用枚举法 若问题的决策序列由n次决策构成 而每次决策有p种选择 则可能的决策序列将有pn个 利用动态规划策略的求解过程中保存了所有子问题的最

16、优解 而舍去了所有不能导致问题最优解的次优决策序列动态规划 可能有多项式的计算复杂度 2020 5 23 与非线性规划相比 动态规划的优点 1 易于确定全局最优解 动态规划方法是一种逐步改善法 它把原问题化为一系列结构相似的最优化子问题 而每个子问题的变量个数比原问题少的多 约束集合也要简单得多 2 能得到一簇解 有利于分析结果 3 能利用经验 提高求解的效率 动态规划方法反映了过程逐段演变的前后联系 较之非线性规划与实际过程联系得更紧密 不足之处 1 没有一个统一的标准模型可供应用 2 应用的局限性 要求状态变量满足 无后效性 条件 不少实际问题在取其自然特征作为状态变量往往不能满足这条件 3 在数值求解中 存在 维数障碍 在计算机中 每递推一段 必须把前一段的最优值函数在相应的状态集合上的全部值存入内存中 当维数增大时 所需的内存量成指数倍增长 2020 5 23 5 2多段图问题 1 问题的描述 在多段图中求从s到t的一条最小成本的路径 可以看作是在k 2个段作出某种决策的结果 第i次决策决定Vi 1中的哪个结点在这条路径上 这里1 i k 2 最优性原理对多段图问题成立 202