动态规划习题详解

动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼(R．Bellman)等人在本世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支——动态规划。他的名著《动态规划》于1957年出版，该书是动态规划的第一本著作。

    动态规划是现代企业管理中的一种重要决策方法，在工程技术、经济管理、工农业生产及军事及其它部们都有广泛的应用，并且获得了显著的效果。动态规划可用于解决最优路径问题、资源分配问题、生产计划与库存问题、投资分配问题、装载问题、设备更新与维修问题、排序问题及生产过程的最优控制等。由于它所具有独特的解题思路，在处理某些优化问题时，常常比线性规划或非线性规划方法更有效。

第 一 节  动态规划的基本方法

多阶段决策的实际问题很多，下面通过具体例子，说明什么是动态规划模型及其求解方法。

例1：最短路线问题

某工厂需要把一批货物从城市A运到城市E，中间可经过B1 、B2、B3、C1、C2、C3、D1、D2等城市，各城市之间的交通线和距离如下图所示，问应该选择一条什么路线，使得从A到E的距离最短？

                                   6

                                                        3

          8                        4                5

                               5                            6                   4                

           9                 8                                   

                                7                      2

                              6                                            3             

          6                   7                      1                       

                                  8                       3

                                    7

下面引进几个动态规划的基本概念和相关符号。

(1)阶段(Stage)

把所给问题的过程，按时间和空间特征划分成若干个相互联系的阶段，以便按次序去求每个阶段的解，阶段总数一般用字母n表示，用字母k表示阶段变量。    

如例l中 (最短路线问题)可看作是n=4阶段的动态规划问题，k=2表示处于第二阶段。

    (2)状态(State)

状态表示每个阶段开始时系统所处的自然状况或客观条件，它描述了研究问题过程状况。描述各阶段状态的变量称为状态变量，常用字母sk表示第k阶段的状态变量，状态变量的取值范围称为状态集，用Sk表示。

  如例l中，第一阶段的状态为A（即出发位置）。第二阶段有三个状态：B1 、B2、B3，状态变量s2=B2表示第2阶段系统所处的位置是B2。第2阶段的状态集S2={ B1 、B2、B3}。

动态规划中的状态变量应具有如下性质：当某阶段状态给定以后，在这个阶段以后过程的发展不受这个阶段以前各个阶段状态的影响。也就是说，未来系统所处的状态只与系统当前所处的状态有关，而与系统过去所处的状态无关，即过去历史只能通过当前的状态去影响它未来的发展，这种特点称为无后效性（又称马尔可夫性）。如果所选定的状态变量不具备无后效性，就不能作为状态变量来构造动态规划模型。如例1中，当某阶段的初始状态即所在的城市选定以后，从这个状态以后的运货路线只与这个城市有关，不受以前的运货路线影响，所以是满足状态的无后效性的。

（3）决策(Decision)

  当系统在某阶段处于某种状态，可以采取的行动（或决定、选择），从而确定下一阶段系统将到达的状态，称这种行动为决策。描述决策的变量，称为决策变量。常用字母u k(sk)表示第k阶段系统处于状态sk时的决策变量。决策变量的取值范围称为决策集，用Dk(sk)表示。

  在例l的第二阶段中，若从状态B2出发，可以做出三种不同的决策，其允许的决策集为D2(B2)={ C1、C2、C3}，决策u 2(B2)= C2表示第二阶段处于状态B2，选择的确行动下一阶段是走到C2。    

    （4）策略(Policy)

系统从第k阶段的状态sk开始由每阶段的决策按顺序组成的决策序列{ u k(sk) ，u k+1(sk+1)，…，u n(sn)}称为一个策略（k=1,2, …，n）,记作。

在例l中，p2,4(B2)={ u 2(B2)= C2，u3(C2)= D1，u 4(D1)=E}是一个策略，表示第二阶段从状态B2出发，沿着B2→C2→D1→E的方向走到终点。注意策略必须是一串实际可行的序列行动。

（5）状态转移方程

系统由这一阶段的—个状态进行决策后转变到下—阶段的另—个状态称为状态转移，状态转移既与状态有关，又与决策有关，描述状态转移关系的方程称为状态转移方程，记为：

sk+1=Tk(sk，uk)

它的实际意义是当系统第k阶段处于状态sk做决策uk时，第k+1阶段系统转移到状态sk+1。

