动态规划所研究的对象是多阶段对策问题

动态规划所研究的对象是多阶段对策问题，是在20世纪50年代初期由美国数学家R.Bellman等

人提出的一类规划模型.动态规划是现代管理领

域的一种重要的决策方法，其主要应用有最优路

径问题、资源分配问题、投资决策问题、生产计

划与库存问题、排序问题、货物装载问题以及生

产过程中的最优控制问题.7、

动态规划模型多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要

做出决策，这个决策不仅决定这一阶段的效益，

而且决定下一阶段的初始状态，每个阶段的决策

确定以后，就得到一个决策序列，称为策略.多

阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优.下面我们通过讲解一个最短路问题来引出处理多阶段决策问题的最优化原理.例10

.

有一辆汽车要把货物从A城运到E

城，而从A城到E

城必须经过一些城市，整段路程可分为若干个阶段，而每个阶段又有若干个城市可供选择，选取怎样的路线才能使路程

最短?假定从A

城到E

城的所有路线如下图

所示：图1

从A城到E城的路线其中B,B₂

,C,C₂

,D,D₂是可供选择的城市，途中

的数字表示两城之间的距离(以10千米为单位)显然，这是一个多阶段决策问题：从A到E

可以分为4个阶段

.

从A

点出发到B,或B,为第一阶段，这时有

两个选择：走到B,或者走到B₂

.

若我们选择走到B

的决

策，则B,就是下一个阶段的起点.在下一阶段，我们

从B

出发，有一个可供选择的决策集合{C,C2},

很明

显，前面各阶段的决策如何选择，直接影响着其余各

阶段的行进路线，我们的目的就是在各个阶段选择一

个决策，使由它们决定的总路程最短.下面我们来求此问题的最短路线，并以此来说明处理多阶段决策问题的最优化原理.先引入动态

规划的基本概念.令k表示由某点至终点之间的阶段数.例如从A到E可以分为4个阶段，从B

到E是5个阶段；第k阶

段的终点又是第k+1

阶段的起点，记为s,

称为状态

变量或状态.某个阶段的所有可能状态全体可用状态集合来描述.例如：

S₂={B,B2};

令x,(s)为决策变

量，它表示当处于状态s,时还有k个阶段时所选择的

一个决策；在各个阶段上选择的决策组成的总体称为一个策略.令f(s,)表示现在处在状态s,还有k个阶段时，由s至终点的最短距离；令d(s,x)

表示s

点到x

点的距离.

现在我们采用逆序递推法从最后一个阶段开始计算并

逐步推移至A

点(也可采用顺序递推法).

由

定

义

，f(D,)

表示由D,至E

的最短距离

，故f(D₁)=4,

同理f(D₂)=3.

当n=2

时，若从C,出发则有

两个选择，

一是至D,

一是至D₂

,

所以：f₂(G)=min{d(C,D,)+f(D,),d(Ci,D₂)+f₁(D₂)}=min

1+4,1+3}=4这说明由C

出发至终点E

的最短距离是4,其最短路线是G→D₂→E,x₂(G)=D₂

.

依次递推，我们能够得到f,(C,)=5,f(B₁)=10,f₃(B₂)=8,

f₄(A)=13,

因

此

最

优

路

线

是

A→B₂→C→D₂→E,

这种方法就是动态规划方

法.态及其初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态而言，必须构成最优策略，同时，

对于多阶段决策问题的最优策略，如果用它的前i步策略

产生的情况(加上原有的约束条件)来形成一个前i步问

题，那么所给最优策略的前，阶段的策略构成这前；步问题的一个最优策略.动态规划的递推关系是依据最优化原理推导出来的：一个过程的最优策略应具有这样的性质，即无论其初始状由上例我们可得到动态规划原理的一般模型：下面我们利用最优化原理解决一个生产与库存管理问题.例11.

某厂计划今年全年生产某种产品A,

已收到的四个季度的订货量分别为600

件、700件、500

件和1200件.产品A的生产费用与产品数量的平方

成正比，比例系数为0.005,存在仓库里的产品要

花费一定的储存费用，每件产品储存费用为每季

度

1

元，为了使费用最小，每一季度应生产多少最好?解：

将每个季度视为一个阶段.取第k季度初具有的产品数为状态变量s,

第k季度需要生产的产品数为决策变量x,

用A,表示每

个季度的订货量，由已知可得：

A,=600,A,=700,A₂=500,A₄=1200由题目已知，两个阶段之间的产品数量关系，可得状态转移方程：Sk+1=Sx+xx-A阶段效益即是费用，所以：d.(sy,x)=sx+0.005x²由于订货量的限制，每季度至少要完成相应的订单，所以有约束条件：Sx+xx≥A用f(s)

表示从状态s,出发，采用最优策略到第四季度结束时的最小费用，可得到动态规划模型：fs(ss)=0,k=4,3,2,1当x₄=1200-s4时，得极小值，即：f₄(s₄)=7200-

11s₄+0.005s²

第三阶段k=3

时：

f₃(s₃)=下面用逆序递推方法求解：从最后一阶段k=4

开始，此时：续对g(x₃)求导后并令其为零得：g'=0.01u3-

11+0.01(s3+x₃-500)=0可得到驻点：x₃=7550-7s₃+0.0025s²即在此点可取极小值，所以：第一阶段k=1时，注意到s₁=0,

同样用第三阶段时的方法得：f(s)=11800

停第二阶段k=2

时，用同样的方法可得：最小费用为11800元.若

每

季

度

都

按

订

货

量

生

产

，

即x₁=600,x₂=700,x₃=500,x₄=1200,则总费用为12700

元，多用了900元.所以各季度的库存量和最优策略分别为：s₁=0,x₁=600S₂=0,x₂=700s³=0,x₃=800S4=300,x₄=900参考文献[1]

刁在筠，郑汉鼎，刘家壮，刘桂真.运筹学(第二版).北京：高等