8.动态规划.ppt

第八章动态规划
(Dynamic Programming)
学习目标
了解动态规划的研究对象及特点;
理解动态规划的基本概念;
掌握最优化原理与动态规划模型;
掌握动态规划的建模过程;
理解动态规划的求解要求;
(常见的动态规划问题)掌握动态规划的求解方法与技巧。
1
第八章动态规划
(Dynamic programming)
五十年代贝尔曼(B. E. Bellman)为代表的研究成果
属于现代控制理论的一部分
以长远利益为目标的一系列决策
最优化原理,可归结为一个递推公式
2
第一节多阶段决策过程及实例
一、多阶段决策过程
在生产和科学试验中,有一类活动的过程,由于它的特殊性,(1)可将过程分为若干个互相联系的阶段,(2)在它的每一个阶段都需要作出决策,(3)从而使整个过程达到最好的活动效果。
各个阶段的选取不是任意的,它依赖于当前面临的状态,又影响以后的发展。当各个阶段的决策确定后,就组成了一个决策序列。
这种可以把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,也称序贯决策过程。这种问题就称为多阶段决策问题。
状态
1
2
……
n
状态
状态
状态
状态
决策
决策
决策
3
在多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前的状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义。因此,把处理它的方法称为动态规划方法。
但是,一些与时间没有关系的静态规划问题,只要人为的引进“时间”因素,也可把它视为多阶段决策问题,用动态规划方法去处理。
需指出:动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种算法。必须对具体问题进行具体分析,运用动态规划的原理和方法,建立相应的模型,然后再用动态规划方法去求解。
4
通常的决策问题分为两大类:
静态决策
动态决策
不考虑时间的变化,一次性决策。
考虑时间的变化,多阶段决策。
5
例1 如下图,给定一个线路网络,两点之间连线上的数字表示两点间的距离(或费用),试求一条由A到G的铺管线路,使总距离为最短(或总费用最小)。
二、多阶段决策过程实例
B1
A
C3
F2
F1
E3
E2
E1
D3
D2
D1
C4
C2
C1
B2
G
5
3
1
3
6
8
7
6
6
8
3
5
3
4
2
1
3
8
2
2
3
3
3
5
5
2
6
6
4
3
6
贪心算法
每一步都走最短的线路:
A—B2—C4—D3—E2—F2—G,长度为21
最短的线路:
A—B1—C2—D1—E2—F2—G,长度为18
B1
A
C3
F2
F1
E3
E2
E1
D3
D2
D1
C4
C2
C1
B2
G
5
3
1
3
6
8
7
6
6
8
3
5
3
4
2
1
3
8
2
2
3
3
3
5
5
2
6
6
4
3
7
枚举法
列出每条可能的路线,然后算出每条路的长度,从中选择最优路线。
缺点是线路太多,随点数增加很快。
B1
A
C3
F2
F1
E3
E2
E1
D3
D2
D1
C4
C2
C1
B2
G
5
3
1
3
6
8
7
6
6
8
3
5
3
4
2
1
3
8
2
2
3
3
3
5
5
2
6
6
4
3
8
动态规划
B1
A
C3
F2
F1
E3
E2
E1
D3
D2
D1
C4
C2
C1
B2
G
5
3
1
3
6
8
7
6
6
8
3
5
3
4
2
1
3
8
2
2
3
3
3
5
5
2
6
6
4
3
4
3
7
5
9
7
6
8
13
10
9
12
13
16
18
该点到G点的最短距离
第一阶段
第二阶段
第三阶段
第四阶段
第五阶段
第六阶段
从G到A的解法称为逆序解法
从A 到G的解法称为顺序解法
9
例2 (机器负荷分配问题)
某企业拥有完好的机器y台,将它们按照高负荷和低负荷两种生产方式生产,已知收益函数分别是:
g=g(x) 和 h=h(x)
x为机器数量。设高负荷下生产时机器的年完好率为a,低负荷下生产时机器的年完好率为b(0≤a≤1,0≤b≤1)
问:对总数量为y的机器进行分配用于生产,试制定一个五年计划,应如