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

1、Good is good, but better carries it.精益求精，善益求善。matlab 動態(tài)規(guī)劃講義-第四章動態(tài)規(guī)劃1引言1.1動態(tài)規(guī)劃的發(fā)展及研究內(nèi)容動態(tài)規(guī)劃（dynamicprogramming）是運籌學的一個分支，是求解多階段決策問題的最優(yōu)化方法。20世紀50年代初R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時，提出了著名的最優(yōu)性原理（principleofoptimality），把多階段過程轉化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法動態(tài)規(guī)劃。1957年出版了他的名著Dynamic

2、Programming，這是該領域的第一本著作。動態(tài)規(guī)劃問世以來，在經(jīng)濟管理、生產(chǎn)調度、工程技術和最優(yōu)控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃），只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。應指出，動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特殊算法（如線性規(guī)劃是一種算法）。因而，它不象線性規(guī)劃那樣有一個標準的數(shù)學表達式和明確定義的一組規(guī)

3、則，而必須對具體問題進行具體分析處理。因此，在學習時，除了要對基本概念和方法正確理解外，應以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。例1最短路線問題下面是一個線路網(wǎng)，連線上的數(shù)字表示兩點之間的距離（或費用）。試尋求一條由到距離最短（或費用最?。┑穆肪€。例2生產(chǎn)計劃問題工廠生產(chǎn)某種產(chǎn)品，每單位（千件）的成本為1（千元），每次開工的固定成本為3（千元），工廠每季度的最大生產(chǎn)能力為6（千件）。經(jīng)調查，市場對該產(chǎn)品的需求量第一、二、三、四季度分別為2，3，2，4（千件）。如果工廠在第一、二季度將全年的需求都生產(chǎn)出來，自然可以降低成本（少付固定成本費），但是對于第三、四季度才能上市的產(chǎn)品需付存儲費

4、，每季每千件的存儲費為0.5（千元）。還規(guī)定年初和年末這種產(chǎn)品均無庫存。試制定一個生產(chǎn)計劃，即安排每個季度的產(chǎn)量，使一年的總費用（生產(chǎn)成本和存儲費）最少。1.2決策過程的分類根據(jù)過程的時間變量是離散的還是連續(xù)的，分為離散時間決策過程（discrete-timedecisionprocess）和連續(xù)時間決策過程（continuous-timedecisionprocess）；根據(jù)過程的演變是確定的還是隨機的，分為確定性決策過程（deterministicdecisionprocess）和隨機性決策過程（stochasticdecisionprocess），其中應用最廣的是確定性多階段決策過程。2

5、基本概念、基本方程和計算方法2.1動態(tài)規(guī)劃的基本概念和基本方程一個多階段決策過程最優(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）表示每個階段開始時過程所處的自然狀況。它應能描述過程的特征并且無后效性，即當某階段的狀態(tài)變量給定時，這個階段以后過程的演變與該階段以前各階段的狀態(tài)無關。通常還要求狀態(tài)是直接或間接可以觀測的。描述狀

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

7、控制問題中也稱為控制（control）。描述決策的變量稱決策變量（decisionvariable），變量允許取值的范圍稱允許決策集合（setofadmissibledecisions）。用表示第階段處于狀態(tài)時的決策變量，它是的函數(shù)，用表示的允許決策集合。在例1中可取或，可記作，而。決策變量簡稱決策。2.1.4策略決策組成的序列稱為策略（policy）。由初始狀態(tài)開始的全過程的策略記作，即.由第階段的狀態(tài)開始到終止狀態(tài)的后部子過程的策略記作，即，.類似地，由第到第階段的子過程的策略記作.可供選擇的策略有一定的范圍，稱為允許策略集合(setofadmissiblepolicies)，用表示。2.

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

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

10、礎，即：最優(yōu)策略的子策略，構成最優(yōu)子策略。用狀態(tài)轉移方程（1）和遞歸方程（2）求解動態(tài)規(guī)劃的過程，是由逆推至，故這種解法稱為逆序解法。當然，對某些動態(tài)規(guī)劃問題，也可采用順序解法。這時，狀態(tài)轉移方程和遞歸方程分別為：，縱上所述，如果一個問題能用動態(tài)規(guī)劃方法求解，那么，我們可以按下列步驟，首先建立起動態(tài)規(guī)劃的數(shù)學模型：（=1*romani）將過程劃分成恰當?shù)碾A段。（=2*romanii）正確選擇狀態(tài)變量，使它既能描述過程的狀態(tài)，又滿足無后效性，同時確定允許狀態(tài)集合。（=3*romaniii）選擇決策變量，確定允許決策集合。（=4*romaniv）寫出狀態(tài)轉移方程。（=5*romanv）確定階段指標

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

