吉林大學(xué)本科運(yùn)籌學(xué)-文庫吧資料
2025-05-18 15:13本頁面
【正文】 要具有可分離性，并滿足遞推關(guān)系。在逆序 (或順序 )解法中，我們得到的不僅僅是由 A點 (或 G點 )出發(fā)到 G點 (或 A點 )的最短路線及相應(yīng)的最短距離，而且得到了從所有各中間點出發(fā)到 G點 (或 A點 )的最短路線及相應(yīng)的距離。而且隨著段數(shù)的增加，計算量將大大地減少。每次比較運(yùn)算相應(yīng)有兩次加法運(yùn)算，再去掉中間重復(fù)兩次 (即 B1→C 1， B2→C 4各多算了一次 )，實際只有 28次加法運(yùn)算。計算例 1若用窮舉法，就要對 48條路線進(jìn)行比較，運(yùn)算在計算機(jī)上進(jìn)行時，比較運(yùn)算要進(jìn)行 47次；求各條路線的距離，即使用逐段累加方法，也要進(jìn)行 6+12+24+48+48＝ 138次加法運(yùn)算。 如例 1最短路線問題，初始狀態(tài) A已知，則按下面箭頭所指的方向逐次變換有 從而可得最優(yōu)策略為｛ u1(A),u2(B1),…, u0’(F2)｝，相應(yīng)的最短路線為 已知）()()()(21239。因此，每段決策的選取是 從全局來考慮的 ，與該段的最優(yōu)選擇答案一般是不同的。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。 動態(tài)規(guī)劃的基本思想和基本方程 動態(tài)規(guī)劃方法基本思想歸納： 1. 動態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件 (簡言之為基本方程 )。 動態(tài)規(guī)劃的基本思想和基本方程 ? ?ku1 1 2 1 2 3 2 1 4 1 2 5 2 2 6 2( ) , ( ) , ( ) , ( ) , ( ) , ( )u A B u B C u C D u D E u E F u F G? ? ? ? ? ?1 2 1 2 2A B C D E F G? ? ? ? ? ?為了找出最短路線，再按計算的順序反推之 ，可求出最優(yōu)決策函數(shù)序列 ，即由 組成一個最優(yōu)策略。若從 E1出發(fā)，則有兩個選擇①至 F1， ②至 F2，則 其相應(yīng)的決策為 11E F G??這說明，由 E1至終點 G的 最短距離為 7，其最短路線是 動態(tài)規(guī)劃的基本思想和基本方程 5 2 1 6 1525 2 2 6 2( , ) ( ) 54( ) m in m in 5( , ) ( ) 2 3d E F f FfEd E F f F? ??? ??? ? ?? ? ? ??? ????22()su E F?5 3 6 1535 3 2 6 2( , 1 ) ( ) 64( ) m in m in 9( , ) ( ) 6 3d E F f FfEd E F f F? ??? ??? ? ?? ? ? ??? ????5 3 2()u E F?同理，從 E2和 E3出發(fā)，則有 其相應(yīng)的決策為 且 動態(tài)規(guī)劃的基本思想和基本方程 4 1 4 1 24 2 4 2 24 3 4 3 2( ) 7 ( )( ) 6 ( )( ) 8 ( )f D u D Ef D u D Ef D u D E????3 1 3 1 13 2 3 2 13 3 3 3 23 4 3 4 3( ) 1 3 ( )( ) 1 0 ( )( ) 9 ( )( ) 1 2 ( )f C u C Df C u C Df C u C Df C u C D????2 1 2 1 22 2 2 2 3( ) 1 3 ( )( ) 1 6 ( )f B u B Cf B u B C??1 1 2 111 2 2 2( , ) ( ) 5 1 3( ) m in m in 1 8( , ) ( ) 3 1 6d A B f BfAd A B f B? ??? ??? ? ?? ? ? ??? ????11()u A B?當(dāng) k=4時，有 當(dāng) k=3時，有 當(dāng) k=2時，有 當(dāng) k=1時，出發(fā)點有一個 A點，則 且 。 動態(tài)規(guī)劃的基本概念 動態(tài)規(guī)劃的基本思想和基本方程 61( ) 4fF? 62( ) 3fF?1 2 3,E E E5 1 1 6 1515 1 2 6 2( , ) ( ) 34( ) m in m in 7( , ) ( ) 5 3d E F f FfEd E F f F? ??? ??? ? ?? ? ? ??? ????11()su E F?當(dāng) k=6時，由 F1到終點 G只有一條路線，故 。所以，動態(tài)規(guī)劃的方法是從終點逐段向始點方向?qū)ふ易疃搪肪€的一種方法。這與假設(shè)矛盾，是不可能的。例如，在最短路線問題中，若找到了A→B 1→C 2→D 1→E 2→F 2→G 是由 A到 G的最短路線，則 D1→E 2→F 2→G應(yīng)該是由 D1出發(fā)到 G點的所有可能選擇的不同路線中的最短路線。 動態(tài)規(guī)劃的基本思想和基本方程 結(jié)合最短路線問題介紹動態(tài)規(guī)劃方法的基本思想。它表示從第 k階段的狀態(tài) sk開始到第 n階段 的終止?fàn)顟B(tài)的過程，采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。即 其中 表示第 j階段的階段指標(biāo)，這時上式可寫成 (2) 過程和它的任一子過程的指標(biāo)是它所包含的 各階段的指標(biāo)的乘積 。即 Vk,n可以表示為 sk、 uk、 Vk+1,n的函數(shù)，記為 在實際問題中很多指標(biāo)函數(shù)都滿足這個性質(zhì)。它是定義在全過程和所有后部子過程上確定的數(shù)量函數(shù)。Tk稱為狀態(tài)轉(zhuǎn)移函數(shù)。即 sk+1的值隨 sk和 uk的值變化而變化。 動態(tài)規(guī)劃的基本概念 1 ( , )k k k ks T s u? ?1 ()k k ks u s? ?5．狀態(tài)轉(zhuǎn)移方程 狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。由每段的決策按順序排列組成的決策函數(shù)序列 稱為 k子過程策略，簡稱子策略，記為 ，即 當(dāng) k=1時， 此決策函數(shù)序列稱為全過程的一個策略，簡稱策略，記為 ，即 在實際問題中，可供選擇的策略有一定的范圍，此范圍稱為 允許策略集合 ，用 P表示。 動態(tài)規(guī)劃的基本概念 ? ?( ) , , ( )k k n nu s u s , ()k n kps? ?, 1 1( ) ( ) , ( ) , , ( )k n k k k k k n np s u s u s u s???1, 1()nps? ?1
高考資料相關(guān)推薦
鄂ICP備17016276號-1