《運籌》教學(xué)課件動態(tài)規(guī)劃 8.2動態(tài)規(guī)劃的基本原理.ppt

《《運籌》教學(xué)課件動態(tài)規(guī)劃 8.2動態(tài)規(guī)劃的基本原理.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、8.2動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的目標(biāo)有多個方案,且每個方案都有一個總指標(biāo)函數(shù)值動態(tài)規(guī)劃的目標(biāo)是找到最優(yōu)的方案,也就是找到使得總指標(biāo)函數(shù)最優(yōu)(最大或最小)方案,即在總指標(biāo)函數(shù)中,一般來說s1是給定的，其它的變量都是不確定的，這樣一來總指標(biāo)函數(shù)有2n-1個變量，直接求極值非常困難。動態(tài)規(guī)劃的最優(yōu)化原理提供了另外一種求解思路。最優(yōu)化原理的語言描述一個過程的最優(yōu)策略具有這樣的性質(zhì)，即無論初始狀態(tài)及初始決策如何，對于先前決策所形成的狀態(tài)而言，其以后的所有決策必構(gòu)成最優(yōu)策略。理解1：如果第一階段到第k階段形成的策略是最優(yōu)策略的話，那么從第一階段到第t階段所形成的策

2、略也必須是最優(yōu)策略（tk)例如在一個圖中，若從點1到點5的最短路線為1→2→3→5則2→3→5是點2到點5的最短路線，3→5是點3到點5的最短路線1.利用前部子指標(biāo)函數(shù)來描述

3、由于opt{V1,t+1}僅僅與狀態(tài)st+1有關(guān)，因而也稱opt{V1,t+1}為前部最優(yōu)值函數(shù)，用ft{st+1}來表示，則上式可表示為最優(yōu)化原理的數(shù)學(xué)描述——和形式為了遞推方程形式的統(tǒng)一,可以引入f0(s1)=0,這樣一來上面的遞推公式就可寫為下式由于f0(s1)=0是專門引入的，特稱之為邊界條件最優(yōu)化原理的數(shù)學(xué)描述——和形式2.利用后部子指標(biāo)函數(shù)由于opt{Vt,n+1}僅僅與狀態(tài)st有關(guān)，因而也稱opt{Vt,n+1}為后部最優(yōu)值函數(shù)，用ft{st}來表示，則上式可表示為最優(yōu)化原理的數(shù)學(xué)描述——和形式為了遞推方程形式的統(tǒng)一,可以引入fn+1(sn

4、+1)=0,這樣一來上面的遞推公式就可寫為下式由于fn+1(sn+1)=0是專門引入的，也稱之為邊界條件最優(yōu)化原理的數(shù)學(xué)描述——和形式由于最優(yōu)值指標(biāo)函數(shù)fk(sk+1)中與狀態(tài)變量st(1≤t≤k)和決策變量ut(1≤t≤k)無關(guān)，這意味著以前的狀態(tài)和決策不影響后面的優(yōu)化過程,也就是fk+1(sk+2)僅僅與fk(sk+1)有關(guān)，把這種特性稱之為無后效性。動態(tài)規(guī)劃的無后效性1.基于前部最優(yōu)值指標(biāo)函數(shù)遞推方程由于最優(yōu)值指標(biāo)函數(shù)fk(sk)中與狀態(tài)變量st+1(k≤t≤n)和決策變量ut(k≤t≤n)無關(guān)，這意味著以前的狀態(tài)和決策不影響以后的優(yōu)化過程，也就是

5、fk-1(sk-1)僅僅與fk(sk)有關(guān)，把這種特性稱之為無后效性。2.基于后部最優(yōu)值指標(biāo)函數(shù)遞推方程1.利用前部子指標(biāo)函數(shù)來描述最優(yōu)化原理的數(shù)學(xué)描述——積形式其中f0(s1)=1為引入的邊界條件2.利用后部子指標(biāo)函數(shù)最優(yōu)化原理的數(shù)學(xué)描述——積形式其中fn+1(sn+1)=1是引入的邊界條件