数学模型第四版姜启源第十三章动态优化

1、第十三章 动态(dngti)优化模型13.1 速降线与短程线13.2 生产计划的制订13.3 国民收入(gumnshur)的增长13.4 渔船出海13.5 赛跑的速度13.6 多阶段最优生产计划共五十四页 连续动态(dngti)过程的优化归结为求泛函的极值. 求泛函极值(j zh)的常用方法: 变分法、最优控制论. 离散动态过程的优化 动态规划模型.静态优化问题优化目标是数值最优策略是数值 函数对应的数值称为泛函(函数的函数).动态优化问题优化目标是数值最优策略是函数共五十四页13.1 速降线与短程(dun chn)线 通过两个(lin )古典问题介绍变分法的基本概念, 给出主要结果. 速降线

2、问题 给定竖直平面内不在一条垂直线上的两个点A, B, 求连接A, B的光滑曲线，使质点在重力作用下沿该曲线以最短时间从A滑到B (摩擦力不计). A. B若沿陡峭曲线下滑, 虽路径加长，但速度增长很快.若沿直线段AB下滑, 路径虽短, 但速度增长慢; 共五十四页速降线问题(wnt) . A. B建立(jinl)坐标系xOy, xyy=y(x)O曲线弧长 能量守恒质点在曲线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) 满足条件共五十四页短程(dun c

3、hn)线问题 . A. Bxyzo给定曲面(qmin)上的两个点A, B, 求曲面上连接A, B的最短曲线. 建立坐标系 A(x0, y0, z0 ), B(x1, y1 , z1 )曲线的弧长 曲线的长度 求y =y(x), z =z(x) 使J(y(x) , z(x)达到最小. 满足条件曲面方程f(x,y,z)=0 f(x,y,z)=0曲面上连接A, B的曲线 y =y(x), z =z(x) y =y(x) z =z(x)共五十四页泛函、泛函的变分和极值(j zh)自变量t，函数(hnsh)x(t), y(t) 函数、函数的微分和极值 泛函、泛函的变分和极值 1. 对于t在某域的任一个值

4、, 有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(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(x

5、0(t) 共五十四页泛函、泛函的变分和极值(j zh)函数(hnsh)、函数(hnsh)的微分和极值 泛函、泛函的变分和极值 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)达到极值的必要条件 共五十四页欧拉方程(最简泛函极值(j zh)的必要条件)最简泛函F具有(jyu)二阶连续偏导数，x(t)为二阶可微函数 固定端点条件下的泛函 J(x(t)在x(t)达到极值的必要条件: x(t)

6、满足二阶微分方程两个任意常数由 确定 欧拉方程共五十四页用欧拉方程解速降线问题(wnt)求y(x) 使 达到最小 , 且欧拉方程(fngchng)圆滚线方程 c2=0, c1由y(x1)=y1确定.共五十四页横截条件(tiojin)(变动端点问题)容许函数 x(t)的一个端点(dun din)固定: x(t1)=x1，另一个端点在给定曲线 x=(t) 上变动: x(t2)= (t2) (t2可变).x(t). A. Bx=(t)txot2欧拉方程在变动端点的定解条件 x=(t)垂直于横轴 (t2固定) x=(t)平行于横轴共五十四页包含多个未知函数(hnsh)泛函的欧拉方程欧拉方程(fngch

7、ng)泛函的条件极值求u(t)U (容许集合) 使J(u(t)在条件下达到极值, 且x(t)X (容许集合) 最优控制问题: u(t)控制函数, x(t)状态函数(轨线).共五十四页泛函的条件极值用拉格朗日乘子化为无条件极值欧拉方程(fngchng)由方程组和端点(dun din)条件解出最优控制u(t)和最优轨线x(t).Hamilton函数共五十四页13.2 生产(shngchn)计划的制订问题(wnt) 生产任务是在一定时间内提供一定数量的产品. 生产费用随着生产率(单位时间的产量)的增加而变大. 贮存费用随着已经生产出来的产量的增加而变大. 生产计划用每一时刻的累积产量表示.建模目的寻

8、求最优生产计划, 使完成生产任务所需的总费用(生产费用与贮存费用之和)最小.共五十四页分析(fnx)与假设生产任务: t=0开始(kish)生产, t=T提供数量为Q的产品.生产计划(累积产量): x(t)生产率(单位时间产量):生产费用贮存费用总费用 生产率提高一个单位的生产费用与生产率成正比 贮存费用与贮存量成正比共五十四页模型(mxng)与求解求x(t) (0, 0tT)使C(x(t)最小.欧拉方程(fngchng)考察x(t)0 (0tT) 的条件txQTO只有当生产任务Q 足够大时才需要从 t=0开始生产.若 怎么办? ?共五十四页模型(mxng)解释最优生产(shngchn)计划满

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

10、资金 . 如何安排积累资金和消费资金的比例， 使国民经济收入得到最快的增长. 从最优控制的角度讨论十分简化的模型.共五十四页一般(ybn)模型国民经济收入 x(t)，其中(qzhng)用于积累资金的部分y(t),求最优积累率使国民收入 x(t)在时间T内增长最快.积累率 u(t)=y(t)/x(t)国民收入增长率对偶等价泛函条件极值哈密顿函数求解最优控制函数u(t)和最优状态x(t).共五十四页简化(jinhu)模型假设(jish)讨论函数f的具体、简化形式描述以上假设的最简模型国民收入相对增长率 积累率u较小时 随u的增加而增加 积累资金扩大再生产的促进作用. 随着u的变大 的增加变慢. u

11、增加到一定程度后 反而减小 消费资金太少对国民收入的制约作用.共五十四页模型(mxng)求解对于最简模型 不必解泛函极值问题, 可以直接得到 u=a/2b时 最大.使国民收入(gumnshur) x(t)增长最快的最优积累率是常数 u=a/2b结果解释共五十四页13.4 渔船(y chun)出海背景(bijng)和问题 继续讨论开发渔业资源的最大经济效益模型. 用出海渔船数量表示捕捞强度, 作为控制函数. 当渔场鱼量增长到一定数量后才出海捕捞. 用特殊形式的控制函数将动态优化问题化为 普通的函数极值.共五十四页模型(mxng)假设 x(t)的自然增长服从Logistic规律, 单位时间(shj

12、in) 捕捞量与u(t), x(t)成正比. 当t 时才派渔船出海, 且u(t)=U(常数). 鱼的出售单价为p, 每只渔船单位时间费用为c, 折扣因子 (通货膨胀率)为 .渔场鱼量x(t), 渔船数量u(t) x(0)=N/K (K很大), t 时x(t)保持稳定.共五十四页建模与求解(qi ji) 泛函极值(j zh)问题目标函数: 捕鱼业的长期效益x(t)在t= 的连续性 函数极值问题共五十四页建模与求解(qi ji)目标函数(hnsh): 捕鱼业的长期效益b(1)费用-价格比的下界共五十四页模型(mxng)解释最优解应在边际收益(shuy)等于边际损失时达到单位时间利润短期利润的增加:

13、长期收益的减少:共五十四页渔 船 出 海以渔船(y chun)数量u(t)为控制函数的最大效益模型泛函极值.假定u(t)的特殊形式 , 化为函数极值. u(t)假定的合理性: 泛函极值(j zh)问题的解正是取这种形式.最优解在边际收益等于边际损失时达到, 是短期利益与长期利益取得折中的结果.共五十四页13.5 赛跑(sipo)的速度背景(bijng)和问题 将赛程分成若干阶段, 根据赛跑运动员的生理 条件对各阶段的速度作最恰当的安排, 以期获 得最好的成绩. Keller提出一个简单模型(1974), 根据4个生理参 数从最优控制的角度确定各阶段的速度函数, 并 可以预测比赛成绩. 寻求速度

14、安排的最佳策略是复杂的生理力学问题.共五十四页问题(wnt)分析 运动员在赛跑中要克服(kf)体内外的阻力以达到 和保持一定速度, 需要发挥向前的冲力. 这些能量怎样分配到赛跑的各个阶段, 并在到 达终点前将其全部用完. 为冲力作功提供能量的来源: 赛跑前贮存在体内 的能量, 赛跑中通过氧的代谢作用产生的能量. 模型要确定的3个关系:冲力与速度 冲力作功与能量来源速度与比赛成绩 将最佳成绩归结成以距离为目标, 与速度、 冲力、能量等函数有关的极值问题.共五十四页模型(mxng)假设 赛跑中体内外的阻力(zl)与速度成正比, 比例系数-1 赛跑中在氧的代谢下单位时间产生的能量是常数 赛跑前贮存在

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

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

17、t), v2(t), v3(t)共五十四页中长跑模型(mxng)初始(ch sh)阶段用最大冲力跑, 与短跑模型相同t1待定最后阶段把体内能量用完, E(t)=0中间阶段保持匀速t2, v2待定共五十四页中长跑模型(mxng)中间阶段在条件(tiojin)E(t2)=0下求v(t)使D(v(t)最大t1, t2, v2待定共五十四页中长跑模型(mxng)引入乘子化为无条件极值泛函极值(j zh)必要条件确定t1, t2, v2共五十四页模型(mxng)解释tvt1t2OTv2中长跑模型(mxng)3段速度示意图 赛跑的最佳策略是最后把体内能量全部用完, 靠惯性 冲刺,这必然导致速度的短暂下降,

18、 单从赛跑的时间看 (不考虑比赛的策略), 这样做是最优的. Keller对一般模型提出分段解法, 不能证明是最优的, 但它是合理的简化, 在将动力学与生理学相结合, 用 建模方法探讨体育问题上提供了范例.最后一段(通常一两秒钟)速度有所下降共五十四页13.6 多阶段(jidun)最优生产计划离散(lsn)动态优化问题动态规划模型是有效方法 问题 考察T个时段某产品的生产计划生产准备费c0 单件生产成本k 单件每时段存贮费h0 每时段最大生产能力Xm 每时段最大存贮量Im 第1时段初有库存量i1 制订产品生产计划(每时段产量)使T个时段的总费用最小 已知需求量dt (t=1,2,T) 例 T

19、=3, d1=2, d2=1, d3=2, Xm =4,c0=3, k=2, h0=1, Im =3, i1=1 确定需求问题优化模型(最短路)随机需求问题共五十四页分析(fnx)与求解 生产(shngchn)费用时段t初的存贮量it, 时段t+1初的存贮量 it+1= it+ xt-dt时段t的存贮费 h(it)= h0(it+ xt-dt) = it+xt-dt 时段t的产量 xt (t=1,2,3)xtXm=4，itIm=3需求量dt准备费c0=3成本k=2存贮费h0=1最大生产能力Xm=4最大存贮量Im=3共五十四页将多时段生产计划问题(wnt)简化为多个单时段问题(wnt) 由后向前

20、(xin qin)分解时段3初的存贮量i3, 产量x3(i3), 最小费用f3(i3)1. 最后时段(时段3)需求量d3=2 f3(0)=c(2)= 3+22=7为使3个时段的总费用最小，时段3末的存贮量应为0 i3= 0f3(1)=c(1)= 3+21=5f3(2)=c(0)=0 x3(0)=2i3= 1x3(1)=1i3= 2x3(2)=0分析与求解 共五十四页2. 时段2需求量d2=1 时段2初存贮(cn zh)量i2, 产量x2(i2), 时段2,3最小费用(fi yong)之和时段2的费用: c(x2)+h(i2) i3=i2+x2-1 1i2+x23 i2x2c(x2)h(i2)f

21、3(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)=0共五十四页3. 时段1时段1初存贮(cn zh)量i1=1, 产量x1(i1), 需求量d1=2 时段13最小费用(fi yong)之和时段1的费用: c(x1)+h(i1) i2=i2+x2-2 2i2+x25 i1x1c(x1)h=i1+x1-2f2(i1+x1-2)c+ h+ f2f1(i

22、1)，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共五十四页最短路(dunl)问题 002101231路段1路段2路段1路段3终点多阶段(jidun)生产计划寻找最短路5811145811069172750各路段站点: i1=1, i2=0,1,2,3, i3=0,1,2, i4=0两站点距离: 本时段生产费与存贮费之和 路段3

23、各站点到终点的最短距离: 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时段)生产(shngchn)计划的一般模型最大生产能力(shn chn nn l)Xm 最大存贮量Im 第1时段初库存量i1 需求量dt, 产量xt , 存贮量it, 生产费c (xt), 存贮费h(it) 1. 根据对时段T末存贮量的要求，确定fT+1(iT+1) 2. 时段从后向前地计算最小费

24、用，递推公式：f1(i1)为总费用最小值 3.时段从前向后地确定最优生产计划: 由i1 , xt(it) 及 it+1= it +xt(it)-dt 得到 xt动态规划模型共五十四页随机(su j)需求下的多阶段生产计划 需求量随机(su j)存贮量随机存贮费及总费用随机优化目标是总费用的期望最小随机动态规划模型随机需求: 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

25、对于存贮量i3, 计划结束时出售剩余量得到的回报为s(i3),期望值Es(i3)=1.5(i3+x3-1)/3+2(i3+x3-2)/3=1.5(i3+x3)-2.5 计划结束时存贮量随机, 假定剩余存贮量以1.5的价格出售 共五十四页随机需求下的多阶段(jidun)生产计划 1. 最后(zuhu)时段(时段3)时段3初的存贮量i3, 产量x3(i3), 期望费用最小值f3(i3)Es(i3)=1.5(i3+x3)-2.5P(dt=1)=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/

26、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期望(qwng)费用最小值2i2+x24, x2Xm , i2Imi2x2c(x2)Eh(i2)f3 (i2+x2-1)/3+2 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/

27、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/3共五十四页3. 时段1时段1初存贮(cn zh)量i1=1 2i1+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 30

28、3/18*时段13期望(qwng)费用最小值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随机需求(xqi)下多阶段生产计划 确定性需求下的最优生产(shngchn)计划在开始时已完全确定: x1=2，x2=0，x3=2 随机需求下的最优生产计划只有当每个时段初的存贮量知道后才能确定! 共五十四页 建立动态规划模型的主要步骤(bzhu)(以求解多阶段生产计划问题为例) 1. 将整个问题划分为若干