最優(yōu)化技術(shù)基礎(chǔ)

關(guān)于最優(yōu)化技術(shù)基礎(chǔ)第一頁，共二十七頁，2022年，8月28日▲最優(yōu)策略：對(duì)應(yīng)于一個(gè)策略，可以由一個(gè)量化的指標(biāo)來確定這個(gè)策略對(duì)應(yīng)的效果，不同的策略有各自的效果。在所有可供選擇的策略中，對(duì)應(yīng)效果最好的策略稱為最優(yōu)策略。

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

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

b)設(shè)備更新問題:需要綜合權(quán)衡決定設(shè)備的使用年限，使總的經(jīng)濟(jì)效益最好

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

e）運(yùn)輸網(wǎng)絡(luò)問題:

運(yùn)輸網(wǎng)絡(luò)連線上的數(shù)字表示兩地距離(也可以是運(yùn)費(fèi)、時(shí)間等)，要求從A

至E的最短路線。這種運(yùn)輸網(wǎng)絡(luò)問題也是靜態(tài)決策問題。但是，按照網(wǎng)絡(luò)中點(diǎn)的分布，可以把它分為幾個(gè)階段，而作為多階段決策問題來研究。第四頁，共二十七頁，2022年，8月28日

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

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

B2

C1

D1

E,最短距離是19．顯然，如果組成網(wǎng)絡(luò)的節(jié)點(diǎn)很多時(shí)，用窮舉法求最優(yōu)路線的計(jì)算量將會(huì)十分龐大，其中包含許多重復(fù)計(jì)算．枚舉法雖可找出最優(yōu)方案，但不是個(gè)好算法第六頁，共二十七頁，2022年，8月28日

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

B3

C3

D1

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

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

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

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

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

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

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

，其取值范圍稱為可能狀態(tài)集Sk,即sk∈Sk。第八頁，共二十七頁，2022年，8月28日3.決策和決策變量決策是狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對(duì)下一階段狀態(tài)作出的選擇。描述決策變化的量稱之決策變量，和狀態(tài)變量一樣，決策變量可以用一個(gè)數(shù)或一向量來描述，也可以是狀態(tài)變量的函數(shù)，記以u(píng)k=uk(sk)，表示階段k狀態(tài)sk時(shí)的決策變量。決策變量的取值也有一定的允許范圍，稱之允許決策集合Uk(sk),uk(sk)∈Uk(sk)。

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

，從中找出具有最優(yōu)效果的策略稱為最優(yōu)策略。第九頁，共二十七頁，2022年，8月28日5.狀態(tài)轉(zhuǎn)移方程系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結(jié)果是系統(tǒng)狀態(tài)的轉(zhuǎn)移，即系統(tǒng)由階段k的初始狀態(tài)sk轉(zhuǎn)移到終止?fàn)顟B(tài)sk+1，或者說由k階段的狀態(tài)sk轉(zhuǎn)移到了k+1階段的狀態(tài)sk+1。對(duì)于具有無后效性的多階段決策過程,系統(tǒng)由階段k到階段k+1的狀態(tài)轉(zhuǎn)移完全由階段k的狀態(tài)sk和決策uk(sk)所確定，與系統(tǒng)過去的狀態(tài)s1,s2,…,sk-1及其決策u1(s1),u2(s2)…uk-1(sk-1)無關(guān)。系統(tǒng)狀態(tài)的這種轉(zhuǎn)移，用數(shù)學(xué)公式描述即有：(1)

式(1)稱為多階段決策過程的狀態(tài)轉(zhuǎn)移方程。有些問題的狀態(tài)轉(zhuǎn)移方程不一定存在數(shù)學(xué)表達(dá)式，但是它們的狀態(tài)轉(zhuǎn)移，還是有一定規(guī)律可循的。第十頁，共二十七頁，2022年，8月28日6.指標(biāo)函數(shù)和最優(yōu)解指標(biāo)函數(shù)是用來衡量策略效果的某種數(shù)量指標(biāo)。對(duì)不同問題，指標(biāo)函數(shù)可以是諸如費(fèi)用、成本、產(chǎn)值、利潤(rùn)、產(chǎn)量、耗量、距離、時(shí)間、效用等等。(1)階段指標(biāo)函數(shù):用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時(shí)的指標(biāo)，它就是第k段指標(biāo)函數(shù)，簡(jiǎn)記為gk

。(2)過程指標(biāo)函數(shù)（也稱目標(biāo)函數(shù)）:用Rk(sk,uk)表示第k子過程的指標(biāo)函數(shù)。如運(yùn)輸網(wǎng)絡(luò)圖的Rk(sk,uk)表示處于第k段sk狀態(tài)且所作決策為uk時(shí)，從sk點(diǎn)到終點(diǎn)E的距離。由此可見，Rk(sk,uk)不僅跟當(dāng)前狀態(tài)sk有關(guān)，還跟該子過程策略pk(sk)有關(guān)，因此它是sk和pk(sk)的函數(shù)，應(yīng)表示為:第十一頁，共二十七頁，2022年，8月28日

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

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

特別當(dāng)k=1且s1取值唯一時(shí)，f1(s1)就是問題的最優(yōu)值，而p1*就是最優(yōu)策略。我們把最優(yōu)策略和最優(yōu)值統(tǒng)稱為問題的最優(yōu)解。第十二頁，共二十七頁，2022年，8月28日7.多階段決策問題的數(shù)學(xué)模型綜上所述，適于應(yīng)用動(dòng)態(tài)規(guī)劃方法求解的一類多階段決策問題，亦即具有無后效性的多階段決策問題的數(shù)學(xué)模型呈以下形式:（5）模型說明對(duì)于給定的多階段決策過程，求取一個(gè)最優(yōu)策略(決策序列)，使之既滿足全部約束條件，又使目標(biāo)函數(shù)取得極值，同時(shí)，執(zhí)行該最優(yōu)策略時(shí)，過程狀態(tài)演變序列即最優(yōu)路線,按上述定義，所謂最優(yōu)決策是指它們?cè)谌^程上整體最優(yōu)第十三頁，共二十七頁，2022年，8月28日8.最優(yōu)化原理（貝爾曼最優(yōu)化原理）作為一個(gè)全過程的最優(yōu)策略具有這樣的性質(zhì)：對(duì)于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策略。該原理的具體解釋是，若某一全過程最優(yōu)策略為：

則對(duì)上述策略中所隱含的任一狀態(tài)而言，第k子過程上對(duì)應(yīng)于該狀態(tài)的最優(yōu)策略必然包含在上述全過程最優(yōu)策略p1*中，即為第十四頁，共二十七頁，2022年，8月28日貝爾曼最優(yōu)化原理概念:

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

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

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

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

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

其中表示第i階段的指標(biāo)，它顯然滿足遞推關(guān)系：第十七頁，共二十七頁，2022年，8月28日求最短路徑4.動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例第十八頁，共二十七頁，2022年，8月28日

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

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

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

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

終端條件為

f5(x5)=f5(E)=0

其含義是從E到E的最短路徑為0。第十九頁，共二十七頁，2022年，8月28日從f5(x5)到f4(x4)的遞推過程用下表表示：