西南科技大学网络教育系列课程 数学建模与数学实验 第7讲 动态规划 主讲教师: 彭煜 杨学南 西南科技大学理学院数学系.

Slides:



Advertisements
Similar presentations
2 和 5 的倍数的特征 运动热身 怎样找一个数的倍数? 从小到大写出 2 的倍数( 10 个): 写出 5 的倍数( 6 个) 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 5 , 10 , 15 , 20 , 25 , 30.
Advertisements

一、 一阶线性微分方程及其解法 二、 一阶线性微分方程的简单应用 三、 小结及作业 §6.2 一阶线性微分方程.
第五节 函数的微分 一、微分的定义 二、微分的几何意义 三、基本初等函数的微分公式与微分运算 法则 四、微分形式不变性 五、微分在近似计算中的应用 六、小结.
2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
第八章 第四节 机动 目录 上页 下页 返回 结束 一个方程所确定的隐函数 及其导数 隐函数的微分法.
2.6 隐函数微分法 第二章 第二章 二、高阶导数 一、隐式定义的函数 三、可微函数的有理幂. 一、隐函数的导数 若由方程 可确定 y 是 x 的函数, 由 表示的函数, 称为显函数. 例如, 可确定显函数 可确定 y 是 x 的函数, 但此隐函数不能显化. 函数为隐函数. 则称此 隐函数求导方法.
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
第二节 换元积分法 一、第一类换元积分 法(凑微分法) 二、第二类换元积分法. 问题 解决方法 利用复合函数,设置中间变量. 过程令 一、第一类换元积分法(凑微分法)
全微分 教学目的:全微分的有关概念和意义 教学重点:全微分的计算和应用 教学难点:全微分应用于近似计算.
§3.4 空间直线的方程.
《解析几何》 -Chapter 3 §7 空间两直线的相关位置.
3.4 空间直线的方程.
运 筹 学 “运筹学”课题组.
第五章 二次型. 第五章 二次型 知识点1---二次型及其矩阵表示 二次型的基本概念 1. 线性变换与合同矩阵 2.
一、二阶行列式的引入 用消元法解二元线性方程组. 一、二阶行列式的引入 用消元法解二元线性方程组.
第4章动态规划 (Dynamic Programming)
(Dynamic programming)
《高等数学》(理学) 常数项级数的概念 袁安锋
恰当方程(全微分方程) 一、概念 二、全微分方程的解法.
高等数学电子教案 第五章 定积分 第三节 微积分基本定理.
第五节 微积分基本公式 、变速直线运动中位置函数与速度 函数的联系 二、积分上限函数及其导数 三、牛顿—莱布尼茨公式.
一、原函数与不定积分 二、不定积分的几何意义 三、基本积分公式及积分法则 四、牛顿—莱布尼兹公式 五、小结
第二节 微积分基本公式 1、问题的提出 2、积分上限函数及其导数 3、牛顿—莱布尼茨公式 4、小结.
第5章 定积分及其应用 基本要求 5.1 定积分的概念与性质 5.2 微积分基本公式 5.3 定积分的换元积分法与分部积分法
定积分习题课.
第三节 格林公式及其应用(2) 一、曲线积分与路径无关的定义 二、曲线积分与路径无关的条件 三、二元函数的全微分的求积 四、小结.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
第二章 导数与微分 第二节 函数的微分法 一、导数的四则运算 二、复合函数的微分法.
第三章 导数与微分 习 题 课 主要内容 典型例题.
2-7、函数的微分 教学要求 教学要点.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
4 动 态 规 划 教学目的与要求 通过对本章的学习,使学生对多阶段决策问题的产生发展和研究现状有基本的了解,对动态规划在现代物流管理中的运用有较全面的认识,了解动态规划方法的含义及其基本特点,明确动态规划模型的基本思想,掌握动态规划的基本概念和动态规划模型的建立,掌握求解动态规划问题的逆序递推法和顺序递推法,能够将动态规划的方法应用在现代物流管理实践中。
§3.7 热力学基本方程及麦克斯韦关系式 热力学状态函数 H, A, G 组合辅助函数 U, H → 能量计算
第二章 矩阵(matrix) 第8次课.
第4章 非线性规划 一维搜索方法 2011年11月.
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
第一章 函数 函数 — 研究对象—第一章 分析基础 极限 — 研究方法—第二章 连续 — 研究桥梁—第二章.
动态规划(Dynamic Programming)
动态规划 本章内容重点 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例.
第八模块 复变函数 第二节 复变函数的极限与连续性 一、复变函数的概念 二、复变函数的极限 二、复变函数的连续性.
第4章 非线性规划 4.5 约束最优化方法 2019/4/6 山东大学 软件学院.
第一章 函数与极限.
§1 图与网络的基本概念 §2 树图与最小生成树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题
Partial Differential Equations §2 Separation of variables
实数与向量的积.
3.8.1 代数法计算终点误差 终点误差公式和终点误差图及其应用 3.8 酸碱滴定的终点误差
线性规 Linear Programming
概 率 统 计 主讲教师 叶宏 山东大学数学院.
第5章 动态规划 5.1, 5.2 多阶段决策和最优化原理 2019/5/1.
第16讲 相似矩阵与方阵的对角化 主要内容: 1.相似矩阵 2. 方阵的对角化.
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
概 率 统 计 主讲教师 叶宏 山东大学数学院.
第三章 函数的微分学 第二节 导数的四则运算法则 一、导数的四则运算 二、偏导数的求法.
1.非线性规划模型 2.非线性规划的Matlab形式
数学建模方法及其应用 韩中庚 编著.
2.2矩阵的代数运算.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
2.2直接证明(一) 分析法 综合法.
导 言 经济学的基本问题 经济学的基本研究方法 需求和供给.
2019/5/20 第三节 高阶导数 1.
正弦、余弦函数的性质 华容一中 伍立华 2017年2月24日.
§2 方阵的特征值与特征向量.
§7.3 离散时间系统的数学 模型—差分方程 线性时不变离散系统 由微分方程导出差分方程 由系统框图写差分方程 差分方程的特点.
9.5空间向量及其运算 2.共线向量与共面向量 淮北矿业集团公司中学 纪迎春.
我们能够了解数学在现实生活中的用途非常广泛
第十七讲 密码执行(1).
《偏微分方程》第一章 绪论 第一章 绪论 1.1.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
3.3.2 两点间的距离 山东省临沂第一中学.
Presentation transcript:

