《運籌學》 課件 第5-7章 非線性規(guī)劃、動態(tài)規(guī)劃、圖與網絡

7/16/2024第5章非線性規(guī)劃1CONTENTS目錄7/16/20245.1

概述5.2

非線性規(guī)劃問題的解5.3

凸函數和凸規(guī)劃5.4

下降迭代算法5.5

一維搜索5.6

無約束極值問題的求解算法5.7

約束極值問題的最優(yōu)性條件5.8約束極值問題的求解算法25.1概述例5.1曲線擬合問題

7/16/20245.1.1非線性規(guī)劃問題舉例

(1)47/16/20245.1.1非線性規(guī)劃問題舉例解:按題意，根據最小二乘原理，有

5例5.3構件設計問題

7/16/20245.1.1非線性規(guī)劃問題舉例67/16/20245.1.1非線性規(guī)劃問題舉例

77/16/20245.1.2非線性規(guī)劃數學模型非線性規(guī)劃數學模型的一般形式是：—可行域

—特別當R=En,稱為無約束優(yōu)化問題85.2非線性規(guī)劃問題的解7/16/20245.2.1解（極值點）的定義

107/16/20245.2.1解（極值點）的定義

117/16/20245.2.2多元函數極值點的存在條件

利用可行方向的定義，下面給出局部極小點所滿足的條件。127/16/20245.2.2多元函數極值點的存在條件

137/16/20245.2.2多元函數極值點的存在條件

(b)局部極大點(b)局部極大點(c)鞍點

014147/16/20245.2.2多元函數極值點的存在條件

157/16/20245.2.2多元函數極值點的存在條件

165.3凸函數和凸規(guī)劃7/16/20245.3.1凸函數的定義

若將上述式中的不等號反向，那么就得到凹函數（ConcaveFunction）和嚴格凹函數（StrictConcaveFunction）的定義。187/16/20245.3.1凸函數的定義197/16/20245.3.2凸函數的性質

207/16/20245.3.2凸函數的性質

217/16/20245.3.3凸函數的判定條件

要判定一個函數是否是凸函數，可以直接根據5.3.1節(jié)的定義。而如果函數

是可微的，則還有下面兩個性質。227/16/20245.3.4凸規(guī)劃

性質5.7凸規(guī)劃的最優(yōu)解具有下述特殊性質：（1）如果最優(yōu)解存在，那么最優(yōu)解集為凸集；（2）任何局部最優(yōu)解也就是全局最優(yōu)解；（3）如果目標函數為嚴格凸函數且最優(yōu)解存在，

那么最優(yōu)解唯一。235.4下降迭代算法7/16/20245.4.1下降迭代算法

257/16/20245.4.2下降迭代算法的步驟

265.5一維搜索7/16/2024黃金分割法（0.618法）

TheGoldenSectionSearchMethod基本思想：對稱取點，等比例的縮小區(qū)間，除第一次外，每次只需計算一次函數值，可使區(qū)間縮小。b0a0t11t12b1a1f(t11)<f(t12)t22t215.5.1斐波那契法和黃金分割法287/16/20245.5.1斐波那契法和黃金分割法特點：具有相同的區(qū)間縮短率0.618；精度不如Fobonacci分數法；適用于不可微、不連續(xù)函數，可以先用“成功-失敗”法搜索到一個包含極小點的區(qū)間。297/16/2024斐波那契法

TheFibonacciSearchMethod問題：如何選擇實驗點，計算n次函數值能得到多大的區(qū)間縮短率？換句話說，計算n次函數值能將多大的區(qū)間縮短到1。答案：若對稱取點，利用上次已有的實驗點的函數值，計算n次函數值可獲得1/Fn區(qū)間縮短率。5.5.1斐波那契法和黃金分割法307/16/20245.5.1斐波那契法和黃金分割法Fibonacci數列(FibonacciSequence)F0=1,F1=1,F2=2,F3=3,F4=5,……Fk=Fk-1+Fk-2特點：需要預先確定迭代次數n;在計算n次函數值情況下，該方法獲得最大的區(qū)間縮短率，精度最高；適用于不可微、不連續(xù)函數。317/16/20245.5.2牛頓法（切線法）基本思想：適合二階連續(xù)可微的函數，求導數為0的方程根。特點適用于二階可微函數；最快的收斂速度，二階收斂速度；初始點要求接近極小點；可與“成功-失敗”法聯(lián)合使用。327/16/2024

5.5.3函數逼近法基本思想：在極小點附近以插值多項式來逼近目標函數的一種方法。事實上，上面的牛頓法就是在附近用一階Taylor展式來近似目標函數的。函數逼近法（插值法）335.6無約束極值問題的求解算法7/16/2024最速下降法（梯度法）

TheSteepestdescentmethod（TheGradientMethod））基本思想：以負梯度方向作為尋優(yōu)方向特點：迭代過程簡單，存儲量少，計算量?。患词故钦ǘ魏瘮狄膊荒苡邢薏绞諗?；相鄰兩次尋優(yōu)方向是垂直的;尋優(yōu)路線呈鋸齒狀（Zig-Zag)，在極小點附近收斂緩慢;5.6.1梯度法357/16/20245.6.1梯度法

36X0P0P1X1X2P2P3X3X*X47/16/20245.6.1梯度法377/16/20245.6.2牛頓法牛頓法（Newton’smethod)

在搜索方向上比梯度法有所改進。利用了目標函數在搜索點的梯度（一階導數）利用了目標函數的二階導數不但考慮了函數的梯度，還考慮了梯度的變化趨勢，收斂速度快。缺點：計算復雜，每步迭代都需要計算目標函數的二階偏導數（Hessian矩陣）和矩陣的逆。387/16/20245.6.2牛頓法

397/16/20245.6.3擬牛頓法擬牛頓法（Quasi-Newtonmethod）（變尺度法（VariableMetricMethod)）

405.7約束極值問題的最優(yōu)性條件7/16/20245.7.1起作用約束

427/16/20245.7.2可行方向和可行下降方向

437/16/20245.7.2可行方向和可行下降方向

447/16/20245.7.3庫恩-塔克條件庫恩-塔克（Kuhn-Tucker）條件，簡稱K-T條件，是非線性規(guī)劃領域中最重要的理論成果之一，是由H.W.Kuhn和A.W.Tucker在1951年發(fā)表的關于最優(yōu)性條件的論文中提出的。K-T條件是確定某點為局部最優(yōu)解的一階必要條件，只要是最優(yōu)點（同時是正則點）就必須滿足這個條件。但一般來說，它不是充分條件，即滿足這個條件的點不一定是最優(yōu)點。不過對于凸規(guī)劃來說，庫恩-塔克條件既是必要條件，也是充分條件。455.8約束極值問題的求解7/16/20245.8.1外點法和內點法

