在多数实际问题中， 级决策的性能指标 取如下形式
是由某级状态和决策决定的性能函数，要求
寻找决策
使J取极小值 。
最优性原理可表示为
根据上式就可证明最优性原理的正确性。若以 为
初态时，余下的决策
不是最优的
，那么就存在另一决策序列
所决定
的指标值
，于是
这与
是极小值发生矛盾，所以余下的决策必须
是最优的。
。两种路线
最优决策为
。
由 到 只有一种路线
，
其时间为 由 到E也只有一种路线 C3D2E ， 其时间为
n=3（倒数第三段）
从B2到E有两种路线：
和
最短时间为： 最优决策
n=4（倒数第四段 ）
从A到E的路线有两种：
和
。
最优决策为
至此求出了A到E的最短时间为9，最优路线
为
。在图中用粗线表示。这里，为
令
表示从点 到点
例如，从 到 的时间为
的时间。
有了这些术语后，就可用动态规划来解这
个例子。从最后一段出发进行计算，并将
计算出的最短时间
用括号表示在相
应的点 处（见图6-1）。
n=1 （倒数第一段）
考虑从 和 到 最短时间分别为
的路线，由定义可知，
n=2（倒数第二段）考虑从
到 的路线。
由 到 有两种路线： ， 中的最短时间由下式确定：
令 表示由某点 到终点的段数（如 到 为2
段，
。
令 表示当前所处点的位置（如 为状态变量。
），称
令 为决策（控制）变量，它表示当处在 位置而还有 段要走时，所要选取的下一点。 例如，从 出发，下一点为 时，则表示为
。
令 表示在位置 ，向终点还有 段要走时 ，由 到终点 的最短时间。 例如，从C2到E的最短时间为4，可表示为 T2(C2)=4。
显然当段数很多时，计算量是很大的。这种方 法的特点是从起点站往前进行，而且把这四级决 策一起考虑。应注意从到 下一站 所花的时 间为1，而到 所花时间为3，但最优路线却不 经过 。
这说明只看下一步的“眼前利益”来作决策是 没有意义的。
对比一下最开始的例子
为将问题表达得清楚，引进下面的术语（写法并不 完全一样）。
从哪下手？
3 5 4
从最后一级开始计算：
9
1
4
5
5
2
4
8
6
1
3
4
5
6
9
2
4
7
1
4
5
7
2
WN(x)：表示从状态x到终点F的N级过程的最短距离； SN (x)：决策变量，表示当处于状态x，还有N级时，所选取的下一个点 ；
同理
9
1
4
3
5
5
2
4
8
5
3
4
6
1
4
5
6
9
2
1
44
7
2
7 5
所以，最短路线为
最短距离为14
最优控制序列为 最优性能指标为
连续系统的动态规划
设系统的状态方程和性能指标为
（6-19）
（6-20）
受约束，可写成
为某一闭集。要寻找
满足此约束且使 最小的最优控制 。
设时间 在区间
内，则根据最优性原理，从
到 这一段过程应当是最优过程。把这段最优
指标写成
,则
（6-21）
显然 满足终端条件
通常假定 。
6-2 离散最优控制问题
设控制系统的状态方程为
式中x(k)是k时刻的几维状态向量，u(k)是k时刻的p维容许控制向量，设系 统在每一步转移中的性能指标为F[x(k),u(k)]
如在u(0)的作用下
在u(1)的作用下
对N级决策过程
性能指标
要求选择控制序列 根据最优性原理
使性能指标达到极小
解上述递推方程，即可获得最优控制序列。
最优控制动态规划1
最短路线问题
问题: 要求从A地到F地，选择一条最短的线路。
9
1
4Leabharlann 3552
1
4
8
6
5
3
4
5
6
9
2
4
4
1
4
7
2
7 5
为了便于分析，引入几个符号：
N：从某点到终点之间的级数； x：表示在任一级所处的位置，称为状态变量； SN (x)：决策变量，表示当处于状态x，还有N级时，所选取的下一个点； WN(x)：表示从状态x到终点F的N级过程的最短距离； d(x, SN)：表示从状态x到点SN的距离。
图6-2 最优性原理示意图
动态规划的特点：
一是它从最后一级反向计算； 二是其将一个N级决策问题化为N个单级决策问题 。 好处：将一个复杂问题化为多个简单问题加以求解 。
最优性原理
贝尔曼的最优性原理可叙述如下： “一个多级决策问题的最优决策具有这样的性质：当 把其中任何一级及其状态作为初始级和初始状态时， 则不管初始状态是什么，达到这个初始状态的决策是 什么，余下的决策对此初始状态必定构成最优策略。 ”
一个N级最优过程，不管第一级决策如何，其余N-1级，决策过程至少必须依据 第一级决策所形成的状态组成一个N-1级最优过程，在此基础上，在选择第一级 决策，使总的N级过程为最优。
这种递推关系可以用下列递推方程式来表达：
是不是穷举法？
再看一个例子
最短时间问题
问题：设有人要从 A 点开车到 E 站，中间要经过任意三个中 间站，站名在图中圆圈内表示。站与站之间称为段，每段路 程所需时间（小时）标在段上。现要问，这人应如何选择路 线才能最快到达目的地？
决定最优路线进行了10次加法，比穷举法的18次
少了8次。当段数n更多时，节省计算将会更多。
以上面的最短时间问题为例，如把 当作初
始状态，则余下的决策
对 来讲是最优策略
；如把 当初始状态，则余下的决策
对
来讲也构成最优策略。一般来说，如果一个最优过
程用状态
来表示，最优决策为
，则对状态 来讲，
必定是最优的，这可用图6-2来表示。
例6-1 设一阶离散系统的状态方程为
初始条件为x(0)，控制变量u不受约束，性能指标为
求最优控制u*(t)，使J达最小，为简便起见，设N＝2 解 设在u(0)、u(1)作用下，系统状态为x(0)、x(1)、x(2) 先考虑从x(1)到x(2)的情况，控制为u(1)
再考虑从x(0)到x(1)的情况，控制为u(0)
对 及 的二阶偏导数存在且有界
现在，考虑系统从 出发，到 分两步走：先从 到 ，再 从到 ， 是小量，则
根据最优性原理，从 。
（6-23） 也应是最优过程
因
故
这样，式（6-23）可写成
什么是穷举法?
从 走到 一共有六条路线，每条路 线由四段组成。这六条路线和对应的行车时间 如下
路线
显然最优路线是
行车时间（小时） 13 11 14 13 12 9
，它所花时间为9小时。
这里每条路线由四段组成，也可以说是四级决 策。
为了计算每条路线所花时间，要做三次加法运 算，为了计算六条路线所花的时间要作3×6=18次 运算。这种方法称为“穷举法”。