文档介绍：13 五月 2018
《数学建模》期末论文组队报名
下周二到工2-105由同学们开始讲课
第八章动态规划
Dynamic Programming
动态规划数学模型
资源分配问题
生产与存储问题
背包问题
案例分析:
动态规划在地区水量分配上的应用
13 五月 2018
动态规划是一种研究多阶段决策问题的理论和方法。
所谓多阶段决策问题是指这样一类决策过程:它可以分为若干个互相联系的阶段,在每一个阶段分别对应着一组可以选择的决策,当每个阶段的决策选定后,过程也就随之确定。
动态规划解题的基本思路:
将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段的决策问题,从而简化计算过程。
3
13 五月 2018
动态规划数学模型
Mathematical Model of DP
13 五月 2018
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之间各点的距离。求v1到v10的最短路径。
图8-1
v1
引例
13 五月 2018
用动态规划的思想求解:
(1) 定义“阶段”,第一阶段、第二阶段、第三阶段、第四阶段、第五阶段;
(2) 找到每一个阶段的“状态”;
(3) 从后向前给每一个阶段的“状态”做出决策;
(4) 计算阶段指标和子过程指标,寻找子过程最优指标、
确定最优子策略
13 五月 2018
下面,从最后一个阶段开始,从终点向始点方向逐阶段逆推,找出各点到终点的最短路,当逆推到始点时,也即找到了从始点到终点的全过程的最短路,这种从后向前逆推的方法叫逆序法,动态规划里常用此方法。
最优化原理:从最短路上的每一个点到终点的道路,也一定是从该点到终点的最短路。
13 五月 2018
第5阶段
阶段:
第1阶段
第2阶段
第3阶段
第4阶段
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
0
5
8
4
7
图8-1
v1
12
17
14
20
19
Min{2+5,8+8,6+4}=7
【】
13 五月 2018
9
从上面解题过程看出:
将一个多阶段的决策问题转化为依次求解多个单阶段的决策问题时,一个重要的特征是将前面的最优解传递并纳入下一个阶段一并考虑,即做到求解的各阶段具有递推性
13 五月 2018
(1)阶段k:根据时间或空间将问题的全过程分成若干个互相联系的阶段
基本概念
(3) 决策xk:从某一状态向下一状态过渡时所做的选择.
决策是所在状态的函数,记为xk(sk),表示第k阶段处于sk状态时的决策变量.
比如x2(v3)= v5表示第2阶段处于v3为始点的状态下选择了由v3到v5的决策.
(2)状态sk:每个阶段开始时所处的自然状况或客观条件.
,第 2阶段有3个状态(始点),记s2={v2, v3, v4}.
在状态sk下,允许采取决策的全体称为决策允许集合,记为Dk(sk).
一步选择
13 五月 2018