動態(tài)規(guī)劃的一種矩陣求解方法及MATLAB實現(xiàn)

李偉鵬

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

關鍵詞：動態(tài)規(guī)劃；矩陣；MATLAB

中圖分類號：G642.0 文獻標志碼：A 文章編號：1674-9324（2015）10-0283-02

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

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

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

動態(tài)規(guī)劃的基本方程是遞推逐段求解的根據(jù)，一般的動態(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是對應的第k階段的指標函數(shù)值，Dk（sk）為第k階段狀態(tài)sk時的允許決策集合.

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

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

階段：1，2，…k，（n將問題化成一族同類型的子問題的總個數(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時的允許決策集合；

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

階段效應矩陣Vk=v

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

運行后的結果：2 5 0 4.（與2.2的結果一致）

四、結語

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

參考文獻：

[1]錢頌迪.運籌學[M].第3版.北京：清華大學出版社，2005：191-203.

[2]胡運權.運籌學教程[M].第3版.北京：清華大學出版社，2007：186-197.

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

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

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