第13章动态优化模型

1、第十三章第十三章 动态优化模型动态优化模型13.1 速降线与短程线速降线与短程线13.2 生产计划的制订生产计划的制订13.3 多阶段最优生产计划多阶段最优生产计划 连续动态过程的优化归结为求泛函的极值连续动态过程的优化归结为求泛函的极值. 求泛函极值的常用方法求泛函极值的常用方法: 变分法、变分法、最优控制论最优控制论. 离散动态过程的优化离散动态过程的优化 动态规划模型动态规划模型.静态优化问题静态优化问题优化目标是数值优化目标是数值最优策略是数值最优策略是数值 函数对应的数值称为泛函函数对应的数值称为泛函(函数的函数函数的函数).动态优化问题动态优化问题优化目标是数值优化目标是数值最优策

2、略是最优策略是函数函数13.1 速降线与短程线速降线与短程线 通过两个古典问题介绍变分法的基本概念通过两个古典问题介绍变分法的基本概念, 给出主要结果给出主要结果. 速速降降线线问问题题 给定竖给定竖直直平面内不在一条垂直线上的两个点平面内不在一条垂直线上的两个点A, B, 求连接求连接A, B的光滑曲线，使质的光滑曲线，使质点在重力作用下沿该曲线以点在重力作用下沿该曲线以最最短时间短时间从从A滑到滑到B (摩擦力不计摩擦力不计). A. B若沿陡峭曲线下滑若沿陡峭曲线下滑, 虽路径加长，但速度增长很快虽路径加长，但速度增长很快.若沿直线段若沿直线段AB下滑下滑, 路径虽短路径虽短, 但速度增

