《运筹学课件-第七章动态规划》由会员分享，可在线阅读，更多相关《运筹学课件-第七章动态规划（81页珍藏版）》请在金锄头文库上搜索。
1、第七章 动态规划动态决策问题：动态决策问题：决策过程具有阶段性和时序性(与时间有关)的决策问题。即决策过程可划分为明显的阶段。动态规划动态规划(D.P.Dynamic Program)(D.P.Dynamic Program)：动态规划是解决多阶段决策过程最优化问题的一种方法。广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。可用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的最优控制等。动态规划动态规划(D.P.)(D.P.)的起源：的起源：1951年,(美)数学家R.Bellman等提出最优化原理，从而建立动态规划，名著动态规划于1957年出版。
2、动态决策问题分类：动态决策问题分类：1、按数据给出的形式分为：离散型动态决策问题。连续型动态决策问题。2、按决策过程演变的性质分为：确定型动态决策问题。随机型动态决策问题。其中离散确定型是最基本的，本章主要针对这种类型的问题，介绍动态规划的基本思想、原理和方法，这些对其它类型的问题也适用。第七章 动态规划一、多阶段决策过程的最优化二、基本概念和基本原理三、动态规划模型的建立与求解四、动态规划在经济管理中的应用一、多阶段决策过程的最优化一、多阶段决策过程的最优化多阶段决策过程：多阶段决策过程：多阶段决策过程，本意是指这样一类特殊的活动过程，它们可以按时间顺序分解成若干相互联系的阶段，称为“时段”
3、，在每一个时段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题属序贯决策问题。动态的含义：动态的含义：动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。多阶段决策过程最优化的目标：多阶段决策过程最优化的目标：达到整个活动过程的总体效果最优。例1 生产与存贮问题 某工厂每月需供应市场一定数量的产品，并将所余产品存入仓库。一般某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用。要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小。显然，可以把每个月作为一个阶段，全年分为12个阶段逐次决
4、策。例2 投资决策问题 某公司现有资金Q万元，在今后5年内考虑给A，B，C，D 4个项目投资，这些项目投资的回收期限、回报率均不相同，问该公司应如何确定这些项目每年的投资额，使到第5年末拥有资金的本利总额最大。这是一个5阶段决策问题。例3 设备更新问题 企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用；现某企业要决定一台设备未来8年的更新计划，已预测了第j年购买设备的价格为Kj，设Gj为设备经过j年后的残值，Cj为设备连续使用j-1年后在第j年的维修费(j1，2，8)，问应在哪些年更新设备可使总费用最小。这是一个8阶段决策问题，每年
5、年初要作出决策，是继续使用旧设备，还是购买新设备。几个例子几个例子几个例子几个例子例4、(基建投资问题)一家公司有三个工厂，每个厂都需要进行扩建。公司用于扩建的资金总共为7万元。各个厂的投资方案及扩建后预期可获得的利润如表所示(单位：万元)。现在公司要确定时各厂投资多少才能使公司的总利润达到最大？解：在这个问题中，因为每个厂都有几种投资方案，所以要对每个厂作出一项决策，总共要作出三个决策。同时，这三个厂的总投资不能超过7万元。如果我们把每个厂看成是一个阶段，这就是一个多阶段的决策问题。几个例子几个例子例5、(货船装运问题)有四种货物准备装到一艘货船上。第i(i12，3，4)种货物的每一箱重量是
6、wi(单位：吨)，其价值是vi(单位：干元)，如表所示。假定这艘货船的总载重量是10吨，现在要确定这四种货物应各装几箱才能使装载货物的总价值达到最大。解：在这个问题中，因为对每一种货物要确定装载的箱数，也就是要作出一项决策，所以总共要作出四个决策。同时，各种货物的总重量不能超过10吨。如果我们把每一种货物看成是一个阶段，这也是一个多阶段的决策问题。几个例子几个例子例6、(最短路程问题)假定从A地到E地要铺设一条管道，其中要经过若干个中间点(如图)。图中两点之间连线上的数字表示两地间的距离，现在要选择一条铺设管道的路线使总长度最短。解：在问题中，从A到B1，B2，B3中的哪一个点要作出一项决策，
7、从B1，B2，B3中的某点到C1，C2，C3中的哪一个点又要作出一项决策等。所以总共要作出四个决策。因此可以把整个路程分为A，B(包括B1，B2，B3)，C(包括C1，C2，C3)和D(包括Dl，D2)四个阶段。这是个多阶段的决策问题。AB1B2B3C1C2C3D1D2 E367769523835436943二、动态规划的基本概念和基本原理二、动态规划的基本概念和基本原理1、阶段：将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用字母k表示阶段变量。动态规划模型要用到的概念：(1)阶段;(2)状态;(3)决策和策略;(4)状态转移;(5)指标函数。2、状
8、态：各阶段开始时的客观条件叫做状态。状态变量：描述各阶段状态的变量，用sk表示第k阶段的状态变量状态集合：状态变量的取值集合，用Sk表示。动态规划中的状态应具有如下性质：当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各段状态的影响。无后效性。一阶段：S1A二阶段：S2B1,B2,B3三阶段：S3C1,C2,C3四阶段：S4D1,D23、决策：当各段的状态取定以后，就可以作出不同的决策（或选择），从而确定下一阶段的状态，这种决定称为决策。决策变量：表示决策的变量，称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。允许决策集合：决策变量的取值往往限制在一定范围内，我们称
9、此范围为允许决策集合，用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。D2(B1)=C1,C2D2(B2)=C1,C2,C3如状态为B1时选择C2，可表示为：u2(B1)=C2策略：各段决策确定后，整个问题的决策序列就构成一个策略，用p1,nu1(s1),u2(s2),.un(sn)表示。对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1,n，使整个问题达到最优效果的策略就是最优策略。4、状态转移方程：动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。第k段的状态sk，本阶段决策为uk(sk)，则第k+1段的状态sk+1也就完全确定，它们的关系可用公式表示
10、：sk+1=Tk(sk,uk)sk+1=uk(sk)5、指标函数：用于衡量所选定策略优劣的数量指标。它分为阶段指标函数和过程指标函数。阶段指标函数是指第k段，从状态sk出发，采取决策uk时的效益，用d(sk,uk)表示。d(B1,C2)一个n段决策过程，从1到n叫作问题的原过程，对于任意一个给定的k(1k n)，从第k段到第n段的过程称为原过程的一个后部子过程。V1,n(s1,p1,n)表示初始状态为s1采用策略p1,n时原过程的指标函数值;而Vk,n(sk,pk,n)表示在第k段，状态为sk采用策略pk,n时,后部子过程的指标函数值。最优指标函数记为fk(sk)表示从第k段状态sk采用最优策
11、略到过程终止时的最佳效益值。f2(B1)f1(A)动态规划的基本思想动态规划的基本思想最简单的方法穷举法。共有多少条路径，依次计算并比较。动态规划方法本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点的最短路线，最后求得起始点到终点的最短路线。动态规划的基本思想动态规划的基本思想第一步：k=5状态s5：E1，E2(4)(3)f5(E1)4f5(E2)3第二步：k=4 状态：D1 D2 D3u4*(D1)=E1u4*(D2)=E2u4*(D3)=E1(4)(3)(7)(5)(5)(4)(3)(5)(5)(7)第三步：k=3 状态：C1 C2 C3 C4u3*(C1)=D1u
12、3*(C2)=D2u3*(C3)=D2f3(C1)12f3(C2)10f3(C3)8u3*(C4)=D3f3(C4)9(12)(10)(8)(9)(4)(3)(7)(5)(5)(12)(10)(8)(9)第四步：k=2状态：B1 B2 u2*(B1)=C2u2*(B2)=C3f2(B1)13f2(B2)15(13)(15)(4)(3)(7)(5)(5)(12)(10)(8)(9)(13)(15)第五步：k=1状态：A u1*(A)=B1f1(A)17(17)即从A到F的最短距离为17。最优路线为：AB1C2D2E2F2511214106104131112396581052C1C3D1AB1B3
13、B2D2EC2练习：求从A到E的最短路径2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=525112141061041311123
14、96581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82511214106104131112396581052C1C3D1AB1B
15、3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1
16、(A)=19f2(B2)=14f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14