12、記狀態(tài)的最優(yōu)決策為，由和按照狀態(tài)轉移方程計算出最優(yōu)狀態(tài)，記作。并得到相應的最優(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ī)劃的關系動態(tài)規(guī)劃與靜態(tài)規(guī)劃（線性和非線性規(guī)劃等）研究的對象本質上都是在若干約束條件下的函數(shù)極值問題。兩種規(guī)劃在很多情況下原則上可以相互轉換。動態(tài)規(guī)劃可以看作求決策使指標函數(shù)達到最優(yōu)（最大或最?。┑臉O值

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

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

15、對于狀態(tài)的穩(wěn)定性時也是很有用的。當最優(yōu)策略由于某些原因不能實現(xiàn)時，這樣的解族可以用來尋找次優(yōu)策略。（=3*romaniii）能夠利用經(jīng)驗提高求解效率。如果實際問題本身就是動態(tài)的，由于動態(tài)規(guī)劃方法反映了過程逐段演變的前后聯(lián)系和動態(tài)特征，在計算中可以利用實際知識和經(jīng)驗提高求解效率。如在策略迭代法中，實際經(jīng)驗能夠幫助選擇較好的初始策略，提高收斂速度速度。動態(tài)規(guī)劃的主要缺點是：（=1*romani）沒有統(tǒng)一的標準模型，也沒有構造模型的通用方法，甚至還沒有判斷一個問題能否構造動態(tài)規(guī)劃模型的準則。這樣就只能對每類問題進行具體分析，構造具體的模型。對于較復雜的問題在選擇狀態(tài)、決策、確定狀態(tài)轉移規(guī)律等方面需要

16、豐富的想象力和靈活的技巧性，這就帶來了應用上的局限性。（=2*romanii）用數(shù)值方法求解時存在維數(shù)災（curseofdimensionality）。若一維狀態(tài)變量有個取值，那么對于維問題，狀態(tài)就有個值，對于每個狀態(tài)值都要計算、存儲函數(shù)，對于稍大（即使）的實際問題的計算往往是不現(xiàn)實的。目前還沒有克服維數(shù)災的有效的一般方法。5若干典型問題的動態(tài)規(guī)劃模型5.1最短路線問題對于例1一類最短路線問題（shortestPathProblem），階段按過程的演變劃分，狀態(tài)由各段的初始位置確定，決策為從各個狀態(tài)出發(fā)的走向，即有，階段指標為相鄰兩段狀態(tài)間的距離，指標函數(shù)為階段指標之和，最優(yōu)值函數(shù)是由出發(fā)到終

17、點的最短距離（或最小費用），基本方程為利用這個模型可以算出例l的最短路線為，相應的最短距離為18。5.2生產(chǎn)計劃問題對于例2一類生產(chǎn)計劃問題（Productionplanningproblem），階段按計劃時間自然劃分，狀態(tài)定義為每階段開始時的儲存量，決策為每個階段的產(chǎn)量，記每個階段的需求量（已知量）為，則狀態(tài)轉移方程為(5)設每階段開工的固定成本費為，生產(chǎn)單位數(shù)量產(chǎn)品的成本費為，每階段單位數(shù)量產(chǎn)品的儲存費為，階段指標為階段的生產(chǎn)成本和儲存費之和，即(6)指標函數(shù)為之和。最優(yōu)值函數(shù)為從第段的狀態(tài)出發(fā)到過程終結的最小費用，滿足其中允許決策集合由每階段的最大生產(chǎn)能力決定。若設過程終結時允許存儲量為

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