资源描述：
《动态规划基本理论推广函数迭代与策略迭代法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、动态规划基本理论推广——函数迭代法与策略迭代法管理科学与系统工程本章内容举例简单说明不定期与无期决策过程的形式和概念；以不定期和无期决策过程为例，介绍函数迭代法和策略迭代法。管理科学与系统工程不定期与无期决策过程定义：多阶段的决策过程的阶段数N确定，称为定期决策过程，当N不确定时，称此类决策过程为不定期决策过程，当N趋向无穷时称为无期决策过程。管理科学与系统工程不定期与无期决策过程例1：段数不定的最短路线问题（不定期决策过程）n个点相互连接组成一个连通图(右图中n=5),各点标号为1,2,…,n。任意两点i，j之间的距离(费用)记作dij。求任意一点i到点n(靶点)的最短路
2、线(距离)。51432322575560.51管理科学与系统工程不定期与无期决策过程例1：段数不定的最短路线问题（不定期决策过程）n个点相互连接组成一个连通图(右图中n=5),各点标号为1,2,…,n。任意两点i，j之间的距离(费用)记作dij。求任意一点i到点n(靶点)的最短路线(距离)。51432322575560.51管理科学与系统工程不定期与无期决策过程例2：无限期决策过程模型，状态变换函数为。(存在明显的级变量，但级数是无限的)管理科学与系统工程不定期与无期决策过程求解这类问题如果仍使用以前的逐级递推方法，将遇到极大的计算量，为此必需寻找新方法。函数方程可以用迭代
3、法求解，通常有函数迭代法和策略迭代法两种迭代方法。管理科学与系统工程函数迭代法与策略迭代法1.函数迭代法的步骤是：(1)选初始函数(一般取)；(2)用迭代公式及计算其中为当前阶段的状态和决策，为已知终止函数，为迭代步数,v为指标函数(3)当或管理科学与系统工程函数迭代法与策略迭代法(4)当或时迭代停止，最优值函数，最优策略；否则以k+1代替k重复(2),(3).管理科学与系统工程函数迭代法与策略迭代法说明：函数迭代法和策略迭代法中，序列和的收敛性在相当广泛的条件下是可以保证的，一般来说它与等的具体形式有关。函数迭代法的基本思想是以步数(段数)作为参数，先求在各个不同步数下的
4、最优策略，然后从这些最优解中再选出最优者，从而同时确定了最优步数。管理科学与系统工程函数迭代法与策略迭代法策略迭代法的基本思想是：先选定一初始策略然后按某种方式求得新策略直至最终求出最优策略。若对某一k，对所有i有：，则称收敛，此时，策略就是最优策略。一般来说，选定初始策略要比选定初始目标最优值函数容易得多，且策略迭代的收敛速度稍快，但其计算量要大些。管理科学与系统工程函数迭代法与策略迭代法(是事先给定的数)时迭代停止，最优值函数,最优策略。2.策略迭代法的步骤是：(1)选初始策略，令k=1；(2)用求解，(3)用求改进策略，管理科学与系统工程函数迭代法与策略迭代法例1的求
5、解：分析：可以不考虑回路，因为含有回路的路线一定不是最短的.本问题路线的段数事先不固定，而是随着最优策略确定的，然而状态、决策、状态转移、指标函数与以前的最短路线问题的相同.状态记作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)是最优策略，满足基本方程管理科学与系统工程
6、函数迭代法与策略迭代法该式记为(﹡)式，它不是一个递推方程，而是一个关于ƒ(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
7、)假设从i点走一步到靶点5的最优距离为,则显然有：最优决策为:管理科学与系统工程51432322575560.51函数迭代法与策略迭代法(2)假设从i点走两步到靶点5的最优距离为,根据最优化原理得：具体计算如下：管理科学与系统工程函数迭代法与策略迭代法注：不取含的地方作为最优决策管理科学与系统工程函数迭代法与策略迭代法(3)假设从i点走三步到靶点5的最优距离为,则得：计算结果如下：管理科学与系统工程函数迭代法与策略迭代法(4)假设从i点走四步到靶点5的最优距离为,则得：计算结果如下：管理科学与系统工程函数迭代法与策
