《运筹学》课程教学资源（课件讲稿）第八章 动态规划

第八章动态规划 本章主要内容： 多阶段的决策问题 ◆最优化原理与动态规划的数学模型 离散确定性动态规划模型的求解 离散随机性动态规划模型的求解 一般数学规划模型的动态规划解法 2014-12-15

2014-12-15 1 第八章 动态规划 多阶段的决策问题 最优化原理与动态规划的数学模型 离散确定性动态规划模型的求解 离散随机性动态规划模型的求解 一般数学规划模型的动态规划解法 本章主要内容：

§1多阶段的决策问题 (Multi-Stage decision process) 动态规划： 一是一种研究多阶段决策问题的理论和方法。 多阶段决策问题： 一是指一类活动过程，它可以分为若干个相互联系的阶 段，在每个阶段需要作出决策。这个决策不仅决定 这一阶段的效益，而且决定下一阶段的初始状态。 策略： 一每个阶段的决策确定以后，就得到一个决策序列，称 为策略。多阶段决策问题就是求一个策略，使各阶段 的总效益达到最优。 2014-12-15 2

2014-12-15 2 §1 多阶段的决策问题 (Multi-Stage decision process) 动态规划： –是一种研究多阶段决策问题的理论和方法。 多阶段决策问题 ： –是指一类活动过程，它可以分为若干个相互联系的阶 段，在每个阶段都需要作出决策。这个决策不仅决定 这一阶段的效益，而且决定下一阶段的初始状态。 策略： –每个阶段的决策确定以后，就得到一个决策序列，称 为策略。多阶段决策问题就是求一个策略，使各阶段 的总效益达到最优

[例1]最短路问题 设有一个旅行者从下图中的A点出发，途中要经过B、C、 D等处，最后到达终点E。从A到E有很多条路线可以选 择，各点之间的距离如图所示，问该旅行者应该选择哪 一条路线，才能使从A到达E的总行程最短？ 决策 决策 状态A 决策 状态B, 状态C3 状态D 决策 状态E 阶段1 阶段2 阶段3 阶段4 行程1 行程2 行程3 行程4 2014-12-15 3

2014-12-15 3 [例1] 最短路问题 设有一个旅行者从下图中的A点出发，途中要经过B、C、 D等处，最后到达终点E。从A到E有很多条路线可以选 择，各点之间的距离如图所示，问该旅行者应该选择哪 一条路线，才能使从A到达E的总行程最短？ A B1 B2 B3 C3 C2 C1 D1 D2 E 2 5 3 7 5 6 3 2 4 5 1 5 1 4 6 3 3 3 3 4 状态A 决策 阶段1 状态B1 阶段2 决策 状态C 状态D1 3 阶段3 决策 阶段4 决策 状态E 行程1 行程2 行程3 行程4

§2最优化原理与动态规划的数学模型 动态规划问题的解题思路 ◆动态规划的基本概念 ◆最优化原理与动态规划的数学模型 ◆逆序解法与顺序解法 ◆动态规划模型的分类 2014-12-15 4

2014-12-15 4 §2 最优化原理与动态规划的数学模型 动态规划问题的解题思路 动态规划的基本概念 最优化原理与动态规划的数学模型 逆序解法与顺序解法 动态规划模型的分类

动态规划问题的解题思路 思路：将一个n阶段的决策问题转化为依次求n个具 有递推关系的单阶段决策问题，从而简化计算。 在例1中，这种转化的实现是从终点E出发一步步进行反推（逆序算法） (1)考虑一个阶段的选择。 到达E之前，上一步必然到达D1或D2, D,到E的最优策略是：D1→E,距离d(D1,E)=3,记fD=3. D2到E的最优策略是：D2→E,距离d(D2,E)=4,记f/D=4. B B 2014-12-15 5

