运筹学动态规划

运筹学动态规划第7章动态规划动态规划是Bellman 在1957年提出的解多阶决策问题的方法，在那个时期，线性规划很流行，它是研究静态问题的，而Bellman 提出的解多阶决策问题的方法适用于动态问题，相对于线性规划研究静态问题，取名动态规划。

动态规划方法应用范围非常广泛，方法也比较简单。

动态规划是将一个多阶决策问题分解为一系列的互相嵌套的一步决策问题，序贯求解使问题得到简化。

动态规划问题按照问题的性质可以分为确定性的和随机性的，按决策变量的和状态变量的取值可以分为离散型的和连续型的。

此外还有依据时间变量连续取值还是离散取值又分为连续时间动态规划问题和离散时间动态规划问题。

本章重点讨论离散时间确定性动态规划问题，包括状态变量和决策变量连续取值和离散取值两种情况。

7.1解多阶决策问题的动态规划法1.多阶决策问题的例(1)最优路径问题—多阶决策问题的例为了直观，先从最优路径问题谈起，它可以看作一个多阶决策过程。

通过最优路径问题的解可以看到用动态规划法解多阶决策问题的基本思想。

考虑图7-1所示的最优路径问题。

一汽车由S 点出发到终点F ，P 和Q 是一些可以通过的点。

图中两点间标出的数字是汽车走这一段路所需的时间(单位为小时)。

最优路径问题是确定一个路径，使汽车沿这条路径由S 点出发达到F 点所用时间最短。

最优路径问题可以看作一个多阶决策问题，由S 到城市甲是第1个阶段，第1个结点P 1或第2个结点Q 1做为第1阶段可以通过的两个站点，由城市甲到城市乙是第2阶段，这个阶段是从P 1或Q 1到P 2或Q 2，由城市乙到城市丙是第3阶段，这个阶段是从P 2或Q 2到P 3或Q 3，由城市丙的P 3或Q 3到F 做为第四阶段。

（2）最优路径问题的解对最优路径问题，存在一个非常明显的原理，即最优路径的一部分还是最优路径。

换句话说，如果SQ P Q F 123是所求的最优路径，那么，汽车从这一路径上的任何一点，例如P 2，出发到F 的最优路径必为P Q F 23。

这一原理称为最优性原理。

根据这一原理可以由后向前递推求出最优路径。

如果汽车已到Q 3，由Q 3直接到F 用3小时，如果汽车已到P 3，由P 3直接到F 用4小时，这两个数字分别标在图7-2中Q 3和P 3旁的方括号内。

再向前推一步，设汽车已在2Q ，1441P 2P 3P 1Q 2Q 3Q 422166753S F 图7-1最优路径问题经P 3需2+4=6小时，经Q 3需2+3=5小时。

这样从Q 2出发经Q 3到F 所需时间最短，需5小时。

将5记在Q 2旁的括号内，经Q 3到达F ，将Q 3标在括号的下角。

类似的可计算出汽车分别从P 2，Q 1，P 1，S 出发达到F 所需的最短时间及路径，见图7-2。

由图7-2可以看出，汽车从S 出发达到F 的最优路径是SQ P Q F 123，需时13小时。

不仅如此，由图7-2还可以看到汽车从任何一点出发到达F 点最短路径，及与它相应的最短时间。

按构造图7-2的方法共需10次加法。

如将所有的路径一一列出则需24次加法。

上面的求最优路径的方法，是把一个四阶段的最优决策问题，化成四个互相嵌套的子问题逐一求解，从而使问题得到简化，这种方法称为动态规划法。

为了说明动态规划方法的优点，我们将应用决策树法的情况画到图9.3中，可以看到用决策树法运算量比用动态规划法大得多。

由图9.3可以看出决策树法是算出所有可能的路径所需的时间，最后从中选出最优路径，动态规划法则是从后面向前递推。

每阶段计算过的结果不在重复计算，从而减少了计算量。

