最優(yōu)化技術基礎

關于最優(yōu)化技術基礎第1頁，講稿共27頁，2023年5月2日，星期三▲最優(yōu)策略：對應于一個策略，可以由一個量化的指標來確定這個策略對應的效果，不同的策略有各自的效果。在所有可供選擇的策略中，對應效果最好的策略稱為最優(yōu)策略。

多階段決策過程最優(yōu)化的目標是要達到整個活動過程的總體效果最優(yōu)。由于各段決策間有機地聯(lián)系著，本段決策的執(zhí)行將影響到下一段的決策，以至于影響總體效果，所以決策者在每段決策時不應僅考慮本階段最優(yōu)，還應考慮對最終目標的影響，從而作出對全局來講是最優(yōu)的決策。動態(tài)規(guī)劃就是符合這種要求的一種決策方法。應指出，動態(tài)規(guī)劃不象線性規(guī)劃那樣有一個標準的數(shù)學表達式和明確定義的一組規(guī)則，而必須對具體問題進行具體分析處理，除了要對基本概念和方法正確理解外，應以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。第2頁，講稿共27頁，2023年5月2日，星期三(2)多階段決策問題舉例

a)工廠生產過程:為了取得全年最佳經濟效益，在全年的生產過程中，根據(jù)市場需求，逐月或者逐季度地根據(jù)庫存和需求情況決定生產計劃安排。

b)設備更新問題:需要綜合權衡決定設備的使用年限，使總的經濟效益最好

c)連續(xù)生產過程的控制問題:一般化工生產過程中，常包含一系列完成生產過程的設備，前一工序設備的輸出則是后一工序設備的輸入，因此，應該如何根據(jù)各工序的運行工況，控制生產過程中各設備的輸入和輸出，以使總產量最大。以上問題的發(fā)展過程都與時間因素有關，因此階段的劃分常取時間區(qū)段來表示，并且各個階段上的決策往往也與時間因素有關，這就是“動態(tài)”的含義，所以把處理這類問題的方法稱為動態(tài)規(guī)劃方法。第3頁，講稿共27頁，2023年5月2日，星期三d）資源分配問題:某工業(yè)部門擬對其所屬企業(yè)進行稀缺資源分配，為此需要制定出收益最大的資源分配方案。這種問題與時間因素無關，不屬動態(tài)決策，但我們可以人為地規(guī)定一個資源分配的階段和順序，從而使其變成一個多階段決策問題。

e）運輸網絡問題:

運輸網絡連線上的數(shù)字表示兩地距離(也可以是運費、時間等)，要求從A

至E的最短路線。這種運輸網絡問題也是靜態(tài)決策問題。但是，按照網絡中點的分布，可以把它分為幾個階段，而作為多階段決策問題來研究。第4頁，講稿共27頁，2023年5月2日，星期三

(3)動態(tài)規(guī)劃求解的多階段決策問題的特點通常多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實現(xiàn)的。一般情況下，系統(tǒng)在某個階段的狀態(tài)轉移除與本階段的狀態(tài)和決策有關外，還可能與系統(tǒng)過去經歷的狀態(tài)和決策有關。因此，問題的求解就比較困難復雜。適合于用動態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策問題，即具有“無后效性”(馬爾柯夫性)的多階段決策過程。所謂無后效性，是指系統(tǒng)從某個階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經歷的狀態(tài)和決策(歷史)無關。多階段決策過程特點:狀態(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第5頁，講稿共27頁，2023年5月2日，星期三(4)動態(tài)規(guī)劃方法導引例1：為了說明動態(tài)規(guī)劃的基本方法和特點，以上面運輸網絡圖為例,討論求最短路問題的方法。

第一種方法枚舉法.它的基本思想是列舉出所有可能發(fā)生的方案和結果，再一一比較，求出最優(yōu)方案。這里從A到E的路程可以分為5個階段。各階段走法:第1段有3種，第2段各有3種，第3段各有2種，第4段各1種，因此共有3×3×2×1＝18條可能的路線，分別算出各條路線的距離進行比較，可知最優(yōu)路線是A

B2

C1

D1

E,最短距離是19．顯然，如果組成網絡的節(jié)點很多時，用窮舉法求最優(yōu)路線的計算量將會十分龐大，其中包含許多重復計算．枚舉法雖可找出最優(yōu)方案，但不是個好算法第6頁，講稿共27頁，2023年5月2日，星期三

第二種方法:“局部最優(yōu)路徑”法.說某人從某站出發(fā)，他選擇“逢近便走”的決策，以為只要“局部最優(yōu)”,就會達到”“整體最優(yōu)”，所取決策必是A

B3

C3

D1

E,但全程長度是25；顯然，這種方法的結果常是錯誤的．局部最優(yōu)法則是錯誤方法.

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

首先將問題劃分為5個階段，每次的選擇總是綜合后繼過程的一并最優(yōu)進行考慮，在各段所有可能狀態(tài)的最優(yōu)后繼過程都已求得的情況下，全程的最優(yōu)路線便也隨之得到。動態(tài)規(guī)劃方法總是從過程的最后階段開始考慮，然后逆著實際過程發(fā)展的順序，逐段向前遞推計算直至始點。動態(tài)規(guī)劃方法屬較科學有效的算法，計算過程中，系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合，從而使計算量比枚舉法大為減少。第7頁，講稿共27頁，2023年5月2日，星期三

2.動態(tài)規(guī)劃的基本概念

使用動態(tài)規(guī)劃方法解決多階段決策問題，首先要將實際問題寫成動態(tài)規(guī)劃模型，需要對動態(tài)規(guī)劃的一些基本術語加以說明和定義：

1.階段為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰當?shù)貏澐譃槿舾蓚€相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段。一個階段，就是需要作出一個決策的子問題，通常，階段是按決策進行的時間或空間上先后順序劃分的。

