动态规划及其应用课件

《动态规划及其应用课件》由会员分享，可在线阅读，更多相关《动态规划及其应用课件（92页珍藏版）》请在金锄头文库上搜索。

1、1,动态规划及其应用,2,第四章 动态规划及其应用,【学习目标】 知识目标 1.了解动态规划的作用与意义以及在实际中的应用 2.掌握动态规划的基本方法以及动态规划的建模 3.掌握动态规划是规划论的一个重要分支，理解它与传统的解题不同方法； 4.掌握动态规划的顺序及逆序解法。,3,能力目标 1. 能够结合实际情况建立动态规划模型 ，把一个复杂的问题，划分为一系列小问题，以便通过解这些小问题来求得全部问题的解决 2. 能够应用顺序及逆序解法求解简单的投资分配问题、货物配装问题、最短路径问题以及生产与存储问题,4,【项目导入】,机械挖掘金矿问题 两个金矿A,B分别有存储量x，y，现有一部开矿机器。

2、如果开采金矿A，则以概率P1得储量x的r1倍（0 r11），并且机器没有损坏，可以继续再去开采金矿A或B。同时又以概率1- P1宣告失败，机器报废，也得不到金子； 如果把这部开矿机器用以开采金矿B，则以概率P2得到储量y的r2倍（0r21），并且机器没有损坏，可以继续再去开采金矿A或B，同时又以概率1- P2宣告失败，机器报废，也得不到金子。 把机器用于开采金矿A或者B，如果机器没有损坏，将继续把机器用于开采金矿A或者B，直到机器损坏，问应该如何选择开矿的序列使获得金子的期望值最大。 讨论题： 1. 运筹学的产生是不是属于偶然现象？ 2. 运筹学与物流的结合应用中间有什么必然联系？,5,动态规

3、划是解决多阶段决策过程最优化问题的一种方法。 该方法在工程技术、企业管理、物流规划与管理以及军事等部门都有广泛的应用，并取得了显著的效果。 在物流管理中，动态规划可以解决最优路径问题、生产计划与库存、资源分配问题、装载排序、投资及生产过程的最优控制等问题。 它的独特解题思路，在处理某些优化问题时，比线性规划或非线性规划方法更有效。 动态规划的优点是可把一个N维优化问题化成N个一维优化问题求解；求得最优解以后，可得所有子问题的最优解。 动态规划的缺点是没有统一的处理方法，不同的问题具有不同的模型，采用不同的求解方法，而且求解技巧要求比较高；状态变量维数不能太高，一般情况下变量维数小于10。,6,

4、任务一：动态规划问题概述,动态规划是把多阶段决策问题作为研究对象。 所谓多阶段决策是指可将问题求解的全过程划分为若干个互相联系的阶段 (即将问题划分为许多个互相联系的子问题)，在它的每一阶段都需要作出决策，并且在一个阶段的决策确定以后再转移到下一个阶段。 在决策过程中，往往前一个阶段的决策要影响到后一阶段的决策，从而影响整个过程。 这类把一个问题划分成若干个相互联系的阶段并选取其最优策略的问题就是多阶段决策问题。,7,一、动态规划问题提出,1951年，美国数学家贝尔曼（RBellman，19201984）研究了一类多阶段决策问题的特征，提出了解决这类问题的基本原理。在研究、解决了某些实际问题的

5、基础上，他于1957年出版了动态规划这一名著。本章将简要介绍动态规划的思想方法及其应用。 由于动态规划与“时间”关系很密切，随着时间过程的发展而决定各阶段的决策，产生一个决策序列，这就是“动态”的意思。 然而它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时间”因素，将问题看成多阶段的决策过程即可。,动态规划解决问题的基本思路：把整体比较复杂的大问题划分成一系列较易于解决的小问题，通过逐个求解，最终取得整体最优解。 这种“分而治之，逐步调整”的方法，在一些比较难以解决的复杂问题中已经显示出优越性。 在经济管理决策中，有些管理决策问题可以按时序或空间演变划分成多个阶段 ，呈现出明显的阶

