§2基本概念、基本方程与最优化原理 用逆序法列表求解右例 k==5时,f5(v10)=0 k=4,递推方程为 阶段 f4(S4)=min{v2(s4,x4)+fs(S5)}1:1 x4∈D4(S4) D4(S4) 4s→x)v(s4x)+5(s)f⑤)最优决策x V7 10 v1 5 5+0=5 v→>v10 v8→>v10 10 8 8+0=8 ν→)v 10 v→>v v 10 4+0=4 vo→)v 10 运筹
管 理 运 筹 学 11 §2 基本概念、基本方程与最优化原理 用逆序法列表求解右例 k=n=5 时，f5 (v10)＝0 ( ) min { ( , ) ( )} 4 4 4 5 5 ( ) 4 4 4 4 4 f s v s x f s x D s = + k=4，递推方程为 s4 D4 (s4 ) s5 v4 (s4 ,x4 ) v4 (s4 ,x4 )+f5 (s5 ) f4 (s4 ) 最优决策x4 * v7 v7→v10 v10 5 5+0=5* 5 v7→ v10 v8 v8→v10 v10 8 8+0＝8 * 8 v8→ v10 v9 v9→v10 v10 4 4+0=4* 4 v9→ v10
§2基本概念、基本方程与最优化原理 k=3,递推方程为 f3(S3)=min{v3(S3,x3)+f4(s4) x3∈D3(S3) 表10-2 sD2()s:n3x)3)s)s)最优决策x vs→>v V72 2+5=7* v8 8+8=16 5→v7 v5→vgv6 6+4=10 12 12+5=17 5+8=13 12 v9 8 8+4=12 管理蓦 12
管 理 运 筹 学 12 §2 基本概念、基本方程与最优化原理 ( ) min { ( , ) ( )} 3 3 3 4 4 ( ) 3 3 3 3 3 f s v s x f s x D s = + k=3，递推方程为 表10-2 s3 D3 (s3 ) s4 v3 (s3 ,x3 ) v3 (s3 ,x3 )+f4 (s4 ) f3 (s3 ) 最优决策x3 * v5 v5→v7 v 5→v8 v 5→v9 v7 v8 v9 2 8 6 2+5=7* 8+8=16 6+4=10 7 v5→v7 v6 v6→ v7 v 6→v8 v 6→v9 v7 v8 v9 12 5 8 12+5=17 5+8=13 8+4=12* 12 v6→v9
§2基本概念、基本方程与最优化原理 k=2,递推方程为 f2(S2)=min{v2(S2,x2)+f3(s3) x2∈D2(2) 表10-3 D2()5(x)吗2)())最优决策 2→>v5v 10+7=17 v2→vv13 13+12=25 17 v2→>v5 v→v 7 7+7=14 3 v3→>v6|v10 10+12=22 14 v→>v5 4→>v5vs13 13+7=20* → 11+12=23 20 理蓦总 13
管 理 运 筹 学 13 §2 基本概念、基本方程与最优化原理 k=2，递推方程为 表10-3 s2 D2 (s2 ) s3 v2 (s2 ,x2 ) v2 (s2 ,x2 )+f3 (s3 ) f2 (s2 ) 最优决策x2 * v2 v2→ v5 v2→ v6 v5 v6 10 13 10+7=17* 13+12=25 17 v2→ v5 v3 v3→ v5 v3→ v6 v5 v6 7 10 7+7=14* 10+12=22 14 v3→v5 v4 v4→ v5 v4→ v6 v5 v6 13 11 13+7=20* 11+12=23 20 v4→v5 ( ) min { 2 ( 2 , 2 ) 3 ( 3 )} ( ) 2 2 2 2 2 f s v s x f s x D s = +
§2基本概念、基本方程与最优化原理 k=1,递推方程为 f1(S1)=min{v1(S12x1)+f2(S2)} x1∈D1(S1) 表10-4 D1() 11r)v(s11)+f(2)f(s)最优决策x v1→>v2 285 2+17=19 19 v1→>v2 v1→>Y3吟3 8+14=22 v1→>v4 5+20=25 最优值是表8-4中f(s1)的值,从v1到v10的最短路长为19。最短路 线从表8-4到表8-1回朔,査看最后一列最优决策,得到最短路 径为: v1→>v→v5→W→>v10 运筹
管 理 运 筹 学 14 §2 基本概念、基本方程与最优化原理 k=1，递推方程为 表10-4 ( ) min { 1 ( 1 , 1 ) 2 ( 2 )} ( ) 1 1 1 1 1 f s v s x f s x D s = + s1 D1 (s1 ) s2 v1 (s1 ,x1 ) v1 (s1 ,x1 )+f2 (s2 ) f1 (s1 ) 最优决策x1 * v1 v1→v2 v1→v3 v1→v4 v2 v3 v4 2 8 5 2+17=19* 8+14=22 5+20=25 19 v1→v2 最优值是表8-4中f1 (s1 )的值，从v1到v10的最短路长为19。最短路 线从表8-4到表8-1回朔，查看最后一列最优决策，得到最短路 径为： v1→ v2 → v5 → v7 → v10
§2基本概念、基本方程与最优化原理 、最优化原理 作为整个过程的最优策略具有如下性质: 不管在此最优策略上的某个状态以前的状 态和决策如何,对该状态来说,以后的所有决 策必定构成最优子策略。就是说,最优策略的 任意子策略都是最优的。 管理蓦 15
管 理 运 筹 学 15 三、最优化原理 作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状 态和决策如何，对该状态来说，以后的所有决 策必定构成最优子策略。就是说，最优策略的 任意子策略都是最优的。 §2 基本概念、基本方程与最优化原理