動(dòng)態(tài)規(guī)劃算法原理與的應(yīng)用

5/5動(dòng)態(tài)規(guī)劃算法原理與的應(yīng)用動(dòng)態(tài)規(guī)劃算法原理及其應(yīng)用研究

系別：xxx姓名：xxx指導(dǎo)教員：xxx

2012年5月20日

學(xué)性質(zhì)做出了巨大的貢獻(xiàn)。

動(dòng)態(tài)規(guī)劃問(wèn)世以來(lái)，在工程技術(shù)、經(jīng)濟(jì)管理等社會(huì)各個(gè)領(lǐng)域都有著廣泛的應(yīng)用，并且獲得了顯著的效果。在經(jīng)濟(jì)管理方面，動(dòng)態(tài)規(guī)劃可以用來(lái)解決最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)調(diào)度問(wèn)題、庫(kù)存管理問(wèn)題、排序問(wèn)題、設(shè)備更新問(wèn)題以及生產(chǎn)過(guò)程最優(yōu)控制問(wèn)題等，是經(jīng)濟(jì)管理中一種重要的決策技術(shù)。許多規(guī)劃問(wèn)題用動(dòng)態(tài)規(guī)劃的方法來(lái)處理，常比線性規(guī)劃或非線性規(guī)劃更有效。特別是對(duì)于離散的問(wèn)題，由于解析數(shù)學(xué)無(wú)法發(fā)揮作用，動(dòng)態(tài)規(guī)劃便成為了一種非常有用的工具。

動(dòng)態(tài)規(guī)劃可以按照決策過(guò)程的演變是否確定分為確定性動(dòng)態(tài)規(guī)劃和隨機(jī)性動(dòng)態(tài)規(guī)劃；也可以按照決策變量的取值是否連續(xù)分為連續(xù)性動(dòng)態(tài)規(guī)劃和離散性動(dòng)態(tài)規(guī)劃。雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過(guò)程的優(yōu)化問(wèn)題，但是一些與時(shí)間無(wú)關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進(jìn)時(shí)間因素，把它視為多階段決策過(guò)程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。

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

一般來(lái)說(shuō)，只要問(wèn)題可以劃分成規(guī)模更小的子問(wèn)題，并且原問(wèn)題的最優(yōu)解中包含了子問(wèn)題的最優(yōu)解，則可以考慮用動(dòng)態(tài)規(guī)劃解決。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此，動(dòng)態(tài)規(guī)劃是一種將問(wèn)題實(shí)例分解為更小的、相似的子問(wèn)題，并存儲(chǔ)子問(wèn)題的解而避免計(jì)算重復(fù)的子問(wèn)題，以解決最優(yōu)化問(wèn)題的算法策略。由此可知，動(dòng)態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問(wèn)題實(shí)例歸納為更小的、相似的子問(wèn)題，并通過(guò)求解子問(wèn)題產(chǎn)生一個(gè)全局最優(yōu)解。其中貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問(wèn)題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個(gè)子問(wèn)題是獨(dú)立的(即不包含公共的子子問(wèn)題)，因此一旦遞歸地求出各子問(wèn)題的解后，便可自下而上地將子問(wèn)題的解合并成問(wèn)題的解。但不足的是，如果當(dāng)前選擇可能要依賴子問(wèn)題的解時(shí)，則難以通過(guò)局部的貪心策略達(dá)到全局最優(yōu)解；如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題。解決上述問(wèn)題的辦法是利用動(dòng)態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問(wèn)題，這類問(wèn)題會(huì)有多種可能的

解，每個(gè)解都有一個(gè)值，而動(dòng)態(tài)規(guī)劃找出其中最優(yōu)(最大或最小)值的解。若存在若干個(gè)取最優(yōu)值的解的話，它只取其中的一個(gè)。在求解過(guò)程中，該方法也是通過(guò)求解局部子問(wèn)題的解達(dá)到全局最優(yōu)解，但與分治法和貪心法不同的是，動(dòng)態(tài)規(guī)劃允許這些子問(wèn)題不獨(dú)立，也允許其通過(guò)自身子問(wèn)題的解作出選擇，該方法對(duì)每一個(gè)子問(wèn)題只解一次，并將結(jié)果保存起來(lái)，避免每次碰到時(shí)都要重復(fù)計(jì)算。

因此，動(dòng)態(tài)規(guī)劃法所針對(duì)的問(wèn)題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問(wèn)題樹中的子問(wèn)題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問(wèn)題，只在第一次遇到時(shí)加以求解，并把答案保存起來(lái)，讓以后再遇到時(shí)直接引用，不必重新求解。

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

