第3章：动态规划

第三章：动态规划3.1基本概念一、动态决策问题决策过程具有阶段性和时序性(与时间有关)的决策问题。即决策过程可划分为明显的阶段。二、什么叫动态规划(D.P.–DynamicProgram)

多阶段决策问题最优化的一种方法。广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。三、动态规划(D.P.)的起源

1951年,(美)数学家R.Bellman等提出最优化原理，从而建立动态规划，名著《动态规划》于1957年出版。四、动态决策问题分类1、按数据给出的形式分为：

离散型动态决策问题。

连续型动态决策问题。2、按决策过程演变的性质分为：

确定型动态决策问题。

随机型动态决策问题。1五、动态决策问题的基本要素AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141、阶段(stage)n：作出决策的若干轮次。n=1、2、3、4、5。2、状态(state)Sn：每一阶段的出发位置。构成状态集，记为Sn

S1={A}，S2={B1,B2,B3}，S3={C1,C2,C3}，S4={D1,D2,D3}，S5={E1,E2}。阶段的起点。3、决策(decision)Xn：从一个阶段某状态演变到下一个阶段某状态的选择。构成决策集，记为Dn(Sn)。

阶段的终点。

D1(S1)={X1(A)}={B1,B2,B3}=S2，

D2(S2)={X2(B1),X2(B2),X2(B3)}={C1,C2;C1,C2,C3;C2,C3}={C1,C2,C3}=S3，

D3(S3)={X3(C1),X3(C2),X3(C3)}={D1,D2;D1,D2,D3;D1,D2,D3}={D1,D2,D3}=S4，

D4(S4)={X4(D1),X4(D2),X4(D3)}={E1,E2;E1,E2;E1,E2}={E1,E2}=S5，

D5(S5)={X5(E1),X5(E2)}={F;F}={F}。2AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975144、策略(policy)：全过程中各个阶段的决策Xn组成的有序总体{Xn}。如A

B2

C1

D1

E2

F

上例从A

F共有38种走法，即有38条路线，38个策略。5、子策略(sub-policy)

：剩下的n个阶段构成n子过程，相应的决策系列叫n子策略。如

C1

D1

E2

F6、状态转移方程：前一阶段的终点(决策)是后前一阶段的起点(状态)。

Xn

=Sn+17、指标函数：各个阶段的数量指标，记为rn(sn,xn)。如上例中，用dn(sn,xn)表示距离。d2(B3,C2)=1,d3(C2,D3)=6等。8、目标函数：策略的数量指标值，记为

Z=opt[r1(s1,x1)*

*rn(sn,xn)]。其中：opt为max或min，*为运算符号。如上例中，Z=min[d1(s1,x1)+

+dn(sn,xn)]=min[d1+d2+…+

dn]3

3.2最优化原理

一、R.Bellman最优化原理：

作为整个过程的最优策略，无任过去的状态和决策如何，对前面的决策形成状态而言，余下的诸决策必构成最优策略。即：若M是从A到B最优路线上的任一点，则从M到B的路线也是最优路线。A

MB

二、指标递推方程：

fn*(Sn)=opt[rn(sn,xn)*fn+1*(sn+1)]

xn∈Dn(Sn)

如上例：

fn*(Sn)=min[dn(sn,xn)+fn+1*(Sn+1)]，n=4、3、2、1

xn∈Dn(Sn)

f5*(S5)=min[r5(s5,x5)]

x5∈D5(S5)

三、求解过程：

用反向嵌套递推法：从最后一个阶段开始，依次对各子过程寻优，直至获得全过程的最优，形成最优策略，获得最优策略指标值。4

3.3DP建模及求解一、建模条件：

决策过程本身具有时顺序性或可以转化为具有时序性的决策问题，均可建立动态规划数学模型求解。

AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514二、典型动态决策问题建模及其求解

1、最短路线问题例1：求下列图中A到F的最短路线及最短路线值。5AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141、阶段(stage)n：n=1、2、3、4、5。2、状态(state)Sn：

S1={A}，S2={B1,B2,B3}，S3={C1,C2,C3}，S4={D1,D2,D3}，S5={E1,E2}。3、决策(decision)Xn：决策集Dn(Sn)。

D1(S1)={X1(A)}={B1,B2,B3}=S2，

D2(S2)={X2(B1),X2(B2),X2(B3)}={C1,C2;C1,C2,C3;C2,C3}={C1,C2,C3}=S3，

D3(S3)={X3(C1),X3(C2),X3(C3)}={D1,D2;D1,D2,D3;D1,D2,D3}={D1,D2,D3}=S4，

D4(S4)={X4(D1),X4(D2),X4(D3)}={E1,E2;E1,E2;E1,E2}={E1,E2}=S5，

D5(S5)={X5(E1),X5(E2)}={F;F}={F}。4、状态转移方程：Xn

=Sn+15、指标函数(距离)：dn(sn,xn)。d2(B3,C2)=1,d3(C2,D3)=6等。6、指标递推方程：fn*(Sn)=min[rn(sn,xn)+fn+1*(Sn+1)]，n=4、3、2、1

xn∈Dn(Sn)

f5*(S5)=min[r5(s5,x5)]

x5∈D5(S5)6AB1B2B3C1C2C3D1D2D3E1E2F3549543517158464422269751411F22F4+1=52+2=44E26+1=79+2=117E17+1=85+2=77E27AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141+4=55+7=12

///5D18+4=124+7=116+7=1311D24+4=84+7=112+7=98D19+5=145+11=16

///14C14+5=93+11=145+8=139C1

