matlab 動態(tài)規(guī)劃講義

1、第四章 動態(tài)規(guī)劃§1 引言1.1 動態(tài)規(guī)劃的發(fā)展及研究內(nèi)容動態(tài)規(guī)劃（dynamic programming）是運籌學(xué)的一個分支，是求解多階段決策問題的最優(yōu)化方法。20世紀(jì)50年代初R. E. Bellman等人在研究多階段決策過程(multistep decision process)的優(yōu)化問題時，提出了著名的最優(yōu)性原理（principle of optimality），把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法動態(tài)規(guī)劃。1957年出版了他的名著Dynamic Programming，這是該領(lǐng)域的第一本著作。動態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度

2、、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關(guān)的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃），只要人為地引進(jìn)時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。應(yīng)指出，動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特殊算法（如線性規(guī)劃是一種算法）。因而，它不象線性規(guī)劃那樣有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對具體問題進(jìn)行具體分析處理。因此，在學(xué)習(xí)時，除了要對基本概念和方法正確理解外

3、，應(yīng)以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。例1 最短路線問題 下面是一個線路網(wǎng)，連線上的數(shù)字表示兩點之間的距離（或費用）。試尋求一條由到距離最短（或費用最?。┑穆肪€。例2 生產(chǎn)計劃問題工廠生產(chǎn)某種產(chǎn)品，每單位（千件）的成本為1（千元），每次開工的固定成本為3（千元），工廠每季度的最大生產(chǎn)能力為6（千件）。經(jīng)調(diào)查，市場對該產(chǎn)品的需求量第一、二、三、四季度分別為2，3，2，4（千件）。如果工廠在第一、二季度將全年的需求都生產(chǎn)出來，自然可以降低成本（少付固定成本費），但是對于第三、四季度才能上市的產(chǎn)品需付存儲費，每季每千件的存儲費為0.5（千元）。還規(guī)定年初和年末這種產(chǎn)品均無庫存。試制定一

4、個生產(chǎn)計劃，即安排每個季度的產(chǎn)量，使一年的總費用（生產(chǎn)成本和存儲費）最少。1.2 決策過程的分類 根據(jù)過程的時間變量是離散的還是連續(xù)的，分為離散時間決策過程（discrete-time decision process）和連續(xù)時間決策過程（continuous-time decision process）；根據(jù)過程的演變是確定的還是隨機(jī)的，分為確定性決策過程（deterministic decision process）和隨機(jī)性決策過程（stochastic decision process），其中應(yīng)用最廣的是確定性多階段決策過程。§2 基本概念、基本方程和計算方法2.1 動態(tài)規(guī)劃的

5、基本概念和基本方程一個多階段決策過程最優(yōu)化問題的動態(tài)規(guī)劃模型通常包含以下要素。2.1.1 階段階段(step)是對整個過程的自然劃分。通常根據(jù)時間順序或空間順序特征來劃分階段，以便按階段的次序解優(yōu)化問題。階段變量一般用表示。在例1中由出發(fā)為，由出發(fā)為，依此下去從出發(fā)為，共個階段。在例2中按照第一、二、三、四季度分為，共四個階段。2.1.2 狀態(tài)狀態(tài)（state）表示每個階段開始時過程所處的自然狀況。它應(yīng)能描述過程的特征并且無后效性，即當(dāng)某階段的狀態(tài)變量給定時，這個階段以后過程的演變與該階段以前各階段的狀態(tài)無關(guān)。通常還要求狀態(tài)是直接或間接可以觀測的。描述狀態(tài)的變量稱狀態(tài)變量（state vari

6、able）。變量允許取值的范圍稱允許狀態(tài)集合(set of admissible states)。用表示第階段的狀態(tài)變量，它可以是一個數(shù)或一個向量。用表示第階段的允許狀態(tài)集合。在例1中可取，或?qū)⒍x為，則或，而。個階段的決策過程有個狀態(tài)變量，表示演變的結(jié)果。在例1中取，或定義為，即。根據(jù)過程演變的具體情況，狀態(tài)變量可以是離散的或連續(xù)的。為了計算的方便有時將連續(xù)變量離散化；為了分析的方便有時又將離散變量視為連續(xù)的。狀態(tài)變量簡稱為狀態(tài)。2.1.3 決策當(dāng)一個階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段的某個狀態(tài)，這種選擇手段稱為決策（decision），在最優(yōu)控制問題中也稱為控制（cont