2.狀態(tài)和狀態(tài)變量用以描述系統(tǒng)在某特定的時間與空間域中所處位置及運動特征的量，稱為狀態(tài)。每個階段的狀態(tài)可分為初始狀態(tài)和終止狀態(tài)，階段k的初始狀態(tài)記作sk，終止狀態(tài)記為sk+1。但通常定義階段的狀態(tài)即指其初始狀態(tài)，故階段k的終止狀態(tài)sk+1為階段k+1的初始狀態(tài)。描述過程k的狀態(tài)變量稱為狀態(tài)變量sk

，其取值范圍稱為可能狀態(tài)集Sk,即sk∈Sk。第8頁，講稿共27頁，2023年5月2日，星期三3.決策和決策變量決策是狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)作出的選擇。描述決策變化的量稱之決策變量，和狀態(tài)變量一樣，決策變量可以用一個數(shù)或一向量來描述，也可以是狀態(tài)變量的函數(shù)，記以uk=uk(sk)，表示階段k狀態(tài)sk時的決策變量。決策變量的取值也有一定的允許范圍，稱之允許決策集合Uk(sk),uk(sk)∈Uk(sk)。

4.策略全過程策略(Policy)是依次進行的全部n個階段決策構成的決策序列，表示為p1,n{u1,u2,…,un};從k階段到第n階段，依次構成的決策序列稱為k部子策略,表示為pk,n{uk,uk+1,…,un}，顯然當k=1時的k部子策略就是全過程策略。在實際問題中，由于在各個階段可供選擇的決策有許多個，因此，它們的不同組合就構成了許多可供選擇的決策序列(策略)，它們組成”允許策略集”，記作P1,n

，從中找出具有最優(yōu)效果的策略稱為最優(yōu)策略。第9頁，講稿共27頁，2023年5月2日，星期三5.狀態(tài)轉移方程系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結果是系統(tǒng)狀態(tài)的轉移，即系統(tǒng)由階段k的初始狀態(tài)sk轉移到終止狀態(tài)sk+1，或者說由k階段的狀態(tài)sk轉移到了k+1階段的狀態(tài)sk+1。對于具有無后效性的多階段決策過程,系統(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)的這種轉移，用數(shù)學公式描述即有：(1)

式(1)稱為多階段決策過程的狀態(tài)轉移方程。有些問題的狀態(tài)轉移方程不一定存在數(shù)學表達式，但是它們的狀態(tài)轉移，還是有一定規(guī)律可循的。第10頁，講稿共27頁，2023年5月2日，星期三6.指標函數(shù)和最優(yōu)解指標函數(shù)是用來衡量策略效果的某種數(shù)量指標。對不同問題，指標函數(shù)可以是諸如費用、成本、產值、利潤、產量、耗量、距離、時間、效用等等。(1)階段指標函數(shù):用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時的指標，它就是第k段指標函數(shù)，簡記為gk

。(2)過程指標函數(shù)（也稱目標函數(shù)）:用Rk(sk,uk)表示第k子過程的指標函數(shù)。如運輸網絡圖的Rk(sk,uk)表示處于第k段sk狀態(tài)且所作決策為uk時，從sk點到終點E的距離。由此可見，Rk(sk,uk)不僅跟當前狀態(tài)sk有關，還跟該子過程策略pk(sk)有關，因此它是sk和pk(sk)的函數(shù)，應表示為:第11頁，講稿共27頁，2023年5月2日，星期三

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

與它相應的子策略稱為sk狀態(tài)下的最優(yōu)子策略，簡記為:

