为总费用最小值3时段从前向后地确定最优生产计划.ppt

短跑模型 用最大冲力F跑全程, 可取得最好成绩 最长的短跑赛程以体内能量E(t)不小于零为标准 t E E0 O tc te (单调增) v小 E增加 v大 E减少 最远距离(最长的短跑赛程)为 短跑模型 Keller根据当时的世界记录得到F, τ的估计值: 后来根据1987年约翰逊的百米成绩(9.83s)修正参数: 估计用最大冲力跑全程时最长的短跑赛程 中长跑模型 当赛程超过Dc时不能用最大冲力跑全程 将赛程分为3个阶段: 初始阶段(0?t ?t1) 用最大冲力跑, 在短时间获得高速度. 中间阶段(t1 ?t ? t2) 保持匀速. 最后阶段(t2 ?t ? T) 把体内能量用完, 靠惯性冲刺. 问题: 确定t1 ,t2 及3个阶段的速度v1(t), v2(t), v3(t) 中长跑模型 初始阶段用最大冲力跑, 与短跑模型相同 t1待定 最后阶段把体内能量用完, E(t)=0 中间阶段保持匀速 t2, v2待定 中长跑模型 中间阶段 在条件E(t2)=0下求v(t)使D(v(t))最大 t1, t2, v2待定 中长跑模型 引入乘子?化为无条件极值 泛函极值必要条件 确定t1, t2, v2 模型解释 t v t1 t2 O T v2 中长跑模型3段速度示意图 赛跑的最佳策略是最后把体内能量全部用完, 靠惯性 冲刺,这必然导致速度的短暂下降, 单从赛跑的时间看 (不考虑比赛的策略), 这样做是最优的. Keller对一般模型提出分段解法, 不能证明是最优的, 但它是合理的简化, 在将动力学与生理学相结合, 用 建模方法探讨体育问题上提供了范例. 最后一段(通常一两秒钟)速度有所下降 13.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 时段t的产量 xt (t=1,2,3) xt≤Xm=4，it≤Im=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+2?2=7 为使3个时段的总费用最小，时段3末的存贮量应为0 i3= 0 f3(1)=c(1)= 3+2?1=5 f3(2)=c(0)=0 x3(0)=2 i3= 1 x3(1)=1 i3= 2 x3(2)=0 分析与 求解 2. 时段2 需求量d2=1 时段2初存贮量i2, 产量x2(i2), 时段2,3最小费用之和 时段2的费用: c(x2)+h(i2) i3=i2+x2-1 1≤i2+x2≤3 i2 x2 c(x2) h(i2) f3(i2+x2-1) c+ h+ f3 f2(i2)，x2(i2) 0 1 5 0 7 12 f2(0)=11 x2(0)=3 0 2 7 1 5 13 0 3 9 2 0 11* 1 0 0 0 7 7* f2(1)=7 x2(1)=0 1 1 5 1 5 11 1 2 7 2 0 9 2 0 0 1 5 6 f2(2)=6 x2(2)=0 2 1 5 2 0 7 3 0 0 2 0 2* f2(3)=2 x2(3)=0 3. 时段1 时段1初存贮量i1=1, 产量x1(i1), 需求量d1=2 时段1~3最小费用之和 时段1的费用: c(x1)+h(i1) i2=i2+x2-2 2≤i2+x2≤5 i1 x1 c(x1) h=i1+x1-2 f2(i1+x1-2) c+ h+ f2 f1(i1)，x1(i1) 1 1 5 0 11 16 f1(1)=15 x1(1)=2 1 2 7 1 7 15* 1 3 9 2 6 17 1 4 11 3 2 16 f1(1)=15, x1(1)=2