應(yīng)用matlab編程中關(guān)于動態(tài)規(guī)劃算法的總結(jié) 動態(tài)規(guī)劃（dynamic programming）是運籌學(xué)的一個分支，是求解決策過程（decision process）最優(yōu)化的數(shù)學(xué)方法。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ī)劃。

動態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(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ī)劃），只要人為的引進(jìn)時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便的求解。需要注意的是，動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特殊算法（如線性規(guī)劃是一種算法）。因而，它不像線性規(guī)劃那樣有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對具體問題進(jìn)行具體分析處理。因此，在學(xué)習(xí)時，除了要對基本概念和方法正確理解外，應(yīng)以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。

根據(jù)過程的時間變量是離散的還是連續(xù)的，分為離散時間決策過程（discrete-time decision process）和連續(xù)時間決策過程（continuous-time decision process）；根據(jù)過程的演變是確定的還是隨機(jī)的，分為確定性決策過程（deterministic decision process）和隨機(jī)性決策過程（stochastic decision process），其中應(yīng)用最廣的是確定性多階段決策過程。

動態(tài)規(guī)劃與靜態(tài)規(guī)劃（線性和非線性規(guī)劃等）研究的對象本質(zhì)上都是在若干約束條件下的函數(shù)極值問題。兩種規(guī)劃在很多情況下原則上可以相互轉(zhuǎn)換。

與靜態(tài)規(guī)劃相比，動態(tài)規(guī)劃的優(yōu)越性在于：?

1、能夠得到全局最優(yōu)解。由于約束條件確定的約束集合往往很復(fù)雜，即使指標(biāo)函數(shù)較簡單，用非線性規(guī)劃方法也很難求出全局最優(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)解的唯一方法。?

2、可以得到一族最優(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)時，這樣的解族可以用來尋找次優(yōu)策略。? 3、能夠利用經(jīng)驗提高求解效率。如果實際問題本身就是動態(tài)的，由于動態(tài)規(guī)劃方法反映了過程逐段演變的前后聯(lián)系和動態(tài)特征，在計算中可以利用實際知識和經(jīng)驗提高求解效率。如在策略迭代法中，實際經(jīng)驗?zāi)軌驇椭x擇較好的初始策略，提高收斂速度。

動態(tài)規(guī)劃的主要缺點是：?

沒有統(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)用上的局限性。

資源分配問題 ：一種或幾種資源（包括資金）分配給若干用戶，或投資于幾家企業(yè)，以獲得最大的效益。資源分配問題（resource allocating Problem）可以是多階段決策過程，也可以是靜態(tài)規(guī)劃問題，都能構(gòu)造動態(tài)規(guī)劃模型求解。

? ?

1 ?