2
4.1
4.1
动态规划的基本概念
动态规划的基本概念
--Dynamic programming
--Dynamic programming
动态规划的发展及研究内容
动态规划的发展及研究内容
有一类特殊的活动过程,
有一类特殊的活动过程,
问题可以按时间顺序分解成若干
问题可以按时间顺序分解成若干
相互联系的阶段
相互联系的阶段
,在每一个阶段都要做出决策,全部过程的决
,在每一个阶段都要做出决策,全部过程的决
策是一个
策是一个
决策序列
决策序列
。要使整个活动的总体效果达到最优的问题,
。要使整个活动的总体效果达到最优的问题,
称为
称为
多阶段决策问题
多阶段决策问题
.
.
现实世界里有许多问题属于这种情况:它有很多解,应用
现实世界里有许多问题属于这种情况:它有很多解,应用
要求最优解。穷举法通过找出全部解,再从中选出最优解。这种
要求最优解。穷举法通过找出全部解,再从中选出最优解。这种
方法对于那些计算复杂度很高、计算量很大的问题(如求最佳子
方法对于那些计算复杂度很高、计算量很大的问题(如求最佳子
集的组合问题),要找出一切可能解,所耗费的计算时间可能是
集的组合问题),要找出一切可能解,所耗费的计算时间可能是
不可以接受的。因此,人们为了降低求解问题的难度,把求解过
不可以接受的。因此,人们为了降低求解问题的难度,把求解过
程分为一系列阶段,各个阶段依次按照最优性原则计算,最后阶
程分为一系列阶段,各个阶段依次按照最优性原则计算,最后阶
段计算得到最优解。包括
段计算得到最优解。包括
分段
分段
、
、
求解
求解
两大步。
两大步。
例:投资决策问题
例:投资决策问题
某公司现有资金
某公司现有资金
Q
Q
万元,在今后
万元,在今后
5
5
年内考虑给
年内考虑给
A,B,C,D 4
A,B,C,D 4
个项目投资,这些项目投资的回收期、回报率均不相同。问公
个项目投资,这些项目投资的回收期、回报率均不相同。问公
司应如何确定这些项目每年的投资额,使得第
司应如何确定这些项目每年的投资额,使得第
5
5
年末拥有资金的
年末拥有资金的
本利总额最大?
本利总额最大?
这是一个
这是一个
5
5
阶段的决策问题
阶段的决策问题
评论2