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

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

系別：xxx姓名：xxx指導教員：xxx

2012年5月20日

學性質(zhì)做出了巨大的貢獻。

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

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

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

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

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

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

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

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

多階段決策問題

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

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

動態(tài)規(guī)劃問題中的術(shù)語

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

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

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

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

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

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

策略：由每個階段的決策組成的序列稱為策略。對于每一個實際的多階段決策過程，可供選取的策略有一定的范圍限制，這個范圍稱為允許策略集合。允許策略集合中達到最優(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)確

定的對應(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)性原理:作為整個過程的最優(yōu)策略，它滿足：相對前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

任務(wù)二：假設(shè)三角形行數(shù)≤100，編程求解從最頂層走到最底層的一條路徑，使得沿著該路徑所經(jīng)過的數(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

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

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

222

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

于是：

2

322

|)(3227

4

22S

xSSf=*=

當1=k時：

}

)({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