动态优化模型(完整版).ppt

《动态优化模型(完整版).ppt》由会员分享，可在线阅读，更多相关《动态优化模型(完整版).ppt（53页珍藏版）》请在三一办公上搜索。

1、动态优化模型（完整版）,连续动态过程的优化归结为求泛函的极值.,求泛函极值的常用方法:变分法、最优控制论.,离散动态过程的优化 动态规划模型.,静态优化问题,优化目标是数值,最优策略是数值,函数对应的数值称为泛函(函数的函数).,动态优化问题,优化目标是数值,最优策略是函数,1 速降线与短程线,通过两个古典问题介绍变分法的基本概念,给出主要结果.,速降线问题,给定竖直平面内不在一条垂直线上的两个点A,B,求连接A,B的光滑曲线，使质点在重力作用下沿该曲线以最短时间从A滑到B(摩擦力不计).,.A,.B,若沿陡峭曲线下滑,虽路径加长，但速度增长很快.,速降线问题,.A,.B,建立坐标系xOy,曲

2、线弧长,能量守恒,质点在曲线y(x)上的速度ds/dt,质点沿曲线y(x)从A到B的时间,求y(x)使 J(y(x)达到最小.,m质点质量，g重力加速度,A(0,0),B(x1,y1),曲线AB y=y(x),满足条件,短程线问题,给定曲面上的两个点A,B,求曲面上连接A,B的最短曲线.,建立坐标系,A(x0,y0,z0),B(x1,y1,z1),曲线的弧长,曲线的长度,求y=y(x),z=z(x)使J(y(x),z(x)达到最小.,满足条件,泛函、泛函的变分和极值,自变量t，函数x(t),y(t),函数、函数的微分和极值,泛函、泛函的变分和极值,1.对于t在某域的任一个值,有y的一个值与之对

3、应,称y是t的函数，记作y=f(t),1.对于某函数集合的每一个函数x(t),有J的一个值与之对应,称J是x(t)的泛函,记作J(x(t),2.t在t0的增量记作 t=t-t0,微分dt=t,2.x(t)在x0(t)的增量记作 x(t)=x(t)-x0(t)，x(t)称x(t)的变分,3.y在t0的增量记作 f=f(t0+t)-f(t0)，f的线性主部是函数的微分,记作dy，dy=f(t0)dt,3.泛函J(x(t)在x0(t)的增量记作J=J(x0(t)+x(t)-J(x0(t),J的线性主部称泛函的变分,记作 J(x0(t),泛函、泛函的变分和极值,函数、函数的微分和极值,泛函、泛函的变分

4、和极值,4.若函数y在域内t点达到极值，则在t点的微分dy(t)=0,4.若泛函J(x(t)在函数集合内的x(t)达到极值,则在x(t)的变分J(x(t)=0,5.y在t的微分的另一表达式,5.泛函J(x(t)在x(t)的变分可以表为,泛函J(x(t)在x(t)达到极值的必要条件,欧拉方程(最简泛函极值的必要条件),最简泛函,F具有二阶连续偏导数，x(t)为二阶可微函数,固定端点条件下的泛函,J(x(t)在x(t)达到极值的必要条件:,x(t)满足二阶微分方程,两个任意常数由 确定,欧拉方程,用欧拉方程解速降线问题,求y(x)使 达到最小,且,欧拉方程,圆滚线方程,c2=0,c1由y(x1)=

5、y1确定.,横截条件(变动端点问题),容许函数 x(t)的一个端点固定:x(t1)=x1，另一个端点在给定曲线 x=(t)上变动:x(t2)=(t2)(t2可变).,欧拉方程在变动端点的定解条件,x=(t)垂直于横轴(t2固定),x=(t)平行于横轴,包含多个未知函数泛函的欧拉方程,欧拉方程,泛函的条件极值,最优控制问题:u(t)控制函数,x(t)状态函数(轨线).,泛函的条件极值,用拉格朗日乘子化为无条件极值,欧拉方程,由方程组和端点条件解出最优控制u(t)和最优轨线x(t).,Hamilton函数,2 生产计划的制订,问题,生产任务是在一定时间内提供一定数量的产品.,生产费用随着生产率(单

6、位时间的产量)的增加而变大.,贮存费用随着已经生产出来的产量的增加而变大.,生产计划用每一时刻的累积产量表示.,建模目的,寻求最优生产计划,使完成生产任务所需的总费用(生产费用与贮存费用之和)最小.,分析与假设,生产任务:t=0开始生产,t=T提供数量为Q的产品.,生产计划(累积产量):x(t),生产率(单位时间产量):,生产费用,贮存费用,总费用,生产率提高一个单位的生产费用与生产率成正比,贮存费用与贮存量成正比,模型与求解,求x(t)(0,0tT)使C(x(t)最小.,欧拉方程,考察x(t)0(0tT)的条件,只有当生产任务Q 足够大时才需要从 t=0开始生产.,若 怎么办?,模型解释,最

7、优生产计划,满足方程,边际成本,生产费用,贮存费用,边际贮存,最优生产计划在边际成本的变化率等于边际贮存时达到.,生产计划的制订,最优生产计划的目标函数只考虑生产费用与贮存 费用,并对这两种费用作了最简单的假设.,对于泛函极值问题用古典变分法求解,得到最优生 产计划x(t)(累积产量)为二次函数.,实际条件x(t)0 导致对已知参数的要求:,对函数施加的闭约束,如对生产率的限制 可能导致古典变分法的失败.,若参数不满足该要求怎样处理?,3 国民收入的增长,背景和问题,国民经济收入的来源:扩大再生产的积累 资金,满足人民生活需要的消费资金.,如何安排积累资金和消费资金的比例，使国民经济收入得到最

8、快的增长.,从最优控制的角度讨论十分简化的模型.,一般模型,国民经济收入 x(t)，其中用于积累资金的部分y(t),求最优积累率使国民收入 x(t)在时间T内增长最快.,积累率 u(t)=y(t)/x(t),国民收入增长率,对偶等价,泛函条件极值,哈密顿函数,求解最优控制函数u(t)和最优状态x(t).,简化模型,假设,讨论函数f的具体、简化形式,描述以上假设的最简模型,国民收入相对增长率,积累率u较小时 随u的增加而增加 积累资金扩大再生产的促进作用.,随着u的变大 的增加变慢.,u增加到一定程度后 反而减小 消费资金太少对国民收入的制约作用.,模型求解,对于最简模型 不必解泛函极值问题,可

9、以直接得到 u=a/2b时 最大.,使国民收入 x(t)增长最快的最优积累率是常数 u=a/2b,结果解释,4 渔船出海,背景和问题,继续讨论开发渔业资源的最大经济效益模型.,用出海渔船数量表示捕捞强度,作为控制函数.,当渔场鱼量增长到一定数量后才出海捕捞.,用特殊形式的控制函数将动态优化问题化为 普通的函数极值.,模型假设,x(t)的自然增长服从Logistic规律,单位时间 捕捞量与u(t),x(t)成正比.,当t 时才派渔船出海,且u(t)=U(常数).,鱼的出售单价为p,每只渔船单位时间费用为c,折扣因子(通货膨胀率)为.,渔场鱼量x(t),渔船数量u(t),x(0)=N/K(K很大)

10、,t 时x(t)保持稳定.,建模与求解,泛函极值问题,目标函数:捕鱼业的长期效益,函数极值问题,建模与求解,目标函数:捕鱼业的长期效益,b(1)费用-价格比的下界,模型解释,最优解应在边际收益等于边际损失时达到,单位时间利润,短期利润的增加:,长期收益的减少:,渔 船 出 海,以渔船数量u(t)为控制函数的最大效益模型泛函极值.,假定u(t)的特殊形式,化为函数极值.,u(t)假定的合理性:泛函极值问题的解正是取这种形式.,最优解在边际收益等于边际损失时达到,是短期利益与长期利益取得折中的结果.,5 赛跑的速度,背景和问题,将赛程分成若干阶段,根据赛跑运动员的生理 条件对各阶段的速度作最恰当的

11、安排,以期获 得最好的成绩.,Keller提出一个简单模型(1974),根据4个生理参 数从最优控制的角度确定各阶段的速度函数,并 可以预测比赛成绩.,寻求速度安排的最佳策略是复杂的生理力学问题.,问题分析,运动员在赛跑中要克服体内外的阻力以达到 和保持一定速度,需要发挥向前的冲力.,这些能量怎样分配到赛跑的各个阶段,并在到 达终点前将其全部用完.,为冲力作功提供能量的来源:赛跑前贮存在体内 的能量,赛跑中通过氧的代谢作用产生的能量.,模型要确定的3个关系:,冲力与速度,冲力作功与能量来源,速度与比赛成绩,将最佳成绩归结成以距离为目标,与速度、冲力、能量等函数有关的极值问题.,模型假设,赛跑中

12、体内外的阻力与速度成正比,比例系数-1,赛跑中在氧的代谢下单位时间产生的能量是常数,赛跑前贮存在体内供赛跑的能量是常数E0,运动员能发挥的最大冲力是F,运动员具有单位质量，初速为零.,比赛成绩：“一定距离下时间最短”等价为“一定时间内距离最大”.,一般模型,以速度v(t)在时间T内跑完赛程D,阻力与速度成正比,比例系数-1,单位质量运动员，初速为零,运动员的最大冲力是F,单位时间产生的能量是,赛跑前贮存的能量是E0,运动员赛跑速度v(t),体内能量E(t),D固定,求v(t)使T最小,以D(v(t)为目标的泛函条件极值(,F,E0为已知参数),短跑模型,用最大冲力F跑全程,可取得最好成绩,最长

13、的短跑赛程以体内能量E(t)不小于零为标准,v小 E增加,v大 E减少,最远距离(最长的短跑赛程)为,短跑模型,Keller根据当时的世界记录得到F,的估计值:,后来根据1987年约翰逊的百米成绩(9.83s)修正参数:,估计用最大冲力跑全程时最长的短跑赛程,中长跑模型,当赛程超过Dc时不能用最大冲力跑全程,将赛程分为3个阶段:,初始阶段(0t t1)用最大冲力跑,在短时间获得高速度.,中间阶段(t1 t t2)保持匀速.,最后阶段(t2 t T)把体内能量用完,靠惯性冲刺.,问题:确定t1,t2 及3个阶段的速度v1(t),v2(t),v3(t),中长跑模型,初始阶段用最大冲力跑,与短跑模型

14、相同,t1待定,最后阶段把体内能量用完,E(t)=0,中间阶段保持匀速,t2,v2待定,中长跑模型,中间阶段,在条件E(t2)=0下求v(t)使D(v(t)最大,t1,t2,v2待定,中长跑模型,引入乘子化为无条件极值,泛函极值必要条件,确定t1,t2,v2,模型解释,中长跑模型3段速度示意图,赛跑的最佳策略是最后把体内能量全部用完,靠惯性 冲刺,这必然导致速度的短暂下降,单从赛跑的时间看(不考虑比赛的策略),这样做是最优的.,Keller对一般模型提出分段解法,不能证明是最优的,但它是合理的简化,在将动力学与生理学相结合,用 建模方法探讨体育问题上提供了范例.,最后一段(通常一两秒钟)速度有

15、所下降,6 多阶段最优生产计划,离散动态优化问题,动态规划模型是有效方法,问题,考察T个时段某产品的生产计划,生产准备费c0,单件生产成本k,单件每时段存贮费h0,每时段最大生产能力Xm,每时段最大存贮量Im,第1时段初有库存量i1,制订产品生产计划(每时段产量)使T个时段的总费用最小,已知需求量dt(t=1,2,T),例 T=3,d1=2,d2=1,d3=2,Xm=4,c0=3,k=2,h0=1,Im=3,i1=1,确定需求问题,分析与求解,生产费用,时段t初的存贮量it,时段t+1初的存贮量 it+1=it+xt-dt,时段t的存贮费 h(it)=h0(it+xt-dt)=it+xt-dt

16、,时段t的产量 xt(t=1,2,3),xtXm=4，itIm=3,需求量dt,准备费c0=3,成本k=2,存贮费h0=1,最大生产能力Xm=4,最大存贮量Im=3,将多时段生产计划问题简化为多个单时段问题,由后向前分解,时段3初的存贮量i3,产量x3(i3),最小费用f3(i3),1.最后时段(时段3),需求量d3=2,f3(0)=c(2)=3+22=7,为使3个时段的总费用最小，时段3末的存贮量应为0,i3=0,f3(1)=c(1)=3+21=5,f3(2)=c(0)=0,x3(0)=2,i3=1,x3(1)=1,i3=2,x3(2)=0,分析与求解,2.时段2,需求量d2=1,时段2初存

17、贮量i2,产量x2(i2),时段2,3最小费用之和,时段2的费用:c(x2)+h(i2),i3=i2+x2-1,1i2+x23,3.时段1,时段1初存贮量i1=1,产量x1(i1),需求量d1=2,时段13最小费用之和,时段1的费用:c(x1)+h(i1),i2=i2+x2-2,2i2+x25,f1(1)=15,x1(1)=2,i2=i1+x1-2=1+2-2=1,i3=i2+x2-1=1+0-1=0,最优生产计划：3个时段的产量为x1=2，x2=0，x3=2,x2(i2)=x2(1)=0,x3(0)=2,最短路问题,多阶段生产计划,寻找最短路,2,各路段站点:i1=1,i2=0,1,2,3,

18、i3=0,1,2,i4=0,两站点距离:本时段生产费与存贮费之和,路段3各站点到终点的最短距离:f3(i3),路段2各站点到终点的最短距离:f2(i2),路段1站点1到终点的最短距离:f1(1),最短路:i1=1,x1(1)=2i2=1,x2(1)=0i3=0,x3(0)=2i4=0,它的子路径如 i2=1i3=0i4=0 也是最短路,确定需求下多时段(T时段)生产计划的一般模型,最大生产能力Xm,最大存贮量Im,第1时段初库存量i1,需求量dt,产量xt,存贮量it,生产费c(xt),存贮费h(it),1.根据对时段T末存贮量的要求，确定fT+1(iT+1),2.时段从后向前地计算最小费用，

19、递推公式：,f1(i1)为总费用最小值,3.时段从前向后地确定最优生产计划:由i1,xt(it)及 it+1=it+xt(it)-dt 得到 xt,动态规划模型,随机需求下的多阶段生产计划,需求量随机,存贮量随机,存贮费及总费用随机,优化目标是总费用的期望最小,随机动态规划模型,随机需求:P(dt=1)=1/3,P(dt=2)=2/3(t=1,2,3),存贮费的期望值Eh(it)=h0E(it+xt-dt)=(it+xt-1)P(dt=1)+(it+xt-2)P(dt=2)=(it+xt-1)/3+2(it+xt-2)/3=it+xt-5/3,对于存贮量i3,计划结束时出售剩余量得到的回报为s

20、(i3),期望值Es(i3)=1.5(i3+x3-1)/3+2(i3+x3-2)/3=1.5(i3+x3)-2.5,计划结束时存贮量随机,假定剩余存贮量以1.5的价格出售,随机需求下的多阶段生产计划,1.最后时段(时段3),时段3初的存贮量i3,产量x3(i3),期望费用最小值f3(i3),Es(i3)=1.5(i3+x3)-2.5,P(dt=1)=1/3,P(dt=2)=2/3,f3(0)=c(2)-Es(0)=7-1/2=13/2,x3(0)=2,f3(1)=c(1)-Es(1)=5-1/2=9/2,x3(1)=1,f3(2)=c(0)-Es(2)=0-1/2=-1/2,x3(2)=0,f

21、3(3)=c(0)-Es(3)=0-2=-2,x3(3)=0,计算,2.时段2,时段2,3期望费用最小值,2i2+x24,x2Xm,i2Im,3.时段1,时段1初存贮量i1=1,2i1+x14,时段13期望费用最小值,x2(i2)=0,d1=1,i2=1+3-1=3,d1=2,i2=1+3-2=2,x2(i2)=0,x3(i3)=0,d2=1,i3=3+0-1=2,d2=2,i3=3+0-2=1,x3(i3)=1,x3(i3)=1,d2=1,i3=2+0-1=1,d2=2,i3=2+0-2=0,x3(i3)=2,随机需求下多阶段生产计划,确定性需求下的最优生产计划在开始时已完全确定:x1=2，

22、x2=0，x3=2,随机需求下的最优生产计划只有当每个时段初的存贮量知道后才能确定!,建立动态规划模型的主要步骤(以求解多阶段生产计划问题为例),1.将整个问题划分为若干离散阶段.,2.定义状态(如存贮量)和决策(如产量).,3.建立状态转移律(如it+1=it+xt-dt).,4.确定允许状态集合和允许决策集合(如itIm,xtXm).,5.列出最优方程(ft(it)并确定终端条件（fT+1(iT+1)）.,6.时段从后向前地求解最优方程.,状态应描述过程特征;能直接或间接观测;具有无后效性.,7.按时段从前向后地确定最优决策.,动态规划模型的优点(与静态规划模型比较),1.能够得到全局最优

23、解,变量个数减少，约束集合简单，在目标函数和状 态转移律无解析表达式时，也可用穷举法求解.,全过程化为一系列结构相似、互相关联的子过程.,2.可以得到一族最优解,得到全过程和所有后部子过程的各个状态的最优解.,用于最优决策和最优值对状态的稳定性或找次优解.,模型反映了动态过程演变的联系和特征.,3.计算时可以利用实际知识和经验提高求解效率,动态规划模型的主要缺点,每类问题要具体分析,在定义状态、建立状态转移律等方面，需要灵活的技巧，由此带来了应用的局限性.,状态个数随维数呈指数增长,高维问题求解十分困难.,2.用数值方法求解时存在维数灾,1.没有统一的标准模型，也没有万能的构造模型的方法,动态规划模型在经济管理领域中的应用,货物存贮,设备更新,资源分配,任务均衡,水库调度,可靠性,