西南科技大学网络教育系列课程 数学建模与数学实验 第7讲 动态规划 主讲教师: 彭煜 杨学南 西南科技大学理学院数学系

第7章 动态规划 动态规划是解决多阶段决策过程最优化问题的一种数学方法.动态规划在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用,而且由于动态规划方法有其独特之处,在解决某些实际问题时,显得更加方便有效。 由于决策过程的时间参数有离散的和连续的情况,故决策过程分为离散决策过程和连续决策过程.本部分内容主要介绍离散决策过程,通过几个类型的问题来说明用动态规划处理问题的方法,但所建立的概念、理论和方法,具有相当的重要性.

7.1 动态规划的基本方法 7.1.1 多阶段决策过程及实例 在生产和科学实验中一类活动的过程,由于它的特殊性,可将其分为若干个互相联系的阶段,在它的每一个阶段都需要作出决策,从而使整个过程达到最好的活动效果.因此,各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又给以后的发展施以影响.当各个阶段决策确定后,就组成了一个决策序列,因而也就决定了整个过程的一条活动路线,这样一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,也称序贯决策过程。

在多阶段决策问题中,各个阶段采取的决策一般来说是与时间有关的,决策依赖于当前的状态,而又随即引起状态的转移,一个决策序列就是在状态的运动变化中产生的,故有“动态”的含义。因此,把处理它的方法称为动态规划方法。但有一些与时间没有关系的静态规划问题,只要人为地引进“时间”因素,也可把它视为多阶段决策问题,从而用动态规划方法去处理。