外點法（罰函數法）

外點法和內點法都是通過構造某種罰函數，將有約束的優(yōu)化問題轉換為一系列無約束的優(yōu)化問題來進行求解，因此稱之為序列無約束極小化技術（SequentialUnconstrainedMinimizationTechnique,SUMT）。極限意義下，無約束優(yōu)化問題的解將最終收斂到有約束優(yōu)化問題的解。477/16/20245.8.1外點法和內點法

內點法（障礙函數法）

和外點法從可行域外部逐漸靠近最優(yōu)解不同，內點法的主要思想是：在可行域的邊界上筑起一道很高的“圍墻”，當迭代點從可行域內部靠近邊界時，目標函數陡然增大，以示懲罰，阻止迭代點穿越邊界，因此搜索過程始終在可行域內，每一個迭代點都是嚴格可行的。顯然，內點法要求優(yōu)化問題的可行域內部非空，因而其不適用于等式約束的優(yōu)化問題。487/16/20245.8.2增廣拉格朗日乘子法為克服這個缺點，Hestenes和Powell于1969年首先提出了針對等式約束優(yōu)化問題的乘子法。Rockafellar于1973年將其推廣到不等式約束的優(yōu)化問題。本節(jié)將介紹在罰函數基礎上提出的增廣拉格朗日乘子法（又稱“乘子罰函數法”）。

497/16/2024第6章動態(tài)規(guī)劃50CONTENTS目錄6.1多階段決策問題6.2動態(tài)規(guī)劃的基本慨念和基本方程6.3最優(yōu)性原理和最優(yōu)性定理6.4動態(tài)規(guī)劃問題的求解6.5動態(tài)規(guī)劃的應用舉例7/16/2024511951年美國數學家（R.Bellman）提出同時提出解決的方法“最優(yōu)化原理”應用范圍十分廣泛。在企業(yè)管理方面：最優(yōu)路徑問題，資源分配問題，生產調度問題，庫存問題，裝載問題，排序問題，設備更新問題優(yōu)點：通常比線性規(guī)劃和非線性規(guī)劃更有效。特別是離散性問題。缺點：沒有標準的數學表達式，沒有統(tǒng)一的處理方法。若變數的維數太大，則無法求解；最致命缺點是最優(yōu)化原理沒有經過理論證明，其適用范圍還不清楚。

前言7/16/20246.1多階段決策問題

動態(tài)規(guī)劃是把多階段決策問題作為研究對象。

所謂多階段決策問題，是指這樣一類活動過程，即根據問題本身的特點，可以將其求解的全過程劃分為若干個相互聯(lián)系的階段(即將問題劃分為許多個相互聯(lián)系的子問題)，在它的每一階段都需要作出決策；并且在一個階段的決策確定以后再轉移到下一個階段。當各個階段的決策確定后，它們就構成一個決策序列，常稱之為策略。由于每個階段可選決策的不唯一性，這些相互聯(lián)系的決策組成的策略也就不止一個，那么這些可供選擇的策略構成一個集合，我們稱之為允許策略集合（簡稱策略集合）。

多階段決策問題概念7/16/2024靜態(tài)決策一次性決策動態(tài)決策多階段決策決策x1x2Zu輸入決策輸出決策效應第一月x1x2r1u1第二月x3r2u2第三月x4r3u3多階段決策問題模型7/16/2024

往往前一個階段的決策要影響到后一個階段的決策，從而影響整個過程。人們把這樣的決策過程稱做多階段決策過程(Multi-Stagedecisionprocess)。第一月x1x2r1u1第二月x3r2u2第三月x4r3u3

各個階段所確定的決策就構成了一個決策序列，稱為一個策略。一般來說，由于每一階段可供選擇的決策往往不止一個，因此，對于整個過程，就會有許多可供選擇的策略。7/16/2024多階段決策問題模型例：從A運送物資到D。AB1DC2C1B244532652階段1階段3階段2劃分階段單階段決策策略量化指標最優(yōu)策略7/16/2024多階段決策問題模型

多階段決策過程最優(yōu)化的目標是要達到整個活動過程的總體效果最優(yōu)。

不應僅考慮本階段最優(yōu)，還應考慮對最終目標的影響，從而作出對全局來講是最優(yōu)的決策。動態(tài)規(guī)劃就是符合這種要求的一種決策方法。7/16/2024多階段決策問題模型1)工廠生產過程：由于市場需求是一隨著時間而變化的因素，因此，為了取得全年最佳經濟效益，就要在全年的生產過程中，逐月或者逐季度地根據庫存和需求情況決定生產計劃安排。

第一月x1x2r1u1第二月x3r2u2第三月x4r3u3多階段決策問題舉例7/16/2024

2)設備更新問題：一般企業(yè)用于生產活動的設備，剛買來時故障少，經濟效益高，即使進行轉讓，處理價值也高，隨著使用年限的增加，就會逐漸變?yōu)楣收隙?，維修費用增加，可正常使用的工時減少，加工質量下降，經濟效益差，并且，使用的年限越長、處理價值也越低，自然，如果賣去舊的買新的，還需要付出更新費．因此就需要綜合權衡決定設備的使用年限，使總的經濟效益最好。

3)連續(xù)生產過程的控制問題：一般化工生產過程中，常包含一系列完成生產過程的設備，前一工序設備的輸出則是后一工序設備的輸入，因此，應該如何根據各工序的運行工況，控制生產過程中各設備的輸入和輸出，以使總產量最大。多階段決策問題舉例7/16/2024

以上所舉問題的發(fā)展過程都與時間因素有關，因此在這類多階段決策問題中，階段的劃分常取時間區(qū)段來表示，并且各個階段上的決策往往也與時間因素有關，這就使它具有了“動態(tài)”的含義，所以把處理這類動態(tài)問題的方法稱為動態(tài)規(guī)劃方法。

實際中尚有許多不包含時間因素的一類“靜態(tài)”決策問題，就其本質而言是一次決策問題，是非動態(tài)決策問題，但是也可以人為地引入階段的概念當作多階段決策問題，應用動態(tài)規(guī)劃方法加以解決。7/16/2024多階段決策問題舉例

4）資源分配問題：便屬于這類靜態(tài)問題。如：某工業(yè)部門或公司，擬對其所屬企業(yè)進行稀缺資源分配，為此需要制定出收益最大的資源分配方案。這種問題原本要求一次確定出對各企業(yè)的資源分配量，它與時間因素無關，不屬動態(tài)決策，但是，我們可以人為地規(guī)定一個資源分配的階段和順序，從而使其變成一個多階段決策問題。總資源部門1x1x2r1u1部門2x3r2u2部門3x4r3u3部門1的分配量多階段決策問題舉例7/16/2024