状态转移方程在不同的问题中有不同的具体表现形式，在例l中，状态转移方程表示为：sk+1=uk(sk)。

（6）阶段指标

阶段效益是衡量系统阶段决策结果的一种数量指标，记为：

表示系统在第k阶段处于状态sk做出决策uk时所获得的阶段效益。这里的阶段效益在不同的实际问题中有不同的意义。在例l中它表示两个中转站的距离，如表示从中转站B2走到中转站C2之间的距离为7。更一般地有。

（7）指标函数

指标函数是用来街量所实现过程的优劣的一种数量指标，它是一个定义在全过程和所有后部子过程上的确定的数量函数，记为：

它应具有可分离性，并满足递推关系式：

常见的指标函数的形式是：

1）过程和任一子过程的指标是它所包含的各阶段指标的和。既

2）过程和任一子过程的指标是它所包含的各阶段指标的积。既

（8）最优值函数

指标函数的最优值，称为最优值函数，记为。它表示系统在第k阶段处于状态sk时按最优策略行动所获得总的效益。既

其中opt是最优化（optimization）的缩写，根据实际问题可取max(最大值)和min(最小值),表示对所有允许策略使后面算式取最优。

下面利用动态规划的逆推归纳法，将例1从最后一个城市E逐步推算到第一个城市A，在此表示第k阶段从城市sk到城市E最短路。

1)当k=4时：要求，由于第4阶段只有两个城市D1、D2（即s4的取值为D1、D2），从D1到E只有一条路，故，同理。

2)当k=3时：s3的取值为C1、C2、C3，从C1出发到E有两条路，一条是经过D1到E，另一条是经过D2到E ，显然：

即从C1出发到E的最短路为7，相应决策为，最短路线是C1→D1→E。

同理    

2)当k=2时：s2的取值为B1、B2、B3，从B1出发到E有三条路，分别是经过C1、C2、C3到E，则有：

同理   

2)当k=1时：s1的只有一个取值为A. 从A出发到E有三条路，分别是经过B1、B2、B3到E，则有：

于是得到从A到E的最短距离17，为了找出最短路线，按计算的顺序逆推回去，可得到最优策略为：，最短路线是A→B1→C2→D2→E。

第 二 节  动态规划的基本原理

从上面的计算过程中可以看出，在求解的各个阶段，利用了k阶段与k+1阶段之间的递推关系：

这种递推关系称为动态规划的基本方程，其中称为边界条件。这个递推方程，是根据下述动态规划的贝尔曼(R．Bellman)最优化原理推导得来的。

动态规划最优化原理：“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简单地说就是一个最优策略的子策略也是最优的。

一般情况下，作为一个动态规划模型的最优值函数在k阶段与k+1阶段之间必须满足下列递推关系：

1）加法型：若

则: 

即:          …(1)

边界条件为    

2）乘法型：      …(2)

边界条件为    

这种递推关系式(1)、(2) 称为动态规划的基本方程。这样的求解方法称为逆推解法（或逆序解法）。

同理也可给出顺推解法（或顺序解法），动态规划的顺序解法的基本方程为：

1）加法型：     …(1)

边界条件为    

2）乘法型：      …(2)

边界条件为    

注意：此时状态转移方程变为：sk=Tk(sk＋1，uk)

通过对最短路线问题的求解，我们可以把动态规划方法的基本思想归纳如下：

动态规划方法的关键，在于利用最优化原理给出最优值函数的递推关系式和边界条件，为此，必须先将问题的过程划分为几个相互联系的阶段，适当选取状态变量、决策变量, 状态转移方程及定义最优值函数。从而把一个大问题化成一系列同类型的子问题，然后逐个求解。

例3：逆推解法求解下面问题: 

解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。设状态变量为s1，s2，s3，s4。并记s1＝c；令变量x1，x2，x3为决策变量；各阶段指标按乘积方式结合。

即令: 

令最优值函数f k(sk)表示为第k阶段的初始状态为sk时，从第k阶段到第3阶段所得到的最大值。

设: s3= x3, s3+ x2=s2, s2+ x1=s1=c

则有：x3=s3, 0≤x2≤s2, 0≤x1≤s1=c

即状态转移方程为： s3=s2－x2, s2 =s1－x1

由逆推解法，即最优解x3＊=s3,

由,得和（舍去）

又，而，故为极大值点。

所以即最优解。

求导并令导数等于0可得：，故

由于s1=c，∴， 

由s2 =s1－x1＊，∴,

