第十章动恋规期 §1多阶段决策过程最优化问题举例 §2基本概念、基本方程与最优化原理 §3动态规划的应用(1) §4动态规划的应用(2) 管理蓦
管 理 运 筹 学 1 第十章 动态规划 §1 多阶段决策过程最优化问题举例 §2 基本概念、基本方程与最优化原理 §3 动态规划的应用(1) §4 动态规划的应用(2)
§1多阶段决策过程最优化问题举例 例1最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最 短路径。 B 10 7 B 2 C 运莓
管 理 运 筹 学 2 §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
§1多阶段决策过程最优化问题举例 讨论: 1、以上求从A到E的最短路径问题,可以转化为四个性质完全相 同,但规模较小的子问题,即分别从D;、C;、B;、A到E的最短路 径问题。 第四阶段:两个始点D1和D2,终点只有一个; 表 10-1 阶段4 本阶段始点|本阶段各终点(决策)」到E的最短距离本阶段最优终点 (状态) E (最优决策) 10* 10 D 6 6 EE 分析得知:从D和D2到E的最短路径唯一 管理蓦
管 理 运 筹 学 3 §1 多阶段决策过程最优化问题举例 讨论： 1、以上求从A到E的最短路径问题，可以转化为四个性质完全相 同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路 径问题。 第四阶段：两个始点D1和D2，终点只有一个； 表10-1 分析得知：从D1和D2到E的最短路径唯一。 阶段4 本阶段始点 （状态） 本阶段各终点（决策） 到E的最短距离 本阶段最优终点 E （最优决策) D1 D2 10* 6 10 6 E E
§1多阶段决策过程最优化问题举例 第三阶段:有三个始点C1,C2,C3,终点有D1,D2,对始点 和终点进行分析和讨论分别求C1,C2,C3到D1,D2的最短路 径问题: 表10-2 阶段3 本阶段始点本阶段各终点(决策) 到E的最短距离本阶段最优终点 (状态) D D (最优决策) C 8+10=18 6+6=12 12 7+10=17 5+6=11 1+10=11 6+6=12 D 分析得知:如果经过C1,则最短路为C1-D2-E; 如果经过C2,则最短路为C2-D2E; 如果经过C3,则最短路为C3-D1-E。 管理蓦 4
管 理 运 筹 学 4 第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点 和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路 径问题： 表10-2 分析得知：如果经过C1，则最短路为C1 -D2 -E； 如果经过C2，则最短路为C2 -D2 -E； 如果经过C3，则最短路为C3 -D1 -E。 §1 多阶段决策过程最优化问题举例 阶段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
§1多阶段决策过程最优化问题举例 第二阶段:有4个始点B1,B2,B3,B4终点有C1C2C3。对始点和终点进行分 析和讨论分别求B1,B2B3,B到C1C2C3的最短路径问题: 表10-3 阶段2 本阶段始点 本阶段各终点(决策) 到E的最本阶段最优终 (状态) C C 短距离点(最优决策) 2+12=14 1+1=126+11-=17 12 BBBB 4+12=16 7+11=182+11=13 13 4+12=16 8+11=193+11=14 14 Cccc 4 7+12=195+11=161+1=12 12 分析得知:如果经过B1,则走B1-C2-D2-E; 如果经过B2,则走B2CxD1E; 如果经过B3,则走B3CxD1E 如果经过B,则走BrC3D1E
管 理 运 筹 学 5 第二阶段：有4个始点B1 ,B2 ,B3 ,B4，终点有C1 ,C2 ,C3。对始点和终点进行分 析和讨论分别求B1 ,B2 ,B3 ,B4到C1 ,C2 ,C3的最短路径问题： 表10-3 分析得知：如果经过B1，则走B1 -C2 -D2 -E； 如果经过B2，则走B2 -C3 -D1 -E； 如果经过B3，则走B3 -C3 -D1 -E； 如果经过B4，则走B4 -C3 -D1 -E。 §1 多阶段决策过程最优化问题举例 阶段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