《运筹学动态规划》PPT课件.ppt

第七章动态规划 动态规划简介 多阶段决策过程最优化 多阶段决策过程 是指一类特殊的过程 它们可以按时间顺序分解成若干个相互联系的阶段 称为 时段 在每个时段都要做决策 全部过程的决策是一个决策序列 多阶段决策问题也称为序贯决策问题 多阶段决策问题的目标是要达到整个活动过程的总体最优 在每个阶段进行决策时不应仅考虑本阶段最优 尤其应考虑对最终目标的影响 从而做出对全局来说最优的决策 动态规划是符合这种要求的一种决策方法 第1阶段 第2阶段 第n阶段 决策 决策 决策 多阶段决策过程图示 动态规划的基本概念 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 1 3 4 3 阶段 k 1 2 3 4 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 1 3 4 3 状态 各阶段开始时的客观条件 表示状态的变量称为状态变量 常用sk表示第k阶段的状态变量 第k阶段所有状态变量的集合记为Sk 动态规划考虑的状态应该具有 无后效性 基本概念 续二 决策 当一个阶段的状态取定了后 就可以作出不同决定 或选择 从而确定下一阶段的状态 这种决定称为决策 表示决策的变量称为决策变量 uk sk 就表示第k阶段当状态为sk时的决策变量 决策变量的取值常常限制在一定的范围内 这一范围称为允许决策集合 常用记号Dk sk 表示第k阶段状态为sk时的允许状态集合 基本概念 续三 各阶段的决策确定后 整个过程各阶段的决策就构成一个决策序列 称为策略 用p1 n u1 s1 u2 s2 un sn 表示 此外还常常需要考虑后部子策略pk n uk sk un sn 动态规划要求的就是使整个问题达到最优的策略 基本概念 续四 状态转移方程 动态规划中一个阶段的状态常常是上一阶段的状态和决策的结果 如果给定了第k阶段的状态sk 和第k阶段的决策uk sk 则第k 1阶段的状态sk 1也就完全确定了 这一关系可用下面的方程表示sk 1 Tk sk uk 称之为状态转移方程 它表示了由第k阶段到第k 1阶段状态转移的规律 基本概念 续五 指标函数 用于衡量决策或策略优劣的数量指标称为指标函数 阶段指标函数 它通常是指在第k阶段 从状态sk出发 采用决策uk时的效益 记为d sk uk 过程指标函数 它通常表示在第k阶段时的状态为sk时 采用后部子策略pk n的效益值 记为Vk n sk pk n 最优指标函数记为fk sk 表示第k阶段的状态为sk时 采用了最优后部子策略p k n的指标函数值 Vk n sk pk n 与fk sk 的关系是 特别地 f1 s1 就是从初始状态s1到全过程结束的整体最优函数 对最短路线问题阶段指标函数就是两点间的距离 后部子过程pk n的指标函数Vk n sk pk n 就是在第k阶段位于点sk时到终点的距离 而fk sk 就是到终点的最短距离 最短路线问题 就是要求f1 A 以及相应的路线 最短路线问题的解 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 1 3 4 3 第一步 从k 5开始 状态变量s5可以取两种状态E1 E2 从它们到终点F的距离分别为4 3 即f5 E1 4 f5 E2 3 动态规划最通常的解法 就是逆序递推的方式求解 第二步 k 4 状态变量s4可以取三个值D1 D2 D3 于是 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 1 3 4 3 k 3 k 2 k 1 最优路线为 A B1 C2 D2 E2 F从起点A到终点F的最短路程为17 动态规划的最优化原理 动态规划方法基于R Bellman等人提出的最优化原理 它可表述为 一个过程的最优化策略具有这样的性质 无论初始状态与初始决策如何 对于先前决策所形成的状态而言 其以后的所有决策应构成