動態規劃的一種矩陣求解方法及MATLAB實現

李偉鵬

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

關鍵詞：動態規劃；矩陣；MATLAB

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

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

一、動態規劃的基本思想及求解方法

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

動態規劃的基本方程是遞推逐段求解的根據，一般的動態規劃基本方程為：

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

式中opt可根據題意取min或max，vk（sk，uk）為狀態sk，決策uk是對應的第k階段的指標函數值，Dk（sk）為第k階段狀態sk時的允許決策集合.

二、動態規劃問題的矩陣求解方法

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

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

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

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

Dk（sk）為第k階段狀態sk時的允許決策集合；

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

階段效應矩陣Vk=v

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

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

四、結語

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

參考文獻：

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

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

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

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

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