2014-12-15 5 动态规划问题的解题思路 思路：将一个n阶段的决策问题转化为依次求n个具 有递推关系的单阶段决策问题，从而简化计算。 在例1中，这种转化的实现是从终点E出发一步步进行反推（逆序算法） （1）考虑一个阶段的选择。 到达E之前，上一步必然到达D1或D2， D1到E的最优策略是：D1E，距离d(D1 ,E)=3,记 f(D1 )=3. D2到E的最优策略是：D2E，距离d(D2 ,E)=4,记 f(D2 )=4. 1 A B1 B2 B3 C3 C2 C1 D1 D2 E 2 5 3 7 5 6 3 2 4 5 1 5 4 6 3 3 3 3 4

动态规划问题的解题思路 (2)联合考虑两个阶段的最优选择。 当旅行者离终点还有两站时，他必然处在C1,C2或C3的某一点上。 C1到终点的路有两条：C1→D1→E,C1→D2→E,旅行者从这两条 路线中选最短的一条，并且不管是经过D或D2,到达该点后，他应 循着从D1或D2到E的最短路线继续走。因此 从C,到E的最短路程为： (d(C,D)+f(D) 1+3 min =min d(C1,D2)+f(D2) 4+4 即从C1到的最短路线为C1→D,→E,记f(C,)三45 如果从C2出发 d(C2,D)+f(D) 6+3 min min =7 dC2,D2)+f(D2) 3+4 fC2)=7 如果从C3出发 「dC3,D)+f(D) 3+3 min min =6 fC3)=6 6 dC3,D2)+f(D2) 3+4

6 (2)联合考虑两个阶段的最优选择。 当旅行者离终点还有两站时，他必然处在C1，C2或C3的某一点上。 C1到终点的路有两条：C1D1E， C1D2E，旅行者从这两条 路线中选最短的一条，并且不管是经过D1或D2，到达该点后，他应 循着从D1或D2到E的最短路线继续走。因此 从C1到E的最短路程为： 1 2 2 1 1 1 min min 4 ( , ) ( ( , ) ( 3 4 ) ) 4 d C D D 1 C D f D f d                   即从C1到E的最短路线为C1D1E，记 1 f C( ) 4  如果从C2出发 2 1 1 2 2 2 2 ( , ) ( ) ( , ) ( ) 3 4 6 3 min min 7 ( ) 7 d C D d C D f D f C f D                    如果从C3出发 3 1 3 1 3 2 2 min min 6 ( ) 6 ( , ( ) ( ) 3 3 4 d C D f , ) ( ) 3 f C C f D D d D                    动态规划问题的解题思路 A B 1 B 2 B 3 C 3 C 2 C 1 D 1 D 2 E 2 5 3 7 5 6 3 2 4 5 1 5 1 4 6 3 3 3 3 4

