动态规划MATLab.ppt

案例 最短路问题 假设要从A城市到E城市铺设一条输油管道 中间需要经过三个地区 每个地区都有若干个转运 站 构成了许多不同的输油路线 转运站间的数字 表示站间的运输路径的长度 由于地理条件等原因 某些地区之间不能直接铺设相通的管道 现需求出 一条使总路径最短的管道路线 动态规划 A B1 B2 B3 C1 C2 C3 D1 D2 E 1动态规划的基本概念 一 阶段 对于一个多阶段决策过程 可以根据问题的特 点 把整个过程划分为几个相互联系的阶段 以便 可以按一定的顺序去求解 这个根据时间和空间的 自然特征来划分的次序称为阶段 描述阶段的变量 称为阶段变量 一般用k表示 如案例中的多阶段决策问题可划分为四个阶 记为 段 二 状态 状态 表示系统每个阶段开始时所处的自然状况或 客观条件 如案例中 状态就是某阶段的出 发位置 它既是该阶段某支路的起点 又是前 一阶段某支路的终点 第一个阶段有一个状态 即为点A 第二个阶段有三个状态 状态变量 描述状态的变量 常用 表示第k阶段 的状态变量 如案例中第三个阶段有3个状 态 则状态 可取三个值 即 这三 个点构成的集合 称为第三个阶段 的允许状态集 记为 有时为了方 便起见 也将阶段的状态编上号码 即有 一般地 第k个阶段的允许状态集 记为 当某个阶段的状态给定后 则这个阶段以后过程 的发展不受这个阶段及以前各阶段状态的影响 也 是说 当前的状态只是以往历史的一个总结 过程 的过去历史只能通过当前的状态去影响它未来的发 展 这种性质称为无后效性 三 决策 决策 各阶段状态确定后 确定下一个阶段的状态 的各种选择 决策变量 描述决策的变量 常用 表示第k 阶段状态处于 时的决策变量 它是状态 变量 的函数 允许决策集 决策变量的取值构成的集合 表明决策 的约束条件 常用 表示第k阶段系统 处于状态 时的允许决策集合 即有 如案例中 第二阶段决策时 若从状 态 出发 则可做出三种不同决策 其允许决策集 合为 若选定的下一个状态是 则 四 策略 策略 从初始阶段到最终阶段 每个阶段均有一决 策 各阶段决策形成一个决策序列 称为系统的一个策略 此序列 最优策略 使系统达到最优效果的策略 全过程策略 对于具有几个阶段的多阶段决策问题 从第一个阶段的某一状态出发到终止阶 段的状态做出的决策序列而形成的策略 记为 即 k后部子过程 从第k阶段到终止阶段状态的过程 简 称为k子过程 后部子过程策略 k后部子过程相应的决策序列 简 称为k子策略 记为 即 允许策略集 在实际问题中 可供选择的策略所在 的范围 常记为P 五 状态转移方程 状态转移方程 描述系统由一个阶段到下一个阶段 的状态转移规律 例如 设系统第k阶段的 状态变量 的值给定 该阶段的决策变量 确定 则第k 1阶段 的状态变量 的值 也就确定了 即 的值随 和 变化而变化 这种对应关系我们记为 的值的 以上状态转移规律 即为状态转移方程 称为状态转移函数 六 指标函数与最优指标函数 k阶段指标函数 第k阶段状态为 决策变量 取 某个值后得到的一个反映这个局部策略效 应的数量指标 也称为k阶段的效应函数 全过程的指标函数 常用 表示 采用全过程的策略 的数量 指标 其指标函数值记为 用 表示第k阶段状态为 采用 策略 时 后部子过程的指标函数值 最优指标函数 指标函数的最优值 记为 表示从第k阶段的状态 开始到第n阶段 的终止过程采取最优策略 所得到的 指标函数值 即 在不同问题中 指标函数的含义是不同的 它可能指 距离 利润 成本 产品的产量或资源消耗等 如 案例中 指标函数是距离 如第二阶段状态为 时 表示由 出发采用决策到下一个 阶段 点的距离 表示从 出发到F的总 距离 而 表示从B1出发到F的最短距离 该问 题的总目标是求 即从A到终点F的最短距离 2动态规划的基本原理 下面我们结合案例的最短路问题来介绍动态 规划的基本思想与基本原理 穷举法的计算量将非常大 显然不适合 考虑最短路线的一个重要特征 若从起点A经过 B点和C点而达到终点D是一条最短路线 则由B点出 发经过C点到达终点D点的这条子路线 对于从B点 出发达到终点D点的所有可能选择的不同路线来说 必定也是最短路线 在本例中 若找到了 是由 A到D的最短路线 则 也应是从B1出 发到D点的所有可能选择的不同路线中的最短路线 如果不是这样 则从B1点到D点有另一条距离更短的 路线存在 把它和原来的最短路线有A点到B1点的那 部分连接起来 就会得到一条从A点到D点的新路线 且比原来的那条最短路线的距离还要短些 这就与 假设矛盾 基于最短路线的这一特性 我们考虑寻找 最短路线的方法 就是从最后一段开始 用由后向前 逆向递推的方法 逐步求出各点到终点的最短路线 最后求得由起点到终点的最短路线 以本案例为例 我们按上述思想寻找从A到E的最 短路线 A B1 B2 B3 C1 C2 C3 D1 D2 E 第一步 从k 4出发 状态变量 可取状态 它们到E点的路长分别为 第二步 k 3 状态变量 可取三个值 这是经过一个中途点到达终点E的两级决策变量 从 到E有两条路线 需加以比较取其中最短的 即 这说明由 到E的最短距离为7 其路径为 相应的决策为 同理 即 到终点E的最短距离为6 其路径为 相应的决策为 即 到终点E的最短距离为10 其路径为 相应的决策为 类似地 k 2时 k 1时 出发点只有一个A点 则 即从起点A到终点E的最短距离为15 反推可得最优决策序列 再按计算顺序 即 所以得最短路线为 注1 从本案例的计算过程可以看出 在各阶段 都 利用了第k阶段和第k 1阶段的如下关系 这种递推关系称为动态规划的基本方程 称为边界条件 上述最短路线的计算过程也可用图直观表示出 来 如图 A B1 B2 B3 C1 C2 C3 D1 D2 E 这里 每个节点上方的括号内的数字 表示该点到 E点的最短距离 连接各点到E点的线表示最短路径 这种在图上直接计算的方法称为标号法 动态规划方法相对于穷举法来说有以下优点 1 减少了计算量 2 丰富了计算结果 动态规划方法存在的不足之处 1 静态规划模型转化为动态规划模型十分困难 2 状态变量的 无后效性 条件难以满足 动态规划的基本思想总结 先将多阶段决策的过程划分成几个相互联系 的阶段 恰当地选取状态变量 决策变量 定义最 优指标函数 从而把问题化成一族同类型的子问题 然后逐个求解 求解时从边界条件开始 逆方向逐 段递推寻优 在每一个子问题求解时 都要使用它 前面已求出的子问题的最优结果 最后一个子问题 的最优解 就是整个问题的最优解 动态规划的基本方程是递推逐段求解的根据 动态规划基本方程可表述为 式中opt可根据实际问题选取min或max 表示状态为 决策为 时对应的第k阶段的指标 函数值 3应用LINGO软件求解动态规划 解 LINGO程序如下 Model Sets Nodes a b1 b2 b3 c1 c2 c3 d1 d2 e d Arcs nodes nodes a b1a b2a b3b1 c1b1 c2b2 c1b2 c2b2 c3b3 c2b3 c3c1 d1c1 d2c2 d1c2 d2c3 d1c3 d2d1 ed2 e w p Endsets n size nodes d n 0 for nodes i i LT n d i min arcs i j w i j d j for arcs i j p i j if d i eq w i j d j 1 0 Data W 357769523835436943 EnddataEnd 迭代后有如下结果 Feasiblesolutionfoundatiteration 0VariableValueN10 00000D A 15 00000D B1 12 00000D B2 11 00000D B3 9 000000D C1 7 000000D C2 6 000000D C3 10 00000D D1 4 000000D D2 3 000000D E 0 000000W A B1 3 000000W A B2 5 000000 W A B3 7 000000W B1 C1 7 000000W B1 C2 6 000000W B2 C1 9 000000W B2 C2 5 000000W B2 C3 2 000000W B3 C2 3 000000W B3 C3 8 000000W C1 D1 3 000000W C1 D2 5 000000W C2 D1 4 000000W C2 D2 3 000000 W C3 D1 6 000000W C3 D2 9 000000W D1 E 4 000000W D2 E 3 000000P A B1 1 000000P A B2 0 000000P A B3 0 000000P B1 C1 0 000000P B1 C2 1 000000P B2 C1 0 000000P B2 C2 1 000000P B2 C3 0 000000 P B3 C2 1 000000P B3 C3 0 000000P C1 D