///1+11=127+8=1512C28AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975143+14=175+9=144+12=1614B2最短路线值为：f1*(s1)=14最短路线求解如下：911F22F4+1=52+2=44E26+1=79+2=117E17+1=85+2=77E21+4=55+7=12

///5D18+4=124+7=116+7=1311D24+4=84+7=112+7=98D19+5=145+11=16

///14C14+5=93+11=145+8=139C1

///1+11=127+8=1512C23+14=175+9=144+12=1614B210AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514即：

A

B2

C1

D1

E2

F112、资源分配问题某种资源总量为a，用于生产n种产品，若分配数量Xi用于生产第i种产品，收益为gi(Xi)。问：如何分配才使总收益最大?例1.某有色金属公司拟拔出50万元对所属三家冶炼厂进行技术改造。若以十万元为最小分割单位，各厂收益与投资的关系如下表示：公司经理从定量决策的需要出发，要求系统分析组求出：对三个工厂如何分配这50万元，才能使总收益达到最大?121、阶段n：

123(工厂)2、状态Sn：

S1，S2=S1-

X1，

S3=S2-

X2，

(可供分配的资源量)={5}，={0,1,

,5}，={0,1,

,5}，

3、决策变量Xn：X1，X2,X3=S3(分配的资源量)={0,1,

,5}，={0,1,

,5}，={0,1,

,5}4、状态转移方程：Sn+1=

Sn

-

Xn

5、指标函数(收益)gn(xn)：g1(x1)=g2(x2)=g3(x3)=

{0,4.5,7,9,10.5,12}，{0,2,4.5,7.5,11,15}，{0,5,7,8,10,13}6、指标递推方程：fn*(Sn)=max[gn(xn)+fn+1*(Sn+1)]，n=2、10≤xn≤Sn

f3*(S3)=max[g3(x3)]，

0≤x3≤S3工厂1工厂2工厂313S2=S1-x1=5-1=4S3=S2-x2=4-3=1最优策略为：P*={x1*，x2*，x3*}={1，3，1}Z*=17万元S3=S2-x2S2=S1-x1143、背包问题

例.设有3种物品，每种数量无限，其重量和价值如下表。现有一只可装载重量为W=5公斤的背包，试问:各种物品应各取多少件放入背包，才能使背包中的物品价值最高？这个问题可以整数规划数学模型来描述：设第i种物品取xi件放入背包，背包中物品总价值记为Z，则有数学模型：

MaxZ=65x1+80x2+30x3s.t.2x1+3x2+x3≤5xj≥0，j=1,2,3；且为整数下面用动态规划求解：

15①、阶段n：123(物品)②、状态Sn：S1={5}，

S2=S1－W1·X1，

S3=S2－W2·X2

(背包可装入的重量)={1,3,5}={0,1,2,3,5}③、决策Xn：0≤X1≤S1/W10≤X2≤S2/W20≤X3≤S3/W3(装入的物品件数)X1={0,1,2}X2={0,1}X3={0,1,2,3,5}④、状态转移方程：

Sn+1=Sn－Wn·Xn

⑤、阶段指标函数(价值)：

r1(x1)=65·x1,r2(x2)=80·x2,r3(x3)=30·x3

⑥、递推方程：

物品A物品B物品C下面利用表格进行计算，从最后一个阶段开始：

16n=3时：此时X3≤S3/W3=S3，为整数X3S3f3(S3)=r3(X3)f3*(S3)X3*0123500

001030

301203060

60230306090

903503060901501505n=2时：此时X2≤S2/W2=S2/3，为整数，S3=S2－W2·X2

X2S2f2(S2)=r2(X2)+f3*(S3)f2*(S2)X2*0110+30=30

30030+90=9080+0=8090050+150=15080+60=1401500n=1时：此时X1≤S1/W1=S1/2，为整数，S2=S1－W1·X1

X1S1f1(S1)=r1(X1)+f2*(S2)f1*(S1)X1*01250+150=15065+90=155130+30=1601602S2=S1－W1X1*=5－2×2=1S3=S2－W2X2*=1－3×0=1最优策略为：X*={x1*，x2*，x3*}={2，0，1}，Z*=f1*(S1)=160即应取第一种物品2件，第二种物品0件，第三种物品1件放入背包，才能使背包中的所有物品总价值最高为160元。

174、生产问题

例.某厂生产一种产品，该产品在未来三个月中的需要量分别为3，4，3万件，若生产准备费为

3万元/次，每件成本为1元，每件每月存储费为0.7元，假定1月初和4月初存货为0，且每月产量不限。试求：该厂未来三个月内的最优生产计划？

1月3月4月2月需求量：D1=3D2=4D3=3①、阶段(月)n：1234②、状态Sn：S1={0}，

S2=S1+X1－D1，

S3=S2+X2－D2S4=S3+X3－D3=0

(月初库存

)={0,1,2,3,4,5,6,7},={0,1,2,3}③、决策Xn：X1=

X2

=

X3=(生产量

){3,4,5,6,7,8,9,10};{0,1,2,3,4,5,6,7};{0,1,2,3}④、状态转移方程：

Sn+1=Sn+Xn－Dn

⑤、阶段指标函数(成本)：成本=生产费用＋存储费用

rn(Xn)=3＋1·Xn，

Xn＞00，Xn＝0＋0.7Sn⑥、递推方程：

18n=3时：

此时

S3+X3－D3=0，即X3=3－S3

n=2时：

因为0≤S3≤3，而S3=S2+X2－D2

，即0≤S2+X2－4≤3

，所以4-S2≤X2≤7－S2X3S3f3(S3)=r3(X3)f3*(S3)X3*01230

6+0=6631

5+0.7=5.7

5.722

4+