動態規劃是解決多階段決策過程最優化問題的一種方法．
該方法是由美國數學家貝爾曼(R．Bellman)等人在2O世紀50年代初提出的．他們針對多階段決策問題的特點，提出了解決這類問題的最優化原理，並成功地解決了生產管理、資源分配等方面的許多實際題，從而建立了運籌學的一個新分支——動態規劃．
動態規劃是現代企業管理中的一種重要決策方法，可用於解決最優路徑、資源分配、生產計劃與庫存、投資、裝載、排序等問題，還可用於生產過程的最優控制等．由於它有獨特的解題思路，因而在處理某些優化問題時，比線性規劃或非線性規劃方法更有效．
而MATLAB是一個功能強大的用於基於矩陣運算的強大數值計算軟體，將Matlab語言應用到動態規劃中去，對實際問題進行程序設計和計算，可以達到計算簡便的目的．
一、動態規劃基本概念
使用動態規劃方法解決多階段決策問題，首先要將實際問題寫成動態規劃模型，此時要用到以下概念：
1)階段
將所給問題的過程，按時間或空間特徵分解成若干互相聯繫的階段，以便按次序去求解每階段的解，每個階段就是一個子問題，常用字母k表示階段變量．
2)狀態
各階段開始時的客觀條件叫做狀態．描述各階段狀態的變量稱為狀態變量，常用sk表示第k階段的狀態變量．狀態變量sk的取值集合稱為狀態集合，用sk表示．
3)決策
當各段的狀態取定以後，就可以作出不同的決策(或選擇)，從而確定下一階段的狀態，這種決定稱為決策．表示決策的變量稱為決策變量，常用uk(sk)表示第k階段當狀態為sk時的決策變量．在實際問題中，決策變量的取值往往限制在一定範圍內，稱此範圍為允許決策集合，常用Dk(sk)表示第k階段從狀態sk出發的允許決策集合，顯然有「uk∈Dk(sk)．
4)策略
一個由每個階段的決策按順序組成的集合稱為策略，用p表示，即p(s1)={u1(s1),u2(s2),..,un(sn),}。一個n階段決策過程，從1到n叫作問題的原過程．對於任意給定的k(1≤k≤n)，從第k階段狀態sk到第n階段狀態sn的過程稱為原過程的一個後部子過程．後部子過程的策略記為pk(sk)={uk(sk),uk+1(sk+1),.,un(sn)}，在實際問題中，可供選擇的策略有一定的範圍，此範圍成為允許策略集合。允許策略集合中達到最優效果的策略成為最優策略
5)狀態轉移
動態規劃中本階段往往是上一階段狀態和上一階段的決策進行綜合的結果．如果給定了第k段的狀態sk，且該階段決策為uk(sk)，則第k+1段的狀態sk+1也就完全確定．它們的關係可表示為：
sk+1=Tk(sk,uk)
由於上式表示了由k階段到k+1階段的狀態轉移規律，所以稱該式為狀態轉移方程．
6)指標函數
用于衡量所選定策略優劣的數量指標稱為指標函數．一個n階段決策過程，從1到n叫作問題的原過程．對於任意一個給定的k(1≤k≤n)，從第k階段到第n階段的過程稱為原過程的一個後部子過程。V1,n(s1,p1,n)表示初始狀態為s1採用策略p1,n時原過程的指標函數值。而Vk,n(sk,pk,n)表示在第k階段，狀態為sk採用策略pk,n時後部子過程的指標函數值．最優指標函數記為fk(sk)，它表示從第k階段狀態sk採用最優策略pk,n到過程終止時的最佳效益值．fk(sk)與Vk,n(sk,pk,n)間的關係為：
fk(sk)=Vk,n(sk,pk,n)=optimize Vk,n(sk,pk,n)
當k=1時，f1(s1)就是從初始狀態s1到全過程結束的整體最優函數．
二、動態規劃基本思路
1)將多階段決策過程劃分階段，恰當地選擇狀態變量、決策變量以定義最優指標函數，從而把問題化成一族同類型的子問題，然後逐個求解．
2)求解時從邊界條件開始，逆序過程行進，逐段遞推尋優．在每一個子問題求解時，都要使用它前面已求出的子問題的最優結果．最後一個子問題的最優解，就是整個問題的最優解．
3)動態規劃方法是既將當前一段與未來各段分開，又把當前效益和未來效益結合起來考慮的一種最優化方法，因此每段的最優決策選取是從全局考慮的，與該段的最優選擇一般是不同的．
三、動態規劃函數使用說明
function [p_opt,fval]=dynprog(x,DecisFun,ObjFun,TransFun)
% 自由始端和終端的動態規劃,求指標函數最小值的逆序算法遞歸計算程序
%輸入參數
% x各階段狀態變量的可能取值，第k列代表第k階段狀態變量可能取值
% DecisFun(k,x)決策函數，由階段k的狀態變量x求出相應的允許決策變量
% ObjFun(k,x,u)階段指標函數
% TransFun(k,x,u)狀態轉移函數，其中x是階段k的某狀態變量，u是相應的決策變量
%輸出參數
% p_opt動態規劃的規划過程，p_opt=[階段序號，狀態變量，決策變量，指標函數]
% fval總目標函數值，是一個列向量，第i元素代表第一個狀態變量取第i個可能值時的總目標
四、動態規劃實例分析
某公司擬將某種設備5臺分配給甲、乙、丙3個工廠，各工廠利潤與設備數量之間的關係如下表所示，問這5臺設備如何分配使3個工廠的總利潤為最大?
應用動態規劃方法分析如下
1.階段k
將問題按工廠分為3個階段，k=1,2,3
2.狀態sk
給第k個工廠分配前擁有的設備臺數，顯然s1=5
3.決策uk
分配給第k個工廠的設備臺數，顯然
分給第一個工廠可以0到s1臺之間
分給第二個工廠也可以0到s2臺之間
分給第三個工廠的為s2臺
function u=decisfun(k,s,u)
if k==3
u=s;
else
u=0:s;
end
4.狀態轉移Tk
前後兩個狀態之間的關係如下
s2=s1-u1，s3=s2-u2
function s_next=transfun(k,s,u)
s_next=s-u
5.階段指標Vk
第k階段的指標函數，表示配給第k個工廠uk臺設備所獲得的利益，顯然
Vk=w(uk,k)
function V=subobjfun(k,s,u)
w=[0 0 0
3 5 4
7 10 6
9 11 11
12 11 12
13 11 12];
w=-w;%由於函數只能求最小值，現在求最大值，故取符號
%第k階段，決策變量為u時，對應的目標值
V=([0 1 2 3 4 5]==u)*w(:,k);%或者直接使用V=w(u,k)
6.各階段狀態變量可能取值
由已知，我們容易知道
s1={5}
s2={0,1,2,3,4,5}
s3={0,1,2,3,4,5}
故
s=nan*ones(6,3);%沒有取值的地方使用nan代替
s(1,1)=5;
s(:,2)=[0 1 2 3 4 5]』;
s(:,3)=[0 1 2 3 4 5]』;
根據上面的分析，我們編寫程序如下
function matlabsky
%動態規劃函數求解問題演示實例
%by dynamic
%see also http://www.matlabsky.com
%2008.12.23
%
%計算各狀態變量可能取值，第k列代表第k個狀態變量的可能取值，沒有的使用NaN代替
s=nan*ones(6,3);
s(1,1)=5;
s(:,2)=[0 1 2 3 4 5]';
s(:,3)=[0 1 2 3 4 5]';
%直接調用dynprg函數
[p_opt,fval]=dynprog(s,@DecisFun,@ObjFun,@TransFun)
function u=DecisFun(k,s,u)
%決策函數
if k==3
u=s;
else
u=0:s;
end
function s_next=TransFun(k,s,u)
%狀態轉移函數
s_next=s-u;
function V=ObjFun(k,s,u)
%階段目標函數
w=[0 0 0
3 5 4
7 10 6
9 11 11
12 11 12
13 11 12];
w=-w;%由於函數只能求最小值，現在求最大值，故取符號
%第k階段，決策變量為u時，對應的目標值
V=([0 1 2 3 4 5]==u)*w(:,k);%或者直接使用V=w(u,k)
運行結果如下
p_opt =
1 5 2 -7
2 3 2 -10
3 1 1 -4
fval =
-21
NaN
NaN
NaN
NaN
NaN
複製代碼
這個運行結果解讀如下，我們要一行一行的解讀
對於p_opt：
第一階段，狀態變量為5，決策變量為2，階段指標為-7，也就是說第一階段時有5臺設備，分配給第一個工廠2臺，該工廠的利益為-7
第二階段，狀態變量為3，決策變量為2，階段指標為-10，也就是說第二階段時有3臺設備，分配給第二個工廠2臺，該工廠的利益為-10
第三階段，狀態變量為1，決策變量為1，階段指標為-4，也就是說第三階段時有1臺設備，分配給第三個工廠1臺，該工廠的利益為-4
對於fval：
總指標值為-21=-7-10-4，也就是說按上面的最優策略，將最大獲利21
後面的那些NaN是由於第一個狀態變量的可能取值我們只是輸入了5，而其他可能值都是用NaN的，故沒有結果
當然第一個狀態變量的可能取多個值，dynprog可以求解第一個狀態變量多取值的情況。可是根據該題實際我們只有一個5。下面我們試試，假如s={4 5}的運行結果
%計算各狀態變量可能取值，第k列代表第k個狀態變量的可能取值，沒有的使用NaN代替
s=nan*ones(6,3);
s(1:2,1)=[4,5];
s(:,2)=[0 1 2 3 4 5]';
s(:,3)=[0 1 2 3 4 5]';
%直接調用dynprg函數
[p_opt,fval]=dynprog(s,@DecisFun,@ObjFun,@TransFun)
複製代碼
運行結果如下，至於結果的解讀，大家可以根據dynprog函數的說明試試看看，能否明白
如果沒法理解，可以與我一起探討下matlabsky@gmail.com
p_opt =
1 4 2 -7
2 2 2 -10
3 0 0 0
1 5 2 -7
2 3 2 -10
3 1 1 -4
fval =
-17
-21
NaN
NaN
NaN
NaN
複製代碼