运筹学动态规划.ppt

管理运筹学 1第十章动态规划§1 多阶段决策过程最优化问题举例§2 基本概念、基本方程与最优化原理§3 动态规划的应用(1) §4 动态规划的应用(2) 管理运筹学 2 §1 多阶段决策过程最优化问题举例例1 最短路径问题下图表示从起点 A到终点 E之间各点的距离。求 A到E的最短路径。 B A C BD B CD E C 4 123 123 12 32 2164724 83 86756 1 10 6 4? 3751管理运筹学 3 §1 多阶段决策过程最优化问题举例用穷举法的计算量:如果从 A到E的站点有 k个,除 A、E之外每站有 3个位置则总共有 3 k-1×2条路径; 计算各路径长度总共要进行(k+1) 3 k-1×2次加法以及 3 k- 1× 2-1 次比较。随着 k 的值增加时,需要进行的加法和比较的次数将迅速增加; 例如当 k=20 时,加法次数为 ×10 15次, 比较 ×10 14次。若用 1亿次/秒的计算机计算需要约 508 天。管理运筹学 4 §1 多阶段决策过程最优化问题举例讨论: 1、以上求从 A到E的最短路径问题,可以转化为四个性质完全相同,但规模较小的子问题,即分别从 D i、C i、B i、A到E的最短路径问题。第四阶段:两个始点 D 1和D 2,终点只有一个; 表 10-1 分析得知:从 D 1和D 2到E的最短路径唯一。阶段 4 本阶段始点(状态) 本阶段各终点(决策) 到E的最短距离本阶段最优终点(最优决策) E D 1 D 2 10 * 6 10 6 E E 管理运筹学 5 第三阶段:有三个始点 C 1,C 2,C 3,终点有 D 1,D 2,对始点和终点进行分析和讨论分别求 C 1,C 2,C 3到D 1,D 2的最短路径问题: 表 10-2 分析得知:如果经过 C 1,则最短路为 C 1 -D 2 -E; 如果经过 C 2,则最短路为 C 2 -D 2 -E; 如果经过 C 3,则最短路为 C 3 -D 1 -E。§1 多阶段决策过程最优化问题举例阶段 3 本阶段始点(状态) 本阶段各终点(决策) 到E的最短距离本阶段最优终点(最优决策) D 1 D 2 C 1 C 2 C 3 8+10=18 7+10=17 1+10=11 6+6=12 5+6=11 6+6=12 12 11 11 D 2 D 2 D 1 管理运筹学 6 第二阶段:有 4个始点 B 1,B 2,B 3,B 4,终点有 C 1,C 2,C 3。对始点和终点进行分析和讨论分别求 B 1,B 2,B 3,B 4到C 1,C 2,C 3的最短路径问题: 表 10-3 分析得知:如果经过 B 1,则走 B 1 -C 2 -D 2 -E; 如果经过 B 2,则走 B 2 -C 3 -D 1 -E; 如果经过 B 3,则走 B 3 -C 3 -D 1 -E; 如果经过 B 4,则走 B 4 -C 3 -D 1 -E。§1 多阶段决策过程最优化问题举例阶段 2 本阶段始点(状态) 本阶段各终点(决策) 到E的最短距离本阶段最优终点(最优决策) C 1 C 2 C 3 B 1 B 2 B 3 B 4 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 C 2 C 3 C 3 C 3 管理运筹学 7 第一阶段:只有 1个始点 A,终点有 B 1,B 2,B 3,B 4。对始点和终点进行分析和讨论分别求 A到B 1,B 2,B 3,B 4的最短路径问题: 表 10-4 最后,可以得到:从 A到E的最短路径为 A? B 4? C 3? D 1? E