動(dòng)態(tài)規(guī)劃的數(shù)學(xué)描述離不開它的一些基本概念與符號(hào)，因此有必要在介紹多階段決策過(guò)程的數(shù)學(xué)描述的基礎(chǔ)上，系統(tǒng)地介紹動(dòng)態(tài)規(guī)劃的一些基本概念。

多階段決策問(wèn)題

如果一類活動(dòng)過(guò)程可以分為若干個(gè)互相聯(lián)系的階段，在每一個(gè)階段都需作出決策，一個(gè)階段的決策確定以后，常常影響到下一個(gè)階段的決策，從而就完全確定了一個(gè)過(guò)程的活動(dòng)路線，則稱它為多階段決策問(wèn)題。

各個(gè)階段的決策構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。每一個(gè)階段都有若干個(gè)決策可供選擇，因而就有許多策略供我們選取，對(duì)應(yīng)于一個(gè)策略可以確定活動(dòng)的效果，這個(gè)效果可以用數(shù)量來(lái)確定。策略不同，效果也不同，多階段決策問(wèn)題，就是要在可以選擇的那些策略中間，選取一個(gè)最優(yōu)策略，使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果.

動(dòng)態(tài)規(guī)劃問(wèn)題中的術(shù)語(yǔ)

階段：把所給求解問(wèn)題的過(guò)程恰當(dāng)?shù)胤殖扇舾蓚€(gè)相互聯(lián)系的階段，以便于求解，過(guò)程不同，階段數(shù)就可能不同．描述階段的變量稱為階段變量。在多數(shù)情況下，階段變量是離散的，用k表示。此外，也有階段變量是連續(xù)的情形。如果過(guò)程可以在任何時(shí)刻作出決策，且在任意兩個(gè)不同的時(shí)刻之間允許有無(wú)窮多個(gè)決策

時(shí)，階段變量就是連續(xù)的。

狀態(tài)：狀態(tài)表示每個(gè)階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉(zhuǎn)移，也稱為不可控因素。在上面的例子中狀態(tài)就是某階段的出發(fā)位置，它既是該階段某路的起點(diǎn)，同時(shí)又是前一階段某支路的終點(diǎn)。

過(guò)程的狀態(tài)通?？梢杂靡粋€(gè)或一組數(shù)來(lái)描述，稱為狀態(tài)變量。一般，狀態(tài)是離散的，但有時(shí)為了方便也將狀態(tài)取成連續(xù)的。當(dāng)然，在現(xiàn)實(shí)生活中，由于變量形式的限制，所有的狀態(tài)都是離散的，但從分析的觀點(diǎn)，有時(shí)將狀態(tài)作為連續(xù)的處理將會(huì)有很大的好處。此外，狀態(tài)可以有多個(gè)分量(多維情形)，因而用向量來(lái)代表；而且在每個(gè)階段的狀態(tài)維數(shù)可以不同。

無(wú)后效性：我們要求狀態(tài)具有下面的性質(zhì)：如果給定某一階段的狀態(tài)，則在這一階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過(guò)程也就確定了。換句話說(shuō)，過(guò)程的每一次實(shí)現(xiàn)可以用一個(gè)狀態(tài)序列表示，在前面的例子中每階段的狀態(tài)是該線路的始點(diǎn)，確定了這些點(diǎn)的序列，整個(gè)線路也就完全確定。從某一階段以后的線路開始，當(dāng)這段的始點(diǎn)給定時(shí)，不受以前線路（所通過(guò)的點(diǎn)）的影響。狀態(tài)的這個(gè)性質(zhì)意味著過(guò)程的歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它的未來(lái)的發(fā)展，這個(gè)性質(zhì)稱為無(wú)后效性。

決策：一個(gè)階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個(gè)狀態(tài)的一種選擇（行動(dòng)）稱為決策。在最優(yōu)控制中，也稱為控制。在許多間題中，決策可以自然而然地表示為一個(gè)數(shù)或一組數(shù)。不同的決策對(duì)應(yīng)著不同的數(shù)值。描述決策的變量稱決策變量，因狀態(tài)滿足無(wú)后效性，故在每個(gè)階段選擇決策時(shí)只需考慮當(dāng)前的狀態(tài)而無(wú)須考慮過(guò)程的歷史。決策變量的范圍稱為允許決策集合。

策略：由每個(gè)階段的決策組成的序列稱為策略。對(duì)于每一個(gè)實(shí)際的多階段決策過(guò)程，可供選取的策略有一定的范圍限制，這個(gè)范圍稱為允許策略集合。允許策略集合中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。

給定k階段狀態(tài)變量x(k)的值后，如果這一階段的決策變量一經(jīng)確定，第k+1階段的狀態(tài)變量x(k+1)也就完全確定，即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變化而變化，那么可以把這一關(guān)系看成(x(k)，u(k))與x(k+1)確