6、段性； 于是可把这类决策问题分解成几个相互联系的阶段，每个阶段即为一个子问题； 原有问题的求解就化为逐个求解几个简单的阶段子问题； 每个阶段的决策一旦确定，整个决策过程也随之确定，此类问题称为多阶段决策问题。,9,二、动态规划的基本概念,动态规划数学模型由阶段、状态、决策与策略、状态转移方程及指标函数等5个要素组成。 为了理解动态规划的解题思路，,10,1.动态规划决策过程划分,根据多阶段决策过程的时间参量是离散的还是连续的，动态规划过程可分为：离散决策过程与连续决策过程； 根据决策过程的演变是确定性的还是随机性的，可分为：确定性、随机性的决策过程。 这样组合起来就有离散确定性、离散随机性、连

7、续确定性、连续随机性 四种决策过程模型。 有些决策过程的阶段数是固定的，称为定期的决策过程， 有些决策过程的阶段数是不固定的或可以有无限多阶段数，分别称为不定期或无期的决策过程。,11,例4.1 线性规划问题,max f (X1,X2)8 X1 9 X2,s.t,这个问题的求解很简单，直观处理便可以找出最这个问题的求解很简单，直观处理便可以找出最优解，因为目标函数为X1， X2的线性函数，且系数均为正值， X2的系数比X1的系数大，所以最优解中的X2 的取值要尽量大，X1 取值要相对较小，再分析约束条件，得： X10， X2 6 目标函数最优值为： Fmax f(X1， X2) 54。,12,

8、运用动态规划的方法来处理这个问题,从形式上我们把问题分解为两个子问题，每次只考虑一个变量。 第一阶段，从形式上考虑X1，由约束条件（3.2）知,第一阶段的X1的取值范围应为：04X112， 其对目标函数的贡献为R18X1。 当第一阶段X1形式取值确定后，在下一阶段X2的变化范围是： 02 X2 124X1 在此基础上，在形式上考虑X2 ，它对目标函数的贡献为R29X2。,13,上面只是形式上考虑X1和X2，并没有说它们具体取何值，下面用回代过程来求解。 求解过程与分析过程相反，即把第二阶段作为计算的第一步。,S.t,第一步：把X1的取值作为参数，考虑子问题 max f19X2,这个问题当X2取

9、最大值时目标函数达到极大，因此最优解 为: X262X1 目标函数值为： F1Maxf19（62X1）,14,第二步：考虑子问题,Maxf28X1 F1 8X19（62X1）5410X1,S.t.,这个问题当X1取最小值时目标函数达到极大，因此最优解为：X10 目标函数值为：F2Max f254。 把X10 代入第一步中的 X2的表达式,得：X26 这个结果与前面直观处理计算是一致的。,15,2.动态规划的基本概念,1）阶段 (stage) 为能应用动态规划方法，首先必须根据实际问题所处的时间、空间或其他条件，把所研究的问题恰当地划分成若干个相互联系的阶段。 用k1，2，n，表示阶段序号，把k

10、 称为阶段变量。如例1分为二个阶段，则n2，k1，2。,16,2） 状态 (state),各阶段开始的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用Yk表示第k阶段的状态变量。 上例中记约束条件的右端的12为初始状态,即Y0 12. 它是第一阶段的输入状态。 Y1Y04X1 为第一阶段的输出状态，也是第二阶段的输入状态。 Y2Y12X1 为第二阶段的输出状态。Y2实际上相当于一般规划中的松弛变量。,17,动态规划中的状态具有如下性质：,在一个阶段中，可以有若干个状态，第k 段所有状态构成的集合，称为第k段状态集，记为Yk y k 。 当某阶段状态给定以后，在这阶段以后的过程的发展不受

