運籌學第五章動態(tài)規(guī)劃(1)-文庫吧
2025-04-20 15:19 本頁面
【正文】 CC D f Df C v C d C f sC D f D ????? ? ??????? ?3 2 3 22 1 4 13 2 3 2 3 2 4 4( ) ( )2 2 4 2()( ) m in m in ( , ( ) ) ( )() d C D CC D f Df C v C d C f sC D f D ????? ? ??????? ?3 3 3 33 1 4 13 3 3 3 3 3 4 4( ) ( )3 2 4 2()( ) m in m in ( , ( ) ) ( )() d C D CC D f Df C v C d C f sC D f D ????? ? ??????? ? ? ?4 1 4 14 1 1 4 1 4 1 4 1 1( ) ( )m in m in( ) ( , ( ) ) ( , )d D D Df D D E v D d D v D D E?? ? ?? ? ? ?4 2 4 24 2 2 4 2 4 2 4 2 2( ) ( )( ) m in m in ( , ( ) ) ( , )d D D Df D D E v D d D v D D E?? ? ?4 3 1 3 1( , ( ) )s T C d C?3 1 1 1 1 2( ) { , }D C C D C D?4 3 2 3 2( , ( ) )s T C d C?3 2 2 1 2 2( ) { , }D C C D C D?5 4 2 4 2( , ( ) )s T D d D?4 2 2( ) { }D D D E?4 3 3 3 3( , ( ) )s T C d C?3 3 3 1 3 2( ) { , }D C C D C D?5 4 1 4 1( , ( ) )s T D d D?4 1 1( ) { }D D D E? 在引入一個虛擬的第五階段后 ， 可將第五階段到第五階段的指標記為 ， 上述過程則可以用一個帶有初始條件 的遞推公式來完全描述： 55( ) 0fs ?55( ) 0fs ? 顯然從 開始 ， 有 55( ) 0fs ?當 時 4k? 41( ) 3fD ? 42( ) 4fD? 4 2 2()d D D E?當 時 3k?31( ) 6fC ? 32( ) 7fC? 33( ) 6fC ?3 3 3 1()d C C D?4 1 1()d D D E? ； 3 1 1 1()d C C D?； 3 2 2 2()d C C D?； ? ?11( ) ( )55( ) m i n ( , ( ) ) ( )( ) 0 , 4 , 3 , 2 ,1k k k kk k k k k k k kd s D sf s v s d s f sf s k???? ????????(52) 當 時， 2k? 2 2 2 2()d B B C?當 時， 1k?可以求得 的最短距離 12， 然后根據(jù)計算過程中的記錄 ，反向追蹤可求得最短路線 ， 最短路線為 AE?或 23( ) 9fB? ， 21( ) 11fB? ， 22( ) 9fB ? ， 2 1 1 2()d B B C? ； 2 2 2 1()d B B C? ； 2 3 3 2()d B B C? 。 1 ( ) 12fA? ， 13()d A AB? 。 3 2 2A B C D E? ? ? ?。 注 ：而事實上 ， 從各點到 的最短路線和最短路線距離都求出來了 。 E 動態(tài)規(guī)劃最優(yōu)性原理 ： “ 作為整個過程的最優(yōu)策略具有這樣的性質(zhì) ， 即無論過去的狀態(tài)和決策如何 ， 對前面的決策所形成的狀態(tài)而言 ， 余下的諸決策必然構(gòu)成最優(yōu)策略 。 ” 將動態(tài)規(guī)劃最優(yōu)性原理應(yīng)用于一般的多階段問題求解即可得到類似 (52)的遞推公式 ? ?11( ) ( )11( ) m in ( , ( ) ) ( )( ) 0 , , , 2 ,1k k k kk k k k k k k kd s D snnf s v s d s f sf s k n?????? ???? ????(53) 動態(tài)規(guī)劃的逆序解法 下面以 例 ， 加深我們對這種方法的理解 。 解 由 ， 例 ： ks表示第 個月月初的庫存量； k 表示第 個月已有庫存 的情況下，要定購的商品量， 表示第 個月已有庫存 的情況下，要銷售的商品量 (為方便，后面將分別依次用 ， 來代替 和 )； 1()kkds kkksks2()kkdskx ky1()kkds2()kkds(2) 狀態(tài)變量： (1) 按月份分段： 4 , 3, 2 ,1k ? ； (3) 決策變量： 狀態(tài)轉(zhuǎn)移方程： (4) 允許決策集： (5) 階段指標： 其中 表示第四階段末
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1