《最优化理论与方法1(2014-简版)解析》由会员分享，可在线阅读，更多相关《最优化理论与方法1(2014-简版)解析（69页珍藏版）》请在金锄头文库上搜索。
1、最优化理论与方法讲义(上)第一章 绪论1.1 学科简介最优化这一数学分支，为这些问题的解决提供了理论基础和求解方法。最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科。1.1.1 优化的含义优化是从处理各种事物的一切可能的方案中，寻求最优的方案。（1）来源：优化一语来自英文Optimization，其本意是寻优的过程；（2）优化过程：是寻找约束空间下给定函数取极大值（以max表示)或极小(以min表示)的过程。1.2 发展概况第一阶段人类智能优化第二阶段数学规划方法优化第三阶段工程优化第四阶段现代优化方法1.3研究意义研究意义：最优化在本质上是一门交叉学科，它对许多学科产生了重
2、大影响，并已成为不同领域中很多工作都不可或缺的工具。应用范围：信息工程及设计、经济规划、生产管理、交通运输、国防工业以及科学研究等诸多领域。总之，它是一门应用性相当广泛的学科，讨论决策的问题具有最佳选择之特性。它寻找最佳的计算方法，研究这些计算方法的理论性质及其实际计算表现。1.4 示例例1 资源分配问题 某工厂生产A和B两种产品，A产品单位价格为万元，B产品单位价格为万元。每生产一个单位A 产品需消耗煤吨，电度，人工个人日；每生产一个单位B 产品需消耗煤吨，电度，人工个人日。现有可利用生产资源煤C 吨，电E 度，劳动力L个人日，欲找出其最优分配方案，使产值最大。分析：(1)产值的表达式；(2
3、)优化变量确定：A 产品，B 产品；(3)优化约束条件：生产资源煤约束；生产资源电约束；生产资源劳动力约束。例2 指派问题设有四项任务、派四个人、去完成。每个人都可以承担四项任务中的任何一项，但所消耗的资金不同。设完成所需资金为。如何分配任务，使总支出最少?分析：设变量则总支出可表示为：数学模型：1.5 最优化的数学模型 最优化的数学模型是描述实际优化问题目标函数、变量关系、有关约束条件和意图的数学表达式，并能反映物理现象各主要因素的内在联系，是进行最优化的基础。1.5.1 基本概念1、决策变量(Decision variables)问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可
4、由决策者决定和控制，也称优化变量。决策变量或优化变量的全体实际上是一组变量，可用一个列向量表示。优化变量的数目称为优化问题的维数，如n个优化变量，则称为n维优化问题。优化问题的维数表征优化的自由度。优化变量愈多，则问题的自由度愈大、可供选择的方案愈多，但难度亦愈大、求解亦愈复杂。 通常，小型优化问题：一般含有210个优化变量； 中型优化问题：1050个优化变量； 大型优化问题：50个以上的优化变量。如何选定优化变量？确定优化变量时应注意以下几点：（1）抓主要，舍次要。 （2）根据要解决问题的特殊性来选择优化变量。2、约束条件(Constraint conditions)指决策变量取值时受到的各
5、种资源条件的限制。约束又可按其数学表达形式分成等式约束和不等式约束两种类型：(1)等式约束：(2)不等式约束：根据约束的性质可以把它们区分成：性能约束针对性能要求而提出的限制条件称作性能约束。边界约束只是对设计变量的取值范围加以限制的约束称作边界约束。图1-2 优化问题中的约束面(或约束线)(a)、二变量问题的约束线 (b)三变量问题的约束面可行域：在优化问题中，满足所有约束条件的点所构成的集合。 如约束条件和的二维设计问题的可行域D。图 约束条件规定的可行域D一般情况下，可行域可表示为：不可行域：可行点和不可行点：约束边界上的可行点为边界点，其余可行点为内点。起作用的约束与不起作用的约束：满
6、足的约束为起作用约束,否则为不起作用的约束。(等式约束一定是起作用约束)3、目标函数(Objective function)它是决策变量的函数。为了对优化进行定量评价，必须构造包含优化变量的评价函数，它是优化的目标，称为目标函数，以表示。 在优化过程中，通过优化变量的不断向值改善的方向自动调整，最后求得值最好或最满意的X值。在构造目标函数时，目标函数的最优值可能是最大值，也可能是最小值。在优化问题中，可以只有一个目标函数，称为单目标函数。当在同一设计中要提出多个目标函数时，这种问题称为多目标函数的最优化问题。3.1 目标函数等值(线)面n 定义：在高维空间中，使目标函数值取同一常数的点集，称为
7、的等值线（或等值面）。 （或定义：对于具有相等目标函数值的自变量构成的平面曲线或曲面称为等值线或等值面。）n 数学表达式为一系列常数，代表一族维超曲面。对于具有相等目标函数值的自变量构成的平面曲线或曲面称为等值线或等值面。n 性质在通常情况下，若目标函数是连续的单值函数，则其等值线具有以下性质：(1) 不同值的等值线不相交；(2) 除极值点所在的等值线外，等值线不会中断；(3) 等值线稠密的地方，目标函数值变化较快，而稀疏的地方，目标函数值变化较慢；(4) 在极值点附近，等值线近似地呈现为同心椭球面族(椭圆族)。4、可行域(Feasible region)满足约束条件的决策变量的取值范围。5、
8、最优解(Optimal solution)可行域中使目标函数达到最优的决策变量的值。1.5.4 优化问题一般数学形式设优化变量向量 求目标函数 满足约束条件 ： 即 s.t. 1.5.5 建模实例建立优化问题的数学模型一般步骤：(1)根据问题要求，应用专业范围内的现行理论和经验等，对优化对象进行分析。(2)对诸参数进行分析，以确定问题的原始参数、优化常数和优化变量。(3)根据问题要求，确定并构造目标函数和相应的约束条件，有时要构造多目标函数。(4)必要时对数学模型进行规范化，以消除诸组成项间由于量纲不同等原因导致的数量悬殊的影响。例 混合饲料配合以最低成本确定满足动物所需营养的最优混合饲料。设
9、每天需要混合饲料的批量为100磅，这份饲料必须含：至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分为：解：设是生产100磅混合饲料所须的石灰石、谷物、大豆粉的量(磅)。1.5.6 优化设计的分类1.6 优化问题的几何解释和基本解法1.6.1 几何解释无约束优化问题就是在没有限制的条件下，对优化变量求目标函数的极小点。在优化空间内，目标函数是以等值面的形式反映出来的，则无约束优化问题的极小点即为等值面的中心。约束优化问题是在可行域内对设计变量求目标函数的极小点，此极小点在可行域内或在可行域边界上。求目标函数在可行
10、域D上的极小点，是在与可行域D有交集的等值线中找出具有最小值的等值线。例1：二维非线性规划问题目标函数等值线是以点(2，0)为圆心的一组同心圆。如不考虑约束，其无约束最优解是： 约束方程所围成的可行域是D，此时例2：非线性规划问题：由图易见约束直线与等值线的切点就是最优点，利用解析几何的方法得到该切点和最优值为：例3：非线性规划问题：解：画出等式约束曲线的图形。这是一条抛物线；画出不等式约束区域：和；画出目标函数等值线，以及等值线与可行集的切点。可见可行域为曲线段ABCD。点是使目标函数值最小的可行点，其坐标可通过解方程组：得出： 1.6.2 优化问题的基本解法求解优化问题的基本解法有：解析法
11、和数值解法。1.6.2.1 解析法利用数学分析(微分、变分等）的方法，根据函数（泛函）极值的必要条件和充分条件求出其最优解析解的求解方法。局限性：工程优化问题的目标函数和约束条件往往比较复杂，有时甚至还无法用数学方程描述，在这种情况下应用数学分析方法就会带来麻烦。1.6.2.2 数值解法这是一种数值近似计算方法，又称为数值迭代方法。它是根据目标函数的变化规律，以适当的步长沿着能使目标函数值下降的方向，逐步向目标函数值的最优点进行探索，逐步逼近到目标函数的最优点或直至达到最优点。数值解法（迭代法）是优化设计问题的基本解法。其中也可能用到解析法，如最速下降方向的选取、最优步长的确定等。数值计算的迭
12、代方法具有以下特点：(1)是数值计算而不是数学分析方法；(2)具有简单的逻辑结构并能反复进行同样的数值计算；(3)最后得出的是逼近精确解的近似解。这些特点正与计算机的工作特点相一致。在数学规划中，采用进行迭代运算时，求n维函数的极值点的具体算法如下图所示。一、求解步骤：数值迭代法的基本思路：是进行反复的数值计算，寻求目标函数值不断下降的可行计算点，直到最后获得足够精度的最优点。这种方法的求优过程大致可归纳为以下步骤：(1)首先初选一个尽可能靠近最小点的初始点，从出发按照一定的原则寻找可行方向和初始步长，向前跨出一步达到点；(2)得到新点后再选择一个新的使函数值迅速下降的方向及适当的步长，从点出
13、发再跨出一步，达到点，并依此类推，一步一步地向前探索并重复数值计算，最终达到目标函数的最优点。在中间过程中每一步的迭代形式为：上式中：第k步迭代计算所得到的点，称第k步迭代点，亦为第k步设计方案；第k步迭代计算的步长； 图 迭代计算机逐步逼近最优点过程示意图第k步迭代计算的探索方向。 用迭代法逐步逼近最优点的探索过程如右图所示。 u 运用迭代法，每次迭代所得新的点的目标函数都应满足函数值下降的要求：u 迭代法要解决的问题：即(1)选择搜索方向；(2)确定步长因子；(3)给定收敛准则。(一) 柯西收敛准则点列收敛的充要条件是：对于任意指定的实数，都存在一个只与有关而与无关的自然数N，使得当两自然
14、数m，p N时，满足或 或 (二) 迭代终止准则（1）点距准则 或 其中是事先给定的要求精度。（2）函数值下降量准则 或 （3）目标函数梯度准则至于采用哪种收敛准则，可视具体问题而定。可以取：第二章 线性规划2.1 线性规划问题及其数学模型2.1.1 问题的提出例1：（下料问题）某车间有长度为180cm的钢管（数量足够多），今要将其截为三种不同长度的管料，长度分别为70cm、52cm和35cm。生产任务规定，70cm的管料只需100根，而52cm、35cm的管料分别不少于150根、120根，问应采取怎样的截法才能完成任务，同时使剩下的余料最少？解：所用可能的截法共有8种，见下表：截法一二三四五六七八需要量/根长度(cm)705235211100001000210321
