数学模型动态规划

动态规划

动态规划(dynamic programming)是运筹学的一个重要分支，它是解决多阶段决策问题的一种有效的数量化方法．动态规划是由美国学者贝尔曼(R．Bellman）等人所创立的．1951年贝尔曼首先提出了动态规划中解决多阶段决策问题的最优化原理，并给出了许多实际问题的解法．1957年贝尔曼发表了《动态规划》一书，标志着运筹学这一重要分支的诞生．

§1动态规划的概念与原理

一、动态规划的基本概念

引例: 最短路线问题

美国黑金石油公司（The Black Gold Petroleum Company）最近在阿拉斯加（Alaska）的北斯洛波（North Slope）发现了大的石油储量。为了大规模开发这一油田，首先必须建立相应的输运网络，使北斯洛波生产的原油能运至美国的3个装运港之一。在油田的集输站（结点C）与装运港（结点P1、P2、P3）之间需要若干个中间站，中间站之间的联通情况如图1所示，图中线段上的数字代表两站之间的距离（单位：10千米）。试确定一最佳的输运线路，使原油的输送距离最短。

解：最短路线有一个重要性质，即如果由起点A经过B点和C点到达终点D是一条最短路线，则由B点经C点到达终点D一定是B到D的最短路（贝尔曼最优化原理）。此性质用反证法很容易证明，因为如果不是这样，则从B点到D点有另一条距离更短的路线存在，不妨假设为B—P—D；从而可知路线A—B—P—D比原路线A—B—C—D距离短，这与原路线A—B—C—D是最短路线相矛盾，性质得证。

根据最短路线的这一性质，寻找最短路线的方法就是从最后阶段开始，由后向前逐步递推求出各点到终点的最短路线，最后求得由始点到终点的最短路；即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。按照动态规划的方法，将此过程划分为4个阶段，即阶段变量；取过程在各阶段所处的位置为状态变量，按逆序算法求解。

 

 

 

当时：

由结点M31到达目的地有两条路线可以选择，即选择P1或P2；故：

   选择P2

由结点M32到达目的地有三条路线可以选择，即选择P1、P2或P3；故：

   选择P2

由结点M33到达目的地也有三条路线可以选择，即选择P1、P2或P3；故：

   选择P3

由结点M34到达目的地有两条路线可以选择，即选择P2或P3；故：

   选择P2

当时：

由结点M21到达下一阶段有三条路线可以选择，即选择M31、M32或M33；故：

   选择M32

由结点M22到达下一阶段也有三条路线可以选择，即选择M31、M32或M33；故：

   选择M32或M33

由结点M23到达下一阶段也有三条路线可以选择，即选择M32、M33或M34；故：

   选择M33或M34

当时：

由结点M11到达下一阶段有两条路线可以选择，即选择M21或M22；故：

   选择M22

由结点M12到达下一阶段也有两条路线可以选择，即选择M22或M23；故：

   选择M22

当时：

由结点C到达下一阶段有两条路线可以选择，即选择M11或M12；故：

   选择M11

从而通过顺序（计算的反顺序）追踪（黑体标示）可以得到两条最佳的输运线路：C—M11—M22—M32—P2；C—M11—M22—M33—P3。最短的输送距离是280千米。

一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。

1、阶段

阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，常用k来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，但要便于将问题的过程转化为多阶段决策的过程。阶段变量一般用表示。

2、状态

状态（state）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。

描述状态的变量称状态变量（state variable）。变量允许取值的范围称允许状态集合(set of admissible states)。用表示第阶段的状态变量，它可以是一个数或一个向量。用表示第阶段的允许状态集合。

个阶段的决策过程有个状态变量，表示演变的结果。

根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。状态变量简称为状态。

3  决策

当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）。

描述决策的变量称决策变量（decision variable），变量允许取值的范围称允许决策集合（set of admissible decisions）。用表示第阶段处于状态时的决策变量，它是的函数，用表示的允许决策集合。决策变量简称决策。

4  策略

决策组成的序列称为策略（policy）。由初始状态开始的全过程的策略记作，即.

由第阶段的状态开始到终止状态的后部子过程的策略记作，即

，.

类似地，由第到第阶段的子过程的策略记作.

可供选择的策略有一定的范围，称为允许策略集合(set of admissible policies)，用表示。

5.  状态转移方程

在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程（equation of state transition）表示这种演变规律，写作

                                        （1）

6.  指标函数和最优值函数

指标函数(objective function)是衡量过程优劣的数量指标，它是定义在全过程和所有后部子过程上的数量函数，用表示，。指标函数应具有可分离性，即可表为的函数，记为

并且函数对于变量是严格单调的。

过程在第阶段的阶段指标取决于状态和决策，用表示。指标函数由组成，常见的形式有：

阶段指标之和，即   ，

阶段指标之积，即        ，

阶段指标之极大（或极小），即

.

这些形式下第到第阶段子过程的指标函数为。

根据状态转移方程指标函数还可以表示为状态和策略的函数，即。在给定时指标函数对的最优值称为最优值函数（optimal value function），记为，即

，

其中可根据具体情况取或。

7  最优策略和最优轨线

使指标函数达到最优值的策略是从开始的后部子过程的最优策略，记作。是全过程的最优策略，简称最优策略（optimal policy）。从初始状态出发，过程按照和状态转移方程演变所经历的状态序列称最优轨线（optimal trajectory）。

二、基本方程：

对于阶段的动态规划问题，在求子过程上的最优指标函数时，子过程与子过程有如下递推关系：

            （2）

在上述方程中，当为加法时取；当为乘法时，取。

三、最优化原理

动态规划的最优化原理是美国学者R．Bellman首先提出的，其表述如下：“作为整个过程的最优策略应具有这样的性质，无论过去的状态和决策如何，对于前面的决策所形成的状态而言，余下的诸决策必须构成最优策略”．也就是说最优策略的任一子策略都是最优的．

最优化原理还阐述这样一个事实，对全过程的任一状态点，我们不考虑以前的决策，只保证以后的决策是最优的。显然，由于k 的任意性（k =1，2，…，n）就保证了全过程的决策是最优的．最优化原理为动态规划从最后阶段的优化开始，逐步向前一阶段优化扩展直至第一阶段，从而达到全程优化的方法奠定了理论基础．

§2动态规划模型的建立与求解

根据动态规划的概念不难看出，在用动态规划方法解决实际问题时，必须首先明确本问题中的阶段、状态、决策、策略以及考察指标，并建立状态转移方程，然后根据k 阶段最优指标的大小找出与之对应的最优子策略，直至找出问题的最优解．我们把找出实际问题中的阶段、状态、决策、策略以及考察指标，并建立状态转移方程这一过程称为建立动态规划模型．应该说建立动态规划模型是解决动态规划问题的第一步，也是非常重要的一步．模型建立的是否简捷、准确，直接关系到问题最优解的筛选及准确性，因此，建立动态规划模型是十分重要的．

其步骤可归纳如下：

（1）将所要解决的问题恰当地划分为若干阶段，经常是按事物发展的时间和空间来划分不同阶段，各阶段的首尾要互相衔接；

（2）正确地选择状态变量，确定它在每一阶段的取值范围；这一步是形成动态模型的关键，状态变量是动态规划模型中最重要的参数。一般来说，状态变量应该具有以下三个特征：

 ①要能够用来描述决策过程的演变特征；

②满足无后效性，即若某阶段状态已经给定后，则以后过程的进展不受以前各个状态的影响，也就是说，过去的历史只通过当前的状态去影响未来的发展；

③递推性，即由k 阶段的状态变量及决策变量可以计算出阶段的状态变量

（3）选择决策变量，确定允许决策集合。

（4）正确写出状态转移方程

（5）建立指标函数，一般用描述阶段效应，表示从阶段的最优子策略函数.

（6）建立动态规划基本方程。对每一对，计算不同指标值．把这些指标值进行比较取出最优的一个，所谓最优是根据实际问题的需要确定指标值的最大者或最小者，即

          

在动态规划基本方程中，，都是已知函数，最优子策略与之间是递推关系，要求出及需要先求出，这就决定了用在动态规划基本方程求最优策略是逆着阶段的顺序进行的，由 k = n ，n –1，…2，1将上式依次逐步递推，直至全过程的优化结束，即可求出动态规划问题的最优策略及最优指标值．称为动态规划的逆序算法。

第三节  动态规划方法应用

一、机器负荷分配问题

例1：某厂新购某种机床125台，据估计，这种设备5年后将被其他设备所代替，此机床如在高负荷状态下工作，年损坏率为，年利润为10万元；如在低负荷状态下工作，年损坏率为，年利润为6万元；问应该如何安排这些机床的生产负荷，才能使5年内获得最大的利润？

解：以年为阶段，k =1，2，3，4，5

取k年初完好的机床数为状态变量，

以k年初投入高负荷运行的机床数为决策变量，则低负荷运行的机床数为，于是状态转移方程为：

以利润为目标函数，则k年利润为：

记  表示从年至5年末的最大总利润。则动态规划基本方程为：

下面具体求解

注意到动态规划基本方程

所以时

当时

当时

当时

当时

即第一年到第5年末的最大利润为。

在按与计算过程相反的顺序推回去，可得最优计划为

年份

k	完好机床数	高负荷机床数	低负荷机床数
第一年	125	0	125
第二年	100	0	100
第三年	80	0	80
第四年			0
第五年	32	32	0

即前三年全部低负荷运转，后两年全部高负荷运转，最大利润为2790万元。

二、资源分配问题

所谓资源分配问题，就是将一定数量的一种或若干种资源（如原材料、机器设备、资金、劳动力等）恰当地分配给若干个使用者，以使资源得到最有效地利用。

1、一维分配问题

    设有某种资源可用于项活动，假设资源的数量为，已知用于第项活动的资源数为时，可以得到的收益为，试确定资源的分配方案使收益最大？

   该问题的数学模型可以表示为

当为线性函数时，该问题是线性规划问题，当为非线性函数时，该问题是非线性规划问题，如果采用非线性规划求解，比较麻烦。可以将它看成多阶段决策问题，利用动态规划求解。

    在应用动态规划方法处理这一 类问题时，提出将资源分配给每项活动的过程看成一个阶段，每个阶段都要确定对一种活动的资源投放量，这时，状态变量可以选择阶段初所拥有的资源量，即是要在第项到第项活动间分配的资源量。

决策变量选择对活动的资源投放量，决策变量的允许集合为。

在选取上述状态变量和决策变量的情况下，状态转移方程为：

去投放资源时的收益为指标函数，则为阶段效益指标。

记  表示从阶段至阶段的最大总利润。则动态规划基本方程为：

例2：某公司拟将500万元的资本投入所属的甲、乙、丙三个工厂进行技术改造，各工厂获得投资后年利润将有相应的增长，增长额如表1所示。试确定500万元资本的分配方案，以使公司总的年利润增长额最大。

表1

投资额	100万元	200万元	300万元	400万元	500万元
甲	30	70	90	120	130
乙	50	100	110	110	110
丙	40	60	110	120	120

解：将问题按工厂分为三个阶段，设状态变量（）代表从第个工厂到第3个工厂的投资额，决策变量代表第个工厂的投资额。于是有状态转移方程为  、允许决策集合和递推关系式：

   

当时：

于是有表2，表中表示第三个阶段的最优决策。

表2                                         （单位：百万元）

	0	1	2	3	4	5
	0	1	2	3	4	5
	0	0.4	0.6	1.1	1.2	1.2

当时：

于是有表3。

表3                                             （单位：百万元）

u2

x2
	0	1	2	3	4	5
0	0+0						0	0
1	0+0.4	0.5+0					0.5	1
2	0+0.6	0.5+0.4	1.0+0				1.0	2
3	0+1.1	0.5+0.6	1.0+0.4	1.1+0			1.4	2
4	0+1.2	0.5+1.1	1.0+0.6	1.1+0.4	1.1+0		1.6	1，2
5	0+1.2	0.5+1.2	1.0+1.1	1.1+0.6	1.1+0.4	1.1+0	2.1	2

当时：

于是有表4。

表4

u1

x1
	0	1	2	3	4	5
5	0+2.1	0.3+1.6	0.7+1.4	0.9+1.0	1.2+0.5	1.3+0	2.1	0，2

然后按计算表格的顺序反推算，可知最优分配方案有两个：（1）甲工厂投资200万元，乙工厂投资200万元，丙工厂投资100万元；（2）甲工厂没有投资，乙工厂投资200万元，丙工厂投资300万元。按最优分配方案分配投资（资源），年利润将增长210万元。

这个例于是决策变量取离散值的一类分配问题，在实际问题中，相类似的问题还有销售店的布局（分配）问题、设备或人力资源的分配问题等。

2、二维分配问题

（1）设数量分别为的两种资源分配给个使用者，

求总收益最大的分配方案

该问题的数学模型可以表示为

（2）二维分配问题的解法

1、逐次逼近法

由于

①  设

  

②

③

   

    轮转若干步，直到满足精确度要求。

2、拉格郎日乘子法

  （1）估计一个拉格郎日乘子

  （2）用动态规划法解一维问题

  若解不唯一，假设共有个

     

（3）计算

（4）判断

   ①若存在

   ②若

   ③若

   ④若

三、存贮控制问题

    在动态规划模型中,以时期为阶段,取各时期初的库存量为状态变量;取各阶段的产量(或采购量)为决策变量,在确定决策变量时一般要考虑需求量、生产能力、库存等因素；指标函数取生产或采购费用。

例3：某工厂要制定今后四个时期某产品的生产计划，估计今后四个时期内市场对该产品的需求如下表

时期k	1       2         3          4
需求量dk	2       3         2          4

假设该厂生产每批产品的固定费用为2千元，若不生产为0；每单位产品的成本为1千元；每件产品的每期保管费为0.5千元；每个时期最大生产能力所允许的生产批量不超过5个单位；最大库存量为4个单位；假设开始时库存量为1个单位，要求第四期末库存在2个单位。试问该厂应如何安排各个时期的产量，才能满足市场需求的条件下使总费用最小？

解：按四个时期将问题分为四个阶段，k=1,2,3,4

取k期初库存量为状态变量；k期内产量为决策变量，则状态转移方程为

 

由题意，第k期内的费用为

   

记  表示第期至第4期末的最小总费用。则动态规划基本方程为：

下面求解

当时  注意： 

当时        注意： 

当时      注意： 

当时      注意： 

至此计算出本问题第一至四期的最小总费用为20.5千元。在按计算顺序反推回去，可以求出最优生产计划为

时期k	1	2	3	4
需求量dk	2	3	2	4
库存量xk	1	3	0	1
产量uk	4	0	3	5

四、设备更新问题

1、只考虑更新与继续使用（不更新）两种情况。

   要考虑一种设备在n年内的更新问题．在每年年初需作出决策，是继续使用还是更新．

令    

以年为阶段，k =1，2，3，…,n

取第k年初设备的机龄为状态变量，决策变量

，于是状态转移方程为：

阶段指标函数， 

记  表示从年至n年末的最大总利润。则动态规划基本方程为：

例：下表列出了某种设备的5年内各年的预测数据。求5年内各年的更新策略，如果开始时设备机龄为1年，使5年总收益最大？

解：以年为阶段，k =1，2，3，4,5

由

k=5  ，  

第5年机龄为1—5年的设备均不更新

k=4  ，  

第4年机龄为1—4年的设备均不更新

k=3  ，  

k=2 ，  

k=1 ，  

因此，第1年不更新；第2年机龄为2年的更新；第3年机龄为2年、3年的更新，第4年、第5年均不更新。

2、考虑更新与继续使用（不更新）和大修三种情况。

费用不仅取决于机龄和购置的年限， 取决于上次大修后的时间。

令    

则动态规划基本方程为：