11、这段以前各段状态的影响。 即：过程的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性。 如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。,18,3）决策（decision）,所谓决策，是指对某一阶段活动初从给定的状态出发，决策者面临若干个不同的行为方案或途径作出的一种选择。 由于实际问题千变万化，因而决策可以有形形色色的不同含义，很难言简而概全。 但无论如何，有一点则是肯定的，就是每段的决策都取决于该段的状态，它要随状态的变化而变化。 用xk 表示第 k 段的决策，称之为第 k 段决策变量；由于决策随状态而变，所以决策变量 xk是状态变量Yk的函数， 记为xkx

12、k (Yk)。 决策变量的取值一般都要受到一定条件的限制，我们把第k段决策变量的允许取值范围称为第k 段允许决策集合， 记为Xk(Yk)，于是xk (Yk) Xk(Yk) .,19,4）状态转移方程,能否成功地应用动态规划方法，重要条件之一，就是所设状态变量和决策变量必须满足： Yk和Xk，的取值一经确定，则下一段状态变量Yk+1的取值规律也能随之确定， 就是说，Yk+1与Yk和Xk之间必须能够建立一种明确的数量对应关系。 在动态规划中本阶段的状态往往是上一阶段的决策结果。 如果给定了第k段的状态Yk ，则第k+1段的状态Yk+1由公式： Yk+1 = Tk（YK，Xk+1） 确定 这种明确的

13、数量关系称为状态转移方程。,20,5）策略 (policy),在多阶段决策过程中，每一阶段均有一个决策，依序组合成一个全过程的决策序列，称为全过程策略，简称策略，记为p1(y1)，有： p1(y1) =x1(y1)，x2(y2)，, xn(yn)， 简记p1 =x1，x2，, xn 从过程的某个阶段开始到最终阶段结束称为后部子过程。从第k阶段开始的后部子策略称为第k子过程策略。 pk(yk) =xk(yk)，xk+1(yk+1),，xn(yn) ， 简记pk=xk，xk+1，, xn 每一阶段有若干状态，每个状态又有若干个不同的决策，即有许多策略可供选择。全体策略构成允许策略集合Pk(yk)。

14、 能使预期目标达到最优效果的策略称为最优策略P*k， 构成最优策略的各决策称为相应阶段的最优决策x*k。,21,6）指标函数,指标函数有阶段的指标函数和过程的指标函数之分。 阶段的指标函数是对应某一阶段状态和从该状态出发的一个阶段的决策效果的优劣的数量指标，称为阶段指标函数Vk ， 阶段指标是状态变量和相应决策变量的函数， 即 Vk = Vk (Yk , xk )。 过程的指标函数是指从第k阶段的状态Yk出发到最后阶段结束，各阶段绩效综合起来反映这个后部子过程的绩效，称为过程指标函数，记为Vk,n 。 Vk,n的大小取决于从第k阶段到最后阶段所采取的子策略。 即 Vk,n = Vk,n (yk

15、，xk , yk+1，xk+1 , yn),22,根据实际问题的性质，指标函数Vk,n 可以是各个阶段指标的和或积。 最优指数函数是指对从状态yk出发某一确定状态选取最优策略后得到的指标函数值，是对应某一最优子策略的某种效益度量。 （这个度量值可以是产量、成本、距离等）。 对应于从状态Yk 出发的最优子策略的效益值记作fk(Yk),于是有 fk(Yk) = optVk,n = opt vk(yk , xk ) + fk+1(yk+1) 其中，opt 表示最优化，根据具体含义 可以求最大（max）或求最小（min）。,23,三、动态规划算法的基本步骤,设计一个标准的动态规划算法,通常可按以下几个

16、步骤进行： 1划分阶段：按照问题的时间或空间特征, 把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的(即无后向性)，否则问题就无法用动态规划求解。 2选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。,24,3确定决策并写出状态转移方程：之所以把这两步放在一起，因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以,如果我们确定了决策, 状态转移方程也就写出来了。但事实上,我们常常是反过来做, 根据相邻两段的各状态之间的关系来确定决策。 4写出规划方程(包括边界条件)，动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。,25,动态规划方法的基本思路总结如下, 将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量，定义最优指标函数，从而把问题化成一簇同类型的子问题，然后逐个求解。 求解时从边界条件开