運(yùn)籌學(xué)第五章動態(tài)規(guī)劃(1)(參考版)
2025-05-14 15:19本頁面
【正文】 小 結(jié) 動態(tài)規(guī)劃所解決的問題； 動態(tài)規(guī)劃是一種技術(shù)，是一種思想 ； 動態(tài)規(guī)劃模型及求解； 動態(tài)規(guī)劃的優(yōu)缺點(diǎn)； 用動態(tài)規(guī)劃可以求解靜態(tài)規(guī)劃； 。 如工廠里在鋼板上要挖一些小圓孔 ， 自動焊機(jī)的割嘴應(yīng)走怎樣的路線使得總路線最短 、 物資運(yùn)送路線中 ， 汽車應(yīng)走怎樣的路線使得總路程最短 、 城市里在一些地方鋪設(shè)管道 ， 管道應(yīng)走怎樣的路線才能使得總的管道長度最短等等 。 邊界條件為 0 12 0 13 0 14( 2 , ) 8 , ( 3 , ) 5 , ( 4 , ) 6f d f d f d? ? ? ? ? ? ? ? ?1 0 321 0 421( 2 , { 3 }) ( 3 , ) 5 9 14( 2 , { 4 }) ( 4 , ) 6 7 131k if f df f d?? ? ? ? ? ?? ? ? ? ? ?， ：當(dāng) 時 即 從 城 開 始 ， 中 間 經(jīng) 過 一 個 城 到 城 的 最 短 距 離 是11( 3 , { 2 } ) 8 8 1 6 , ( 3 , { 4 } ) 6 8 1 4( 4 , { 2 } ) 8 5 1 3 , ( 4 , { 3 } ) 5 5 1 0ff ? ? ? ? ? ?? ? ? ? ? ?2 1 3 2 1 4 222( 2 , { 3 4 }) m in [ ( 3 , { 4 }) , ( 4 , { 3 }) ]m in [ 1 4 9 ,10 7 ]1 7 ( 2 , { 3 4 }) 41k if f d f dP?? ? ?? ? ???：，當(dāng) 時 , 即 從 城 開 始 ， 中 間 經(jīng) 過 兩 個 城 市 到 城 的 最 短 距 離 是2222( 3 , { 2 4 }) m in [ 1 3 8 ,13 8 ]2 1 ( 3 , { 2 4 }) 2 4( 4 , { 2 3 }) m in [ 1 4 5 ,16 5 ]1 9 ( 4 , { 2 3 }) 2fPfP? ? ???? ? ???， 或，3 2 2 1 2 3 1 2 4 133( 1 , { 2 3 4 }) m in [ ( 2 { 3 4 }) ( 3 { 2 4 }) ( 4 , { 2 3 }) ]m in [ 1 7 6 , 2 1 7 ,19 9 ]2 3 ( 1 , { 2 3 4 }) 21k if f d f d f dP?? ? ? ?? ? ? ???， ， ， ， ， ， ， ， ， ，當(dāng) 時 , 即 從 城 開 始 ， 中 間 經(jīng) 過 三 個 城 市 到 城 的 最 短 距 離 是 ： 所以 ， 推銷員的最短旅行路線是 1－ 3－ 4－ 2－ 1， 最短路程為 23。kk k k k jijsi k if i s f j s j df i d k n i n s N???? ????? ? ? ? ???(7) 動態(tài)規(guī)劃基本方程： 的最短路線的距離； (6) 最優(yōu)函數(shù)： (5) 階段指標(biāo)： (4) 狀態(tài)轉(zhuǎn)移方程： 允許決策集為 : (3) 決策變量： j市 ； 1 ( , 。 一個推銷商從城市 1 出發(fā)到其他每個城市去一次且只去一次 ， 最后回到城市 1， 問怎樣選擇行走路線 ， 才能使得行走總路程最短 ？ ,ijn 1, 2, ,nijd其 動態(tài)規(guī)劃模型 如下： 1, ,1kn??ks將從城市 1到 城市的中間城市集合用 i表示第 階段到達(dá) 城市之 k i 旅行推銷商問題 { 2 , 3 , , 1 , 1 , , }iN i i n? ? ?表示， i 城 ， 規(guī)定推銷員是從城市 1開始的 ， 設(shè)推銷員走到 (2)狀態(tài)變量： 按經(jīng)過城市的個數(shù)來分段 ， (1) 階段變量： 1n? 個階段 ， 將整個過程分為 問題 一般描述 如下： ； 前中途所經(jīng)過的城市的集 ， 則有 ， 其中 ， 因此 ， kisN? ksk?可選取 作為描述過程的狀態(tài)變量； ( , )kisku表示推銷商在狀態(tài) 下前往的下一個城 ( , )kisijd表示從城市 到城市 的距離； i j( , )kkf i s 表示從城市 1經(jīng)過 個城市 到達(dá)城市 kksi? ?101( , ) m i n ( , \ { } )( , ) , 1 , 2 , , 1 。 1s A B1x A 11sx? B1 1 1( ) ( )g x h s x?? ()gx ()hx( 0 ) ( 0 ) 0gh?? A B01a?? 01b??2 1 1 1()s ax b s x? ? ?此問題的靜態(tài)規(guī)劃模型為： ? ?11m a x ( ) ( )( ) ,0 , 1 , 2 , , .ni i iik k k kkkz g x h s xs a x b s xx s k n??? ? ?? ? ??? ???≤ ≤此問題的 動態(tài)規(guī)劃模型 為 : , ,1kn? ， 按年份將整個過程分為 個階段； nks 表示在第 階段可投入 , 兩種生產(chǎn)的資源量
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1