优化,报童,变分模型.ppt

优化模型,优化模型的数学意义,优化问题是在工程技术、经济管理和科学研究等领域 中最常遇到的一类问题。设计师要求在满足强度要求等 条件下合理选择材料的尺寸；公司经理要根据生产成本 和市场需求确定产品价格和生产计划，使利润达到最 大；调度人员要在满足物质需求和装载条件下安排从各 供应点到各需求点的运量和路线，使运输总费用达到最 低。 ,本章讨论的是用数学建模的方法来处理优化问题：即 建立和求解所谓的优化模型。注意的是建模时要作适当 的简化，可能使得结果不一定完全可行或达到实际上的 最优，但是它基于客观规律和数据，又不需要多大的费 用。如果在建模的基础上再辅之以适当的检验，就可以 期望得到实际问题的一个比较圆满的回答。,本章介绍较为简单的优化模型，归结为微积分中的极 值问题，因而可以直接使用微积分中的方法加以求解。,当你决定用数学建模的方法来处理一个优化问题时， 首先要确定优化的目标，其次确定寻求的决策，以及决策 受到哪些条件的限制。在处理过程中，要对实际问题作若 干合理的假设。最后用微积分的进行求解。在求出最后决 策后，要对结果作一些定性和定量的分析和必要的检验。,一、存储模型,问题的提出,工厂定期订购原料存入仓库供生产之用；车间一次加 工零件供装配线生产之用；商店成批订购各种商品，放 进货柜以备零售；诸多问题都涉及到一个存储量为多大 的问题：存储量过大，会增加存储费用；存储量过小， 会增加订货次数，从而增加不必要的订购费用.,本节讨论在需求稳定的情况下，两个简单的存储模 型: 不容许缺货和容许缺货的存储模型.,1.不容许缺货的存储模型,例 配件厂为装配线生产若干种部件. 轮换生产不同 的部件时因更换设备要支付一定的生产准备费用（与产 量无关）. 同一部件的产量大于需求时需支付存储费用. 已知某一部件的日需求量为100件，生产准备费为5000 元, 存储费为每日每件一元. 如果生产能力远大于需求， 并且不容许出现缺货，试安排生产计划: 即多少天生产 一次（生产周期）、每次产量多少可使总费用最少？,分析,若每天生产一次，无存储费，生产准备金5000元， 故每天的总费用为5000元；,若10天生产一次，每次生产1000件，准备金5000 元，存储费900+800+100=4500元。平均每天950元。,若50天生产一次，每次生产5000件，准备金5000 元，存储费4900+4800+100=122500元，平均每天 2500元。,以上分析表明: 生产周期过短，尽管没有存储费，但 准备费用高, 从而造成生产成本的提高；生产周期过长, 会造成大量的存储费用, 也提高了生产成本. 由此可以 看到, 选择一个合适的生产周期，会降低产品的成本； 从而赢得竞争上的优势。,模型假设,为处理上的方便，假设模型是连续型的，即周期 ， 产量 均为连续变量.,1.每天的需求量为常数 ；,2.每次生产的准备费用为 每天每件的存储费为,3.生产能力无限大，即当存储量为零时， 件产品可以 立即生产出来.,建模,设存储量为 以 递减，直到 则有,在一个微小时间中段 中，存储费为 因而在一个周期中，总存储 费用为,准备费用为 ，故总费用为,所以，每天的平均费用为,模型求解,原问题转变为使取极小值的问题。利用求极值的方 法，对式求导，并令其为零:,即有:,而,将代入到式，得最小的平均费用为,，被称为经济订货批量公式（EOQ公式）.,结果解释,由，式可以看到，当 （准备费用）提高时，生 产周期和产量都变大；当 存储费增加时，生产周期和 产量都变小；当需求量 增加时，生产周期变小而产量 变大。这些结果都是符合常识的。,以 代入、 式得 元.,注意的是：用此公式计算的结果与原题有一定的误 差，原因在于变量选择的不同.,敏感性分析,讨论参数 对生产周期 的影响.,我们用相对改变量来衡量结果对参数的敏感程度. 对 的敏感程度记为 定义式为,再由 得,而,代入上式，得,同理可得:,即： 每增加 ， 增加 每增加 ， 减 少,注 此模型也可适用于商店的进货问题.,3.容许缺货的模型,下面讨论的是容许缺货的问题. 为此做以下的假设:,生产能力无限大（相对于需求量），容许缺货，每天 每件产品缺货造成的损失费为 但缺货量在下次补足。,建模,因存储量不足而造成缺货时，可以认为存储量 为 负值（如图所示），周期仍记为 是每周期的存储 量，当 时， 故有,在 到 这段缺货时间内需求率 不变， 按原斜率继续下降， 由于规定缺货量需补足，所以在 时数量为 的产品立即达，,使下周期初的存储量恢复到,则每天的平均费用为,与不容许缺货的模型相似，一个周期内的存储费是 乘以图中三角形 的面积，缺货损失费是 乘以三角形 面积 加上准备费，得一周期内的总费用为,解模,为求使 达到最小的 在中分别对 求偏导，并令其为零，即,由第二个方程, 得,再由第一个方程, 得,即,再代入前一式, 有,由于每周期的供货量为 有,记,与不容许缺货模型的结果、进行比较，得到,结果分析 由式知 再由知,此说明周期及供货量应增加，周期初的存储量减少。 缺货损失费 越大， 越小（越接近1），从而,由此说明不容许缺货是容许缺货的特殊情况.,二、生猪出售的最佳时机,一饲养场每天投入4元资金用于饲料、设备、人力， 估计可使一头80公斤重的生猪每天增加2公斤. 目前生 猪出售的市场价格为每公斤8元，但是预测每天会降低 0.1元. 问该场该什么时候出售这样的生猪，如果这样 的估计和预测有出入，对结果有多大的影响.,分析 造成价格变化的两大因素,1.资金投入使得成本增加； 2.市场因素使得价格降低.,模型假设 每天投入4元资金使生猪体重每天增加常 数 公斤，生猪出售的价格每天降低常数 （0.1元）。,模型建立,记 时间； 生猪体重； 出售的价格； 出售的收入； 每天的投入； 纯利润。则有,最后得纯利润为：,其中 求使 达到最大值的,模型求解,该问题是二次函数的极值问题。在上式对 求导，并 令其为零，则有,得,敏感性分析,因在上面的讨论中，参数 是预测的，下面讨论当 它们发生变化时对模型价格的影响。,是 的增函数，下图反映了 与 的关系。,1.设每天生猪价格的下降率 不变，研究 变化 对 的影响。由式，得,下表给出了 与 的数据关系。,2.设每天生猪体重的增加 公斤不变，研究 变化 对 的影响。由式得,即 是 的减函数。,用相对改变量来衡量结果对参数的敏感程度。 对 的敏 感程度记为 定义式为,由式，得,再代入式，得,将 代入式，得,此说明: 若每天的体重增加 则出售时间推迟,类似可以定义 对 的敏感度,由式可得,当 时，可得,此说明价格每降低 则出售的时间提早,说明: 该模型的建模和解模都较为简单. 我们的注意 力是放在对模型的结果分析上, 即重点讨论敏感性分析 上. 另外该模型还适用与其它与之类似的模型.,三、报童问题,问题 报童每天清晨从邮局批进报纸进行零售，晚上 将卖不掉的报纸返回邮局进行处理. 售出一份报纸可获 得相应的利润，而处理一份报纸会造成亏损. 为此要考 虑报童如何确定每天的进货量以达到最大利润.,随机性的函数极值问题,模型假设,1.报童知道卖出各个数量的概率的大小.,2.设报童每天批进报纸 份，进价为 元，卖价为 元，处理价为 元.,建模,由假设，报童每卖出一份报纸获利 元，每处理 一份报纸亏损 元。当卖出量 时，报童获利,元，,当卖出量 时，报童获利,元.,由大数定律，报童每天的平均收入因为每天收入的期望 值来表示.,设每天卖出 份报纸的概率为 因而期望收入为,从而问题转变为求出进货量 使期望收入 达到最 大.,解模,为了用微积分的方法解决该问题，将变量连续化，从 而相应的概率函数 用连续型随机变量的概率密度 来表示. 于是由连续性随机变量的数学期望公式,由极值存在的条件，对式求导并令其为零，再由含,参变量积分的求导公式得,整理后得:,即:,再由合比定理得,即,再由概率密度的性质:,从而上式为,由于 是一个常数，当概率密度为已知时，可由 式计算相应的 在统计学中数 又称为 分位数.,数值 是卖出一份报纸的收益与处理一份报,纸所造成亏损的比值。这个比值越大，进报量就应该 大一点，如果处理价 变小，则应该少进一些.,应用举例,设某报亭销售新民晚报，售价为 元，进价为 元，处理价为 元，销售量服从参数为 的指数 分布，求相应的进货量,解 由,即,在Mathematic下计算积分，输入命令.,IntegrateE(-0.015x)*0.015,x,0,74,得积分值为0.670441，即进报纸的份数近似为74.,分析，若提高处理价，如处理价为 元，则,输入命令：,IntegrateE(-0.015x)*0.015,x,0,92,得积分值为0.748421，即进货量为92.,四、森林救火问题,问题 在森林发生火灾时，要派出消防人员去灭火. 需要选择合理的方案，使得救火的费用和森林被毁所造 成的损失达到最低.,问题分析,设起火时间为 开始灭火， 时火被扑灭， 在整个灭火过程中，总费用由损失费与救援费构成，设 在时刻 时，森林被毁面积为 则被毁总面积为,考虑 单位时间被毁面积，它表示的是火势,的蔓延程度，注意到, 时，火势越来越大， 时，火势逐渐减少，且,由此即得关系,假设,单位面积损失费为 ；,当 时， 与时间成正比，即,称为蔓延速度；,派出 名消防队员进行灭火，每名队员的灭火速度为 ；则当 时，有,每名消防队员单位时间的灭火费用为 ，于是在灭,火过程中，每名队员的费用为 ；,每名队员的一次性开支为,注 模型假设的意义：火势以起火点为中心，以均匀 速度向四周呈圆形蔓延，蔓延的半径 与时间 成正 比。又被毁面积与 成正比，故被毁面积 与 成正 比，从而 与 成正比.,火过程中，每名队员的费用为 ；,每名队员的一次性开支为,注 模型假设的意义：火势以起火点为中心，以均匀 速度向四周呈圆形蔓延，蔓延的半径 与时间 成正 比。又被毁面积与 成正比，故被毁面积 与 成正 比，从而 与 成正比。,火过程中，每名队员的费用为 ；,每名队员的一次性开支为,注 模型假设的意义：火势以起火点为中心，以均匀 速度向四周呈圆形蔓延，蔓延的半径 与时间 成正 比。又被毁面积与 成正比，故被毁面积 与 成正 比，从而 与 成正比。,又，每名消防队员的灭火速度 为常量，它将火势的 蔓延速度压低为负值，因此,由于 此说明要把火扑灭，应满足 名,消防队员。,记 因 即有,即,由此得,由定积分的几何意义，得,建模,设派出 名消防队员，则由前面讨论知: 森林总损失 费为 开支费用为 于是目 标函数为,解模,因 作变换 从而将目标函数化为,其中， 是一个与 无关的常量。两边对 求导，并令 其为零，则有,由于 解之得：,而 相应的极值点为,从上式中可以看到，要扑灭火势就得派出 名消防 队员，并预计灭火需要的时间为,分析,参数 为已知，而 由森林的类型，消防队 员的素质等因素确定. 参数 的值，可从灭火 现场的考察来估计.,有人认为每名消防队员的救火速度为常量的假设是不 妥当的，因为当火势蔓延程度 大的时候消防队员的救 火速度会小些，于是 是 的单调减函数，若假设,或,于是用替换 可得,从而得到 的极值点为,五、变分法简介,众所周知，平面上两点的距离以直线段最短，现在我 们用数学的方法来推导这一结论.,设平面上两定点为 和 这两点的 连线的方程为 弧段 的长为,显然函数 还需满足条件:,则原问题转变为求函数 使得成立并使 弧长 取最小值。,由于 故积分,当 时取最小值，即该曲线为直线段时距离达到 最小值。,一、固定端点的简单泛函极值问题,设 为函数类，若有法则，使在该法则之下，对 中的每一个元素都可以确定一个相应的数与之对应， 则称该法则为 上的一个泛函。,例如，取 区间上的黎曼可积函数 类，定义泛函 为,在此定义之下，函数类 称为泛函的定义域，泛函一,般记为,考虑简单泛函,其中，函数 且,问题是求函数 满足条件，并使由式定 义的泛函取得极小值或极大值。这样的问题称为泛函,极值问题。,假设函数 使泛函 取得极值，任 意取得函数 要求它满足条件,若限制函数在 的范围中，则函 数,在 时取得极值。,由函数取得极值的必要条件，有 因,再由复合函数微分法，得,再由分部积分公式，第二项积分可化为,由得,因而有,所以，,由函数 的任意性及因子 的连续性， 则有,是使泛函 取得极值的函 数应满足的方程。这个方程成为Eular方程。,注意到，Eular方程经展开后，成为,该方程为一个二阶常微分方程，方程的解还需满足条件 ，即,二、固定端点的简单泛函的条件极值问题,考虑简单泛函,其中函数 且,及满足条件,求函数 满足条件和并使由式定义的泛 函取得极小值。这样的问题就称为泛函条件极值问题。,如同条件极值，泛函条件极值问题也可拉格朗日乘数 法加以解决。为此作辅助函数,和辅助泛函,其中 为引入的待定常数。,得到的使泛函 取极值的函数 即为 原问题的解。,六、生产安排问题,泛函极值问题,工厂与客户签定合同，规定工厂在时间 内向客户提 供 件产品。为了使工厂在生产过程中的费用达到最 小，工厂应如何安排生产？,模型假设,1.工厂在单位时间内生产这类产品的生产费用是当时 产品增长率的函数;,2.工厂必须按合同规定交付产品，提前交付或滞后交 付都属违约，存储费与产量成正比。,建模,设在时刻 时开始生产， 为时刻 时的累计 产量，则由条件所设，有,记在时刻 时单位时间内所生产的产品费用为 产 品增长率为 即,由假设1，有,因而有 令,其中 为比例常数，所以在时段 内总的生产费用 为,记在 时刻单位时间内的产品存储费用为 由假设2. 有,其中 为比例常数。于是在时间段 总存储费用为,所以在时间段 总费用为,即问题转变为求满足条件的函数 使得泛函取 得极小值。,解模,由于被积函数为 故相应的,Eular方程为,与构成一个二阶常微分方程的边际问题。方程的通 解为,再由初始条件 得,当生产计划为 时，工厂完成合同中的生产任务的总 费用最小。,分析,由于 所以 的图象为开口向上的经过原 点一条抛物线。又由于当 时， 所以只有 在第一象限中的部分才是问题的解。,1.若当 时，总有,即有,即有,即,等价于,此说明，在条件满足时，所规定的生产计划是最优 的计划。,2.若式不成立，即,则必存在 使得 令 则平移曲线 在时间 区间中，由 可完成相应的生产计划。 但此时要增加存储费,这显然是不合理的。反之在区间 中不安排生 产，而从 开始生产，并到 时完成生产计划。此 为最佳生产计划。,应用,例1 设 则,相应的生产方案为,例2 设 则 同样可以得到,令 即在区间 按 安 排生产。,思考：该问题解的意义是什么？,七、商品的最优价格,条件泛函极值问题,如何根据市场的变化确定商品的价格，以获得最大利 润，这是企业经营决策中的一个重要问题。,模型假设,根据供销平衡的原则，设产量和销售量均为 每件产 品的生产成本为 价格为 则总成本为 销售 收入为,建模,在市场竞争的制约下，销售量是价格的减函数，即,此函数称为需求函数。因而在总成本不变的情况下，利 润为,从而问题转变为求 使 达到最大。,解模,当销售价格 不随时间变化而变化时，可采用求极值 的方法。即令,即,在经济学中，上式的左端称为边际收入，右边称为边 际成本，因此式所反映的一个重要的定律：最优经济,效益是当边际收入等于边际成本时取得。,模型分析,设需求函数,在该问题中， 称为绝对需求量，表示向社会提供的 免费产品的需求量。而,表示市场需求对价格的敏感程度。,此时,由此得到，,上式说明最优价格由两部分组成：第一部分为成本的 一半，另一部分与绝对需求量成正比，与敏感程度成反 比。,要求在一段时间 内达到总销售量 的情况。,设价格 为时间的函数。并设需求函数仍然为,则相应的总利润为,且函数 还需满足条件,此是一个条件泛函极值问题。由拉格朗日乘数法，得,因被积函数,中未出现 故相应的Eular方程为,即,解得：,将代入到条件 得到,因被积函数为常数，得,即,所以，,解出 得,代入，有,即,从式中可以看到，最优价格与成本无关，若销售周期 延长，则价格 可定得高一些；若销售量 增多，则价 格 可低一些。,考虑因滞销所产生的影响,假设其它情况如同 此时由于因滞销而造成了损 失，因而成本不再是常量。而应该是时间的函数。,设 的相对增长率为 即,注意到初始成本,解此微分方程、，得到解,于是如同的讨论，总收益为,限制条件为,由此得到条件泛函为,相应的Eular方程为,即,解出 得,再代入限制条件,得,积分后得到，,从而,代入式，得到,八、赛跑的最优速度安排,问题 赛跑时运动员要根据自己的体力来合理安排速 度是重要的技术问题。能充分发挥运动员的潜力。使得 比赛的成绩有所提高。那么如何安排体能使比赛成绩达 到最佳？,假设,1.运动员能发挥出的最大冲力是有限的。在除了其它 因素的干扰下，每个运动员认为自己的最大冲力是常数。,2.在运动的时候，来自体外的阻力和来自体内的阻力 存在，与速度成正比；,3.在运动过程中，运动员通过呼吸从外界吸入氧气， 然后通过体内的消化系统、血液系统等进行新陈代谢作 用，为运动员提供能量。假定运动员足够强壮，使得这,种能量的提供速度在运动期间保持常量。,4.运动员在运动过程中体内所存储的能量是逐渐减少 的。对每个运动员来说，在平时能提供的体能可设为常 量。这个量就是运动刚开始时体能的初始值。,建模,假设比赛距离为 运动员跑的时间为 速度函数为 则有,则问题转变为求速度 使得在赛跑距离 一定时， 赛跑时间 取得最小值。该问题等价于求速度函数 使得在赛跑时间一定时，赛跑的距离 取得最大值。,记 为运动员能够发挥出来的冲力函数。记 为 运动员的最大冲力，则有,记 为体内外的总阻力系数。由假设2总阻力为,则由牛顿定律，有,其中 为为运动员的质量。取 则式可写为,初始条件为,从而问题转变成如何控制函数 使得在赛跑时间 一定时，由和所确定的赛跑距离 达到最大。,记 为运动员的体能函数， 为运动员体能的最 大值，由假设4，知 为常量，且有,记 为在单位时间内由氧的新陈代谢为运动员所提供 能量，由假设3， 为常量，单位时间内体能的变化为由 氧的新陈代谢为运动员所提供能量和所消耗的能量（为 获得速度 而所作的功 ）的差，即,现在的问题是：寻找合适的函数 使 得在赛跑时间 一定时，由，所确定的赛跑距 离 达到最大值。,解模,把整个过程分成三个阶段：初始阶段、中间阶段和最 后阶段。,1.初始阶段,这个阶段的时间段为 其中 为待定的常量，且 在这个阶段中，赛跑的速度为,在这个阶段中，假设运动员是以全力赛跑的，即以最 大的冲力在加速跑。此时即有 从而方程为,由和初始条件 可解出,将代入，则变成,由及初始条件可得,在中应有,因 及,由连续函数的零点定理，知存在某个时刻 使得,若运动员赛跑的时间 则运动员应该以最大的冲 力去赛跑，此时赛跑只有初始阶段，即,如果让运动员用最大冲力去跑，而要保持 则 能跑的最大距离为,所以，若赛程不超过 则运动员应该以最大的冲力来 跑才是最优策略。,2.最后阶段,设此阶段为 其中 为待定参数，且 而赛跑速度为,假设在这个时段中运动员已经把全部存储的能量使用,完了，而是依靠在 时获得的速度的惯性来冲刺。因此 有,将代入，得,由条件，得,该方程可写成,相应的解为,其中 为这个阶段的初始速度。,3.中间阶段,为了确定数值 设该阶段为 赛跑速 度为 现求取得最大赛程 时的速度,由于在初始阶段和最后阶段的速度都已经有了相应的 表达式和，故赛程为,其中 还满足,由方程及初始条件，得方程,当 时得到,现在的问题是，在条件满足的条件下，求泛函的 极值。由Lagrange乘数法，作辅助泛函,在上式中将与 无关的量略去，则可写成,在上式中，第一项依赖于 后两项依赖于数值,因而上式是对函数 的泛函极值问题。对函数 是 函数的极值问题，由Eular方程，有,即,从中解出,4.确定参数,因 是连续函数，故在 时有,即得,(21),(22),(24),在(21)中将 代入后积分得,在最后阶段能量为零，把 代入能量公式，并积 分得,(24),(25),由(23)、(24)和(25)可确定三个参数，由此可确定速度,最优速度的函数图形如图。,模型