【正文】 最短路線問題 給定一個線路網(wǎng)絡(luò)，兩點之間連線上的數(shù)字表示兩點間的距離 (或費用 )，試求一條由 A到 G的鋪管線路，使總距離為最短 (或總費用最小 )。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。顯然，當(dāng)某階段的始點給定后，會影響后面各階段的行進路線和整個路線的長短，而后面各階段路線的發(fā)展不受這點以前各階段決策的影響。它既是該階段某支路的起點，又是前一階段某支路的終點。有時為了方便起見，將該階段的狀態(tài)編上號碼 1， 2… 這時也可記S3＝｛ 1， 2， 3， 4｝。它可用一個數(shù)、一組數(shù)或一向量來描述。由每段的決策按順序排列組成的決策函數(shù)序列 稱為 k子過程策略，簡稱子策略，記為 ，即 當(dāng) k=1時， 此決策函數(shù)序列稱為全過程的一個策略，簡稱策略，記為 ，即 在實際問題中，可供選擇的策略有一定的范圍，此范圍稱為 允許策略集合 ，用 P表示。它是定義在全過程和所有后部子過程上確定的數(shù)量函數(shù)。 動態(tài)規(guī)劃的基本思想和基本方程 結(jié)合最短路線問題介紹動態(tài)規(guī)劃方法的基本思想。 動態(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只有一條路線，故 。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。每次比較運算相應(yīng)有兩次加法運算，再去掉中間重復(fù)兩次 (即 B1→C 1， B2→C 4各多算了一次 )，實際只有 28次加法運算。 動態(tài)規(guī)劃的基本思想和基本方程 ? ?11 1 1()( ) o p t ( , ) ( ) 1 , 2 , ,rk k kk k k k k k ku D sf s v s u f s k n?? ? ??? ? ?01( ) 0fs?1( , )rk k k ks T s u??1()nnfs?動態(tài)規(guī)劃順序解法的基本方程 邊界條件 為 式中 求解過程：根據(jù)邊界條件， 從 k=1開始，由前向后順推 ，逐步求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求出 ， 就得到整個問題的最優(yōu)解。 第 4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 ?動態(tài)規(guī)劃方法 ?逆序解法 ?順序解法 ?關(guān)鍵：正確寫出動態(tài)規(guī)劃的遞推關(guān)系式 ?逆 推形式 ， 當(dāng)初始狀態(tài)給定時 ， 用逆推比較方便 ?順推形式 ， 當(dāng)終止?fàn)顟B(tài)給定時 ， 用順推比較方便 第 4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 1 2 1, , , ns s s ?12, , , nx x x1 ( , ) , 1 , 2 , ,k k k ks T s x k n? ??1 , 1 1 1 2 2 2( , ) ( , ) ( , )n n n nV v s x v s x v s x? ? ? ?1,nV1,opt nV 1,max nV考查如圖所示的 n階段決策過程。 最優(yōu)解 由 所以 第 4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 ? ?1 1 1 11131 1 1 2 2 1 1 1001 1 104( ) m a x ( ) m a x ( )27m a x ( , )x s x sxsf s x f s x s xh s x? ? ? ?????? ? ??????*1114xs?41 1 11() 64f s s?1sc?像前面一樣利用微分法易知 故 由于已知 而按計算的順序反推算，可得各階段的最優(yōu)決策和最優(yōu)值。 設(shè) 則有 第 4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 121 2 1 2( ) m a x ( )xsf s x s??? *12xs?2 3 2 32 2 32 3 2 1 2 2 3 2 3004( ) m a x ( ) m a x ( ) 27x s x sf s x f s x s x x? ? ? ?? ? ? ?? ? ? ?? ? ? ?*2323xs?? ?3 4 3 4343 4 3 2 3 3 4 3 40041( ) m a x ( ) m a x ( )2 7 6 4x s x sf s x f s x s x S? ? ? ???? ? ? ?????*3314xs?4sc?* * *1 2 31 1 1,4 2 4x c x c x c? ? ?41m a x 64zc?用順推解法，從前向后依次有 及最優(yōu)解 及最優(yōu)解 及最優(yōu)解 由于已知 ，故易得到最優(yōu)解為 最大值為 及最優(yōu)解 第 4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 2 2 21 2 31 2 3m a x 4 2 123 2 9 0 , 1 , 2 , 3iF x x xx x xxi? ? ? ?? ? ??? ???0 1 2 3s s s s、 、 、3 9s ? 1 2 3x x x、 、()kkfs例 5 用動態(tài)規(guī)劃方法解下面問題 解： 按問題中變量的個數(shù)分為三個階段。 再按計算的順序反推算可求得最優(yōu)解為 最大值為 。令最優(yōu)值函數(shù) 表示第 k階段的結(jié)束狀態(tài)為 sk，從 1階段至 k階段的最大值。 已知終止?fàn)顟B(tài) sn+1用順推解法與已知初始狀態(tài)用逆推解法在本質(zhì)上沒有區(qū)別，它相當(dāng)于把實際的起點視為終點，實際的終點視為起點，而按逆推解法進行的。在第 k階段，決策 xk使?fàn)顟B(tài) sk(輸入）轉(zhuǎn)移 為 sk+1 (輸出 )，設(shè)狀態(tài)轉(zhuǎn)移函數(shù)為 假定過程的總效益 (指標(biāo)函數(shù) )與各階段效益 (階段指標(biāo)函數(shù) )的關(guān)系為 其中記號 ?*都表示為 +,或都表示為 ?！? 簡言之， 一個最優(yōu)策略的子策略總是最優(yōu)的 。而且隨著段數(shù)的增加，計算量將大大地減少。因此，每段決策的選取是 從全局來考慮的 ，與該段的最優(yōu)選擇答案一般是不同的。若從 E1出發(fā)，則有兩個選擇①至 F1， ②至 F2，則