管理運(yùn)籌學(xué)-動(dòng)態(tài)規(guī)劃(完整版)
【正文】 令 E (sk+1) = ? p(sk+1) fk+1*(sk+1) = fk+1*(500) + fk+1*(550) + fk+1*(600) 則函數(shù)方程為 fk*(sk) = min {sk， E(sk+1)}， k = 4， 3， 2， 1 又因第五周只得采購(gòu)，即 x5* = 1， 故有 f5*(s5) = s5 此即函數(shù)的 邊界條件 。 f 1 ( 1 , x 1 ) = b+100 x 1 + 806() x 1 x 1 s 1 0 1 2 3 4 f 1 ( s 1 ) x 1 * 1 806 884 790 774 804 774 3 * 。按函數(shù)方程有 f4*(s4) = min { s4 ， E(s5)} 而 E (s5) = f5*(500) + f5*(550) + f5*(600) = 500 + 550 + 600 = 555 故有 f5*(s5) = s5 500， 當(dāng) s5 = 500 550， 當(dāng) s5 = 550 600， 當(dāng) s5 = 600 = 第 7章 動(dòng)態(tài)規(guī)劃 39 其他典例 f4*(s4) = min { s4 , 555 } 500，當(dāng) s4 = 500 (x4* = 1 ) 550，當(dāng) s4 = 550 (x4* = 1 ) 555，當(dāng) s4 = 600 (x4* = 0 ) = x4*= 1 x4* = 0 第 7章 動(dòng)態(tài)規(guī)劃 40 類似可求得 500， 當(dāng) s3 = 500， (x3* = 1) 537， 當(dāng) s3 = 550 或 600 (x3* = 0) 500， 當(dāng) s2 = 500 (x2* = 1) 526, 當(dāng) s2 = 550 或 600 (x2* = 0) 500， 當(dāng) s1= 500 (x1* = 1) 518， 當(dāng) s1= 550 或 600 (x1* = 0) 其他典例 f3* (s3) = min { s3 , 537 } f2*(s2) = f1*(s1) = = 第 7章 動(dòng)態(tài)規(guī)劃 41 根據(jù)以上結(jié)果，可得 最優(yōu)采購(gòu)策略 為： 若 前三周 原料價(jià)格為 500元，則應(yīng)立即 采購(gòu) ，否則 等待 以后再采購(gòu)； 第四周 當(dāng)原材料價(jià)格為 500或 550元時(shí)，都應(yīng)立即 采購(gòu) ，否則 等待 到第五周再采購(gòu)； 若前四周均未采購(gòu)，則 第五周 無(wú)論原料價(jià)格如何， 都應(yīng)立即按價(jià) 采購(gòu) ； 這樣， 原料期望價(jià)格 最低為： f0* = 500 + ( + ) 518 = 513 (元 ) 其他典例 第 7章 動(dòng)態(tài)規(guī)劃 42 其他典例 試制品批量問(wèn)題 (離散 隨機(jī)型 典例 ) 例 7 某廠按合同要為用戶制造一臺(tái)特殊設(shè)備，據(jù)估計(jì)一臺(tái)該設(shè) 備的制造費(fèi)用為 100元，而其合格品的概率為 ，每制造一批的 準(zhǔn)備費(fèi)用為 300元。 第 7章 動(dòng)態(tài)規(guī)劃 28 離散確定型典例 k=2 s3 = s2 + x2 2 s2 2 1 0 5 4 3 2 1 0 x2* f2*(s2) 2+ x2+ + f3*(s3, x3) + f3*(s3) f2(s2, x2) x2 2 1 0 第 7章 動(dòng)態(tài)規(guī)劃 29 離散確定型典例 由上已知 s1 = 0， s2 = x1 3 因 s2 ≥ 0，故 x1 ≥ 3，但 x1 ≤ 5，則 x1 = 3, 4, 5。 表 75中 s1 = 6時(shí) f *1(s1) =18，值最大，故 s1* = 6。 遞推 (逆 推 )求解 3176。 五、策略 由各階段決策 xk構(gòu)成的決策序列 ,稱為 全過(guò)程策略 ,簡(jiǎn)稱 策略 ,記為 p1(s1),有 p1(s1) = { x1(s1),x2(s2),… ,xn(sn)} pk(sk) = { xk(sk),xk+1(sk+1),… ,xn(sn)} ∈ Pk 稱為 第 k子過(guò)程策略 ，簡(jiǎn)稱 子策略 。 第 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 多階段決策問(wèn)題 階段、決策、策略 . 2 動(dòng)態(tài)規(guī)劃的 基本特性 一、多階段決策問(wèn)題的 基本特性 引言 Sk Sk+1 Sn T S’n Q = S1 反證法 容易得證。 sk∈ Sk ∈ Xk 第 7章 動(dòng)態(tài)規(guī)劃 6 基本概念 四、狀態(tài)轉(zhuǎn)移方程 sk+1與 sk,xk之間必須能夠建立一種明確的數(shù)量對(duì)應(yīng)關(guān)系，記為 Tk(sk,xk), 即有 sk+1 = Tk(sk,xk) 這種明確的數(shù)量關(guān)系稱為 狀態(tài)轉(zhuǎn)移方程 。 建立模型 (1) 劃分階段，設(shè)定 k (2) 設(shè)定狀態(tài)變量 sk (3) 設(shè)定決策變量 xk (4) 建立 狀態(tài)轉(zhuǎn)移方程 (5) 確定指標(biāo)函數(shù) vk， fk*
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1