5）運輸網絡問題：如圖所示的運輸網絡，點間連線上的數字表示兩地距離(也可是運費、時間等)，要求從v1至v10的最短路線。這種運輸網絡問題也是靜態(tài)決策問題。但是，按照網絡中點的分布，可以把它分為4個階段，而作為多階段決策問題來研究。多階段決策問題舉例7/16/2024

通常多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實現(xiàn)的。

一般情況下，系統(tǒng)在某個階段的狀態(tài)轉移除與本階段的狀態(tài)和決策有關外，還可能與系統(tǒng)過去經歷的狀態(tài)和決策有關。因此，問題的求解就比較困難復雜。

而適合于用動態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策問題，即具有“無后效性”的多階段決策過程。

第一月x1x2r1u1第二月x3r2u2第三月x4r3u3動態(tài)規(guī)劃求解特點7/16/2024Xk+1=Tk(xk,uk)T1x1x2r1(x1,u1)u1(x1)T2x3r2(x2,u2)u2(x2)Tkxkxk+!rk(xk,uk)uk(xk)Tnxnxn+1……rn(xn,un)un(xn)

所謂無后效性，又稱馬爾柯夫性，是指系統(tǒng)從某個階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經歷的狀態(tài)和決策(歷史)無關。動態(tài)規(guī)劃求解特點7/16/2024多階段決策過程特點:要點：階段，狀態(tài)，決策，狀態(tài)轉移方程，k-后部子過程狀態(tài)

x1階段1T1決策u1狀態(tài)

x2決策u2階段2T2狀態(tài)

x3...狀態(tài)

xk決策uk階段kTk狀態(tài)

xk+1...狀態(tài)

xn決策un階段nTn狀態(tài)

xn+1動態(tài)規(guī)劃求解特點7/16/2024多段決策過程中從第k階段到最終階段的過程稱為k-后部子過程，簡稱k-子過程。Tkxkxk+!rk(xk,uk)uk(xk)Tnxnxn+1…rn(xn,un)un(xn)動態(tài)規(guī)劃求解特點7/16/2024例1：為了說明動態(tài)規(guī)劃的基本思想方法和特點，下面以圖1所示為例討論的求最短路問題的方法。動態(tài)規(guī)劃方法導引案例7/16/2024第一種方法稱做全枚舉法或窮舉法。

它的基本思想是列舉出所有可能發(fā)生的方案和結果，再對它們一一進行比較，求出最優(yōu)方案。最優(yōu)路線是v1→v3→

v7→

v9→v10,最短距離是18．

顯然，當組成交通網絡的節(jié)點很多時，用窮舉法求最優(yōu)路線的計算工作量將會十分龐大，而且其中包含著許多重復計算．

第二種方法即所謂“局部最優(yōu)路徑”法，是說某人從k出發(fā)，他并不顧及全線是否最短，只是選擇當前最短途徑，“逢近便走”，錯誤地以為局部最優(yōu)會致整體最優(yōu)，在這種想法指導下，所取決策必是v1→v3→v5→

v8→

v10

，全程長度是20；顯然，這種方法的結果常是錯誤的．動態(tài)規(guī)劃方法導引案例7/16/2024

第三種方法是動態(tài)規(guī)劃方法。

基本思想:

首先將問題劃分為4個階段，每次的選擇總是綜合后繼過程的一并最優(yōu)進行考慮，

在各段所有可能狀態(tài)的最優(yōu)后繼過程都已求得的情況下，全程的最優(yōu)路線便也隨之得到。為了找出所有可能狀態(tài)的最優(yōu)后繼過程，動態(tài)規(guī)劃方法總是從過程的最后階段開始考慮，然后逆著實際過程發(fā)展的順序，逐段向前遞推計算直至始點。

動態(tài)規(guī)劃方法導引案例7/16/2024

整個求解過程分為兩個階段：

先按整體最優(yōu)的思想逆序地求出各個子問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線值，然后再順序地求出整個問題的最優(yōu)策略和最優(yōu)路線。動態(tài)規(guī)劃方法導引案例7/16/20246.2動態(tài)規(guī)劃的基本概念和基本方程6.2.1動態(tài)規(guī)劃的基本概念階段

狀態(tài)

決策

策略

狀態(tài)轉移方程

指標函數

最優(yōu)解

邊界條件動態(tài)規(guī)劃模型7/16/2024為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰當地劃分為若干個相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段。一個階段，就是需要作出一個決策的子問題，通常，階段是按決策進行的時間或空間上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量．階段數等于多段決策過程從開始到結束所需作出決策的數目。從第

k個階段到最后一個階段的過程被稱為

k后部子過程。階段和階段變量7/16/2024v1v6v5v4v3v2v7v8444656332415k=1k=2k=3k=4階段和階段變量7/16/2024用以描述事物(或系統(tǒng))在某特定的時間與空間域中所處位置及運動特征的量，稱為狀態(tài)。反映狀態(tài)變化的量叫做狀態(tài)變量,記作sk

。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達狀態(tài)集.可能狀態(tài)集實際上是關于狀態(tài)的約束條件。通?？赡軤顟B(tài)集用相應階段狀態(tài)sk的大寫字母Sk表示，sk∈Sk，可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問題而定狀態(tài)，狀態(tài)變量和可能狀態(tài)集合7/16/2024

在上述最短路問題中第一階段狀態(tài)為v1，狀態(tài)變量s1的狀態(tài)集合S1={v1}；第二階段則有三個狀態(tài)：v2,v3,v4

,狀態(tài)變量s2的狀態(tài)集合S2={v2,v3,v4}

；第三階段也有三個狀態(tài):v5,v6,v7

，狀態(tài)變量s3的狀態(tài)集合S3={v5,v6,v7}

；第四階段則有二個狀態(tài)：v8,v9,狀態(tài)變量s4的狀態(tài)集合S4={v8,v9}

；狀態(tài)，狀態(tài)變量和可能狀態(tài)集合7/16/2024

所謂決策，就是確定系統(tǒng)過程發(fā)展的方案。決策的實質是關于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)作出的選擇。

