数学方法动态规划1

第七章动态规划(D.P.–DynamicProgram)是解决多阶段决策过程最优化问题的一种方法。动态的含义：动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。一、多阶段决策问题的最优化第七章动态规划的起源：1951年,(美)数学家R.Bellman等人，根据多阶段序贯决策问题的特点，提出了著名的“最优性原理”。将多阶段决策问题转变为一系列的互相联系的单阶段决策问题，然后，逐个阶段予以解决，最后再形成总体解决。从而创建了求解优化问题的新方法——动态规划。1957年，他的名著《动态规划》出版。一、多阶段决策过程的最优化第七章•最优性原理:•作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优子策略。简言之，最优策略的子策略总是最优的。一、多阶段决策过程的最优化第七章动态决策问题分类：1、按数据给出的形式分为：离散型动态决策问题。连续型动态决策问题。2、按决策过程演变的性质分为：确定型动态决策问题。随机型动态决策问题。一、多阶段决策过程的最优化第七章例1生产与存贮问题要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小？例2投资决策问题某公司现有资金Q万元，在今后5年内考虑给A，B，C，D4个项目投资？例3设备更新问题现企业要决定一台设备未来8年的更新计划，问应在哪些年更新设备可使总费用最小？一、多阶段决策过程的最优化第七章例4基建投资问题一家公司有三个工厂，每个厂都需要进行扩建。公司用于扩建的资金总共为7万元。各个厂的投资方案及扩建后预期可获得的利润如表所示(单位：万元)。现在公司要确定各厂投资多少才能使公司的总利润达到最大？厂名方案1方案2方案3方案4投资数利润投资数利润投资数利润投资数利润一厂001528510二厂001339411三厂0027311413一、多阶段决策过程的最优化第七章例5货船装运问题有四种货物准备装到一艘货船上。第i(i＝1．2，3，4)种货物的每一箱重量是wi(单位：吨)，其价值是vi(单位：干元)，如表所示。假定这艘货船的总载重量是10吨，现在要确定这四种货物应各装几箱才能使装载货物的总价值达到最大？货物i单位重量wi单位价值vi124212347435一、多阶段决策过程的最优化第七章例6最短路程问题假定从A地到E地要铺设一条管道，其中要经过若干个中间点(如图)。图中两点之间连线上的数字表示两地间的距离，现在要选择一条铺设管道的路线使总长度最短。AB1B2B3C1C2C3D1D2E367769523835436943一、多阶段决策过程的最优化第七章动态规划是解决多阶段决策问题的一种方法。所谓多阶段决策问题是指这样的决策问题：其过程可分为若干个相互联系的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。当每一阶段的决策选定以后，就构成一个决策序列，称为一个策略，它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。二、基本概念和基本原理第七章二、基本概念和基本原理1、阶段：将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用字母k表示阶段变量。动态规划模型要用到的概念：(1)阶段;(2)状态;(3)决策和策略;(4)状态转移;(5)指标函数。第七章2、状态：各阶段开始时的客观条件叫做状态。状态变量：描述各阶段状态的变量，用sk表示第k阶段的状态变量。状态集合：状态变量的取值集合，用Sk表示。一阶段：S1＝{A}二阶段：S2＝{B1,B2,B3}三阶段：S3＝{C1,C2,C3}四阶段：S4＝{D1,D2}AB1B2B3C1C2C3D1D2E367769523835436943二、基本概念和基本原理第七章3、决策：当各段的状态取定以后，就可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。决策变量：表示决策的变量，称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。允许决策集合：决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合，用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。D2(B1)={C1,C2}D2(B2)={C1,C2,C3}如状态为B1时选择C2，可表示为：u2(B1)=C2二、基本概念和基本原理第七章策略：各段决策确定后，整个问题的决策序列就构成一个策略，用p1,n{u1(s1),u2(s2),...un(sn)}表示。允许策略集合：对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1,n，使整个问题达到最优效果的策略就是最优策略。AB1B2B3C1C2C3D1D2E367769523835436943p1,4{B1,C1,D1,E}二、基本概念和基本原理第七章4、状态转移方程：动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。第k段的状态sk，本阶段决策为uk(sk)，则第k+1段的状态sk+1也就完全确定，它们的关系可用公式表示：sk+1=Tk(sk,uk)sk+1=uk(sk)AB1B2B3C1C2C3D1D2E367769523835436943二、基本概念和基本原理第七章5、指标函数：用于衡量所选定策略优劣的数量指标。它分为阶段指标函数和过程指标函数。阶段指标函数是指第k段，从状态sk出发，采取决策uk时的效益，用d(sk,uk)表示。d(B1,C2)一个n段决策过程，从1到n叫作问题的原过程，对于任意一个给定的k(1≤k≤n)，从第k段到第n段的过程称为原过程的一个后部子过程。V1,n(s1,p1,n)表示初始状态为s1采用策略p1,n时原过程的指标函数值;Vk,n(sk,pk,n)表示在第k段，状态为sk采用策略pk,n时,后部子过程的指标函数值。最优指标函数记为fk(sk)：表示从第k段状态sk采用最优策略到过程终止时的最佳效益值。二、基本概念和基本原理第七章最简单的方法－－穷举法。共有多少条路径，依次计算并比较。动态规划方法－－本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点的最短路线，最后求得起始点到终点的最短路线。二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2练习：求从A到E的最短路径。二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0505)E(f)ED(d)D(f5114二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)E(f)ED(d)D(f5224二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=51124211411138118min2953min)(),()(),(min)(DCDfDCdDfDCdCf最优决策二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82224221412237711min2556min)(),()(),(min)(DCDfDCdDfDCdCf最优决策二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333121213min21058min)(),()(),(min)(DCDfDCdDfDCdCf最优决策二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8113331232113111220222120min1210714812min)(),()(),()(),(min)(CBCfCBdCfCBdCfCBdBf最优决策二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21123332232213122214161714min12471086min)(),()(),()(),(min)(CBCfCBdCfCBdCfCBdBf最优决策二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14233333232313133219231921min1211712813min)(),()(),()(),(min)(CBCfCBdCfCBdCfCBdBf最优决策二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=212323222121119201923min191145212min)(),()(),()(),(min)(BABfBAdBfBAdBfBAdAf最优决策二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(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）C1二、基本概念和基本原理第七章2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)