特別當k=1且s1取值唯一時，f1(s1)就是問題的最優(yōu)值，而p1*就是最優(yōu)策略。我們把最優(yōu)策略和最優(yōu)值統(tǒng)稱為問題的最優(yōu)解。第12頁，講稿共27頁，2023年5月2日，星期三7.多階段決策問題的數(shù)學模型綜上所述，適于應用動態(tài)規(guī)劃方法求解的一類多階段決策問題，亦即具有無后效性的多階段決策問題的數(shù)學模型呈以下形式:（5）模型說明對于給定的多階段決策過程，求取一個最優(yōu)策略(決策序列)，使之既滿足全部約束條件，又使目標函數(shù)取得極值，同時，執(zhí)行該最優(yōu)策略時，過程狀態(tài)演變序列即最優(yōu)路線,按上述定義，所謂最優(yōu)決策是指它們在全過程上整體最優(yōu)第13頁，講稿共27頁，2023年5月2日，星期三8.最優(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*中，即為第14頁，講稿共27頁，2023年5月2日，星期三貝爾曼最優(yōu)化原理概念:

如圖,如果已經給出從點A到點C的最優(yōu)軌跡，那么從任一中間點B到點C的部分軌跡必須是從B到C的最優(yōu)軌跡。

設給出路線Ⅰ-Ⅱ是從A到C的最優(yōu)路線，根據(jù)貝爾曼原理，則路線Ⅱ是從B到C的最優(yōu)路線。[證]:用反證法,假設某條其它路線，例如Ⅱ’是從B到C的最優(yōu)路線，那么，路線I-Ⅱ’比路線I-Ⅱ有更小的費用。但這與I-Ⅱ是從A到C最優(yōu)路線的前提相矛盾，因此Ⅱ必是從B到C的最優(yōu)路線貝爾曼闡述:“一個最優(yōu)策略有這樣的特性，不論初始狀態(tài)和初始決策如何，相對于第一個決策所形成的狀態(tài)來說，余下的決策必定構成一個最優(yōu)策略”。第15頁，講稿共27頁，2023年5月2日，星期三(1)應將實際問題恰當?shù)胤指畛蒼個子問題(n個階段)。通常是根據(jù)時間或空間而劃分的。(2)正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，又能滿足無后效性．動態(tài)規(guī)劃中的狀態(tài)變量必須具備以下三個特征：

a)要能夠正確地描述受控過程的變化特征。

b)要滿足無后效性。即如果在某個階段狀態(tài)已經給定，那么在該階段以后，過程的發(fā)展不受前面各段狀態(tài)的影響，如果所選的變量不具備無后效性，就不能作為狀態(tài)變量來構造動態(tài)規(guī)劃的模型。

c)要滿足可知性。即所規(guī)定的各段狀態(tài)變量的值，可以直接或間接地測算得到。3.動態(tài)規(guī)劃方法的基本步驟第16頁，講稿共27頁，2023年5月2日，星期三(3)正確地定義決策變量及各階段的允許決策集合Uk(sk).根據(jù)經驗，一般將問題中待求的量，選作動態(tài)規(guī)劃模型中的決策變量?；蛘咴诎鸯o態(tài)規(guī)劃模型(如線性與非線性規(guī)劃)轉換為動態(tài)規(guī)劃模型時，常取前者的變量xj為后者的決策變量uk。(4)能夠正確地寫出狀態(tài)轉移方程。如果給定第k階段狀態(tài)變量sk的值，則該段的決策變量uk一經確定，第k+1段的狀態(tài)變量sk+1的值也就完全確定，即有sk+1=Tk(sk,uk)(5)正確地構造出目標函數(shù).例如常見的指標函數(shù)是取各段指標和的形式

其中表示第i階段的指標，它顯然滿足遞推關系：第17頁，講稿共27頁，2023年5月2日，星期三求最短路徑4.動態(tài)規(guī)劃方法應用舉例第18頁，講稿共27頁，2023年5月2日，星期三

將問題分成五個階段，第k階段到達的具體地點用狀態(tài)變量xk表示，例如：x2=B3表示第二階段到達位置B3，等等。這里狀態(tài)變量取字符值而不是數(shù)值。

將決策定義為到達下一站所選擇的路徑，例如目前的狀態(tài)是x2=B3，這時決策允許集合包含三個決策，它們是

D2(x2)=D2(B3)={B3C1,B3C2,B3C3}

最優(yōu)指標函數(shù)fk(xk)表示從目前狀態(tài)到E的最短路徑。

終端條件為

f5(x5)=f5(E)=0

其含義是從E到E的最短路徑為0。第19頁，講稿共27頁，2023年5月2日，星期三從f5(x5)到f4(x4)的遞推過程用下表表示：

第四階段的遞推方程為：

在上表