《动态规划基本理论推广函数迭代与策略迭代法学习教案》由会员分享，可在线阅读，更多相关《动态规划基本理论推广函数迭代与策略迭代法学习教案（58页珍藏版）》请在金锄头文库上搜索。
1、会计学1动态规划基本动态规划基本(jbn)理论推广函数迭代理论推广函数迭代与策略迭代法与策略迭代法第一页，共58页。本章本章(bn zhn)内容内容举例简单说明(shumng)不定期与无期决策过程的形式和概念；以不定期和无期决策过程为例，介绍函数迭代法和策略迭代法。管理科学与系统工程第1页/共57页第二页，共58页。不定期与无期不定期与无期(w q)决决策过程策过程定义：多阶段的决策过程的阶段数N确定，称为(chn wi)定期决策过程，当N不确定时，称此类决策过程为不定期决策过程，当N趋向无穷时称为(chn wi)无期决策过程。管理科学与系统工程第2页/共57页第三页，共58页。不定期与无期不
2、定期与无期(w q)决决策过程策过程例例1 1：段数不定的最短路线问题（不定期决策：段数不定的最短路线问题（不定期决策(juc)(juc)过程）过程）n n个点相互连接组成个点相互连接组成 一一个连通图个连通图( (右图中右图中n=5),n=5),各点各点标号为标号为1,2,n1,2,n。任意两点。任意两点i i，j j之间的距离之间的距离( (费用费用) )记作记作dij dij 。求任意一点。求任意一点i i到点到点n(n(靶靶点点) )的最短路线的最短路线( (距离距离) )。5143232257 5560.51管理科学与系统工程第3页/共57页第四页，共58页。不定期与无期决策不定期与
3、无期决策(juc)过程过程例例1 1：段数不定的最短路线问题（不定期决策过程）：段数不定的最短路线问题（不定期决策过程）n n个点相互连接组成个点相互连接组成 一一个连通图个连通图( (右图中右图中n=5),n=5),各点各点标号为标号为1,2,n1,2,n。任意。任意(rny)(rny)两点两点i i，j j之间的距离之间的距离( (费用费用) )记作记作dij dij 。求任意。求任意(rny)(rny)一点一点i i到点到点n(n(靶靶点点) )的最短路线的最短路线( (距离距离) )。5143232257 5560.51管理科学与系统工程第4页/共57页第五页，共58页。不定期与无期不
4、定期与无期(w q)决决策过程策过程例例2 2：无限期决策过程：无限期决策过程模型模型 ，状态变换，状态变换(binhun)(binhun)函数函数为为。( ( 存在明显的级变量，但级存在明显的级变量，但级数是无限的数是无限的 ) )管理科学与系统工程第5页/共57页第六页，共58页。不定期与无期决策不定期与无期决策(juc)过程过程求解这类问题如果仍使用以前的逐级递推方法，将遇到极大的计求解这类问题如果仍使用以前的逐级递推方法，将遇到极大的计算算(j sun)(j sun)量，为此必需寻找新方法。量，为此必需寻找新方法。函数方程可以用迭代法求解，通常有函数迭代法和策略迭代法两函数方程可以用迭
5、代法求解，通常有函数迭代法和策略迭代法两种迭代方法。种迭代方法。管理科学与系统工程第6页/共57页第七页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法1. 1.函数迭代法的步骤是：函数迭代法的步骤是：(1)(1)选初始函数选初始函数 ( (一般取一般取 ) )；(2)(2)用迭代公式用迭代公式及及 计算计算其中其中为当前阶段的状态和决策为当前阶段的状态和决策(juc)(juc)， 为为已知终止函数，已知终止函数， 为迭代步数为迭代步数, v, v为指标函数为指标函数(3)(3)当当或或管理科学与系统工程第7页/共57页第八页，共58页。函数函数(hnsh)迭代法与策略迭代
6、迭代法与策略迭代法法(4)(4)当当或或时迭代停止，最优值函数时迭代停止，最优值函数，最，最优策略优策略 ；否则以；否则以k+1k+1代替代替(dit)k(dit)k重复重复(2),(3).(2),(3).管理科学与系统工程第8页/共57页第九页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法说明：说明：函数迭代法和策略迭代法中，序列函数迭代法和策略迭代法中，序列 和和 的收敛性在相当广泛的条件下是可以的收敛性在相当广泛的条件下是可以保证的，一般来说它与保证的，一般来说它与 等等的具体形式有关。的具体形式有关。函数迭代法的基本函数迭代法的基本(jbn)(jbn)思想是以步数
7、思想是以步数( (段数段数) )作为参数，先求在各个作为参数，先求在各个不同步数下的最优策略，然后从这些最优解中再选出最优者，从而同时不同步数下的最优策略，然后从这些最优解中再选出最优者，从而同时确定了最优步数。确定了最优步数。管理科学与系统工程第9页/共57页第十页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法策略迭代法的基本思想是：先选定一初始策略策略迭代法的基本思想是：先选定一初始策略 然后按某种方然后按某种方式求得新策略式求得新策略 直至最终求出最优策略。若对某一直至最终求出最优策略。若对某一k k，对所，对所有有i i有：有： ，则称，则称 收敛，此时，策略收敛
8、，此时，策略就是最优策略。就是最优策略。一般来说，选定初始策略要比选定初始目标一般来说，选定初始策略要比选定初始目标(mbio)(mbio)最优值函数容易最优值函数容易得多，且策略迭代的收敛速度稍快，但其计算量要大些。得多，且策略迭代的收敛速度稍快，但其计算量要大些。管理科学与系统工程第10页/共57页第十一页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法 ( ( 是事先给定的数是事先给定的数) )时迭代停止，最优值函数时迭代停止，最优值函数, ,最优策略最优策略(cl)(cl) 。2. 2.策略策略(cl)(cl)迭代法的步骤是：迭代法的步骤是：(1)(1)选初始策略选
9、初始策略(cl)(cl) ，令，令k=1k=1；(2)(2)用用 求解求解 ， (3)(3)用用 求改进策略求改进策略(cl)(cl) ，管理科学与系统工程第11页/共57页第十二页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法例例1 1的求解：的求解：分析：可以不考虑回路，因为含有回路的路线一定不是最短的分析：可以不考虑回路，因为含有回路的路线一定不是最短的. .本问题路线的段数事先不固定，而是随着最优策略确定的，然而状本问题路线的段数事先不固定，而是随着最优策略确定的，然而状态、决策、状态转移态、决策、状态转移(zhu(zhu ny)ny)、指标函数与以前的最短路线问
10、、指标函数与以前的最短路线问题的相同题的相同. .状态记作状态记作x=ix=i，i=1,2,ni=1,2,n，决策记作，决策记作u(i).u(i).策略是对任意状态策略是对任意状态x x的决策函的决策函数，记作数，记作u(x)u(x)。阶段指标是任意两状态。阶段指标是任意两状态i,j i,j间的距离间的距离dijdij，指标函数，指标函数V(i,u(x)V(i,u(x)是由状态是由状态i i出发，在策略出发，在策略u(x)u(x)下到达状态下到达状态n n的路线的的路线的管理科学与系统工程第12页/共57页第十三页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法距离，它是阶
11、段指标之和，距离，它是阶段指标之和， 并满足可分离性要求，有并满足可分离性要求，有最优值函数最优值函数(i)(i)为由为由i i出发到达出发到达(dod)n(dod)n的最短距离，即的最短距离，即式中式中u*(x)u*(x)是最优策略，满足基本方程是最优策略，满足基本方程 管理科学与系统工程第13页/共57页第十四页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法该式记为该式记为( ( ) )式，它不是一个递推方程式，它不是一个递推方程(fngchng)(fngchng)，而是一个关于，而是一个关于(i)(i)的函数方程的函数方程(fngchng),(fngchng),对固
12、定的对固定的i i使使( ( ) )右端右端 dij+(j) dij+(j) 达到极达到极小的小的j j即为最优决策即为最优决策u*(i)u*(i)，对所有的，对所有的i i求解求解( ( ) )式得到最优策略式得到最优策略u*(x)u*(x)。管理科学与系统工程第14页/共57页第十五页，共58页。不定期与无期不定期与无期(w q)决决策过程策过程例例1 1：段数不定：段数不定(bdng)(bdng)的最短路线问题（不定的最短路线问题（不定(bdng)(bdng)期决策过程）期决策过程）n n个点相互连接组成个点相互连接组成 一一个连通图个连通图( (右图中右图中n=5),n=5),各点各点
13、标号为标号为1,2,n1,2,n。任意两点。任意两点i i，j j之间的距离之间的距离( (费用费用) )记作记作dij dij 。求任意一点。求任意一点i i到点到点n(n(靶靶点点) )的最短路线的最短路线( (距离距离) )。管理科学与系统工程第15页/共57页第十六页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法用函数迭代法求解例用函数迭代法求解例1 1只求只求1,2,3,41,2,3,4各点到点各点到点5 5的最优路线，其余类似。的最优路线，其余类似。解：解：(1)(1)假设从假设从i i点走一步到靶点点走一步到靶点5 5的最优距离的最优距离(jl)(jl)为为
14、 , , 则显然有：则显然有： 最优决策为最优决策为: :管理科学与系统工程5143232257 5560.51第16页/共57页第十七页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法 (2) (2)假设从假设从i i点走两步到靶点点走两步到靶点5 5的最优距离为的最优距离为 , , 根据根据(gnj)(gnj)最最优化原理得：优化原理得： 具体计算如下：具体计算如下：管理科学与系统工程第17页/共57页第十八页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法 注：不取含注：不取含 的地方的地方(dfng)(dfng)作为最优作为最优决策决策管理科学与
15、系统工程第18页/共57页第十九页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法 (3) (3)假设假设(ji (ji sh)sh)从从i i点走三步到靶点点走三步到靶点5 5的最优距离为的最优距离为 , , 则得：则得： 计算结果如下：计算结果如下：管理科学与系统工程第19页/共57页第二十页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法 (4) (4)假设假设(ji (ji sh)sh)从从i i点走四步到靶点点走四步到靶点5 5的最优距离为的最优距离为 , , 则得：则得： 计算结果如下：计算结果如下：管理科学与系统工程第20页/共57页第二十
16、一页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法 管理科学与系统工程第21页/共57页第二十二页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法 由于由于(yuy)(yuy)只有只有5 5个点个点, ,因而从任一点出发到达靶点因而从任一点出发到达靶点, ,其间最多有其间最多有4 4步步( (否则，有回路否则，有回路) )，这样就不需继续下去了。将计算结果列成表：，这样就不需继续下去了。将计算结果列成表：管理科学与系统工程i1252525252755.534.534.53355444444435353535第22页/共57页第二十三页，共58页。函数函
17、数(hnsh)迭代法与策略迭代迭代法与策略迭代法法 分析上面的结果分析上面的结果(ji gu(ji gu ) )可得：可得：从点从点1 1到点到点5 5走一步为最优，最优距离为走一步为最优，最优距离为2 2，最优路线，最优路线 ；从点从点2 2到点到点5 5走三步为最优，最优距离为走三步为最优，最优距离为4.5,4.5,最优路线最优路线 ；从点从点3 3到点到点5 5走两步为最优，最优距离为走两步为最优，最优距离为4, 4,最优路线最优路线 ；从点从点4 4到点到点5 5走一步为最优，最优距离为走一步为最优，最优距离为3 3，最优路线，最优路线 。管理科学与系统工程第23页/共57页第二十四页
18、，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法 最优决策最多走最优决策最多走4 4步，多于此步数，会出现走回头路或回路，显步，多于此步数，会出现走回头路或回路，显然这些不是最优路线。然这些不是最优路线。 从任一点出发到靶点，走从任一点出发到靶点，走m(m=1,2,)m(m=1,2,)步与走步与走m+1m+1步的最优距离一步的最优距离一样，决策函数也一样，如果样，决策函数也一样，如果(rgu(rgu ) )继续计算走继续计算走m+2m+2步、步、m+3m+3步、步、，其结果仍一样，其结果仍一样, , 即即 也就说明也就说明 一致收敛于一致收敛于 ， 一致收敛于一致收敛于 。
19、故当这种一出现，。故当这种一出现，计算便可停止。计算便可停止。管理科学与系统工程第24页/共57页第二十五页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法例例1 1的求解：的求解：( (策略迭代法）策略迭代法） 解：解：第一步，先选取初始第一步，先选取初始(ch sh(ch sh ) )策略策略 。如取：。如取：即即 , ,但必需没有回路，每点可达靶点。但必需没有回路，每点可达靶点。第二步，由第二步，由 求求 ，由策略迭代法的方程组可得：，由策略迭代法的方程组可得：因策略因策略 直达靶点，应先计算：直达靶点，应先计算：管理科学与系统工程第25页/共57页第二十六页，共58
20、页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法第三步，由第三步，由 求求 , ,由由求出它的解求出它的解 ：时，时，管理科学与系统工程第26页/共57页第二十七页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法所以所以(su(su y y ) )， （不在含（不在含 的项取的项取 ） 时，时，管理科学与系统工程第27页/共57页第二十八页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法所以，所以，同理，可求得同理，可求得 , ,于是得到第一次策略迭代的于是得到第一次策略迭代的结果结果(ji gu(ji gu ) )为为以以 为初始策略继续反
21、复使用第二、三步进行迭代。为初始策略继续反复使用第二、三步进行迭代。第二步：由第二步：由 求求管理科学与系统工程第28页/共57页第二十九页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法第三步：由第三步：由 求求, ,即由即由求解求解 。 时，时，所以所以(su(su y y ) )同理，求出同理，求出故第二次策略迭代的结果为故第二次策略迭代的结果为管理科学与系统工程第29页/共57页第三十页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法第二步：由第二步：由 求求第三步：由第三步：由 求求，类似前面，类似前面(qin mian)(qin mian)的
22、方法求得第三次策的方法求得第三次策略迭代的结果为略迭代的结果为管理科学与系统工程第30页/共57页第三十一页，共58页。i1234545321156535525.553534524.5435345函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法将以上将以上(y (y shng)shng)结果记录下来：结果记录下来：管理科学与系统工程第31页/共57页第三十二页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法由以上结果得到由以上结果得到 ，对所有的，对所有的i i都成立，说明都成立，说明迭代步骤可以停止。故找到最优策略迭代步骤可以停止。故找到最优策略(cl)(cl)为
23、为列表表示为列表表示为从而可以得到各点到靶点从而可以得到各点到靶点( (点点5)5)的最优路线和最优距离：的最优路线和最优距离：管理科学与系统工程i12345345第32页/共57页第三十三页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法最优路线最优路线(lxin)(lxin) 最短距离值最短距离值 2 2 4.5 4.5 4 4 3 3可以看到策略迭代法得到的结果与函数迭代法的结果一致。可以看到策略迭代法得到的结果与函数迭代法的结果一致。管理科学与系统工程第33页/共57页第三十四页，共58页。不定期与无期决策不定期与无期决策(juc)过程过程例例2 2：无限期决策过程
24、：无限期决策过程模型模型 ，状态变换函数，状态变换函数为为。( ( 存在明显的级变量存在明显的级变量(binling)(binling)，但级但级数是无限的数是无限的 ) )管理科学与系统工程第34页/共57页第三十五页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法例例2 2的求解（函数的求解（函数(hnsh)(hnsh)迭代法）迭代法）解：解：(1)(1)任取初值，如任取初值，如状态变换函数状态变换函数(hnsh)(hnsh)为为迭代公式为迭代公式为(2)i=1(2)i=1时，进行第一次迭代时，进行第一次迭代管理科学与系统工程第35页/共57页第三十六页，共58页。函数
25、函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法 对对 求导，并令其等于零，有求导，并令其等于零，有 可得可得管理科学与系统工程第36页/共57页第三十七页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法 ，取，取i=2i=2时，进行时，进行(jnxng)(jnxng)第二次迭代第二次迭代对对 求导，并令其等于零，得求导，并令其等于零，得管理科学与系统工程第37页/共57页第三十八页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法故故由于由于 ，应继续进行迭代。，应继续进行迭代。当当i=3i=3时，进行第三次迭代，类似时，进行第三次迭代，类似(li
26、s)(li s)以上才方法，可得以上才方法，可得管理科学与系统工程第38页/共57页第三十九页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法由于由于(yuy) (yuy) , ,取取i=4i=4继续进行第四次迭代。其结果如下继续进行第四次迭代。其结果如下: :管理科学与系统工程第39页/共57页第四十页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法由于由于 , ,可以确定该问题可以确定该问题(wnt)(wnt)的最优收益函数为的最优收益函数为最优决策为最优决策为管理科学与系统工程第40页/共57页第四十一页，共58页。函数函数(hnsh)迭代法与策略
27、迭代迭代法与策略迭代法法例例2 2的求解（策略的求解（策略(cl)(cl)迭代法）迭代法）解：解：(1)(1)任取初始策略任取初始策略(cl)(cl)值，如值，如及及(2)(2)进行第一次迭代，取进行第一次迭代，取i=1,2,i=1,2,得得管理科学与系统工程第41页/共57页第四十二页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法 由于由于(yuy)(yuy)取取 再来确定第二次迭代的决策再来确定第二次迭代的决策 ： 管理科学与系统工程第42页/共57页第四十三页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法上式的解为上式的解为 由于由于，需要进行
28、，需要进行(jnxng)(jnxng)第二次迭代：第二次迭代： 管理科学与系统工程第43页/共57页第四十四页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法由于由于 ，需要继续进行迭代，直到，需要继续进行迭代，直到 时为止，节省时间，直接给出结果时为止，节省时间，直接给出结果 ，但由于，但由于 ，因此需要继续进行迭代。，因此需要继续进行迭代。现在来确定现在来确定(qudng)(qudng)第三次迭代的决策第三次迭代的决策，有，有管理科学与系统工程第44页/共57页第四十五页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法则则由于由于，还必须，还必须(b
29、x)(bx)进行下次迭代。进行下次迭代。第三次迭代：第三次迭代：管理科学与系统工程第45页/共57页第四十六页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法由于由于 ，需要继续进行迭代，直到，需要继续进行迭代，直到 时为止，最后得到时为止，最后得到 由于由于 ，因此需要继续进行迭代。，因此需要继续进行迭代。现在现在(xinzi)(xinzi)来确定第四次迭代的决策来确定第四次迭代的决策，有，有管理科学与系统工程第46页/共57页第四十七页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法则则第四次迭代第四次迭代(di di)(di di)：管理科学与系统
30、工程第47页/共57页第四十八页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法继续进行迭代，直到继续进行迭代，直到(zhdo)(zhdo) 时为止，最后时为止，最后得到得到 由于由于 ，因此可停止迭代。，因此可停止迭代。最优收益函数为最优收益函数为 相应的最优策略为相应的最优策略为管理科学与系统工程第48页/共57页第四十九页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法注：对于定义一个无期注：对于定义一个无期(w q)(w q)决策过程的最优化问题，须满足三个条件，决策过程的最优化问题，须满足三个条件，即对所有的即对所有的有：有：状态转移方程状态转
31、移方程有意义；有意义；允许决策集合允许决策集合 有意义，而且有意义，而且非空，则存在允许策略非空，则存在允许策略使得对所有使得对所有 非空；非空；目标函数目标函数 对所有对所有 有意义，且对所有允许策略，极限有意义，且对所有允许策略，极限 存存在。在。管理科学与系统工程第49页/共57页第五十页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法注：对于定义一个无期决策过程的最优化问题，须满足三个条件，注：对于定义一个无期决策过程的最优化问题，须满足三个条件，即对所有的即对所有的有：有：状态转移方程状态转移方程有意义；有意义；允许决策集合允许决策集合 有意义，而且有意义，而且(
32、r qi)(r qi)非空，则存在允许策略非空，则存在允许策略使得对所有使得对所有 非空；非空；目标函数目标函数 对所有对所有 有意义，且对所有允许策略，极限有意义，且对所有允许策略，极限 存存在。在。管理科学与系统工程第50页/共57页第五十一页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法当上述三个条件当上述三个条件(tiojin)(tiojin)成立时，就可以说，无期决策过程的最成立时，就可以说，无期决策过程的最优化的意义在于求最优策略优化的意义在于求最优策略 使得使得其中其中P P是定义在无期过程上的非空允许策略集。是定义在无期过程上的非空允许策略集。 是是 P
33、P的元素，的元素， 是定义在是定义在P P上的目标函数。上的目标函数。管理科学与系统工程第51页/共57页第五十二页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法例例1 1、例、例2 2的共同点是在多阶段决策过程中允许决策集合、状态转移规律、的共同点是在多阶段决策过程中允许决策集合、状态转移规律、阶段指标等于阶段变量阶段指标等于阶段变量k k无关，从而基本方程成为函数方程，称这样的过程无关，从而基本方程成为函数方程，称这样的过程是平稳的。是平稳的。定义：满足以下条件的多阶段决策过程成为平稳过程，相应定义：满足以下条件的多阶段决策过程成为平稳过程，相应(xingyng)(x
34、ingyng)的策略称为平稳策略的策略称为平稳策略: :(1) (1) 允许决策集合允许决策集合Uk(x)Uk(x)与与k k无关，可记为无关，可记为U(x)U(x)， 为状态变量为状态变量; ;(2) (2) 状态转移状态转移TkTk与与k k无关，于是可写作无关，于是可写作x x，u u为当前的阶段和决策，为当前的阶段和决策， 为下一阶段状态为下一阶段状态; ;管理科学与系统工程第52页/共57页第五十三页，共58页。函数函数(hnsh)迭代法与策略迭代迭代法与策略迭代法法(3) (3) 阶段指标阶段指标VkVk与与k k无关，可记作无关，可记作 。如果决策序列如果决策序列 中中 与与k
35、k无关，称为平稳无关，称为平稳(pngwn)(pngwn)的，可用一个函数的，可用一个函数u(x)u(x)表表示。平稳示。平稳(pngwn)(pngwn)过程的最优策略一定是平稳过程的最优策略一定是平稳(pngwn)(pngwn)策略，记作策略，记作 . .管理科学与系统工程第53页/共57页第五十四页，共58页。附：理论附：理论(lln)证明证明 收敛性证明收敛性证明 对所有的对所有的k k、i i、j, j,根据根据(gnj)(gnj)极限存在准则，极限存在准则， 必收敛于必收敛于 当当收敛性于收敛性于 时，证明时，证明 即为即为 的解的解管理科学与系统工程第54页/共57页第五十五页，共
36、58页。附：理论附：理论(lln)证明证明 收敛收敛(shuli(shuli n)n)于于 ，有，有管理科学与系统工程第55页/共57页第五十六页，共58页。附：理论附：理论(lln)证明证明合并合并(hbng)(hbng)上面两式，即得上面两式，即得管理科学与系统工程第56页/共57页第五十七页，共58页。内容(nirng)总结会计学。以不定期和无期决策过程为例，介绍函数迭代法和策略迭代法。管理科学与系统工程。n个点相互连接组成 一个连通图(右图中n=5),各点标号为1,2,。任意两点i，j之间的距离(费用)记作dij。分析：可以不考虑回路，因为含有回路的路线一定(ydng)不是最短的.。最优值函数(i)为由i出发到达n的最短距离，即。只求1,2,3,4各点到点5的最优路线，其余类似。从任一点出发到靶点，走m(m=1,2,第五十八页，共58页。
