動態(tài)規(guī)劃基本理論推廣(函數(shù)迭代與策略迭代法)（57頁)ppt課件

1、動態(tài)規(guī)劃根本實際推行函數(shù)迭代法與戰(zhàn)略迭代法本章內容舉例簡單闡明不定期與無期決策過程的方式和概念；以不定期和無期決策過程為例，引見函數(shù)迭代法和戰(zhàn)略迭代法。不定期與無期決策過程定義：多階段的決策過程的階段數(shù)N確定，稱為定期決策過程，當N不確定時，稱此類決策過程為不定期決策過程，當N趨向無窮時稱為無期決策過程。不定期與無期決策過程例1：段數(shù)不定的最短道路問題不定期決策過程n個點相互銜接組成 一個連通圖(右圖中n=5),各點標號為1,2,n。恣意兩點i，j之間的間隔(費用)記作dij 。求恣意一點i到點n(靶點)的最短道路(間隔)。322575560.51不定期與無期決策過程例1：段數(shù)不定的最短道路問

2、題不定期決策過程n個點相互銜接組成 一個連通圖(右圖中n=5),各點標號為1,2,n。恣意兩點i，j之間的間隔(費用)記作dij 。求恣意一點i到點n(靶點)的最短道路(間隔)。322575560.51不定期與無期決策過程例2：無限期決策過程模型 ，形狀變換函數(shù)為。( 存在明顯的級變量，但級數(shù)是無限的 )不定期與無期決策過程求解這類問題假設仍運用以前的逐級遞推方法，將遇到極大的計算量，為此必需尋覓新方法。函數(shù)方程可以用迭代法求解，通常有函數(shù)迭代法和戰(zhàn)略迭代法兩種迭代方法。函數(shù)迭代法與戰(zhàn)略迭代法1.函數(shù)迭代法的步驟是：(1)選初始函數(shù) (普通取 )；(2)用迭代公式及 計算其中為當前階段的形狀和

3、決策， 為知終止函數(shù)， 為迭代步數(shù), v為目的函數(shù)(3)當或函數(shù)迭代法與戰(zhàn)略迭代法(4)當或時迭代停頓，最優(yōu)值函數(shù)，最優(yōu)戰(zhàn)略 ；否那么以k+1替代k反復(2),(3).函數(shù)迭代法與戰(zhàn)略迭代法闡明：函數(shù)迭代法和戰(zhàn)略迭代法中，序列 和 的收斂性在相當廣泛的條件下是可以保證的，普通來說它與 等的詳細方式有關。函數(shù)迭代法的根本思想是以步數(shù)(段數(shù))作為參數(shù)，先求在各個不同步數(shù)下的最優(yōu)戰(zhàn)略，然后從這些最優(yōu)解中再選出最優(yōu)者，從而同時確定了最優(yōu)步數(shù)。函數(shù)迭代法與戰(zhàn)略迭代法戰(zhàn)略迭代法的根本思想是：先選定一初始戰(zhàn)略 然后按某種方式求得新戰(zhàn)略 直至最終求出最優(yōu)戰(zhàn)略。假設對某一k，對一切i有： ，那么稱 收斂，此時，

4、戰(zhàn)略就是最優(yōu)戰(zhàn)略。普通來說，選定初始戰(zhàn)略要比選定初始目的最優(yōu)值函數(shù)容易得多，且戰(zhàn)略迭代的收斂速度稍快，但其計算量要大些。函數(shù)迭代法與戰(zhàn)略迭代法 ( 是事先給定的數(shù))時迭代停頓，最優(yōu)值函數(shù),最優(yōu)戰(zhàn)略 。2.戰(zhàn)略迭代法的步驟是：(1)選初始戰(zhàn)略 ，令k=1；(2)用 求解 ，(3)用 求改良戰(zhàn)略 ，函數(shù)迭代法與戰(zhàn)略迭代法例1的求解：分析：可以不思索回路，由于含有回路的道路一定不是最短的.本問題道路的段數(shù)事先不固定，而是隨著最優(yōu)戰(zhàn)略確定的，然而形狀、決策、形狀轉移、目的函數(shù)與以前的最短道路問題的一樣.形狀記作x=i，i=1,2,n，決策記作u(i).戰(zhàn)略是對恣意形狀x的決策函數(shù)，記作u(x)。階段目