用以描述決策變化的量稱之決策變量.和狀態(tài)變量一樣，決策變量可以用一個數，一組數或一向量來描述，也可以是狀態(tài)變量的函數，記以uk=uk(sk)，表示于階段k處于狀態(tài)sk時的決策變量。決策變量的取值往往也有一定的允許范圍，稱之允許決策集合。決策變量uk(sk)的允許決策集用Uk(sk)表示,uk(sk)∈Uk(sk)允許決策集合實際是決策的約束條件。決策，決策變量和允許決策集合7/16/2024v1v6v5v4v3v2v7v8444656332415u1(v1)=v2U1(v1)={v2,v3}u2(v3)=v4U2(v3)={v4,v5}決策，決策變量和允許決策集合7/16/2024

策略(Policy)也叫決策序列．策略有全過程策略和k部子策略之分.

全過程策略是指具有n個階段的全部過程，由依次進行的n個階段決策構成的決策序列，簡稱策略，表示為p1,n{u1,u2,…,un}。從k階段到第n階段，依次進行的階段決策構成的決策序列稱為k部子策略,表示為pk,n{uk,uk+1,…,un}

，顯然當k=1時的k部子策略就是全過程策略。在實際問題中，由于在各個階段可供選擇的決策有許多個，因此，它們的不同組合就構成了許多可供選擇的決策序列(策略)，由它們組成的集合，稱之允許策略集合，記作P1,n,從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。

策略和允許策略集合7/16/2024

系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結果是系統(tǒng)狀態(tài)的轉移，即系統(tǒng)由階段k的初始狀態(tài)sk轉移到終止狀態(tài)sk+1

，或者說，系統(tǒng)由k階段的狀態(tài)sk轉移到了階段k+1的狀態(tài)sk+1

，多階段決策過程的發(fā)展就是用階段狀態(tài)的相繼演變來描述的。第一月x1x2r1u1第二月x3r2u2第三月x4r3u3狀態(tài)轉移方程7/16/20242024/7/16對于具有無后效性的多階段決策過程,系統(tǒng)由階段k到階段k+1的狀態(tài)轉移完全由階段k的狀態(tài)sk和決策uk(sk)所確定，與系統(tǒng)過去的狀態(tài)s1,s2,…,sk-1及其決策u1(s1),u2(s2)…uk-1(sk-1)無關。系統(tǒng)狀態(tài)的這種轉移，用數學公式描述即有這一關系式指明了由第階段到第階段的狀態(tài)轉移規(guī)律，稱為狀態(tài)轉移方程或狀態(tài)轉移函數如果狀態(tài)轉移方程是確定性的，則該過程稱為確定性多階段決策過程。如果這種轉移關系是以某種概率實現(xiàn)的，則稱這種過程為隨機性多階段決策過程。狀態(tài)轉移方程7/16/2024

用來衡量策略或子策略或決策的效果的某種數量指標，就稱為指標函數。它是定義在全過程或各子過程或各階段上的確定數量函數。對不同問題，指標函數可以是諸如費用、成本、產值、利潤、產量、耗量、距離、時間、效用，等等。指標函數有階段指標函數和過程指標函數之分(1)階段指標函數（也稱階段效應）。

用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時的指標，則它就是第k段指標函數，簡記為gk

。例如g2(v2,v5)=3,即v2到v5的距離為3。指標函數和最優(yōu)值函數7/16/2024

(2)過程指標函數（也稱目標函數）。

用Rk(sk,uk)表示第k子過程的指標函數。如例1的Rk(sk,uk)表示處于第k段sk狀態(tài)且所作決策為uk時，從sk點到終點v10的距離。由此可見，Rk(sk,uk)不僅跟當前狀態(tài)sk有關，還跟該子過程策略pk(sk)有關，因此它是sk和pk(sk)的函數，嚴格說來，應表示為:

實際應用中指標函數往往表示為Rk(sk,uk)或Rk(sk)。它與第k子過程上各段指標函數有關，過程指標函數Rk(sk)通常是描述k后部子過程效果優(yōu)劣的數量指標，它是由各階段的階段指標函數gk(sk,uk)累積形成的指標函數和最優(yōu)值函數7/16/2024

適于用動態(tài)規(guī)劃求解的問題的過程指標函數（即目標函數），必須具有關于階段指標的可分離形式．對于k部子過程的指標函數可以表示為：式中，

表示某種運算，可以是加、減、乘、除、開方等。

多階段決策問題中，常見的目標函數形式之一是取各階段效應之和的形式，即:

有些問題，如系統(tǒng)可靠性問題，其目標函數是取各階段效應的連乘積形式，如：

總之，具體問題的目標函數表達形式需要視具體問題而定。指標函數和最優(yōu)值函數7/16/2024

用fk(sk)表示第k子過程指標函數在狀態(tài)sk下的最優(yōu)值,即

稱fk(sk)為第k子過程上的最優(yōu)值函數；與它相應的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)

；而構成該子策賂的各段決策稱為該過程上的最優(yōu)決策記為

指標函數和最優(yōu)值函數7/16/2024簡記為

特別當k=1且s1取值唯一時，f1(s1)就是問題的最優(yōu)值，而p1*就是最優(yōu)策略。如例1只有唯一始點v1即s1取值唯一,故f1(s1)=18就是例的最優(yōu)值，而

就是例1的最優(yōu)策略。

我們把最優(yōu)策略和最優(yōu)值統(tǒng)稱為問題的最優(yōu)解。指標函數和最優(yōu)值函數7/16/2024多階段決策問題的數學模型

綜上所述，適于應用動態(tài)規(guī)劃方法求解的一類多階段決策問題，亦即具有無后效性的多階段決策問題的數學模型呈以下形式:式中“OPT”表示最優(yōu)化，視具體問題取max或min。

上述數學模型說明了對于給定的多階段決策過程，求取一個(或多個)最優(yōu)策略或最優(yōu)決策序列

7/16/20246.2.2動態(tài)規(guī)劃的基本方程標號法動態(tài)規(guī)劃的建模實例動態(tài)規(guī)劃問題的建模函數基本方程動態(tài)規(guī)劃的基本方程7/16/2024

標號法適用于例1這類最優(yōu)路線問題的特殊解法——標號法。

標號法是借助網絡圖通過分段標號來求出最優(yōu)路線的一種簡便、直觀的方法。通常標號法采取“逆序求解”的方法來尋找問題的最優(yōu)解，即從最后階段開始，逐次向階段數小的方向推算，最終求得全局最優(yōu)解。標號法7/16/2024下面給出標號法的一般步驟：

1.從最后一段標起，該段各狀態(tài)(即各始點)到終點的距離用數字分別標在各點上方的方格內，并用粗箭線連接各點和終點。

