项多阶段决歌过程的圾优化 局部最优路径法:某人从k点 出发,并不顾及全线是否最短 只是选择当前最短途径 逢 近便走”,错误地以为局部最 优会致整体最优,在这种想法 指导下,所取决策必是1>V3 8 10 全程长度 是20:显然。这种方法的结果 常是错误的
16 1.多阶段决策过程的最优化 局部最优路径法：某人从k点 出发，并不顾及全线是否最短， 只是选择当前最短途径， “逢 近便走” ，错误地以为局部最 优会致整体最优，在这种想法 指导下，所取决策必是v1 →v3 →v5 → v8 → v10 ，全程长度 是20；显然，这种方法的结果 常是错误的．
1多阶段决过程的优化 动态规划方法:动态规均方法寻 求该最短路问题的基本思想是, 首先将问题划分为4个阶段,每 次的选择总是综合后继过程的一 并最优进行考處在各段所有可 能状态的最优后继过程都已求得 %的情况下,全程的最优路线也 随之得到(如图)
17 1.多阶段决策过程的最优化 动态规划方法：动态规划方法寻 求该最短路问题的基本思想是， 首先将问题划分为4个阶段，每 次的选择总是综合后继过程的一 并最优进行考虑，在各段所有可 能状态的最优后继过程都已求得 的情况下，全程的最优路线便也 随之得到（如图）
1.多阶段决敢过程的最化 (15) 12) 34 跳过过程 (5) (18) (15)4 12 12 11 3)3聊10 9)6 (12) 3 图运输网络动态规划方法求解图示
1.多阶段决策过程的最优化 图1 运输网络动态规划方法求解图示 跳过过程
1多阶殷决过程的录龙化 具体说,此问题先从0开始,因为v0是 终点。再无后继过程,故可以接着考虑第4阶 毅上所有可能状态,v的最优后续过程.因 为从v,巧到v的路线是唯一的,所以,v 最优决策和最优后继过程就是到vρ,它们 的最短距离分别是5和3。 接着考虚阶段3上可能的状态,而6,v 到v0的最优决策和最优后继过程.在状态V5 上,虽然到κ是8,到是9,但是综合考虑后 继过程整体最优,取最优决策是到ⅳ,最优后 继过程是V 最短距离是12.同 埋,状态v的最优决策是至;V的最优决 策是到vgo
19 1.多阶段决策过程的最优化 具体说，此问题先从v10开始，因为v10是 终点。再无后继过程，故可以接着考虑第4阶 段上所有可能状态v8 ,v9的最优后续过程．因 为从v8 ,v9 到v10的路线是唯一的，所以v8 ,v9 的最优决策和最优后继过程就是到v10 ，它们 的最短距离分别是5和3。 接着考虑阶段3上可能的状态v5 ,v6 , v7 , 到v10的最优决策和最优后继过程．在状态V5 上，虽然到v8是8，到v9是9，但是综合考虑后 继过程整体最优，取最优决策是到v9,最优后 继过程是v5→v9 → v10 ，最短距离是12．同 理，状态v6的最优决策是至v8 ；v7的最优决 策是到v9
项多阶段决歌过程的圾优化 同样,当阶段3上所有可能状恋的最 优后继过程都已求得后,便可以开始考慮 阶段2上所有可能状态的最优决策和最优 后继过程,如V的最优决策是到κ,最优路 线是v2→v→0,最短距离是15.依此 类推,最后可以得到从初始状态V的最优 决策是到v最优路线是→巧v→→Ⅵ0 全程的最短距离是18。图5-1中粗实线表 示各点到的最优路线,每点上方括号内的 数字表示该点到终点的最短路距离
20 1.多阶段决策过程的最优化 同样，当阶段3上所有可能状态的最 优后继过程都已求得后，便可以开始考虑 阶段2上所有可能状态的最优决策和最优 后继过程，如v2的最优决策是到v5,最优路 线是v2→v5→v9→v10 ，最短距离是15…依此 类推，最后可以得到从初始状态v1的最优 决策是到v3最优路线是v1→v3→v7→v9→v10 ， 全程的最短距离是18。图5—1中粗实线表 示各点到的最优路线，每点上方括号内的 数字表示该点到终点的最短路距离