、决策和策略 Decision and Policy) 当各阶段的状态确定以后,就可以做出不同的决定或选择,从而确 定下一阶段的状态,这种决定就是决策。表示决策的变量称为决策变量, 常用Uk(Sk)表示第k阶段当状态为Sk时的决策变量,在实际问题中, 决策变量的取值是被限制在一定的范围内,我们称此范围为允许的决策集 合,用Dk(Sk)表示第k阶段从状态Sk出发时的允许决策集合,显然 有Uk(S1)∈D(SA)。 在例51中第二阶段如决定从B1出发,即s2=B1,可选择走C1或 C2,C3,即其允许的决策变量集合D2(B1){C1C2,C3}。如果我们选择 从C2走,则此时的决策变量可表示为UB1)=C2。所以,在这里决策变 量的取值实际上也是给定集合的一个元素 在各阶段决策确定以后,整个问题的决策序列就构成了一个策略,用 (U1,2,U)表示如对于例51、Pn(AB2CD2E)就是一个策略。 对于每个实际问题,可供选择的策略有一定范围,称为允许策略集合,用P 表示,使整个问题达到最优效果的策略就是最优策略。如对于例5.1总共 可有18个策略,但最优策略只有一个。 2021/2/24
2021/2/24 6 三、 决策和策略(Decision and Policy) 当各阶段的状态确定以后，就可以做出不同的决定或选择，从而确 定下一阶段的状态，这种决定就是决策。表示决策的变量称为决策变量， 常用Uk （ k s ）表示第 k 阶段当状态为 k s 时的决策变量，在实际问题中, 决策变量的取值是被限制在一定的范围内，我们称此范围为允许的决策集 合，用 Dk （ k s ）表示第 k 阶段从状态 k s 出发时的允许决策集合，显然 有Uk （ k s ）∈ Dk （ k s ）。 在例 5.1 中第二阶段如决定从 B1 出发，即 s2=B1，可选择走 C1 或 C2，C3，即其允许的决策变量集合 D2 (B1)={C1,C2,C3} 。如果我们选择 从 C2 走，则此时的决策变量可表示为 U2 (B1)=C2 。所以, 在这里决策变 量的取值实际上也是给定集合的一个元素。 在各阶段决策确定以后， 整个问题的决策序列就构成了一个策略 ,用 P1,n (U1 ,U2 ,…,Un ) 表示,如对于例 5.1, P1,n (A,B2,C1,D2,E)就是一个策略。 对于每个实际问题,可供选择的策略有一定范围 ,称为允许策略集合，用 P 表示，使整个问题达到最优效果的策略就是最优策略。如对于例 5.1 总共 可有 18 个策略，但最优策略只有一个
四、状态转移方程 在动态规划中,本阶段的状态往往是上阶段决策的结果。所以如果给 定了第k阶段的状态Sk和该阶段的决策Uk(Sk),则第k+1段的状态Sk 由于k阶段决策的完成也就完全确定了,它们之间的关系可用如下公式表示: SkHI=TK (Sk, UK) 其中,Tk表示从状态Sk出发经过Uk向下一阶段的转移( Transfer),换 言之,即Sk+1是从状态Sk出发经过决策Uk转移的结果 由于上式表示了由k段到第k+1段的状态转移规律,所以就称为状态 转移方程。在例51中状态转移方程即Sk+1=U 五、指标函数 用于衡量所选定策略优劣的数量指标称作指标函数。一个n阶段的决策 过程,从1到n叫作问题的原过程,对于任意一个给定的k(1≡k≡n),从k 段到第n段称为原过程的一个后部子过程用Vn(S1,Bn)表示初始状态为 s1采用策略Pn时原过程的效益值用kn(SA,Pn)表示在第k阶段状态 2021/2/24
2021/2/24 7 四、状态转移方程 在动态规划中，本阶段的状态往往是上阶段决策的结果。所以如果给 定了第 k 阶段的状态 k s 和该阶段的决策Uk ( k s )，则第 k+1 段的状态 k+1 s 由于 k 阶段决策的完成也就完全确定了 ,它们之间的关系可用如下公式表示： k+1 s ＝Tk （ k s ，U k ） 其中，Tk 表示从状态 k s 出发经过Uk 向下一阶段的转移(Transfer) ，换 言之，即 k+1 s 是从状态 k s 出发经过决策U k 转移的结果。 由于上式表示了由 k 段到第 k+1 段的状态转移规律，所以就称为状态 转移方程。在例 5.1 中,状态转移方程即 k+1 s ＝U k 。 五、指标函数 用于衡量所选定策略优劣的数量指标称作指标函数。 一个 n 阶段的决策 过程, 从 1 到 n 叫作问题的原过程,对于任意一个给定的 k(1 ≦k≦n),从 k 段到第 n 段称为原过程的一个后部子过程.用V1,n (s1,P1,n )表示初始状态为 s1采用策略 P1,n 时原过程的效益值,用Vk ,n （ k s ， Pk ,n ）表示在第 k 阶段状态
为Sk采用策略Pn时的后部子过程的效益值。最优指标函数记为f(Sk) 它表示从第k阶段的状态Sk出发采用最优策略Pkn到过程终止时的最佳效 益值,于是有下面的关系式: fr(sk)=vkn(sk, pk.n)=opt Vkn(Sk, Pkn) 其中,opt全称 optimization即最优化,在最大化时用max,在最小化时用 min。fk(Sk)也称作k阶段从状态Sk出发时的后部子过程的最佳效益值 当k=1时,f1(S1)就是从初始状态S1到全过程结束的整体最优指标函数。 在例51中指标函数就是距离。如在第2阶段,状态为B2时,V2,4(B2) 就表示从B2到E的可能距离,f2(B2则表示从B2到E的最短距离。本问 题的总目标是求f1(A),即从A到E的最短距离 2021/2/24 8
2021/2/24 8 为 k s 采用策略 Pk ,n 时的后部子过程的效益值。最优指标函数记为 ( ) k k f s , 它表示从第 k 阶段的状态 k s 出发采用最优策略 * pk ,n 到过程终止时的最佳效 益值,于是有下面的关系式： k f （ k s ）＝Vk ,n （ k s ， * pk ,n ）＝optVk ,n ( k s , Pk ,n ) 其中,opt 全称 optimization 即最优化，在最大化时用 max,在最小化时用 min。 k f （ k s ）也称作 k 阶段从状态 k s 出发时的后部子过程的最佳效益值, 当 k=1 时, ( ) 1 1 f s 就是从初始状态 s1 到全过程结束的整体最优指标函数。 在例 5.1 中,指标函数就是距离。如在第 2 阶段,状态为 B2 时,V2，4(B2) 就表示从 B2 到 E 的可能距离，f2(B2)则表示从 B2 到 E 的最短距离。本问 题的总目标是求 f1(A),即从 A 到 E 的最短距离
5.1.3最短路径问题的动态规划 为了求出例5.1的最短路线,一个简单的方法是,可以求出 所有从A到E的可能走法的路长并加以比较。不难知道,从A到 E共有18条不同的路线,每条路线有四个阶段,要做3次加法,要 求出最最短路线需做54次加法运算和17次比较运算,这叫做穷 举法。不难理解,当问题的段数很多,各段的状态也很多时这 种方法的计算量会大大增加,甚至使得寻优成为不可能。 下面应用动态规划方法求解例5.1。为了获得每一个后部 子过程的最佳效益值只能运用逆序递推方法求解即由最后 段到第一段逐步求出各点到终点的最短路线最后求出A点到E 点的最短路线。运用逆序递推方法的好处是可以始终盯住目 标不致脱离最终目标。例5.1是一个四阶段决策问题,一般可 分为四步: 第一步,从k-4开始状态变量S可取两种状态D1D2,它们到E点 的距离分别为4和3,这也就是由D和D2到终点E的最短距离 即f4(D1)=4,f(D2)=3 2021/2/24 9
2021/2/24 9 为了求出例5.1的最短路线,一个简单的方法是,可以求出 所有从A到E的可能走法的路长并加以比较。不难知道,从A到 E共有18条不同的路线,每条路线有四个阶段,要做3次加法,要 求出最最短路线需做54次加法运算和17次比较运算,这叫做穷 举法。不难理解,当问题的段数很多,各段的状态也很多时,这 种方法的计算量会大大增加,甚至使得寻优成为不可能。 下面应用动态规划方法求解例5.1。为了获得每一个后部 子过程的最佳效益值,只能运用逆序递推方法求解,即由最后一 段到第一段逐步求出各点到终点的最短路线,最后求出A点到E 点的最短路线。运用逆序递推方法的好处是可以始终盯住目 标,不致脱离最终目标。例5.1是一个四阶段决策问题,一般可 分为四步： 第一步,从k=4开始,状态变量s4可取两种状态D1 ,D2 ,它们到E点 的距离分别为4和3,这也就是由D1和D2到终点E 的最短距离 即 f4 (D1 )=4, f4 (D2 )=3。 5.1.3 最短路径问题的动态规划
第二步,k=3,状态变量s3可取3个值即C1,C2和C3,这是需经过一个 中间站才能到达终点E的二级决策间题为方便应用,规定用ds,U)表 示由状态Sk出发,采用决策Uk到达下一阶段Sk1时的两点距离。显然从C1 到E有两条路线需加以比较,取其中最短的,即: f 3(Cl)=min d(C1,D)+f(D)3+4 ld(ci d,)+f(d - min =7 5+3 这说明,由C1到E的最短距离为7,其路径为以C1→D1→E,相应的决策 为U3(C1)=D1 5,(C,)-min1 ∫d(C2,D)+f4(D)6+4 -min d(C2,D2)+f4(D2) 2+3 即从C2到E的最短距离为5,其路径为C2→D2→E,相应的决策为 U3(C2)=D 2021/2/24 10
2021/2/24 10 第二步,k=3, 状态变量 s3 可取 3 个值即 C1,C2 和 C3,这是需经过一个 中间站才能到达终点 E 的二级决策问题。为方便应用，规定用 d( k s ,Uk )表 示由状态 k s 出发,采用决策U k 到达下一阶段 k+1 s 时的两点距离。显然从 C1 到 E 有两条路线需加以比较,取其中最短的,即： 3 f （C1）＝min + + ( , ) ( ) ( , ) ( ) 1 2 4 2 1 1 4 1 d C D f D d C D f D =min + + 5 3 3 4 =7 这说明,由C1 到 E 的最短距离为 7,其路径为以C1 → D1 →E,相应的决策 为 * U3 （C1）= D1 3 f （C2 ）＝min + + ( , ) ( ) ( , ) ( ) 2 2 4 2 2 1 4 1 d C D f D d C D f D =min + + 2 3 6 4 =5 即从 C2 到 E 的最短距离为 5,其路径为C2 → D2 →E,相应的决策为 * U3 （C2 ）= D2