清华大学运筹学课件动态规划.pdf

《清华大学运筹学课件动态规划.pdf》由会员分享，可在线阅读，更多相关《清华大学运筹学课件动态规划.pdf（58页珍藏版）》请在三一文库上搜索。

1、动态规划动态规划 基本概念 多阶段问题 建模与求解 迭代求解方法 主要内容 基本概念 多阶段问题 建模与求解 迭代求解方法 主要内容 基本概念基本概念 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 例、（无阶段划分）最短路问题例、（无阶段划分）最短路问题 下图五个城市，任何两个城市间均有道路相连，往返 路程一样，由图中数字所示。求每个城市到第五个城 市的最短路线和最短路程 下图五个城市，任何两个城市间均有道路相连，往返 路程一样，由图中数字所示。求每个城市到第五个城 市的最短路线和最短路程 ( , ),( )T s uSsS uU s 状态转移函数 阶段指

2、标函数 状态转移函数 阶段指标函数 ( , )0d s s 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 状态与状态集状态与状态集 ,1,5 i Sv i 决策与决策集决策与决策集 ( ),1,5 , i U sv isS 策略与策略集策略与策略集 ,1,5 ii PuU vi 对每个初始状态，以极小化阶段指标函数之和为 目标，确定一个能够转移到末状态的最优策略 对每个初始状态，以极小化阶段指标函数之和为 目标，确定一个能够转移到末状态的最优策略 5 v 问题 （） 问题 （）( , ),( )d s usS uU s 马尔可夫（马尔可夫（Markov）性

3、（或无后效性）性（或无后效性） 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 以任何状态为初始状态进行决策所产生的 效果，不受如何到达这个状态的决策影响 以任何状态为初始状态进行决策所产生的 效果，不受如何到达这个状态的决策影响 最优性原理最优性原理 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 若在自到的最优路线上，那么这条路线 上自到的部分就是自到的最优路线 若在自到的最优路线上，那么这条路线 上自到的部分就是自到的最优路线 5 v j v j v 5 v i v 5 v j v 理由：马尔科夫性理由：马尔科夫性

4、1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 根据最优性原理，最优值函数一定满足最优值方程根据最优性原理，最优值函数一定满足最优值方程 定义各点到目的地的最优值函数定义各点到目的地的最优值函数 , f ssS min, u U s f sd s uf T s usS 动态规划的核心是解最优值方程动态规划的核心是解最优值方程 多阶段问题多阶段问题 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 4 3 5 6 2 1 3 3 选择从至的最短路铺设输

