文档介绍：第七章第七章动态规划动态规划动态规划问题和基本概念动态规划的基本原理动态规划的应用 1 引言引言动态规划与多阶段决策: 动态规划与多阶段决策: 多阶段决策是指这样一类特殊的活动过程, 它们可以按时间顺序分解成若干相互联系的阶段, 每个阶段都要作出决策, 全部过程的决策是一个决策序列, 所以多阶段决策问题又称为序贯决策问题。多阶段决策的目标是要达到整个活动过程的总体效果最优, 所以多阶段决策又叫做过程最优化。所谓动态规划, 就是解决多阶段决策和过程最优化问题的一种规划方法。 2 . 例7 .1 最短路问题设A地的某一企业要把一批货物由 A地运到 E城销售, 其间要经过八个城市,各城市间的交通路线及距离如下图所示, 问应选择什么路线才能使总的距离最短? 动态规划问题和基本概念例中,路线图(共18条路线,3×3×2× 1=18) 3 枚举法: 例中,路线图(共18条路线,3×3×2× 1=18) 4 为解决这个最短路径问题,首先给出几个定义。 1)、阶段(stage) 将所给问题的过程,按时间或空间特征分解成若干相互联系的段落, 以便按次序求解就形成了阶段,阶段变量常用字母 K来表示。如例有四个阶段, K就等于 1,2,3,4 。第一阶段共有 3 条路线即(A,B1), (A,B2) 和(A,B3) ,第二阶段有 9条路线,第 3 阶段有 6条路线,第 4 阶段有 2 条路线。 12 34 5 2)、状态 ( state) 各阶段开始时的出发点称作状态。描述各阶段状态的变量,称作状态变量, 用s k 表示。在例中,第一阶段的状态为 A,第二阶段的状态为城市 B1 , B2 和 B3 。所以状态变量 S1的集合 S1={A} , S2的集合是 S2={B1,B2,B3}, 依次有 S3={C1,C2,C3}, S4={D1,D2} 。 12 34 6 3)、决策( Decision ) 当各阶段的状态确定以后,就可以做出不同的决定或选择,从而确定下一阶段的状态,这种决定就是决策,表示决策的变量称为决策变量。常用 kX ( ks )表示第 K阶段当状态为 ks 时的决策变量, 在例 B 1出发,即 S 2 =B 1,可选择走 C 1或C 2, C 3,如果我们选择, 从 C2 走,则此时的决策变量可表示 x 2 (B 1 )=C 2。 12 34 7 4)、策略( Policy ) 在各阶段决策确定以后, 整个问题的决策序列就构成了一个策略, 用P 1n(s 1)表示。如对于例 18个策略,但最优策略只有一个。 1234 8 5)、目标函数用于衡量所选定策略优劣的数量指标称作目标函数。一个 n阶段的决策过程,从 1到n 叫作问题的原过程。目标函数的最优值称为最优目标函数,最优目标函数记为 f k(s k),它表示从第 K阶段的状态 S k出发采用的最优策略。当 K=1 时, f 1(s 1 )就是从初始状态 S 1到全过程结束的整体最优目标函数。,9 在例 ,目标函数就是距离。如在第 2阶段,状态为 B 2时, f 2 (B 2)则表示从 B 2到E的最短距离。本问题的总目标是求 f 1 (A), 即从 A到E的最短距离。 12 34 10