運(yùn)籌學(xué)74動(dòng)態(tài)規(guī)劃應(yīng)用舉例-資料下載頁(yè)
2025-08-07 10:57本頁(yè)面
【正文】 )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)買的設(shè)備到第二、三、四年初各更新一次，用到第 5年末，其總效益為 17萬(wàn)元。 ? ?KRRRK , k＝ 5， s5可取 1,2,3,4。 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。 s4 1 2 3 u4 K R K R K R v4+f5 + + +2 + + + f4 u4* R R R k＝ 3， s3可取 1,2。 s3 1 2 u3 K R K R v3+f4 + + + + f4 u4* R R k＝ 2, s2可取 1。 s2 1 u2 K R v3+f2 + + f2 u2* R k＝ 1, s2可取 0。 s1 0 u1 K R v1+f2 + + f1 17 u1* K 貨郎擔(dān)問題一般提法為：一個(gè)貨郎從某城鎮(zhèn)出發(fā)，經(jīng)過若干個(gè)城鎮(zhèn)一次，且僅一次，最后仍回到原出發(fā)的城鎮(zhèn)，問應(yīng)如何選擇行走路線可使總行程最短，這是運(yùn)籌學(xué)的一個(gè)著名問題，實(shí)際中有很多問題可以歸結(jié)為這類問題。 四、貨郎擔(dān)問題 設(shè) 是已知的 n個(gè)城鎮(zhèn)，城鎮(zhèn) 到城鎮(zhèn) 的距離為 ，現(xiàn)求從 出發(fā)，經(jīng)各城鎮(zhèn)一次且僅一次返回 的最短路程。若對(duì) n個(gè)城鎮(zhèn)進(jìn)行排列，有 (n一 1)!／ 2種方案，所以窮舉法是不現(xiàn)實(shí)的，這里介紹一種動(dòng)態(tài)規(guī)劃方法。 貨郎擔(dān)問題也是求最短路徑問題，但與例 4的最短路問題有很大不同，建動(dòng)態(tài)規(guī)劃模型時(shí)，雖然也可按城鎮(zhèn)數(shù)目 n將問題分為 n個(gè)階段。但是狀態(tài)變量不好選擇，不容易滿足無后效性。為保持狀態(tài)間相互獨(dú)立，可按以下方法建模： nvvv , 21 ? jvijd1viv1v 設(shè) S表示從 到 中間所有可能經(jīng)過的城市集合， S實(shí)際上是包含除 與 兩個(gè)點(diǎn)之外其余點(diǎn)的集合，但 S中的點(diǎn)的個(gè)數(shù)要隨階段數(shù)改變。 狀態(tài)變量 表示：從 點(diǎn)出發(fā)．經(jīng)過 S集合中所有點(diǎn)一次最后到達(dá) 。 最優(yōu)指標(biāo)函數(shù) 為從 出發(fā)經(jīng)由 k個(gè)城鎮(zhèn)的 S集合到 Vi的最短距離。 1v iv1v iv),( Si 1viv),( Sif k 1v 決策變量 表示：從 經(jīng) k個(gè)中間城鎮(zhèn)的 S集合到 城鎮(zhè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的最短路徑與距離。 表 7 — 16 v j 距離 vi 1 2 3 4 1 0 6 7 9 2 8 0 9 7 3 5 8 0 8 4 6 5 5 0 解 由邊界條件（ ）知： 當(dāng) k=1時(shí)，從城市 v1出發(fā)，經(jīng)過 1個(gè)城鎮(zhèn)到達(dá) vi的最短距離為： 9),4(7),3(6),2( 140130120 ????????? dfdfdf? ?? ?? ?? ?? ?? ? 1587),3()3,4(1376),2()2,4(1459),4()4,3(1596),2()2,3(1459),4()4,2(1587),3()3,2(340124014301230142013201????????????????????????????????????dffdffdffdffdffdff 當(dāng) k=2時(shí)，從城市 v1出發(fā)，經(jīng)過 2個(gè)城鎮(zhèn)到達(dá)vi的最短距離為： ? ? ? ? ? ?20]515,814m i n[])3,4(,)4,3(m i n[)4,3,2( 4213212??????? dfdff? ?? ? 18]513,914m i n [)4,2,3(4)4,3,2(22?????fP? ?? ? 22]815,715m i n [)3,2,4(4)4,3,2(22?????fP? ? 2)3,2,4(2 ?P所以 所以 所以 當(dāng) k=3時(shí)，從城市 v1出發(fā)，經(jīng)過 3個(gè)城鎮(zhèn)到達(dá)vi的最短距離為： ? ? ? ? ? ? ,)4,2,3(,)4,3,2(m i n [)4,3,2,1( 3122123 dfdff ???? ? 23]622,518,820m i n [])3,2,4( 412 ?????? df? ? 3)4,3,2,1(3 ?P所以 逆推回去，貨郎的最短路線是 l→2→4→3→1最短距離為 23。 貨郎擔(dān)問題當(dāng)城市數(shù)目增加時(shí)，用動(dòng)態(tài)規(guī)劃方法求解，無論是計(jì)算量還是存貯量都會(huì)大大增加，所以本方法只適合于 n較小情況。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1