管理運(yùn)籌學(xué)-動(dòng)態(tài)規(guī)劃(已修改)
2025-01-30 19:16 本頁面
【正文】 第 7 章 Dynamic Programming DP 動(dòng) 態(tài) 規(guī) 劃 第 7章 動(dòng)態(tài)規(guī)劃 2 引言 基本概念 離散確定型典例 其他典例 第 7章 動(dòng)態(tài)規(guī)劃 第 7章 動(dòng)態(tài)規(guī)劃 3 … S’k+1 … … S2 . 1 多階段決策問題 階段、決策、策略 . 2 動(dòng)態(tài)規(guī)劃的 基本特性 一、多階段決策問題的 基本特性 引言 Sk Sk+1 Sn T S’n Q = S1 反證法 容易得證。 若 {S2 , … , Sk , Sk+1 , … , Sn , T} 全程最優(yōu) 則 {Sk+1 , … , Sn , T} 子程最優(yōu) 第 7章 動(dòng)態(tài)規(guī)劃 4 引言 二、 動(dòng)態(tài)規(guī)劃 方法 的 基本思路 例 1 最短路問題 1 2 3 4 3 4 0 4 7 6 11 7 8 11 階段 A1 2 4 3 7 4 6 3 2 4 4 1 5 1 4 6 3 3 3 3 4 A3 B1 Q A2 B2 B3 T C1 C2 —— 標(biāo)號法 第 7章 動(dòng)態(tài)規(guī)劃 5 三、決策 是指人們對某一階段活動(dòng)中各種不同的 行為 或 方案 或 途徑 等的 一種 選擇 。 用 xk表示第 k段的決策，稱為第 k段 決策變量 。 由于決策隨狀態(tài) 而變 ,所以決策變量 xk是狀態(tài)變量 sk的函數(shù) ,記為 xk= xk(sk) 基本概念 動(dòng)態(tài)規(guī)劃的 基本概念 一 、 階段 把所研究的問題恰當(dāng)?shù)膭澐殖扇舾蓚€(gè)相互聯(lián)系的階段。用 k = 1， 2， … ， n 表示階段序號，稱為 階段變量 。 二、狀態(tài) 狀態(tài)表示某段的初始條件。用 sk表示第 k段的狀態(tài)，稱為第 k段 狀態(tài)變量 。 sk∈ Sk ∈ Xk 第 7章 動(dòng)態(tài)規(guī)劃 6 基本概念 四、狀態(tài)轉(zhuǎn)移方程 sk+1與 sk,xk之間必須能夠建立一種明確的數(shù)量對應(yīng)關(guān)系，記為 Tk(sk,xk), 即有 sk+1 = Tk(sk,xk) 這種明確的數(shù)量關(guān)系稱為 狀態(tài)轉(zhuǎn)移方程 。 五、策略 由各階段決策 xk構(gòu)成的決策序列 ,稱為 全過程策略 ,簡稱 策略 ,記為 p1(s1),有 p1(s1) = { x1(s1),x2(s2),… ,xn(sn)} pk(sk) = { xk(sk),xk+1(sk+1),… ,xn(sn)} ∈ Pk 稱為 第 k子過程策略 ，簡稱 子策略 。 ∈ P1 而 第 7章 動(dòng)態(tài)規(guī)劃 7 基本概念 六、指標(biāo)函數(shù) (1) 階段指標(biāo)函數(shù) 用 vk(sk,xk)表示第 k段處于 sk狀態(tài)且所作決策為 xk 時(shí)的指標(biāo)，則它就是 第 k段指標(biāo)函數(shù) ，簡記為 vk。 ∈ P1 (2) 過程指標(biāo)函數(shù) 用 fk(sk,xk)表示 第 k子過程的指標(biāo)函數(shù) 。 它是各 vk的累積效應(yīng)。 常用函數(shù) ： fk(sk,xk) = vi(si,xi) n ? i= k fk(sk,xk) = vi(si,xi) n ? i= k 積函數(shù) 和函數(shù) 第 7章 動(dòng)態(tài)規(guī)劃 8 七 、 最優(yōu)解 (1) 最優(yōu)指標(biāo)函數(shù) fk*(sk) = opt {fk(sk, pk(sk))}, k=1,2,… ,n pk∈ Pk (2) 最優(yōu)策略 能使上式成立的子策略 pk*稱為 最優(yōu)子策略 ，記為 pk* (sk) = { xk*(sk),… ,xn*(sn)} 特別當(dāng) k=1時(shí) ,稱為 最優(yōu)策略 ，記為 p1* (s1) = { x1*(s1),… ,xk*(sk),… ,xn*(sn)} (3) 最優(yōu)決策 構(gòu)成最優(yōu)策略的決策 稱為 最優(yōu)決策 ，記為 xk*。 (4) 最優(yōu)值 ： 最優(yōu)策略對應(yīng)的最優(yōu)指標(biāo) f *1 基本概念 第 7章 動(dòng)態(tài)規(guī)劃 9 基本概念 動(dòng)態(tài)規(guī)劃的 基本方程 一 、 最優(yōu)化原理 作為一個(gè) 全過程最優(yōu)策略 具有這樣的 性質(zhì) ： 無論過去的狀態(tài)和決策如何，對前面所形成的狀態(tài)而言， 余下的諸決策必構(gòu)成最優(yōu)策略 。 二、函數(shù)基本方程 f*n+1(sn+1) = 0 f*k(sk) = opt {vk(sk,xk)+fk+1*(sk+1)} xk∈ Xk f*n+1(sn+1) = 1 f*k(sk) = opt {vk(sk,xk) fk+1*(sk+1)} xk∈ Xk 和 積 k = n, n1, … , 2, 1 k = n, n1, … , 2, 1 第 7章 動(dòng)態(tài)規(guī)劃 10 基本概念 . 3 動(dòng)態(tài)規(guī)劃的 基本方法 1176。 建立模型 (1) 劃分階段，設(shè)定 k (2) 設(shè)定狀態(tài)變量 sk (3) 設(shè)定決策變量 xk (4) 建立 狀態(tài)轉(zhuǎn)移方程 (5) 確定指標(biāo)函數(shù) vk， fk* (6) 建立 函數(shù)基本方程 2176。 遞推 (逆 推 )求解 3176。 得出 (順 推 )結(jié)論 第 7章 動(dòng)態(tài)規(guī)劃 11 基本概念 . 4 動(dòng)態(tài)規(guī)劃的 基本類型 一、 按階段變量 k劃分 (1) 定期型 : k = 1, 2, … , n (2) 不定期型 : k = 1, 2, … , n (解前未知 ) (3) 無期型 : k = 1, 2, … , n , … 二 、 按狀態(tài)變量 sk劃分 確定型 隨機(jī)型 離散型 連續(xù)型 第 7章 動(dòng)態(tài)規(guī)劃 12 離散確
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1