最优化方法归纳总结

1 / 48 最优化方法归纳总结 最优化方法综述 1.引论 应用介绍 最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多的方案中什么样 的方案最优以及怎样找出最优方案。这类问题普遍存在。例如，工程设计中怎样选择设计参数，使得设计方案满足设计要求，又能降低成本；资源分配中，怎样分配有限资源，使得分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产评价安排中，选择怎样的计划方案才能提高产值和利润；原料配比问题中，怎样确定各种成分的比例，才能提高质量，降低成本；城建规划中，怎样安排工厂、机关、学校、商店、医院、住户和其他单位的合理布局，才能方便群众，有利于城市各行各业的发展；农田规划中，怎样安排各种农作物的合理布局，才能保持高产稳产，发挥 地区优势；军事指挥中，怎样确定最佳作战方案，才能有效地消灭敌人，保存自己，有利于战争2 / 48 的全局；在人类活动的各个领域中，诸如此类，不胜枚举。最优化这一数学分支，正是为这些问题的解决，提供理论基础和求解方法，它是一门应用广泛、实用性强的学科。 优化的问题的基本概念 工程设计问题一般都可以用 数学模型来描述，即转化为数学模型。优化设计的数学模型通常包括设计变量、目标函数和约束条件。三个基本要素。设计变量的个数决定了设计空间的维数。确定设计变量的原则是：在满足设计基本要求的前提下，将那些对设计目标影响 交大的而参数选为设计变量，而将那些对设计目标影响不大的参数作为设计变量，并根据 具体情况，赋以定值，以减少设计变量的个数。用来评价和追求最优化设计方案的函数就称 为 目 标 函 数 ， 目 标 函 数 的 一 般 表 达 式 为f?x?f?x1,x2,?xn?。 优化设计的目的，就是要求所选择的设计变量使目标函数达到最佳值。所谓最佳值就是极大值或极小值。在设计空间中，虽然有无数个设计点，即可能的设计方案，但是一般工程实际问题对设计变量的取值总是有一些限制的，这些限制条件3 / 48 显然是设计变量的函数，一般称之为优化 设计问题的约束条件或约束函数。在优化设计问题中，约束条件有两种表现形式 ， 一 种 是 不 等 式 约 束 ， 其 一 般 表 达 式 为 ： gu?x?0,?u?1,2,?m? ， 另 一 种 是 等 式 约 束 ， 即hv(x)?0,(v?1,2,?p?n)。 由设计变量、目标函数和约束条件三个基本要素所组成的工程优化设计数学模型所表达的意思是：在满足一定的约束以偶案件下，寻求一组设计变量，使得目标函数取得极小值或极大值。 在设计空间中，每一个不等式约束条件都把设计空间划分成两部分，一部分是满足不等式约束条件的，另一部分是不满足约束条件的，两部分的分界面就是 g(x)?0 所形成的曲面，称为约束面。在二维设计空间中约束面是一条曲线或直线，在三维设计空间中则是一个曲面或超曲面。一个优化设计问题的所有不等式约束的边界将组成一个复合约束边界。满足约束条件的区域称为可行域，而不满足约束条件的区域称为非可行域。可行域内的点称为可行点。 分类： 4 / 48 ( 转 载 于 : 海 达范 文网 :最 优化 方法归纳 总结 ) 若工程优化设计问题的数学模型中只有目标函数而没有约束条件，则称之为无约束优化问题。无约束优化问题的目标函数如果是一元函数，则称之为一 维优化问题，他的求解方法称之为一维搜索方法。对于约束优化问题，课按其目标函数和约束函数的特性，分为线性规划问题和非线性规划问题。如果目标函数和所有的约束函数都是线性函数，则称之为线性规划问题；否则称之为非线性规划问题。对于目标函数是二次函数而约束函数都是线性函数这一类问题，一般称之为二次规划问题。另外，还有整数规划、几何规划和多目标规划等。线性规划和非线性规划是数学规划中欧偶那个的两个重要的分支，在工程实际问题中均得到了广泛的应用。 凸函数、凸规划： 工程优化设计问题大多是非线性规划问题，其数学本质是多元非线性函数求极值问题，如果函数在整个区域有两个或两个以上的极值点，则称每一个极值点为局部极值点。在整个可行域中，比较所有的局部极值点，可得到一个最小或最大的局部极值点，称为全局极值点。但基于数学规划的工程优化设计方法一般只能求得为题的局部极值点，只有当函数具有凸性的情况下，局部极值点才 是全域极值点。对于一元函5 / 48 数来说，在某区间内，如果函数的曲线是下凸的，即在刺区间内，一元函数曲线上任意两点间相连的弦线，总不会位于这两点间函数曲线的下面，则称此一元函数具有凸性，或称此函数为凸函数；反之，若函数曲线上任意两点间相连的弦线，总不会位于这两点间的函数曲线的上面，则称此函数具有下凸性，或称此函数为凹函数。 如果约束优化问题 minf(x)x?R,?0(u?1,2,?,m)n中的目标函 数 f(x)是凸函数，所有的不等式约束也都是凸函数，则称此约束优化问题为凸规划。凸规划具有一个重要特性，这就是：凸规划的局部极小值一定是全域极小值。对于凸规划问题，只要求出一个局部极小值，它就是全域极小值。所以，优化理论与方法常限于讨论凸规划问题，故称为凸规划理论。应强调指出的是。实际工程优化问 题往往不是凸规划问题。所以，采用常用的优化方法，求得的最优解往往是局部最优解。凸规划的可行域是凸集。 2.线性规划问题： 线性规划的标准形式 6 / 48 线性规划即目标函数和约束函数 都是线性的约束最优化问题。线性规划在理论和计算方法上都很成熟。他在工程管理和经济管理中，应用都和广泛。它的解法在理论上和方法上都很成熟。虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解非线性问题的。此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优化问题，线性规划方法就更有用了。 线性规划的标准形式： 课程论文 (设计 ) 题 目 最优化理论与方法小结 学生姓名 学 号 院 系 专 业 系统科学 指导教师 二一二年 十一 月 十 日 7 / 48 最优化课程小结 由于我本科是学电气的 ,没有接触过运筹学和最优化的知识 ,刚开始学习的两周很迷惑 ,后来在图书馆借了书看 ,也问了其他同学 ,才能跟得上老师的步子 .那我就总结一下这两个月的学习 ,以及我对的认识 . 1.运筹学的起源与方法 首先学习的是运筹学 ,这也是我第一次听说这个名词 ,刚开始以为是运输之类的问题 .通过学习 ,我了解到运筹学的广泛应用 .在这里我简述一下 .运筹学在商业活动与行政事务中的早期应用可追溯到几个世纪以前 ,但是系统的运筹学理论源于第二次世界大战期间 .最初是英国军方为了最大限度的利用已经十分短缺的战争资源 ,召集了一批科学家与工程人员共同筹划作物资的分配问题 .英国军方的这一举动很快引起了美国军方的重视 ,类似的研究小组在美国三军机构中相继成立 ,并开 发出一套相对完整的新技术 ,用以指导协约方面在战略上和战术上的各种军事行动 .许多诺贝尔奖金获得者都为运筹学的建立与发展做出过重要的贡献 .运筹学理论和方法建立在人类认识和人类活动的基础之上 ,反映了人类分析和处理事务的思辨过程 .因此运筹学既是一门科学 ,8 / 48 又是一门艺术 . 作为科学 ,运筹学必须在科学方法论的指导下进行科学探索 .其工作步骤包括 : (1)确定问题 :目标 ,约束 ,变量和参数 . (2)建立模型 :目标 ,约束 ,变量和参数之间的关系 . (3)求解模型 :最优解 ,有效解和满意解 . (4)解的检验 :正确性 ,有效性和稳定性 . (5)解的控制 :灵敏度分析 . (6)解的实施 :解释 ,培训和监测 . 作为艺术 ,运筹学设计军侧着的社会环境 ,心理作用 ,主观意愿和工作经验等多方面因素 ,而这些因素又大都具有模糊特征与动态性质 .为了有效的应用运筹学 ,前英国运筹学学会会长托姆林森提出以下原则 : 9 / 48 (1)合伙原则 :运筹学工作者与管理工作者相结合 . (2)催化原则 :多学科协作 ,打破常规 . (3)渗透原则 :跨部门 ,跨行业联合 . (4)独立原则 :不受某人或者某部门的特殊政策所左右 . (5)宽容原则 :广开思路 ,兼容并需 . (6)平衡原则 :平衡矛盾 ,平衡关系 . 模型是运筹学研究客观现实的工具和手段 .常见的模型有以下 3 种基本形式 (1)思维模型 :研究者对于某种事物的想想或者概念性 的描述 ,如公司主管头脑中对公司未来市场的规划 .这虽然不是一种精确 ,具体 ,可见的形式 ,但通常是其他模型的渊源 . (2)物理模型 :可以是一个与事物同等尺寸 ,或者被放大 ,或者被缩小 ,或者被简化的几何模型 ,用以形象的表现和演示被研究的对象 ;也可以是一些图标 ,用以说明事物的流程 . 10 / 48 (3)数学模 型 :采用数学符号精确描述实际事物中的变动因素和因素见的相互关系 . 构造模型是一种创造性劳动 ,成功的模型往往是科学和艺术的结晶 .建模的方法和思路有以下四种 . (1)直接分析法 :根据研究者对问题内在的机理的认识直接构造模型 ,并利用已知的算法对问题求解与分析 ,如线性规划模型 ,动态规划模型 ,排队模型 ,存储模型 ,决策与对策模型等 . (2)类比法 :模仿类似问题的结构性质建立模型并进行类比分析 .例如 ,物理系统 ,化学系统 ,信息系统以及经济系统之间都有某些相同的地方 ,因而可互相借鉴 . (3)统计分析法 :尽管机理为名 ,但可根据历史资料或实验结果运用统计分析方法建模 . (4)逻辑推理法 :利用知识和经验对事物的变化过程进行逻辑推理来构造模型 . 11 / 48 数学模型是 3中常见模型中最抽象 ,最复杂的模型 ,它反映的是事物的本质 .数学模型的一般形式可以写为 目标的评价准则 U=f(x,y,z) 约束条件 g(x,y,z)=0 式中 :x为可控变量 ,y为已知参数 ,z为不确定性因素 . 目标的评价准则一般要求达到最佳 ,适中 ,满 意等 .准则可以使一个 ,也可以是多个 .约束条件可以由多个 ,也可以一个没有 .如果 g 为等式 ,即为平衡条件 .当模型中没有不确定因素是 ,改模型称之为确定性模型 .如果不确定性因素是随机因素 ,则气味随机模型 ;如果是模糊因素 ,则为模糊模型 ;如果机油随机因素又有模糊因素 ,则为模糊随机模型 . 在建立了问题的数学模型之后 ,如何求解模型是运筹学的另一个关键所在 .运筹学的进步有来与定量分析技术的应用于发展 ,尤其是近年来计 算机技术的迅速提高 ,各种管理决策方面的应用性软件相继推出 .这是决策者得以借助计算机对复杂的实际问题进行定量分析 ,大大该井了定量技术的有效性 . 12 / 48 2.无约束最有化方法 最优化问题无处不在。只要存在选择，并涉及稀缺资源，就一定存在优化问题。可以很 “ 高深 ” ，比如前面提到的电力系统无功优化问题 ，比如导弹的轨迹优化问题；也可以很“ 生活 ” ，比如有同学研究了在交大教室、图书馆、实验室和几个食堂之间的最优路径问题，比如我曾经写过一篇恋爱中的博弈问题，又比如有同学问周老师： “ 如何花费最少的时间获得相对较好的最优化课程分数？ ” 但它们有着共同的特点，就是很实际，并且很有趣。可以说，作为一个普通的工学研究生，以往从没有接触过一门数学课程，如此地贴近现实问题，立足现实问题，而最终亦指向现实问题。在最优化理论系统 中，除了可以感受到一般数学理论的那种纯粹、抽象、透彻、简洁，也能感受一种无处不在的实用主义价值观， “ 实用 ” 、“ 好用 ” 、 “ 凑效 ” 这些看起来不那么 “ 数学 ” 的评价标准在这个领域中也有着相当的地位。而在各种 “ 数学 ” 、 “ 非数学 ” 的标准之间的权衡取舍，本身就是一个多目标优化问题而体现出某种对系统性思维的诉求。思考、研究这样的问题，即有用，又有趣，令人快乐无穷。下面依次介绍我们所13 / 48 学的几种方法 . 最速下降法基本原理 (一 )无约束问题的最优性条件 无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此我们有以下几个定理。 定理 1 设 f : Rn ?R1 在点 x ?Rn 处可微。若存在 p?Rn，使 ?f (x)T p ?0 则向量 p 是 f 在点 x 处的下降 方向。 定理 2 设 f : Rn ?R1 在点 x?Rn 处可微。若 x?是无约束问题的局部最优解，则 ?f (x?) ?0 由数学分析中我们已经知道，使 ?f (x) ?0的点 x 为函数 f 14 / 48 的驻点或平稳点。函数 f 的一个驻点可以是极小点；也可以是极大点；甚至也可能既不是极小点也不是极大点，此时称它为函数 f 的鞍点。以上定理告诉我们， x?是无约束问题的的局部最优解的必要条件是： x?是其目标函数 f 的驻点。 现给出无约束问题局部最优解的充分条件。 定理 3 设 f : Rn ?R1 在点 x?Rn 处的 Hesse 矩阵 ?2 f (x?)存在。若 ?f (x?) ?0，并且 ?2 f (x?)正定 则 x?是无约束问题的严格局部最优解。 一般而言，无约束问题的目标函数的驻点不一定是无约束问题的最优解。但对于其目标函数是凸函数的无约束凸规划，下面定理证明了，它的目标函数的驻点就是它的整体最优解。 定理 4 设 f : Rn ?R1， x?Rn， f 是 Rn 上的可微凸函数。若有 ?f 15 / 48 (x?) ?0 则 x?是无约束问题的整体最优解。 Newton 法的基本原理 如前面所提 到的，最速下降法在最初几步迭代中函数值下降很快外，总的说来下降的并不快，且愈接近极值点下降的愈慢。因此，应寻找使目标函数下降更快的方法。牛顿法就是一种收敛很快的方法，其基本思路是利用二次曲线来逐点近似原目标函数，以二次曲线的极小值点来近似原目标函数的极小值点并逐渐逼近改点。 一维目标函数 f(x) 在 x ?(x(k)(k) 点 逼 近 用 的 二 次 曲 线 为 (k)(k)?f?(x)(x?x)?)?f(x(k)1 2(k)(k)2f?(x)(x?x) 此二次函数的极小点 可由 ?(x(k)?0 求得。 16 / 48 对于 n维问题， n为目标函数 f(X)在 X(k)点逼近用的二次曲线为： ?(X(k)?f(x(k)?f(X (k)(k)?.X?X(k)(k)?12X?X(k)T.?f(X2(k).X?X(k) 令式中的 Hessian?2f(X)?H(X (k)，则上式可改写为： (k)?(X(k)?f(x ?f(X)(k)?f(X)?.X?X?12X?X(k)T.H(X(k).X?X(k) 当 ?(X)?0 时可求得二次曲线 ?(X)的极值点，且当且仅当改点处的 Hessian矩阵为正定时有极小值点。 由上式得： ?(X)?f(X(k)?H(X (k)(k)X?X(k) 令 ?(X)?0，则 ?f(X 若 H(X(k)(k)?H(X(k)X?X?0 (k)为可逆矩阵，将上式等号两边左乘 ?H(X)?1，则得 17 / 48 ?0 ?H(X?(k)?1?f(X(k)?InX?X(k) 整理后得 X?X(k)?H(X(k)?1?f(X(k) (k)当目标函数 f(X)是二次函数时，牛顿法变得极为简单、有效，这时 H(X 常数矩阵，式 )是一个 ?(X(k)?f(x ?f(X)(k)?f(X(k)?.X?X(k)?12X?X(k)T.H(X(k).X?X(k)变成精 确表达式，而利用式 X?X(k)?H(X(k)?1?f(X(k)作一次迭代计算所得的 X 就是最优点 X*。在一般情况下 f(X)不一定是二次函数，则不能一步就能求出极小值，即极小值点不在 ?H(X(k)?1?f(X(k)方向上，但由于在 X(k)点附近函数 ?(X)与 f(X)是近似的， 18 / 48 ?H(X ?1(k)所以这个方向可以作为近似方向，可以用式X?X为一个逼近点 X(k?1)(k)?1?f(X(k)求出点 X 作。这时式 X?X(k)?H(X(k)?f(X(k)可改成牛顿法的一般迭代 最优化理论学习心得 本拟撰写以考虑电力系统静态电压稳定的无功优化问题的建模与求解实验为题的课程小论文，无奈问题复杂，数据有限，再加上撰写三个数值报告消耗了大量时间精力，实在无力在考试之前完成这篇论文，只能退而草草炮制这篇学习心得，论文留待假期或以后，涉及到专业研究方向，总是要写的。 下面谈七点心得体会：最优化问题的普遍性、实用性和趣味性，最优化问题的困难，数学的简单与复杂的辩证关系及其引发的对生活态度的思考，理论问题与数值问题的差异，最优化问题的信息论视角，最优化问题和解方程问题的关系，周老师的可贵精神。 19 / 48 最优化问题无处不在。只要存在选择，并涉及稀缺资源，就一定存在优化问题。可以很 “ 高深 ” ，比如前面提到的电力系统无功优化问题，比如导弹的轨迹优化问题；也可 以很“ 生活 ” ，比如有同学研究了在交大教室、图书馆、实验室和几个食堂之间的最优路径问题，比如我曾经写过一篇恋爱中的博弈问题，又比如有同学问周老师： “ 如何花费最少的时间获得相对较好的最优化课程分数？ ” 但它们有着共同的特点，就是很实际，并且很有趣。可以说，作为一个普通的工学研究生，以往从没有接触过一门数学课程，如此地贴近现实问题，立足现实问题，而最终亦指向现实问题。在最优化理论系统中，除了可以感受到一般数学理论的那种纯粹、抽象、透彻、简洁，也能感受一种无处不在的实用主义价值观， “ 实用 ” 、 “ 好用 ” 、 “ 凑效 ” 这些 看起来不那么 “ 数学 ” 的评价标准在这个领域中也有着相当的地位。而在各种 “ 数学 ” 、 “ 非数学 ” 的标准之间的权衡取舍，本身就是一个多目标优化问题而体现出某种对系统性思维的诉求。思考、研究这样的问题，即有用，又有趣，令人快乐无穷。 这些可能与生活琐事紧紧相连的问题可能引发数学上极大的麻烦。比如现在大家都知 道的背包问题，我看到这个问题20 / 48 的第一反应是：这应该是个很简单的问题！不错，模型是简单的，求解确实极富挑战的。又比如最速下降法的收敛性，从直觉上讲实在是让人感到不证自明的东西。然而，放到数学领域严谨考察，问题就不那么简单了，仅仅对一个正定二次函数就花费了近半节课的时间去证明。再比如对于 “ 皮球下山法 ” 的局部收敛问题。将一个皮球掷向一个可微的谷域曲面，最终能停止到极小值点周围，这是直觉必然，也是物理事实。为了让它能在理论上最终精确停在极小值点，需要取消摩擦力作用；为了让球的能量最终全部耗散，同时为了让连续运动问题变 为离散的跳跃问题，必须让球在任何情况下都保持跳跃而不能滚动，且每次跳跃按一定规则衰减动能。然而，就是这一点点和实际物理过程的看起来不影响结果的改动，放到数学领域严格考察，就会发现收敛性恐怕是有条件的，因为速度的衰减太快，在某种具体的目标函数形态下，完全有可能使算法收敛到不是极小值点的地方。进而，要证明或给出收敛条件，就是很困难的工作了。由于最优化问题本身的多样性与复杂性，虽然在最优化理论课程上，我们学习了众多的算法，可是放到现实科学工程领域，真正全面有效的算法其实却不多，甚至限于我的认识，还没有任何一种对于 高维的、有复杂约束的全局优化问题凑效的算法，而现实科学工程领域中，这样的问题并非少见，在我个人的领域中，更是随处都是。然而，正因为有困难，这个领域也21 / 48 才拥有无限的发展空间和蓬勃生机，从而散发出醉人的魅力。 数学近乎天下之至简，好比全局优化算法 “ 穷其一生 ” 也无法完全掌握的目标函数的全局信息，通过目标 函数一个短短的解析式就能完整包括；一个二维的优化问题也许我们可以 凭直观观察迅速获得全局最小值点，但对于大于更高维，多约束的问题，直观就无能为力，经过严格证明可行的数学方法确定解决这些问题；千差万别的现实世界信息似乎无穷无尽，然而全部的重要的核心数学理论 集中起来或许一张CD都装不满 就能描述其中大部分的运动变化规律，难怪有毕达哥拉斯者认为世界就是数学的实例。然而数学也近乎天下之至繁，一方面，数学是对现实某一方面的抽象，另一方面数学要求严格的逻辑必然性，掺不得半点沙子。而现实对象往往是具体的复杂的，要用数学准确描述一个具体对象的全部是不可能的。回到最优化问题上来，这就引发了一种对生活态度的思考：现实生活中，我们是否需要最优化结果和最优化方法？我想现实的考虑是，需奉中庸之道。如果我们面对生活中的任何问题，都追求用绝对严格的优化方法，追求获得绝对的最优解，那么，很可能什么事都做不了了。很多时 候，在现有已掌握的方法和结果中选择最不差，比在22 / 48 一切可能的方法和结果中选择最好，要实际有效得多。比如对于社会改良问题，政策设计问题。而对于另一些问题，如果我们把注意压力集中在最优性的功利思维上，就有可能最终反而破坏结果的最优性，比如对于那个学习最优化课程的最优时间花费问题，周老师认为读书做学问不能采取这样的态度。 理论问题和数值问题的差异是在本学期两门相关数学课上才被真正当作一个问题摆在我们面前的。我想这本身就是我国数学基础教育的一个弊病：由于在研究生教育以前，很少接触数值计算及相关问题，学生无法对这个问题有充足的感知和眼界，而现实当中需要数学的时候，恰恰又都无法避免数值计算问题，于是，所学和所用之间多了一条裂痕。这是应当引起思考和重视的。在最优化理论课程的三次数值实验中，无处不是数值计算相对理论计算的差异。最典型的问题是局部优化算法的可靠性。对于一切基于一维搜索的方法，当一维搜索在理论上绝对可行的 时候，在现实计算中出现理论外结果的情况几乎可说是大量存在的，特别对于某些专门的测试函数。目标函数的数量级太大，梯度函数的数量级太小，舍入误差等等，都可能使一维搜索失败、结果不可靠甚至异常退出，为防止这些不符合理论要求的情况出现，又需增加运算负责检查矫正，最终也很难完全避免。信赖域的方23 / 48 法同样存在着数值计算中的不可靠，甚至在小尺度时，实验中比基于一维搜索的方法有时更加不可靠。又比如特征值计算问题，当使用 eigs()函数而 Hessian阵数值的数量级太大时，就会发生异常返回。再比如，在各种出现数值大小比较的地方， 都存在着数值计算带来的问题和隐患，比如判定Hessian 阵正定，理论上只需最小特征值大于 0，可是，万一由于数值的原因这个最小特征值在计算机中是负的，就会得出错误的结果。相等判断更是 如此，一切 “x=A” 对double 变量都因舍入误差的存在是不可靠的，只能是|x-A| 最优化问题到底是个什么问题？我认为，抽象地讲，解最优化问题的过程，就是获取目标函数一条全局信息的过程，这个需要获取的全局信息，就是某点的函数值最小。为什么说这是个全局信息？因为说某点函数值 “ 最小 ” ，其实是说某点函数值 “ 比其它所有点 的函数值都小 ” ，包含了该点函数值对所有点函数值的大小比较关系，这当然是全局性的。而最优化问题的主要矛盾就是，问题的解所包含的信息是全局性的，但为求取这个解所能采集到的可利用信息 (如函数值大小或大小关系 )是局部的甚至单点的， 且采集次数是有限的。比如求一点函数值，只能得单点信息。又比如水平集 方法之所以不好用，就是因为它每一步都要求24 / 48 算法获得水平集测度这种全局信息。正是这个根本矛盾，导致了最优点搜索、确认上的困难。局部优化问什么可获得必然的解决？因为对于可微函数，从解析式中的有限次信息采集 如求单点梯度 就可获得一个有限领域内可利用的局部信息。比如，如果知道一点梯度为零并且知道函数正定，我就知道在某个领域中该点函数值一定最小，而不用通过无限次求取领域内各点函数值与该点函数值比大小来获取这个局部信息。然而，对于全局优化问题，我们却没有这样的手段。我在第三次报告中总结了一类算法的思路，是对极小值点 有限的目标函数，设计有效的办法在极小值点间转移或遴选，从而最终得到全局最小值点。放到这里来讲，就是对于极小值点有限的函数，全局可以划分为有限个局部，而局部有效信息，可以通过有限的信息采集获得，最后把所有局部有效信息拼接起来就得到需要的全局信息。也就是说，通过局部信息的有限次累计，得到全局信息。其实比较各种局部优化算法就可有这样的体会，理论上好的算法，往往就是能在各次获取单点信息的过程中实现一种信息累积，使得算法掌握的信息越来越能钩织出局部信息。出于这样的认识，我认为，要发明一种好的全局优化算法，可以在两个地 方下功夫：一是如何从解析式与约束中通过少的信息采样挖掘出更大范围、更大信息量的信息；二是，如何逐步有效累积信息把前面挖掘的信息汇成全局信息。另外是否可以把25 / 48 信息、通信领域的理论方法结合到最优化理论中，也是值得思考的问题。 最优化问题和解方程问题在很多时候是等效的。比如一阶最性条件就是个方程，而一些解方程的方法，就是将方程反构成最优化问题来解。 Matlab 的非线性方程求解函数fsolve()，其实就 是把求函数值零点转化为求函数值范数的最小值，用最优化问题来求解。这样的例子数不胜数，体现了数学中问题转化的基本思想。 最后要说的是，周国标老师的那种 “ 热血 ” 背后的激情、自信、率真、坦荡、良知和责任感，让我在连呼幸甚至哉的同时，也在某种角度看到了中国高等教育的希望。周老师不是完美的，然而，今天的中 国，这样的老师不是太多，而是太少。 第一次课后作业： 老三论：控制论、信息论和系统论 ,新三论：突变理论、耗散结构理论和协同论 美国数学家维纳的 “ 控制论 ” ，美国数学家申农的 “ 信息论 ” ，美籍奥地利理论生物学家和哲学家贝塔朗菲的 “ 系统论 ” ； 比利时化学家普里高津的 “ 耗26 / 48 散 结构理论 ” ，德国物理学家哈肯的 “ 协同论 ” ， 法国数学家托姆的 “ 突变理论 ” 。 第二次课后作业： 首先标准化： Max z=-3x1-2x2-x3+x4 x1-2x2+3x3-x415 2x1+x2-x3+2x410 x1 ,x2 ,x2”,x3 ,x40 添加 2 个 松 弛 变 量 x5 x6 x1-2x2+3x2-x4+x5=15 2x1+x2-x3+2x4+x6=10 0 X5 20 2 - 0 1 5 1 X4 5 1 - 1 0 - -z -5 -4 - - 0 0 - 在最优单纯性表中， x5,x6 的检验数均为负数，于是得到最优解 X*=(0,0,0,5,20)T，所以可以 最小值为： -5 27 / 48 1 此题和上题类似： 变成标准化 Max -x1-x2-x3 x1 -x4 -2x6=5 x2+2x4-3x5+x6=3 x3+2x4-5x5+6x6=5 xj0,j=1.6; Cb Xb b -1 -1 -1 0 X1 X2 X3 X4 0 X4 5 1 0 0 -1 0 X5 3 0 1 0 2 0 X6 5 0 0 1 2 -z 0 1 1 1 0 0 X4 5 1 0 0 -1 0 X5 3 0 1 0 2 0 X6 5 0 0 (1) 2 -z 0 -1 -1 -1* 28 / 48 于是得到最优解 X*=(0,0,0,5,3,3)T 由此得出 min的值为 0,。 添加松弛变量 x5， x6， x7 化 为 标 准 化 为 ： max 10x1+5x2+2x3-6x4 5x1+3x2+x39 -5x1+6x2+15x215 2x1+x2+x3-x4=13 0 0 X5 X6 0 -2 -3 1 -5 6 0 0 0 -2 -3 1 -5 6 0 ?i - - 5 2 29 / 48 X1 x40 5x1+3x2+x1+x5=9 -5x1+6x2+15x3+x6=15 2x1+x2+x3-x4+x7=13 Cb 0 0 0 -z 0 0 0 -z Xb X5 X6 X7 b 9 15 13 0 10 X1 5 -5 2 -10 1 0 0 0 5 X2 3 6 1 -5 9 - -1 2 X3 1 15 1 -2 16 0 -6 X4 0 0 -1 6 0 0 -1 -6 0 X5 1 0 0 0 1 - -2 0 X6 0 1 0 0 0 1 0 0 0 X7 0 0 1 0 0 0 1 0 ?i 30 / 48 X1 X6 X7 24 -18 于是得到最优解 X*=(,0,0,0,0,24,)T 于 是最小值为： -18 对第二个约束条件左右同时乘上 -1，再添加松弛变量 x5，x6， x7。令 X4=x41-2，其中 x41?0 X1-2x2+x3-x41-2+x5=15 即 X1-2x2+x3-x41+x5=17 2x1+x2-x3+2(x41-2)+x6+x7= 10 即2x1+x2-x3+2x41+x6+x7= 14 于 是 变 为 标 准 形 为 ： max -3x1-2x2-x2+x41 X1-2x2+x3-x41+x5=17 2x1+x2-x3+2x41+x6+x7= 14 x41?0 X1 x30 令 Z1=3x1+2x2+x3-x41 31 / 48 3 则 Z=3x1+2x2+x3-x41+2=Z1+2 Cb Xb b -3 -2 -1 X1 X2 X3 0 X5 17 1 -2 1 0 X6 14 2 1 -1 -z1 0 3 2 1 0 X5 24 2 - 0 X4 7 1 - -z1 -7 -4 - 32 / 48 - 0 X5 24 2 - 0 X4 7 1 - -z1 -7 -4 - - 于是得到最优解 X*=(0,0,0,7,24,0,0)T 于是最小值为 -5 添加松弛变量 x4， x5 2x1+x2+2x3+x4=2; 4x1+2x2+x3+x5=2 Cb Xb b 1 1 X1 X2 0 X4 2 2 1 0 X5 2 4 2 -z 0 1 1 0 X4 2 2 1 0 X5 33 / 48 2 4 2 -z 0 1 1 1 X3 1 1 1/2 1 0 X41 X5 -1 1 2 0 -1 0 1 1 0 -0 0 1 1 0 0 1 0 X3 X4 2 1 1 0 1 0 (2) 1 1 0 1* 1 1/2 0 0 X6 X7 0 0 1 1 0 - - 34 / 48 - - 0 ?iX5 0 1 0 0 1 1 2 0 0 2 ?i 4 0 X5 1 2 3/2 0 -1/2 1 -z -1 0 1/2 0 -1/2 0 1 X3 1 1 1/2 1 1/2 0 1 X2 1 2 (3/2) 0 -1/2 1 -z -1 0 1/2* 0 -1/2 0 1 X3 2/3 1/3 0 1 2/3 0 1 X2 2/3 4/3 1 0 -1/3 2/3 -z -4/3 -2/3 0 0 -1/3 -1/3 在最优单纯性表中， x5,x6 的检验数均为负数，于是得到最优解为 X*=(0,2/3,2/3,0,0)T,最优化目标值为 Z*=4/3。 35 / 48 添加松弛变量 x3， x4， x5， x6 Max 3x1+2x2 X1-3x2+x3=6 2X1+4x2+x4+x5= 8 -x1+3x2+x6=6 Cb Xb b 3 2 0 0 0 X1 X2 X3 X4 X5 0 X4 6 1 -3 1 0 0 0 X5 8 2 4 0 1 1 0 X6 6 -1 3 0 0 0 -z 0 3 2 0 0 0 0 X4 6 1 -3 1 0 0 0 X5 8 2 (4) 0 1 1 0 X6 6 -1 3 0 0 0 -z 0 3 2* 0 0 0 0 X4 12 5/2 0 1 3/4 3/4 2 X2 2 1/2 1 0 1/4 1/4 0 X6 0 -5/2 0 0 -3/4 3/4 -z -4 2 0 0 -1/2 -1/2 0 X4 12 5/2 0 1 3/4 3/4 2 X2 2 (1/2) 36 / 48 1 1/4 1/4 1 2 2/3 2 4/9 0 ?i X6 0 0 1 0 0 - 0 2 1 2 0 0 0 1 0 0 24/5 0 4 5 摘 要： 最优化方法普遍的应用于工业、农业、商业、交通运输、国防、通信、建设、等各个方面与我们的生活息息相关；最优化方法主要用来解决最优计划、最优决策、最优设计、最优37 / 48 分配等最优化问题。本文主要研究的内容是通过单纯形方法对最优化问题的解决进行归纳总结，分析最优化问题所涉及的原理和方法，使用软件对最优化问题进行实践仿真测试，并将最优化问题推广应用到生活当中去。 关键词 : 最优化 单纯形方法 仿真 Abstract Optimization method is widely used in industry, agriculture, commerce, transportation, defense, communications, construction, and other aspects of our lives; the optimization method is used to solve the optimal planning, optimal decision-making, optimal design, optimal allocation optimization problem. The main research content of this paper is summarized by the simplex method to solve the optimization problem, the principle and method of optimization analysis of the problems involved in the use of software simulation test of practical optimization problems, and promote the use of the optimization problem to life. 38 / 48 Keywords : optimization Simplex method Simulation 目 录 第一章 绪论 1 最 优 化 问 题 简述 1 单 纯 形 方 法 的 简述 2 39 / 48 第二章 最 优 化 问 题 研究 3 最 优 化 问 题 简介 3 最 优 化 问 题 的 发展 3 最优化问题的常见方法 40 / 48 4 最 优 化 的 工 作 步骤 5 模 型 的 基 本 要素 5 最优解的概念 7 41 / 48 最 优 化 方 法 的 应用 7 第 三 章 基 于 单 纯 形 法 的 最 优 化 方法 10 单纯形法方法及其特点 10 单纯形方法的基本思想 10 42 / 48 单 纯 形 法 的 迭 代 原理 11 基 于 单 纯 形 法 的 最 优 化 设计 14 单纯形法处理最优化的一般解题设计步骤可归纳如下 14 最 优 解 可 能 出 现 下 列 的 情况 15 43 / 48 第 四 章 软 件 仿 真 实验 16 软件简介 16 实验仿真 16 第五章 结论 44 / 48 19 致谢 20