運(yùn)籌學(xué)第五章動態(tài)規(guī)劃(1)(文件)
【正文】 1( 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) 時(shí) , 即 從 城 開 始 ， 中 間 經(jīng) 過 兩 個(gè) 城 市 到 城 的 最 短 距 離 是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) 時(shí) , 即 從 城 開 始 ， 中 間 經(jīng) 過 三 個(gè) 城 市 到 城 的 最 短 距 離 是 ： 所以 ， 推銷員的最短旅行路線是 1－ 3－ 4－ 2－ 1， 最短路程為 23。 小 結(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)走怎樣的路線才能使得總的管道長度最短等等 。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 ( , 。 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? ， 按年份將整個(gè)過程分為 個(gè)階段； nks 表示在第 階段可投入 , 兩種生產(chǎn)的資源量； k A Bkx表示第 階段用于 生產(chǎn)的資源量， k Akksx?表示用于生產(chǎn) 的資源量 ， B? ?( ) 0k k k k kD s x x s? ≤ ≤(3) 決策變量： (2) 狀態(tài)變量： (1) 階段變量： 允許決策集為： (4) 狀態(tài)轉(zhuǎn)移方程： 1 ()k k k ks ax b s x? ? ? ?( ) ( )k k kg x h s x??(6) 動態(tài)規(guī)劃基本方程： ? ?11()11( ) m a x ( ) ( ) ( )( ) 0 , , 2 ,1k k kk k k k k k k kx D snnf s g x h s x f sf s k n?????? ? ? ? ??? ????(5) 階段指標(biāo)： ； 【 例 】 (機(jī)器負(fù)荷分配問題 )某種機(jī)器可以在兩種不同的負(fù)荷下進(jìn)行生產(chǎn) ， 設(shè)機(jī)器在高負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為 ， 其中 為投入生產(chǎn)的機(jī)器數(shù)量 ， 年完好率為 ；在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為 ， 其中 為投入生產(chǎn)的機(jī)器數(shù)量 ， 年完好率為 。 在資源分配問題中，還有一種要考慮資源回收利用的問題，這里決策變量為連續(xù)值，故又可以稱之為 資源連續(xù)分配問題 ，這類分配問題的 一般敘述 如下 : 第二年再將資源數(shù)量 中的 和 分別投入到 、 兩種生產(chǎn) ， 則第二年又可以得到收入為 ， 如此繼續(xù)進(jìn)行 年 ， 試問：應(yīng)該如何決定每年投入生產(chǎn) 的資源量 ， 才能使得總的收入最大 ？ 2s 2x 22sx? A B2 2 2( ) ( )g x h s x??n A12 nx x x、 、 、 設(shè)有數(shù)量為 的某種資源 ， 可投入
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1