42DP基本概念與最優(yōu)化原理課件

1、42DP基本概念與最優(yōu)化原理42DP基本概念與最優(yōu)化原理一、基本概念 DP中描述多段決策過程的基本概念主要有：階段和階段變量；狀態(tài)和狀態(tài)變量；決策、決策變量和決策序列；狀態(tài)轉(zhuǎn)移方程；階段效應和目標函數(shù)等。 一、基本概念 DP中描述多段決策過程的基本概念主要有： 1. 階段和階段變量把所研究的多段決策過程恰當?shù)貏澐譃槿舾蓚€相互獨立又相互聯(lián)系的部分，每一個部分就稱為一個階段。事實上一個階段也就是需要作出一個決策的子問題部分。通常階段是按照過程進行的時間和空間上的先后順序劃分的，并用階段變量k表示。階段數(shù)等于多段決策過程中從開始到結(jié)束所需要作出決策的數(shù)目，劃分階段的目的是便于求解。 1. 階段和階段

2、變量把所研究的多段決策過程恰當?shù)貏澐?. 狀態(tài)和狀態(tài)變量 狀態(tài)是描述系統(tǒng)狀況所必須的信息。一般定義為某一個階段的初始點、初始位置或初始情況。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息，階段k的狀態(tài)表示為xk。比如：在最短路問題中，狀態(tài)就是網(wǎng)絡中的各個節(jié)點。 2. 狀態(tài)和狀態(tài)變量 狀態(tài)是描述系統(tǒng)狀況 狀態(tài)變量的取值有一定的允許范圍，稱為狀態(tài)可能集。狀態(tài)可能集可以是一個離散取值的集合，也可以是一個連續(xù)的區(qū)間，視所給問題而定。 狀態(tài)可能集是關(guān)于狀態(tài)的約束條件。狀態(tài)可能集用相應階段狀態(tài)xk的大寫字母Xk表示，其中xkXk 狀態(tài)變量的取值有一定的允許范圍，稱為狀態(tài)可能集。狀態(tài)可能3. 決

3、策、決策變量和決策序列 決策就是決策者從本階段出發(fā)對下一階段狀態(tài)的選擇。 多段決策過程的發(fā)展是用各個階段的狀態(tài)演變來描述的。因為用狀態(tài)描述的過程具有無后效性，因此在進行階段決策時，只須根據(jù)當前的狀態(tài)而無須考慮過去的歷史。在階段k如果給出了決策變量uk隨狀態(tài)變量 xk變化的函數(shù)，稱為決策函數(shù)，表示為uk(xk)。 3. 決策、決策變量和決策序列 決策 決策變量的允許取值范圍，稱為允許決策集合。允許決策集合是決策的約束條件。 uk的允許決策集合表示為Uk，ukUk 。 Uk要根據(jù)相應的狀態(tài)可能集Xk并結(jié)合具體問題來確定。 決策序列就叫策略。策略有全過程策略和k-子策略之分。全過程策略是整個n段決策

4、過程中依次進行的n個階段決策構(gòu)成的決策序列，簡稱策略，表示為： 決策變量的允許取值范圍，稱為允許決策集合 從階段k到階段n依次進行的階段決策構(gòu)成的決策序列稱為k-子策略，表示為： 當k=1時，k-子策略就是全過程策略。 在n段決策問題中，各階段的狀態(tài)可能集和決策允許集確定了決策的允許范圍。 特別，過程的初始狀態(tài)不同，決策和策略也就不同，即策略是初始狀態(tài)的函數(shù)。 從階段k到階段n依次進行的階段決策構(gòu)4. 狀態(tài)轉(zhuǎn)移方程 狀態(tài)轉(zhuǎn)移方程表示從階段k到階段k+1的狀態(tài)轉(zhuǎn)移規(guī)律的表達式。 多階段過程的發(fā)展就是用階段狀態(tài)的相繼演變來描述的。對具有無后效性的多段決策過程，系統(tǒng)由從階段k到階段k+1的狀態(tài)轉(zhuǎn)移方

5、程表示為：4. 狀態(tài)轉(zhuǎn)移方程 狀態(tài)轉(zhuǎn)移方程表示 意即階段的狀態(tài)完全由階段的狀態(tài)和決策確定，與系統(tǒng)過去的狀態(tài) x1,x2,xk-1及其決策u1(x1)，u2(x2)，,uk-1(xk-1)無關(guān)。 Tk( xk,uk)稱為變換函數(shù)或變換算子。變換函數(shù)可以分為確定型和隨機型兩種類型，據(jù)此形成確定型動態(tài)規(guī)劃和隨機型動態(tài)規(guī)劃。 問：狀態(tài)轉(zhuǎn)移方程是否一定是數(shù)學意義上的方程？ 意即階段的狀態(tài)完全由階段的狀態(tài)和決策確5. 階段效應和目標函數(shù) 多段決策過程中，在階段k的狀態(tài)xk執(zhí)行決策uk ，不僅帶來系統(tǒng)狀態(tài)的轉(zhuǎn)移，而且也必然帶來對目標函數(shù)的影響。階段效應就是執(zhí)行階段決策時所帶來的目標函數(shù)的增量。 在具有無后效

6、性的多段決策過程中，階段效應完全由階段k的狀態(tài)xk和決策uk決定，與階段以前的狀態(tài)和決策無關(guān)，表示為 5. 階段效應和目標函數(shù) 多段決策 多階段決策過程關(guān)于目標函數(shù)的總效應是由各階段的階段效應累積形成。適于動態(tài)規(guī)劃求解的問題的目標，必需具有關(guān)于階段效應的可分離形式、遞推性和對于變元RK+1的嚴格單調(diào)性。k-子過程的目標函數(shù)可以表示為: 多階段決策過程關(guān)于目標函數(shù)的總效應是由各階今后要討論的主要就是這種形式的目標函數(shù)。其中 表示某種運算，可以是加、減、乘、除、開方等。經(jīng)濟管理領(lǐng)域中最常見的目標函數(shù)取階段效應之和的形式，即：今后要討論的主要就是這種形式的目標函數(shù)。其中 表示某種運二、多階段決策過程

