《运筹学09-动态规划》由会员分享，可在线阅读，更多相关《运筹学09-动态规划（127页珍藏版）》请在金锄头文库上搜索。
1、第十章 动态规划10.1 多阶段决策问题 10.2 动态规划的基本概念和基本方程 10.3 动态规划的建模与求解方法 10.4 动态规划应用举例n动态规划(dynamic programming)是运筹学的一个分支 ，是求解决策过程(decision process)最优化的数学方法 。20世纪50年代初美国数学家R.E.Bellman等人在研究 多阶段决策过程(multistep decision process)的优化问 题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题， 逐个求解，创立了解决这类过程优化问题的新方法 动态规
2、划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。n动态规划问世以来，在经济管理、生产调度、工程技术 和最优控制等方面得到了广泛的应用。例如最短路线、 库存管理、资源分配、设备更新、排序、装载等问题， 用动态规划方法比用其它方法求解更为方便。10.1 多阶段决策问题n多阶段决策过程，是指这样的一类特殊的活动过程，问 题可以按时间顺序分解成若干相互联系的阶段，在每一 个阶段都要做出决策，全部过程的决策是一个决策序列 。要使整个活动的总体效果达到最优的问题，称为多阶 段决策问题。n决策:在多个可行方案中选择或选定一个的过程或行为;n策略:由一系列相互衔接的
3、决策构成的决策序列;n策略集合:有可供选择的策略构成的集合;n最优策略:在预定标准下达到最好效果的策略.l静态决策 一次性决策l动态决策 多阶段决策决策s1s2vu输入决策输出决策效应第一月s1s2v1u1第二月s3v2u2第三月s4v3u3例例1 1给定一个线路网络图给定一个线路网络图, ,两点之间联线上的数字两点之间联线上的数字 表示两点间的距离表示两点间的距离( (或运费或运费), ),试求一条由试求一条由s s到到t t的铺管的铺管 线路线路, ,使总距离最短使总距离最短. .adbetcfs97 5784 56 46547例2 某公司拟将50万元资金投放下属A、B、C三 个部门，各部
4、门在获得资金后的收益如表所示 ，求总收益最大的投资分配方案（投资数以10 万元为单位）。投放资金(万元)01020304050收益 （万元） A01520252830B0010254570C01020304050n例3 已知货物的单位重量i，单位体积i及价值 pi如表所示，船的最大载重能力为W5，最大装 载体积为V8，求最优装载方案。 iiipi11230234803236510.2 动态规划的基本概念和基本方程(1) 动态规划的基本概念n阶段与阶段变量:n将所要研究的问题,按时间或空间特征分成若 干个互相联系的阶段.简称“阶段”n我们就是要按阶段的顺序来求解.n描述阶段的变量阶段变量,常用字
5、母k来表示;n状态、状态变量和状态集合n各阶段开始时的客观条件叫做状态.n描述各阶段状态的变量叫做状态变量,常用sk表示 第阶段的状态变量； n状态变量sk的取值集合称为状态集合,用Sk表示；n动态规划中状态具有以下性质:某阶段状态一旦确 定以后过程的状态变化不受这个状态以前的影响, 也就是说某状态以后的过程和以前无关,只与当前 状态有关,我们称这种特性为“无后效性.” n决策、决策变量和策略n当个阶段的状态取定以后,就可以做出关于下一步 的选择,从而确定下一阶段的状态,这种决定称为决 策；n表示决策的变量叫做决策变量,常用uk(sk)表示.第k 阶段当状态为sk时的决策变量；n在实际问题中决
6、策变量的取值往往限制在一定的 范围内,我们称此范围为允许决策集,常用Dk(sk)表 示第k阶段从状态sk出发的允许决策集,因此有 uk(sk) Dk(sk).n各段决策确定后,整个问题的决策序列就构成了一 个策略,用P1,nu1(s1),u2(s2), ,un(sn)表示；n使整个问题达到最优效果的的策略就是最优策略.n动态规划中本阶段的状态是上一阶段的决策结果. 如果给定了第k阶段的状态sk,本阶段的决策就为 uk(sk),则第k+1段的状态uk+1也就完全确定了,它的 关系可表示为:sk+1=Tk(sk,uk).由于它表示了由k到 k=1段的状态转移规律,所以称为状态转移方程.T1s1s2
7、v1 (s1, u1)u1(s1 )T2s3v2 (s2 ,u2)u2 (s2)Tksksk+!vk (sk,uk)uk (sk)Tnsnsn+1vn (sn,un)un (sn)n指标函数与最优值函数n用于衡量所选定策略优劣的数量指标称为指标函 数.n阶段指标函数vk(sk,xk)n一个n段决策过程,从1到n叫作问题的原过程,对 于任意一个给定的k ,从第k 到n段的过程称为原 过程的一个后部子过程.V1,n(s1,p1,n)表示初始状态 s1采用策略p1,n.时原过程指标函数值. nVkn=(sk,xk,sk+1,xk+1, ,sn,xn) (k=1,2, ,n) nV1n=(s1,x1,
8、s2,x2, ,sn,xn)多段决策过程中从第k阶段到最终阶段的过程 称为k-后部子过程，简称k-子过程。 Tksksk+!vk (sk,uk)uk (xk)Tnsnsn+1vn (sn,un)un (xn)n指标函数应具有三个条件 q指标函数在全过程和所有后部子过程上有定义；q指标函数应具有可分离性，满足递推公式 Vkn=(sk,xk, Vkn+1( sk+1,xk+1, ,sn,xn)q函数是一个关于变量Vk+1 n单调递增的函数。n指标函数Vkn达到最优值，称为最优值函数。nfk(sk)=opt. Vkn (sk,xk,sk+1,xk+1, ,sn,xn) (k=1,2, ,n) n使指
9、标函数Vkn达到最优值的策略是从k开始的后部子 过程的最优策略，记作pkn*=uk*,un*,p1n*又是全过 程的最优策略，简称最优策略。 n指标函数的两种基本形式：nnn(2) 最优化原理最优化原理“最优策略具有的基本性质是：无论初始状 态和初始决策如何，对于前面决策所造成的某一 状态而言，下余的决策序列必构成最优策略”。AMBn最优性原理的含意n 最优策略的任何一部分子策略，也是相 应初始状态的最优策略。n 每个最优策略只能由最优子策略构成。n 显然，对于具有无后效性的多段决策过 程而言，如果按照k后部子过程最优的原则 来求各阶段状态的最优决策，那么这样构成 的最优决策序列或策略一定具有
10、最优性原理 所提示的性质。 (3)动态规划基本方程 多段决策过程的特点 每个阶段都要进行决策 相继进行的阶段决策构成的决策序列 前一阶段的终止状态又是后一阶段的初始状态 阶段最优决策不能只从本阶段的效应出发，必须通 盘考虑，整体规划。 阶段k的最优决策不应该只是本阶段效应的最优， 而必须是本阶段及其所有后续阶段的总体最优，即 关于整个k后部子过程的最优决策。多段决策过程中所要求解的是，从起始状态x1开 始，进行一系列的决策，使目标 V 达到最优最优目标值 V*最优策略使得目标达到最优的决策序列。最优路线在采取最优策略时，系统从s1开始所经过的状态 序列求解动态规划模型找到最优策略、最优路线和最
11、优目标值。 对于类指标函数设在阶段k的状态xk执行了任意选定决策uk后的状 态是sk+1=Tk(sk,xk)。这时k-后部子过程就缩小为 k+1后部子过程。根据最优性原理，对k+1后部子 过程应采取最优策略，由于无后效性，k后部子 过程的目标函数值为 给出边界条件：何在一起即构成动态规划的基本方程。类指标函数的基本方程（逆序）为II类指标函数的基本方程（逆序）为适用于 初始状 态给定类指标函数的基本方程（顺序）为II类指标函数的基本方程（顺序）为同理适用于 终止状 态给定10.4 动态规划的求解方法n(1) 基本求解过程q动态规划建模q递推q回溯n(2)动态规划逆推解法n(3)动态规划顺推解法
12、n(1) 基本求解过程n动态规划建模n确定阶段与阶段变量n明确状态变量和状态可能集合。n确定决策变量和决策允许集合。n确定状态转移方程。n明确阶段效应和目标，即写出指标函数。确定阶段与阶段变量阶段的划分一般是按照决策进行的时间或空间上的先 后顺序划分的，阶段数等于多段决策过程中从开始到 结束所需要作出决策的数目，阶段变量用k表示。明确状态变量和状态可能集合状态变量必须包含在给定的阶段上确定全部允许决策 所需要的信息。状态变量的确定决定了整个决策过程 是不是具有无后效性，因而也决定着能不能用动态规 划方法来求解。状态可能集是关于状态的约束条件， 因此为了求解必须正确地确定状态可能集。确定决策变量
13、和决策允许集合。与静态问题相同，决策变量应能够反映对问题所 作的决策，决策变量也应有其相应的约束条件， 在建模时应明确决策允许集合Uk(sk)。确定状态转移方程。系统k阶段从状态sk出发作了决策uk(sk)之后的结果 之一是系统状态的转移，这一结果直接影响系统 往后的决策过程，因此必须明确状态的转移过程 ，即根据问题的内在关系，明确sk+1=Tk(sk,uk)中的 函数Tk(sk,uk) 。l递推l运用基本方程的递推公式和边界条件，从k=n 开始，由后向前逆推，从而逐步求得各阶段的 最优决策和相应的最优值，最后求得f1(s1),将s1 的值代入计算即得。l回溯l由s1和x1* ，利用状态转移方
14、程计算出s2 ，从而 确定x2* ，依此类推，最后确定xn* ，于是 获得最优策略(2) 动态规划逆推解法例1 某旅行者希望从s地起到t地，其间的道路 系统如图所示，图上圆圈表示途径的地方，称 为节点，连结两地的箭线表示道路，其上的数 字表示该段道路长度，箭头表示通行的方向。 试求s到t的最短路。adbetcfs97 5784 56 46547第一阶段 第二阶段 第三阶段划分阶段 k=1,2,3 代表三个阶段adbetcfs97 5784 56 46547状态变量sk取为k阶段所在地，则有： adbetcfs97 5784 56 46547边界条件 f4(t)=0k阶段决策是决定下一步走到哪里
15、，uk(sk)取为下 一步的所在点。 adbetcfs97 5784 56 46547由于第3阶段末已到达t，往后的距离自然是零， 因此f4(t)=0 对3阶段所有可能的状态S3=d, e, f计算f3( )如下也可以用表格方法计算如下t/tf3()u3() d e f5+0 7+0 4+05 7 4t t tv3(s3,u3)+f4(s4) f3(s3) u3(s3) adbetcfs97 5784 56 46547475对2阶段所有可能的状态s2=a,b,c计算f2()如下也可以用表格方法计算如下d/de/ef/ff2()u2()a b c7+5 5+5 4+56+7 5+74+46+48
16、 10 9f d d f2(s2) u2(s2) v2(s2,u2)+f3(s3) adbetcfs97 5784 56 465474759108对1阶段所有可能的状态S1=s计算f1( )如下a/ab/bc/cf2()u2() s9+88+107+916c顺序回溯求最优策略、最优路线和最优 目标函数值adbetcfs97 5784 56 46547475910816例2 某公司有资金10万元，若投资项目i（i=1,2,3） 的投资额为 时,其效益分别为:问应如何分配投资树额才能使总收益最大?可列出它的静态模型:分析:这是一个表面与时 间没有任何关系的问题,但 要用动态规划的方法去解 则必须把它划分为“时段”. 本题可划分为3各时段,每 段只决定
