管理運(yùn)籌學(xué)-動態(tài)規(guī)劃(編輯修改稿)
2025-02-14 19:16 本頁面
【文章內(nèi)容簡介】 * = 6) = { 1, 2, 3 } 或 { 2, 1, 3 } 即該廠應(yīng)訂購 6套該設(shè)備，可分給 1， 2， 3分廠 1， 2， 3 套 或 2， 1， 3 套。這樣預(yù)計(jì)每年創(chuàng)利最大 ， 為 18萬元 。 第 7章 動態(tài)規(guī)劃 21 離散確定型典例 . 3 生產(chǎn)調(diào)度問題 例 4 某廠根據(jù)市場預(yù)測，確認(rèn)今后四個(gè)月該廠的一種主要 產(chǎn)品每月需求量如下表所示。已知每月生產(chǎn)固定費(fèi)用 b=2 千元 ，但若當(dāng)月不生產(chǎn)則 b=0；產(chǎn)品成本為 c=1千元 /萬件 ； 存貯費(fèi)用為 h= /萬件 /月 ；每月最大生產(chǎn)能力為 a=5 萬件 ,最大存貯能力為 ω=4萬件 。若第 1月初無庫存產(chǎn)品， 第 4月末也不留庫存，則該廠應(yīng)如何安排生產(chǎn)，才能使今后 四個(gè)月的總費(fèi)用最少？ 月 1 2 3 4 需求量（萬件） 3 2 3 2 第 7章 動態(tài)規(guī)劃 22 離散確定型典例 解 ： 1 . 建立模型 令 k = 1， 2， 3， 4 表示今后 4個(gè)月的序號。 設(shè) sk = 第 k月初 (或第 k1月末 ) 的庫存量； xk = 第 k月的產(chǎn)量； 令以 dk表示第 k月的需求量，則狀態(tài)轉(zhuǎn)移方程為 sk+1 = sk+ xk dk 設(shè)： vk( sk,xk ) = 第 k月生產(chǎn)費(fèi)用； fk(sk,xk ) = 第 k月初到第 4月末的生產(chǎn)費(fèi)用； fk*(sk) = 第 k月初到第 4月末的最低生產(chǎn)費(fèi)用； 第 7章 動態(tài)規(guī)劃 23 離散確定型典例 由題意知 : vk (sk,xk) = = fk(sk, xk ) = fk+1* ( sk+1 ) + xk = { xk| 0≤xk≤ 5 } 上式中的允許決策集合為 fk*(sk) = min { fk(sk,xk )}， k = 4, 3, 2, 1 f5*(s5 ) = 0 函數(shù)基本方程為 2+xk+， 當(dāng) xk 0 ， 當(dāng) xk = 0 當(dāng) xk = 0 2+xk+ 當(dāng) xk 0 hsk 當(dāng) xk = 0 b+cxk+hsk， 當(dāng) xk 0 第 7章 動態(tài)規(guī)劃 24 離散確定型典例 2 . 逆序遞推求解 k=4 (1) k = 4 已知 d4= 2， s5= 0，由 s5 = s4 +x4 2 得 s4= 2 x4 ≤ 2 故 s4= 0， 1， 2，則 x4 的值也隨之確定了。 2 1 4 0 2 1 0 s4 x4* f4*(s4) 2+ x4+ f4(s4, x4) x4 4 2 1 0 第 7章 動態(tài)規(guī)劃 25 離散確定型典例 (2) k = 3 d3 = 3，由上知 0 ≤ s4 ≤ 2，由 s4 = s3 + x3 3 得 0 ≤ s3 + x3 3 ≤ 2， 即 3 ≤ s3 + x3 ≤5 又 s3 ≤ ω = 4， 故 s3 = 0, 1， 2， 3， 4 則有 X3 = { x3 | 3 ≤ s3 + x3 ≤ 5， s3 = 0,1 ,2 ,3 ,4 } 第 7章 動態(tài)規(guī)劃 26 離散確定型典例 f3(s3, x3) + f4*(s4) 2 + x3 + + f4*(s4) f3*(s3) x3* x3 s3 0 1 2 3 4 5 0 1 2 3 4 k=3 4 5 4 3 0 0 沿 方向遞減 ch = = s4= s3+x3 3 第 7章 動態(tài)規(guī)劃 27 離散確定型典例 (3) k = 2 d2 = 2，由 0 ≤ s3 ≤4，又 s3 = s2 + x2 2, 可得 0 ≤s2 +x2 2 ≤4 或 2≤ s2+x2 ≤6 又由假設(shè)條件可知 s1 = 0，則 s2 = s1 + x1 d1 = x1 3 因 x1 ≤5，故 s2 = x1 3 ≤ 5 3 = 2 即 s2 = 0， 1， 2； 則 x2 的取值也相應(yīng)確定了。 第 7章 動態(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章 動態(tài)規(guī)劃 29 離散確定型典例 由上已知 s1 = 0， s2 = x1 3 因 s2 ≥ 0，故 x1 ≥ 3，但 x1 ≤ 5，則 x1 = 3, 4, 5?？傻茫? 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) 。 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ī)床 全年在高
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1