由s3 =s2－x2＊，∴， 

因此最优解为：，，，

最大值为： 

例3：用顺推解法求解下面问题: 

解:设s4＝c，决策变量仍为x1，x2，x3；最优值函数f k(sk+1)表示为第k阶段末的结束状态为sk+1，从第1阶段到第k阶段所得到的最大值。

设: s2= x1, s2+ x2=s3, s3+ x3=s4=c

则有：x1=s2, 0≤x2≤s3, 0≤x3≤s4=c

即状态转移方程为： s2=s3－x2, s3=s4－x3

由顺推解法，即最优解x1＊=s2,

最优解。

最优解

由于s4=c，∴， 

由s3=s4－x3＊，∴,

由s2=s3－x2＊，∴， 

因此最优解为：，，，

最大值为： 

例4：用顺推解法求解下面问题: 

解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。

设状态变量为s0，s1，s2，s3。并记s3≤9；

令变量x1，x2，x3为决策变量；

最优值函数f k(sk)表示为第k阶段末的结束状态为sk，从第1阶段到第k阶段所得到的最大值。

设: 3x1=s1, s1+2x2=s2, s2+ x3=s3≤9

则有：x1=s1／3,0≤x2≤s2／2 , 0≤x3≤s3≤9

即状态转移方程为： s1=s2－2x2, s2=s3－x3

由顺推解法，即最优解x1＊=s1／3,

由,得(它不在决策集内)

则最大值在端点上，∵

∴最大值点为x2=0。故得到及最优解。

由,得

又，故该点为极小值点。

而

∴最大值点为x3=s3。故得到及最优解。

由于s3不知道，故须在对s3求一次极值，即

反推回去即可得最优解为：，，，

最大值为： 

作业   P214         1，5（1逆推，2顺推）

第 二 节  动态规划应用举例

一、资源分配问题

假设有某种资源的总数量为a(例如原材料、能源、机器设备、劳力、食品等)，可用于生产n个产品，若生产j种产品的所用资源数为xj时，可获得利润为gj(xj)，问如何分配该种资源，使所获得的总利润达到最大。

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

当gj(xj)都是线性函数时，它是一个线性规划问题；当gj(xj)是非线性函数时,它是—个非线性规划问题。但当n比较大时，求解起来是非常麻烦的。由于该问题的特殊性，可以将它看成一个多阶段决策问题，并利用动态规划的方法来求解。

我们将n个产品看作是n个阶段，设状态变量sk表示生产第k个产品至第n个产品的资源数量，。

决策变量xj表示生产第k个产品的所用资源数量，。

显然状态转移方方程为：

第k阶段的阶段指标为：。

最优值函数表示生产第k个产品至第n个产品的资源数量为sk时所获得的最大总利润。

则由动态规划最优化原理，可得动态规划的基本方程为：

下面我们来考虑一种资源可回收利用的资源分配问题，这类分配问题的一般描述如下：

设有某种资源，初始的拥有量是s1。计划在A、B两个生产车间连续使用n个阶段。巳知在A车间投入资源x时的阶段收益是g(x)，在B车间投入资源y时的阶段收益是h(y)。投入的资源在生产过程中有部分消耗,已知，每生产一个阶段后，车间A、B的资源回收率分别为a和b，0 ＜a，b ＜1。回收的资源下一阶段可继续使用，求n阶段间总收益最大的资源分配计划。

设sj为第j阶段投入A、B两个车间使用的资源数，j=1、2、…、n。

xj为第j阶段投入A车间使用的资源数，投入B车间使用的资源数为yj=sj-xj，j=1、2、…、n。此问题的静态规划模型为：

该模型可用动态规划的方法来处理。

令sk为状态变量，表示在第k阶段投入A、B两个车间使用的资源数，k=1、2、…、n。

xk为决策变量，它表示在第k阶段投入A车间使用的资源数，则yk=sk－xk表示在第k阶段投入B车间使用的资源数，k=1、2、…、n。

状态转移方程为：sk+1=axk+b(s k－xk)

最优值函数表示拥有资源数为sk时，从第k阶段至第n阶段采取最优分配方案进行生产时所获得的最大总收益。

则动态规划的递推公式

下面我们对一个具体问题，用此方法求解。

  例1：机器负荷分配问题