例(生产-存贮问题)某工厂根据市场调研情况,需制定今后四个月的生产计划,据估计,在这四个月内,市场对该产品需求量如下表所示.

此外,各种资源(人力、物力)分配问题、背包问题、购货问题、水库调度问题等等,也都具有多阶段决策问题的特性. 假定生产每批产品的固定成本费用为3千元,每单位产品生产成本费用为1千元,库存费用每月为0.5千元.并且规定四月初和4月末均无产品库存,试求该厂如何安排各个月的生产与库存,使总成本费用最小. 此外,各种资源(人力、物力)分配问题、背包问题、购货问题、水库调度问题等等,也都具有多阶段决策问题的特性.

教材上例1的最短路线问题是动态规划中一个较为直观的典型例子.我们通过讨论它的解法来说明动态规划方法的基本思想,并阐述它的基本概念. 7.1.2 动态规划的基本概念和基本方程 教材上例1的最短路线问题是动态规划中一个较为直观的典型例子.我们通过讨论它的解法来说明动态规划方法的基本思想,并阐述它的基本概念. 如教材图7—1所示的线路网络,明显地,从A点到G点可分为6个阶段.从A到B为第一阶段,从B到C为第M阶段,…,从F到G为第六阶段.在第一阶段中A为起点,终点有B1、B2二个,因而这时走的路线有两个选择,若我们选择走到B2的决策,则B2就是我们选择的决策结果.

在第二阶段,从B2出发,对应于B2就有一个可供选择的终点集合{C2,C3,C4},若选择B2到C2为第二阶段的决策,则C2就是第二阶段的终点,同时又是第三阶段的始点.类似地递推下去,我们看到各个阶段的决策不同所走的路线就不同,因而整个路线的长短也不同.问题的要求是在各个阶段选取一个恰当的决策,使由这些决策所决定的一条路线,其总路程最短.

若我们采取穷举法.即把由 A到G共有条不同的路线都算出来,比较48条不同路线的最短距离,最短距离为18,找出相应的最短路线为 l.动态规划的基本概念 (1)阶段 把所给问题的过程,恰当地划分为若干个相互联系的阶段,以便于求解.通常用k表示阶段变量.如例1可分为6个阶段来求解.

(2)状态 状态表示在任一阶段所处的位置.通常一个阶段有若干个状态.描述状态的变量称为状态变量.参数表示第k阶段的状态变量.如在例1中第三阶段有四个状态,则状态变量 可取四个值,即C1,C2,C3,C4,点集合{C1,C2,C3,C4}就称为第三阶段的可能状态集合,记为S3= {C1,C2,C3,C4}。 (3)决策 在某一阶段,当状态给定后,往往可以作出不同的决定,从而确定下一阶段的状态,这种决定称为决策.描述决策的变量称为决策变量,用 表示第阶段当状态为Sk时的决策变量,它是状态Sk的函数.决策变量的变化范围称为允许决策集合.通常以 表示第k阶段状态为Sk时的允许决策集合.显然有

(4)状态转移方程 状态转移方程描述由一个状态到另一个状态的演变过程.用 表示,它表示 k阶段与k+1阶段状态的变换规律.如在例1第二阶段中,若从状态B1出发,就可作出三种不同的决策,其允许决策集合 若选取的点为C2,则C2是状态B1在决策 作用下的一个新的状态,记作

(5)策略 由过程的第k阶段开始到终点为止的过程,称为问题的后部子过程,由每段的决策组成的决策函数序列 就称为子过程的策略,简称子策略,记为 当k=1时,则此决策函数序列称为全过程的一个策略,简称策略,记为

在实际问题中,由于每个阶段都有若干个状态,针对每一个状态又有多种不同的决策,从而组成了不同的决策函数序列,即存在许多策略可供选择这种可供选择的策略范围,称为允许策略集合,用P表示.从允许策略集合中找出使问题达到最优效果的策略称为最优策略. (6)指标函数和最优指标函数值 指标函数(又称目标函数)是用来衡量所实现过程优劣的一种数量指标,它是定义在过程上的数量函数,用 表示:

