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

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

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

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

4、戰(zhàn)略就是最優(yōu)戰(zhàn)略。普通來說，選定初始戰(zhàn)略要比選定初始目的最優(yōu)值函數(shù)容易得多，且戰(zhàn)略迭代的收斂速度稍快，但其計(jì)算量要大些。函數(shù)迭代法與戰(zhàn)略迭代法 ( 是事先給定的數(shù))時(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)略確定的，然而形狀、決策、形狀轉(zhuǎ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)下到達(dá)形狀n的道路的函數(shù)迭代法與戰(zhàn)略迭代法間隔，它是階段目的之和， 并滿足可分別性要求，有最優(yōu)值函數(shù)(i)為由i出發(fā)到達(dá)n的最短間隔，即式中u*(x)是最優(yōu)戰(zhàn)略，滿足根本方程 函數(shù)迭代法與戰(zhàn)略迭代法該式記為()式，它不是一個(gè)遞推方程，而是一個(gè)關(guān)于(i)的函數(shù)方程,對固定的i使()右端 dij+(j) 到達(dá)極小的j即為最優(yōu)決策u*(i)，對一切的i求解()式得到最優(yōu)戰(zhàn)略u*(x)。不定期與無期決策過程例1：段數(shù)不定的最短道路問題不定期決策過程n個(gè)點(diǎn)相互銜接組成 一個(gè)連通圖(右圖中n=5),各點(diǎn)標(biāo)號為1,2,

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

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

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

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

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

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

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