1442]10[1P P 3]4[2Q P ]4[3P 2]8[1P Q 3]5[2Q Q ]3[3Q 4221667531]13[Q S F 图7-2最优路径问题的2.应用动态规划解多阶决策问题的基本特征动态规划是解多阶决策问题的一种方法。

它可以求解的问题有如下特征：决策问题可以分成若干个阶段，每个阶段有若干与该阶段有关的状态和需要做的决策，系统从一个阶段的状态按一定的规律转移到下一个阶段的状态，多阶决策问题是求一个由每个阶段的决策构成的最优策略使得按决策目标最好。

应用动态规划解多阶决策问题有如下基本特征：（1）问题可以依时间顺序或空间的自然特征划分为几个阶段，每个阶段有一个决策变量需要作出决策。

用k 表示阶段数，用)(k u 表示第k 阶段的决策变量。

（2）动态规划中本阶段状态往往是上一阶段的状态和上一阶段的决策进行综合的结果．每个阶段作出决策后，使得当前的状态)(k x 转移到下一阶段的状态)1(+k x)),(),(()1(k k u k x f k x =+ 1,,2,0-=N k函数)),(),((k k u k x f 决定了这一转移过程，称它为转移函数。

这个方程称为状态转移方程简称状态方程。

状态方程是研究对象的内在规律的数学描述，也称为研究对象的数学模型。

（3）每个阶段的决策变量的集合构成多阶决策问题的一个策略)}1(,),1(),0({-N u u u按照决策的目标，引进一个用于衡量所选定策略优劣的数量指标称为指标函数．一些决策过程的指标函数越大越好（例如指标函数是利润、产值等），另一些决策过程的指标函数越小越好（例如指标函数是成本、误差等）。

使得指标函数最大（或最小）的策略称为最优策略。

最优策略常记为)}1(*,),1(*),0(*{-N u u u（4）以)),(),((k k u k x L 表示第k 阶段的指标函数，则N 阶决策过程的指标函数为∑-==10)),(),((N k N k k u k x L J3.多阶段决策问题的一般提法图最短线路问题中的决策树4665744315 1111111第一第二第三第四设多阶决策问题状态方程为x k f x k u k k ()((),(),)+=1 （7-1）指标函数为∑-==1)),(),((N k N k k u k x L J （7-2）其中u k ()为决策变量。

多阶段决策问题是求一个策略:u ()0，u ()1，…，u N ()-1，使得指标函数J N 最大(或最小)。

使得指标函数J N 最大(或最小)的策略称为最优策略，常记为)1(*,),1(*),0(*-N u u u为了讨论简单，假设函数f 和L 都不依赖于时间变量，设状态方程为x k f x k u k ()((),())+=1 （7-3）指标函数为J L x k u k N k N ==-∑((),())01（7-4）我们遇到的多数问题属于这种情况。

假设系统的初始状态给定为x x ()00=，在指标函数中逐次应用状态方程，可得到N 步决策的指标函数的值为J L x u L x u L x N u N L x u L f x u u N =+++--=++((),())((),())((),())((),())(((),()),())00111100001经逐次代入可得到J J x u u u N N N =-((),(),(),())0011如果已经求出了使N J 最大（或最小）的最优策略u *(),0u *(),1 ,u N *-()1，那么，将它们代入上式，就得到控制N 步的指标函数的最大值(或最小值)。

由于)1(*,),1(*),0(*-N u u u 已确定，N J 只依赖于x ()0，记为J x N * (())0，即))1(*,),1(*),0(*),0(())0((-=*N u u u x J x J N N一般地，初始条件为)(i x 时，i N -步决策的指标函数为∑-=-=1))(),((N ik i N k u k x L J如果已经求出了使i N J -最大（或最小）的最优策略)1(*,),1(*),(*-+N u i u i u ，那么，将它们代入上式，就得到控制i N -步的指标函数的最大值(或最小值)。

由于)1(*,),1(*),(*-+N u i u i u 已确定，N J 只依赖于)(i x ，记为))((i x J i N *-，即))1(*,),1(*),(*),(())((-+=*-N u i u i u i x J i x J N i N 简记为))((i x J i N *-))((i x J i N *-是第i 阶段状态为)(i x 指标函数的最优值，称为最优值函数。

4.动态规划的基本方程—Bellman 方程(1)最优性原理在最短路径问题中讲的最优性原理，对于一般多阶段决策问题也成立。

多阶段决策问题的最优性原理，可用一句话概括：最优策略序列的一部分也构成一个最优策略序列。

更具体的可叙述为如下的定理。

最优性原理：如果),0(*u ),1(*u ,)1(*-N u 是最优策略序列，那么它的一部分),1(*u ,)1(*-N u 也是一个最优策略序列，其初始状态为))0(*),0(()1(u x f x =。

(2)动态规划的基本方程下面导出动态规划的基本方程，它给出N 阶决策问题的指标函数最优值与它的子问题(一个N -1阶决策问题)的指标函数最优值之间的递推关系式。

这个基本方程是用动态规划解一切多阶段决策问题的基础。

假设)0(*u 已求出，那么)1(*,),1(*),0(*-N u u u 的问题构成一个初始条件为x f x u ()((),())100=*的N -1阶决策问题。

这一问题的指标函数最小值记作J x N -*11(())，则有=∑-=-*10)1(),1(),0())(),((min ))0((N k N u u u Nk u k x L x J ?+=∑-=-11)1(),1(),0())(),(())0()0((min N k N u u u k u k x L u x L+=∑-=-11)1(),1(,)0())(),((min ))0(),0((min N k N u u u k u k x L u x L{}))1(())0(),0((min 1)0(x J u x L N u *-+=方程 {}J x L x u J x N u N *-*=+(())min ((),())(())()000101称为动态规划的基本方程，它给出了J x N *(())0与J x N -*11(())之间的递推关系。

类似于上面的推导，可以得到动态规划基本方程的如下一般形式：{}))1(())(),((min ))((1)(++=*--*-i x J i u i x L i x J i N i u i N （7-5）动态规划的基本方程，也称递推方程或Bellman 方程，它给出了J x i N *(())与J x i N i --*+11(())之间的递推关系。