【正文】 入生產(chǎn)的機器數(shù)量 u2的關(guān)系為 h=h(u2) 假定開始生產(chǎn)時完好的機器數(shù)量為 s1。 相應(yīng)的機器年完好率 b, 0 b1。 不包含時間因素的靜態(tài)決策問題（本質(zhì)上是一次決策問題）也可以適當(dāng)?shù)匾腚A段的概念，作為多階段的決策問題用動態(tài)規(guī)劃方法來解決。 5 . 最短路問題 ：給定一個交通網(wǎng)絡(luò)圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從 A點到 G點的最短距離（總費用最?。?。 描述階段的變量稱為 階段變量 。 狀態(tài)：表示每個階段開始所處的 自然狀況或客觀條件 。 年、月、路段 一個數(shù)、一組數(shù)、一個向量 狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為 狀態(tài)允許集合 。 描述決策的變量，稱為 決策變量 ?？捎靡粋€數(shù)、一組數(shù)或一向量（多維情形）來描述。 系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過去的歷史狀態(tài)和決策有關(guān)。如果第 k階段狀態(tài)變量sk的值、該階段的決策變量一經(jīng)確定，第 k+1階段狀態(tài)變量 sk+1的值也就確定。 如果狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。 狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下 無后效性 (馬爾可夫性 ) 如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響； 過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展； 構(gòu)造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求； 狀態(tài)變量要滿足無后效性的要求 ； 策略：是一個按順序排列的決策組成的集合。從允許策略集合中找出達到最優(yōu)效果的策略稱為 最優(yōu)策略 。 指標(biāo)函數(shù)和最優(yōu)值函數(shù)：用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，為 指標(biāo)函數(shù) 。在不同的問題中，指標(biāo)函數(shù)的含義是不同的，它可能是距離、利潤、成本、產(chǎn)量或資源消耗等。 小結(jié) : ? ?),()( 1,susVoptsf nkknkkkuu nk?? ??)],(,[ 111,1 ?????? nkknkkkk susVus ?方程 :狀態(tài)轉(zhuǎn)移方程 ),(1 kkkk usTs ??概念 : 階段變量 k﹑ 狀態(tài)變量 sk﹑ 決策變量 uk。 效益 指標(biāo)函數(shù)形式 : 和、 積 無后效性 ),( 111, ??? nkkkknk sususV ?可遞推 },{ **2*1 nuuu ?},{ **2*1 nsss ?解多階段決策過程問題，求出 最優(yōu)策略 ，即最優(yōu) 決策序列 ? ?? ?? ?susvoptsf nkknkkk uunk1, ?? ??f1(s1) 最優(yōu)軌線 ， 即執(zhí)行最優(yōu)策略時的 狀態(tài)序列 最優(yōu)目標(biāo)函數(shù)值 ),( ***1*1*,1*,1 nnnn ususVV ??從 k 到終點最優(yōu)策略 子策略的最優(yōu)目標(biāo)函數(shù)值 動態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡稱基本方程）。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的 . 最優(yōu)化原理：作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。 在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐段變換得到，從而確定了最優(yōu)路線。 對于靜態(tài)問題要人為地賦予 “ 時間 ” 概念 ， 以便劃分階段 。 一般地 ， 狀態(tài)變量的選擇是從過程演變的特點中尋找 。 確定狀態(tài)轉(zhuǎn)移方程 根據(jù) k 階段狀態(tài)變量和決策變量，寫出 k+1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。 以上五步是建立動態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。 例一、從 A 地到 D 地要鋪設(shè)一條煤氣管道 ,其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。 第一階段（ C → D）： C 有三條路線到終點 D 。 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 (最短路線為 B1→ C1 → D) d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 5 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 (最短路線為 B2→ C1 → D) 第三階段（ A → B ）： A 到 B 有二條路線。 假設(shè)： xi 為分配給第 i 個工廠的資金數(shù)量（萬元） ；gi(xi)為第 i 個工廠得到資金后提供的利潤值（萬元）。 ?????????????nixaxxgZiniiniii.. 0)(m a x11?據(jù)此，有下式： 三、投資分配問題 令： fk(x) = 以數(shù)量為 x 的資金分配給前 k 個工廠，所得到的最大利潤值。 當(dāng) k=1 時， f1(x) = g1(x) （因為只給一個工廠） 當(dāng) 1＜ k≤n 時，其遞推關(guān)系如下： 設(shè)： y 為分給第 k 個工廠的資金（其中 0≤y ≤ x ），此時還剩 x － y（萬元）的資金需要分配給前 k1 個工廠 ,如果采取最優(yōu)策略，則得到的最大利潤為 fk－ 1(x－ y) ,因此總的利潤為： gk(y) ＋ fk－ 1(x－ y) ? ?nkyxfygxf kkxyk..)()(m a x)( 10????? ???其中 如果 a 是以萬元為資金分配單位，則式中的 y 只取非負(fù)整數(shù) 0， 1， 2， … ， x。 投資 利潤 0 10 20 30 40 50 60 g1(x) 0 20 50 65 80 85 85 g2(x) 0 20 40 50 55 60 65 g3(x) 0 25 60 85 100 110 115 g4(x) 0 25 40 50 60 65 70 解：依據(jù)題意，是要求 f4(60) 。 第一階段：求 f1(x)。此時需考慮第一、第二個工廠如何進行投資分配，以取得最大的總利潤。 同理可求得其它 f2(x) 的值。 ? ?90 )40()(m a x)40( 1240,10,0