#.是什么：

动态规划--把多阶段过程转化为一系列单阶段问题，逐个求解，是求解决策过程（decisionprocess）最优化的数学方法。

#.为什么：

应用领域：

--经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

--动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

根据过程的时间变量是离散的还是连续的，分为离散时间决策过程（discrete-timedecision process）和连续时间决策过程（continuous-time decision process）；

根据过程的演变是确定的还是随机的，分为确定性决策过程（deterministicdecision process）和随机性决策过程（stochastic decision process），其中应用最广的是确定性多阶段决策过程。

#怎么做：

步骤

动态规划模型通常包含以下要素：（以题目展示）

1.阶段：阶段(step)是根据时间顺序或空间顺序特征对整个过程的自然划分。阶段变量一般用k=1,2,L,n表示。在例1中由A出发为k=1，由B(i=1,2)i出发为k=2，依此下去从F(i=1,2)i出发为k=6，共n=6个阶段。

2.状态：状态（state）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。

-状态变量：描述状态的变量，xk表示第k阶段的状态变量，它可以是一个数或一个向量。（小写x）

-允许状态集合：变量允许取值的范围，Xk表示第k阶段的允许状态集合。(大写X)

在例1可取B1,B2，或将Bi定义为i(i=1,2)，则=1或2，而X2={1,2}。

n个阶段的决策过程有n+1个状态变量，表示演变的结果。在例1中取G，或定义为1，即=1

3.决策：当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）。

-决策变量：描述决策的变量，

-允许决策集合：变量允许取值的范围

4.策略：

类似地，由第k到第j阶段的子过程的策略记作

5.状态转移方程

6.指标函数和最优值函数

指标函数

最优值函数

7.最优策略和最优轨线

8.递归方程:

动态规划递归方程是动态规划的最优性原理的基础，即：最优策略的子策略，构成最优子策略。

当⊗为加法时取()=0；当⊗为乘法时，取()=1

--用状态转移方程（1）和递归方程（2）求解动态规划的过程，是由k=n+1逆推至k=1，故这种解法称为逆序解法。

--对某些动态规划问题，采用顺序解法。这时，状态转移方程和递归方程分别为：

用lingo求解例1最短路线问题: