动态规划数学建模在企业决策中的应用

文/赵晓艳，河南质量工程职业学院基础教学部

1 动态规划的定义

决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义.因此，把处理它的方法称为动态规划方法.但是，一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因素，也可把它视为多阶段决策问题，用动态规划方法来处理[1].涉及到动态规划，总会有下面几个概念：下面介绍动态规划的基本概念。阶段：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序求解.描述阶段的变量称为阶段变量，常用k表示.阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程能转化成为多阶段决策的过程.状态：状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题的状况，又称不可控因素.在最短路问题中，状态就是某阶段的出发位置.它既是该阶段某支路的起点，又是前一阶段某支路的终点.通常一个阶段有若干个状态（一般第一个阶段只有一个状态，它构成动态规划的递推方程的出口），每一个阶段的所有状态构成一个集合，叫做状态集合.用一个变量Si来描述在第i个阶段的状态集合上的取值，此变量Si称为状态变量（如7.2节中最短路问题中的Si，以及后面要介绍的背包问题、分割问题及设备更新问题中的参数λ）.这里所说的状态是具体的属于某阶段的[2]，它应具备下面的性质：如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响.换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态是以往历史的总结.这个性质称为无后效性，也称马尔可夫（Markov）性.如果状态仅仅描述过程的具体特征，则并不是任何实际过程都能满足无后效性的要求.所以，在构造决策过程的动态规划模型时，不能仅由描述过程的具体特征这点着眼去规定状态变量，而要充分注意到是否满足无后效性的要求.如果状态的某种规定方式可能导致不满足无后效性，则应适当地改变状态的规定方法，达到能使它满足无后效性的要求.决策：决策表示当过程处于某一阶段的某一状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策.在最优控制中也称为控制（只有它才是我们能够控制的）.描述决策的变量称为决策变量.它可以用一个数、一组数或一个向量来描述.常用 uk(sk)表示第k阶段当状态处于sk时的决策变量，它是状态或状态变量的函数（可能是向量值函数或多值函数）.在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合.常用Dk(sk)表示第k阶段当状态处于sk出发的允许决策集合，显然有uk(sk)∈ Dk(sk).例如，在最短路问题中，策略：策略是一个按顺序排列的决策组成的集合.由过程的第k阶段开始到终止状态为止的过程，称为问题的后部子过程.由每段的决策按顺序排列组成的决策函数序列称为子策略，记为

当k=1时，此决策函数序列即为一个策略.

在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合.从允许策略集合中找到达到最优效果的策略称为最优策略.状态转移方程：状态转移方程式确定过程有一个状态到另一个状态的演变过程.若给定第k阶段状态sk和该阶段的决策变量uk(sk)，则第k+1阶段的状态sk+1也就完全确定.即sk+1的值随sk和 uk( sk)的值变化而变化.这种确定的对应关系，记为sk+1=Tk(sk,uk(sk))，它描述了由第k阶段到第k+1阶段的状态转移规律，称为状态转移方程.Tk称为状态转移函数[3].例如，在最短路问题中，状态转移方程为 sk+1=uk( sk).指标函数和最优值函数：用来衡量所实现过程优劣的数量指标，称为指标函数.它是定义在全过程和所有后部子过程上确定的函数.对于要构成动态规划模型的指标函数，应具有可分性，并满足递推关系。在实际问题中，很多指标函数都满足此性质.指标函数的最优值，称为最优值函数.根据问题，取min或max之一.在动态规划模型中，总会出现一个或一组递推关系，我们把它称为动态规划的基本方程动态规划方法的基本思想

2 现将动态规划方法的基本思想

2.1 动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件（基本方程）.要做到这一点，必须先将问题的整个过程分成几个相互联系的阶段，恰当地选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解.即从边界条件开始[4]，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解.

2.2 在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法.因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的.

2.3 在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优策略.

动态规划的理论基础叫做动态规划的最优化原理，它是这样描述的：作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面决策所形成的状态而言，余下的诸决策必须构成最优策略.简言之，一个最优策略的子策略总是最优的.动态规划的优劣：

优点：

（1）易于确定全局最优解.因为它求解的全是一维问题，所以容易确定.

（2）能得到一族（全部的）最优解，有利于分析结果.

（3）能利用经验，提高求解效率.

缺点：

（1）到目前为止，没有一个统一的标准模型可供应用.由于问题的不同，有时要将问题转化成满足条件（无后效性、目标函数的可分性）的多阶段决策过程是非常困难的，需要丰富的想象力和灵活的技巧.

（2）应用的局限性.“无后效性”条件的限制，降低了动态规划的通用性.

（3）在数值计算时，存在所谓的“维数灾难”.当阶段数目较多且每一阶段的允许状态也较多时，计算成本变得非常昂贵，有时使得计算不可能进行下去.在二维或三维动态规划中，问题显得更加突出.

下面的方程在动态规划逆序求解中起着本质的作用。

称此为动态规划逆序求解的基本方程（贝尔曼方程）。

可以把建立动态规划模型归纳成以下几个步骤：

（1）将问题恰当地划分为若干个阶段；

（2）正确选择状态变量，使它既能描述过程的演变，又满足无后效性；

（3）规定决策变量，确定每个阶段的允许决策集合；

（4）写出状态转移方程；

（5）确定各阶段各种决策的阶段指标，列出计算各阶段最优后部策略指标的基本方程。

3 应用

下面结合具体例子阐述建立动态规划模型的思路。例如生产计划问题。公司要对某产品制定n周的生产计划，产品每周的需求量、生产和贮存费用、生产能力的限制、初始库存量n等都是已知的，试在满足需求的条件下，确定每周的生产量，使 周的总费用最少。决策变量是第k周的生产量，记作 uk(k = 1,2, … ,n)。已知下列数据及函数关系：第k周的需求量dk：第k周产量为uk时的生产费为 ck( uk)；第k周初贮存量为xk时这一周的贮存费为 hk( xk)；第k周的生产能力限制为Uk；初始（k=0）及终结（k=n）时贮存量均为零。按照最短路问题的思路，设从第k周初贮存量为xk到（n周末）过程结束的最小费用函数为 fk( xk)，则下列逆向递推公式成立。

而xk与xk+1满足

这里贮存量xk是状态变量，（2）式给出了相邻阶段的状态在决策变量作用下的转移规律，称为状态转移规律。在用（1）式计算时，xk的取值范围——允许状态集合Xk由（2）式及允许决策集合(0≤ uk≤Uk)决定。在实际问题中，为简单起见，生产费用常取ck(uk)， uk=0； ck(uk)= a +cuk， uk＞0，其中c是单位产品生产费，而a是生产准备费。贮存费用常取 hk(xk)= hxk，h是单位产品（一周的）贮存费。最优方程（1）和状态转移方程（2）构成了这个多阶段决策问题的动态规划模型。实际上，多阶段决策问题有时也可用静态规划方法求解，如例2的生产计划问题。