2.向前遞推，給前一階段的各個狀態(tài)標號。每個狀態(tài)上方方格內的數字表示該狀態(tài)到終點的最短距離。即為該狀態(tài)到該階段已標號的各終點的段長，再分別加上對應終點上方的數字而取其最小者。將剛標號的點沿著最短距離所對應的已標號的點用粗箭線連接起來，表示出各剛標號的點到終點的最短路線。3.逐次向前遞推，直到將第一階段的狀態(tài)(即起點)也標號，起點方格內的數字就是起點到終點的最短距離，從起點開始連接終點的粗箭線就是最短路線。標號法7/16/20242024/7/16

用標號法來求解下例

例：網絡圖表示某城市的局部道路分布圖。一貨運汽車從S出發(fā)，最終到達目的地E。其中Ai(i＝1，2，3),Bj(j＝1，2)和Ck(k＝1，2)是可供汽車選擇的途經站點，各點連線上的數字表示兩個站點問的距離。問此汽車應走哪條路線，使所經過的路程距離最短?

圖2某城市的局部道路分布圖標號法-案例7/16/2024

第一步：先考慮第四階段，即k=4，

該階段共有兩個狀態(tài)：C1、C2，設f4(C1)和f4(C2)分別表示C1、C2到E的最短距離，顯然有

f4(C1)=5和f4(C2)=8，邊界條件f5(E)=0。

58標號法-案例7/16/2024

第二步：即k=3,該階段共有兩個狀態(tài):B1,

B2

從B1出發(fā)有兩種決策:B1→C1，B1→C2

。

d3(B1,C1)表示B1到C1的距離,B1→C1的階段指標函數為d3(B1,C1)＝6，B1→C2的階段指標函數為d3(B1,C2)＝5。

f3(B1)＝min{d3(B1,C1)+f4(C1),d3(B1,C2)+f4(C2)}＝min(6＋5，5＋8)＝11。那么，從B1出發(fā)到E的最短路線是B1→C1→E，對應的決策u3(B1)=C1

。5811標號法-案例7/16/2024

(2)從B2出發(fā)也有兩種決策:B2→C1,B2→C2同理,有f3(B2)=min{d3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)}＝min(9+5，8+87)＝14，那么，從B2出發(fā)到E的最短路線是B2→C1→E，且u3(B2)=C1。

581114標號法-案例7/16/2024第三步：即k＝2,該階段共有三個狀態(tài):Al,A2,A3

（1）A1→B1,A1→B2。則

f2(A1)=min{d2(A1,B1)+f3(B1),d2(A1,B2)+f3(B2)}＝min{6＋11，5＋14}＝17，即A1到E的最短路線為A1→B1→C1→E且u3(A1)＝B1

。(2）A2→B1,A2→B2。f2(A2)＝min{d2(A2,B1)+f3(B1),d2(A2,B2)+f3(B2)}＝min{8+11，6+14}＝19，即A2到E的最短路線為A2→B1→C1→E，且u3(A2)＝B1。(3)A3→B1,A3→B2

此時

f2(A3)=min{d2(A3,B1)+f3(B1),d2(A3,B2)+f3(B2)}＝min{7+11，4+14}＝18，即A3到E的最短路線為A3→B1→C1→E

，u2(A3)＝B1

A3→B2→C1→E對應的u2(A3)＝B2

標號法-案例7/16/2024581114標號法-案例7/16/2024第四步：即k＝1，該階段只有一個狀態(tài)S,從S出發(fā)有三種決策:S→A1,S→A2,S→A3,那么,

f1(S)=min{d1(S,A1)+f2(A1),d1(S,A2)+f2(A2),d1(S,A3)+f2(A3)}＝min{4+17，3+19,3+18}＝21，

那么,從S到E共有三條最短路線：

此時,u1(S)＝A1

u1(S)＝A3

，最短距離為21。58111417191821標號法-案例7/16/202458111417191821

每個狀態(tài)上方的方格內的數字表示該狀態(tài)到E的最短距離，首尾相連的粗箭線構成每一狀態(tài)到E的最短路線。

因此，標號法不但給出起點到終點的最短路線和最短距離，同時也給出每一狀態(tài)到終點的最短路線及其最短距離。

S---A1---B1---C1---E標號法-案例7/16/2024

在上例中，用標號法求解最短路線的計算公式可以概括寫成：

其中，

在這里表示從狀態(tài)sk到由

決策uk(sk)所決定的狀態(tài)sk+1之間的距離,邊界條件表示全過程到第四階段終點結束。邊界條件第k子過程的最優(yōu)指標第k+1子過程的最優(yōu)指標K階段指標逆序遞推法；這里可以指出，該法的關鍵在于給出一種遞推關系。一般把這種遞推關系稱為動態(tài)規(guī)劃的函數基本方程。函數基本方程7/16/20242024/7/1610158函數基本方程7/16/2024

一般地，對于n個階段的決策過程，假設只考慮指標函數是“和”與“積”的形式，第k階段和第k+1階段間的遞推公式可表示如下：(1)當過程指標函數為下列“和”的形式時，

相應的函數基本方程為

函數基本方程7/16/2024(2)當過程指標函數為下列“積”的形式時,

相應的函數基本方程為

可以看出，和、積函數的基本方程中邊界條件(即的取值)是不同的。函數基本方程7/16/2024

標號法僅適用于求解象最短路線問題那樣可以用網絡圖表示的多階段決策問題。但不少多階段決策問題不能用網絡圖表示。此時,應該用函數基本方程來遞推求解.

首先，要有效地建立動態(tài)規(guī)劃模型,然后再遞推求解,最后得出結論.

構造成動態(tài)規(guī)劃模型,這是非常重要的一步。正確地建立一個動態(tài)規(guī)劃模型,往往問題也就解決了一大半,而一個正確的動態(tài)規(guī)劃模型,應該滿足哪些條件呢?動態(tài)規(guī)劃問題的建模7/16/2024

1．應將實際問題恰當地分割成n個子問題(n個階段)。通常是根據時間或空間而劃分的，或者在經由靜態(tài)的數學規(guī)劃模型轉換為動態(tài)規(guī)劃模型時，常取靜態(tài)規(guī)劃中變量的個數n，即k=n。2．正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，又能滿足無后效性．動態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng)中和通常所說的狀態(tài)的概念是有所不同的，動態(tài)規(guī)劃中的狀態(tài)變量必須具備以下三個特征：動態(tài)規(guī)劃問題的建模7/16/2024

