《最优化课件-研究生-2012修改版第一章最优化原理建模与数学预备知识》由会员分享，可在线阅读，更多相关《最优化课件-研究生-2012修改版第一章最优化原理建模与数学预备知识（69页珍藏版）》请在金锄头文库上搜索。
1、最优化方法,各位同学：欢迎大家选修“最优化方法”课程！ 本课程为工科硕士研究生学位基础课程，课程采用平时考核和期末考试综合评定成绩的方法结业。 本课程课件为非公共用品，敬请不要商量拷贝课件事宜！ 建议购买相关教材或者借阅参考书，适当做听课笔记！,工科硕士研究生 最优化方法 张鸿雁,计划学时数：32学时 主要参考书目： 1最优化方法，解可新等，天津大学出版社，1997。 2最优化原理与方法（修订版），薛嘉庆，冶金工业出版社，2003.6。 3最优化方法，何坚勇，清华大学出版社，2007.1。 4最优化方法，孙文瑜，徐成贤，朱德通，高等教育出版社，2005.3。 5非线性规划，胡毓达，高等教育出版
2、社，1990。 6微粒群优化与调度算法，王凌，刘波，清华大学出版社，2008.5。 7蚁群优化算法，马良 等，科学出版社，2008.2。,最优化方法 第一章 最优化问题数学建模专题,1 引 言 最优化技术是一门较新的学科分支。它是在本世纪五十年代初在电子计算机广泛应用的推动下才得到迅速发展，并成为一门直到目前仍然十分活跃的新兴学科。最优化所研究的问题是在众多的可行方案中怎样选择最合理的一种以达到最优目标。,将达到最优目标的方案称为最优方案或最优决策，搜寻最优方案的方法称为最优化方法，关于最优化方法的数学理论称为最优化理论。 最优化问题至少有两要素：一是可能的方案；二是要追求的目标。后者是前者的
3、函数。如果第一要素与时间无关就称为静态最优化问题，否则称为动态最优化问题。 本课程专门讲授静态最优化问题。 最优化技术应用范围十分广泛，在我们日常生活中，在工农业生产、社会经济、国防、航空航天工业中处处可见其用途。 比如我们自己所接触过的课题有：结构最优设计、电子器件最优设计、光学仪器最优设计、化工工程最优设计、运输方案、机器最优配备、油田开发、水库调度、饲料最优配方、食品结构优化等等。,最优化技术工作被分成两个方面，一是由实际生产或科技问题形成最优化的数学模型，二是对所形成的数学问题进行数学加工和求解。 对于第二方面的工作，目前已有一些较系统成熟的资料，但对于第一方面工作即如何由实际问题抽象
4、出数学模型，目前很少有系统的资料，而这一工作在应用最优化技术解决实际问题时是十分关键的基础，没有这一工作，最优化技术将成为无水之源，难以健康发展。 因此，我们在学习本科程时要尽可能了解如何由实际问题形成最优化的数学模型。 为了便于大家今后在处理实际问题时建立最优化数学模型，下面我们先把有关数学模型的一些事项作一些说明。,所谓数学模型就是对现实事物或问题的数学抽象或描述。建立数学模型时要尽可能简单，而且要能完整地描述所研究的系统，但要注意到过于简单的数学模型所得到的结果可能不符合实际情况，而过于详细复杂的模型又给分析计算带来困难。因此，具体建立怎样的数学模型需要丰富的经验和熟练的技巧。 即使在建
5、立了问题的数学模型之后，通常也必须对模型进行必要的数学简化以便于分析、计算。 一般的模型简化工作包括以下几类： （1）将离散变量转化为连续变量。 （2）将非线性函数线性化。 （3）删除一些非主要约束条件。,建立最优化问题数学模型的三要素： （1）决策变量和参数。 决策变量是由数学模型的解确定的未知数。参数表示系统的控制变量，有确定性的也有随机性的。 （2）约束或限制条件。 由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。 （3）目标函数。 这是作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。,2 最
6、优化问题数学建模,最优化在物资运输、自动控制、机械设计、采矿冶金、经济管理等科学技术各领域中有广泛应用。下面举几个专业性不很强的实例。 例1. 把半径为1的实心金属球熔化后，铸成一个实心圆柱体，问圆柱体取什么尺寸才能使它的表面积最小？ 解：决定圆柱体表面积大小有两个决策变量：圆柱体底面半径r、高h。 问题的约束条件是所铸圆柱体重量与球重相等。即,min,即,问题追求的目标是圆柱体表面积最小。即,则得原问题的数学模型：,利用在高等数学中所学的Lagrange乘子法可求解本问题,分别对r、h、求偏导数，并令其等于零，有:,即,此时圆柱体的表面积为,例2. 多参数曲线拟合问题 已知两个物理量x和y之
7、间的依赖关系为: 其中 和 待定参数,为确定这些参数,对x、 y测,解:很显然对参数 和 任意给定的一组数值,就由上式确定了 y关于x的一个函数关系式,在几何上它对应一条曲线,这条曲线不一定通过那m个测量点,而要产生“偏差”. 将测量点沿垂线方向到曲线的距离的 平方和作为这种“偏差”的度量.即,得m个实验点:,试将确定参数的问题表示成最优化问题.,显然偏差S越小,曲线就拟合得越好,说明参数值就选择得越好，从而我们的问题就转化为5维无约束最优化问题。即：,例3：两杆桁架的最优设计问题。由两根空心圆杆组成的对称两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为，
8、弹性横量为E，屈吸强度为。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。,由此得稳定约束：,解：桁杆的截面积为 ：,桁杆的总重量为：,负载2p在每个杆上的分力为：,于是杆截面的应力为：,此应力要求小于材料的屈吸极限，即,圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为,例4.（混合饲料配合）以最低成本确定满足动物所需营养的最优混合饲料。下面举一个简化了的例子予以说明。设每天需要混合饲料的批量为100磅，这份饲料必须含：至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分
9、为：,另外还要考虑到设计变量d和h有界。 从而得到两杆桁架最优设计问题的数学模型：,解:根据前面介绍的建模要素得出此问题的数学模型如下: 设 是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量（磅）。,3.最优化问题的基本概念,其中 是向量变量实值函数 则有m个式约束的最优化问题为：,n维欧氏空间 向量,向量变量实值函数： 无约束最优问题：,向量变量向量值函数：,其中 均为向量Z的实值连续函数，有二阶连续偏导数，采用向量表示法即为：,其中 这就是最优化问题的一般形式，又称非线性规划。 注意集约束通常可用不等式约束表示出来，有时,在本课程我们讨论的是如下形式的静态最优化问题：,因此，一般不考虑
10、集约束。 称满足所有约束条件的向量Z为容许解或可行解，容许点的集合称为容许集或可行集。,在容许集中找一点 ，使目标函数 在该点取最小值，即满足： 的过程即为最优化的求解过程。,称为问题的最优点， 称为最优值， 称为最优解。,如果约束条件中有“小于等于“的，即 则转化为 ，另外，等式约束 可以由下面两个不等式来代替：,因而最优化问题的一般形式又可写成： 对于最优化问题一般可作如下分类：,其中求解一维无约束问题的方法称为一维搜索或直线搜索，这在最优化方法中起十分重要的作用。,4.二维问题的图解法,这是定义在 平面 上的无约束极小化问题，其目标函数 在 三维空间中代表一个曲面 。,二维最优化问题具有
11、鲜明的几何解释，并且可以象征性地把这种解释推广到n维空间中去。因此我们简要介绍一下图解法，这对于以后理解和掌握最优化的理论和方法是很有益处的。,例1. 求解,=4 =9 =1 0 s s L,在 平面上任给一点 ，就对应有一个目标函数值 =,这个值就是过 点作 平面的垂线与S曲面交点的纵坐标。,反之，任给一个值 ,使目标函数 取值为 的点Z 个数就不相同了。可能没有，可能只有一个，可能有多个。 这一事实的几何意义是：过 f 轴上坐标为 的点作 坐标平面的平行平面L，可能与曲面S无交点（ 0 时），可能与S有一个交点（ =0 时），可能与S交成一条曲线（ 0 ）。,我们感兴趣的是至少有一个交点（
12、 0）的情形。 此时用平面L截曲面S得到一个圆，将它投影到 平面上，仍为同样大小的圆。在这个圆上每一点的目标 函数值均为 , 若一条曲线上任何一点的目标函数值等于同一常数，则称此曲线为目标函数的等值线。 易见，变动 f 的值，得到不同等值线，这是一组同心圆 ，对应 f=0的等值线缩为一点G，对应 f 0 的等值线为空集。 易见，随着 f 值变小，等值线圆半径变小，最后缩为一点，即为问题的最小值点G， =,解：先画出目标函数等值线，再画出约束曲线，本处约束曲线是一条直线，这条直线就是容许集。而最优点就是容许集上使等值线具有最小值的点。 由图易见约束直线与等值线的切点是最优点，利用解析几何的方法得
13、该切点为 = ， 对应的最优值为 =2 (图一） 。,例2 用图解法求解,例3：用图解法求解,解：先画出等式约束曲线 的图形。 这是一条抛物线，如图 再画出不等式约束区域，如图（怎样选定哪侧区域） 最后画出目标函数等值线，特别注意可行集边界点，以及等值线与可行集的切点。,易见可行域为曲线段ABCD。当动点沿抛物曲线段ABCD由A点出发时，AB段目标函数值下降。过点B后，在BC段目标函数值上升。过C点后，在CD段目标函数值再次下降。D点是使目标函数值最小的可行点，其坐标可通过解方程组：,得出 = ， =4,由以上三个例子可见，对二维最优化问题。我们总可以用图解法求解，而对三维或高维问题，已不便在
14、平面上作图，此法失效。 在三维和三维以上的空间中，使目标函数取同一常数值的是 Z| f(Z)=r,r是常数称为目标函数的等值面。 等值面具有以下性质： （1）不同值的等值面之间不相交，因为目标函数是单值函数。 （2）除了极值点所在的等值面外，不会在区域内部中断，因为目标函数是连续的 （3）等值面稠的地方，目标函数值变化得较快，而稀疏的地方变化得比较慢。 （4）一般地，在极值点附近，等值面（线）近似地呈现为同心椭球面族（椭圆族）。,5 二次函数,定义：设Q为nn对称矩阵 若 ，Z 0 ，均有 0 ，则称矩阵Q是正定的。 若 ，均有 0 ，则称矩阵Q是半正定的。 若 ，且Z0，均有 0，则称Q是负定的。,在代数学中将特殊的二次函数 称为二次型。 对于二次函数，我们更关心的是Q为正定矩阵的情形。,其向量矩阵表示形式是：,其中 Q= 为对称矩阵，b=,若 ，均有 0，则称Q是半负定的。 判定一个对称矩阵Q是不是正定的，可以用Sylvester定理来判定。 Sylvester定理：一个nn对称矩阵Q是正定矩阵的充要条件是矩阵Q的各阶主子式都是正的。,例：判定矩阵Q= 是否正定 解：对称矩阵Q的三个主子式依次为：,A是正定矩阵 非奇异矩阵A= A的所有特征根大于零 有高矩阵G，使A= （矩阵秩等于 矩阵列：高矩阵） A的所有主子式0,=60，
