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

第八章 动态规划 §1多阶段决策最优化问题举例 §2 基本概念、基本方程与最优化原理 §3 离散确定性动态规划求解 §41 离散随机性动态规划求解 §5一般数学规划模型的动态规划解法 2025/4/6

2025/4/6 2 第八章 动态规划 §1 多阶段决策最优化问题举例 §2 基本概念、基本方程与最优化原理 §3 离散确定性动态规划求解 §4 离散随机性动态规划求解 §5 一般数学规划模型的动态规划解法

§1 多阶段快策过程最优化问题举例 例1最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的 最 短路径。 4 6 D 10 4 7 3 7 A B 2 E 2 2 D 2 6 6 3 3 3 5 B 2025/4/6

2025/4/6 3 §1 多阶段决策过程最优化问题举例 例1 最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的 最 短路径。 A B B C D B C D E C 4 1 2 3 1 2 3 1 2 3 2 2 1 6 4 7 2 4 8 3 8 6 7 5 6 1 10 6 4 3 7 5 1

用穷举法的计算量： 如果从A到E的站点有k个，除A、E之外每站有3个位置则 总共有3k-1×2条路径： 计算各路径长度总共要进行(k+1)3k-1×2次加法以及 3k-1×2-1次比较。随着k的值增加时，需要进行的加法和比较 的次数将迅速增加； 例如当k=20时，加法次数为4.2550833966227×1015 次，比较1.3726075472977×1014次。若用1亿次/秒的计 算机计算需要约508天。 2025/4/6

2025/4/6 4 用穷举法的计算量: 如果从A到E的站点有k个，除A、E之外每站有3个位置则 总共有3 k-1×2条路径； 计算各路径长度总共要进行 (k+1) 3k-1×2次加法以及 3 k-1×2-1次比较。随着 k 的值增加时，需要进行的加法和比较 的次数将迅速增加； 例如当 k=20时，加法次数为 4.2550833966227×1015 次，比较 1.3726075472977×1014 次。若用1亿次/秒的计 算机计算需要约508天

局部最优不一定全局最优 如：本例中D-E的最短 2025/4/6

局部最优不一定全局最优 如:本例中D-E的最短 2025/4/6

动态规划的解题思路 把多(n)阶段的决策问题转化为求个具有递推 关系的单阶段决策问题 ■这些单阶段决策具有相似的性质. ■此例中考虑A到E的最短距离，可分为四个阶段 ,A到B,C,D,E ■每个阶段所处的状态，如：B有B1,B2,. ■考虑由此状态下，到E的最短距 ■逆序求解，先考虑D到E,再考虑C到E. ▣具有递推关系 2025/4/6

动态规划的解题思路 ◼ 把多(n)阶段的决策问题转化为求n个具有递推 关系的单阶段决策问题. ◼ 这些单阶段决策具有相似的性质. ◼ 此例中考虑A到E的最短距离,可分为四个阶段 ,A到B,C,D,E. ◼ 每个阶段所处的状态, 如: B 有B1,B2,. ◼ 考虑由此状态下,到E的最短距 ◼ 逆序求解,先考虑Di到E,再考虑Ci到E. ◼ 具有递推关系 2025/4/6

讨论： 1、以上求从A到E的最短路径问题，可以转化为四个性质 完全相同，但规模较小的子问题，即分别从D、CB、 A到E的最短路径问题。 第四阶段：两个始点D,和D2,终点只有一个； 表-1 阶段4 本阶段始点 本阶段各终点（决策） 到E的最短距离 本阶段最优终点 (状态) E (最优决策) Di 10 10 E D2 6 6 E 分析得知：从D,和D,到E的最短路径唯一。 2025/4/6 >

2025/4/6 7 讨论： 1、以上求从A到E的最短路径问题，可以转化为四个性质 完全相同，但规模较小的子问题，即分别从Di 、Ci、Bi、 A到E的最短路径问题。 第四阶段：两个始点D1和D2，终点只有一个； 表-1 分析得知：从D1和D2到E的最短路径唯一。 阶段4 本阶段始点 （状态） 本阶段各终点（决策） 到E的最短距离 本阶段最优终点 （最优决策) E D1 D2 10 6 10 6 E E

