内容发布更新时间 : 2024/10/23 19:19:43星期一 下面是文章的全部内容请认真阅读。

动态规划

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

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

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

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

例1：最短路线问题

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

到E的距离最短？

6 B1 C1 3 8 4 5 5 D 1 6 4 A B 9 8 C2 7 2 2 E 6 3 D3 6 7 1 8 3 B3 C3 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）,记作pk,n(sk)。

在例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）阶段指标

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

vk(sk,uk)

表示系统在第k阶段处于状态sk做出决策uk时所获得的阶段效益。这里的阶段效益在不同的实际问题中有不同的意义。在例l中它表示两个中转站的距离，如

v2(B2,u2(B2)?C2)?d(B2,C2)?7表示从中转站B2走到中转站C2之间的距离为7。更一

般地有vk(sk,uk(sk))?d(sk,uk(sk))。

（7）指标函数

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

Vk,n(sk,uk,sk?1,uk?1,?,sk,uk)k?1,2,?,n

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

Vk,n(sk,uk,sk?1,uk?1,?,sk,uk)??[sk,uk,Vk?1,n(sk?1,uk?1,?,sk,uk)]

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

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

nVk,n(sk,uk,sk?1,uk?1,?,sk,uk)??vj?1j(sj,uj)?vk(sk,uk)?Vk?1,n(sk?1,uk?1,?,sk,uk)]

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

nVk,n(sk,uk,sk?1,uk?1,?,sk,uk)??vj?1j(sj,uj)?vk(sk,uk)?Vk?1,n(sk?1,uk?1,?,sk,uk)]

（8）最优值函数

指标函数的最优值，称为最优值函数，记为fk(sk)。它表示系统在第k阶段处于状

态sk时按最优策略行动所获得总的效益。既

fk(sk)?optVk,n(sk,uk,sk?1,uk?1,?,sk,uk)

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

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

1)当k=4时：要求f4(s4)，由于第4阶段只有两个城市D1、D2（即s4的取值为D1、

*D2），从D1到E只有一条路，故f4(D1)?d(D1,E)?4,u4(D1)?E，同理

f4(D2)?d(D2,E)?3,u4(D2)?E。

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

?d(C1,D1)?f4(D1)??3?4?f3(C1)?min???min???7,?5?3??d(C1,D2)?f4(D2)?

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

?d(C2,D1)?f4(D1)??6?4?同理 f3(C2)???????5,d(C,D)?f(D)2?3???2242?u3(C2)?D2

*?d(C3,D1)?f4(D1)??1?4? f3(C3)???????5,d(C,D)?f(D)3?3??3242??u3(C3)?D1

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

C3到E，则有：

?d(B1,C1)?f3(C1)??6?7?????f2(B1)??d(B1,C2)?f3(C2)???4?5??9,?d(B,C)?f(C)??5?5???1333???d(B2,C1)?f3(C1)??8?7?????同理 f2(B2)??d(B2,C2)?f3(C2)???7?5??11,?d(B,C)?f(C)??6?5???2333???d(B3,C1)?f3(C1)??7?7?????f2(B3)??d(B3,C2)?f3(C2)???8?5??12,?d(B3,C)?f(C)??7?5???333??*u2(B1)?C2

u2(B2)?C3

*u2(B3)?C3

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

B3到E，则有：

?d(A,B1)?f2(B1)???f1(A)?min?d(A,B2)?f2(B2)??min?d(A,B)?f(B)?323???8?9????9?11??17,???6?12?*u1(A)?B1

于是得到从A到E的最短距离17，为了找出最短路线，按计算的顺序逆推回去，可得到最优策略为：p1,4(A)?{u1(A)?B1,u2(B1)?C2,u3(C2)?D2,u4(D2)?E}，最短路线是A→B1→C2→D2→E。

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

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

?d(sk,uk(sk))?fk?1(sk?1)???fk(sk)?ukmin?Dk(sk)???f5(s5)?0(或f4(s4)?d(s4,E))k?4,3,2,1

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

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

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

1） 加法型：若

nVk,n(sk,uk,sk?1,uk?1,?,sk,uk)??vj?1j(sj,uj)?vk(sk,uk)?Vk?1,n(sk?1,uk?1,?,sk,uk)]fk(sk)?optVk,n(sk,uk,sk?1,uk?1,?,sk,uk)pk,n(sk)则:

??opt{vk(sk,uk)?uk?Dk(sk)optpk?1,n(sk?1)Vk?1,n(sk?1,uk?1,?,sk,uk)}

optuk?Dk(sk)?vk(sk,uk)?optuk?Dk(sk)fk?1(sk?1)?fk?1(sk?1)?k?n,n?1,?,2,1 ?(1)

即:fk(sk)??vk(sk,uk)?边界条件为 fn?1(sn?1)?0 2）乘法型：fk(sk)?optxk?Dk(sk)?vk(sk,uk)?fk?1(sk?1)?k?n,n?1,?,2,1 ?(2)

边界条件为 fn?1(sn?1)?1

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

同理也可给出顺推解法（或顺序解法），动态规划的顺序解法的基本方程为： 1）加法型：fk(sk?1)?optuk?Dk(sk)?vk(sk,uk)?fk?1(sk)?k?1,2,?,n?1,n ?(1)

边界条件为 f0(s1)?0 2）乘法型：fk(sk?1)?max边界条件为 f0(s1)?1

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

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

xk?Dk(sk)?vk(sk,uk)?fk?1(sk)?k?1,2,?,n?1,n ?(2)

maxz?x1x2x3例3：逆推解法求解下面问题:?x1?x2?x3?c

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

2即令:v1(s1,x1)?x1,v2(s2,x2)?x2,v3(s3,x3)?x3