南京工业大学 运筹学 课件 第7章动态规划

第七章 动态规划
主要内容:
§7.1多阶段决策问题 §7.2 动态规划的基本概念和基本原理
§7.3 动态规划应用举例
例 求解最短路问题
A1 2 Q 4 3 A3 A2 6 3 7 4 B1 1 4 2 4 4 1 5 6 B2 3 B3 3 3 C2 C1 3 4 T
Ⅰ
Ⅱ
Ⅲ
Ⅳ
分阶段的最短路径
• • • • • • • Ⅳ ： C1—T Ⅲ --Ⅳ : B1—C1—T Ⅱ--Ⅲ--Ⅳ ：A2—B1—C1—T Ⅰ--Ⅱ--Ⅲ --Ⅳ： Q—A2—B1—C1—T Q--A3—B1—C1—T Q--A3—B2—C2—T 3 4 7
决策为 xk 时的指标，则它就是第 k 段指标函
数，简记为vk 。 （2）过程指标函数（也称目标函数） 用f(sk , xk)表示第k子过程的指标函数。表
示处于第 k 段 sk 状态且所作决策为xk时，
从 sk 点到终点的距离。由此可见， f(sk , xk)
不仅跟当前状态 sk 有关，
还跟该子过程策略 pk(sk) 有关,严格说来，应
(6) 指标函数
用来衡量策略或子策略或决策的效果的 某种数量指标，就称为指标函数。它是定义 在全过程或各子过程或各阶段上的确定数量 函数。对不同问题，指标函数可以是诸如费 用、成本、产值、利润、产量、耗量、距离、 时间、效用，等等。
（1）阶段指标函数（也称阶段效应）
用vk(sk , xk)表示第 k 段处于状态 sk且所作
资规划, 排序问题和生产过程的最优控制
等问题;
§7.2 动态规划的基本概念和基本思想
一、基本概念
使用动态规划方法求解决策问题首先要将 问题改造成符合动态规划求解要求的形式, 要涉及以下概念: (1)阶段 (3)决策与策略 (2)状态 (4)状态转移方程

J 表示留在左岸的仆人人数
初始状态s1是T(3,3)
结束状态sn是 T(0,0)
可达状态有哪些?(3,J) (2,2) (1,1) (0,J) J 3 2 1 0
2013-6-9
A
1
运筹学课件
2
3
I
阶段指标——每阶段选定决策xk后所产生的效益，记
vk= vk(Sk， xk)。
指标函数——各阶段的总效益，记相应于Pkn的指标函数
2013-6-9 运筹学课件
动态规划模型的分类： 以“时间”角度可分成：
离散型和连续型。
从信息确定与否可分成：
确定型和随机型。
从目标函数的个数可分成： 单目标型和多目标型。
2013-6-9 运筹学课件
8.2基本概念与方程
1.基本概念
阶段（Stage）——分步求解的过程，用阶段变量k表示，k=1，，n 状态（State）——每阶段初可能的情形或位置，用状态变 量Sk表示。 按状态的取值是离散或连续，将动态规划问题分为
当 k 3，f Max f v
3 0
3 3
3
4
Max 3x 5s 13.6(0.9s 0.2x )
0
3 3
3
3
3
3
Max 0.28x 17.24s
0
3 3
3
3

x s , f 17.52s ,即第3年初将全部完好机器都 投入高负荷。
指标函数vkn=
v

5
表示第k至5年的总产量；
1
递推公式：f Max f v
6

f 0, k 5, ,1
2013-6-9
运筹学课件

4
C2
5 8
E D2
2
4
1
13
B3
12 11
C3
10
设备更新问题
企业在使用设备时都要考虑设备的更新问题，因为设 备越陈旧，所需的维修费用就越高，但购置新设备一次性 支出的费用较大。现某企业要做出一台设备未来5年的更 新计划，经预测，第j年初购买设备的价格为rj，设备连续
使用(j-1)年后在第j年的维护费为kj，使用(j-1)年后设备的
最优决策C1 D1
21
f3(C1)=8
B1
2
10 6
12 14
C1
f3(C2)=7 9 6 5 8
3
f4(D1)=5
D1
f5(E)=0 5
A
5
B2 10
4 13
C2
E
1
D2
f4(D2)=2
2
B3
12 11
C3
10
d (C2 , D1 ) f 4 ( D1 ) f3 (C2 ) min d (C2 , D2 ) f 4 ( D2 )
运筹学
王莉莉
四川农业大学数学系
2012年11月
1
第七章—动态规划
•
― ― ―
学习目标
掌握动态规划的基本概念； 掌握动态规划的最优化原理； 动态规划在经济管理中的应用
2
引言
在生产和经营活动中，经常遇到这样的问题， 它们包含若干个相互联系的阶段，在每个阶段都要 做出决策，一个阶段的决策除了影响本阶段的效果 之外，还经常影响到下一个阶段的初始状态，从而 影响整个过程的最优。因此不仅要考虑这一个阶段， 还要把它看成是整个过程决策链中的一链环，这种 过程称为多阶段决策过程。

5 A
3
1 B1 3
6
8 B2 7
6
C1 6 8
3 C2 5
3 C3 3
84 C4
2 D1
2
D2 1 2
3 D3
3
E1 3
5 5 E2 2
6 6
E3
F1 4
G 3 F2
1
2
3 4 运筹学课程动态规划
5
6
7
示例5（生产与存储问题）：
某工厂生产并销售某种产品。已知今后四个月市场需求 预测及每月生产j个单位产品的费用如下：
上一个阶段的决策直接影响下一个阶段的决策
运筹学课程动态规划
8
示例6（航天飞机飞行控制问题）：
由于航天飞机的运动的环境是不断变化的，因 此就要根据航天飞机飞行在不同环境中的情况， 不断地决定航天飞机的飞行方向和速度（状态）， 使之能最省燃料和实现目的（如软着落问题）。
运筹学课程动态规划
9
所谓多阶段决策问题是指一类活动过程，它可以分为若 干个相互联系的阶段，在每个阶段都需要作出决策。这 个决策不仅决定这一阶段的效益，而且决定下一阶段的 初
1 6
C3
D1
10
E
D2
6
运筹学课程动态规划
12
以上求从A到E的最短路径问题，可以转化为四个性质完
全相同，但规模较小的子问题，即分别从 Di 、 Ci 、Bi、
A到E的最短路径问题。
第四阶段：两个始点 D 1 和 D 2 ，终点只有一个；
本阶段始点 （状态）
D1 D2
本阶段各终点（决策） E 10 6
cj30j
j0 j1,2,6
月1 2 3
4
需求 2 3 2