【正文】 C1， C2， C3，C4｝。它可用一個數(shù)、一組數(shù)或一向量 (多維情形 )來描述。在例 1中， 狀態(tài)就是某階段的出發(fā)位置 。描述階段的變量稱為 階段變量 ，常用 k表示。遞推下去可看到： 各個階段的決策不同，路線就不同 。 由圖 82可知，從 A點到 G點可以分為 6個階段。 假定開始生產(chǎn)時完好的機器數(shù)量為 s1。 當各個階段決策確定后 ， 就組成了一個決策序列 ，因而也就決定了整個過程的一條活動路線 。 ? 組合起來可分為 ? 離散確定性 ? 離散隨機性 ? 連續(xù)確定性 ? 連續(xù)隨機性 本書主要研究離散 確定性 決策過程。 動態(tài)規(guī)劃 ? 動態(tài)規(guī)劃在企業(yè)管理中的主要應用領域 ? 最優(yōu)路徑問題 ? 資源分配問題 ? 生產(chǎn)調(diào)度問題 ? 庫存問題 ? 裝載問題 ? 排序問題 ? 設備更新問題 ? 生產(chǎn)過程最優(yōu)控制問題 ? 等等 動態(tài)規(guī)劃是求解某類問題的一種方法，是考查問題的一種途徑，而不是一種特殊算法 (如線性規(guī)劃是一種算法 )。 ? 動態(tài)規(guī)劃的形成 ? 產(chǎn)生于 20世紀 50年代。 1951年美國數(shù)學家貝爾曼 ()等人，根據(jù)一類多階段決策問題的特點，把多階段決策問題變換為一系列 互相聯(lián)系的單階段 問題，然后逐個加以解決。 因而，它不像線性規(guī)劃那樣有一個標準的數(shù)學表達式和明確定義的一組規(guī)則，而 必須對具體問題進行具體分析處理。 第 8章 動態(tài)規(guī)劃的基本方法 ?第 1節(jié) 多階段決策過程及實例 ?第 2節(jié) 動態(tài)規(guī)劃的基本概念和基本方程 ?第 3節(jié) 動態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理 ?第 4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關系 第 1節(jié) 多階段決策過程及實例 ? 例 1 最短路線問題 給定一個線路網(wǎng)絡，兩點之間連線上的數(shù)字表示兩點間的距離 (或費用 )，試求一條由 A到 G的鋪管線路，使總距離為最短 (或總費用最小 )。 這種把一個問題可看作是一個前后關聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為 多階段決策過程 ， 也稱序貫決策過程 。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。在第一階段， A為起點，終點有 B B2兩個，因而這時走的路線有兩個選擇，一是走到 B1；一是走到 B2，若選擇走到 B2的決策，則 B2就是第一階段決策的結(jié)果。顯然，當某階段的始點給定后，會影響后面各階段的行進路線和整個路線的長短，而后面各階段路線的發(fā)展不受這點以前各階段決策的影響。階段的劃分，一般是根據(jù)時間和空間的自然特征來劃分，但要便于把問題的過程能轉(zhuǎn)化為多階段決策的過程。它既是該階段某支路的起點，又是前一階段某支路的終點。 常用 Sk表示第 k階段的狀態(tài)變量 。有時為了方便起見，將該階段的狀態(tài)編上號碼 1， 2… 這時也可記S3＝｛ 1， 2， 3， 4｝。這個性質(zhì)稱為無后效性 (即馬爾科夫性 )。它可用一個數(shù)、一組數(shù)或一向量來描述。 常用 Dk(sk)表示第 k階段從狀態(tài) sk出發(fā)的允許決策集合，顯然有 uk（ sk） ∈ Dk(sk)。由每段的決策按順序排列組成的決策函數(shù)序列 稱為 k子過程策略，簡稱子策略，記為 ，即 當 k=1時， 此決策函數(shù)序列稱為全過程的一個策略，簡稱策略，記為 ，即 在實際問題中，可供選擇的策略有一定的范圍，此范圍稱為 允許策略集合 ，用 P表示。即 sk+1的值隨 sk和 uk的值變化而變化。它是定義在全過程和所有后部子過程上確定的數(shù)量函數(shù)。即 其中 表示第 j階段的階段指標，這時上式可寫成 (2) 過程和它的任一子過程的指標是它所包含的 各階段的指標的乘積 。 動態(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?當 k=6時，由 F1到終點 G只有一條路線，故 。 動態(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ōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。 如例 1最短路線問題，初始狀態(tài) A已知，則按下面箭頭所指的方向逐次變換有 從而可得最優(yōu)策略為｛ u1(A),u2(B1),…, u0’(F2)｝，相應的最短路線為 已知）()()()(21239。每次比較運算相應有兩次加法運算，再去掉中間重復兩次 (即 B1→C 1， B2→C 4各多算了一次 )，實際只有 28次加法運算。在逆序 (或順序 )解法中，我們得到的不僅僅是由 A點 (或 G點 )出發(fā)到 G點 (或 A點 )的最短路線及相應的最短距離，而且得到了從所有各中間點出發(fā)到 G點 (或 A點 )的最短路線及相應的距離。 動態(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ōu)值，最后求出 ， 就得到整個問題的最優(yōu)解。 ?不同點 ?線性規(guī)劃和非線性規(guī)劃研究的問題通常與時間無關，故又稱為靜態(tài)規(guī)劃。 第 4節(jié) 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關系 ?動態(tài)規(guī)劃方法 ?逆序解法 ?順序解法 ?關鍵：正確寫出動