某公司新购进1000台机床，每台机床都可在高、低两种不同的负荷下进行生产，设在高负荷下生产的产量函数为g(x)=10x（单位：百件），其中x为投入生产的机床数量，年完好率为a=0.7；在低负荷下生产的产量函数为h(y)=6y（单位：百件），其中y为投人生产的机床数量，年完好率为b=0.9。计划连续使用5年，试问每年如何安排机床在高、低负荷下的生产计划，使在五年内生产的产品总产量达到最高。

  解：该问题可看作一个5阶段决策问题，一个年度就是一个阶段。

状态变量sk取为第k年度度初具有的完好机床台数。

决策变量xk为第k年度中分配在高负荷下生产的机器台数，则yk=sk－xk为第k年度中分配在低负荷下生产的机器台数（假定xk、sk皆为连续变量）。

状态转移方方程为：sk+1=axk+b(sk-xk)=0.7xk+0.9(sk-xk)

第k年度的产量为：vk(sk,xk)=10xk+6(sk-xk)

最优值函数表示拥有机床数为sk时，从第k年度至第五年度采取最优分配方案进行生产时所获得的最大总产量。

则动态规划的基本方程为：

   下面第5年度开始，用逆推归纳法进行计算。

1）k=5时，有

因为是x5的单调增加函数，故的最大解为，相应有=10s5。

  2) k=4时，有

因为是x4的单调增加函数，故的最大解为，相应有=17s4。

3) k=3时，有

因为是x3的单调增加函数，故的最大解为，相应有=21.9s3。

4)当k=2时，有

    因为是x2的单调减少函数，故的最大解为，相应有=25.71s2。

5) 当k=1时，有

因为是x1的单调减少函数，故的最大解为，相应有=29.139s1。

由于第l阶段的初始状态s1是给定的，即s1=1000，因此最优目标函数值为=29139（百件）。

计算结果表明：最优策略为，，，，。即前两年应把年初全部完好机床投入低负荷生产，后三年应把年初全部完好机床投入高负荷生产。这样所得的产量最高，其最高产量为29139百件产品。同时，从求解过程还可反过来确定每年年初的状态，即每年年初所拥有的完好机器台数。已知s1=1000，于是可得：

由此可知最优的决策过程是：第一年将全部1000台机器全部投入到低负荷下进行生产，第一年末机床完好数是900台，第二年将900台机器继续投入到低负荷下进行生产，第二年末机床完好数成为810台，第三年改变策略将这810台机床全部投入到高负荷下进行生产，第三年末机床完好数为567台，第四年将这567台机床全部投入到高负荷下进行生产，第四年末机床完好数成为397台，第五年将这397台机床投入到高负荷下进行生产，这样第五年末剩下的完好机床数为278台，五年共生产产品29139（百件）。 

二、生产与存储问题

假设为有一个企业，要制定某种产品n个阶段（例如年、月、周）的生产（或购买）计划，已知初始的存储量为零，第k个阶段市场需求量为dk，每个阶段企业的最大产量为M，单位产品的生产成本为a，每次生产的生产准备成本为K。问该企业如何安排生产和存储，才能即满足市场需求，又使总的费用最少？

设xk为第k个阶段该产品的生产量。

sk为第k个阶段末该产品的库存量，则有sk=sk-1+xk-dk。

表示第k个阶段该产品xk时的成本费用，它包括生产准备成本K和产品成本axk两项费用，即

表示在第k个阶段结束时有库存量sk所需的存储费用。故第k个阶段的总成本费用为。

上述问题的数学模型为：

现在我们用动态规划的顺推归纳法来求解，把它看作一个n阶段决策问题。令

  xk为决策变量，它表示在第k阶段的生产量。

sk为状态变量，它表示在第k个阶段末该产品的库存量。

则状态转移方程为：sk=sk-1+xk-dk。

最优值函数表示从第1阶段初始库存量为0到第k阶段末库存量为sk时的最小总费用。

则其顺序递推关系式：

    其中，这是因为一方面在每个阶段企业的最大产量为M，另一方面由于满足每个阶段市场的需求量，因为第k-1阶段末库存量为sk-1必须非负，即:

sk-1= dk+sk -xk≥0   ,     ∴    xk ≤dk+sk。

边界条件为（或）。

从边界条件出发，利用上面顺序递推关系式，最后求出的即为所要求的最小总费用。

下面通过一个实际例子计算之。

例2：某企业通过市场调查，估计今后四个时期市场对某种产品的需要量如下表：

    若  0＜x≤6 ，   则生产总成本＝3十1·x

    若 x＝0 ，  则生产总成本＝0