当初始状态给定时,过程的策略就确定了,因而指标函数也就确定,故指标函数是初始状态和策略的函数,即 阶段指标(又称阶段效益)是衡量该段决策效果的数量指标,用 表示在第k阶段 由状态 和决策所得的效益 ,它表示从第k阶段由状态 的最优值,称为最优指标函 数值,记为 指标函数 它表示从第k阶段由状态 出发到过程结束时所获得的最优指标函数值.

在不同的问题中,指标的含义是不同的,可能是距离、利润、资源消耗等.如在最短路线问题中, 表示从第 k阶段的点 Sk至终点 G的距离; 表示由点 Sk到 G的最短距离,用 表示在第k阶段由点sk到点 的距离. 如在第5段中由点E1 到F1的距离为3就记为

2.动态规划的基本思想和基本方程 现在,我们结合解决最短路线问题来介绍动态规划方法的基本思想.最短路线有一个重要特性,即如果从起点到终点的最短路线在第k站通过点 ,则由点 出发到达终点的所有可能选择的不同路线来说,必定也是最短的. 最短路线的这一特性,启发我们找最短路线的方法,那就是从最后一段开始,由后向前逐步递推,求出各点到G点的最短路线,最后就求得由A点到G点的最短路线.所以动态规划的方法是从终点逐段向始点寻找最短路线的一种方法. 下面我们按照动态规划的方法,将例1从最后一段开始计算,由后向前逐步推移至A点.

当k=5时,出发点有El,E2,E3三个.若从E1出发,则有两个选择,一是至Fl,一是至F2,所以 当k=6时,由F1到终点G只有一条路线,故 ,同理, 当k=5时,出发点有El,E2,E3三个.若从E1出发,则有两个选择,一是至Fl,一是至F2,所以 . . 这说明,其最短路线是 而相应的决策为

同理,从E2和E3出发,则有 其最短路线是 其最短路线是

完全类似地,可算得如下结果: 当k=4时,有 当k=3时,有 当k=2时,有

再按计算顺序反推之,可得最优决策函数序列 当k=l时,出发点只有一个A点,则 至此,求得图7一1的最短路线为 相应的最短路为18. ,即由 再按计算顺序反推之,可得最优决策函数序列 ,即由 组成一个最优策略.

从最短路线问题例子的计算过程中,我们可以看到,用动态规划方法求解问题的关键,在于正确地写出k阶段与k+l阶段之间的速推关系式: (或写成 ) 和边界条件 一般地,k阶段与k+l阶段的递推关系式可写为 : 边界条件为 其中“opt”是Optimzation(最优化)的缩写.可根据题意选取min或max.这种递推关系式称为动态规划的函数基本方程.

7.2 最优化原理与最优性定理 20世纪50年代,R.Bellman等人根据研究一类多阶段决策问题,提出了“最优化原理”作为动态规划的理论基础.长期以来,人们一直沿用这一提法.动态规划原理的内容是,“作为整个过程的最优策略具有这样的性质:即无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略.” 后来,随着人们深入地研究动态规划,认为动态规划基本方程在动态规划理论中具有更为基础的作用.反映动态规划基本方程的最优性定理是策略最优性的充要条件,而最优化原理是策略最优性的必要条件,它仅是最优性定理的推论而已.

最优性定理: 设阶段数为n的多阶段决策过程,其阶段编号为k=0,1,2,…,n-1允许策略 是最优策略的充要条件是对任意一个k(0<k<n-1) 和初始状态 有 其中,

它是由初始状态s0和子策略 所确定的k阶段状态, 是状态转移方程.. 是最优策略, 推论: 若允许策略 则对任意的k(0<k<n-l),它的子策略 对于以 为起点的k到n-1子过程来说,必是最优策略 (注意:k段状态 所确定的) 是由S0和 此推论就是最优化原理所谈的内容.关于定理和推论的证明从略.

