基于Matlab的动态规划算法的实现及应用

◆陈甜甜

(湘南学院数学与金融学院)

一、引言

动态规划是用于解决运筹学中多阶段决策过程最优化问题的一种方法。其广泛应用于工程技术、科学管理、工农业生产及军事等领域。在理论上，动态规划是求解这类问题全局最优解的一种有效方法，特别是对于实际中的某些非线性规划问题可能是最优解的唯一方法。然而，动态规划仅仅是解决多阶段决策问题的一种方法，或者说是考查问题的一种途径，而不是一种具体的算法。就目前而言，动态规划没有统一的标准模型，其解法也没有标准算法。在实际应用中，需要具体问题具体分析。动态规划模型的求解问题是影响动态规划理论和方法应用的关键所在，而子问题的求解和大量结果的存储、调用更是一个难点所在。然而，随着计算机技术的快速发展，特别是内存容量和计算速度的增加，使求解较小规模的动态规划问题成为可能，从而使得动态规划的理论和方法在实际中的应用范围迅速增加。

目前，在计算机上实现动态规划的一般求解方法并不多见，尤其是用来解决较复杂的具体问题数学成果甚少。本文从实际出发，利用Matlab软件的强大功能，对动态规划中的生产与存储问题编制程序，并且进行了应用检验来说明方法的可行性。

二、动态规划的基本理论

实际中，要构造一个标准的动态规划模型，通常需要采用以下几个步骤：

(1)划分阶段。将所给问题的过程，按照问题的时间或空间特征分解成若干互相联系的阶段，以便按次序求每阶段的解。

(2)选择状态。将问题发展到各个阶段时所处的各种客观条件用不同的状态表示，即称为状态。状态的选择要满足无后效性和可知性，即状态不仅依赖于状态的转移规律，还依赖于允许决策集合和指标函数结构。

(3)确定决策变量与状态转移方程。当各段的状态取定后，可以做出不同的决策，从而确定下一阶段的状态，这种决定称为决策。描述决策的变量称为决策变量。在决策过程中，由一个状态到另一个状态的演变过程称为状态转移。状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。

(4)写出动态规划的基本方程动态规划的基本方程一般根据实际问题可分为两种形式，逆序形式和顺序形式。动态规划基本方程的逆序形式为：

三、Matlab程序设计

为了编制动态规划的Matlab程序，我们需要创建M文件。M文件有两种：命令文件和函数文件。两者的区别在于：命令文件没有输入参数，也不返回输出参数；而函数文件可以输入参数，也可以输出参数。命令文件对Matlab工作空间中的变量进行操作，而函数文件中定义的变量为局部变量，当函数文件执行完毕后，这些变量被清除。

由于动态规划问题的特殊性，其涉及的实际问题均需要进行反复计算求解，所以在使用Matlab语言对其进行程序设计的过程中用的最多的是循环结构。本文中的编程主要用到了循环结构中的if语句和for语句。

动态规划法算法的关键为每月产量和库存量的取值范围及相互关系，这也是程序实现时的最主要部分。程序整体上采用逆推法，首先，计算四月份最优指标及对应月初库存量，并将其存入数组，然后再计算三月份最优指标对应月初库存量。其中，三月份计算过程需用到存储的四月份最优指标及对应月初库存量数值。然后再计算二月份最优指标，以此类推。其次，在计算每月最优指标及对应月初库存量时采用遍历法，取当月月初库存量及当月产量所有值(当月月初库存量取值极限为零到前面几月均最大生产能力减去前面几月的市场需求数，当月产量取值极限为零到月最大生产能力)，但必须在满足当月月初库存量和当月产量大于当月市场需求量并且小于当月及后续月市场需求总和才进行计算。

四、实例分析——生产与存储问题

某厂某月生产某种产品600件，当月生产的产品若未销出，就需存储(当月入库的产品，当月不需要支付存储费)。月初入库的产品需支付该月的存储费，费用为每月每100件1千元。如果假设生产100件产品的费用为5千元，并且如果安排了生产该月工厂还要支付经营费4千元，每月的市场需求我们在下表中给出，如果要求第1个月的月初及第4个月的月底库存量为零，问每月应如何安排生产，才能即满足市场需求，又可以使这4个月的总生产及存储费用之和最小。

1.应用动态规划法的方法求解

首先对于动态规划的概念做一下处理。

计算过程及结果如表2所示。

计算过程及结果如表3所示。

由表4可知，最优生产及存储方案为第一个月产量为5个单位，第二个月产量为6个，第三个月第四个月不生产，总最低费用67元。

2.Matlab程序设计(略)

根据前面的分析与实际应用结果，可以充分证明，我们采用的求解动态规划问题的方法和Matlab实现程序是有效的。该程序不仅可以方便简洁地得到结果，避免了繁琐的计算，大大降低了工作量，而且可以处理生产函数和存储函数变化时的其他一系列生产与存储问题。简化了动态规划问题的计算。