(1)要能夠正確地描述受控過程的變化特征。(2)要滿足無后效性。即如果在某個階段狀態(tài)已經給定，那么在該階段以后，過程的發(fā)展不受前面各段狀態(tài)的影響，如果所選的變量不具備無后效性，就不能作為狀態(tài)變量來構造動態(tài)規(guī)劃的模型。(3)要滿足可知性。即所規(guī)定的各段狀態(tài)變量的值，可以直接或間接地測算得到。一般在動態(tài)規(guī)劃模型中，狀態(tài)變量大都選取那種可以進行累計的量。此外，在與靜態(tài)規(guī)劃模型的對應關系上，通常根據經驗，線性與非線性規(guī)劃中約束條件的個數，相當于動態(tài)規(guī)劃中狀態(tài)變量sk的維數．而前者約束條件所表示的內容，常就是狀態(tài)變量sk所代表的內容。動態(tài)規(guī)劃問題的建模7/16/20243．正確地定義決策變量及各階段的允許決策集合Uk(sk)，根據經驗，一般將問題中待求的量，選作動態(tài)規(guī)劃模型中的決策變量?；蛘咴诎鸯o態(tài)規(guī)劃模型(如線性與非線性規(guī)劃)轉換為動態(tài)規(guī)劃模型時，常取前者的變量xj為后者的決策變量uk。4.能夠正確地寫出狀態(tài)轉移方程，至少要能正確反映狀態(tài)轉移規(guī)律。如果給定第k階段狀態(tài)變量sk的值，則該段的決策變量uk一經確定，第k+1段的狀態(tài)變量sk+1的值也就完全確定，即有sk+1=Tk(sk,uk)動態(tài)規(guī)劃問題的建模7/16/20245．根據題意,正確地構造出目標與變量的函數關系——目標函數，目標函數應滿足下列性質：(1)可分性，即對于所有k后部子過程，其目標函數僅取決于狀態(tài)sk及其以后的決策uk,uk+1,┈,un,就是說它是定義在全過程和所有后部子過程上的數量函數。(2)要滿足遞推關系，即(3)函數對其變元Rk+1來說要嚴格單調。動態(tài)規(guī)劃問題的建模7/16/20246．寫出動態(tài)規(guī)劃函數基本方程例如常見的指標函數是取各段指標和的形式

其中表示第i階段的指標，它顯然是滿足上述三個性質的。所以上式可以寫成：動態(tài)規(guī)劃問題的建模7/16/2024

例3有某種機床,可以在高低兩種不同的負荷下進行生產,

在高負荷下生產時,產品的年產量為g,與年初投入生產的機床數量u1的關系為g=g(u1)=8u1,

這時,年終機床完好臺數將為au1,(a為機床完好率，0<a<1,設a=0.7).

在低負荷下生產時,產品的年產量為h,和投入生產的機床數量u2的關系為h=h(u2)=5u2,相應的機床完好率為b(0<b<1,設b=0,9),一般情況下a<b。動態(tài)規(guī)劃問題的建模-實例7/16/2024

假設某廠開始有x=1000臺完好的機床，現(xiàn)要制定一個五年生產計劃，問每年開始時如何重新分配完好的機床在兩種不同的負荷下生產的數量，以使在5年內產品的總產量為最高。

第一年完好機器高負荷低負荷產量產量第二年剩余完好機器動態(tài)規(guī)劃問題的建模-實例7/16/2024解：首先構造這個問題的動態(tài)規(guī)劃模型。

1．變量設置

(1)設階段變量k表示年度，因此，階段總數n=5。(2)狀態(tài)變量sk表示第k年度初擁有的完好機床臺數，同時也是第k-1年度末時的完好機床數量。

(3)決策變量uk，表示第k年度中分配于高負荷下生產的機床臺數。

sk-uk便為該年度中分配于低負荷下生產的機床臺數．動態(tài)規(guī)劃問題的建模-實例7/16/2024這里sk與uk均取連續(xù)變量，當它們有非整數數值時．可以這樣理解：如sk＝0.6，就表示一臺機器在k年度中正常工作時間只占6/10；uk=0.4時，就表示一臺機床在k年度只有4/10的時間于高負荷下工作．2．狀態(tài)轉移方程為

k=1，2，…,63．允許決策集合,在第k段為動態(tài)規(guī)劃問題的建模-實例7/16/20244目標函數。設gk(sk,uk)為第k年度的產量，則gk(sk,uk)=8uk+5(sk-uk),因此目標函數為

k＝1,2,．．．,5

5．條件最優(yōu)目標函數遞推方程。

令fk(sk)表示由第k年的狀態(tài)sk出發(fā)，采取最優(yōu)分配方案到第5年度結束這段時間的產品產量，根據最優(yōu)化原理有以下遞推關系：

k=1,2,3,4,5114動態(tài)規(guī)劃問題的建模-實例7/16/2024,=

=

因此，當u4*=s4時，有最大值f4(s4)=13.6s46.邊界條件為

下面采用逆序遞推計算法,從第5年度開始遞推計算。k=5時有顯然，當u5*=s5時，f5(s5)有最大值，相應的有f5(s5)=8s5k=4時有動態(tài)規(guī)劃問題的建模-實例7/16/20246.3最優(yōu)化原理和最優(yōu)性定理最優(yōu)化原理：作為一個全過程的最優(yōu)策略具有這樣的性質：對于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下的諸決策必構成一個最優(yōu)子策略。即若某一全過程最優(yōu)策略為：

則對上述策略中所隱含的任一狀態(tài)而言，第k子過程上對應于該狀態(tài)的最優(yōu)策略必然包含在上述全過程最優(yōu)策略p1*中，即為6.3最優(yōu)化原理和最優(yōu)性定理1177/16/20246.4動態(tài)規(guī)劃問題的求解6.4動態(tài)規(guī)劃問題的求解動態(tài)規(guī)劃問題的狀態(tài)變量可以是離散變量或者是連續(xù)變量，可分為離散型動態(tài)規(guī)劃和連續(xù)型動態(tài)規(guī)劃。通常對于連續(xù)型動態(tài)規(guī)劃，由于變量的取值不可一一列舉，通常用解析法進行求解，而對于離散型動態(tài)規(guī)劃，尤其是當指標函數沒有明確的解析表達式（例如用數值表給出）時通常用數值法求解。下面通過舉例進行分析：7/16/2024資源分配：設有某種資源，總量為M，可以投入n種生產活動。已知用于活動k的資源為uk時的收益是gk(uk)，問應如何分配資源，使n種生產活動的總收益最大。這種問題就是資源的多元分配問題。6.4.1離散確定性動態(tài)規(guī)劃7/16/2024如果將n種活動作為一個互相銜接的整體，對一種活動的資源分配作為一個階段，每個階段確定對一種活動的資源投放量。則該問題成為一個多階段決策問題。在資源分配問題中，決策變量選為對活動k的資源投放量，因此狀態(tài)變量可以選擇為階段k初所擁有的資源量，即將要在第k種到第n種活動間分配的資源量。狀態(tài)變量xk的選取原則是要能夠據此確定決策uk，以及滿足狀態(tài)轉移方程所要求的無后效性。資源分配7/16/2024關于狀態(tài)變量xk的約束條件是0≤xk≤M關于決策變量uk的約束條件是0≤uk≤xk狀態(tài)轉移方程為xk+1=xk-uk顯然它滿足無后效性要求。階段效應為對活動k投放資源uk時的收益，

