动态规划基本理论推广(函数迭代与策略迭代法)

动态规划根本实际推行——函数迭代法与战略迭代法管文科学与系统工程本章内容举例简单阐明不定期与无期决策过程的方式和概念；以不定期和无期决策过程为例，引见函数迭代法和战略迭代法。管文科学与系统工程不定期与无期决策过程定义：多阶段的决策过程的阶段数N确定，称为定期决策过程，当N不确定时，称此类决策过程为不定期决策过程，当N趋向无穷时称为无期决策过程。管文科学与系统工程不定期与无期决策过程例1：段数不定的最短道路问题〔不定期决策过程〕n个点相互衔接组成一

个连通图(右图中n=5),各点

标号为1,2,…,n。恣意两点

i，j之间的间隔(费用)记作

dij。求恣意一点i到点n(靶

点)的最短道路(间隔)。51432322575560.51管文科学与系统工程不定期与无期决策过程例1：段数不定的最短道路问题〔不定期决策过程〕n个点相互衔接组成一

个连通图(右图中n=5),各点

标号为1,2,…,n。恣意两点

i，j之间的间隔(费用)记作

dij。求恣意一点i到点n(靶

点)的最短道路(间隔)。51432322575560.51管文科学与系统工程不定期与无期决策过程例2：无限期决策过程模型 ，形状变换函数为 。(存在明显的级变量，但级

数是无限的)管文科学与系统工程不定期与无期决策过程求解这类问题假设仍运用以前的逐级递推方法，将遇到极大的计算量，为此必需寻觅新方法。函数方程可以用迭代法求解，通常有函数迭代法和战略迭代法两种迭代方法。管文科学与系统工程函数迭代法与战略迭代法1.函数迭代法的步骤是：(1)选初始函数 (普通取)；(2)用迭代公式及 计算其中 为当前阶段的形状和决策，为

知终止函数，为迭代步数,v为目的函数(3)当 或管文科学与系统工程函数迭代法与战略迭代法(4)当或时迭代停顿，最优值函数 ，最优战略 ；否那么以k+1替代k反复(2),(3).管文科学与系统工程函数迭代法与战略迭代法阐明：函数迭代法和战略迭代法中，序列

和 的收敛性在相当广泛的条件下是可以

保证的，普通来说它与 等

的详细方式有关。函数迭代法的根本思想是以步数(段数)作为参数，先求在各个不同步数下的最优战略，然后从这些最优解中再选出最优者，从而同时确定了最优步数。管文科学与系统工程函数迭代法与战略迭代法战略迭代法的根本思想是：先选定一初始战略 然后按某种方式求得新战略 直至最终求出最优战略。假设对某一k，对一切i有： ，那么称

收敛，此时，战略 就是最优战略。普通来说，选定初始战略要比选定初始目的最优值函数容易得多，且战略迭代的收敛速度稍快，但其计算量要大些。管文科学与系统工程函数迭代法与战略迭代法(是事先给定的数)时迭代停顿，最优值函数 ,最优战略 。2.战略迭代法的步骤是：(1)选初始战略 ，令k=1；(2)用求解 ，

(3)用 求改良战略 ，管文科学与系统工程函数迭代法与战略迭代法例1的求解：分析：可以不思索回路，由于含有回路的道路一定不是最短的.本问题道路的段数事先不固定，而是随着最优战略确定的，然而形状、决策、形状转移、目的函数与以前的最短道路问题的一样.形状记作x=i，i=1,2,…,n，决策记作u(i).战略是对恣意形状x的决策函数，记作u(x)。阶段目的是恣意两形状i,j间的间隔dij，目的函数V(i,u(x))是由形状i出发，在战略u(x)下到达形状n的道路的管文科学与系统工程函数迭代法与战略迭代法间隔，它是阶段目的之和，并满足可分别性要求，有最优值函数ƒ(i)为由i出发到达n的最短间隔，即

式中u*(x)是最优战略，满足根本方程

