资源描述：
《运筹学 第05章 动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、运筹学第五章动态规划本章重点动态规划的四大要素、一个方程动态规划问题的建模与求解动态规划概念(1)前面介绍的线性规划研究的是一次性的决策线性规划决策过程可以总结为在给定资源和环境的情况下，决定变量的取值，使某个目标达到最大或最小值这个决策过程可以表示如下图决策x1x2uZ其中u表示决策变量x1表示决策所依赖的资源和环境Z表示目标函数x2表示决策后的资源和环境状况动态规划概念(2)例如，前面讲过的生产计划问题就是一次决策某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的日生产计划产品所需原料数量（公斤/件）产品Q1（件）产品Q2（件）
2、产品Q3（件）原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000产品的利润（千元/件）354动态规划概念(3)在这个模型中模型中的A、b和C就是x1模型中的X就是u模型中的f(X)=CX就是ZA、C和剩余的原料为x2设每天生产三种产品的件数分别为x1、x2、x3其线性规划模型为决策x1x2uZ动态规划概念(4)如果上例中的生产计划不是只在一天里进行，而是连续一周，每天投入一定量的原料，剩余的原料后面可以继续使用，每天只允许生产一种产品并获得相应的利润。问怎样决策才能使一周的总利润最大？解决这样的问题需要将决策过程分为
3、多个阶段，本问题需要分为如下的7个阶段。周日x1x2u1r1周一x3u2r2周六x8u7r7x7…动态规划概念(5)uk（k=1,2,3,4,5,6,7）表示第k天生产三种产品中的哪一种以及生产多少x1=技术环境A、市场环境C和原料bxk+1=技术环境A、市场环境C和原料b+第k天剩余的原料（k=1,2,3,4,5,6,7）rk=第k天生产产品获得的利润总利润=r1+r2+r3+r4+r5+r6+r7动态规划就是解决这种多阶段决策过程的方法多阶段决策过程(1)其中包含n个决策子问题，每个子问题称为一个阶段，用变量k表示，称为阶段变量xk描述k阶段初系统
4、的状况，称为状态变量每个阶段有一个输入状态和一个输出状态一般把输入状态称为该阶段的阶段状态TnT1x1x2u1r1T2x3u2r2Tkxk+1ukrkxk…xn+1unrnxn…一般的多阶段决策过程表示如下多阶段决策过程(2)uk代表k阶段对第k子问题进行的决策，称uk为k阶段的决策变量，uk的一组确定的取值称为一个决策rk表示k阶段从状态xk出发做决策uk之后产生的后果，称为k阶段的阶段效应若在上述的多阶段决策过程中，系统k阶段以后的决策只与k阶段系统的状态xk有关，而与系统以前的决策无关，则称该多阶段决策过程具有无后效性注：动态规划的建模和求解都是
5、针对具有无后效性的多阶段决策过程多阶段决策过程(3)在具有无后效性的多阶段决策过程中，uk由xk决定，rk和xk+1由xk和uk决定，因此决策可以写为uk(xk)阶段效应可以写为rk(xk,uk)状态xk+1=Tk(xk,uk)称为状态转移方程，其中Tk是已知函数多阶段决策过程中，从第k阶段到最终阶段的过程称为k-后部子过程，简称k-子过程动态规划模型动态规划模型如下表示求和或加权求和opt表示求最优(最大值或最小值)Xk表示k阶段状态可能的取值范围，称为状态可能集合Uk表示k阶段决策可能的取值范围，称为决策允许集合动态规划建模确定阶段根据实际情况进行
6、阶段划分明确状态变量xk和状态可能集合Xk确定决策变量uk(xk)和决策允许集合Uk确定状态转移方程xk+1=Tk(xk,uk)明确阶段效应rk(xk,uk)和目标R示例(5.1-1)前面讲过的生产计划问题某工厂用三种原料生产三种产品，已知的条件如下表所示，如连续生产一周，每天投入一定量的原料，剩余的原料后面可以继续使用，每天只允许生产一种产品并获得相应的利润。试制订总利润最大的周生产计划(只建模，不求解)产品所需原料数量（公斤/件）产品Q1（件）产品Q2（件）产品Q3（件）原料可用量（公斤/日）原料P12301500原料P2024800原料P3325
7、2000产品的利润（千元/件）354示例(5.1-2)示例(5.1-3)动态规划解的概念(1)最优目标值在多阶段决策过程中，从起始状态x1开始，进行一系列的决策，使得目标R达到最优，我们把这种目标的值称为最优目标值，记为R*最优策略把使目标达到最优的决策序列称为最优策略，记为{u1*,u2*,…,un*}最优路线在采用最优策略时，系统从x1开始所经过的状态序列称为最优路线，记为{x1*,x2*,…,xn+1*}动态规划解的概念(2)求解动态规划问题就是要找到最优策略、最优路线和最优目标值动态规划最优性原理(1)一个多阶段决策过程的最优策略具有这样的性质
8、无论其初始状态及其初始决策如何，对于前面决策所形成的某一状态而言，下余的决策序列必定构成最优策