7、rol）。描述決策的變量稱決策變量（decision variable），變量允許取值的范圍稱允許決策集合（set of admissible decisions）。用表示第階段處于狀態(tài)時的決策變量，它是的函數(shù)，用表示的允許決策集合。在例1中可取或，可記作，而。決策變量簡稱決策。2.1.4 策略決策組成的序列稱為策略（policy）。由初始狀態(tài)開始的全過程的策略記作，即.由第階段的狀態(tài)開始到終止?fàn)顟B(tài)的后部子過程的策略記作，即，.類似地，由第到第階段的子過程的策略記作.可供選擇的策略有一定的范圍，稱為允許策略集合(set of admissible policies)，用表示。2.1.5. 狀態(tài)

8、轉(zhuǎn)移方程在確定性過程中，一旦某階段的狀態(tài)和決策為已知，下階段的狀態(tài)便完全確定。用狀態(tài)轉(zhuǎn)移方程（equation of state transition）表示這種演變規(guī)律，寫作 （1）在例1中狀態(tài)轉(zhuǎn)移方程為。2.1.6. 指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)(objective function)是衡量過程優(yōu)劣的數(shù)量指標(biāo)，它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)，用表示，。指標(biāo)函數(shù)應(yīng)具有可分離性，即可表為的函數(shù)，記為并且函數(shù)對于變量是嚴(yán)格單調(diào)的。過程在第階段的階段指標(biāo)取決于狀態(tài)和決策，用表示。指標(biāo)函數(shù)由組成，常見的形式有：階段指標(biāo)之和，即，階段指標(biāo)之積，即，階段指標(biāo)之極大（或極小），即.這些形式下第

9、到第階段子過程的指標(biāo)函數(shù)為。根據(jù)狀態(tài)轉(zhuǎn)移方程指標(biāo)函數(shù)還可以表示為狀態(tài)和策略的函數(shù)，即。在給定時指標(biāo)函數(shù)對的最優(yōu)值稱為最優(yōu)值函數(shù)（optimal value function），記為，即，其中可根據(jù)具體情況取或。2.1.7 最優(yōu)策略和最優(yōu)軌線使指標(biāo)函數(shù)達(dá)到最優(yōu)值的策略是從開始的后部子過程的最優(yōu)策略，記作。是全過程的最優(yōu)策略，簡稱最優(yōu)策略（optimal policy）。從初始狀態(tài)出發(fā)，過程按照和狀態(tài)轉(zhuǎn)移方程演變所經(jīng)歷的狀態(tài)序列稱最優(yōu)軌線（optimal trajectory）。2.1.8 遞歸方程如下方程稱為遞歸方程 （2）在上述方程中，當(dāng)為加法時取；當(dāng)為乘法時，取。動態(tài)規(guī)劃遞歸方程是動態(tài)規(guī)劃的

10、最優(yōu)性原理的基礎(chǔ)，即：最優(yōu)策略的子策略，構(gòu)成最優(yōu)子策略。用狀態(tài)轉(zhuǎn)移方程（1）和遞歸方程（2）求解動態(tài)規(guī)劃的過程，是由逆推至，故這種解法稱為逆序解法。當(dāng)然，對某些動態(tài)規(guī)劃問題，也可采用順序解法。這時，狀態(tài)轉(zhuǎn)移方程和遞歸方程分別為：， 縱上所述，如果一個問題能用動態(tài)規(guī)劃方法求解，那么，我們可以按下列步驟，首先建立起動態(tài)規(guī)劃的數(shù)學(xué)模型：（i）將過程劃分成恰當(dāng)?shù)碾A段。（ii）正確選擇狀態(tài)變量，使它既能描述過程的狀態(tài)，又滿足無后效性，同時確定允許狀態(tài)集合。 （iii）選擇決策變量，確定允許決策集合。（iv）寫出狀態(tài)轉(zhuǎn)移方程。（v）確定階段指標(biāo)及指標(biāo)函數(shù)的形式（階段指標(biāo)之和，階段指標(biāo)之積，階段指標(biāo)之極大或