管文科学与系统工程函数迭代法与战略迭代法该式记为(﹡)式，它不是一个递推方程，而是一个关于ƒ(i)的函数方程,对固定的i使(﹡)右端[dij+ƒ(j)]到达极小的j即为最优决策u*(i)，对一切的i求解(﹡)式得到最优战略u*(x)。管文科学与系统工程不定期与无期决策过程例1：段数不定的最短道路问题〔不定期决策过程〕n个点相互衔接组成一

个连通图(右图中n=5),各点

标号为1,2,…,n。恣意两点

i，j之间的间隔(费用)记作

dij。求恣意一点i到点n(靶

点)的最短道路(间隔)。管文科学与系统工程函数迭代法与战略迭代法用函数迭代法求解例1只求1,2,3,4各点到点5的最优道路，其他类似。解：(1)假设从i点走一步到靶点5的最优间隔为,那么显然有： 最优决策为:51432322575560.51管文科学与系统工程函数迭代法与战略迭代法(2)假设从i点走两步到靶点5的最优间隔为,根据最优化原理得：

详细计算如下： 管文科学与系统工程函数迭代法与战略迭代法

注：不取含 的地方作为最优决策

管文科学与系统工程函数迭代法与战略迭代法(3)假设从i点走三步到靶点5的最优间隔为,那么得：

计算结果如下： 管文科学与系统工程函数迭代法与战略迭代法(4)假设从i点走四步到靶点5的最优间隔为,那么得：

计算结果如下： 管文科学与系统工程函数迭代法与战略迭代法

管文科学与系统工程函数迭代法与战略迭代法由于只需5个点,因此从任一点出发到达靶点,其间最多有4步(否那么，有回路)，这样就不需继续下去了。将计算结果列成表：

