大连海事大学-刘巍-高等运筹第五讲PPT课件.ppt

高等运筹学
大连海事大学
刘巍
目录
第一篇运筹学发展历史
第二篇运筹学中的数学规划
第三篇运筹学中的组合优化
第四篇运筹学中的随机优化
第五篇运筹学中的博弈论
第六篇运筹学中管理科学
第七篇运筹学中智能计算
第八篇运筹学发展势态
第二篇运筹学中的数学规划
第四章线性规划
第五章非线性规划
第六章锥规划
第七章矩阵规划
第八章变分不等式与互补问题
第九章整数规划
第十章动态规划
第十一章向量优化(多目标优化)
第十二章全局优化
第六讲内容
第十章动态规划
第十章动态规划
当系统模型具备马尔科夫性,同时目标函数可分且嵌套单调时,基于贝尔曼提出的最优性原理,运用动态规划可将求解多阶段全局最优决策问题分解为一系列在各个时间段上的局部优化问题。相比其它解法,特别是在有扰动或在随机情况下,动态规划总是能有效地提供一个在当前信息集下的最优反馈控制策略。
马尔科夫性
在某些随机系统中,有一类具有“无后效性性质”,即当随机过程在某一时刻to所处的状态已知的条件下,过程在时刻t>to时所处的状态只和to时刻有关,而与to以前的状态无关。这种在已知“现在”的条件下,“未来”与“过去”彼此独立的特性就被称为马尔科夫性,具有这种性质的随机过程就叫做马尔科夫过程,其最原始的模型就是马尔科夫链。
9
§1 多阶段决策过程最优化问题举例
例1 最短路径问题
下图表示从起点A到终点E之间各点的距离。求A到E的最
短路径。
B
A
C
B
D
B
C
D
E
C
4
1
2
3
1
2
3
1
2
3
2
2
1
6
4
7
2
4
8
3
8
6
7
5
6
1
10
6
3
7
5
1
10
§1 多阶段决策过程最优化问题举例
用穷举法的计算量:
如果从A到E的站点有k个,除A、E之外每站有3个位置则
总共有3k-1×2条路径;
计算各路径长度总共要进行(k+1) 3k-1×2次加法以及3k-
1×2-1次比较。随着 k 的值增加时,需要进行的加法和比较的
次数将迅速增加;
例如当 k=20时,加法次数为 ×1015 次,
比较 ×1014 次。若用1亿次/秒的计算机计算
需要约508天。