吉林大學本科運籌學(編輯修改稿)
2025-06-15 15:13 本頁面
【文章內(nèi)容簡介】 路線是 動態(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?當 k=4時，有 當 k=3時，有 當 k=2時，有 當 k=1時，出發(fā)點有一個 A點，則 且 。于是得到從起點 A到終點 G的最短距離為 18。 動態(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)策略。因而， 找出相應(yīng)的最短路線 為 動態(tài)規(guī)劃的基本思想和基本方程 ? ?1()7 7 6 6 6 6( ) m i n ( , ( ) ) ( ( ) ) 6 , 5 , 4 , 3 , 2 , 1( ) 0( ( ) ( , ) )k k kk k k k k k k k ku D sf s d s u s f u s kf s f s d s G??? ? ? ??????? 或 寫 成? ?1()( ) op t ( , ( ) ) ( ( ) ) ( 8 1 ), 1 , , 1k k kk k k k k k k k ku D sf s v s u s f u sk n n??? ? ???11( ) 0nnfs?? ?從上面的計算過程中可以看出，在求解的各個階段，我們利用了 k階段與 k+1階段之間的遞推關(guān)系： 一般情況， k階段與 k+1階段的遞推關(guān)系式可寫成 邊界條件為 遞推關(guān)系式 (81)稱為 動態(tài)規(guī)劃的基本方程 。 動態(tài)規(guī)劃的基本思想和基本方程 動態(tài)規(guī)劃方法基本思想歸納： 1. 動態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當?shù)倪吔鐥l件 (簡言之為基本方程 )。要做到這一點，必須先將問題的過程分成幾個相互聯(lián)系的階段，恰當?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個大問題化成 一族同類型的子問題 ，然后逐個求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。 2. 在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前一段和未來各段分開，又把當前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是 從全局來考慮的 ，與該段的最優(yōu)選擇答案一般是不同的。 動態(tài)規(guī)劃的基本思想和基本方程 GFEDCBA 22111 ??????3. 在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐次變換得到，從而確定了最優(yōu)路線。 如例 1最短路線問題，初始狀態(tài) A已知，則按下面箭頭所指的方向逐次變換有 從而可得最優(yōu)策略為｛ u1(A),u2(B1),…, u0’(F2)｝，相應(yīng)的最短路線為 已知）()()()(21239。0121GCBAFuBuAu??????? 動態(tài)規(guī)劃的基本思想和基本方程 求解最短路問題的標號法 ——逆序解法 動態(tài)規(guī)劃的基本思想和基本方程 求解最短路問題的標號法 ——順序解法 動態(tài)規(guī)劃的基本思想和基本方程 動態(tài)規(guī)劃的方法比窮舉法有以下優(yōu)點： (1) 減少了計算量。計算例 1若用窮舉法，就要對 48條路線進行比較，運算在計算機上進行時，比較運算要進行 47次；求各條路線的距離，即使用逐段累加方法，也要進行 6+12+24+48+48＝ 138次加法運算。用動態(tài)規(guī)劃方法來計算，比較運算 (從 k=5段開始向前算 )共進行 3+3+4+4+1＝ 15次。每次比較運算相應(yīng)有兩次加法運算，再去掉中間重復(fù)兩次 (即 B1→C 1， B2→C 4各多算了一次 )，實際只有 28次加法運算?？梢姡瑒討B(tài)規(guī)劃方法比窮舉法減少了計算量。而且隨著段數(shù)的增加，計算量將大大地減少。 (2) 豐富了計算結(jié)果。在逆序 (或順序 )解法中，我們得到的不僅僅是由 A點 (或 G點 )出發(fā)到 G點 (或 A點 )的最短路線及相應(yīng)的最短距離，而且得到了從所有各中間點出發(fā)到 G點 (或 A點 )的最短路線及相應(yīng)的距離。這就是說，求出的不是一個最優(yōu)策略，而是一族的最優(yōu)策略。 動態(tài)規(guī)劃的基本思想和基本方程 建立動態(tài)規(guī)劃模型的五個要點： (1) 將問題的過程劃分成恰當?shù)碾A段； (2) 正確選擇狀態(tài)變量 sk，使它既能描述過程的演變，又要滿足無后效性； (3) 確定決策變量 uk及每階段的允許決策集合 Dk(sk)； (4) 正確寫出狀態(tài)轉(zhuǎn)
高考資料相關(guān)推薦
鄂ICP備17016276號-1