11、極小等）。（vi）寫出基本方程即最優(yōu)值函數(shù)滿足的遞歸方程，以及端點條件。§3 逆序解法的計算框圖以自由終端、固定始端、指標(biāo)函數(shù)取和的形式的逆序解法為例給出計算框圖，其它情況容易在這個基礎(chǔ)上修改得到。一般化的自由終端條件為 (3)其中為已知。固定始端條件可表示為。如果狀態(tài)和決策是連續(xù)變量，用數(shù)值方法求解時需按照精度要求進(jìn)行離散化。設(shè)狀態(tài)的允許集合為.決策的允許集合為.狀態(tài)轉(zhuǎn)移方程和階段指標(biāo)應(yīng)對的每個取值和的每個取值計算，即，。最優(yōu)值函數(shù)應(yīng)對的每個取值計算?；痉匠炭梢员頌?（4）按照（3），（4）逆向計算出，為全過程的最優(yōu)值。記狀態(tài)的最優(yōu)決策為，由和按照狀態(tài)轉(zhuǎn)移方程計算出最優(yōu)狀態(tài)，記作

12、。并得到相應(yīng)的最優(yōu)決策，記作。于是最優(yōu)策略為。算法程序的框圖如下。圖的左邊部分是函數(shù)序列的遞推計算，可輸出全過程最優(yōu)值，如果需要還可以輸出后部子過程最優(yōu)值函數(shù)序列和最優(yōu)決策序列。計算過程中存是備計算之用，在算完后可用將替換掉；存是備右邊部分讀之用。圖的右邊部分是最優(yōu)狀態(tài)和最優(yōu)決策序列的正向計算，可輸出最優(yōu)策略和最優(yōu)軌線。§4 動態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系動態(tài)規(guī)劃與靜態(tài)規(guī)劃（線性和非線性規(guī)劃等）研究的對象本質(zhì)上都是在若干約束條件下的函數(shù)極值問題。兩種規(guī)劃在很多情況下原則上可以相互轉(zhuǎn)換。動態(tài)規(guī)劃可以看作求決策使指標(biāo)函數(shù)達(dá)到最優(yōu)（最大或最?。┑臉O值問題，狀態(tài)轉(zhuǎn)移方程、端點條件以及允許狀態(tài)集、允

13、許決策集等是約束條件，原則上可以用非線性規(guī)劃方法求解。一些靜態(tài)規(guī)劃只要適當(dāng)引入階段變量、狀態(tài)、決策等就可以用動態(tài)規(guī)劃方法求解。下面用例子說明。例3 用動態(tài)規(guī)劃解下列非線性規(guī)劃 ； s.t. .其中為任意的已知函數(shù)。解 按變量的序號劃分階段，看作段決策過程。設(shè)狀態(tài)為，取問題中的變量為決策。狀態(tài)轉(zhuǎn)移方程為取為階段指標(biāo)，最優(yōu)值函數(shù)的基本方程為（注意到）；.按照逆序解法求出對應(yīng)于每個取值的最優(yōu)決策，計算至后即可利用狀態(tài)轉(zhuǎn)移方程得到最優(yōu)狀態(tài)序列和最優(yōu)決策序列。與靜態(tài)規(guī)劃相比，動態(tài)規(guī)劃的優(yōu)越性在于：（i）能夠得到全局最優(yōu)解。由于約束條件確定的約束集合往往很復(fù)雜，即使指標(biāo)函數(shù)較簡單，用非線性規(guī)劃方法也很難求

14、出全局最優(yōu)解。而動態(tài)規(guī)劃方法把全過程化為一系列結(jié)構(gòu)相似的子問題，每個子問題的變量個數(shù)大大減少，約束集合也簡單得多，易于得到全局最優(yōu)解。特別是對于約束集合、狀態(tài)轉(zhuǎn)移和指標(biāo)函數(shù)不能用分析形式給出的優(yōu)化問題，可以對每個子過程用枚舉法求解，而約束條件越多，決策的搜索范圍越小，求解也越容易。對于這類問題，動態(tài)規(guī)劃通常是求全局最優(yōu)解的唯一方法。 （ii）可以得到一族最優(yōu)解。與非線性規(guī)劃只能得到全過程的一個最優(yōu)解不同，動態(tài)規(guī)劃得到的是全過程及所有后部子過程的各個狀態(tài)的一族最優(yōu)解。有些實際問題需要這樣的解族，即使不需要，它們在分析最優(yōu)策略和最優(yōu)值對于狀態(tài)的穩(wěn)定性時也是很有用的。當(dāng)最優(yōu)策略由于某些原因不能實現(xiàn)時

