運(yùn)籌學(xué)74動(dòng)態(tài)規(guī)劃應(yīng)用舉例-閱讀頁(yè)
2024-08-26 10:57本頁(yè)面
【正文】 =0。 最優(yōu)指標(biāo)函數(shù) ：第 k周實(shí)際價(jià)格為 時(shí) ， 從第 k周至第 5周采取最優(yōu)策略所花費(fèi)的最低期望價(jià)格 。 kskx kxkES? ?????????)()()(1,2,3,4,m i n)(55555 bDsssfakDsSssf kkkEkkkkD為狀態(tài)集合 {500， 600， 700}。 若第四周價(jià)格為 500或 600， 則立即采購(gòu) ， 否則等第五周再采購(gòu) 。 按照以上策略進(jìn)行采購(gòu) ， 期望價(jià)格為： )700()600()500()(11111??????????? fffsf三 、 設(shè)備更新問(wèn)題 從經(jīng)濟(jì)上分析，一臺(tái)設(shè)備應(yīng)該 使用多少年更新最合算，這就是設(shè)備更新問(wèn)題。如果更新可提高年凈收入，但是當(dāng)年要支出一筆數(shù)額較大的購(gòu)買(mǎi)費(fèi)，為了比較不同決策的優(yōu)劣，常常要在一個(gè)較長(zhǎng)的時(shí)間內(nèi)考慮更新決策問(wèn)題。 rk(t)：在第 k年設(shè)備已使用過(guò) t年 (或稱(chēng)役齡為 t年 )， 再使用 1年時(shí)的效益 。 ck(t) ：在第 k年賣(mài)掉 — 臺(tái)役齡為 t年的設(shè)備 ， 買(mǎi)進(jìn)一臺(tái)新設(shè)備的更新凈費(fèi)用 。 動(dòng)態(tài)規(guī)劃模型 階段變量 k： k=1,2,… ,n， 表示計(jì)劃使用該設(shè)備的年限數(shù) 。 決策變量 xk: 是第 k年初更新 （ Replacement） ， 還是保留使用 （ keep）舊設(shè)備 ， 分別用 R與 K表示 。 試確定今后 5年內(nèi)的更新策略 ， 使總收益最大 。 ???????)1()0()0()1()1(m a x)1(555555 cururfRxKx55??當(dāng)當(dāng) a x ??????? ?? ?? K)1(x 5 ?當(dāng)= ?????????? a x)2(5f K)2(x 5 ?當(dāng)=2 ?????????? a x)3(5f R)3(x 5 ?當(dāng)= ?????????? a x)4(5f R)2(x 5 ?當(dāng) 役齡 項(xiàng)目 0 1 2 3 4 5 效益 5 4 3 維修費(fèi) 1 2 3 更新費(fèi) 3 當(dāng) k=4時(shí) ， 狀態(tài)變量 s4可取 1， 2， 3。 = = 役齡 項(xiàng)目 0 1 2 3 4 5 效益 5 4 3 維修費(fèi) 1 2 3 更新費(fèi) 3 ??????????)1()()0()0()1()()(m a x)(4333334333333 fscursfsusrsfRxKx33 ??當(dāng)當(dāng))1(3f?????? ??? ?? a x R)1(x 3 ?當(dāng))2(3f = ?????? ??? ?? a x = R)2(x 3 ?當(dāng)當(dāng) k=2時(shí) ， 狀態(tài)變量 s2只能取 1 役齡 項(xiàng)目 0 1 2 3 4 5 效益 5 4 3 維修費(fèi) 1 2 3 更新費(fèi) 3 = = ??????????)1()()0()0()1()()(m a x)(3222223222222 fscursfsusrsfRxKx22??當(dāng)當(dāng))1(2f??????????? a x R)1(x 2 ?當(dāng)當(dāng) k=1時(shí) ， 狀態(tài)變量 s1只能取 0 役齡 項(xiàng)目 0 1 2 3 4 5 效益 5 4 3 維修費(fèi) 1 2 3 更新費(fèi) 3 = 17 ??????????)1()()0()0()1()()(m a x)(2111112111111fscursfsusrsfRxKx11??當(dāng)當(dāng)???????? ??? ??? a x)0(1fKx ?)0(1 上述計(jì)算遞推回去 ， 當(dāng) 時(shí) ， 由狀態(tài)轉(zhuǎn)移方程 ， 則 則查 得： 狀態(tài) ， 查： Kx ?? )0(1?????????RxRxfsKxss1*222112 1)1(11 得，查知????????RxsKxss23223 111 推出)1(3f Rx ?*3推出 ， 查 14 ?s)1(4f Rx ?*415 ?s )1(5f Kx ?*5最優(yōu)策略為： ，即第一年初購(gòu)買(mǎi)的設(shè)備到第二、三、四年初各更新一次，用到第 5年末，其總效益為 17萬(wàn)元。 s5 1 2 3 4 u5 K R K R K R K R v5+f6 f5 2 u5* K K R R k＝ 4, s4可取 1,2,3。 s3 1 2 u3 K R K R v3+f4 + + + + f4 u4* R R k＝ 2, s2可取 1。 s1 0 u1 K R v1+f2 + + f1 17 u1* K 貨郎擔(dān)問(wèn)題一般提法為：一個(gè)貨郎從某城鎮(zhèn)出發(fā)，經(jīng)過(guò)若干個(gè)城鎮(zhèn)一次，且僅一次，最后仍回到原出發(fā)的城鎮(zhèn)，問(wèn)應(yīng)如何選擇行走路線(xiàn)可使總行程最短，這是運(yùn)籌學(xué)的一個(gè)著名問(wèn)題，實(shí)際中有很多問(wèn)題可以歸結(jié)為這類(lèi)問(wèn)題。若對(duì) n個(gè)城鎮(zhèn)進(jìn)行排列，有 (n一 1)!／ 2種方案，所以窮舉法是不現(xiàn)實(shí)的，這里介紹一種動(dòng)態(tài)規(guī)劃方法。但是狀態(tài)變量不好選擇，不容易滿(mǎn)足無(wú)后效性。 狀態(tài)變量 表示：從 點(diǎn)出發(fā)．經(jīng)過(guò) S集合中所有點(diǎn)一次最后到達(dá) 。 1v iv1v iv),( Si 1viv),( Sif k 1v 決策變量 表示：從 經(jīng) k個(gè)中間城鎮(zhèn)的 S集合到 城鎮(zhèn)的最短路線(xiàn)上鄰接 的前一個(gè)城鎮(zhèn)，則動(dòng)態(tài)規(guī)劃的順序遞推關(guān)系為 ： ),( SiPk 1viv iv? ?? ?????????????? ??)(),3,2,1,2,1(),()()\,(m i n),(101bninkdifadjSjfSifijikSjk??為空集例 6 已知 4個(gè)城市間距離如表 7— 16，求從 v1出發(fā)，經(jīng)其余城市一次且僅一次最后返回 v1的最短路徑與距離。 貨郎擔(dān)問(wèn)題當(dāng)城市數(shù)目增加時(shí)，用動(dòng)態(tài)規(guī)劃方法求解，無(wú)論是計(jì)算量還是存貯量都會(huì)大大增加，所以本方法只適合于 n
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1