动态规划问题的解题思路 (3)再联合起来考虑三个阶段的最优选择。 从B,点出发的最优选择为 「d(B,C)+f(C) 7+4 mind(B,C2)+f(C2) =min{5+7 11 f(B)÷115 d(B,C3)+f(C3) 6+6 从B2点出发的最优选择为 [d(B,C)+f(C) 3+4 min d(B2,C2)+f(C2) min 2+7}=7 fB2)=7 d(B2,C3)+fC3) 4+6 从B3点出发的最优选择为 d(B3,C)+f(C) [5+4 min d(B3,C2)+f(C2) =min{1+7=8 f(B3)=8 d(B,C3)+f(C3) 5+6 2014-12-15

2014-12-15 7 （3）再联合起来考虑三个阶段的最优选择。 从B1点出发的最优选择为 1 1 1 2 2 1 1 3 1 3 min ( , ) ( ) min 5 7 11 ( ) 11 ( , ) ( ) ( , ) ( ) 7 4 6 6 d B C f C f d B C f C B d B C f C                              从B2点出发的最优选择为 2 2 2 2 2 3 3 2 1 1 min ( , ) ( ) min 2 7 7 ( ) 7 ( ( , ) ( ) 3 , ) ( ) 4 6 d 4 d B C f C f B B d f C f B C C C                              从B3点出发的最优选择为 3 1 1 3 3 3 3 3 2 2 ( , ) ( ) 5 4 min min 8 ( ) 8 ( , ( , ) ( ) 5 6 d B C ) ( ) 1 7 d B C f C f B d B C C C f f                              动态规划问题的解题思路 A B 1 B 2 B 3 C 3 C 2 C 1 D 1 D 2 E 2 5 3 7 5 6 3 2 4 5 1 5 1 4 6 3 3 3 3 4

动态规划问题的解题思路 (4)四个阶段联合考虑时从A到E的最优选择。 d(A,B)+f(B) [2+11 min d(A,B2)+f(B2)=min5+7 =11 f(A)=11 d(A,B3)+f(B3) 3+8 从A到E的最短路线为A→B3→C2→D2→E,距离为11。 以上计算过程可以在图上通过标号法实现 11 A 3 0 11 A 3 5 2014-12-15

2014-12-15 8 （4）四个阶段联合考虑时从A到E的最优选择。 3 1 2 2 3 1 ( , ) ( ) 2 11 min ( , ) ( ) min 5 7 11 ( ) 11 ( , ) ( ) 3 8 d A B f B d A B f B f A d A B f B                              从A到E的最短路线为AB3C2D2E，距离为11。 1 A B1 B2 B3 C3 C2 C1 D1 D2 E 2 5 3 7 5 6 3 2 4 5 1 5 4 6 3 3 3 3 4 3 4 4 7 6 11 7 8 11 以上计算过程可以在图上通过标号法实现 动态规划问题的解题思路 0

动态规划的基本概念 1.阶段(stage):指一个问题需要作出决策的步数。 通常用k表示问题的阶段数。阶段一般是根据时间和空间的自然特征 来划分的。 2.状态(state):表示每个阶段开始所处的自然状况或客观条 件，它描述了研究问题过程的状况，是动态规划中最关键的 一个参数。 它既反映前面各个阶段决策的结局，又是本阶段决策的出发点和依据。 它是动态规划问题各个阶段信息的传递点和结合点。通常一个阶段有 多个状态。如例1中第一阶段有1个状态，A.第三阶段有三个状态 C1,C2,C3。 状态变量：描述状态的变量。 可以是数、数组或向量。通常用$k表示k阶段的状态集。如例1中 s3={C1,C2,C3}. 状态的性质：无后效性。 2014-12-15

2014-12-15 9 动态规划的基本概念 1. 阶段(stage)：指一个问题需要作出决策的步数。 通常用k表示问题的阶段数。阶段一般是根据时间和空间的自然特征 来划分的。 2. 状态(state)：表示每个阶段开始所处的自然状况或客观条 件，它描述了研究问题过程的状况，是动态规划中最关键的 一个参数。 它既反映前面各个阶段决策的结局，又是本阶段决策的出发点和依据。 它是动态规划问题各个阶段信息的传递点和结合点。通常一个阶段有 多个状态。如例1中第一阶段有1个状态，A. 第三阶段有三个状态 C1,C2,C3。 状态变量：描述状态的变量。 可以是数、数组或向量。通常用sk表示k阶段的状态集。 如例1中 s3={C1,C2,C3}. 状态的性质：无后效性

动态规划的基本概念 3.决策(de cision)是指某阶段初从给定的状态出发，决 策者在面临的若干种不同方案中做出的选择。 决策变量Xk(Sk)表示第k阶段状态为$k时对方案的选择。 用Dk(Sk)表示在第k阶段状态为Sk时决策允许的取值范围， 称为允许决策集合。即xk(Sk)∈Dk(Sk)。 D2(B1)={B1→C1,B1→C2,B1→C3} (Sk)表示第k阶段状态为Sk时的最优决策。 决策的性质：第k阶段某一状态下的决策直接决定第k+1 阶段的状态。 2014-12-15 10

2014-12-15 10 3.决策(decision) 是指某阶段初从给定的状态出发，决 策者在面临的若干种不同方案中做出的选择。 决策变量 xk (sk ) 表示第k阶段状态为sk时对方案的选择。 用Dk (sk ) 表示在第k阶段状态为sk时决策允许的取值范围， 称为允许决策集合。即xk (sk )Dk (sk )。 D2 (B1 )={B1→ C1 , B1→ C2 , B1→C3 } xk * (sk )表示第k阶段状态为sk时的最优决策。 决策的性质：第k阶段某一状态下的决策直接决定第k+1 阶段的状态。 动态规划的基本概念