7、的數(shù)學模型（DP的建模）1 構(gòu)模條件： 一個大前提：恰當?shù)貏澐謫栴}的階段， 把問題化為多階段決策過程； 四個條件 (詳見下頁） 一個方程動態(tài)規(guī)劃基本方程 （DP基本方程）二、多階段決策過程的數(shù)學模型（DP的建模）1 構(gòu)模條件： 四 個 條 件（1）正確地選擇狀態(tài)變量：能描述過程的演變特征；-滿足無后效性指系統(tǒng)從某個階段往后的發(fā)展，完全由本階段所處的狀態(tài)及其往后的決策決定，與系統(tǒng)以前的狀態(tài)和決策無關(guān)。即過程過去的歷史只能通過當前的狀態(tài)去影響未來的發(fā)展，當前狀態(tài)是未來過程的初始狀態(tài)。 四 個 條 件（1）正確地選擇狀態(tài)一個例子：負指數(shù)分布具有無記憶性 Ps+t| s=Pt=e-t可知性各階段狀態(tài)變

8、量的值直接或間接均為已知。（2）能確定決策變量及各階段的允許決策集合；（3）能寫出狀態(tài)轉(zhuǎn)移方程；（4）能根據(jù)題意列出階段效應和目標函數(shù)；一個例子：負指數(shù)分布具有無記憶性 在明確四個條件（或稱四個要素）的基礎(chǔ)上，寫出動態(tài)規(guī)劃基本方程。DP模型的數(shù)學表達式一般形式：式中opt指最優(yōu)化，根據(jù)具體問題要求取max或min。 在明確四個條件（或稱四個要素）的基礎(chǔ)上，具體的 DP模型 包括：四個條件和一個方程（動態(tài)規(guī)劃基本方程）的全體。問：動態(tài)規(guī)劃模型由哪些部分構(gòu)成？具體的 DP模型 包括：問：動態(tài)規(guī)劃模型由哪些部分構(gòu)成？求解要求： (逆序)求出最優(yōu)策略，即最優(yōu)決策序列； 其中,(順序)求出最優(yōu)路線，即執(zhí)

9、行最優(yōu)策略時的最優(yōu)狀態(tài)序列： 求出最優(yōu)目標函數(shù)值:求解要求： (逆序)求出最優(yōu)策略，即最優(yōu)決策序列； 其中三、DP基本方程Bellman函數(shù)（最優(yōu)指數(shù)函數(shù)）亦稱條件最優(yōu)目標函數(shù)。 該函數(shù)是為了便于應用最優(yōu)性原理，建立動態(tài)規(guī)劃基本方程所定義的輔助函數(shù) ，是在階段K從初始狀態(tài) 出發(fā)，執(zhí)行最優(yōu)決策序列或策略到達過程終點時的目標函數(shù)取值。 對于目標函數(shù)是階段效應之和的多段決策過程而言:三、DP基本方程Bellman函數(shù)（最優(yōu)指數(shù)函數(shù)）亦稱條件最 為了將關(guān)于多段決策過程的任一階段狀態(tài) 的最優(yōu)策略和最終的最優(yōu)策略相區(qū)別，稱前者為條件最優(yōu)策略，意即相對于狀態(tài) 時的最優(yōu)策略。構(gòu)成條件最優(yōu)策略的決策稱為條件最優(yōu)

10、決策。階段k處于狀態(tài) 的條件最優(yōu)決策表示為 ，簡記為 ，相應的條件最優(yōu)策略表示為: 為了將關(guān)于多段決策過程的任一階段狀態(tài) 執(zhí)行條件最優(yōu)策略時的階段狀態(tài)序列稱為條件最優(yōu)路線，表示為 條件最優(yōu)目標函數(shù)值亦稱執(zhí)行條件最優(yōu)策略時的目標函數(shù)值，因此其中, 執(zhí)行條件最優(yōu)策略時的階段狀態(tài)序列稱為條件最優(yōu)2. 最優(yōu)化原理 最優(yōu)策略具有的基本性質(zhì)是：無論初始狀態(tài)和初始決策如何，對于前面決策所造成的某一狀態(tài)而言，下余的決策序列必構(gòu)成最優(yōu)策略。2. 最優(yōu)化原理 最優(yōu)策略具有的基3. DP基本方程 包括主體部分和邊界條件兩個部分。特別，當目標函數(shù)為階段效應求和形式時，基本方程為3. DP基本方程 包括主體部分和邊界條件兩四、動態(tài)規(guī)劃的分類 動態(tài)規(guī)劃的表現(xiàn)形式隨多段決策過程的特點不同而不同，據(jù)此可將動態(tài)規(guī)劃作以下分類：1、按決策的特性分a、時間多段決策過程b、空間多段決策過程2、按允許決策集合的連續(xù)或不連續(xù)分a、連續(xù)多段決策過程b、離散多段決策過程四、動態(tài)規(guī)劃的分類 動態(tài)規(guī)劃的表現(xiàn)形式隨多段決策過程的3.按構(gòu)成決策序列的決策數(shù)目有限或無限分 a、有限多段決策過程 b、無限多段決策過程按狀態(tài)變化的確定或隨機性分 a、 確定型多段決策過程 b、隨機性多段決策過程按決策序列與時間起點的關(guān)系分 a、定常(與時間起點無關(guān))多段決策過程 b、非定常多段決策過程3.按構(gòu)成決