运筹学10-动态规划

《运筹学10-动态规划》由会员分享，可在线阅读，更多相关《运筹学10-动态规划（153页珍藏版）》请在金锄头文库上搜索。

1、第十章 动态规划Dynamic Programming10.1 多阶段决策问题 10.2 动态规划的基本概念和基本方程 10.3 动态规划的建模与求解方法 10.4 动态规划应用举例n动态规划Dynamic programmingn是解决多阶段决策过程（multi-step decision process）最优化的一种数量化方法，所以又名多阶 段规划（multi-stage programming）n五十年代贝尔曼(Richard Bellman)为代表的研究成 果n属于现代控制理论的一部分n以长远利益为目标的一系列决策n1951年提出了 “最优化原理”（principle of decis

2、ion optimality）可归结为一个递推公式n1957年动态规划n动态规划应用等其它著作n成功之处：把一个n维决策问题变换为n个 一维最优化问题，一个一个地求解。n这是经典极值方法所做不到的，它几乎超 越了所有现存的计算方法，特别是经典优 化方法n动态规划能够求出全局极大或极小，这也 是其它优化方法很难做到的注意n动态规划是求解某类问题的一种方法，是 考察问题的一种途径，n而不是一种特殊的算法，没有统一的数学 模型和算法n必须具体问题具体分析n针对具体问题，运用动态规划的原理和方 法，建立起相应的模型，然后再用动态规 划方法去求解n动态规划(dynamic programming)是运筹

3、学的一个分支 ，是求解决策过程(decision process)最优化的数学方法 。20世纪50年代初美国数学家R.E.Bellman等人在研究 多阶段决策过程(multi-step decision process)的优化问 题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题， 逐个求解，创立了解决这类过程优化问题的新方法 动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。n动态规划问世以来，在经济管理、生产调度、工程技术 和最优控制等方面得到了广泛的应用。例如最短路线、 库存管

4、理、资源分配、设备更新、排序、装载等问题， 用动态规划方法比用其它方法求解更为方便。2511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0问题的引入：最短路问题求上述问题中A到E的最短路。2511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214 106 104 131112396581052C1C3D1AB1B

5、3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(

6、D1)=5f2(B1)=20f3(C2)=7f3(C1)=82511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=202511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=20f2(B2)=142511214 106 104 131112396581052

7、C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=202511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B22511214 106 104 13111

8、2396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B2 （B2，C1） C12511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20

9、状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B2 （B2，C1） C1 （C1，D1） D12511214 106 104 131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E从A到E的最短路径为19，路线为AB 2C1

10、D1 E 10.1 多阶段决策问题n多阶段决策过程，是指这样的一类特殊的活动 过程，问题可以按时间顺序分解成若干相互联 系的阶段，在每一个阶段都要做出决策，全部 过程的决策是一个决策序列。要使整个活动的 总体效果达到最优的问题，称为多阶段决策问 题。n决策:在多个可行方案中选择或选定一个的过程 或行为;n策略:由一系列相互衔接的决策构成的决策序列 ;n策略集合:有可供选择的策略构成的集合;n最优策略:在预定标准下达到最好效果的策略.l静态决策 一次性决策l动态决策 多阶段决策决策s1s2vu输入决策输出决策效应第一月s1s2v1u1第二月s3v2u2第三月s4v3u3例例1 1给定一个线路网络

11、图给定一个线路网络图, ,两点之间联线上的数字两点之间联线上的数字 表示两点间的距离表示两点间的距离( (或运费或运费), ),试求一条由试求一条由s s到到t t的铺管的铺管 线路线路, ,使总距离最短使总距离最短. .adbetcfs97 5784 56 46547例2 某公司拟将50万元资金投放下属A、B、C三 个部门，各部门在获得资金后的收益如表所示 ，求总收益最大的投资分配方案（投资数以10 万元为单位）。投放资金(万元)01020304050收益 （万元） A01520252830B0010254570C01020304050n例3 已知货物的单位重量i，单位体积i及价值 pi如表

12、所示，船的最大载重能力为W5，最大装 载体积为V8，求最优装载方案。 iiipi11230234803236510.2 动态规划的基本概念和基本方程(1) 动态规划的基本概念n阶段与阶段变量:n将所要研究的问题,按时间或空间特征分成若 干个互相联系的阶段.简称“阶段”n我们就是要按阶段的顺序来求解.n描述阶段的变量阶段变量,常用字母k来表示;n状态、状态变量和状态集合n各阶段开始时的客观条件叫做状态.n描述各阶段状态的变量叫做状态变量,常用sk表示 第阶段的状态变量； n状态变量sk的取值集合称为状态集合,用Sk表示；n动态规划中状态具有以下性质:某阶段状态一旦确 定以后过程的状态变化不受这个

13、状态以前的影响, 也就是说某状态以后的过程和以前无关,只与当前 状态有关,我们称这种特性为“无后效性.” n决策、决策变量和策略n当个阶段的状态取定以后,就可以做出关于下一步 的选择,从而确定下一阶段的状态,这种决定称为决 策；n表示决策的变量叫做决策变量,常用uk(sk)表示.第k 阶段当状态为sk时的决策变量；n在实际问题中决策变量的取值往往限制在一定的 范围内,我们称此范围为允许决策集,常用Dk(sk)表 示第k阶段从状态sk出发的允许决策集,因此有 uk(sk) Dk(sk).n各段决策确定后,整个问题的决策序列就构成了一 个策略,用P1,nu1(s1),u2(s2), ,un(sn)

14、表示；n使整个问题达到最优效果的的策略就是最优策略.n动态规划中本阶段的状态是上一阶段的决策结果. 如果给定了第k阶段的状态sk,本阶段的决策就为 uk(sk),则第k+1段的状态uk+1也就完全确定了,它的 关系可表示为:sk+1=Tk(sk,uk).由于它表示了由k到 k=1段的状态转移规律,所以称为状态转移方程.T1s1s2v1 (s1, u1)u1(s1 )T2s3v2 (s2 ,u2)u2 (s2)Tksksk+!vk (sk,uk)uk (sk)Tnsnsn+1vn (sn,un)un (sn)n指标函数与最优值函数n用于衡量所选定策略优劣的数量指标称为指标函 数.n阶段指标函数v

15、k(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,s2,x2, ,sn,xn)多段决策过程中从第k阶段到最终阶段的过程 称为k-后部子过程，简称k-子过程。 Tksksk+!vk (sk,uk)uk (xk)Tnsnsn+1vn (sn,un)un (xn)n指标函数应具有三个条件 q指标函数在全过程和所有后部子过程

16、上有定义；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使指标函数Vkn达到最优值的策略是从k开始的后部子 过程的最优策略，记作pkn*=uk*,.un*,p1n*又是全过 程的最优策略，简称最优策略。 n指标函数的两种基本形式：nnn(2) 最优化原理最优化原理“最优策略具有的基本性质是：无论初始状 态和初始决策如何，对于前面