多阶段决策过程的动态规划方法培训

第八章

动态规划动态规划是解决多阶段决策过程最优化问题的一种方法。由美国数学家

贝尔曼

（

Ballman

）等人在20

世纪

50

年代提出。他们针对多阶段决策问题的特点，提出了解决这类问题的

“

最优化原理

”

，并成功地解决了生产管理

、

工程技术等方面的许多实际问题。

动态规划是现代企业管理中的一种重要决策方法，可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。动态规划模型的分类：以

“

时间

”

角度可分成：

离散型

和连续型。从信息确定与否可分成：

确定型

和随机型。从目标函数的个数可分成：单目标型

和多目标型。8-1

动态规划的基本原理多阶段决策过程最优化

多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。例

8-1

生产与存储问题

某工厂每月需供应市场一定数量的产品。供应需求所剩余产品应存入仓库，一般地说，某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用，要确定一个每月的生产计划，在满足需求条件下，使一年的生产与存储费用之和最小。例

8-2

投资决策问题某公司现有资金

Q

亿元，在今后

5

年内考虑给

A

、

B

、

C

、

D

四个项目投资，这些项目的投资期限、回报率均不相同，问应如何确定这些项目每年的投资额，使到第五年末拥有资金的本利总额最大。例

8-3

设备更新问题

企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用。现在某企业要决定一台设备未来

8年的更新计划，已预测到第

j

年购买设备的价格为

K

j

，

G

j

为设备经过

j

年后的残值，

C

j

为设备连续使用

j-1

年后在第

j

年的维修费用(j=1,2…8)

，问应在哪年更新设备可使总费用最小。动态规划的基本概念阶段；状态；决策和策略；状态转移；指标函数。例

8-4

（不定阶段最短路线问题）

如图是一个五座城市的及其相连道路的交通图，线上的数字是对应的路长。问：应如何选择行驶路线，才能使从

A

、

B

、

C

、

D

各城市到

E

城市的行驶路程最短？ADBCE252755610.53从图中可以看出，任意两座城市之间都有道路相通。我们把从一座城市直达另一座城市作为一个阶段。例从

A

城市到

E

城市的阶段数，少则一个（例从

A

城市直达

E城市），多则无限（例从

A

城市通过其他

B

、

C

、

D

三城市循环到

E

城市）。为避免循环，加上约束条件：每个城市至多经过一次。于是从

A

城市到达

E

城市的阶段数有下列四种情形：1.

从

A

城市直达

E

城市，一个阶段。于是从

A

城市到达

E

城市的阶段数有下列四种情形：1.

从

A

城市直达

E

城市，一个阶段。2.

从

A

城市通过其他

B

、

C

、

D

三城市之一到

E

城市，二个阶段。于是从

A

城市到达

E

城市的阶段数有下列四种情形：3.

从

A

城市通过其他

B

、

C

、

D

三城市之二到

E

城市，三个阶段。于是从

A

城市到达

E

城市的阶段数有下列四种情形：3.

从

A

城市通过其他

B

、

C

、

D

三城市之二到

E

城市，三个阶段。4.

从

A

城市通过其他

B

、

C

、

D

三城市各一次到

E

城市，四个阶段。例

8-5

（一定阶段最短路问题）

W先生每天驾车去公司上班。如图，W

先生的住所位于

A

，公司位于

F，图中的直线段代表公路，交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在

W

先生的问题是要确定一条最省时的上班路线。532A3B14C13D1423

1B2

2C2

3D2

4E1C34D35E22FC2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEF1

阶段（

Stage

）将所给问题的过程，按时间或空间特征分解成若干个相互联系的阶段，以便按次序去求每阶段的解，常用

k

表示阶段变量。我们把从

A

到

F

看成一个五阶段问题。2

状态（

State

）各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用

s

k

表示第

k

阶段的状态变量，状态变量的取值集合称为状态集合，用

S

k

表示。动态规划中的状态具有如下性质：

当某阶段状态给定以后，在这阶段以后的过程的发展不受这段以前各段状态的影响。即：过程的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性。如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。3

决策和策略（

Decision

and

Policy

）

当各段的状态确定以后，就可以做出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。决策变量用

d

k

(S

k

)

表示，允许决策集合用

D

k

(S

k

)

表示。

各个阶段决策确定后，整个问题的决策序列就构成一个策略，用p

1,n

(d

1

,d

2

,…d

n

)

表示。对每个实际问题，可供选择的策略有一定的范围，称为允许策略集合，用

P

表示。使整个问题达到最优效果的策略就是最优策略。4

状态转移方程

动态规划中本阶段的状态往往是上一阶段的决策结果。如果给定了第

k

段的状态

S

k

，本阶段决策为

d

k

(S

k

)

，则第

k+1

