动态规划的一种矩阵求解方法及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.