第三阶段：有三个始点C1,C2,C3,终点有D1,D2,对始点 和终点进行分析和讨论分别求C1,C2,C3到D1,D2的最短路 径问题： 表-2 阶段3 本阶段始点 本阶段各终点（决策） 本阶段最优终点 (状态) 到E的最短距离 Di D2 (最优决策) C1 8+10=18 6+6=12 12 D2 C2 7+10=17 5+6=11 11 D2 C3 1+10=11 6+6=12 11 Di 分析得知：如果经过C, 则最短路为C1-D2-E; 如果经过C2,则最短路为C2D2-E; 如果经过C3,则最短路为C3-DE。 2025/4/6

2025/4/6 8 第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点 和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路 径问题： 表-2 分析得知：如果经过C1，则最短路为C1 -D2 -E； 如果经过C2，则最短路为C2 -D2 -E； 如果经过C3，则最短路为C3 -D1 -E。 阶段3 本阶段始点 （状态） 本阶段各终点（决策） 到E的最短距离 本阶段最优终点 D （最优决策) 1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=11 6+6=12 5+6=11 6+6=12 12 11 11 D2 D2 D1

第二阶段：有4个始点B1,B2,B3,B4,终点有C1,C2,C3。对始点和 终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3的最短路 径问题： 表-3 阶段2 本阶段始点 本阶段各终点（决策） 到E的最 本阶段最优终 (状态) C1 C2 点（最优决策） C3 短距离 Bi 2+12=14 1+11=12 6+11=17 12 C2 B2 4+12=16 7+11=18 2+11=13 13 C3 Ba 4+12=16 8+11=19 3+11=14 14 C3 Ba 7+12=19 5+11=16 1+11=12 12 C3 分析得知： 如果经过B1,则走B-C2-D2-E; 如果经过B2,则走B2C3-D-E; 如果经过B3,则走B3C3-D-E; 如果经过B4,则走B4-C3-D1-E。 2025/4/6

2025/4/6 9 第二阶段：有4个始点B1 ,B2 ,B3 ,B4，终点有C1 ,C2 ,C3。对始点和 终点进行分析和讨论分别求B1 ,B2 ,B3 ,B4到C1 ,C2 ,C3 的最短路 径问题： 表-3 分析得知：如果经过B1，则走B1 -C2 -D2 -E； 如果经过B2，则走B2 -C3 -D1 -E； 如果经过B3，则走B3 -C3 -D1 -E； 如果经过B4，则走B4 -C3 -D1 -E。 阶段2 本阶段始点 （状态） 本阶段各终点（决策） 到E的最 短距离 本阶段最优终 点（最优决策) C1 C2 C3 B1 B2 B3 B4 2+12=14 4+12=16 4+12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11=17 2+11=13 3+11=14 1+11=12 12 13 14 12 C2 C3 C3 C3

第一阶段：只有1个始点A,终点有B1,B2,B3,B4。对始点和终 点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题： 表10-4 阶段1 本阶段始 本阶段各终点（决策） 本阶段最优终 点（状态） 到E的最 点（最优决策） B, B2 B3 Ba 短距离 4+12=16 3+13=16 3+14=17 2+12=14 12 B4 最后， 可以得到：从A到E的最短路径为A→B4→C3→D,→E 2025/4/6 10

2025/4/6 10 第一阶段：只有1个始点A，终点有B1 ,B2 ,B3 ,B4 。对始点和终 点进行分析和讨论分别求A到B1 ,B2 ,B3 ,B4的最短路径问题： 表10-4 最后，可以得到：从A到E的最短路径为A→ B4→ C3→ D1→ E 阶段1 本阶段始 点(状态) 本阶段各终点（决策） 到E的最 短距离 本阶段最优终 点(最优决策) B1 B2 B3 B4 A 4+12=16 3+13=16 3+14=17 2+12=14 12 B4

以上计算过程及结果，可用图2表示，可以看到，以上方法不仅 得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最 短路径。 12 12 14 13 10 0 3 12 以上过程，仅用了22次加法，计算效率远高于穷举法。 2025/4/6

2025/4/6 11 以上计算过程及结果，可用图2表示，可以看到，以上方法不仅 得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最 短路径。 以上过程，仅用了22次加法，计算效率远高于穷举法。 A B B C D B C D E C 4 1 2 3 1 2 3 1 2 3 3 2 1 6 4 7 2 4 8 3 8 6 7 5 1 6 10 6 0 10 6 12 11 11 12 13 14 14 B4 12 7 5 1 2