动态规划习题详解.doc

动态规划
动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼(R．Bellman)等人在本世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支——动态规划。他的名著《动态规划》于1957年出版，该书是动态规划的第一本著作。
动态规划是现代公司管理中的一种重要决策方法，在工程技术、经济管理、工农业生产及军事及其它部们都有广泛的应用，并且获得了显著的效果。动态规划可用于解决最优途径问题、资源分派问题、生产计划与库存问题、投资分派问题、装载问题、设备更新与维修问题、排序问题及生产过程的最优控制等。由于它所具有独特的解题思绪，在解决某些优化问题时，经常比线性规划或非线性规划方法更有效。
第 一 节 动态规划的基本方法
多阶段决策的实际问题很多，下面通过具体例子，说明什么是动态规划模型及其求解方法。
例1：最短路线问题
某工厂需要把一批货品从城市A运到城市E，中间可通过B1 、B2、B3、C1、C2、C3、D1、D2等城市，各城市之间的交通线和距离如下图所示，问应当选择一条什么路线，使得从A到E的距离最短？
C1
B1
6
3
D1
8 4 5
B2
A
5 6 4
E
C2
9 8
7 2
D3
6 3
6 7 1
C3
B3
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：某公司通过市场调查，估计此后四个时期市场对某种产品的需要量如下表：
时期(k)
1
2
3
4
需要量(dk)
2（单位）
3
2
4
假定不管在任何时期，生产每批产品的固定成本费为3(千元)，若不生产，则为零；生产单位产品成本费为1(千元)；每个时期生产能力所允许的最大生产批量为不超过6个单位，则任何时期生产x个单位产品的成本费用为：
若 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：设某公司在第一年初购买一台新设备，该设备在五年内的年运营收益、年运营费用及更换新设备的净费用如下表：（单位：万元）
年份(k)
役龄(t)
运营收益
运营费用
更新费用
第一年
0
22
6
18
次年
0
1
23
21
6
8
19
22
第三年
0
1
2
23
21
18
5
7
10
19
23
28
第四年
0
1
2
3
24
22
19
16
5
7
10
15
20
24
30
38
第五年
0
1
2
3
4
25
23
20
17
14
4
6
9
14
20
20
24
30
38
48
试为该公司制定一个五年中的设备更新策略，使得公司在五年内总收益达成最大？
解：这是一个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吨的卡车，用以装载三种货品，每种货品的单位重量及单件价值如表所示，问各种货品应装多少件，才干既不超过总重量又使总价值最大？

货品
1
2
3
单位重量
3
4
5
单件价值
4
5
6
设xj表达第j种货品的件数（j=1,2,3）,则问题可归结为
s.t
解: 用动态规划方法来解，问题变为求。

必须先算出，，。而

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

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

从而

最后得到：

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

作业 求解：