rk(xk,uk)=gk(uk)目標函數是為n種活動投放資源后的總收益動態(tài)規(guī)劃基本方程資源分配7/16/2024案例：

某公司擬將50萬元資金投放下屬A、B、C三個部門，各部門在獲得資金后的收益如表所示，用動態(tài)規(guī)劃方法求總收益最大的投資分配方案（投資數以10萬元為單位）。投放資金（萬元）01020304050收益（萬元）A01520252830B0010254570C01020304050資源分配7/16/2024xk表示給部門k分配資金時擁有的資金數。uk表示給部門k分配的資金數（以10萬元為單位）。狀態(tài)轉移方程是xk+1=xk-uk。gk(uk)

階段效應如表所示。fk(xk)目標函數是階段效應求和。首先逆序遞推資源分配7/16/2024資金01020304050收益A01520252830B0010254570C01020304050從表可知g3()是單調遞增的函數，因此，當u3=x3時達到最大。即：逆序求條件最優(yōu)目標函數值集合和條件最優(yōu)決策集合。資源分配7/16/2024逆序求條件最優(yōu)目標函數值集合和條件最優(yōu)決策集合。k=2時，0≤x2≤50≤u2≤x2

資金01020304050收益A01520252830B0010254570C01020304050資源分配7/16/2024資金01020304050收益A01520252830B0010254570C01020304050資源分配7/16/2024資金01020304050收益A01520252830B0010254570C01020304050資源分配7/16/2024逆序求條件最優(yōu)目標函數值集合和條件最優(yōu)決策集合。當k=1時，有x1=5，0≤u1≤x1=5資金01020304050收益A01520252830B0010254570C01020304050資源分配7/16/2024順序求最優(yōu)目標函數值和最優(yōu)策略、最優(yōu)路線資源分配7/16/2024一維背包背包問題的特征類似于往旅行背包里面裝用品的問題，要求在旅行袋容積和／或載重量的限制下，所裝物品的總價值最大。這一類問題在海運、航運以及航天等領域都有應用。

例:對于一個具體問題 W=5用動態(tài)規(guī)劃求解k=3

貨物123單位重量231單位價值658030解:該問題中有三種物品需要裝載，因此可以作為三段決策問題，每階段為一個物品決定裝船的數量.k階段系統(tǒng)的狀態(tài)為在給第k物品決定裝載數量時，船上還剩余的載重能力xk7/16/2024

貨物123單位重量231單位價值658030一維背包7/16/2024一維背包7/16/2024k=20≤x2≤5

貨物123單位重量231單位價值658030一維背包7/16/2024一維背包7/16/2024對于k=1,x1=5

貨物123單位重量231單位價值658030一維背包7/16/2024一維背包7/16/2024二維背包若只考慮重量或體積限制，則稱為一維背包問題，若同時考慮重量和體積限制,則稱為二維背包問題.考慮有N種物品需要裝船。第i種物品單位的重量為ωi，單件體積為υi，而價值為pi。最大的裝載重量為W，最大體積為V?，F(xiàn)在要確定在不超過船的最大載重量和最大體積（不考慮貨物形狀）的條件下，使所載物品價值最大的裝載方案。7/16/2024例已知貨物的單位重量ωi，單位體積υi及價值pi如表所示，船的最大載重能力為W＝5，最大裝載體積為V＝8，求最優(yōu)裝載方案。iωiυipiA1230B3480C2365二維背包7/16/2024例W＝5，V＝8k階段系統(tǒng)的狀態(tài)為在給第k物品決定裝載數量時，船上還剩余的載重能力xk和剩余體積yk.因此狀態(tài)變量是二維的，記為（xk,yk）。有0≤xk≤5，0≤yk≤8決策變量uk表示裝載第k種物品的數量。二維背包7/16/2024例W＝5，V＝8解狀態(tài)轉移方程為：xk+1=xk-uk·ωkyk+1=yk-uk·υk各階段的狀態(tài)可能集與決策允許集為：

iωiυiA12B34C23二維背包7/16/2024iωiυiA12B34C23階段效應為rk(xk,yk,uk)=pk·uk二維背包7/16/2024iωiυipiA1230B3480C2365二維背包7/16/2024解當k＝3時，由f4(x4,y4)=0(x3,y3)0/(x3,y3)1/(x3-2,y3-3)2/(x3-4,y3-6)f3()U’3(5,8)0＋065＋02×65＋01302(4,6)0＋065＋02×65＋01302(3,4)0＋065＋0×651(2,2)0＋0××00(1,0)0＋0××00(2,4)0＋065＋0×651(1,2)0＋0××00(0,0)0＋0××00iωiυipiA1230B3480C2365u3二維背包7/16/2024當k＝2時iωiυipiA1230B3480C2365二維背包7/16/2024解當k＝2時，由f3(x3,y3)已知(x2,y2)0/(x2,y2)1/(x2-3,y2-4)f2()U’2（5，8）0＋13080＋651451（4，6）0＋13080＋01300（3，4）0＋6580＋0801（2，2）0＋0×00（1，0）0＋0×00u2iωiυipiA1230B3480C2365二維背包7/16/2024(x2,y2)0/(x2,y2)1/(x2-2,y2-4)f2()U’2（5，8）0＋13080＋651451（4，6）0＋13080＋01300（3，4）0＋6580＋0801（2，2）0＋0×00（1，0）0＋0×000/(5,8)1/(4,6)2/(3,4)3/(2,2)4/(1,0)f1()u1(5,8)0＋14530＋13060＋8090＋0120＋01601解當k＝1時，W=5,V=8二維背包7/16/2024(x3,y3)0/(x3,y3)1/(x3-2,y3-3)2/(x3-4,y3-6)f3()U’3(5,8)0＋065＋02×65＋01302(4,6)0＋065＋02×65＋01302(3,4)0＋065＋0×651(2,2)0＋0××00(1,0)0＋0××00(2,4)0＋065＋0×651(1,2)0＋0××00(0,0)0＋0××00二維背包7/16/2024二維背包7/16/20246.4.2連續(xù)確定性動態(tài)規(guī)劃用動態(tài)規(guī)劃方法求解線性規(guī)劃問題：

