数学建模与数学实验第五讲§1.ppt

* §1 问题描述与无约束优化问题数学模型 一、优化问题数学模型的描述 最优化问题在科学研究、工程技术和经济管理等诸多领域中最常遇到的为题。例如，资源分配问题是利用有限的资源合理分配使生产的产品数量最多、效益最大；运输安排问题是要在满足物资需求和运载条件下使运输总费用最低；编制生产计划问题是按照生产的工艺流程和客户要求，尽量降低人力、设备、原材料等成本使总利润率最高。随着科学技术特别是计算机的普及，以及数学理论与方法向各个应用领域广泛深入地渗透，在信息时代，最优化理论和技术必将在社会的诸多方面起着越来越大的作用。 最优化问题在高等数学课程中已经作了初步的介绍，我们以一个简单的例子回顾一下。 将周长为2p的矩形绕其一边旋转一周而构成的圆柱体，求矩形的边长各为多少时，圆柱体体积最大？ 设矩形的边长分别为a, b, 由于a, b含义的相同性, 不妨设圆柱体绕边长为b的一边旋转构成, 则圆柱体的体积为 V=πa2b (1) 并且有2(a+b)=2p, 0a,bp, 即 a+b=p, 0a,bp (2) 其目的是求满足条件(2)情况下体积V的最大值, 即 max V=πa2b s.t. a+b=p, 0a,bp (3) (3)式就是我们所求问题的数学模型。其中s.t.(subject to)表示目标函数max V=πa2b 中的变量受约束于条件(2)式，(2)式也称为约束条件。 这个模型的求解方法我们已经非常熟悉，我们将其求解过程作简单描述，用以引出要介绍的问题。 方法一、从约束条件中解出a(或b), 代回目标函数中, 将问题转化为一元函数的无条件极值问题求解。 方法二、引入参数λ, 利用Lagrange乘数法, 将其转化为多元函数的无条件极值问题。 一般的最优化模型描述为 min z = f (x) s.t. gi (x)≤ 0 i=1,2,···,m 其中对目标函数z = f (x)可以是求最小(min)也可以是求最大(max)。 对于更普遍问题来说, 变量个数很多, 约束条件也很多, 且并不都是等式形式。因此, 利用高等数学中求最优化的方法往往是很困难的。 其一, 难以从约束条件中解出一些变量为另一些变量的显函数形式; 其二, 如果约束条件中有不等式约束时, Lagrange乘数法无法使用; 其三, 即使约束条件中均为等式约束时, 我们利用Lagrange乘数法求微分后, 需要求一个多元非线性方程组的根, 有时这是很难办到的事情。因此, 我们必须考虑求最优化问题的数值解法。 我们上面描述的一般优化模型是带有约束条件的模型形式, 称为约束优化模型, 不带有约束条件的模型形式称为无约束优化模型。优化问题的数学模型一般统称为数学规划问题。 我们先来介绍无约束优化模型及其算法。还是从具体模型开始讨论。 产销量的最佳安排问题 某厂一种产品有甲乙两种牌号, 讨论在产销平衡的情况下如何确定各自的产量, 使总利润最大。所谓产销平衡是指工厂的产量等于市场的销量。利润既取决于销量和(单件)价格, 又取决于产量和(单件)成本。按照市场经济规律, 甲的价格p1固然会随其销量x1的增长而降低, 同时乙销量x2的增长也会使甲的价格有稍微的下降, 可以简单地假设其价格与销量成线性关系, 即 p1=b1-a11x1-a12x2, b1, a11, a12 0, a11a12 甲的成本q1随其产量的增长而降低, 且有一渐进值, 合理的假设为负指数关系, 即 q1=r1 e-d1 x1 +c1 , r1, d1, c10 二、无约束优化模型解法简介 乙的价格和成本遵循同样的规律, 即 p2=b2-a21x1-a22x2, b2, a21, a22 0, a22a21 q2=r2 e-d2 x2 +c2 , r2, d2, c20 于是总利润为 z(x1, x2 )=(p1-q1 )x1+(p2-q2 )x2