管理科学与系统工程
1.函数迭代法的步骤是： (1)选初始函数 f0 (x()一般取 (2)用迭代公式
)；f0 (x) 0
及 fk (x) opt v(x,u)计 算fk1(T (x,u)), x X uU ( x)
其中fk (x) 为 当(x前),阶x 段X的n 状态和f决k (策x),，k 1, 2为, , 已知终x,u止函数，k 为迭代步数, v为指标函(x数)
可达靶点{u。1(i)} {5, 4,5,3}
第二步，由 求 ，由策略迭代法的方
程组可得： u1(i)
f1 (i)
因策略
f1(i)
di,u1 (i)
f1 (u1 (i))
f1(5) 0
直达靶点，应先计算：
u1 (1)管,理u科1 (学3与)系统工程
f1(1) d15 f1(5) 2 0 2
管理科学与系统工程
②最优决策最多走4步，多于此步数，会出现走 回头路或回路，显然这些不是最优路线。
③从任一点出发到靶点，走m(m=1,2,…)步与走
m+1步的最优距离一样，决策函数也一样，如果
继续计算走m+2步、m+3步、……，其结果仍一样,
即 fm (i) fm1(i)
,
um
(i)
u m1
(i)
d42 f1(2), d43 f1(3), d44 f1(4), d45 f1(5)]
min[2 2,5 7,1 5,0 3,3 0] 3
u2 (4) 5
管理科学与系统工程
由于只有5个点,因而从任一点出发到达靶点, 其间最多有4步(否则，有回路)，这样就不需继续 下去了。将计算结果列成表：
管理科学与系统工程
f2 (4) d45 3
f2 (2) d23 f2 (3) 0.5 5 5.5
第三步：由 求解u3 (i) 。
管理科学与系统工程
所以，u2 (2) 3 同理，可求得u2 (3) 5，u2 (4) 5,于是得到第 一次策略迭代的结果为
{u2 (i)} {5,3,5,5} ②以 u2 (i) 为初始策略继续反复使用第二、三 步进行迭代。 第二步：由u2 (i)求 f2 (i)
f2 (1) d15 2 f2 (3) d35 5
从点2到点5走三步为最优，最优距离为4.5,最 优路线 2 u3 (2) 3 u2(3) 4 u1(4) 5 ；
从点3到点5走两步为最优，最优距离为4,最优 路线 3 u2 (3) 4 u1 (4) 5 ；
从点4到点5走一步为最优，最优距离为3，最 优路线4 u1 (4) 5。
管理科学与系统工程
距离，它是阶段指标之和， 并满足可分离性要 求，有
V (i, u( x)) dij V ( j, u( x))
最优值函数ƒ(i)为由i出发到达n的最短距离，即
f (i) minV (i,u(x)) V (i,u*(x)) u(x)
式中u*(x)是最优策略，满足基本方程
f
(i)
fk (x) v(x,uk (x)) fk (T (x,uk (x))), x X .
fk (x) (x), x X n.
(3)用 fk (x) 求改进策略 uk1(x) ，
uk1(x) (u opt v(x,u) fk (T (x,u))).
uU ( x)
管理科学与系统工程
例1的求解：
i f1(i) u1 (i) f2 (i) u2 (i) f3 (i) u3 (i) f4 (i) u4 (i) 125252525 2 7 5 5.5 3 4.5 3 4.5 3 355444444 435353535
管理科学与系统工程
分析上面的结果可得：
①从点1到点5走一步为最优，最优距离为2，最 优路线1 u1 (1) 5；
模型min z
2 j
j0
x
2 j
lim
k
V0
，状态变换函数
k
为j1 j xj 。( 存在明显的级变量，但级
数是无限的 )
管理科学与系统工程
求解这类问题如果仍使用以前的逐级递推方法， 将遇到极大的计算量，为此必需寻找新方法。 函数方程可以用迭代法求解，通常有函数迭代法 和策略迭代法两种迭代方法。
管理科学与系统工程
策略迭代法的基本思想是：先选定一初始策 略{uk (i) i 1, 2, , n 1}然后按某种方式求得新策 略 u1(i),u2 (i), , 直至最终求出最优策略。若对某 一k，对所有i有：uk1(i) uk (i) ，则称 u1(i),u2 (i), 收敛，此时，策略{uk (i) i 1, 2, , n 1} 就是最优 策略。
0.5
则显然有：
f1(1) d15 2 最优决策为:u(1) 5
f1(2) d25 7
u (2) 5
f1 (i)
f1(3) d35 5 f1(4) d45 3
u (3) 5 u (4) 5
f1(5) d55 0
u (5) 5
管理科学与系统工程
(2)假设从i点走两步到靶点5的最优距离为f2 (i), 根据最优化原理得：
f3 (i)
min
1 i 5
dij
f2 ( j) ,i
1, 2,3, 4
f3 (5) 0
计算结果如下： f3 (1) 2,u3 (1) 5 f3 (2) 4.5,u3 (2) 3
f3 (3) 4,u3 (3) 4 f3 (4) 3,u3 (4) 5
管理科学与系统工程
(4)假设从i点走四步到靶点5的最优距离为f4 (i), 则得：
f2 (2)
min
1i 5
d
2
j
f1( j)
min[d21
f1 (1),
d22 f1(2), d23 f1(3), d24 f1(4), d25 f1(5)]
min[6 2,0 7,0.5 5,5 3,7 0] 5.5
u2 (2) 3
管理科学与系统工程
(3)假设从i点走三步到靶点5的最优距离为f3 (i), 则得：
mu(iin) [d1,u(i) f1(u(i))] min[d11 f1(1), d12 f1(2), d13 f1(3), d14 f1(4), d15 f1(5)] min[0 2,6 11,5 5, 2 6, 2 0] 2 所以，u2 (1) 5（不在含dii 的项取u2 (1)） u(i) 2时， mu(iin) [d2,u(i) f1(u(i))] min[6 2,0 11,0.5 5,5 6,7 0] 5.5
一般来说，选定初始策略要比选定初始目标 最优值函数容易得多，且策略迭代的收敛速度稍 快，但其计算量要大些。
管理科学与系统工程
x X( 是事先给定的数)时迭代停止，最优值函 数 f (x) fk (x) ,最优策略u(x) uk (x)。
2.策略迭代法的步骤是：
(1)选初始策略u1 ( x)，令k=1； (2)用uk (x)求解 fk (x) ，
(3)当
或
fk1(x) fk (x), x X ,
管理科学与系统工程
fk1(x) fk (x)
fk (x)
(4)当
uk1(x) uk (x), x X ,
或
fk1(x) fk (x) , x X
fk (x)
时迭代停止，最优值函数 f (x) fk (x) ，最优策 略u(x) uk (x) ；否则以k+1代替k重复(2),(3).
个连通图(右图中n=5),各点 标号为1,2,…,n。任意两点 i，j之间的距离(费用)记作 dij 。求任意一点i到点n(靶 点)的最短路线(距离)。
管理科学与系统工程
5
275 12
用函数迭代法求解例1
6 55
只求1,2,3,4各点到点5的最优路线，其余类似。 解：(1)假设从i点走一步到靶点5的最优距离为 2,
min
1 jn
dij
f
(
j) ,i
1, 2,
, n 1.
管理科学与系统工程
该式记为(﹡)式，它不是一个递推方程，而是一 个关于ƒ(i)的函数方程,对固定的i使(﹡)右端 [dij+ƒ(j)] 达到极小的j即为最优决策u*(i)，对所有 的i求解(﹡)式得到最优策略u*(x)。
管理科学与系统工程
例1：段数不定的最短路线问题（不定期决策过程） n个点相互连接组成 一
f1(3) d35 f1(5) 5 0 5
f1(4) d43 f1(3) 1 5 6
f1(2) d24 f1(4) 5 6 11
第三步，由 f1(i)求 求出它的解u2 (i) ：
u2 (i)
,由
mu(iin) [di,u(i)
f1 (u (i))]
u(i) 1时，
管理科学与系统工程
例1：段数不定的最短路线问题（不定期决策过程）
n个点相互连接组成 一 个连通图(右图中n=5),各点 标号为1,2,…,n。任意两点 i，j之间的距离(费用)记作 dij 。求任意一点i到点n(靶 点)的最短路线(距离)。
5 2753 1 24 6 55 1
2 0.5 3
管理科学与系统工程
例2：无限期决策过程
, 也就说明
{ fm (i)}一致收敛于 f (i) ，{um (i)}一致收敛于 u (i)。
故当这种一出现，计算便可停止。
管理科学与系统工程
例1的求解：(策略迭代法）
解：①第一步，先选取初始策略u1(i) 。如取：
u1(1) 5,u1(2) 4,u1(3) 5,u1(4) 3.
即
,但必需没有回路，每点
min
1i 5
d3
j
f1 (
j)
min[d31