管理運籌學(xué)-動態(tài)規(guī)劃(存儲版)
【正文】 型 典例 ) 例 6 某廠供應(yīng)科必須在今后 5周內(nèi)購買一原料， 以保證第六周生產(chǎn)之用。 設(shè) 1 ，當(dāng)?shù)?k段 之前 未得到合格品 0 ，否則 sk = xk = 第 k段的批量 (臺 ) 第 7章 動態(tài)規(guī)劃 43 其他典例 狀態(tài)轉(zhuǎn)移方程 為 p (sk+1= 1) = ()xk p (sk+1= 0) = 1 ()xk 第 k段的費用為 vk (xk) = b+100 xk 其中 b = 0， 當(dāng) xk = 0 300， 當(dāng) xk 0 第 k段及其后的最小期望費用值為 f *k(sk) = min { fk (sk， xk)} 其中 f *k(0) = 0， k = 1， 2， 3， 4 fk (1， xk) = vk (xk)+ ? p (sk+1) f *k+1 (sk+1) = b + 100xk + ()xkf *k+1(1)+[1 ()xk] f*k+1(0) = b + 100xk + ()xkf *k+1(1) 第 7章 動態(tài)規(guī)劃 44 其他典例 因此， 函數(shù)基本方程 為 fk*(1) = min { b+100xk+ ()xk fk+1*(1) } k = 3， 2， 1 邊界條件 為 f4*(1) = 2022 表示總共三批全未得到合格品而賠償用戶 2022 元。若三批未得到一臺合格品，則要賠 償用戶 2022元。 0 5 4 3 s1 x1* f1*(s1) 2+x1+ + f2*(s2, x2) f1(s1, x1) x1 5 第 7章 動態(tài)規(guī)劃 30 其他典例 機(jī)器負(fù)荷分配問題 (連續(xù) 確定型 典例 ) 例 5 設(shè)有 100臺同一規(guī)格的完好自動機(jī)床，每臺機(jī)床 全年在高負(fù)荷下工作可創(chuàng)利 9萬元，折損率為 ；在低負(fù) 荷下工作可創(chuàng)利 6萬元 ， 折損率為 。這樣預(yù)計每年創(chuàng)利最大 ， 為 18萬元 。 據(jù)預(yù)測， 今后五年不同價格下每年盈利如表所示 , 但是各相鄰年度價格增減不超過 1 元。 ∈ P1 (2) 過程指標(biāo)函數(shù) 用 fk(sk,xk)表示 第 k子過程的指標(biāo)函數(shù) 。 用 xk表示第 k段的決策，稱為第 k段 決策變量 。 二、狀態(tài) 狀態(tài)表示某段的初始條件。 (4) 最優(yōu)值 ： 最優(yōu)策略對應(yīng)的最優(yōu)指標(biāo) f *1 基本概念 第 7章 動態(tài)規(guī)劃 9 基本概念 動態(tài)規(guī)劃的 基本方程 一 、 最優(yōu)化原理 作為一個 全過程最優(yōu)策略 具有這樣的 性質(zhì) ： 無論過去的狀態(tài)和決策如何，對前面所形成的狀態(tài)而言， 余下的諸決策必構(gòu)成最優(yōu)策略 。該廠應(yīng)訂購幾套設(shè)備并如何分配，才能使每年預(yù)計 創(chuàng)利總額最大？ 盈利：萬元 套數(shù) 分廠 0 1 2 3 4 5 6 1 0 3 5 6 7 6 5 2 0 4 6 7 8 9 10 3 0 2 5 9 8 8 7 第 7章 動態(tài)規(guī)劃 15 離散確定型典例 解 1. 建立 DP模型 以 k = 1， 2， 3 表示給三個分廠分配的順序。若第 1月初無庫存產(chǎn)品， 第 4月末也不留庫存，則該廠應(yīng)如何安排生產(chǎn)，才能使今后 四個月的總費用最少？ 月 1 2 3 4 需求量（萬件） 3 2 3 2 第 7章 動態(tài)規(guī)劃 22 離散確定型典例 解 ： 1 . 建立模型 令 k = 1， 2， 3， 4 表示今后 4個月的序號。 根據(jù)過去的統(tǒng)計資料， 預(yù)計該原料今后每周的 價格如右表所示。 第 7章 動態(tài)規(guī)劃 45 其他典例 k = 3 x3 0 1 300+100x3 0 2022()x3 400 2 3 4 5 6 500 600 2022 1200 720 432 700 259 800 900 156 93 f3(1, x3) = b+100x3 + f4*(1)()x3 x3 s3 0 1 0 0 1 2022 1600 1220 2 3 1032 4 959 5 956 6 993 f 3 (s3) * 0 0 956 5 x3 * 第 7章 動態(tài)規(guī)劃 46 其他典例 k = 2 x2 0 1 2 3 4 5 6 300+100x2 0 400 500 600 700 800 900 956()x2 956 574 344 206 124 x2 s2 0 1 0 0 1 956 974 2 844 3 806 4 824 f 2 (s2) * x2 * 0 0 806 3 f2(1, x2) = b+100x2 + f3*(1)()x2 第 7章 動態(tài)規(guī)劃 47 其他典例 k = 1 綜上， 最優(yōu)策略 是：第一批試制 3臺；若 無合格品，則第 2批再試制 3臺； 若仍無合格 品，則第 3批試制 5臺，這樣能使 總費用期望值 最小，為 774元 。若一批試制品全不合格，可再試制一批，但 在規(guī)定期限內(nèi)最多試制三批。可得： k=1 s2= x1 3 3. 順推結(jié)論 按 例 3的方法，可以推知最優(yōu)解： p1* = { 5， 0， 5， 0 } (萬件 ) 最優(yōu)值： f1* = (千元 ) 即第 1, 3月分別生產(chǎn) 5萬件，第 2, 4月 不生產(chǎn) 。順次查 看 k = 1， 2， 3 時的表格，可知最優(yōu)策略為： p1*(s1* = 6) = { 1, 2, 3 } 或 { 2, 1, 3 } 即該廠應(yīng)訂購 6套該設(shè)備，可分給 1， 2， 3分廠 1， 2， 3 套 或 2， 1， 3 套。 得出 (順 推 )結(jié)論 第 7章 動態(tài)規(guī)劃 11 基本概念 . 4 動態(tài)規(guī)劃的 基本類型 一、 按階段變量 k劃分 (1) 定期型 : k = 1, 2, … , n (2) 不定期型
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1