• 欢迎访问,电商运营建站推广服务,有需求请与我联系!

第五章:动态规划

学习笔记-选修课 4年前 (2018-10-05) 2166次浏览 已收录 0个评论 扫描二维码

5.1.1 动态规划问题

1、什么是动态规划?

是解决多阶段决策过程最优化问题的一种方法。

2、什么是多阶段决策过程?

是指这样一类特殊的活动过程,它们可以按时间顺序分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决策是一个决策序列,所以多阶段决策问题也称为序贯决策问题。

3、多阶段决策过程最优化的目标

是要达到整个活动过程的总体效果最优,所以多阶段的决策并不是各阶段决策的简单总合。由于各段决策间有机地联系着,本段决策的执行将影响到下一段的决策,以至于影响总体效果,所以决策者在每段决策时不应仅考虑本阶段最优,还应考虑对最终目标的影响,从而做出对全局来讲是最优的决策。

4、动态规划的基本特征

(1)数学规划;

(2)时间;

(3)分段决策。

由上述可知,动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各阶段的决策,产生一个决策序列,这就是“动态”的意思。然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入“时间”因素,将问题看成多阶段的决策过程即可。

5、动态规划基本类型

动态规划模型的分类,根据决策过程的时间参数是离散的还是连续的,过程的演变是确定性的还是随机性的,可以分为如下 4 类:

(1)离散确定型;

(2)离散随机型;

(3)连续确定型;

(4)连续随机型。

 

一、基本原理

动态规划方法基于贝尔曼等人提出的最优化原理,这个最优化原理指出:“一个过程的最优策略具有这样的性质,即无论初始状态及初始决策如何,对于先前决策所形成的状态而言,其以后的所有决策必构成最优策略”。

二、基本思想

1、将多阶段决策过程划分阶段,恰当地选取状态变量、决策变量及定义最优指标函数,从而把问题化成一族同类型的子问题,然后逐个求解。

2、求解时从边界条件开始,逆过程行进方向,逐段递推寻优。在每一个子问题求解时,都要使用它前面已求出的子问题的最优结果,最后一个子问题的最优解,就是整个问题的最优解。

3、动态规划方法是既把当前一段与未来各段分开,又把当前效益和未来效益结合起来考虑的一种最优化方法,因此每段的最优决策选取是从全局考虑的,与该段的最优选择一般是不同的。

 

三、基本方法

1、基本方程分段求解方法

对基本方程分段求解,不像线性规划或非线性规划那样有固定的解法,必须根据具体问题的特点,结合数学技巧灵活求解,大体有以下几种方法:

(1)离散变量的分段穷举算法

动态规划模型中的状态变量与决策变量若被限定只能取离散值,则可采用分段穷举法。由于每段的状态变量和决策变量离散取值个数较少,所以动态规划的穷举法要比一般的穷举法有效。用分段穷举法求最优指标函数值时,最重要的是正确确定每段状态变量取值范围和允许决策集合的范围。

(2)连续变量的解法

当动态规划基本方程中状态变量与决策变量为连续变量,就要根据方程的具体情况灵活选取求解方法,如经典解析方法、线性规划方法、非线性规划法或其它数值计算方法等。

2、动态规划求解的基本方法

(1)逆序解法(后向动态规划方法)

从最后一段开始计算逐段向前递推,求得全过程的最优策略(即寻优的方向与多阶段决策过程实际进行的方向相反),称为逆序解法。

(2)顺序解法(前向动态规划方法)

从第一段开始计算逐段向后递推,计算后一段要用到前一段的求优结果,最后一段的结果就是全过程的最优策略(即寻优的方向与多阶段决策过程实际进行的方向相同),称为顺序解法。

 

本章主要教学内容总结:

1、介绍了什么是动态规划问题,动态规划问题的特征,动态规划问题的类型。

2、基本概念包括阶段、状态、决策、策略、状态转移方程和指标函数的定义。

3、介绍了动态规划的基本原理和基本思想,求解动态规划的方法有逆序解法和顺序解法。

 

 


个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用wordpress 相关隐私与版权
转载请注明原文链接:第五章:动态规划
喜欢 (0)
[18669058523]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址