多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即：Rk =gk(Sk,uk)i=k有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式NRe = Igk(Sk,uk)i=k
多阶段决策问题中，常见的目标函数形式 之一是取各阶段效应之和的形式，即: = = n i k k k k uk R g (s , ) 有些问题，如系统可靠性问题，其目标函 数是取各阶段效应的连乘积形式， = = n i k k k k uk R g (s , )
(7)最优解用fi(s）表示第k子过程指标函数R(Sk，Pk(s）在状态sk下的最优值，即：k = 1,2,...,nfk(sk)= opt (Rk(Sk,Pk(Sk))PkEPk (Sk)称fi(s)为第k子过程上的最优指标函数;与它相应的子策略pk(s)称为状态sk下的最优子策略，记为 pk*(sr)
(7) 最优解 用 fk (sk ) 表示第 k 子过程指标函数Rk (sk , pk (sk )) 在状态 sk 下的最优值，即: f (s ) opt {R (s ,p (s ))} k 1,2, ,n k k k k p P (s ) k k k K k = = 称 fk (sk ) 为第 k 子过程上的最优指标函数； 与它相应的子策略pk (sk ) 称为状态 sk 下的最 优子策略，记为 pk * (sk )
例 5.2用动态规划求解最短路问题65268511881065983691014789573841
例 5 .2 用动态规划求解最短路问题 2 5 8 6 14 10 9 1 3 8 8 7 7 8 8 6 5 6 11 7 9 5 1 3 4 6 5 7 9 8 10
最短路的求解阶段：可分为5个阶段,k=1,,5。状态:可用城市编号,S,={1},S,=[2,3,4}S3={5, 6, 7], S4=[8, 9}, Ss={10]决策：决策变量也可用城市编号；状态转移方程：Sk+1=uk;损益递推函数：(C, + fk+1(Sk+1)fr(sk)=min..ieDkjeDk+l
最短路的求解: 阶段: 可分为5个阶段, k = 1, ., 5。 状态: 可用城市编号, S1={1}, S2={2, 3, 4}, S3={5, 6, 7}, S4={8, 9}, S5={10} 决策: 决策变量也可用城市编号; 状态转移方程: sk+1= uk ; 损益递推函数: ( ) 1 ( 1 ) 1 + + = + + i j k k i D j D k k f s min c f s k k
k= 4f4 (8) = 10, f4 (9) = 14k=3fs(5)=min(6+f(8)=16*, 8+f4(9)=22)=16fs(6)=min[5+f4(8)=15*, 9+f4(9)=23}=15fs(7)=min[8+f4(8)=18, 3+f4(9)=17*}=17k=2f(2) = min[6+ fs(5), 8+ fs(6), 11+ fs(7) } =min[22*,23, 28} = 22
k = 4 f4 (8) = 10, f4 (9) = 14 k = 3 f3 (5)=min{6+f4 (8)=16*, 8+f4 (9)=22}=16 f3 (6)=min{5+f4 (8)=15*, 9+f4 (9)=23}=15 f3 (7)=min{8+f4 (8)=18, 3+f4 (9)=17*}=17 k = 2 f2 (2) = min{6+ f3 (5), 8+ f3 (6), 11+ f3 (7) } = min{22*, 23, 28} = 22