最优化问题概述.ppt

1、第一章 最优化问题概述,最优化技术是一门较新的学科分支。它是在本世纪五十年代初在电子计算机广泛应用的推动下才得到迅速发展，并成为一门直到目前仍然十分活跃的新兴学科。最优化所研究的问题是在众多的可行方案中怎样选择最合理的一种以达到最优目标。,1 最优化问题的数学模型与基本概念,数学模型就是对现实事物或问题的数学抽象或描述。,建立数学模型时要尽可能简单，而且要能完整地描述所研究的系统，具体建立怎样的数学模型需要丰富的经验和熟练的技巧。即使在建立了问题的数学模型之后，通常也必须对模型进行必要的数学简化以便于分析、计算。,建立最优化问题数学模型的三要素：,（1）决策变量和参数。 决策变量是由数学模型的

2、解确定的未知数。参数表示系统的控制变量，有确定性的也有随机性的。,（2）约束或限制条件。 由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。,（3）目标函数。 这是作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。,解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径r、高h。 问题的约束条件是所铸圆柱体重量与球重相等。即,例1.把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？,则得数学模型： s.t. Subject to.,问题目标是圆柱体表面积最小。即

3、min,即 即,此时圆柱体的表面积为,分别对r.h.求偏导数,并令其等于零.有:,利用在高等数学中所学的Lagrange乘子法可求解本问题,例2.多参数曲线拟合问题 已知两个物理量x和y之间的依赖关系为: 其中 和 待定参数,为确定这些参数,对x.y测得m个实验点: 试将确定参数的问题表示成最优化问题.,解:很显然对参数 和 任意给定的一组数值,就由上式确定了 y关于x的一个函数关系式,在几何上它对应一条曲线,这条曲线不一定通过那m个测量点,而要产生“偏差”. 将测量点沿垂线方向到曲线的距离的 平方和作为这种“偏差”的度量.即 显然偏差S越小,曲线就拟合得越好,说明参数值就选择得越好，从而我们

4、的问题就转化为5维无约束最优化问题。即：,例3.（混合饲料配合）以最低成本确定满足动物所需营养的最优混合饲料。下面举一个简化了的例子予以说明。 设每天需要混合饲料的批量为100磅，这份饲料必须含：至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养,配料,每磅配料中的营养含量,钙,蛋白质,纤维,每磅成本（元）,石灰石 谷物 大豆粉,0.380 0.00 0.00 0.001 0.09 0.02 0.002 0.50 0.08,0.0164 0.0463 0.1250,解:根据前面介绍的建模要素得出此问题的数学模型如下:

5、 设 是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。,成分为：,例4：两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，弹性模量为E，屈曲强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。,受力分析图,圆杆截面图,桁杆示意图,解：桁杆的截面积为 ：,桁杆的总重量为：,负载2p在每个杆上的分力为：,于是杆截面的应力为：,此应力要求小于材料的屈曲极限，即,圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为,由此得稳定约束：,另外还要考虑到设计变量d和h

6、有界。,从而得到两杆桁架最优设计问题的数学模型：,例5 （运输问题） 设有位于不同城市的m个电视机厂A1，A2，Am，其产量分别为a1，a2，am（台），其产品供应n个城市B1，B2，Bn。每个城市的需要量分别为b1，b2，bn（台）。假定产需平衡，即,已知从Ai到Bj的运费单价为cij（元/台）（i=1,2, m；j=1,2, n）。问由每个厂到每个城市的运输量各为多少时，即既能保证需要量，又能使总运费最少？,例6、选址问题,问：选择适当地点建仓库，在满足商店需求条件下，总费用最小。,解：设xi ( i=1,2,3)为是否在 Ai 建仓库 yij ( i=1,2,3, j=14)由 i仓库向

7、 j商店运货量,y11 + y21 = d1 y12 + y22 + y32 = d2 y23+ y33 = d3 y14 + y24 + y34 = d4 x1 + x2 + x3= 2 y11 + y12 + y14 a1x1 y21 + y22 + y23 + y24a2x2 y32 + y33 + y34 a3x3 xi 为01， yij 0,混合整数规划,例7：某市场营销调查指派问题 市场营销调查公司有3个新客户需要进行市场调查，目前正好有3个人没有其他工作，由于他们的对不同市场的经验和能力不同，估计他们完成不同任务所需时间如下表。公司面临的问题是如何给每个客户指派一个项目主管（代理

8、商），使他们完成市场调查的时间最短。,设xij=1表示指派主管i完成第j项市场调查，否则xij=0 则问题的数学模型为：,min f= 10 x11+15x12+9x13+9x21+18x22+5x23+6x31+14x32+3x33 x11+x12+x13 = 1 x21+x22+x23 = 1 x31+x32+x33 = 1 x11+x21+x31 = 1 x12+x22+x32 = 1 x13+x23+x33 = 1 xij0，i=1，2，3；j=1，2，3,指派问题（Assignment problem） 指派问题是01整数规划问题。在实践中经常会遇到：有m项任务要m个人去完成（每人只

9、完成一项工作），在分配过程中要充分考虑各人的知识、能力、经验等，应如何分配才能使工作效率最高或消耗的资源最少？这类问题就属于指派问题。引入01变量xij,例8（非线性方程组的求解） 解非线性方程组是相当困难的一类问题，由于最优化方法的发展，对解非线性方程组提供了一种有力的手段。,n维欧氏空间 向量 向量变量实值函数： 无约束最优问题：,最优化问题的一般数学模型,其中 均为向量 的实值函数，,目标函数,不等式约束,等式约束,称满足所有约束条件的向量 为容许解，或可行解，或可行点，全体容许点的集合称为容许集或可行集，记为 。,若 是连续函数，则 是闭集。,在容许集中找一点 ，使目标函数 在该点取最小值，即满足： 的过程即为最优化的求解过程。 称为问题的最优点或最优解， 称为最优值。,定义1：整体（全局）最优解：若 ，对于一切 ，恒有 则称 是最优化问题的整体最优解。 定义2：局部最优解：若 ，存在某邻域 ，使得对于一切 ，恒有 则称 是最优化问题的局部最优解。其中 严格最优解：当 ，有