K=3,2,1

7/16/2024當k=3時有

再用狀態(tài)轉移方程來替換上式中的

6.4.2連續(xù)確定性動態(tài)規(guī)劃7/16/2024當k=1時，有

這就是指標函數的最優(yōu)值

6.4.2連續(xù)確定性動態(tài)規(guī)劃7/16/2024即線性規(guī)劃問題的最優(yōu)解為最優(yōu)值為6.4.2連續(xù)確定性動態(tài)規(guī)劃7/16/20246.5動態(tài)規(guī)劃的應用舉例前面已經討論過的最短路問題、裝載問題（又稱背包問題）和資源分配問題都可以作為動態(tài)規(guī)劃應用的實例。為了進一步擴大動態(tài)規(guī)劃的應用范圍，我們再舉幾個應用實例。7/16/20241556.5.1可回收資源再利用

7/16/2024156狀態(tài)轉移方程為允許決策集合

過程指標是階段指標的和，即

6.5.1可回收資源再利用7/16/2024157

依次類推，可求得：6.5.1可回收資源再利用7/16/2024158

計算結果表明最優(yōu)策略為即前兩年將全部設備都投入低負荷生產，后三年將全部設備都投入高負荷生產，這樣可以使5年的總產量最大，最大產量是23700件。有了上述最優(yōu)策略，各階段的狀態(tài)也就隨之確定了，即按階段順序計算出各年年初的完好設備數量。6.5.1可回收資源再利用7/16/2024

6.5.1可回收資源再利用7/16/2024設某廠計劃全年生產某種產品A。其四個季度的訂貨量分別為600公斤，700公斤，500公斤和1200公斤。已知生產產品A的生產費用與產品產量的平方成正比，系數為0.005。廠內有倉庫可以存放產品，存儲費為每公斤每季度1元。求最佳的生產安排使得年總成本最小。解：四個季度為四個階段，采用階段編號與季度順序一致。設sk

為第k季初的庫存量，則s1=s5=0；

設xk

為第k季的生產量，設yk

為第k季的訂貨量；

sk

，xk

，yk

都取實數，狀態(tài)轉移方程為sk+1=sk+xk-yk；

目標函數為6.5.2生產存儲問題7/16/2024第一步：(第四季度)總效果f4(s4,x4)=0.005x42+s4由邊界條件有：s5=s4+x4–y4=0，解得：x4*=1200–s4將x4*代入

f4(s4,x4)得：

f4*(s4)=0.005(1200–s4)2+s4=7200–11s4+0.005s42第二步：(第三、四季度)總效果f3(s3,x3)=0.005x32+s3+f4*(s4)將s4=s3+x3–500代入f3(s3,x3)得：6.5.2生產存儲問題7/16/2024第三步：(第二、三、四季度)總效果f2(s2,x2)=0.005x22+s2+f3*(s3)

將s3=s2+x2–700代入f2(s2,x2)得：162注意：最優(yōu)階段總效果僅是當前狀態(tài)的函數，與其后的決策無關。6.5.2生產存儲問題7/16/2024第四步：(第一、二、三、四季度)總效果f1(s1,x1)=0.005x12+s1+f2*(s2)

將s2=s1+x1–600=x1–600代入f1(s1,x1)得：163由此回溯，得最優(yōu)生產–庫存方案：

x1*=600，s2*=0；x2*=700，s3*=0；x3*=800，s4*=300；

x4*=900。6.5.2生產存儲問題7/16/2024凈費用=維護費+更新費-殘值收益6.5.3設備更新問題7/16/20246.5.3設備更新問題7/16/2024在時刻2購買的機器可以在時刻3，時刻4，或時刻5去交易更換。因此，在時刻3購買的機器可以在時刻4或時刻5去交易更換。因此，對在時刻4購買的機器，只有一個合理的決策，就是將機器使用到時刻5然后賣掉獲得殘值。因此，6.5.3設備更新問題7/16/2024在時刻0購買的機器可以在時刻1，時刻2，或時刻3去交易更換。因此，在時刻1購買的機器可以在時刻2，時刻3，或時刻4去交易更換。因此，6.5.3設備更新問題7/16/2024對于設備更新問題，還有另外一種建立動態(tài)規(guī)劃的辦法。

階段:

時刻

t

狀態(tài):

在時刻

t機器的年齡

6.5.3設備更新問題7/16/2024某電子系統(tǒng)由若干個部件串聯(lián)而成，如果其中一個部件失靈整個系統(tǒng)便會失靈。為了提高整個系統(tǒng)的可靠性，各部件可以采用并聯(lián)相同元件的設計方案。例如部件1可以由若干個元件并聯(lián)而成。這樣部件1的可靠性就提高了，但同時成本也增加了。那么在整個系統(tǒng)成本是有定額的情況下，如何設計并聯(lián)方案（即各部件分別由多少相同元件并聯(lián)而成）才能使整個系統(tǒng)的可靠性最大，這就是一個系統(tǒng)可靠性優(yōu)化的問題。6.5.3復雜系統(tǒng)可靠性問題7/16/2024并聯(lián)元件數目部件1部件2部件3部件410.70.50.70.620.80.70.90.730.90.80.950.9各部件安裝不同數目原件的成本表并聯(lián)元件數目部件1部件2部件3部件4110201020220403030330504040某電子系統(tǒng)由四個部件串聯(lián)構成，四個部件分別是采用不同數量元件并聯(lián)的，其工作的可靠性如表所示。若系統(tǒng)成本總定額為100，求最大可靠性的串聯(lián)方案？6.5.3復雜系統(tǒng)可靠性問題7/16/2024（1）按構成系統(tǒng)的部件數量，確定動態(tài)規(guī)劃有4個階段，即k=4（2）各階段的狀態(tài)參數為在各階段可用的成本總值，即在第k階段允許使用的總費用（3）各階段的決策變量為第k個部件采用的元件數（4）狀態(tài)轉換方程為6.5.3復雜系統(tǒng)可靠性問題7/16/2024s3u3=x3P3(x3)s4f4(s4)P3(x3)·f4(s4)u3*10≤s3≤2910.70≤s4≤190030≤s3≤39120.70.920≤s4≤290≤s4≤90.600.7×0.6=0.420140≤s3≤491230.70.90.9530≤s4≤3910≤s4≤190≤s4≤90.7000.7×0.7=0.4900150≤s3≤591230.70.90.9540≤s4≤4920≤s4≤2910≤s4≤190.90.600.7×0.9=0.630.9×0.6=0.541第三階段計算表k=36.5.3復雜系統(tǒng)可靠性問題7/16/2024s3u3=x3P3(x3)s4f4(s4