段的状态S

k+1

由公式：

S

k+1

=T

k

（

S

k

，

d

k

）确定，称为状态转移方程。5指标函数

用于衡量所选定策略优劣的数量指标称为指标函数。最优指标函数记为

f

k

(S

k

)

。动态规划的基本思想：

从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点

E

最短路线，最后求出

A

点到

E

点的最短路线。C2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEF当

K=5

时，此时

d

5

(S

5

)=F

，其初始状态E

1

或

E

2

，

故

f

5

(E

1

)=4,

f

5

(E

2

)=2用

d

5

*(S

5

)

表示最优决策。C2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEF当

K=4

时，有两个阶段，初始状态

S

4

可以是

D

1

、

D

2

或

D

3

。如果

S

4

=D

1

，则下一步只能取

E

1

，故f

4

(D

1

)=

r(D

1

,E

1

)+

f

5

(E

1

)=2+4=6最短路线：

D

1

——E

1

——F最优解：

d

4

*(D

1

)=

E

1C2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEF如果

S

4

=D

2

，则下一步能取

E

1

或

E

2

，故f

4

(D

2

)=MIN

r(D

2

,E

1

)+

f

5

(E

1

)r(D

2

,E

2

)+

f

5

(E

2

)=MIN

（

4+4

，

3+2

）

=

5最短路线：

D

2

——E

2

——F最优解：

d

4

*(D

2

)=

E

2C2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEF如果

S

4

=D

3

，则下一步只能取

E

2

，故f

4

(D

3

)=

r(D

3

,E

2

)+

f

5

(E

2

)=5+2=7最短路线：

D

3

——E

2

——F最优解：

d

4

*(D

3

)=

E

2C2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEF当

K=3

时，还有三个阶段，初始状态

S

3

可以是

C

1

、

C

2

或

C

3

。如果

S

3

=C

1

，则下一步能取

D

1

或

D

2

，故f

3

(C

1

)=MIN

r(C

1

,D

1

)+

f

4

(D

1

)r(C

1

,D

2

)+

f

4

(D

2

)=MIN

（

3+6

，

3+5

）

=

8最短路线：

C

1

——D

2

——E

2

——F最优解：

d

3

*(C

1

)=

D

2C2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEF如果

S

3

=C

2

，则下一步能取

D

2

或

D

3

，故f

3

(C

2

)=MIN

r(C

2

,D

2

)+

f

4

(D

2

)r(C

2

,D

3

)+

f

4

(D

3

)=MIN

（

3+5

，

2+7

）

=

8最短路线：

C

2

——D

2

——E

2

——F最优解：

d

3

*(C

2

)=

D

2C2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEF如果

S

3

=C

3

，则下一步只能取

D

3

，故f

3

(C

3

)=

r(C

3

,D

3

)+

f

4

(D

3

)=

（

4+7

）

=

11最短路线：

C

3

——D

3

——E

2

——F最优解：

d

3

*(C

3

)=

D

3C2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEF当

K=2

时，还有四个阶段，初始状态

S

2

可以是

B

1

或

B

2

。如果

S

2

=B

1

，则下一步能取

C

1

或

C

2

，故f

2

(B

1

)=MIN

r(B

1

,C

1

)+

f

3

(C

1

)r(B

1

,C

2

)+

f

3

(C

2

)=MIN

（

4+8

，

5+8

）

=

12最短路线：

B

1

——C

1

——D

2

——E

2

——F最优解：

d

2

*(B

1

)=

C

1C2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEF如果

S

2

=B

2

，则下一步能取

C

2

或

C

3

，故f

2

(B

2

)=MIN

r(B

2

,C

2

)+

f

3

(C

2

)r(B

2

,C

3

)+

f

3

(C

3

)=MIN

（

2+8

，

1+11

）

=

10最短路线：

B

2

——C

2

——D

2

——E

2

——F最优解：

d

2

*(B

2

)=

C

2C2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEF当

K=1

时，五个阶段的原问题，初始状态S

1

是

A

。则下一步能取

B

1

或

B

2

，故f

1

(A)=MIN

r(A,B

1

)+

f

2

(B

1

)r(A,B

2

)+

f

2

(B

2

)=MIN

（

3+12

，

4+10

）

=

14最短路线：A——

B

2

——C

2

——D

2

——E

2

——F最优解：

d

1

*(A)=

B

2

，

最短用时

14C2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEFC2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEFC2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEFC2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEFC2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEFC2D2AB1B2C1C3D1D3E1E2F415445

433

33

32

4222ABCDEF动态规划的函数方程（

DP

）

建立

DP

函数方程是指确定过程的阶段及阶段数，规定状态变量和决策变量的取法，给出各阶段的状态集合，允许决策集合，状态转移方程和指标函数等。