動態(tài)規(guī)劃的基本概念-在線瀏覽
2024-09-15 03:53本頁面
【正文】 2) … rn(xn, un) 指標函數(shù)的最優(yōu)值，稱為 最優(yōu)函數(shù)值 。 167。由于前階段的終止狀態(tài)又是后一階段的初始狀態(tài)，因此確定階段最優(yōu)決策不能只從本階段的效應出發(fā)，必須通盤考慮，整體規(guī)劃。 對此，貝爾曼在深入研究的基礎上，針對具有無后效性的多階段決策過程的特點，提出了著名的多階段決策的 最優(yōu)性原理 ： “整個過程的最優(yōu)策略具有這樣的性質：即無論過程過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構成最優(yōu)策略。 如例 1， A— B2— C1— D2— E是由 A到 E的最短路線，我們在該路線上任取一點 C1 ，按照最優(yōu)性原理 C1— D2— E應該是 C1到 E的最短路。 按最優(yōu)性原理，可以將例 1分成 A— B— C— D— E 4個階段，由后向前逐步求出各點到 E的最短線路，直至求出 A至 E的最短線路。顯然： f4（ D1） =7， u4(D1)=E f4（ D2） =8， u4(D2)=E f4（ D3） =6， u4(D3)=E K=3時，出發(fā)點有 C1， C2， C3 f3（ C1） =min｛ d（ C1D1） +f4（ D1） ,d（ C1D2） +f4（ D2）｝ =min｛ 4+7,2+8｝ =10, u3(C1)= D2 f3（ C2） =min｛ d（ C2D2） +f4（ D2） ,d（ C2D3） +f4（ D3）｝ =min｛ 5+8,7+6｝ =13, u3(C2)= D2或 D3 f3（ C3） =min｛ d（ C3D2） +f4（ D2） ,d（ C3D3） +f4（ D3）｝ =min｛ 10+8,9+6｝ =15, u3(C3)= D3 K=2時，出發(fā)點有 B1， B2， B3 f2（ B1） =min｛ d（ B1C1） +f3（ C1） ,d（ B1C2） +f3（ C2）｝ =min｛ 6+10,4+13｝ =16, u2(B1)= C1 f2（ B2） =min｛ d（ B2C1） +f3（ C1） ,d（ B2C3） +f3（ C3）｝ =min｛ 3+10,1+15｝ =13, u2(B2)= C1 f2（ B3） =min｛ d（ B3C2） +f3（ C2） ,d（ B3C3） +f3（ C3）｝ =min｛ 8+13,4+15｝ =19, u2(B3)= C3 K=1時，出發(fā)點只有 A d（ AB1） +f2（ B1） 4+16 f1（ A） =min d（ AB2） +f2（ B2） = 5+13 =18, d（ AB3） +f2（ B3） 3+19 u1(A)= B2 由 f1（ A） =18， 可知從起點 A到終點 E的最短距離為 18。稱上述遞推關系為 動態(tài)規(guī)劃的基本方程 ，這個方程是最優(yōu)化原理的具體表達形式。 另一方面，由于 k+1階段的狀態(tài) xk+1=T(xk, uk)是由前面的狀態(tài)和決策所形成的，在計算 fk+1（ xk+1） 時還不能具體確定 xk+1的，這就要求必須就 k+1階段的各個可能狀態(tài)計算 fk+1（ xk+1）， 因此動態(tài)規(guī)劃不但能求出整個問題的最優(yōu)策略和最優(yōu)目標值，而且還能求出決策過程中所有可能狀態(tài)的最優(yōu)策略及最優(yōu)目標值。 3 建立動態(tài)規(guī)劃數(shù)學模型的步驟 “最優(yōu)化原理”是動態(tài)規(guī)劃的核心 ,所有動態(tài)規(guī)劃問題的遞推關系都是根據(jù)這個原理建立起來的 ,并且根據(jù)遞推關系依次計算 ,最終可求得動態(tài)規(guī)劃問題的解。有些問題不具有時空次序，也可以人為地引進時空次序，劃分階段。這一步是形成動態(tài)模型的關鍵，狀態(tài)變量是動態(tài)規(guī)劃模型中最重要的參數(shù)。 ⑵要滿足無后效性。 ⑶遞推性。
物理相關推薦
鄂ICP備17016276號-1