《多阶段生产计划寻找最短路》由会员分享，可在线阅读，更多相关《多阶段生产计划寻找最短路（52页珍藏版）》请在金锄头文库上搜索。
1、 连续动态过程的优化归结为求泛函的极值连续动态过程的优化归结为求泛函的极值. 求泛函极值的常用方法求泛函极值的常用方法: 变分法变分法, 最优控制论最优控制论. 离散动态过程的优化离散动态过程的优化 动态规划模型动态规划模型.静态优化问题静态优化问题优化目标是数值优化目标是数值最优策略是数值最优策略是数值 函数对应的数值称为泛函函数对应的数值称为泛函(函数的函数函数的函数).动态优化问题动态优化问题优化目标是数值优化目标是数值最优策略是最优策略是函数函数12.1 速降线与短程线速降线与短程线 通过两个古典问题介绍变分法的基本概念通过两个古典问题介绍变分法的基本概念, 给出主要结果给出主要结果.
2、 速速降降线线问问题题 给定竖给定竖直直平面内不在一条垂直线上的两个点平面内不在一条垂直线上的两个点A, B, 求连接求连接A, B的光滑曲线，使质的光滑曲线，使质点在重力作用下沿该曲线以点在重力作用下沿该曲线以最最短时间短时间从从A滑到滑到B (摩擦力不计摩擦力不计). A. B若沿陡峭曲线下滑若沿陡峭曲线下滑, 虽路径加长，但速度增长很快虽路径加长，但速度增长很快.若沿直线段若沿直线段AB下滑下滑, 路径虽短路径虽短, 但速度增长慢但速度增长慢; 速速降降线线问问题题 . A. B建立坐标系建立坐标系xOy, xyy=y(x)O曲线弧长曲线弧长 能量守恒能量守恒质点在曲线质点在曲线y(x)
3、上的速度上的速度ds/dt 质点沿曲线质点沿曲线y(x)从从A到到B的时间的时间 求求y(x) 使使 J(y(x) 达到最小达到最小. m质点质量，质点质量，g重力加速度重力加速度 A(0,0), B(x1,y1), 曲线曲线AB y=y(x) 满足条件满足条件短短程程线线问问题题 . A. Bxyzo给定曲面上的两个点给定曲面上的两个点A, B, 求曲面上连接求曲面上连接A, B的最短曲线的最短曲线. 建立坐标系建立坐标系 A(x0, y0, z0 ), B(x1, y1 , z1 )曲线的弧长曲线的弧长 曲线的长度曲线的长度 求求y =y(x), z =z(x) 使使J(y(x) , z(
4、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)泛函、泛函的变分和极值泛函、泛函的变分和极值自变量自变量t，函数，函数x(t), y(t) 函数、函数的微分和极值函数、函数的微分和极值 泛函、泛函的变分和极值泛函、泛函的变分和极值 1. 对于对于t在某域的任一个值在某域的任一个值, 有有y的一个值与之对应的一个值与之对应, 称称y是是t的函数，记作的函数，记作y=f(t) 1.对于某函数集合的每一个函对于某函数集合的每一个函数数x(t),
5、有有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的线性主部称
6、的线性主部称泛函的变分泛函的变分,记作记作 J(x0(t) 泛函、泛函的变分和极值泛函、泛函的变分和极值函数、函数的微分和极值函数、函数的微分和极值 泛函、泛函的变分和极值泛函、泛函的变分和极值 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)达到极值的必要条件达到
7、极值的必要条件 欧拉方程欧拉方程( (最简泛函极值的必要条件最简泛函极值的必要条件) )最简泛函最简泛函F具有二阶连续偏导数，具有二阶连续偏导数，x(t)为二阶可微函数为二阶可微函数 固定端点条件下的泛函固定端点条件下的泛函 J(x(t)在在x(t)达到极值的必要条件达到极值的必要条件: x(t)满足二阶微分方程满足二阶微分方程两个任意常数由两个任意常数由 确定确定 欧拉方程欧拉方程用欧拉方程解速降线问题用欧拉方程解速降线问题求求y(x) 使使 达到最小达到最小 , 且且欧拉方程欧拉方程圆滚线方程圆滚线方程 c2=0, c1由由y(x1)=y1确定确定.横截条件横截条件( (变动端点问题变动端
8、点问题) )容许函数容许函数 x(t)的一个端点固定的一个端点固定: x(t1)=x1; 另一个端点另一个端点在给定曲线在给定曲线 x= (t) 上变动上变动: x(t2)= (t2) (t2可变可变).x(t). A. Bx= (t)txot2欧拉方程在欧拉方程在变动端点的定解条件变动端点的定解条件 x= (t)垂直于横轴垂直于横轴 (t2固定固定) x= (t)平行于横平行于横轴轴包含多个未知函数泛函的欧拉方程包含多个未知函数泛函的欧拉方程欧拉方程欧拉方程泛函的条件极值泛函的条件极值求求u(t) U (容许集合容许集合) 使使J(u(t)在条件在条件下达到极值下达到极值, 且且x(t) X
9、 (容许集合容许集合) 最优控制问题最优控制问题: u(t)控制函数控制函数, x(t)状态函数状态函数(轨线轨线).泛函的条件极值泛函的条件极值用拉格朗日乘子化为无条件极值用拉格朗日乘子化为无条件极值欧拉方程欧拉方程由方程组和端点条件解出最优控制由方程组和端点条件解出最优控制u(t)和最优轨线和最优轨线x(t).Hamilton函数函数12.2 生产计划的制订生产计划的制订问题问题 生产任务是在一定时间内提供一定数量的产品生产任务是在一定时间内提供一定数量的产品. 生产费用随着生产率生产费用随着生产率(单位时间的产量单位时间的产量)的增加而变大的增加而变大. 贮存费用随着已经生产出来的产量的
10、增加而变大贮存费用随着已经生产出来的产量的增加而变大. 生产计划用每一时刻的累积产量表示生产计划用每一时刻的累积产量表示.建模目的建模目的寻求寻求最优生产计划最优生产计划, 使完成生产任务所需的总费用使完成生产任务所需的总费用(生产费用与贮存费用之和生产费用与贮存费用之和)最小最小.分析与假设分析与假设生产任务生产任务: t=0开始生产开始生产, t=T提供数量为提供数量为Q的产品的产品.生产计划生产计划(累积产量累积产量): x(t)生产率生产率(单位时间产量单位时间产量):生产费用生产费用贮存费用贮存费用总费用总费用 生产率提高一个单位的生产费用与生产率成正比生产率提高一个单位的生产费用与
11、生产率成正比 贮存费用与贮存量成正比贮存费用与贮存量成正比模型与求解模型与求解求求x(t) ( 0, 0 t T)使使C(x(t)最最小小.欧拉方程欧拉方程考察考察x(t) 0 (0 t T) 的条的条件件txQT0只有当生产任务只有当生产任务Q 足够大足够大时才需要从时才需要从 t=0开始生产开始生产.若若 怎么办怎么办? ?模型模型解释解释最优生产计划最优生产计划满足方程满足方程 边际成本边际成本生产费用生产费用贮存费用贮存费用边际贮存边际贮存最优生产计划在边际成本的变化率等于边际贮存时达到最优生产计划在边际成本的变化率等于边际贮存时达到.生产计划的制订生产计划的制订 最优生产计划最优生产
12、计划的目标函数只考虑生产费用与贮存的目标函数只考虑生产费用与贮存 费用费用, 并对这两种费用作了最简单的假设并对这两种费用作了最简单的假设. 对于泛函极值问题用古典变分法求解对于泛函极值问题用古典变分法求解, 得到得到最优生最优生 产计划产计划x(t)(累积产量累积产量)为二次函数为二次函数. 实际条件实际条件x(t) 0 导致对已知参数的要导致对已知参数的要求求: 对函数施加的闭约束对函数施加的闭约束, 如对生产率的限制如对生产率的限制 可能导致可能导致古典变分法的失败古典变分法的失败.若参数不满足该要求怎样处理若参数不满足该要求怎样处理?12.3 国民收入的增长国民收入的增长背景和问题背景
13、和问题 国民经济收入的来源国民经济收入的来源: 扩大再生产的积累扩大再生产的积累 资金；满足人民生活需要的消费资金资金；满足人民生活需要的消费资金 . 如何安排积累资金和消费资金的比例，如何安排积累资金和消费资金的比例， 使国民经济收入得到最快的增长使国民经济收入得到最快的增长. 从最优控制的角度讨论十分简化的模型从最优控制的角度讨论十分简化的模型.一般模型一般模型国民经济收入国民经济收入 x(t)，其中用于积累资金的部分，其中用于积累资金的部分y(t),求最优积累率使国民收入求最优积累率使国民收入 x(t)在时间在时间T内增长最快内增长最快.积累率积累率 u(t)=y(t)/x(t)国民收入
14、增长率国民收入增长率对偶等价对偶等价泛函条件极值泛函条件极值哈密顿函数哈密顿函数求解最优控制函数求解最优控制函数u(t)和最优状态和最优状态x(t).简化模型简化模型假设假设讨论函数讨论函数f的具体、简化形式的具体、简化形式描述以上假设的最简模型描述以上假设的最简模型国民收入相对增长率国民收入相对增长率 积累率积累率u较小时较小时 随随u的增加而增加的增加而增加 积累资金扩大再生产的促进作用积累资金扩大再生产的促进作用. 随着随着u的变大的变大 的增加变慢的增加变慢. u增加到一定程度后增加到一定程度后 反而减小反而减小 消费资金太少对国民收入的制约作用消费资金太少对国民收入的制约作用.模型模
15、型求解求解对于最简模型对于最简模型 不必解泛函极不必解泛函极值问题值问题, 可以直接得到可以直接得到 u=a/2b时时 最大最大.使国民收入使国民收入 x(t)增长最快的最优积累率是常数增长最快的最优积累率是常数 u=a/2b结果结果解释解释12.4 渔船出海渔船出海背景和问题背景和问题 继续讨论开发渔业资源的最大经济效益模型继续讨论开发渔业资源的最大经济效益模型. 用出海渔船数量表示捕捞强度用出海渔船数量表示捕捞强度, 作为控制函数作为控制函数. 当渔场鱼量增长到一定数量后才出海捕捞当渔场鱼量增长到一定数量后才出海捕捞. 用特殊形式的控制函数将动态优化问题化为用特殊形式的控制函数将动态优化问
16、题化为 普通的函数极值普通的函数极值.模型假设模型假设 x(t)的自然增长服从的自然增长服从Logistic规律规律, 单位时间单位时间 捕捞量与捕捞量与u(t), x(t)成正比成正比. 当当t 时才派时才派渔船出海渔船出海, 且且u(t)=U(常数常数). 鱼的出售单价为鱼的出售单价为p, 每只渔船单位时间费用为每只渔船单位时间费用为c, 折扣因子折扣因子 (通货膨胀率通货膨胀率)为为 .渔场鱼量渔场鱼量x(t), 渔船数量渔船数量u(t) x(0)=N/K (K很大很大), t 时时x(t)保持稳定保持稳定.建模与求解建模与求解 泛函极值问题泛函极值问题目标函数目标函数: 捕鱼业的长期效
17、益捕鱼业的长期效益x(t)在在t= 的的连续性连续性 函数极值问题函数极值问题建模与求解建模与求解目标函数目标函数: 捕鱼业的长期效益捕鱼业的长期效益b(1)费用费用-价格比的下界价格比的下界模型解释模型解释最优解应在边际收益等于边际损失时达到最优解应在边际收益等于边际损失时达到单位时间利润单位时间利润短期利润的增加短期利润的增加:长期收益的减少长期收益的减少:渔渔 船船 出出 海海以渔船数量以渔船数量u(t)为控制函数为控制函数的最大效益模型的最大效益模型泛函极值泛函极值.假定假定u(t)的特殊形式的特殊形式 , 化为化为函数极值函数极值. u(t)假定的假定的合理性合理性: 泛函极值问题的
18、解正是取这种形式泛函极值问题的解正是取这种形式.最优解在边际收益等于边际损失时达到最优解在边际收益等于边际损失时达到, 是短期利益是短期利益与长期利益取得折中的结果与长期利益取得折中的结果.12.5 赛跑的速度赛跑的速度背景和问题背景和问题 将赛程分成若干阶段将赛程分成若干阶段, 根据赛跑运动员的生理根据赛跑运动员的生理 条件对各阶段的速度作最恰当的安排条件对各阶段的速度作最恰当的安排, 以期获以期获 得最好的成绩得最好的成绩. Keller提出一个简单模型提出一个简单模型(1974), 根据根据4个生理参个生理参 数从最优控制的角度确定各阶段的速度函数数从最优控制的角度确定各阶段的速度函数,
19、 并并 可以预测比赛成绩可以预测比赛成绩. 寻求速度安排的最佳策略是复杂的生理力学问题寻求速度安排的最佳策略是复杂的生理力学问题.问题分析问题分析 运动员在赛跑中要克服体内外的阻力以达到运动员在赛跑中要克服体内外的阻力以达到 和保持一定速度和保持一定速度, 需要发挥向前的冲力需要发挥向前的冲力. 这些能量怎样分配到赛跑的各个阶段这些能量怎样分配到赛跑的各个阶段, 并在到并在到 达终点前将其全部用完达终点前将其全部用完. 为冲力作功提供能量的来源为冲力作功提供能量的来源: 赛跑前贮存在体内赛跑前贮存在体内 的能量的能量;赛跑中通过氧的代谢作用产生的能量赛跑中通过氧的代谢作用产生的能量. 模型要确
20、定的模型要确定的3个关系个关系:冲力与速度冲力与速度 冲力作功与能量来源冲力作功与能量来源速度与比赛成绩速度与比赛成绩 将最佳成绩归结成以距离为目标、与速度、将最佳成绩归结成以距离为目标、与速度、 冲力、能量等函数有关的极值问题冲力、能量等函数有关的极值问题.模型假设模型假设 赛跑中体内外的阻力与速度成正比赛跑中体内外的阻力与速度成正比, 比例系数比例系数 -1 赛跑中在氧的代谢下单位时间产生的能量是常数赛跑中在氧的代谢下单位时间产生的能量是常数 赛跑前贮存在体内供赛跑的能量是常数赛跑前贮存在体内供赛跑的能量是常数E0 运动员能发挥的最大冲力是运动员能发挥的最大冲力是F 运动员具有单位质量，初
21、速为零运动员具有单位质量，初速为零. 比赛成绩：比赛成绩：“一定距离下时间最短一定距离下时间最短”等价为等价为 “一定时间内距离最大一定时间内距离最大” .一般模型一般模型以速度以速度v(t)在时间在时间T内跑完赛程内跑完赛程D阻力与速度成正比阻力与速度成正比, 比例系数比例系数 -1单位质量运动员，初速为零单位质量运动员，初速为零运动员的最大冲力是运动员的最大冲力是F单位时间产生的能量是单位时间产生的能量是 赛跑前贮存的能量是赛跑前贮存的能量是E0运动员赛跑速度运动员赛跑速度v(t), 体内能量体内能量E(t)D固定固定, 求求v(t)使使T最小最小T固定固定, 求求v(t)使使D最大最大以
22、以D(v(t)为目标的泛函条件极值为目标的泛函条件极值 ( ,F, ,E0为已知参数为已知参数)短跑模型短跑模型用最大冲力用最大冲力F跑全程跑全程, 可取得最好成绩可取得最好成绩最长的短跑赛程以体内能量最长的短跑赛程以体内能量E(t)不小于零为标准不小于零为标准tEE00tcte(单调增单调增)v小小 E增加增加 v大大 E减少减少 最远距离最远距离(最长的短跑赛程最长的短跑赛程)为为短跑模型短跑模型Keller根据当时的世界记录得到各参数的估计值根据当时的世界记录得到各参数的估计值:后来根据后来根据1987年约翰逊的百米成绩年约翰逊的百米成绩(9.83s)修正参数修正参数:估计用最大冲力跑全
23、程时最长的短跑赛程估计用最大冲力跑全程时最长的短跑赛程中长跑模型中长跑模型当赛程超过当赛程超过Dc时不能用最大冲力跑全程时不能用最大冲力跑全程将赛程分为将赛程分为3个阶段个阶段:初始阶段初始阶段(0 t t1) 用最大冲力跑用最大冲力跑, 在短时间获得高速度在短时间获得高速度.中间阶段中间阶段(t1 t t2) 保持匀速保持匀速.最后阶段最后阶段(t2 t T) 把体内能量用完把体内能量用完, 靠惯性冲刺靠惯性冲刺.问题问题: 确定确定t1 ,t2 及及3个阶段的速度个阶段的速度v1(t), v2(t), v3(t)中长跑模型中长跑模型初始阶段初始阶段用最大冲力跑用最大冲力跑, 与短跑模型相同
24、与短跑模型相同t1待定待定最后阶段最后阶段把体内能量用完把体内能量用完, E(t)=0中间阶段中间阶段保持匀速保持匀速t2, v2待定待定中长跑模型中长跑模型中间阶段中间阶段在条件在条件E(t2)=0下求下求v(t)使使D(v(t)最大最大t1, t2, v2待定待定中长跑模型中长跑模型引入乘子引入乘子 化为无化为无条件极值条件极值泛函极值必要条件泛函极值必要条件确定确定t1, t2, v2模型模型解释解释tvt1t20Tv2中长跑模型中长跑模型3 3段速度示意图段速度示意图 赛跑的最佳策略是最后把体内能量全部用完赛跑的最佳策略是最后把体内能量全部用完, 靠惯性靠惯性 冲刺冲刺,这必然导致速度
25、的短暂下降这必然导致速度的短暂下降, 单从赛跑的时间看单从赛跑的时间看 (不考虑比赛的策略不考虑比赛的策略), 这样做是最优的这样做是最优的. Keller对一般模型提出分段解法对一般模型提出分段解法, 不能证明是最优的不能证明是最优的, 但它是合理的简化但它是合理的简化, 在将动力学与生理学相结合在将动力学与生理学相结合, 用用 建模方法探讨体育问题上提供了范例建模方法探讨体育问题上提供了范例.最后一最后一段段(通常一两通常一两秒钟秒钟)速度有所下降速度有所下降12.6 多阶段最优生产计划多阶段最优生产计划离散动态优化问题离散动态优化问题动态规划模型是有效方法动态规划模型是有效方法 问题问题
26、 考察考察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 确定需求问题确定需求问题优化模型优化模型(最短路最短路)随机需
27、求问题随机需求问题分析分析与与求解求解 生产费用生产费用时段时段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 4，itIm=3需求量需求量dt准备费准备费c0=3成本成本k=2存贮费存贮费h0=1最大生产能力最大生产能力Xm=4最大存贮量最大存贮量Im=3将多时段生产计划问题简化为多个单时段问题将多时段生产计划问题简化为多个单时段问题 由后向前分解由后向前分解时段时段3初的存贮量初的存贮量i3
28、, 产量产量x3(i3), 最小费用最小费用f3(i3)1. 最后时段最后时段(时段时段3)需求量需求量d3=2 f3(0)=c(2)= 3+2 2=7为使为使3个时段的总费用最小，时段个时段的总费用最小，时段3末的存贮量应为末的存贮量应为0 i3= 0f3(1)=c(1)= 3+2 1=5f3(2)=c(0)=0x3(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
29、-1 1i2+x23 i2x2c(x2)h(i2)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 2i2+x25 i1x1c(x1)h
30、=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)=0x3(0)=2最短路问题最短路问题 002101231路段1路段2路段1路段3终点多阶段生产计划多阶段生产计划寻找最短路寻找最短路5811145811069172750各路段站点各路段站点: i1=1, i
31、2=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时段时段)生产计划的一般模型生产计划的一般模型最大生产能力
32、最大生产能力Xm 最大存贮量最大存贮量Im 第第1时段初库存量时段初库存量i1 需求量需求量dt, 产量产量xt , 存贮量存贮量it, 生产生产费费c (xt), 存贮费存贮费h(it) 1. 根据对时段根据对时段T末存贮量的要求，确定末存贮量的要求，确定fT+1(iT+1) 2. 时段时段从后向前从后向前地计算最小费用，递推公式：地计算最小费用，递推公式：f1(i1)为总费用最小值为总费用最小值 3.时段时段从前向后从前向后地确定最优生产计划地确定最优生产计划: 由由i1 , xt(it) 及及 it+1= it +xt(it)-dt 得到得到 xt动态规划模型动态规划模型随机需求下的多阶
33、段生产计划随机需求下的多阶段生产计划 需求量随机需求量随机存贮量随机存贮量随机存贮费及总费用随机存贮费及总费用随机优化目标是总费用的期望最小优化目标是总费用的期望最小随机动态规划模型随机动态规划模型随机需求随机需求: 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
34、(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)=1/3, P(dt=2)=2/3 f3(0)=c(2)-Es(0)=7-1/2=13/2, x3(0)=2f3(1)=c(1
35、)- 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期望期望费用最小值费用最小值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(
36、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 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
37、/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=0x3=2i2=2x2=0随机需求下多随机需求下多阶段生产计划阶段生产计划 确定性需求下的最
38、优生产计划在开始时已完全确定确定性需求下的最优生产计划在开始时已完全确定: x1=2，x2=0，x3=2 随机需求下的最优生产计划只有当每个时段初的随机需求下的最优生产计划只有当每个时段初的存贮量知道后才能确定存贮量知道后才能确定! ! 建立动态规划模型的主要步骤建立动态规划模型的主要步骤(以求解以求解多阶段生产计划问题为例多阶段生产计划问题为例) ) 1. 将整个问题划分为若干离散阶段将整个问题划分为若干离散阶段. 2. 定义状态定义状态(如存贮量如存贮量)和决策和决策(如产量如产量). 3. 建立状态转移律建立状态转移律(如如it+1= it+xt-dt). 4. 确定允许状态集合和允许决
39、策集合确定允许状态集合和允许决策集合(如如itIm, xtXm). 5. 列出最优方程列出最优方程( ft(it)并确定终端条件（并确定终端条件（fT+1(iT+1)）. 6. 时段从后向前地求解最优方程时段从后向前地求解最优方程.状态应描述过程特征状态应描述过程特征; ;能直接或间接观测能直接或间接观测; ;具有无后效性具有无后效性. . 7. 按时段从前向后地确定最优决策按时段从前向后地确定最优决策.动态规划模型的优点动态规划模型的优点(与静态规划模型比较与静态规划模型比较)1. 能够得到全局最优解能够得到全局最优解 变量个数减少，约束集合简单，在目标函数和状变量个数减少，约束集合简单，在
40、目标函数和状 态转移律无解析表达式时，也可用穷举法求解态转移律无解析表达式时，也可用穷举法求解. 全过程化为一系列结构相似、互相关联的子过程全过程化为一系列结构相似、互相关联的子过程. 2. 可以得到一族最优解可以得到一族最优解 得到全过程和所有后部子过程的各个状态的最优解得到全过程和所有后部子过程的各个状态的最优解. 用于最优决策和最优值对状态的稳定性或找次优解用于最优决策和最优值对状态的稳定性或找次优解. 模型反映了动态过程演变的联系和特征模型反映了动态过程演变的联系和特征.3. 计算时可以利用实际知识和经验提高求解效率计算时可以利用实际知识和经验提高求解效率动态规划模型的主要缺点动态规划
41、模型的主要缺点每类问题要具体分析每类问题要具体分析, 在定义状态、建立状态转移律在定义状态、建立状态转移律等方面，需要灵活的技巧，由此带来了应用的局限性等方面，需要灵活的技巧，由此带来了应用的局限性.状态个数随维数呈指数增长状态个数随维数呈指数增长, 高维问题求解十分困难高维问题求解十分困难.2. 用数值方法求解时存在维数灾用数值方法求解时存在维数灾1. 没有统一的标准模型，也没有万能的构造模型的方法没有统一的标准模型，也没有万能的构造模型的方法 动态规划模型在经济管理领域中的应用动态规划模型在经济管理领域中的应用 货物存贮货物存贮设备更新设备更新资源分配资源分配任务均衡任务均衡水库调度水库调度可靠性可靠性