i1252525252755.534.534.53355444444435353535管文科学与系统工程函数迭代法与战略迭代法分析上面的结果可得：①从点1到点5走一步为最优，最优间隔为2，最优道路 ；从点2到点5走三步为最优，最优间隔为4.5,最优道路 ；从点3到点5走两步为最优，最优间隔为4,最优道路 ；从点4到点5走一步为最优，最优间隔为3，最优道路 。管文科学与系统工程函数迭代法与战略迭代法②最优决策最多走4步，多于此步数，会出现走回头路或回路，显然这些不是最优道路。③从任一点出发到靶点，走m(m=1,2,…)步与走m+1步的最优间隔一样，决策函数也一样，假设继续计算走m+2步、m+3步、……，其结果仍一样,即 也就阐明 一致收敛于 ， 一致收敛于 。故当这种一出现，计算便可停顿。管文科学与系统工程函数迭代法与战略迭代法例1的求解：(战略迭代法〕解：①第一步，先选取初始战略。如取：

即 ,但必需没有回路，每点可达靶点。第二步，由求 ，由战略迭代法的方程组可得：因战略 直达靶点，应先计算：管文科学与系统工程函数迭代法与战略迭代法

第三步，由求 ,由

求出它的解： 时，管文科学与系统工程函数迭代法与战略迭代法

所以， 〔不在含 的项取〕 时，管文科学与系统工程函数迭代法与战略迭代法所以， 同理，可求得 ,于是得到第一次战略迭代的结果为②以 为初始战略继续反复运用第二、三步进展迭代。第二步：由求管文科学与系统工程函数迭代法与战略迭代法第三步：由求 ,即由

求解 。 时，所以同理，求出故第二次战略迭代的结果为管文科学与系统工程函数迭代法与战略迭代法③第二步：由求第三步：由求 ，类似前面的方法求得第三次战略迭代的结果为管文科学与系统工程i1234545321156535525.553534524.5435345函数迭代法与战略迭代法④将以上结果记录下来：管文科学与系统工程函数迭代法与战略迭代法由以上结果得到 ，对一切的i都成立，阐明迭代步骤可以停顿。故找到最优战略为列表表示为从而可以得到各点到靶点(点5)的最优道路和最优间隔：i12345345管文科学与系统工程函数迭代法与战略迭代法最优道路 最短间隔值①→⑤ 2②→③→④→⑤ 4.5③→④→⑤ 4④→⑤ 3可以看到战略迭代法得到的结果与函数迭代法的结果一致。管文科学与系统工程不定期与无期决策过程例2：无限期决策过程模型 ，形状变换函数为 。(存在明显的级变量，但级

数是无限的)管文科学与系统工程函数迭代法与战略迭代法例2的求解〔函数迭代法〕解：(1)任取初值，如形状变换函数为迭代公式为(2)i=1时，进展第一次迭代管文科学与系统工程函数迭代法与战略迭代法对求导，并令其等于零，有

可得管文科学与系统工程函数迭代法与战略迭代法 ，取i=2时，进展第二次迭代对求导，并令其等于零，得管文科学与系统工程函数迭代法与战略迭代法故由于 ，应继续进展迭代。当i=3时，进展第三次迭代，类似以上才方法，可得管文科学与系统工程函数迭代法与战略迭代法由于 ,取i=4继续进展第四次迭代。其结果如下:管文科学与系统工程函数迭代法与战略迭代法由于 ,可以确定该问题的最优收益函数为最优决策为管文科学与系统工程函数迭代法与战略迭代法例2的求解〔战略迭代法〕解：(1)任取初始战略值，如及(2)进展第一次迭代，取i=1,2,…得管文科学与系统工程函数迭代法与战略迭代法

由于取再来确定第二次迭代的决策 ：

管文科学与系统工程函数迭代法与战略迭代法上式的解为

由于 ，需求进展第二次迭代：

管文科学与系统工程函数迭代法与战略迭代法由于 ，需求继续进展迭代，直到 时为止，节省时间，直接给出结果 ，但由于 ，因此需求继续进展迭代。如今来确定第三次迭代的决策 ，有管文科学与系统工程函数迭代法与战略迭代法那么由于 ，还必需进展下次迭代。第三次迭代： 管文科学与系统工程函数迭代法与战略迭代法由于 ，需求继续进展迭代，直到 时为止，最后得到 由于 ，因此需求继续进展迭代。如今来确定第四次迭代的决策 ，有管文科学与系统工程函数迭代法与战略迭代法那么第四次迭代： 管文科学与系统工程函数迭代法与战略迭代法继续进展迭代，直到 时为止，最后得到 由于 ，因此可停顿迭代。 最优收益函数为相应的最优战略为管文科学与系统工程函数迭代法与战略迭代法注：对于定义一个无期决策过程的最优化问题，须满足三个条件，即对一切的 有：①形状转移方程 有意义；②允许决策集合 有意义，而且

非空，那么存在允许战略 使得对一切 非空；③目的函数 对一切 有意义，且对一切允许战略，极限 存在。管文科学与系统工程函数迭代法与战略迭代法注：对于定义一个无期决策过程的最优化问题，须满足三个条件，即对一切的 有：①形状转移方程 有意义；②允许决策集合 有意义，而且

非空，那么存在允许战略 使得对一切 非空；③目的函数 对一切 有意义，且对一切允许战略，极限 存在。管文科学与系统工程函数迭代法与战略迭代法当上述三个条件成立时，就可以说，无期决策过程的最优化的意义在于求最优战略 使得其中P是定义在无期过程上的非空允许战略集。是P的元素， 是定义在P上的目的函数。管文科学与系统工程函数迭代法与战略迭代法例1、例2的共同点是在多阶段决策过程中允许决策集合、形状转移规律、阶段目的等于阶段变量k无关，从而根本方程成为函数方程，称这样的过程是平稳的。定义：满足以下条件的多阶段决策过程成为平稳过程，相应的战略称为平稳战略:(1)允许决策集合Uk(x)与k无关，可记为U(x)，

为形状变量;(2)形状转移Tk与k无关，于是可写作

x，u为当前的阶段和决策，为下一阶段形状;管文科学与系统工程函数迭代法与战略迭代法(3)