15、，這樣的解族可以用來尋找次優(yōu)策略。（iii）能夠利用經(jīng)驗提高求解效率。如果實際問題本身就是動態(tài)的，由于動態(tài)規(guī)劃方法反映了過程逐段演變的前后聯(lián)系和動態(tài)特征，在計算中可以利用實際知識和經(jīng)驗提高求解效率。如在策略迭代法中，實際經(jīng)驗?zāi)軌驇椭x擇較好的初始策略，提高收斂速度速度。動態(tài)規(guī)劃的主要缺點是： （i）沒有統(tǒng)一的標(biāo)準(zhǔn)模型，也沒有構(gòu)造模型的通用方法，甚至還沒有判斷一個問題能否構(gòu)造動態(tài)規(guī)劃模型的準(zhǔn)則。這樣就只能對每類問題進(jìn)行具體分析，構(gòu)造具體的模型。對于較復(fù)雜的問題在選擇狀態(tài)、決策、確定狀態(tài)轉(zhuǎn)移規(guī)律等方面需要豐富的想象力和靈活的技巧性，這就帶來了應(yīng)用上的局限性。 （ii）用數(shù)值方法求解時存在維數(shù)災(zāi)（c

16、urse of dimensionality）。若一維狀態(tài)變量有個取值，那么對于維問題，狀態(tài)就有個值，對于每個狀態(tài)值都要計算、存儲函數(shù)，對于稍大（即使）的實際問題的計算往往是不現(xiàn)實的。目前還沒有克服維數(shù)災(zāi)的有效的一般方法。§5 若干典型問題的動態(tài)規(guī)劃模型5.1 最短路線問題 對于例1一類最短路線問題（shortest Path Problem），階段按過程的演變劃分，狀態(tài)由各段的初始位置確定，決策為從各個狀態(tài)出發(fā)的走向，即有，階段指標(biāo)為相鄰兩段狀態(tài)間的距離，指標(biāo)函數(shù)為階段指標(biāo)之和，最優(yōu)值函數(shù)是由出發(fā)到終點的最短距離（或最小費用），基本方程為利用這個模型可以算出例l的最短路線為， 相應(yīng)

17、的最短距離為18。5.2 生產(chǎn)計劃問題對于例 2一類生產(chǎn)計劃問題（Production planning problem），階段按計劃時間自然劃分，狀態(tài)定義為每階段開始時的儲存量，決策為每個階段的產(chǎn)量，記每個階段的需求量（已知量）為，則狀態(tài)轉(zhuǎn)移方程為 (5)設(shè)每階段開工的固定成本費為，生產(chǎn)單位數(shù)量產(chǎn)品的成本費為，每階段單位數(shù)量產(chǎn)品的儲存費為，階段指標(biāo)為階段的生產(chǎn)成本和儲存費之和，即 (6)指標(biāo)函數(shù)為之和。最優(yōu)值函數(shù)為從第段的狀態(tài)出發(fā)到過程終結(jié)的最小費用，滿足其中允許決策集合由每階段的最大生產(chǎn)能力決定。若設(shè)過程終結(jié)時允許存儲量為，則終端條件是 （7）（5）（7）構(gòu)成該問題的動態(tài)規(guī)劃模型。5.3

18、資源分配問題一種或幾種資源（包括資金）分配給若干用戶，或投資于幾家企業(yè)，以獲得最大的效益。資源分配問題（resource allocating Problem）可以是多階段決策過程，也可以是靜態(tài)規(guī)劃問題，都能構(gòu)造動態(tài)規(guī)劃模型求解。下面舉例說明。例4 機(jī)器可以在高、低兩種負(fù)荷下生產(chǎn)。臺機(jī)器在高負(fù)荷下的年產(chǎn)量是，在低負(fù)荷下的年產(chǎn)量是，高、低負(fù)荷下機(jī)器的年損耗率分別是和（）。現(xiàn)有臺機(jī)器，要安排一個年的負(fù)荷分配計劃，即 每年初決定多少臺機(jī)器投入高、低負(fù)荷運行，使年的總產(chǎn)量最大。如果進(jìn)一步假設(shè)，（），即高、低負(fù)荷下每臺機(jī)器的年產(chǎn)量分別為和，結(jié)果將有什么特點。解 年度為階段變量。狀態(tài)為第年初完好的機(jī)器數(shù)，決策為第年投入高負(fù)荷運行的臺數(shù)。當(dāng)或不是整數(shù)時，將小數(shù)部分理解為一年中正常工作時間或投入高負(fù)荷運行時間的比例。機(jī)器在高、低負(fù)荷下的年完好率分別記為和，則，有。因為第年投入低負(fù)荷運行的機(jī)器臺數(shù)為，所以狀態(tài)轉(zhuǎn)移方程是 （8）階段指標(biāo)是第年的產(chǎn)量，