第七章动态规划.pptx

动态规划(.–DynamicProgram)是解决多阶段决策过程最优化问题的一种方法。广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。可用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的最优控制等。动态的含义:动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是“动态”的意思。一、多阶段决策过程的最优化1动态规划的起源:1951年,(美),根据多阶段序贯决策问题的特点,提出了著名的“最优性原理”。将多阶段决策问题转变为一系列的互相联系的单阶段决策问题,然后,逐个阶段予以解决,最后再形成总体解决。从而创建了求解优化问题的新方法——动态规划。1957年,他的名著《动态规划》出版。最优性原理:作为整个过程的最优策略具有这样的性质:即无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优子策略。简言之,最优策略的子策略总是最优的。一、多阶段决策过程的最优化2动态决策问题:决策过程具有阶段性和时序性(与时间有关)的决策问题。即决策过程可划分为明显的阶段。动态决策问题分类:1、按数据给出的形式分为:离散型动态决策问题。连续型动态决策问题。2、按决策过程演变的性质分为:确定型动态决策问题。随机型动态决策问题。一、多阶段决策过程的最优化3例1生产与存贮问题要求确定一个逐月的生产计划,在满足需求条件下,使一年的生产与存贮费用之和最小?例2投资决策问题某公司现有资金Q万元,在今后5年内考虑给A,B,C,D4个项目投资?例3设备更新问题现企业要决定一台设备未来8年的更新计划,问应在哪些年更新设备可使总费用最小?一、多阶段决策过程的最优化4例4基建投资问题一家公司有三个工厂,每个厂都需要进行扩建。公司用于扩建的资金总共为7万元。各个厂的投资方案及扩建后预期可获得的利润如表所示(单位:万元)。现在公司要确定时各厂投资多少才能使公司的总利润达到最大?厂名方案1方案2方案3方案4投资数利润投资数利润投资数利润投资数利润一厂001528510二厂001339411三厂0027311413一、多阶段决策过程的最优化5例5货船装运问题有四种货物准备装到一艘货船上。第i(i=,3,4)种货物的每一箱重量是wi(单位:吨),其价值是vi(单位:干元),如表所示。假定这艘货船的总载重量是10吨,现在要确定这四种货物应各装几箱才能使装载货物的总价值达到最大?货物i单位重量wi单位价值vi124212347435一、多阶段决策过程的最优化6例6最短路程问题假定从A地到E地要铺设一条管道,其中要经过若干个中间点(如图)。图中两点之间连线上的数字表示两地间的距离,现在要选择一条铺设管道的路线使总长度最短。AB1B2B3C1C2C3D1D2E367769523835436943一、多阶段决策过程的最优化7二、基本概念和基本原理1、阶段:将所给问题的过程,按时间或空间特征分解成若干互相联系的阶段,以便按次序去求每阶段的解,常用字母k表示阶段变量。动态规划模型要用到的概念:(1)阶段;(2)状态;(3)决策和策略;(4)状态转移;(5)指标函数。82、状态:各阶段开始时的客观条件叫做状态。状态变量:描述各阶段状态的变量,用sk表示第k阶段的状态变量。状态集合:状态变量的取值集合,用Sk表示。一阶段:S1={A}二阶段:S2={B1,B2,B3}三阶段:S3={C1,C2,C3}四阶段:S4={D1,D2}AB1B2B3C1C2C3D1D2E367769523835436943二、基本概念和基本原理93、决策:当各段的状态取定以后,就可以作出不同的决定(或选择),从而确定下一阶段的状态,这种决定称为决策。决策变量:表示决策的变量,称为决策变量,常用uk(sk)表示第k阶段当状态为sk时的决策变量。允许决策集合:决策变量的取值往往限制在一定范围内,我们称此范围为允许决策集合,用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。D2(B1)={C1,C2}D2(B2)={C1,C2,C3}如状态为B1时选择C2,可表示为:u2(B1)=C2二、基本概念和基本原理10