文档介绍：第八章动态规划
(Dynamic programming)
理解动态规划的基本概念
会用动态规划的方法建立多阶段决策问题的数学模型
了解动态规划的基本解法
会用动态规划的方法解决实际中的最短路问题、资源分配问题
1
引例 P192 如下图,给定一个线路网络,两点之间连线上的数字表示两点间的距离,试求一条由A到G的铺管线路,使总距离为最短(或总费用最小)。
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
E3
F1
F2
G
5
3
1
3
6
8
7
6
6
8
3
5
3
3
8
4
2
2
1
2
3
3
3
5
5
2
6
6
4
3
解:将问题分为6个阶段,当k=6时,f6(F1)=4,u6(F1)=G; f6(F2)=3, u6(F2)=G
当k=5时,有
f5(E1)=min{d(E1,F1)+f6(F1),d(E1,F2)+f6(F2)}=min{3+4,5+3}=7, u5(E1)=F1
f5(E2)=min{d(E2,F1)+f6(F1),d(E2,F2)+f6(F2)}=min{5+4,2+3}=5, u5(E2)=F2
f5(E3)=min{d(E3,F1)+f6(F1),d(E3,F2)+f6(F2)}=min{6+4,6+3}=9, u5(E3)=F2
4
3
k=4: f4(D1)=7, u4(D1)=E2; f4(D2)=6,u4(D2)=E2; f4(D3)=8,u4(D3)=E2
k=3: f3(C1)=13,u3(C1)=D1; f3(C2)=10, u3(C2)=D1; f3(C3)=9, u3(C3)=D2;
f3(C4)=12,u3(C4)=D3
k=2: f2(B1)=13, u2(B1)=C2; f2(B2)=16, u3(B2)=C3
k=1: f1(A)=18, u1(A)=B1
7
5
9
7
6
8
13
10
9
12
13
16
18
0
2
动态规划是求解多阶段决策过程最优化的一种数学方法。它将问题的整体按时间或空间的特征分成若干个前后衔接的时空阶段,把多阶段决策问题表示为一系列单阶段决策问题,然后逐个求解,从而求出整个问题的最优决策序列,它强调了时间和空间的连续性。
1951年,美国数学家贝尔曼(B. E. Bellman)等人,根据多阶段决策问题的特点,把多阶段决策问题表示为一系列单阶段问题而逐个加以解决,提出了解决这类问题的“最优化原理”,并将其应用于很多实际问题的研究,从而建立了运筹学的一个分支——动态规划。1957年,这个领域的第一部著作《动态规划》问世。
3
第一节多阶段决策过程及实例
一、多阶段决策过程
在生产和科学试验中,有一类活动的过程,由于它的特殊性,可将过程分为若干个互相联系的阶段,在它的每一个阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此,各个阶段的选取不是任意的,它依赖于当前面临的状态,又影响以后的发展。当各个阶段的决策确定后,就组成了一个决策序列,因而也就决定了整个过程的一条活动路线。这种可以把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,也称序贯决策过程。这种问题就称为多阶段决策问题。
状态
1
2
……
n
状态
状态
状态
状态
决策
决策
决策
4
在多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前的状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义。因此,把处理它的方法称为动态规划方法。但是,一些与时间没有关系的静态规划问题,只要人为的引进“时间”因素,也可把它视为多阶段决策问题,用动态规划方法去处理。
5
企业在生产过程中,由于需求是随着时间变化的因素,因此企业为了获得全年最佳经济效益,就要在整个生产过程中逐月或逐季的根据库存和需求决定生产计划。
某种机器,可以在高、低两种负荷下生产。高负荷下生产的产量多,但每生产一个阶段后机器的完好率低;低负荷下生产时的情况则相反。现在需要安排该种机器在多个阶段内的生产,问应该如何决定各阶段中机器的使用,使整个计划期内的总产量最大。
某台设备,例如汽车,刚买来时故障少,耗油低,出车时间长,处理价值和经济效益高。随着使用时间的增加则变为故障多,耗油高,维修费用增加,经济效益差。使用时间愈长,处理价值也愈低。另外,每次更新都要付出更新费用。因此,应当如何决定设备的使用年限,使总的效益最佳。
二、多阶段决策过程实例
6
第二节动态规划的基本概念和基本方程
一、动态规划的基本概念