管理運籌學-動態(tài)規(guī)劃-展示頁
2025-01-27 19:16本頁面
【正文】 最大 ， 為 18萬元 。 表 75中 s1 = 6時 f *1(s1) =18，值最大，故 s1* = 6。 設 sk = 在給 k分廠分配時尚余的套數(shù)； xk = 分給 k分廠的套數(shù)； 可知狀態(tài)方程為 sk+1 = sk xk vk ( sk, xk ) = 從現(xiàn)有 sk套設備中分給 k分廠 xk套 設備后的預計創(chuàng)利額； fk ( sk, xk ) = 將現(xiàn)有 sk套設備從 k 3 分配后 (其中 k分廠分得 xk套 )的預計創(chuàng)利額之和； fk* ( sk ) = max { fk ( sk, xk )} 0≤xk≤sk 第 7章 動態(tài)規(guī)劃 16 離散確定型典例 函數(shù)基本方程為 f4*(s4) = 0 fk*(sk) = max {vk(sk, xk) + fk+1*(sk+1)}, k=3,2,1 0≤ xk≤ sk 還有 fk(sk ,xk) = vk(sk, xk) + fk+1*(sk+1) 2 . 按逆序遞推法逐段求解 (1) k=3 此時， 1， 2廠已分完，而目前所剩設備套數(shù)為 s3= 0， 1， 2， 3， 4， 5， 6 允許決策為 x3= 0， 1， 2， 3， 4， 5， 6 得下表。預計各分廠分得不同套數(shù)的設備后每年創(chuàng)造的 利潤如下表所示。 據(jù)預測， 今后五年不同價格下每年盈利如表所示 , 但是各相鄰年度價格增減不超過 1 元。 遞推 (逆 推 )求解 3176。 二、函數(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章 動態(tài)規(guī)劃 10 基本概念 . 3 動態(tài)規(guī)劃的 基本方法 1176。 常用函數(shù) ： fk(sk,xk) = vi(si,xi) n ? i= k fk(sk,xk) = vi(si,xi) n ? i= k 積函數(shù) 和函數(shù) 第 7章 動態(tài)規(guī)劃 8 七 、 最優(yōu)解 (1) 最優(yōu)指標函數(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)} 特別當 k=1時 ,稱為 最優(yōu)策略 ，記為 p1* (s1) = { x1*(s1),… ,xk*(sk),… ,xn*(sn)} (3) 最優(yōu)決策 構(gòu)成最優(yōu)策略的決策 稱為 最優(yōu)決策 ，記為 xk*。 ∈ P1 (2) 過程指標函數(shù) 用 fk(sk,xk)表示 第 k子過程的指標函數(shù) 。 五、策略 由各階段決策 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子過程策略 ，簡稱 子策略 。用 sk表示第 k段的狀態(tài)，稱為第 k段 狀態(tài)變量 。用 k = 1， 2， … ， n 表示階段序號，稱為 階段變量 。 用 xk表示第 k段的決策，稱為第 k段 決策變量 。 第 7 章 Dynamic Programming DP 動 態(tài) 規(guī) 劃 第 7章 動態(tài)規(guī)劃 2 引言 基本概念 離散確定型典例 其他典例 第 7章 動態(tài)規(guī)劃 第 7章 動態(tài)規(guī)劃 3 … S’k+1 … … S2 . 1 多階段決策問題 階段、決策、策略 . 2 動態(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章 動態(tài)規(guī)劃 4 引言 二、 動態(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 —— 標號法 第 7章 動態(tài)規(guī)劃 5 三、決策 是指人們對某一階段活動中各種不同的 行為 或 方案 或 途徑 等的 一種 選擇 。 由于決策隨狀態(tài) 而變 ,所以決策變量 xk是狀態(tài)變量 sk的函數(shù) ,記為 xk= xk(sk) 基本概念 動態(tài)規(guī)劃的 基本概念 一 、 階段 把所研究的問題恰當?shù)膭澐殖扇舾蓚€相互聯(lián)系的階段。 二、狀態(tài) 狀態(tài)表示某段的初始條件。 sk∈ Sk ∈ Xk 第 7章 動態(tài)規(guī)劃 6 基本概念 四、狀態(tài)轉(zhuǎn)移方程 sk+1與 sk,xk之間必須能夠建立一種明確的數(shù)量對應關(guān)系，記為 Tk(sk,xk), 即有 sk+1 = Tk(sk
教學課件相關(guān)推薦
鄂ICP備17016276號-1