把一个实际问题化为能用动态规划的方法来求解,首先要做的是根据题意把它构造成动态规划的数学模型.构造动态规划模型的步骤为: 7.3 构成动态规划模型的条件 把一个实际问题化为能用动态规划的方法来求解,首先要做的是根据题意把它构造成动态规划的数学模型.构造动态规划模型的步骤为: 一、将实际问题恰当地划分为若干个阶段,一般是根据时间和空间的自然特征而划分,但要便于能把问题的过程转化成多阶段决策的过程.

二、正确地选择状态变量 ,使它既能描述过程的演变特征,又要满足无后效性(马尔可夫性).所谓“无后效性”是指:如果某段状态结定,则在这段以后过程的发展只与当前的状态有关,而与过去的历史无关.若选择状态变量不满足无后效性的要求,则就不能唯一确定下段的状态及其最优指标函数. 三、确定决策变量 及每段的允许决策集合 三、确定决策变量

四、正确写出状态转移方程 五、正确列出指标函数关系 ,并要求满足 递推性。 正确的指标函数关系要满足三点: 1.它是定义在过程上的数量函数; 2.要有可分离性并满足推关系,即 的函数,记为 可以表示为

3. 对其变元 来说严格单调。 常见的指标函数是取各段指标和的形式,即:

其中, 表示初始状态为 时的后部子过程所有子策略中的最优子策略。

7.4动态规划的递推方法 在上节已看到,动态规划方法的关键在于正确写出动态规划的递推关系式,而动态规划的递推方式有逆推和顺推两种形式,一般地,当初始状态给定时,用逆推比较方便,当终止状态给定时,用顺推比较方便。 7.4.1 逆推解法 ,并假定最优值函数 设已知初始状态 是以s为初始状态,从k阶段到n阶段所 得到的最大效益。

首先从第n 阶段开始,对任意输入参数 ,则此阶段最大效益为 这里 是由状态 所确定的第n阶段的允许决策集合。解此一维极值问题,得到最优值 及最优解 它就是当第n阶段的初始状态为 时的最优决策。

然后,进入第n-1阶段,则最大效益为 其中 。解此一维极值问题, 得到最优解 ,就是当第n-1阶段的输入为 时的最优决策。 如此类推,直到第一阶段,得到最大效益为

其中 ,解之,得到最优解 在上述逆推过程中,我们逐步求出了极值函数 及相应决策函数 由于初始状态 是已知的,按照上述递推过程相反的顺序推算,就可逐步确定出每一阶段的决策及效益。 综上所述,整个过程包括两个步骤,前一步骤称为“迭代”或“递推”,后一步骤称为“回代”。

例: 求 在满足约束条件 之下,使函数 达到最大值。 这个例子可有用初等方法或微分学方法求出它的最优解,现在用动态规划方法来求解。按变量划分阶段,可把它看作一个三阶段决策问题,决策变量分别为 设初始状态 ,状态转移函数为 ,各阶段的效益 按乘法结合起来,

。因此从最后一阶段开始,依次列出极值函数不清的递推关系为 设 然后,可逐步求出各阶段的最优值及最优解, 显然有 及最优解 接着可求出(如用微分法) 及最优解

及最优解 ,进行回代运算, 由于已知初始状态 得 , 由此得到最优策略 最大值

上述递推过程为求极值问题提供了一条新的途径,把n 维极值问题化为n 个前后关联的一维极值问题,这正是动态规划方法的基本特征。 7.4.2 顺推解法

由于终止状态 是已知的,所以回代过程从 开始,按上述过程相反的顺序,就可以逐步确定出每阶段的决策及效益,从而得到整个问题的最优策略。

通过上面的讨论,对如何恰当地运用动态规划中的逆推和顺推方法有了比较明确的了解。至于当初始状态和终止状态都已知时,顺推和逆推都可以进行,应视具体情况而定。 注意理解教材中例2的计算方法,它对我们用动态规划的方法去解某些非线性规划问题的思路是有启发的。

7.5 动态规划模型举例 畜牧领域的资源分配问题 :