李偉鵬

摘要：提出了動(dòng)態(tài)規(guī)劃問題的一種矩陣求解方法，同時(shí)給出了基于MATLAB軟件的函數(shù)文件程序.

關(guān)鍵詞：動(dòng)態(tài)規(guī)劃；矩陣；MATLAB

中圖分類號(hào)：G642.0 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1674-9324（2015）10-0283-02

動(dòng)態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種有效方法，是現(xiàn)代企業(yè)管理中的重要決策辦法，利用該方法成功地解決了生產(chǎn)管理、資源分配等方面的許多實(shí)際問題.文獻(xiàn)[1-2]給出了動(dòng)態(tài)規(guī)劃的基本思路和求解方法，文獻(xiàn)[3-4]討論了動(dòng)態(tài)規(guī)劃在路經(jīng)規(guī)劃中的應(yīng)用及MATLAB實(shí)現(xiàn).本文將給出動(dòng)態(tài)規(guī)劃問題的矩陣求解方法及MATLAB實(shí)現(xiàn).

一、動(dòng)態(tài)規(guī)劃的基本思想及求解方法

動(dòng)態(tài)規(guī)劃的基本思想是：（1）將多階段決策過程劃分階段，恰當(dāng)?shù)剡x取狀態(tài)變量，決策變量以定義最優(yōu)指標(biāo)函數(shù)，把問題化成一族同類型的子問題，然后逐個(gè)求解.（2）求解時(shí)從邊界條件開始，逆（或順）過程行進(jìn)方向，逐段遞推尋優(yōu).在每一個(gè)子問題求解時(shí)，都要使用它前面已求出的子問題的最優(yōu)結(jié)果，最后一個(gè)子問題的最優(yōu)解，就是整個(gè)問題的最優(yōu)解.（3）動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段與未來各段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法.

動(dòng)態(tài)規(guī)劃的基本方程是遞推逐段求解的根據(jù)，一般的動(dòng)態(tài)規(guī)劃基本方程為：

fk（sk）=vk（sk，uk）+fk+1（sk+1） k=n，n-1，L，1fn+1（Sn+1）=0

式中opt可根據(jù)題意取min或max，vk（sk，uk）為狀態(tài)sk，決策uk是對(duì)應(yīng)的第k階段的指標(biāo)函數(shù)值，Dk（sk）為第k階段狀態(tài)sk時(shí)的允許決策集合.

二、動(dòng)態(tài)規(guī)劃問題的矩陣求解方法

1.基本概念（逆序解法）.

階段：1，2，…k，（n將問題化成一族同類型的子問題的總個(gè)數(shù)）；

狀態(tài)變量向量S∶S=（s1，s2，L，sm），si為所有可能的狀態(tài)變量的取值，si≠sj（i≠j），s1初始邊界狀態(tài)；

決策變量向量X∶X=（x1，x2，L，xn），uj為所有可能的狀態(tài)變量的取值，xi≠xj（i≠j），

Dk（sk）為第k階段狀態(tài)sk時(shí)的允許決策集合；

狀態(tài)轉(zhuǎn)移方程sk+1=tk（sk，xk）：第k階段狀態(tài)為sk，決策為xk時(shí)第k+1階段的狀態(tài)；

階段效應(yīng)矩陣Vk=v

例：設(shè)某機(jī)械制造廠生產(chǎn)某種產(chǎn)品，今年1～4季度市場(chǎng)對(duì)該產(chǎn)品的需求量dk分別為2，3，2，4臺(tái)；而該廠每得季度生產(chǎn)能力bk均為6臺(tái)，每季度生產(chǎn)這種產(chǎn)品的固定成本為3萬元（不生產(chǎn)時(shí)，k=0），每臺(tái)產(chǎn)品的追加成本為（消耗費(fèi)用）1萬元.本季度的產(chǎn)品如銷售不出，則需運(yùn)到倉(cāng)庫(kù)存儲(chǔ)，每季度每臺(tái)的庫(kù)存費(fèi)用為0.5萬元，每季度倉(cāng)庫(kù)能夠存儲(chǔ)這種產(chǎn)品的最大數(shù)量ck為3臺(tái).試問該廠因如何安排生產(chǎn)，在保證滿足市場(chǎng)需求的前提下，使生產(chǎn)和存儲(chǔ)的總費(fèi)用最小.并假定倉(cāng)庫(kù)第一季度初和第三季度末的庫(kù)存量都必須為零.

運(yùn)行后的結(jié)果：2 5 0 4.（與2.2的結(jié)果一致）

四、結(jié)語

動(dòng)態(tài)規(guī)劃問題的矩陣求解方法，可以計(jì)算任意階段任一狀態(tài)的最優(yōu)目標(biāo)函數(shù)值以及最優(yōu)決策，可以解決數(shù)據(jù)量較大的動(dòng)態(tài)規(guī)劃問題.動(dòng)態(tài)規(guī)劃問題的矩陣求解方法為Matlab軟件的編程提供了思路，從而使計(jì)算更為方便.

參考文獻(xiàn)：

[1]錢頌迪.運(yùn)籌學(xué)[M].第3版.北京：清華大學(xué)出版社，2005：191-203.

[2]胡運(yùn)權(quán).運(yùn)籌學(xué)教程[M].第3版.北京：清華大學(xué)出版社，2007：186-197.

[3]熊德國(guó)，胡勇文.用Dijkstra算法求解最短路的矩陣方法[J].河南理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，（5）：608-612.

[4]薛定宇，陳陽(yáng)泉.高等應(yīng)用數(shù)學(xué)問題的MATLAB求解[M].北京：清華大學(xué)出版社，2008：205-209.

[5]劉衛(wèi)國(guó).MATLAB程序設(shè)計(jì)與應(yīng)用[M].第2版.北京高等教育出版社，2006：71-77.