Chapter06_动态规划
举例说明什么是多阶段的决策过程以及具有多阶段决策问题的特性？
什么是？ 一个过程可以分为多个阶段，在每个阶段都需要做出决策，且前一个决策的结果会成为后一个决策的起点；这样将一个问题看做一个前后关联具有链式结构问题称为多阶段过程。特性 各个阶段采取的决策，一般来说与时间相关，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生。例如 在寻找最短路时，可将其划分为多个不同阶段，且每一阶段的决策会成为下一阶段决策的起点。
解释以下概念
阶段
将说给问题的过程分为若干个相互联系的阶段，以便能按一定的次序求解。
描述阶段的变量，称为阶段变量 ，常用 k k k
状态
表示每个阶段开始所处的自然状态或客观条件，其描述了研究问题过程的状况，又称不可控因素。
描述状态的变量称为状态变量 。其可用一个数、一组数或一组向量来描述。常用 S k \mathbb{S}_k S k k k k
可达状态集 在某阶段下，可达到的状态的集合。此阶段的某状态 s k s_k s k s k ∈ S k s_k\in\mathbb{S}_k s k ∈ S k 此处的状态应该满足无后效性 ：某阶段的状态给定后，则此阶段以后过程的发展不收这个阶段以前各阶段的影响。
决策
处于某一阶段的某个状态时，可以做出不同的决定（或选择），从而确定下一阶段的状态，此种决定称为决策 。
描述决策的变量称为决策变量 ，其用一个数、一组数或一组向量表示。常用 u k ( s k ) u_k(s_k) u k ( s k ) k k k s k s_k s k
允许决策集合 实际问题中，决策变量的取值往往限制于某一范围之内，此范围称为允许决策集合 。常用 D k ( s k ) \mathbb{D}_k(s_k) D k ( s k ) k k k s k s_k s k u k ( s k ) ∈ D k ( s k ) u_{k}(s_k)\in \mathbb{D}_k(s_k) u k ( s k ) ∈ D k ( s k )
最优策略
策略 策略是按顺序排列的决策组成的集合。子策略 由过程第 k k k 后部子过程 （或 k k k { u k ( s k ) , ⋯ , u n ( s n ) } \{u_k(s_k),\cdots, u_n(s_n)\} { u k ( s k ) , ⋯ , u n ( s n )} k k k 子策略 ，记 p k , n ( s k ) p_{k,n}(s_k) p k , n ( s k ) p k , n ( s k ) = { u k ( s k ) , u k + 1 ( s k + 1 ) , ⋯ , u n ( s n ) } p_{k,n}(s_k) = \{u_{k}(s_k),u_{k+1}(s_{k+1}),\cdots, u_n(s_n)\} p k , n ( s k ) = { u k ( s k ) , u k + 1 ( s k + 1 ) , ⋯ , u n ( s n )} 全过程策略 当 k = 1 k=1 k = 1 p 1 , n ( s 1 ) p_{1,n}(s_1) p 1 , n ( s 1 ) p 1 , n ( s 1 ) = { u 1 ( s 1 ) , u 2 ( s 2 ) , ⋯ , u n ( s n ) } p_{1,n}(s_{1}) = \{u_{1}(s_1),u_{2}(s_2),\cdots, u_{n}(s_n)\} p 1 , n ( s 1 ) = { u 1 ( s 1 ) , u 2 ( s 2 ) , ⋯ , u n ( s n )} 可供选择的策略范围，称为允许策略集合 用 P \mathbb{P} P
从允许策略集合中找出达到最优效果的策略称为最优策略
状态转移方程
确定过程由一个状态到另一个状态的演变过程。若给定第 k k k s k s_k s k u k u_k u k k + 1 k+1 k + 1 s k + 1 s_{k+1} s k + 1 s k + 1 s_{k+1} s k + 1 s k s_k s k u k u_k u k s k + 1 = T k ( s k , u k ) s_{k+1}=T_{k}(s_k,u_k) s k + 1 = T k ( s k , u k )
指标函数 和最优值函数
指标函数 用于衡量所实现过程优劣的一种数量指标。是定义在全过程和所有后部子过程上所确定的数量指标。常用 V k , n V_{k,n} V k , n V k , n = V k , n ( s k , u k , s k + 1 , u k + 1 , ⋯ , s n + 1 ) , k = 1 , 2 , ⋯ , n V_{k,n}= V_{k,n}(s_k,u_k,s_{k+1},u_{k+1},\cdots,s_{n+1}),\ k= 1,2,\cdots,n V k , n = V k , n ( s k , u k , s k + 1 , u k + 1 , ⋯ , s n + 1 ) , k = 1 , 2 , ⋯ , n V k , n V_{k,n} V k , n s k s_{k} s k u k u_{k} u k V k + 1 , n V_{k+1,n} V k + 1 , n V k , n ( s k , u k , s k + 1 , ⋯ , s n + 1 ) = ψ k [ s k , u k , V k + 1 , n ( s k + 1 , ⋯ , s n + 1 ) ] V_{k,n}(s_k,u_k,s_{k+1},\cdots,s_{n+1}) = \psi_{k}[s_k,u_k,V_{k+1,n}(s_{k+1},\cdots,s_{n+1})] V k , n ( s k , u k , s k + 1 , ⋯ , s n + 1 ) = ψ k [ s k , u k , V k + 1 , n ( s k + 1 , ⋯ , s n + 1 )] 常见的指标函数形式
过程和其任意子过程的指标是其所包含各阶段的指标之和 V k , n ( s k , u k , s k + 1 , ⋯ , s n + 1 ) = ∑ j = k n v j ( s j , u j ) V_{k,n}(s_{k},u_k,s_{k+1},\cdots,s_{n+1})=\sum_{j=k}^{n}v_{j}(s_j,u_j) V k , n ( s k , u k , s k + 1 , ⋯ , s n + 1 ) = j = k ∑ n v j ( s j , u j ) v j ( s j , u j ) v_{j}(s_j,u_j) v j ( s j , u j ) j j j V k , n ( s k , u k , s k + 1 , ⋯ , s n + 1 ) = v k ( s k , u k ) + V k + 1 , n ( s k + 1 , u k + 1 , ⋯ , s n + 1 ) V_{k,n}(s_{k},u_k,s_{k+1},\cdots,s_{n+1}) = v_{k}(s_k,u_k) + V_{k+1,n}(s_{k+1},u_{k+1},\cdots,s_{n+1}) V k , n ( s k , u k , s k + 1 , ⋯ , s n + 1 ) = v k ( s k , u k ) + V k + 1 , n ( s k + 1 , u k + 1 , ⋯ , s n + 1 )
过程和其子过程的指标是其所包含各阶段指标之积 V k , n ( s k , u k , s k + 1 , ⋯ , s n + 1 ) = ∏ j = k n v j ( s j , u j ) V_{k,n}(s_{k},u_k,s_{k+1},\cdots,s_{n+1})=\prod_{j=k}^{n}v_{j}(s_j,u_j) V k , n ( s k , u k , s k + 1 , ⋯ , s n + 1 ) = j = k ∏ n v j ( s j , u j ) v j ( s j , u j ) v_{j}(s_j,u_j) v j ( s j , u j ) j j j V k , n ( s k , u k , s k + 1 , ⋯ , s n + 1 ) = v k ( s k , u k ) ⋅ V k + 1 , n ( s k + 1 , u k + 1 , ⋯ , s n + 1 ) V_{k,n}(s_{k},u_k,s_{k+1},\cdots,s_{n+1}) = v_{k}(s_k,u_k) \cdot V_{k+1,n}(s_{k+1},u_{k+1},\cdots,s_{n+1}) V k , n ( s k , u k , s k + 1 , ⋯ , s n + 1 ) = v k ( s k , u k ) ⋅ V k + 1 , n ( s k + 1 , u k + 1 , ⋯ , s n + 1 )
指标函数的最优值，称为最优值函数 ，记为 f k ( s k ) f_k(s_k) f k ( s k ) k k k s k s_k s k n n n f k ( s k ) = o p t { u k , ⋯ , u n } V k , n ( s k , u k , ⋯ , s n + 1 ) f_k(s_k) = \underset{\{u_k,\cdots,u_n\}}{\mathrm{opt}} V_{k,n}(s_k,u_k,\cdots,s_{n+1}) f k ( s k ) = { u k , ⋯ , u n } opt V k , n ( s k , u k , ⋯ , s n + 1 )
边界条件 最终阶段的最优值函数 f n + 1 ( s n + 1 ) f_{n+1}(s_{n+1}) f n + 1 ( s n + 1 ) 边界条件
建立动态规划模型时需要注意哪些点，他们在模型中的作用是什么？
注意事项
各阶段的状态应该满足无后效性 ，即某阶段的状态给定后，该阶段后的过程，不会收到该阶段之前各段状态的影响。即s k + 1 = T ( s k , u k ) s_{k+1} = T(s_k,u_k) s k + 1 = T ( s k , u k )
试述动态规划方法的基本思想，动态规划基本方程的结构、方程中各个符号的含义以及正确写出动态规划方程的关键要素
基本思想
动态规划方法的关键在于正确写出基本的递推关系式以及恰当的边界条件。要做到这一点，必须将问题的过程分为几个相互联系的阶段，恰当地选取状态变量和决策变量以及定义最优值函数，从而将一个大问题化为一族同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解
多阶段决策过程中，动态规划方法既是把当前一段和未来各段分开，又把当前效益和未来效益结合考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的
求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变化得到，从而确定最优路线。
基本方程
k k k k + 1 k+1 k + 1 递推式 ：f k , n ( s k ) = o p t u k ∈ D k ( s k ) { v k ( s k , u k ( s k ) ) + f k + 1 ( u k ( s k ) ) } , k = n , n − 1 , ⋯ , 1 f_{k,n}(s_k) = \underset{u_k\in\mathbb{D}_k(s_k)}{\mathrm{opt}}\{v_{k}(s_k,u_k(s_k)) + f_{k+1}(u_k(s_k))\},\ k =n,n-1,\cdots,1 f k , n ( s k ) = u k ∈ D k ( s k ) opt { v k ( s k , u k ( s k )) + f k + 1 ( u k ( s k ))} , k = n , n − 1 , ⋯ , 1 边界条件 f n + 1 ( s n + 1 ) = 0 f_{n+1}(s_{n+1}) = 0 f n + 1 ( s n + 1 ) = 0
正确写出规划方程的重要因素
将问题的过程划分为恰当的阶段
正确选择状态变量 s k s_k s k 无后效性
确定决策变量 u k u_k u k D k \mathbb{D}_k D k
正确写出状态转移方程
正确写出指标函数 V k , n V_{k,n} V k , n
是定义在全过程和所有后部子过程上的数量函数
具有可分离性，并满足地递推关系，即V k , n ( s k , u k , ⋯ , s n + 1 ) = ψ k [ s k , u k , V k + 1 , n ( s k + 1 , u k + 1 , ⋯ , s n + 1 ) ] V_{k,n}(s_k,u_k,\cdots,s_{n+1}) = \psi_k[s_k,u_k, V_{k+1,n}(s_{k+1},u_{k+1},\cdots,s_{n+1})] V k , n ( s k , u k , ⋯ , s n + 1 ) = ψ k [ s k , u k , V k + 1 , n ( s k + 1 , u k + 1 , ⋯ , s n + 1 )]
函数 ψ k ( s k , u k , V k + 1 , n ) \psi_k(s_k,u_k,V_{k+1,n}) ψ k ( s k , u k , V k + 1 , n ) V k + 1 , n V_{k+1,n} V k + 1 , n
试述动态规划的最优化原理，以及它同动态规划基本方程的之间的关系
最优性原理
“一个过程的最优策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。” 即 一个最优策略的子策略总是最优的；
其与动态规划基本方程的之间并不是无条件等价的，也不存在确定的蕴含关系。
是策略最优性必要条件
动态规划的最优性定理 （充要条件） 设阶段数为 n n n k = 0 , 1 , ⋯ , n k=0,1,\cdots,n k = 0 , 1 , ⋯ , n p 0 , n − 1 ∗ = ( u 0 ∗ , u 1 ∗ , ⋯ , u n − 1 ∗ ) p^*_{0,n-1}=(u_0^*,u_1^*,\cdots,u_{n-1}^*) p 0 , n − 1 ∗ = ( u 0 ∗ , u 1 ∗ , ⋯ , u n − 1 ∗ ) k k k 0 < k < n − 1 0<k<n-1 0 < k < n − 1 s 0 ∈ S 0 s_0\in\mathbb{S}_0 s 0 ∈ S 0 V 0 , n − 1 ( s 0 , p 0 , n − 1 ∗ ) = o p t p 0 , k − 1 ∈ p 0 , k − 1 ( s 0 ) { V 0 , k − 1 ( s 0 , p 0 , k − 1 ) + o p t p k , n − 1 ∈ p 0 , k − 1 ( s k ~ ) ( s k ~ , p k , n − 1 ) } \begin{split}V_{0,n-1}(s_0,p^*_{0,n-1}) = & \underset{p_{0,k-1}\in p_{0,k-1}(s_0)}{\mathrm{opt}}\{V_{0,k-1}(s_0,p_{0,k-1})+ \\& \underset{p_{k,n-1}\in p_{0,k-1}(\widetilde{s_k})}{\mathrm{opt}}(\widetilde{s_k},p_{k,n-1})\}\end{split} V 0 , n − 1 ( s 0 , p 0 , n − 1 ∗ ) = p 0 , k − 1 ∈ p 0 , k − 1 ( s 0 ) opt { V 0 , k − 1 ( s 0 , p 0 , k − 1 ) + p k , n − 1 ∈ p 0 , k − 1 ( s k ) opt ( s k , p k , n − 1 )} p 0 , n − 1 ∗ = ( p 0 , k − 1 , p k , n − 1 ) p^*_{0,n-1} = (p_{0,k-1},p_{k,n-1}) p 0 , n − 1 ∗ = ( p 0 , k − 1 , p k , n − 1 ) s k ~ = T k − 1 ( s k − 1 , u k − 1 ) \widetilde{s_k} = T_{k-1}(s_{k-1},u_{k-1}) s k = T k − 1 ( s k − 1 , u k − 1 ) s 0 s_0 s 0 p 0 , k − 1 p_{0,k-1} p 0 , k − 1 k k k
推论 若允许策略 p 0 , n − 1 ∗ p^*_{0,n-1} p 0 , n − 1 ∗ k , 0 < k < n − 1 k,\ 0<k<n-1 k , 0 < k < n − 1 p k , n − 1 ∗ p^*_{k,n-1} p k , n − 1 ∗ s k ∗ = T k − 1 ( s k − 1 ∗ , u k − 1 ∗ ) s_k^*=T_{k-1}(s^*_{k-1},u^*_{k-1}) s k ∗ = T k − 1 ( s k − 1 ∗ , u k − 1 ∗ ) k k k n − 1 n-1 n − 1
试述动态规划方法与逆推解法和顺推解法之间的联系及应注意之处
逆推解法 设已知初始状态 为 s 1 s_1 s 1 f k ( s k ) f_k(s_k) f k ( s k ) k k k s k s_k s k k k k n n n
从第 n n n f n ( s n ) = max x n ∈ D n ( s n ) v n ( s n , x n ) f_{n}(s_n) = \max_{x_{n}\in\mathbb{D}_n(s_n)} v_n(s_n,x_n) f n ( s n ) = x n ∈ D n ( s n ) max v n ( s n , x n ) D ( s n ) \mathbb{D}(s_n) D ( s n ) s n s_n s n n n n x n = x n ( s n ) x_n = x_{n}(s_n) x n = x n ( s n ) f n ( s n ) f_n(s_n) f n ( s n ) D n ( s n ) \mathbb{D}_n(s_n) D n ( s n ) x n ∈ D n ( s n ) x_{n}\in\mathbb{D}_n(s_n) x n ∈ D n ( s n ) x n = x n ( s n ) x_n=x_n(s_n) x n = x n ( s n )
在 n − 1 n-1 n − 1 f n − 1 ( s n − 1 ) = max x n − 1 ∈ D n − 1 ( s n − 1 ) [ v n − 1 ( s n − 1 , x n − 1 ) ⋅ f n ( s n ) ] f_{n-1}(s_{n-1}) = \max_{x_{n-1}\in\mathbb{D}_{n-1}(s_{n-1})} [v_{n-1}(s_{n-1},x_{n-1})\cdot f_{n}(s_n)] f n − 1 ( s n − 1 ) = x n − 1 ∈ D n − 1 ( s n − 1 ) max [ v n − 1 ( s n − 1 , x n − 1 ) ⋅ f n ( s n )] s n = T n − 1 ( s n − 1 , x n − 1 ) s_n = T_{n-1}(s_{n-1},x_{n-1}) s n = T n − 1 ( s n − 1 , x n − 1 ) x n − 1 = x n − 1 ( s n − 1 ) x_{n-1}=x_{n-1}(s_{n-1}) x n − 1 = x n − 1 ( s n − 1 ) f n − 1 ( s n − 1 ) f_{n-1}(s_{n-1}) f n − 1 ( s n − 1 )
在 k k k f k ( s k ) = max x k ∈ D k ( s k ) [ v k ( s k , u k ) ⋅ f k + 1 ( s k + 1 ) ] f_{k}(s_k) = \max_{x_{k}\in\mathbb{D}_k(s_k)}[v_{k}(s_k,u_k)\cdot f_{k+1}(s_{k+1})] f k ( s k ) = x k ∈ D k ( s k ) max [ v k ( s k , u k ) ⋅ f k + 1 ( s k + 1 )] s k + 1 = T k ( s k , x k ) s_{k+1} = T_{k}(s_k,x_k) s k + 1 = T k ( s k , x k ) x k = x k ( s k ) x_{k} = x_{k}(s_k) x k = x k ( s k ) f k ( s k ) f_{k}(s_k) f k ( s k )
如此类推，直到第一阶段，有 f 1 ( s 1 ) = max x 1 ∈ D 1 ( s 1 ) [ v 1 ( s 1 , x 1 ) ⋅ f 2 ( s 2 ) ] f_{1}(s_{1}) = \max_{x_{1}\in\mathbb{D}_{1}(s_1)}[v_1(s_1,x_1)\cdot f_{2}(s_2)] f 1 ( s 1 ) = x 1 ∈ D 1 ( s 1 ) max [ v 1 ( s 1 , x 1 ) ⋅ f 2 ( s 2 )] s 2 = T 1 ( s 1 , x 1 ) s_{2} = T_{1}(s_1,x_1) s 2 = T 1 ( s 1 , x 1 ) x 1 = x 1 ( s 1 ) x_{1}=x_1(s_1) x 1 = x 1 ( s 1 ) f 1 ( s 1 ) f_{1}(s_1) f 1 ( s 1 )
由于初始状态 s 1 s_1 s 1 x 1 = x 1 ( s 1 ) x_1=x_1(s_1) x 1 = x 1 ( s 1 ) f 1 ( s 1 ) f_1(s_1) f 1 ( s 1 ) s 2 = T 1 ( s 1 , x 1 ) s_2 = T_{1}(s_{1},x_1) s 2 = T 1 ( s 1 , x 1 ) x 2 = x 2 ( s 2 ) x_2=x_2(s_2) x 2 = x 2 ( s 2 ) f 2 ( s 2 ) f_{2}(s_2) f 2 ( s 2 )
顺推解法 设已知终止状态的 s n + 1 s_{n+1} s n + 1 f k ( s ) f_k(s) f k ( s ) k k k s s s 1 1 1 k k k
从第一阶段有f 1 ( s 2 ) = max x 1 ∈ D 1 r ( s 2 ) v 1 ( s 2 , x 1 ) f_{1}(s_2) = \max_{x_1\in\mathbb{D}_1^{r}(s_{2})} v_{1}(s_2,x_{1}) f 1 ( s 2 ) = x 1 ∈ D 1 r ( s 2 ) max v 1 ( s 2 , x 1 ) s 1 = T 1 r ( s 2 , x 1 ) s_{1} = T_{1}^r(s_{2},x_1) s 1 = T 1 r ( s 2 , x 1 ) x 1 = x 1 ( s 2 ) x_1=x_{1}(s_2) x 1 = x 1 ( s 2 ) f 1 ( s 2 ) f_{1}(s_2) f 1 ( s 2 ) D 1 r ( s 2 ) \mathbb{D}_1^r(s_2) D 1 r ( s 2 ) x 1 ∈ D 1 r ( s 2 ) x_1\in\mathbb{D}^r_1(s_2) x 1 ∈ D 1 r ( s 2 ) x 1 = x 1 ( s 2 ) x_{1} = x_{1}(s_2) x 1 = x 1 ( s 2 )
在第二阶段有f 2 ( s 3 ) = max x 2 ∈ D 2 r ( s 3 ) [ v 2 ( s 3 , x 2 ) ⋅ f 1 ( s 2 ) ] f_2(s_3) = \max_{x_{2}\in\mathbb{D}^r_2(s_3)}[v_{2}(s_3,x_2)\cdot f_{1}(s_2)] f 2 ( s 3 ) = x 2 ∈ D 2 r ( s 3 ) max [ v 2 ( s 3 , x 2 ) ⋅ f 1 ( s 2 )] s 2 = T 2 r ( s 3 , x 2 ) s_{2} = T_{2}^r(s_3,x_2) s 2 = T 2 r ( s 3 , x 2 ) x 2 = x 2 ( s 3 ) x_2 = x_{2}(s_3) x 2 = x 2 ( s 3 ) f 2 ( s 3 ) f_{2}(s_3) f 2 ( s 3 )
在 k k k f k ( s k + 1 ) = max x k ∈ D k r ( s k + 1 ) [ v k ( s k + 1 , x k ) ⋅ f k − 1 ( s k ) ] f_{k}(s_{k+1})=\max_{x_{k}\in\mathbb{D}^r_k(s_{k+1})}[v_{k}(s_{k+1},x_k)\cdot f_{k-1}(s_k)] f k ( s k + 1 ) = x k ∈ D k r ( s k + 1 ) max [ v k ( s k + 1 , x k ) ⋅ f k − 1 ( s k )] s k = T k r ( s k + 1 , x k ) s_{k} = T^r_{k}(s_{k+1},x_k) s k = T k r ( s k + 1 , x k ) x k = x k ( s k + 1 ) x_{k} = x_{k}(s_{k+1}) x k = x k ( s k + 1 ) f k ( s k + 1 ) f_k(s_{k+1}) f k ( s k + 1 )
如此类推到 n n n f n ( s n + 1 ) = max x n ∈ D n r ( s n + 1 ) [ v n ( s n + 1 , x n ) ⋅ f n − 1 ( s n ) ] f_{n}(s_{n+1}) = \max_{x_{n}\in\mathbb{D}^r_{n}(s_{n+1})}[v_{n}(s_{n+1},x_n)\cdot f_{n-1}(s_n)] f n ( s n + 1 ) = x n ∈ D n r ( s n + 1 ) max [ v n ( s n + 1 , x n ) ⋅ f n − 1 ( s n )] s n = T n r ( s n + 1 , x n ) s_{n} = T^r_n(s_{n+1},x_n) s n = T n r ( s n + 1 , x n ) x n = x n ( s n + 1 ) x_{n} = x_{n}(s_{n+1}) x n = x n ( s n + 1 ) f n ( s n + 1 ) f_{n}(s_{n+1}) f n ( s n + 1 )
由于终止状态 s n + 1 s_{n+1} s n + 1 x n = x x ( s n + 1 ) x_n = x_{x}(s_{n+1}) x n = x x ( s n + 1 ) f n ( n + 1 ) f_{n}(n+1) f n ( n + 1 )
联系 顺序解法和逆序解法在本质上并无区别，顺序解法相当于将现实的起点当做重点，将现实的终点当做起点，采用逆序方法求解。应注意的是 顺序解法是由 s k + 1 s_{k+1} s k + 1 x k x_k x k s k s_k s k s k s_k s k x k x_k x k s k + 1 s_{k+1} s k + 1
对静态规划的模型（如线性规划、非线性规划、整数规划等），一般可以采用动态规划的方法求解，对此你能否说一下各自的优缺点？
对于某些静态问题，可以人为引入时间因素，将其看作是按阶段进行的一个动态规划问题，这就使得动态规划成为求解某些线性、非线性规划的有效方法。