运筹学 Operations Research 气走到看制EA 第八章动态规划 Dynamic Programming ③本章篇目 8.1动态规划数学模型 Mathematical model of dp 82资源分配问题 Resource assignment problem 83生产与存储问题 Production and inventory problem 84背包问题 Knapsack problem 8.5其它动态规划模型 Other model ofdm
第八章 动态规划 Dynamic Programming 8.1 动态规划数学模型Mathematical Model of DP 8.2 资源分配问题 Resource Assignment Problem 8.3 生产与存储问题Production and inventory problem 8.4 背包问题 Knapsack Problem 8.5 其它动态规划模型 Other Model of DP 运筹学 Operations Research
8.1动态规划数学模型 Mathematical model of dp
8.1 动态规划数学模型 Mathematical Model of DP
【例8-1】最短路径问题图8-1表示从起点A到终点 E之间各点的距离。求A到E的最短路径。 Min{2+5,8+86+4}=7 v2 14 19 0 128 阶段」第1阶段」第2阶段」第3阶段」第4阶段第5阶段 图8-1
v2 v3 v4 v7 v5 v9 v6 v8 v10 2 8 5 12 13 10 7 10 13 11 2 8 6 5 8 8 5 4 0 5 8 4 7 【例8-1】最短路径问题 图8－1表示从起点A到终点 E之间各点的距离。求A到E的最短路径。 图8－1 v1 阶段： 第1阶段 第2阶段 第3阶段 第4阶段 第5阶段 12 17 14 20 19 Min{2+5,8+8,6+4}=7
8.1动态规划数学模型 第8章动态规划 电气信息学院 Mathematical model of Dp Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期 Page 4 用 Win QsB软件计算时,需要对状态重新编号,如下图所示 4 阶段」第1阶段」第2阶段」第3阶段」第4阶段第5阶段 图8-2
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 4 2 3 4 7 5 9 6 8 10 2 8 5 12 13 10 7 10 13 11 2 8 6 5 8 8 5 4 图8－2 1 阶段： 第1阶段 第2阶段 第3阶段 第4阶段 第5阶段 用WinQSB软件计算时,需要对状态重新编号,如下图所示. 8.1 动态规划数学模型 Mathematical Model of DP
8.1动态规划数学模型 第8章动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 Mathematical model of Dp 2021年1月26日星期 Page 5 用 Win QsB软件计算时,当某状态没有路到下阶段某状态时,添加 条虚拟决策(线条),距离很大,如下图点3到点5 12 13 8 10 10 4 4
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 5 1 2 3 4 8 5 7 6 9 10 2 8 5 12 13 10 M 10 4 13 11 11 2 8 6 5 8 8 6 4 用WinQSB软件计算时,当某状态没有路到下阶段某状态时，添加 一条虚拟决策（线条），距离很大，如下图点3到点5. 8.1 动态规划数学模型 Mathematical Model of DP
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