8.1动态规划数学模型 第8章动态规划 电气信息学院 佃松宜、李彬、曾晓东 Mathematical model of dp Dynamic Programming 2021年1月26日星期 Page 6 动态规划问题具有以下基本特征 1.问题具有多阶段决策的特征。阶段可以按时间划分,也 可以按空间划分。 2.每一阶段都有相应的“状态”与之对应。 3.每一阶段都面临一个决策,选择不同的决策将会导致下 一阶段不同的状态,同时,不同的决策将会导致这一阶段不同 的目标函数值。 4.每一阶段的最优解问题可以递归地归结为下一阶段各个 可能状态的最优解问题,各子问题与原问题具有完全相同的结 构。能否构造这样的递推归结,是解决动态规划问题的关键。 这种递推归结的过程,称为“不变嵌入
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 6 动态规划问题具有以下基本特征 1. 问题具有多阶段决策的特征。阶段可以按时间划分，也 可以按空间划分。 2. 每一阶段都有相应的“ 状态”与之对应。 3. 每一阶段都面临一个决策，选择不同的决策将会导致下 一阶段不同的状态，同时，不同的决策将会导致这一阶段不同 的目标函数值。 4. 每一阶段的最优解问题可以递归地归结为下一阶段各个 可能状态的最优解问题，各子问题与原问题具有完全相同的结 构。能否构造这样的递推归结，是解决动态规划问题的关键。 这种递推归结的过程，称为“ 不变嵌入” 。 8.1 动态规划数学模型 Mathematical Model of DP
8.1动态规划数学模型 第8章动态规划 电气信息学院 佃松宜、李彬、曾晓东 Mathematical model of Dp Dynamic Programming 21年1月26日星期 Page 7 5.状态具有无后效性当某阶段状态确定后,此阶段以后过 程的发展不受此阶段以前各阶段状态的影响。如下图所示 BI C1 3 14 C2 9 DI 6 A B2 C3 E 5 12 10 B31 C4
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 7 5 . 状态具有无后效性 当某阶段状态确定后，此阶段以后过 程的发展不受此阶段以前各阶段状态的影响。如下图所示： 9 A B1 B2 B3 D1 C1 C4 C3 D2 E 7 8 12 12 14 4 12 1 3 6 5 10 6 4 C2 9 0 8.1 动态规划数学模型 Mathematical Model of DP
第8章动态规划 电气信息学院 8.1动态规划数学模型 佃松宜、李彬、曾晓东 Mathematical model of Dp Dynamic Programming 2021年1月26日星期 Page 8 动态规划基本原理是将一个问题的最优解转化为求子问题的最 优解,研究的对象是决策过程的最优化,其变量是流动的时间 或变动的状态,最后到达整个系统最优。 基本原理一方面说明原问题的最优解中包含了子问题的最优解, 另一方面给出了一种求解问题的思路,将一个难以直接解决的 大问题,分割成一些规模较小的相同子问题,每一个子问题只 解一次,并将结果保存起来以后直接引用,避免每次碰到时都 要重复计算,以便各个击破,分而治之,即分治法,是一种解 决最优化问题的算法策略。 动态规划求解可分为三个步骤:分解、求解与合并
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 8 动态规划基本原理是将一个问题的最优解转化为求子问题的最 优解，研究的对象是决策过程的最优化，其变量是流动的时间 或变动的状态，最后到达整个系统最优。 基本原理一方面说明原问题的最优解中包含了子问题的最优解， 另一方面给出了一种求解问题的思路，将一个难以直接解决的 大问题，分割成一些规模较小的相同子问题，每一个子问题只 解一次，并将结果保存起来以后直接引用，避免每次碰到时都 要重复计算，以便各个击破，分而治之，即分治法，是一种解 决最优化问题的算法策略。 动态规划求解可分为三个步骤：分解、求解与合并。 8.1 动态规划数学模型 Mathematical Model of DP
第8章动态规划 电气信息学院 8.1动态规划数学模型 Dynamic Programming 佃松宜、李彬、曾晓东 Mathematical model of dp 2021年1月26日星期 Page 9 8.12基本概念 (1)阶段( Stage):表示决策顺序的时段序列,阶段可以按时间 或空间划分,阶段数k可以是确定数、不定数或无限数 (2)状态( State):描述决策过程当前特征并且具有无后效性 的量。状态可以是数量,也可以是字符,数量状态可以是连续的, 也可以是离散的。每一状态可以取不同值,状态变量记为s各 阶段所有状态组成的集合称为状态集。 (3)决策( Decision)xk:从某一状态向下一状态过度时所做的 选择。决策变量记为x,xk是所在状态的函数。 在状态sk下,允许采取决策的全体称为决策允许集合,记为DA(SA)。 各阶段所有决策组成的集合称为决策集
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 9 （1）阶段(Stage)：表示决策顺序的时段序列，阶段可以按时间 或空间划分，阶段数k可以是确定数、不定数或无限数 8.1.2基本概念 （3）决策（Decision）xk：从某一状态向下一状态过度时所做的 选择。决策变量记为xk，xk是所在状态sk的函数。 在状态sk下，允许采取决策的全体称为决策允许集合，记为Dk (sk )。 各阶段所有决策组成的集合称为决策集。 （2）状态（State）：描述决策过程当前特征并且具有无后效性 的量。状态可以是数量，也可以是字符，数量状态可以是连续的， 也可以是离散的。每一状态可以取不同值，状态变量记为sk。各 阶段所有状态组成的集合称为状态集。 8.1 动态规划数学模型 Mathematical Model of DP
第8章动态规划 电气信息学院 8.1动态规划数学模型 Mathematical model of Dp Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期 Page 10 (4)策略( Strategy):从第1阶段开始到最后阶段全过程的决策构成 的序列称为策略,第k阶段到最后阶段的决策序列称为子策略。 (5)状态转移方程( State transformation function):某一状态以 及该状态下的决策,与下一状态之间的函数关系,记为 k+ T(Sktp (6)指标函数或收益函数( Return function):是衡量对决策过 程进行控制的效果的数量指标,具体可以是收益、成本、距离 等指标。分为k阶段指标函数、k子过程指标函数及最优指标函 数
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 10 (4) 策略(Strategy)：从第1阶段开始到最后阶段全过程的决策构成 的序列称为策略，第k阶段到最后阶段的决策序列称为子策略。 （5）状态转移方程(State transformation function)：某一状态以 及该状态下的决策，与下一状态之间的函数关系，记为 sk+1=T(sk ,xk ) （6）指标函数或收益函数(Return function)：是衡量对决策过 程进行控制的效果的数量指标，具体可以是收益、成本、距离 等指标。分为k阶段指标函数、k子过程指标函数及最优指标函 数。 8.1 动态规划数学模型 Mathematical Model of DP