5、油管道选择从至的最短路铺设输油管道AF （多阶段决策）最短路问题（多阶段决策）最短路问题 阶段阶段1 状态状态 k s 状态集状态集 k S 212 ,BBS 决策决策 k u 决策集决策集() kk Us 如：如： 2124 ,)(EEDU 策略策略 ,55 , kk puu )(,),( 555 , sUsUP kkk 阶段阶段2 阶段阶段3 阶段阶段4 阶段阶段5 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 4 3 5 6 2 1 3 3 1 s 2 s 3 s 5 s 4

6、 s 6 s 1 u 2 u 5 u 4 u 3 u 策略集策略集,5k P 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 4 3 5 6 2 1 3 3 1 (,),() kkkkkkkkk T s uSsSuUs 过程指标函数过程指标函数 状态转移函数状态转移函数 5 ,5,5 (|), kkkiii i k Vpsds u 阶段指标函数阶段指标函数 (,),() kkkkkkkk ds usSuUs 用动态规划的术语描述最短路问题 已知 用动态规划的术语描述最短路问题 已知6

7、 , 2 , 1,kSk状态集状态集 (,),(),1,2,5 kkkkkkkkk T s uusS uUsk 状态转移函数 问题 阶段指标函数 决策集 状态转移函数 问题 阶段指标函数 决策集5 , 2 , 1,),(kSssU kkkk (,),(),1,2,5 kkkkkkkk ds usS uUsk 求使下述过程指标函数达到最小求使下述过程指标函数达到最小5 , 15 , 1 Pp 5 1,51,51 1 (|), kkk k Vpsds u 最短路问题的动态规划模型最短路问题的动态规划模型 5 1,51,51 1 1 min(|), s.t. ,( ), 15 kkk k kkkkk

8、kkkk Vpsds u sTs usSuUsk 满足马尔可夫性：满足马尔可夫性： k s 给定，系统在阶段以后的状态和系统经由什 么路径到达无关，即和的取值无关 给定，系统在阶段以后的状态和系统经由什 么路径到达无关，即和的取值无关121 , k sss k k s 最优值函数一定满足最优值方程最优值函数一定满足最优值方程 min, u U s f sd s uf T s usS 多阶段最短路问题的逆推求解多阶段最短路问题的逆推求解 定义最优值函数为从到终点的最短路程，并根 据多阶段结构将其表示为 定义最优值函数为从到终点的最短路程，并根 据多阶段结构将其表示为 1 min, min, k

9、u U s kkkkk u Us f sd s uf T s u fsds ufTs usS f s s ,1,6 kk f sfssSk 终止条件：终止条件： 66 0,f sfssS 利用多阶段结构，可得到最优性方程的以下等价式利用多阶段结构，可得到最优性方程的以下等价式 5 4 3 2 1 66 55655 ( ) 44544 ( ) 33433 ( ) 22322 ( ) 11211 ( ) ( )0, ( )min, ( )min, ( )min, ( )min, ( )min, u Us u Us u Us u Us u Us f ssS f sds ufTs usS f sds

10、ufTs usS f sds ufTs usS f sds ufTs usS f sds ufT s usS 结论：最优值函数可以用以下公式逆推确定结论：最优值函数可以用以下公式逆推确定 f s 最短路问题的逆推结果（最优决策可由最优值得到）最短路问题的逆推结果（最优决策可由最优值得到） 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 4 3 5 6 2 1 3 3 4 0 3 7 5 5 12 10 8 9 13 15 17 多阶段最短路问题的顺推求解多阶段最短路问题的顺推求解 定

11、义最优值函数为从起点到的最短路程，并根 据多阶段结构将其表示为 定义最优值函数为从起点到的最短路程，并根 据多阶段结构将其表示为 , , 11 , , min, min, k kk T s us sS u U s kkkk Ts us sSu Us fsd s ufs fsds ufssS fs s ,1,6 kk fsfssSk 初始条件：初始条件： 11 0,fsfssS 由于对任意成立，所以由于对任意成立，所以k 1 , kkkkk STS US 1 11 2 22 3 33 4 44 11 2112 , ,( ) 3223 , ,( ) 4334 , ,( ) 5445 , ,( )

12、6 ( )0, ( )min, ( )min, ( )min, ( )min, ( T s us s S u Us Ts us s S u Us T s us s S u Us Ts us s S u Us f ssS f sds ufssS f sds ufssS f sds ufssS f sds ufssS f 5 55 556 , ,( ) )min, Ts us s S u Us sds ufssS 结论：最优值函数可以用以下公式顺推确定结论：最优值函数可以用以下公式顺推确定 f s 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4

13、5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 4 3 5 6 2 1 3 3 14 17 14 11 12 14 6 7 10 12 4 5 0 最短路问题的顺推结果（最优决策可由最优值得到）最短路问题的顺推结果（最优决策可由最优值得到） 一般性动态规划模型（其中表示某种运算，如加法）一般性动态规划模型（其中表示某种运算，如加法） 111222 1 min (or max ), s.t. ,( ), 1 nnn kkkkkkkkk ds uds uds u sTs usSuUskn 逆推求解逆推求解 11 1 ( ) ( )0, ( )min,1 k nn kkkkk u Us

14、fssS fsds ufTs usS kn 顺推求解顺推求解 11 11 , ,( ) ( )0, ( )min,1, k kk kkkk Ts us s Su Us f ssS fsds ufssSkn （的含义根据问题定）（的含义根据问题定）0 问题：动态规划方法能否保证最优解？ 动态规划方法如何节省计算量？ 问题：动态规划方法能否保证最优解？ 动态规划方法如何节省计算量？ 穷举（可保证最优解）穷举（可保证最优解） 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 4 3 5 6

15、2 1 3 3 总路径数总路径数 2 3 2 224 加法次数加法次数 5 24120 逆推求解逆推求解 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 4 3 5 6 2 1 3 3 4 0 3 7 5 5 12 10 8 9 13 15 17 加法次数加法次数 2 3 2 4 3 2222 等价于穷举 无重复计算 等价于穷举 无重复计算 1 B 2 B 1 C A 2 C 3 C 4 C 1 D 2 D 3 D 1 E F 2 E 4 5 2 3 6 8 7 7 5 8 4 5

16、3 4 8 4 4 3 5 6 2 1 3 3 14 17 14 11 12 14 6 7 10 12 4 5 0 顺推求解 加法次数 顺推求解 加法次数 22 22 243 2222 等价于穷举 无重复计算 等价于穷举 无重复计算 建模与求解建模与求解 投资分配问题投资分配问题 10万元资金，投资三个项目，收益分别为万元资金，投资三个项目，收益分别为 3 , 2 , 1, 0 10 s.t. 294max 321 2 321 ix xxx xxx i 2 333222111 2)(,9)(,4)(xxgxxgxxg 如何分配投资额？ 上述问题可以表示成非线性规划问题 不是凸规化，用非线性优化

17、算法不能保证得到最优解 如何分配投资额？ 上述问题可以表示成非线性规划问题 不是凸规化，用非线性优化算法不能保证得到最优解 建立序贯决策模型 阶段三个决策阶段，顺序决策三个项目投资额 状态 阶段实际投资额 建立序贯决策模型 阶段三个决策阶段，顺序决策三个项目投资额 状态 阶段实际投资额k决策 状态转移函数 决策 状态转移函数 k x 阶段开始可用投资额阶段开始可用投资额 k s k ,1,2,3 k Ts xsx k 阶段指标 允许决策集 阶段指标 允许决策集 0,1,2,3 k Ussk 2 123 ,4 ,9 ,2ds xx ds xx ds xx 状态集状态集 1 10 ,0,10 ,2

18、,3,4 k SSk 逆推求解（表示 及以后阶段总收益）逆推求解（表示 及以后阶段总收益） 44 1 ( ) ( )0, ( )max, k kkkkk x Us f ssS fsds xfTs xsS 22 33 0 :( )max 22 x s sSf sxs 2 2 22 0 :( )max 92max 2,9 x s sSf sxsxss （凸函数最大值在边界达到）（凸函数最大值在边界达到） 逆推公式逆推公式 2 11 010 2 10:(10)max 4max 2(10) ,9(10) max 2 10 ,9 10,4 10200 x sSsfxxx 由最优值定最优决策由最优值定最优

19、决策 * 12123223 0,1010,0,10,10 xsxxssxx k( ) k fs 顺推求解（表示 阶段以前总收益）顺推求解（表示 阶段以前总收益） 11 11 ,( ) ( )0, ( )max, kk kkkk sx s s Sx Us f ssS fsds xfssS 顺推公式顺推公式 k 1 2 10 ,00 ( )max4max 44 10 sx sx s s Sx sx s f sxxs 3 010 010 0 ( )max 94 10max 94 109 10 sx sxs s x s f sxsxsxs 22 4 010 010 0 2 ( )max 29 10ma

20、x 29 10 max 9 10,2 10 sx sxs s x s f sxsxsx ss * 433221 0,10,10010,0,0 1010,0sxsxsx ( ) k fs 连续状态变量的离散化求解方法连续状态变量的离散化求解方法 1 ( ) ( )min, k kkkkk u Us fsds ufTs usS 连续状态变量动态规划问题关键是求解下述递推方程 只有在特殊情况下才能得到的解析表达式 连续状态变量动态规划问题关键是求解下述递推方程 只有在特殊情况下才能得到的解析表达式 ( ) k fs 一般情况下，可以用离散点集近似连续状态变量集 将原问题近似转换成和最短路问题类似的多

21、阶段问题 一般情况下，可以用离散点集近似连续状态变量集 将原问题近似转换成和最短路问题类似的多阶段问题 k S 投资分配问题的离散化求解方法 将连续区间离散化为有限点集 投资分配问题的离散化求解方法 将连续区间离散化为有限点集 10, 010, 8 , 6 , 4 , 2, 0 等价于 求右边 的最长 路问题 等价于 求右边 的最长 路问题 21 4ss 32 9ss 2 43 2ss 2 8 0 4 6 10 2 8 0 4 6 10 100 21 4ss 32 9ss 2 43 2ss 2 8 0 4 6 10 0 2 8 0 4 6 10 200 8 128 72 32 0 200 12

22、8 72 36 18 0 200 010 逆序求解逆序求解 21 4ss 32 9ss 2 43 2ss 顺序求解顺序求解 2 8 0 4 6 10 0 2 8 0 4 6 10 0 72 18 36 54 0 8 16 24 32 40 0 20010 90 背包问题背包问题 10吨卡车，装三种货物，单位重量和价值如下吨卡车，装三种货物，单位重量和价值如下 321 321 321 , 10543 s.t. 654max xxx xxx xxx 如何装载使总价值最大？ 静态优化模型 这是一个 如何装载使总价值最大？ 静态优化模型 这是一个NP难问题难问题 1 2 3货物编号 单位重量（吨） 单

23、位价值 货物编号 单位重量（吨） 单位价值 3 4 4 56 5 非负整数非负整数 建立序贯决策模型 阶段三个决策阶段，顺序决策三种货物装载量 状态 阶段实际装载量 建立序贯决策模型 阶段三个决策阶段，顺序决策三种货物装载量 状态 阶段实际装载量 10 1 s k决策 状态转移方程 决策 状态转移方程 k x 阶段开始可用装载量，阶段开始可用装载量， k s k 211322433 3 ,4,5ssx ssxssx 阶段指标 允许决策集 阶段指标 允许决策集112233 3, 4,5xsxsxs 123 4 ,5,6xxx 状态集状态集 14 0,0 k sss k x， 非负整数， 非负整数

24、 转化成最长路问题转化成最长路问题 7 3 10 4 1 1 10 4 2 0 10 0 4 12 8 0 5 10 0 5 0 5 0 3 7 6 1 10 4 2 0 5 0 12 6 6 6 0 0 0 0 阶段指标 状态转移 阶段指标 状态转移 123 4 ,5,6xxx 211322433 3 ,4,5ssx ssxssx 顺序求解顺序求解 7 3 10 4 1 1 10 4 2 0 10 0 4 12 8 0 5 10 0 5 0 5 0 3 7 6 1 10 4 2 0 5 0 12 6 6 6 0 0 0 0 0 4 8 12 0 4 5 8 9 10 12 13 13 12

25、10 9 最优解最优解 0, 1, 2 * 3 * 2 * 1 xxx 最优目标最优目标 3(0) 13f 旅行商问题旅行商问题 下图四个城市，任何两个城市间均有道路相连，路程 由图中数字所示。从出发，找出一条经过其他每个 城市最终回到的最短路线 下图四个城市，任何两个城市间均有道路相连，路程 由图中数字所示。从出发，找出一条经过其他每个 城市最终回到的最短路线 1 v 1 v 1 v 4 v 3 v 2 v 7 6 9 7 8 5 8 5 6 5 9 8 转换成多阶段决策问题 直接以城市为状态会存在后效性问题，如下图，处的 容许决策取决于第二阶段状态值 转换成多阶段决策问题 直接以城市为状态

26、会存在后效性问题，如下图，处的 容许决策取决于第二阶段状态值 4 v 3 v 2 v 1 v 4 v 3 v 2 v 4 v 3 v 2 v 1 v 3 v 无后效性的状态设置方法 ：步到达城市， 无后效性的状态设置方法 ：步到达城市，,k i s i vk13, 24ki 1 v 234 |,vv v 4 v 3 v 2 v 324 |,vv v 423 |,vv v 23 |vv 34 |vv 24 |vv 32 |vv 42 |vv 43 |vv 1234 |,vv v v 7 6 9 7 8 5 8 5 6 5 9 8 7 9 5 8 5 8 逆推求解逆推求解 1 v 234 |,vv

27、 v 4 v 3 v 2 v 324 |,vv v 423 |,vv v 23 |vv 34 |vv 24 |vv 32 |vv 42 |vv 43 |vv 1234 |,vv v v 7 6 9 7 8 5 8 5 6 5 9 8 7 9 5 8 5 8 0 6 7 9 13 15 15 14 15 14 22 18 20 23 最优路径：最优路程：最优路径：最优路程： 13421 vvvvv23 迭代求解方法迭代求解方法 值迭代方法值迭代方法 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 （无阶段划分）最短路问题（无阶段划分）最短路问题 下图五个城市，

28、任何两个城市间均有道路相连，往返 路程一样，由图中数字所示。求每个城市到第五个城 市的最短路线和最短路程 下图五个城市，任何两个城市间均有道路相连，往返 路程一样，由图中数字所示。求每个城市到第五个城 市的最短路线和最短路程 min, u U s f sd s uf T s usS 最优值方程：最优值方程： 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2首先取首先取 15 ,15 ii fvd v vi 然后对按下述公式迭代然后对按下述公式迭代 1 15 min, kiijkj j fvd v vfv 如果到某个满足 那么就成立 如果到某个满足 那么就成立

29、k 1 ,15 kiki fvfvi 15 min,15 kiijkj j fvd v vfvi 于是得到最优值方程的解 最优路线可以由最优值函数确定 于是得到最优值方程的解 最优路线可以由最优值函数确定 ,15 iki f vfvi 1k 值迭代方法值迭代方法 直接在图上进行值迭代直接在图上进行值迭代 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 2 0 7 5 3 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 2 0 5.5 4 3 15 , ii fvd v v 21 15 min, iijj j fvd v v

30、fv 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 2 0 5.5 4 3 2i fv 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 2 0 4.5 4 3 32 15 min, iijj j fvd v vfv 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 2 0 4.5 4 3 3i fv 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 2 0 4.5 4 3 43 , ii fvfvi 43 15 min, iijj j fvd v vfv

31、 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 2 0 4.5 4 3 根据最优值确定最优路线 最优路线：最优值： 根据最优值确定最优路线 最优路线：最优值： 45 vv 3 345 vvv 4 2345 vvvv 4.5 15 vv 2 保证最短路问题的值迭代法收敛的充要条件：保证最短路问题的值迭代法收敛的充要条件： 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 没有总路程之和小于零的回路没有总路程之和小于零的回路 例如，右图不满足条件例如，右图不满足条件 3453 vvvv 1 理由：理由： 1ki fv 就是经过

32、不超过个中转城市到达目的 地的最短路，城市数有限，最后必重复，没有负回 路的重复不可能减少任何点的总路程 就是经过不超过个中转城市到达目的 地的最短路，城市数有限，最后必重复，没有负回 路的重复不可能减少任何点的总路程 i v k 1 15 min, kiijkj j fvd v vfv 15 , ii fvd v v 策略迭代方法策略迭代方法 无回路策略无回路策略 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 一个策略就是在每个点的某种一个策略就是在每个点的某种 决策构成的集合，写成决策构成的集合，写成 ( ),15 i Pp vi 12345 ( )4

33、,()1,()2,()3,()5p vp vp vp vp v 其中表示后面城市的下标其中表示后面城市的下标 ( ) i p v i v 没有决策在一个回路上的策略称为无回路的策略没有决策在一个回路上的策略称为无回路的策略 例如：下面是无回路的策略 下面不是无回路的策略 例如：下面是无回路的策略 下面不是无回路的策略 12345 ( )4,()4,()4,()5,()5p vp vp vp vp v 策略迭代法（策略空间迭代法）策略迭代法（策略空间迭代法） 任意选取一个无回路策略任意选取一个无回路策略 11( ),1 5 i Pp vi 求解线性方程组 （无回路的策略保证方程有唯一解） 利用确

34、定改进的策略 改进途经 求解线性方程组 （无回路的策略保证方程有唯一解） 利用确定改进的策略 改进途经 ()() 5 ,14 0 kiki kii pvkpv k fvcfvi fv 得得 ,15 ki fvi ,15 ki fvi 11( ),1 5 kki Ppvi 11 ()() 15 min,14 kiki i pvkpvijkj j cfvcfvi 重复上述过程直到策略不改变重复上述过程直到策略不改变 1421 3243 55 ( ),() (),() () p vvp vv p vvp vv p vv 有回路策略有回路策略 1144 2211 3322 4433 kk kk kk

35、kk fvcfv fvcfv fvcfv fvcfv 有（无）回路的策略和方程组的关系 无解 无回路策略 有（无）回路的策略和方程组的关系 无解 无回路策略 12 34 5 ( )4,()4 ()4,()5 ()5 p vp v p vp v p v 1144 2244 3344 4455 kk kk kk kk fvcfv fvcfv fvcfv fvcfv 54123 0, kkkkk fvfvfvfvfv 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 用策略迭代法解最短路问题的例子用策略迭代法解最短路问题的例子 1112 1314 15 ( )4,(

36、)4 ()4,()5 ()5 p vp v p vp v p v 1114 1214 1314 1415 2 5 1 3 fvfv fvfv fvfv fvfv 11 12 13 14 5 8 4 3 fv fv fv fv 22 ()1()1 15 min,14 ii i pvpvijj j cfvcfvi 2122232415 ( )5,()3,()4,()5,()5p vp vp vp vp v 1 v 4 v 3 v 5 v 2 v 5 1 0.5 5 3 7 5 2 6 2 继续迭代继续迭代 2125 2223 2324 2425 2 0.5 1 3 fvfv fvfv fvfv f

37、vfv 21 22 23 24 2 4.5 4 3 fv fv fv fv 33 ()2()2 15 min,14 ii i pvpvijj j cfvcfvi 2122 232425 ( )5,()3 ()4,()5,()5 p vp v p vp vp v 3132333435 ( )5,()3,()4,()5,()5p vp vp vp vp v 32 PP停止停止 3132333435 ( )5,()3,()4,()5,()5p vp vp vp vp v 最优策略 最优路径： 最优策略 最优路径： 45 vv 345 vvv 2345 vvvv 15 vv 同值迭代法结果一样同值迭代法结果一样