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

《matlab動態(tài)規(guī)劃講義》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、第四章動態(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），把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法—動態(tài)規(guī)劃。1957年出版了他的名著《DynamicProgramming》，這是該領(lǐng)域的第

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

3、那樣有一個標準的數(shù)學表達式和明確定義的一組規(guī)則，而必須對具體問題進行具體分析處理。因此，在學習時，除了要對基本概念和方法正確理解外，應(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（千件）。如果工廠

4、在第一、二季度將全年的需求都生產(chǎn)出來，自然可以降低成本（少付固定成本費），但是對于第三、四季度才能上市的產(chǎn)品需付存儲費，每季每千件的存儲費為0.5（千元）。還規(guī)定年初和年末這種產(chǎn)品均無庫存。試制定一個生產(chǎn)計劃，即安排每個季度的產(chǎn)量，使一年的總費用（生產(chǎn)成本和存儲費）最少。1.2決策過程的分類-51-根據(jù)過程的時間變量是離散的還是連續(xù)的，分為離散時間決策過程（discrete-timedecisionprocess）和連續(xù)時間決策過程（continuous-timedecisionprocess）；根據(jù)過程的演變是確定的還

5、是隨機的，分為確定性決策過程（deterministicdecisionprocess）和隨機性決策過程（stochasticdecisionprocess），其中應(yīng)用最廣的是確定性多階段決策過程?！?基本概念、基本方程和計算方法2.1動態(tài)規(guī)劃的基本概念和基本方程一個多階段決策過程最優(yōu)化問題的動態(tài)規(guī)劃模型通常包含以下要素。2.1.1階段階段(step)是對整個過程的自然劃分。通常根據(jù)時間順序或空間順序特征來劃分階段，以便按階段的次序解優(yōu)化問題。階段變量一般用表示。在例1中由出發(fā)為，由出發(fā)為，依此下去從出發(fā)為，共個階段。在

6、例2中按照第一、二、三、四季度分為，共四個階段。2.1.2狀態(tài)狀態(tài)（state）表示每個階段開始時過程所處的自然狀況。它應(yīng)能描述過程的特征并且無后效性，即當某階段的狀態(tài)變量給定時，這個階段以后過程的演變與該階段以前各階段的狀態(tài)無關(guān)。通常還要求狀態(tài)是直接或間接可以觀測的。描述狀態(tài)的變量稱狀態(tài)變量（statevariable-51-）。變量允許取值的范圍稱允許狀態(tài)集合(setofadmissiblestates)。用表示第階段的狀態(tài)變量，它可以是一個數(shù)或一個向量。用表示第階段的允許狀態(tài)集合。在例1中可取，或?qū)⒍x為，則或，而

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

8、ecisions）。用表示第階段處于狀態(tài)時的決策變量，它是的函數(shù)，用表示的允許決策集合。在例1中可取或，可記作，而。決策變量簡稱決策。2.1.4策略決策組成的序列稱為策略（policy）。由初始狀態(tài)-51-開始的全過程的策略記作，即.由第階段的狀態(tài)開始到終止狀態(tài)的后部子過程的策略記作，即，.類似地，由第到第階段的子過