动态规划问题的基本要素和最优化原理ppt课件.ppt
《动态规划问题的基本要素和最优化原理ppt课件.ppt》由会员分享,可在线阅读,更多相关《动态规划问题的基本要素和最优化原理ppt课件.ppt(12页珍藏版)》请在文库网上搜索。
1、第二节第二节 动态规划问题的基本要素动态规划问题的基本要素 和最优化原理和最优化原理 2.1 动态规划的基本概念 2.2 动态规划的基本思想 2.3 建立动态规划模型的步骤 1、阶段: 把一个问题的过程,恰当地分为若干个相互联系 的阶段,以便于按一定的次序去求解。 描述阶段的变量称为阶段变量。阶段的划分,一 般是根据时间和空间的自然特征来进行的,但要便 于问题转化为多阶段决策。 2、状态:表示每个阶段开始所处的自然状况或客观 条件。通常一个阶段有若干个状态,描述过程状态 的变量称为状态变量。 年、月 、路段 一个数 、一组 数、一 个向量 状态变量的取值有一定的允许集合或范围,此 集合称为状态
2、允许集合。 2.1 动态规划的基本概念 3、决策:表示当过程处于某一阶段的某个状态时 ,可以作出不同的决定,从而确定下一阶段的状态, 这种决定称为决策。 描述决策的变量,称为决策变量。决策变量是状态 变量的函数。可用一个数、一组数或一向量(多维情 形)来描述。 在实际问题中决策变量的取值往往在某一范围之内 ,此范围称为允许决策集合。 系统在某一阶段的状态转移不但与系统的当前的状态 和决策有关,而且还与系统过去的历史状态和决策有 关。 4、多阶段决策过程 可以在各个阶段进行决策,去控制过程发展的多段过 程; 其发展是通过一系列的状态转移来实现的; 图示如下: 状态转移方程是确定 过程由一个状态到
3、另 一个状态的演变过程 。如果第k阶段状态变 量sk的值、该阶段的决 策变量一经确定,第 k+1阶段状态变量sk+1 的值也就确定。 其状态转移方程如下(一般形式) 12 k s1 u1 s2 u2 s3sk uk sk+1 能用动态规划方法求解的多阶段决策过程是一类 特殊的多阶段决策过程,即具有无后效性的多阶段 决策过程。 如果状态变量不能满足无后效性的要求,应 适当地改变状态的定义或规定方法。 动态规划中能 处理的状态转移 方程的形式。 状态具有无后效性的多阶段决策过程的状 态转移方程如下 无后效性(马尔可夫性) 如果某阶段状态给定后,则在这个阶段以后 过程的发展不受这个阶段以前各段状态的
4、影响; 过程的过去历史只能通过当前的状态去影响 它未来的发展; 构造动态规划模型时,要充分注意是 否满足无后效性的要求; 状态变量要满足无后效性的要求; 5、策略:是一个按顺序排列的决策组成的集合。在 实际问题中,可供选择的策略有一定的范围,称为允 许策略集合。从允许策略集合中找出达到最优效果的 策略称为最优策略。 6、状态转移方程:是确定过程由一个状态到另一个 状态的演变过程,描述了状态转移规律。 7、指标函数和最优值函数:用来衡量所实现过程优 劣的一种数量指标,为指标函数。指标函数的最优值 ,称为最优值函数。在不同的问题中,指标函数的含 义是不同的,它可能是距离、利润、成本、产量或资 源消
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 问题 基本要素 优化 原理 ppt 课件