matlab求动态规划最优解 .pdfVIP

matlab求动态规划最优解

求解步骤：

（1）将过程划分为恰当的阶段。

（2）选择状态变量Xk，使它既能描述过程的状态，又满足无后

效性，同时确定允许状态集合Xk。

（3）选择决策变量Uk，确定允许决策集合Uk（Xk）。

（4）写出状态转移方程。

（5）确定阶段指标Vk（xk，Wx）及指标函数Vkn的形式。

（6）写出基本方程即最优值函数满足的递归方程，以及端点条

件。

例题：最短路线问题

阶段按过程的演变划分，状态由各段的初始位置确定，决策为从

各个状态出发的走向，即有Xk+1=Uk（Xk），阶段指标为相邻两段状

态间的距离dk（Xk，Uk（Xk）），指标函数为阶段指标之和，最优值

函数fk（Xk）是由出发Xk到终点的最短距离（或最小费用），基本

方程为：

fk（Xk）=min[dk（Xk，Uk（Xk））+fk+1（Xk+1）]，k=n，n-1...，

2，1，fn+1（Xn+1）=0

利用这个模型可以算出例1的最短路线为AB1C2D1E2F2G，相应

的最短距离为18。

动态规划的最优性原理：

无论过去的状态跟决策如何，对前面的决策所形成的状态而言，

后续决策必须构成最优策略。

对于动态规划而言，重要的并不是所谓的模板，比较重要的是在

动态规划中，推导的思维方式。在个人看来动态规划实际就是编程解

决大量数据的决策问题的一种重要编程理念和编程思路。

在动态规划的思路即是反向确立后三次状态改变的两次决策量

的最优决策，确定了该最优决策之后每次反向推导一步，穷举倒数第

三次的不同决策所带来的状态变化量，与之前所得到的的最优决策量

进行加成处理（可能加和也可能相减或相乘相除，具体视情况而定），

将所得后三次决策的总决策量对比选取最优值，作为后四步的最优状

态变化值。先前重复推导，最终得到该问题的最优策略。