3、长慢但速度增长慢; 速速降降线线问问题题 . A. B建立坐标系建立坐标系xOy, xyy=y(x)O曲线弧长曲线弧长 2d1dsyx能量守恒能量守恒21d()2dsmmgyt质点在曲线质点在曲线y(x)上的速度上的速度ds/dt 21dd2ytxgy质点沿曲线质点沿曲线y(x)从从A到到B的时间的时间 1201( ( )d2xyJ y xxgy11)(, 0)0(yxyy求求y(x) 使使 J(y(x) 达到最小达到最小. m质点质量，质点质量，g重力加速度重力加速度 A(0,0), B(x1,y1), 曲线曲线AB y=y(x) 满足条件满足条件短短程程线线问问题题 . A. Bxyzo给

4、定曲面上的两个点给定曲面上的两个点A, B, 求曲面上连接求曲面上连接A, B的最短曲线的最短曲线. 建立坐标系建立坐标系 A(x0, y0, z0 ), B(x1, y1 , z1 )曲线的弧长曲线的弧长 22d1dsyzx曲线的长度曲线的长度 1022( ( ), ( )1dxxJ y x z xyzx求求y =y(x), z =z(x) 使使J(y(x) , z(x)达到最小达到最小. 0)(),(,(xzxyxf满足条件满足条件曲面方程曲面方程f(x,y,z)=0 f(x,y,z)=0曲面上连接曲面上连接A, B的曲线的曲线 y =y(x), z =z(x) y =y(x) z =z(

5、x)泛函、泛函的变分和极值泛函、泛函的变分和极值自变量自变量t，函数，函数x(t), y(t) 函数、函数的微分和极值函数、函数的微分和极值 泛函、泛函的变分和极值泛函、泛函的变分和极值 1. 对于对于t在某域的任一个值在某域的任一个值, 有有y的一个值与之对应的一个值与之对应, 称称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(

6、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.

7、 若函数若函数y在域内在域内t点达到极点达到极值，则在值，则在t点的微分点的微分dy(t)=0 4. 若泛函若泛函J(x(t)在函数集合内的在函数集合内的x(t)达到极值达到极值, 则在则在x(t)的的变分变分 J(x(t)=0 0d ( )()y tf tt 5. y在在t的微分的另一表达式的微分的另一表达式5. 泛函泛函J(x(t)在在x(t)的变分可以表为的变分可以表为0)()()(txtxJtxJ泛函泛函J(x(t)在在x(t)达到极值的必要条件达到极值的必要条件 0)()(0txtxJ欧拉方程欧拉方程( (最简泛函极值的必要条件最简泛函极值的必要条件) )21( ( )( , ( )

8、, ( )dttJ x tF t x tx tt最简泛函最简泛函F具有二阶连续偏导数，具有二阶连续偏导数，x(t)为二阶可微函数为二阶可微函数 固定端点条件下的泛函固定端点条件下的泛函 J(x(t)在在x(t)达到极值的必要条件达到极值的必要条件: x(t)满足二阶微分方程满足二阶微分方程d0dxxFFt0 xFxFFFxxxxx tx 2211)(,)(xtxxtx两个任意常数由两个任意常数由 确定确定 欧拉方程欧拉方程用欧拉方程解速降线问题用欧拉方程解速降线问题0 xFxFFFxxxxx tx 11)(, 0) 0(yxyy1201( ( )d2xyJ y xxgy求求y(x) 使使 达到

9、最小达到最小 , 且且欧拉方程欧拉方程yyyyF21),(0 yFyFFFyyyyyxyd()0dyFy FxcFyFycyyyyy)1 (122222/1)1 (cyy)cos1 ()sin(121tcycttcx圆滚线方程圆滚线方程 c2=0, c1由由y(x1)=y1确定确定.横截条件横截条件( (变动端点问题变动端点问题) )容许函数容许函数 x(t)的一个端点固定的一个端点固定: x(t1)=x1，另一个端点，另一个端点在给定曲线在给定曲线 x= (t) 上变动上变动: x(t2)= (t2) (t2可变可变).x(t). A. Bx= (t)txot2欧拉方程在欧拉方程在变动端点的

10、定解条件变动端点的定解条件0)(2ttxFxF x= (t)垂直于横轴垂直于横轴 (t2固定固定)02 ttxF x= (t)平行于横轴平行于横轴02 ttxFxF包含多个未知函数泛函的欧拉方程包含多个未知函数泛函的欧拉方程21( ( ), ( )( , ( ), ( ), ( ), ( )dttJ x tu tF t x tx tu tu ttdd0,0ddxxuuFFFFtt欧拉方程欧拉方程泛函的条件极值泛函的条件极值21( ( )( , ( ), ( )dttJ u tF t x tu tt)(),(,()(tutxtftx求求u(t) U (容许集合容许集合) 使使J(u(t)在条件在

11、条件下达到极值下达到极值, 且且x(t) X (容许集合容许集合) 最优控制问题最优控制问题: u(t)控制函数控制函数, x(t)状态函数状态函数(轨线轨线).泛函的条件极值泛函的条件极值21( ( )( , ( ), ( )dttJ u tF t x tu tt)(),(,()(tutxtftx用拉格朗日乘子化为无条件极值用拉格朗日乘子化为无条件极值21( ( ), ( )( , , )( )( , , )dttI x tu tF t x utf t x uxt),()(),(),(uxtftuxtFuxtH21()dttHxt欧拉方程欧拉方程d()()0dd()()0dxxuuHxHxt

12、HxHxt00)(uHtxH),(0)(uxtfxuHxHt由方程组和端点条件解出最优控制由方程组和端点条件解出最优控制u(t)和最优轨线和最优轨线x(t).Hamilton函数函数13.2 生产计划的制订生产计划的制订问题问题 生产任务是在一定时间内提供一定数量的产品生产任务是在一定时间内提供一定数量的产品. 生产费用随着生产率生产费用随着生产率(单位时间的产量单位时间的产量)的增加而变的增加而变大大. 贮存费用随着已经生产出来的产量的增加而变大贮存费用随着已经生产出来的产量的增加而变大. 生产计划用每一时刻的累积产量表示生产计划用每一时刻的累积产量表示.建模目的建模目的寻求寻求最优生产计划

13、最优生产计划, 使完成生产任务所需的总费用使完成生产任务所需的总费用(生产费用与贮存费用之和生产费用与贮存费用之和)最小最小.分析与假设分析与假设生产任务生产任务: t=0开始生产开始生产, t=T提供数量为提供数量为Q的产品的产品.生产计划生产计划(累积产量累积产量): x(t)生产率生产率(单位时间产量单位时间产量):)(txf ddfxx 生产费用生产费用贮存费用贮存费用)(txg0( ( ) ( ( )( ( )dTC x tf x tg x tt总费用总费用 生产率提高一个单位的生产费用与生产率成正比生产率提高一个单位的生产费用与生产率成正比 贮存费用与贮存量成正比贮存费用与贮存量成

14、正比)()(2txktxg)()(21txktxf)(tx 模型与求解模型与求解2120( ( )( )( )dTC x tk x tk x ttQTxx)(, 0)0(求求x(t) ( 0, 0 t T)使使C(x(t)最小最小.d0dxxFFt欧拉方程欧拉方程)()(221txktxkF0)(212txkk tTkTkQktkktx1221212444)(考察考察x(t) 0 (0 t T) 的条件的条件txQTO1224/ kTkQ 只有当生产任务只有当生产任务Q 足够大足够大时才需要从时才需要从 t=0开始生产开始生产.,4/122kTkQ 若若 怎么办怎么办? ?0) 0(x 模型模

15、型解释解释最优生产计划最优生产计划tTkTkQktkktx1221212444)(0)(212txkk 满足方程满足方程221dd( )ddkk xttx)()(21txktxfdd()ddftx)()(2txktxgddfx 边际成本边际成本生产费用生产费用贮存费用贮存费用2ddgkx边际贮存边际贮存最优生产计划在边际成本的变化率等于边际贮存时达到最优生产计划在边际成本的变化率等于边际贮存时达到.生产计划的制订生产计划的制订 最优生产计划最优生产计划的目标函数只考虑生产费用与贮存的目标函数只考虑生产费用与贮存 费用费用, 并对这两种费用作了最简单的假设并对这两种费用作了最简单的假设. 对于泛

16、函极值问题用古典变分法求解对于泛函极值问题用古典变分法求解, 得到得到最优最优生生 产计划产计划x(t)(累积产量累积产量)为二次函数为二次函数. 实际条件实际条件x(t) 0 导致对已知参数的要求导致对已知参数的要求:1224/ kTkQ 对函数施加的闭约束对函数施加的闭约束, 如对生产率的限制如对生产率的限制 可能导致可能导致古典变分法的失败古典变分法的失败.BtxA)( 若参数不满足该要求怎样处理若参数不满足该要求怎样处理?13.3 国民收入的增长国民收入的增长背景和问题背景和问题 国民经济收入的来源国民经济收入的来源: 扩大再生产的积累扩大再生产的积累 资金资金, 满足人民生活需要的消

17、费资金满足人民生活需要的消费资金 . 如何安排积累资金和消费资金的比例，如何安排积累资金和消费资金的比例， 使国民经济收入得到最快的增长使国民经济收入得到最快的增长. 从最优控制的角度讨论十分简化的模型从最优控制的角度讨论十分简化的模型.一般模型一般模型),()(uxtftx国民经济收入国民经济收入 x(t)，其中用于积累资金的部分，其中用于积累资金的部分y(t),求最优积累率使国民收入求最优积累率使国民收入 x(t)在时间在时间T内增长最快内增长最快.积累率积累率 u(t)=y(t)/x(t)(max,)0(0Txxx),(1uxtfH1000 xTxxxuxtftxuxtfuxtftux)

18、()(),()(),(),()(,国民收入增长率国民收入增长率对偶等价对偶等价,)(,)0(),()(10 xTxxxuxtftx0min( ( )dTJ u tt泛函条件极值泛函条件极值哈密顿函数哈密顿函数求解最优控制函数求解最优控制函数u(t)和最优状态和最优状态x(t).简化模型简化模型)()(/ )(buautxtx假设假设讨论函数讨论函数f的具体、简化形式的具体、简化形式1, 0)()0()()(0)2()()(xTxxxxbuautxxbuxabuaut描述以上假设的最简模型描述以上假设的最简模型国民收入相对增长率国民收入相对增长率)(/ )(txtx 积累率积累率u较小时较小时

19、随随u的增加而增加的增加而增加 积累资金扩大再生产的促进作用积累资金扩大再生产的促进作用.)(/ )(txtx 随着随着u的变大的变大 的增加变慢的增加变慢.)(/ )(txtx u增加到一定程度后增加到一定程度后 反而减小反而减小 消费资金太少对国民收入的制约作用消费资金太少对国民收入的制约作用.)(/ )(txtx xbuauuxtf)(),(1, 0)()0()()(0)2()()(xTxxxxbuautxxbuabuaut模型模型求解求解1000 xTxxxuxtftxuxtfuxtftux)()(),()(),(),()(,xbuauuxtftx)(),()(对于最简模型对于最简模型

20、 不必解泛函不必解泛函极值问题极值问题, 可以直接得到可以直接得到 u=a/2b时时 最大最大.xbuautx)()()(tx 使国民收入使国民收入 x(t)增长最快的最优积累率是常数增长最快的最优积累率是常数 u=a/2b2140204( ),( )e,ln2atbxabu tx txTbax结果结果解释解释13.3 多阶段最优生产计划多阶段最优生产计划离散动态优化问题离散动态优化问题动态规划模型是有效方法动态规划模型是有效方法 问题问题 考察考察T个个时段某产品的时段某产品的生产计划生产计划生产准备费生产准备费c0 单件生产成本单件生产成本k 单件每时段单件每时段存贮费存贮费h0 每时段最

21、大生产能力每时段最大生产能力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-

22、dt时段时段t的的存贮费存贮费 h(it)= h0(it+ xt-dt) = it+xt-dt 时段时段t的的产量产量 xt (t=1,2,3)0, 00,23)(0tttttxxxkxcxcxtXm=4 4，itIm=3需求量需求量dt准备费准备费c0=3成本成本k=2存贮费存贮费h0=1最大生产能力最大生产能力Xm=4最大存贮量最大存贮量Im=3将多时段生产计划问题简化为多个单时段问题将多时段生产计划问题简化为多个单时段问题 由后向前分解由后向前分解时段时段3初的存贮量初的存贮量i3, 产量产量x3(i3), 最小费用最小费用f3(i3)1. 最后时段最后时段(时段时段3)需求量需求量d3

23、=2 f3(0)=c(2)= 3+2 2=7为使为使3个时段的总费用最小，时段个时段的总费用最小，时段3末的存贮量应为末的存贮量应为0 i3= 0f3(1)=c(1)= 3+2 1=5f3(2)=c(0)=0 x3(0)=2i3= 1x3(1)=1i3= 2x3(2)=0分析分析与与求解求解 2. 时段时段2需求量需求量d2=1 时段时段2初存贮量初存贮量i2, 产量产量x2(i2), 时段时段2,3最小费用之和最小费用之和时段时段2的费用的费用: c(x2)+h(i2) i3=i2+x2-1 )1()()(min)(22322222xifihxcifx1i2+x23 i2x2c(x2)h(i

24、2)f3(i2+x2-1)c+ h+ f3f2(i2)，x2(i2)0150712f2(0)=11x2(0)=3027151303920 11*10007 7*f2(1)=7x2(1)=01151511127209200156f2(2)=6x2(2)=021520730020 2*f2(3)=2x2(3)=03. 时段时段1时段时段1初存贮量初存贮量i1=1, 产量产量x1(i1), 需求量需求量d1=2 时段时段13最小费用之和最小费用之和时段时段1的费用的费用: c(x1)+h(i1) i2=i2+x2-2 )2()()(min)(11211111xifihxcifx2i2+x25 i1x

25、1c(x1)h=i1+x1-2f2(i1+x1-2)c+ h+ f2f1(i1)，x1(i1)11501116f1(1)=15x1(1)=212717 15*139261714113216f1(1)=15, x1(1)=2i2=i1+x1-2=1+2-2=1i3=i2+x2-1=1+0-1=0最优生产计划：最优生产计划：3个时段的产量为个时段的产量为x1=2，x2=0，x3=2x2(i2)=x2(1)=0 x3(0)=2最短路问题最短路问题 002101231路段1路段2路段1路段3终点多阶段生产计划多阶段生产计划寻找最短路寻找最短路5811145811069172750各路段站点各路段站点:

26、 i1=1, i2=0,1,2,3, 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时段时段)生产计划的一般模型生产计划的一般

27、模型最大生产能力最大生产能力Xm 最大存贮量最大存贮量Im 第第1时段初库存量时段初库存量i1 需求量需求量dt, 产量产量xt , 存贮量存贮量it, 生产生产费费c (xt), 存贮费存贮费h(it) 1. 根据对时段根据对时段T末存贮量的要求，确定末存贮量的要求，确定fT+1(iT+1) 2. 时段时段从后向前从后向前地计算最小费用，递推公式：地计算最小费用，递推公式：1 , 1,),()()(min)(111TTtXxIidxiiifihxcifmtmtttttttttxtttf1(i1)为总费用最小值为总费用最小值 3.时段时段从前向后从前向后地确定最优生产计划地确定最优生产计划:

28、由由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+x

29、t-2)/3=it+xt-5/3 对于存贮量对于存贮量i3, 计划结束时出售剩余量得到的回报为计划结束时出售剩余量得到的回报为s(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.5P(dt=1

30、)=1/3, P(dt=2)=2/3 f3(0)=c(2)-Es(0)=7-1/2=13/2, x3(0)=2f3(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 f3(3)=c(0)- Es(3)=0-2= -2, x3(3)=0 计算计算2. 时段时段2 时段时段2,3期望期望费用最小值费用最小值3/ ) 2(23/ ) 1()()(min)(22322322222xifxifiEhxcifx2i2+x24, x2Xm , i2Imi2x2c(x2)Eh(i2)f3 (i2+x2-1)/3+2

31、f3 (i2+x2-2)/3c+Eh+ f3f2(i2)，x2(i2)0271/335/679/6f2(0)= 37/3x2(0)=40394/317/679/604117/3-1 37/3*1151/335/667/6f2(1)= 31/3x2(1)=31274/317/667/61397/3-1 31/3*2001/335/6 37/6*f2(2)=37/6x2(2)=02154/317/655/62277/3-125/33004/317/6 25/6*f2(3)= 25/6x2(3)=03157/3-119/33. 时段时段1时段时段1初存贮量初存贮量i1=1 3/ )2(23/ ) 1

32、()()(min)(11211211111xifxifiEhxcifx2i1+x14 i1x1c(x1)Eh(i1)f2 (i1+x1-1)/3+2 f2 (i1+x1-2)/3c+Eh+ f2f1(i1)，x1(i1)1151/3105/9306/18f1(1)=303/18x1(1)=31274/3161/18311/181397/333/6 303/18*时段时段13期望期望费用最小值费用最小值x2(i2)=0 d1=1i2=1+3-1=3d1=2 i2=1+3-2=2 x2(i2)=0 x3(i3)=0 d2=1i3=3+0-1=2d2=2 i3=3+0-2=1 x3(i3) =1 x3(i3)=1 d2=1i3=2+0-1=1d2=2 i3=2+0-2=0 x3(i3) =2 d2=2d2=2d2=1d2=1d1=2d1=1i1=1x1=3i2=3x2=0i3=2x3=0i3=1x3=1i3=1x3=1i3=0 x3=2i2=2x2=0随机需求下多随机需求下多阶段生产计划阶段生产计划 确定性需求下的最优生产计划在开始时已完全确定确定性需求下的最优生产计划在开始时已完全确定: x1=2，x2=0，x3=2 随机需求下的最优生产计划只有当每个时段初的随机需求下的最优生产计划只有当每个时段初的存贮量知道后才能确定存贮量知道后