5、的是恣意兩形狀i,j間的間隔dij，目的函數(shù)V(i,u(x)是由形狀i出發(fā)，在戰(zhàn)略u(x)下到達形狀n的道路的函數(shù)迭代法與戰(zhàn)略迭代法間隔，它是階段目的之和， 并滿足可分別性要求，有最優(yōu)值函數(shù)(i)為由i出發(fā)到達n的最短間隔，即式中u*(x)是最優(yōu)戰(zhàn)略，滿足根本方程 函數(shù)迭代法與戰(zhàn)略迭代法該式記為()式，它不是一個遞推方程，而是一個關于(i)的函數(shù)方程,對固定的i使()右端 dij+(j) 到達極小的j即為最優(yōu)決策u*(i)，對一切的i求解()式得到最優(yōu)戰(zhàn)略u*(x)。不定期與無期決策過程例1：段數(shù)不定的最短道路問題不定期決策過程n個點相互銜接組成 一個連通圖(右圖中n=5),各點標號為1,2,

6、n。恣意兩點i，j之間的間隔(費用)記作dij 。求恣意一點i到點n(靶點)的最短道路(間隔)。函數(shù)迭代法與戰(zhàn)略迭代法用函數(shù)迭代法求解例1只求1,2,3,4各點到點5的最優(yōu)道路，其他類似。解：(1)假設從i點走一步到靶點5的最優(yōu)間隔為 , 那么顯然有： 最優(yōu)決策為:322575560.51函數(shù)迭代法與戰(zhàn)略迭代法 (2)假設從i點走兩步到靶點5的最優(yōu)間隔為 , 根據(jù)最優(yōu)化原理得：詳細計算如下：函數(shù)迭代法與戰(zhàn)略迭代法 注：不取含 的地方作為最優(yōu)決策函數(shù)迭代法與戰(zhàn)略迭代法 (3)假設從i點走三步到靶點5的最優(yōu)間隔為 , 那么得：計算結果如下：函數(shù)迭代法與戰(zhàn)略迭代法 (4)假設從i點走四步到靶點5的最

7、優(yōu)間隔為 , 那么得：計算結果如下：函數(shù)迭代法與戰(zhàn)略迭代法 函數(shù)迭代法與戰(zhàn)略迭代法 由于只需5個點,因此從任一點出發(fā)到達靶點,其間最多有4步(否那么，有回路)，這樣就不需繼續(xù)下去了。將計算結果列成表：i1252525252755.534.534.53355444444435353535函數(shù)迭代法與戰(zhàn)略迭代法 分析上面的結果可得：從點1到點5走一步為最優(yōu)，最優(yōu)間隔為2，最優(yōu)道路 ；從點2到點5走三步為最優(yōu)，最優(yōu)間隔為4.5,最優(yōu)道路 ；從點3到點5走兩步為最優(yōu)，最優(yōu)間隔為4,最優(yōu)道路 ；從點4到點5走一步為最優(yōu)，最優(yōu)間隔為3，最優(yōu)道路 。函數(shù)迭代法與戰(zhàn)略迭代法 最優(yōu)決策最多走4步，多于此步數(shù)，會

8、出現(xiàn)走回頭路或回路，顯然這些不是最優(yōu)道路。 從任一點出發(fā)到靶點，走m(m=1,2,)步與走m+1步的最優(yōu)間隔一樣，決策函數(shù)也一樣，假設繼續(xù)計算走m+2步、m+3步、，其結果仍一樣, 即 也就闡明 一致收斂于 ， 一致收斂于 。故當這種一出現(xiàn)，計算便可停頓。函數(shù)迭代法與戰(zhàn)略迭代法例1的求解：(戰(zhàn)略迭代法 解：第一步，先選取初始戰(zhàn)略 。如?。杭?,但必需沒有回路，每點可達靶點。第二步，由 求 ，由戰(zhàn)略迭代法的方程組可得：因戰(zhàn)略 直達靶點，應先計算：函數(shù)迭代法與戰(zhàn)略迭代法第三步，由 求 ,由求出它的解 ：時，函數(shù)迭代法與戰(zhàn)略迭代法所以， 不在含 的項取 時，函數(shù)迭代法與戰(zhàn)略迭代法所以，同理，可求得

9、,于是得到第一次戰(zhàn)略迭代的結果為以 為初始戰(zhàn)略繼續(xù)反復運用第二、三步進展迭代。第二步：由 求函數(shù)迭代法與戰(zhàn)略迭代法第三步：由 求,即由求解 。 時，所以同理，求出故第二次戰(zhàn)略迭代的結果為函數(shù)迭代法與戰(zhàn)略迭代法第二步：由 求第三步：由 求，類似前面的方法求得第三次戰(zhàn)略迭代的結果為i1234545321156535525.553534524.5435345函數(shù)迭代法與戰(zhàn)略迭代法將以上結果記錄下來：函數(shù)迭代法與戰(zhàn)略迭代法由以上結果得到 ，對一切的i都成立，闡明迭代步驟可以停頓。故找到最優(yōu)戰(zhàn)略為列表表示為從而可以得到各點到靶點(點5)的最優(yōu)道路和最優(yōu)間隔：i12345345函數(shù)迭代法與戰(zhàn)略迭代法最優(yōu)道

10、路 最短間隔值 2 4.5 4 3可以看到戰(zhàn)略迭代法得到的結果與函數(shù)迭代法的結果一致。不定期與無期決策過程例2：無限期決策過程模型 ，形狀變換函數(shù)為。( 存在明顯的級變量，但級數(shù)是無限的 )函數(shù)迭代法與戰(zhàn)略迭代法例2的求解函數(shù)迭代法解：(1)任取初值，如形狀變換函數(shù)為迭代公式為(2)i=1時，進展第一次迭代函數(shù)迭代法與戰(zhàn)略迭代法 對 求導，并令其等于零，有 可得函數(shù)迭代法與戰(zhàn)略迭代法 ，取i=2時，進展第二次迭代對 求導，并令其等于零，得函數(shù)迭代法與戰(zhàn)略迭代法故由于 ，應繼續(xù)進展迭代。當i=3時，進展第三次迭代，類似以上才方法，可得函數(shù)迭代法與戰(zhàn)略迭代法由于 ,取i=4繼續(xù)進展第四次迭代。其結

11、果如下:函數(shù)迭代法與戰(zhàn)略迭代法由于 ,可以確定該問題的最優(yōu)收益函數(shù)為最優(yōu)決策為函數(shù)迭代法與戰(zhàn)略迭代法例2的求解戰(zhàn)略迭代法解：(1)任取初始戰(zhàn)略值，如及(2)進展第一次迭代，取i=1,2,得函數(shù)迭代法與戰(zhàn)略迭代法 由于取 再來確定第二次迭代的決策 ： 函數(shù)迭代法與戰(zhàn)略迭代法上式的解為 由于，需求進展第二次迭代： 函數(shù)迭代法與戰(zhàn)略迭代法由于 ，需求繼續(xù)進展迭代，直到 時為止，節(jié)省時間，直接給出結果 ，但由于 ，因此需求繼續(xù)進展迭代。如今來確定第三次迭代的決策，有函數(shù)迭代法與戰(zhàn)略迭代法那么由于，還必需進展下次迭代。第三次迭代：函數(shù)迭代法與戰(zhàn)略迭代法由于 ，需求繼續(xù)進展迭代，直到 時為止，最后得到 由

12、于 ，因此需求繼續(xù)進展迭代。如今來確定第四次迭代的決策，有函數(shù)迭代法與戰(zhàn)略迭代法那么第四次迭代：函數(shù)迭代法與戰(zhàn)略迭代法繼續(xù)進展迭代，直到 時為止，最后得到 由于 ，因此可停頓迭代。最優(yōu)收益函數(shù)為 相應的最優(yōu)戰(zhàn)略為函數(shù)迭代法與戰(zhàn)略迭代法注：對于定義一個無期決策過程的最優(yōu)化問題，須滿足三個條件，即對一切的有：形狀轉移方程有意義；允許決策集合 有意義，而且非空，那么存在允許戰(zhàn)略使得對一切 非空；目的函數(shù) 對一切 有意義，且對一切允許戰(zhàn)略，極限 存在。函數(shù)迭代法與戰(zhàn)略迭代法注：對于定義一個無期決策過程的最優(yōu)化問題，須滿足三個條件，即對一切的有：形狀轉移方程有意義；允許決策集合 有意義，而且非空，那么存在允許戰(zhàn)略使得對一切 非空；目的函數(shù) 對一切 有意義，且對一切允許戰(zhàn)略，極限 存在。函數(shù)迭代法與戰(zhàn)略迭代法當上述三個條件成立時，就可以說，無期決策過程的最優(yōu)化的意義在于求最優(yōu)戰(zhàn)略 使得其中P是定義在無期過程上的非空允許戰(zhàn)略集。 是 P的元素， 是定義在P上的目的函數(shù)。函數(shù)迭代法與戰(zhàn)略迭代法例1、例2的共同點是在多階段決策過程中允許決策集合、形狀轉移規(guī)律、階段目的等于階段變量k無關，從而根本方程成為函數(shù)方程，稱這樣的過程是平穩(wěn)的。定義：滿足以下條件的多階段決策過程成為平穩(wěn)過程，相應的戰(zhàn)略稱為平穩(wěn)戰(zhàn)略:(1) 允許決策集合Uk(x)與k無關，可記為U(x)， 為形狀變量;(2) 形