文档介绍：第八章动态规划
Dynamic Programming
动态规划数学模型Mathematical Model of DP
资源分配问题 Resource Assignment Problem
生产与存储问题Production and Inventory Problem
背包问题 Knapsack Problem
其它动态规划模型 Other Model of DP
运筹学
Operations Research
1、动态规划是解决多阶段决策过程最优化的一种有效的数学方法, 在1951年提出的,1957年他的专著《动态规划》的问世标志着运筹学的一个重要分支——动态规划的诞生。
动态规划(Dynamic Programming)简介
3、动态规划是考察解决问题的一种途径,其基本思想是:
把一个较复杂的问题按照阶段划分,分解为若干个较小的局部问题,然
后按照局部问题的递推关系,依次作出一系列决策,直至整个问题达到总体
最优的目标。
2、所谓多阶段决策问题是指这样一类问题,该问题的决策过程是一种在多
个相互联系的阶段分别作出决策以形成序列决策的过程,而这些决策均是根
据总体最优化这一共同的目标而采取的。
动态规划数学模型
Mathematical Model of DP
v2
v3
v4
v7
v5
v9
v6
v8
v10
2
8
5
12
13
10
7
10
13
11
2
8
6
5
8
8
5
4
【】如图8-1所示,弧边上的权表示两点间的距离,求v1到v10的最短路径及最短路长。
图8-1
v1
第1阶段
第2阶段
第3阶段
第4阶段
阶段:
第5阶段
状态:
v1
v2, v3, v4
v5, v6
v7, v8, v9
v10
思考思路:
在始点站我们考虑是这样的一个多阶段决策问题:“从现在出发应经过哪些点才能使总路长最短”。而当我们到达第一阶段时,考虑的仍是这样一个问题:“从现在出发应经过哪些点才能使总路长最短”。这一问题与前一初始问题内容相同,解决方法也相似,他是前一问题的子问题,只要后一问题能解决,则前一问题也能解决,类似在第二阶段、第三阶段,我们面临着同样的问题和同样相似的解决方法,只是问题变得越来越小和越来越好解决。
思路具体化:
当我们处在v1时,问题是:“如果要获得从该点到终点的最短路线,那么下一
点该选哪一点最好?”假设我们知道下一阶段各个点到终点的最短路线,那么
问题就容易解决,现在的关键问题是如何获得这些点到终点的最短路线。
动态规划问题的基本特征:
1. 问题具有多阶段决策的特征: 阶段可按时间划分,也可按空间划分。
2. 每一阶段都有相应的“状态”与之对应。
3. 每一阶段的某个状态都面临若干个决策,选择不同的决策将会导致下一阶段不同的状态,同时,不同的决策将会导致这一阶段不同的目标函数值。
4. 每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题,各子问题与原问题具有完全相同的结构。
动态规划数学模型
Mathematical Model of DP
注:动态规划解决问题的关键将问题归结为一个递推过程,建立一个递推的
指标函数求最优解。这种递推归结的过程,称为“不变嵌入”。
v2
v3
v4
v7
v5
v9
v6
v8
v10
2
8
5
12
13
10
7
10
13
11
2
8
6
5
8
8
5
4
v1
第1阶段
第2阶段
第3阶段
第4阶段
阶段:
第5阶段
状态:
v1
v2, v3, v4
v5, v6
v7, v8, v9
v10
递推指标函数为 Vk=Vk(sk, xk, xk+1, ···,xn)=vk(sk, xk)+Vk+1
最优指标函数为
其中fk(sk)为阶段k状态为sk时到终点的最短距离,fk+1(sk+1)为阶段k+1状态为sk+1时到终点的最短距离,vk(xk, sk)是状态为sk选择决策xk时sk到xk的距离,Dk(sk)为状态sk的决策集合。
Vk=Vk(sk, xk, xk+1, ···,xn)=vk(sk, xk)+Vk+1
称(8-1)式为动态规划的基本方程或最优性方程,fk+1(sk+1)同样可以
写成上述形式,这里将fk+1(sk+1)嵌入到fk(sk)中,动态规划的这
种特殊形式叫做不变嵌入。
注: (8-1)式描述了动态规划的最优性原理:如果点xk到终点的
最短路线通过点vt,则点vt到终点的最短路线也