定的對(duì)應(yīng)關(guān)系，用x(k+1)=Tk(x(k),u(k))表示。這是從k階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。

最優(yōu)性原理:作為整個(gè)過(guò)程的最優(yōu)策略，它滿足：相對(duì)前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。

4.動(dòng)態(tài)規(guī)劃求解的基本步驟

動(dòng)態(tài)規(guī)劃所處理的問(wèn)題是一個(gè)多階段決策問(wèn)題，一般由初始狀態(tài)開始，通過(guò)對(duì)中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過(guò)程的一條活動(dòng)路線(通常是求最優(yōu)的活動(dòng)路線)。如圖所示。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟。

初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結(jié)束狀態(tài)

動(dòng)態(tài)規(guī)劃決策過(guò)程示意圖

(1)劃分階段：，按照問(wèn)題的時(shí)間或空間特征，把問(wèn)題分為若干個(gè)階段。在劃分階段時(shí)，注意劃分后的階段一定要是有序的或者是可排序的，否則問(wèn)題就無(wú)法求解。

(2)確定狀態(tài)和狀態(tài)變量：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)。當(dāng)然，狀態(tài)的選擇要滿足無(wú)后效性。

(3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過(guò)來(lái)做，根據(jù)相鄰兩段各狀態(tài)之間的關(guān)系來(lái)確定決策。

(4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。

(5)程序設(shè)計(jì)實(shí)現(xiàn)：動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。

根據(jù)上述動(dòng)態(tài)規(guī)劃設(shè)計(jì)的步驟，可得到大體解題框架如圖所示。

動(dòng)態(tài)規(guī)劃設(shè)計(jì)的一般模式圖

上述提供了動(dòng)態(tài)規(guī)劃方法的一般模式，對(duì)于簡(jiǎn)單的動(dòng)態(tài)規(guī)劃問(wèn)題，可以按部就班地進(jìn)行動(dòng)態(tài)規(guī)劃的設(shè)計(jì)。下面，給出一個(gè)利用動(dòng)態(tài)規(guī)劃方法求解的典型例子。

上圖示出了一個(gè)數(shù)字三角形寶塔。數(shù)字三角形中的數(shù)字為不超過(guò)100的整數(shù)?，F(xiàn)規(guī)定從最頂層走到最底層，每一步可沿左斜線向下或右斜線向下走。

任務(wù)一：假設(shè)三角形行數(shù)≤10，鍵盤輸入一個(gè)確定的整數(shù)值M，編程確定是否存在一條路徑，使得沿著該路徑所經(jīng)過(guò)的數(shù)字的總和恰為M，若存在則給出所有路徑，若不存在，則輸出“NOAnswer!”字樣。

任務(wù)二：假設(shè)三角形行數(shù)≤100，編程求解從最頂層走到最底層的一條路徑，使得沿著該路徑所經(jīng)過(guò)的數(shù)字的總和最大，輸出最大值。

輸人數(shù)據(jù)：由文件輸入數(shù)據(jù)，任務(wù)一中文件第一行是三角形的行數(shù)N和整數(shù)值M。以后的N行分別是從最頂層到最底層的每一層中的數(shù)字。任務(wù)二中文件數(shù)據(jù)格式同任務(wù)一，只是第一行中沒有整數(shù)值M。在例子中任務(wù)二的文件數(shù)據(jù)表示如下：

輸入：5

7輸出：輸出路徑和最大值

387或“NoAnswer!”字樣。

81038

2774810

452652744

圖3數(shù)字三角形45265

【分析】對(duì)于這一問(wèn)題，很容易想到用枚舉的方法去解決，即列舉出所有路徑并記錄每一條路徑所經(jīng)過(guò)的數(shù)字總和。然后判斷數(shù)字總和是否等于給定的整數(shù)值M或?qū)ふ页鲎畲蟮臄?shù)字總和，這一想法很直觀，而且對(duì)于任務(wù)一，由于數(shù)字三角形的行數(shù)不大(，02

=x是)(22Sf的極小值點(diǎn)

222

2222222()2226dhdxSxxxSx==-，2223xS=是22()fS的極大值點(diǎn)

于是：

2

322

|)(3227

4

22S

xSSf=*=

當(dāng)1=k時(shí)：

}

)({max)}({max)(311274

102210111

11

1xSxSfxSfSxSx-?=?=≤≤≤≤

同上可得：

9

464

14164

1

111

411

|2624436)36(==*=?=

==SxSSf

由279361

12=-=-=*

xSS，有18

273

2232

2=?=

=

*

Sx

由322

2