又设每个时期末未销售出去的产品，在一个时期内单位产品的库存费用为0.5(千元)，同时还假定第1时期开始之初和在第4个时期之末，均无产品库存。现在我们的问题是；在满足上述给定的条件下，该厂如何安排各个时期的生产与库存，使所花的总成本费用最低？

解：我们将四个时期分为4个阶段，设k为阶段变量，

k＝1，2，3，4。

状态变量为sk，它表示在第k个阶段末该产品的库存量。

决策变量为xk，它表示在第k阶段的生产量。

则状态转移方程为：sk-1= sk-xk+dk。

在第k个阶段生产准备成本为： 

第k个阶段结束时有库存量sk所需的存贮费用为：。

故第k个阶段的总成本费用为。

则其顺序递推关系式：

其中

  边界条件，。  

1）当k=1时，由于

对s1的可能取值在0至的值分别进行计算。

2）当k=2时，由于

对s2的可能取值在0至

( s1最大可取到4)的值分别进行计算。

3）当k=3时，由于

对s3的可能取值在0至

( s2最大可取到6)的值分别进行计算。

4）当k=4时，由于要求的第4个阶段结束时的库存量为0，即s4=0，因此只须计算

再按计算的顺序反推回去，可得到每个时期的确最优生产决策为：。其相应的最小总成本为20.5千元。

三、设备更新问题

  现以一台机器在n年内使用和更新决策为例来说明模型的求解方法，用表示在第k年初机器已使用t年（或称役龄为t年），再使用1年时所获得的收益。

  表示在第k年初役龄为t年的机器，再使用1年时所需要的运行费用（或维修保养费用）。

  表示在第k年初卖掉一台役龄为t年的机器，再买进一台新机器所需要净成本费用。

  要求在n年内机器的更新策略，使得总效益达到最大。下面建立该问题的动态规划模型。

  设状态变量sk表示在第k年初机器已使用的年数，即机器的役龄。

决策变量xk表示在第k年初是继续使用旧机器还是更换新机器的决策，令。

状态转移方程为：

第k阶段的效益函数为

。

最优值函数表示第k年初有一台役龄为sk的机器至第n年按最优方案进行更新决策时所获得的最大总效益。则由动态规划的最优化原理，可得动态规划的基本方程为：

一个具数字例子如下：

例3：设某企业在第一年初购买一台新设备，该设备在五年内的年运行收益、年运行费用及更换新设备的净费用如下表：（单位：万元）

解：这是一个n=5阶段且初始状态为s1=0的设备更新问题，有关符号假定如上，目标是要求，下面用逆推归纳法进行计算。

1）当k=5时，有

2）当k=4时，有

3）当k=3时，有

4）当k=2时，有

5）当k=1时，有

因为=44，，由上述计算过程逆推回去可知；；；。即最优的设备更新策略是{K，K，R，K，K}，也就是该企业在第一年初购买一台新设备后连续使用两年，第三年初再购买一台新设备一直使用到第五年底，这样可使得企业在五年内的达到最大为方便用44万元。

四、背包问题

  有一个徒步旅行者带一背包，它可容纳物品重量的限度为a公斤。有n种物品可供他选择装入背包中。这n种物品编号为1，2，…，n。已知第i种物品每件重量为wi公斤，使用价值是第i种物品携带数量xi的函数ci(xi)。问该旅行者应如何选择携带这些物品的件数,使得总使用价值最大? 

   设xi为第i种物品的装入件数，则问题的数学模型为：

将n种物品划分为n个阶段，

状态变量sk表示装入第1种物品至第k种物品的总重量。

决策变量xk表示装入第k种物品的件数。

则状态转移方程为：sk-1=sk－wkxk。

最优值函数表示当总重量不超过sk公斤，背包中只装前k种物品的最大价值。

则动态规划的递归方程为：

最后得到的就是所求的最大价值。

例4：设有一辆栽重为10吨的卡车，用以装载三种货物，每种货物的单位重量及单件价值如表所示，问各种货物应装多少件，才能既不超过总重量又使总价值最大？

            s.t

解: 用动态规划方法来解，问题变为求。

必须先算出，，。而

必须先算出，，，，，。而

相应的最优策略为，于是得到

从而

最后得到：

所以最优装入方案为：，最大使用价值为13。

作业 求解：