毕业设计（论文）-基于单纯形法的最优化方法.doc

摘 要： 最优化方法普遍的应用于工业、农业、商业、交通运输、国防、通信、建设、等各个 方面与我们的生活息息相关；最优化方法主要用来解决最优计划、最优决策、最优设计、 最优分配等最优化问题。本文主要研究的内容是通过单纯形方法对最优化问题的解决进行 归纳总结，分析最优化问题所涉及的原理和方法，使用软件对最优化问题进行实践仿真测 试，并将最优化问题推广应用到生活当中去。 关键词: 最优化 单纯形方法 仿真 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. keywords : optimization simplex method simulation 目目 录录 第一章 绪论1 1.1最优化问题简述1 1.2 单纯形方法的简述2 第二章 最优化问题研究3 2.1 最优化问题简介3 2.1.1 最优化问题的发展3 2.2 最优化问题的常见方法4 2.3 最优化的工作步骤5 2.3.1 模型的基本要素5 2.3.2 最优解的概念7 2.4 最优化方法的应用7 第三章 基于单纯形法的最优化方法10 3.1 单纯形法方法及其特点10 3.2 单纯形方法的基本思想10 3.2.1 单纯形法的迭代原理11 3.3 基于单纯形法的最优化设计13 3.3.1 单纯形法处理最优化的一般解题设计步骤可归纳如下13 3.3.2 最优解可能出现下列的情况14 第四章 软件仿真实验15 4.1 软件简介15 4.2 实验仿真16 第五章 结论19 致谢20 参考文献21 第 1 页 共 21 页 第一章绪论 最优化问题的解决方法是在最近几十年渐渐形成的。那么可想而知，就要 提到最优化问题的主要研究对象：是各种有组织系统的管理问题和一些生产经 营活动。最优化方法产生的目的是在于对所研究问题的整体，能有一个合理运 用物质、财产和人力的最优方案，并且让整体的效能达到一个增涨和提高，以 最终达到最优化解决问题的目标。实践是检验真理的唯一标准，实践证明，由 于人们掌握的科学技术的不断更新和进步，人类的发展生产经营规模的不断扩 大，最优化方法已经渐渐深入人心，成为了一个重要的理论依据在指导现代科 学管理中起到重要的作用。总之，现在最优化方法已经变得越来越重要了，被 普遍的应用到经济、管理、工程、国防等各个领域。 1.1最优化问题简述 最优化问题简单的可以说是一种数学问题，它的理论和算法是一个非常重 要的数学分支，又被人们叫做数学规划。所针对解决的问题就是在很多的计划 方案里确定什么计划方案最好，并且找出最优计划方案进行具体实施。下面我 们就针对工程类问题的最优化处理进行一下简单的介绍，让大家了解最优化方 法大概应该怎么去应用。首先，我们要进行问题的转化，即把工程问题转化成 数学问题，建立数学模型，也就是说使用数学表达式来更具体的描述工程上的 问题。然后，在建好数学模型的基础上，根据数学模型里的特点来选择用那种 最优化的设计方法，要求出问题的解还需要借助计算机这一现代科技必不可少 的工具，通过计算机上的软件编写程序来求出最优解，也就是所要求得最优化 的结果。所以，在这就可以总结一下工程上的最优化问题无非就是数学建模和 最优化方法的选择以及计算机软件编程方面的应用等一些内容。其中，工程优 化设计成败的关键是从工程实际命题中抽象出的正确的数学模型。 这也是工程 设计工作者进行优化设计时所要完成的主要任务。 我们已经了解到工程类问题 第 2 页 共 21 页 的最优化设计可以先建立数学模型。现在就针对数学模型来进行近一步的分析， 最优化问题设计时的数学模型一般包括一些设计的变量、目标函数和约束条件。 其中这三个基本要素：设计变量里的个数决定了应该设计空间的维数；还有设 计变量的要求那就是，在满足设计基本要求的前提下，把那些对设计目标影响 比较大的参数选为设计的变量，并根据具体问题具体分析的原则，给变量赋值 来简化设计变量的数量等。 总而概括，解决这一类最优化问题我们至少要注意两点：（1）要有明确的 问题方向，也即是说通过实际面临的问题的概况，进行简单的描述进而转化成 纯粹的数学问题，然后建立成一个数学建模的过程；（2）既然建好了数学模型 接下来就是求解过程，也就是说用已经掌握的最优化的相关知识来求解出最优 的处理方案 。数学问题来源于生活，然后又可以用数学知识来反作用于生活， 在掌握一定的数学基础的前提下，结合日常生活当中可能出现的数学问题， 通 过适当的规划安排，运用数学原理求解出行之有效的最优化方案。 在最优化介绍的末尾，我们不仅要了解最优化的一些简单常识，而且要更 进一步懂得研究最优化问题的意义所在，最优化方法致力于解决日常生活中的 一些常见规划安排问题，例如，如果要完成一件事情怎样能资源最省，时间最 省，并且效率高，产值高等常见的生活中的问题，这就需要你运用最优化的知 识来进行解决，用最优化方法来寻找一种更科学合理的方案来解决这些问题。 1.2 单纯形方法的简述 数学最优化中，由乔治伯纳德丹齐格（george dantzig）发明的单纯 形法（simplex algorithm）是线性规划问题的数值求解的流行技术。这二者都 使用了单纯形的概念，它是 n 维中的 n + 1 个顶点的凸包，是一个多胞体：直 线上的一个线段，平面上的一个三角形，三维空间中的一个四面体，等等。 单纯行法问题的理论依据为：在可行域为 n 维向量空间 rn 中的多面凸集的 线性规划问题中，如果其最优值存在则必在这个凸集的某顶点处达到。顶点所 对应的可行解称为基本可行解。 第 3 页 共 21 页 第二章最优化问题研究 2.1 最优化问题简介 最优化问题，主要是指以下形式的问题：给出一个函数，查找一个元素使 所有 a 的元素，取得最小化；或者最大化。这种类型有时也被称为“数学规划” （例如，线性规划） 。许多理论和实际问题可被建模为这样的一般性框架。最优 化，是应用数学的一个分支。 既然提到最优化问题是应用数学的一个分支，再此我就简略阐述一下最优 化问题的一些数学意义：人们为了解决最优化问题从而提出很多种求解的方法。 然而从数学意义上来说，其实求最优化问题就是一种求极值的问题，也就是说 在给定的一组条件约束的条件下，可以让系统的里的目标函数达到极大值或极 小值。然而，如果你从经济上来看，那就可以看成是在一定物质，人力的条件 下，通过最优化方法可以让系统的经济效益达到极值；或者也可以说是在效益 相等的前提下，让投入的人力、资源等物质越少越好。 2.1.1 最优化问题的发展 最优化问题离不开人类的发展，人类的不断发展也让最优化问题变得越来 越完善，早在公元前五百年的古希腊人就从建筑美学中懂得了黄金分割比，因 为只有按那个黄金分割比来建设建筑才可以让建筑更美达到建筑里的最优化。 到目前为止，在生活等各个方面中的黄金分割比仍然被广泛使用。随着人们知 识的增长，见识的开阔，很多有学识的人开始研究用具体的数学方法来打开最 优化方法研究的瓶颈。历史会证明一切，在最优化问题发展的过程中，不断被 科学家给以证明并不断完善最优化方法。为什么古代欧洲的城堡几乎都是圆形 的呢？那是因为给定的周边圆行区域所包含的面积是最大的，这是阿基米德所 证明的，也是前期人们对最优化问题的一种研究与追求。但是，直到 17 世纪以 后，使用科学的方法来解决最优化问题才算真正形成。在 17 世纪，牛顿和莱布 尼茨在其创作的微积分中，他们就发现了求解含有多个自变量的实值函数的最 第 4 页 共 21 页 大值和最小值得方法。时间在推移，人类在进步，直到第二次世界大战，不仅 是人类的大决战，更是科学技术进步的大熔炉。战时军事的需要从而使科学技 术和生产以高速发展，最优化问题的解决方法也已经无法被以往的方法所解决， 这也就导致了现代最优化方法的形成与出现。近现代最优化问题的出现其中的 一些标志性事件有：以苏联 .康托罗维奇和美国 g.b.丹齐克为代表的线性 规划；以美国库恩和塔克尔为代表的非线性规划；以美国 r.贝尔曼为代表的动 态规划；以苏联庞特里亚金为代表的极大值原理等。 ”这些人的研究很好的推进 了最优化问题研究的进步，这些近现代的方法慢慢的都形成了它们各自的体系， 这很好的对促进我们当代的运筹学，最优化问题，控制论和系统工程等的发展 起到了很重要的作用。 2.2 最优化问题的常见方法 任何事情都会有它的研究方法，当然最优化问题也不例外。要解决一个问 题就要有一个切实可行的方法，针对不同类型的最优化问题我们可以有不同的 处理方法，即使是遇到相同的最优化问题我们也可以用各种不同的方法来处理 这一个问题。我们从另一个方面来讲，不同类型的模型也要用不同的最优化方 法来处理。就目前来看，解决最优化的方法大体上可以分为解析法、直接法、 数值计算法等。 （1） 解析法：这种方法只适应于那些目标函数与约束条件是很明显的解 析式表达式的情况。解决这种问题的方法是：先要求出最优的必要条件，从而 得到一组方程或不等式，接下来，就要进行求解这组方程和不等式，一般可以 用求导数的方法或者变分法来求出必要的条件，然后再用必要条件来简化所求 的问题。 （2） 直接法：当遇到目标函数是那些较为复杂或者不是很确定的可变函 数时，没有办法用解析法求解出必要条件的时候。我们这时可以用直接查找的 办法通过若干次的迭代从而得到最优值。往往这种方法得到的结果是根据经验 和试验来实现的。还有当我们遇到一维（即单变量极值）的查找时，我们主要 使用消去法或者多项式插值法；而当遇到多维（即多变量极值）查找的问题时， 第 5 页 共 21 页 我们主要是应用的爬山法。 （3） 数值计算法：我们来说一下这个方法，这个方法也是一种直接的方 法。它往往是以梯度法为基础的一种解决最优化的方法，所以我们大家可以理 解为是一种解析与数值计算相组合的方法。 （4） 本次毕业设计研究的主要内容是基于单纯形法的最优化方法： 单纯形法的方法的优点:单纯形法它尝试从空间的一个顶点移动到另一个顶 点，直到人们找到最优点为止。单纯形法可以解决多维问题，那是因为它将图 形法转化成了代数法，从而避免掉了多维空间的不可描述性。 2.3 最优化的工作步骤 我们人类提出一个问题发现一种方法，都有它的用途。都有它的工作方法。 再此，我们就来进行工作步骤的具体讨论。在我们使用最优化方法解决现实中 我们自己遇到的实际问题时，我们通常可以用以下工作方法步骤：（1）首先， 我们要针对最优化提出关于他的问题，然后分工去进行一些关于这个问题的一 些数据和相应资料的收集采样；（2）这是在第二点也是很重要的一环，那就是 要建立数学模型关于你所要解决的最优化问题，并且还要确定最优化问题里面 包含的一些变量，确定变量之后，我们还要列出关于这个问题的目标函数和与 它对应的约束条件；（3）在上一步建立好模型之后，我们就要对问题的模型进 行更进一步的模型分析，分析后，我们来选择应该采用哪种最优化方法来解决 问题；（4）以上都齐全了以后我们就要开始进行求解了，对于求解现在我们一 般都是借助计算机软件程序，在计算机上进行操作求得结果；（5）最后，在上 一步我们求好解以后，我们还要对所遇到的问题进行一些常规的测试并根据问 题的具体情况进行完善和实地验证。从上述五个工作方法步骤中我们可以看出， 他们之间一环扣一环，环环相连，相互照应并且相互制约互相有影响，牵一发 而动全身。所以，在以后我们的具体实践工作里我们要反复的进行这几个步骤， 来确保我们所遇到的问题能最优化的完善解决。 2.3.1 模型的基本要素 第 6 页 共 21 页 在此，我专门分了一个小节来进一步介绍最优化工作步骤里的模型这一个 方面。将生活中实际的问题转化为我们所要的数学模型，它的重要性就好比， 建筑里的地基这一项，提出问题，就好比选好地址，而数学建模就好比是地基 的构建，万丈高楼平地起，孰不知只有地基打的深他才敢盖起那万丈的高楼啊！ 我们这里主要来说一下最优化模型，他主要包含了一些变量、约束条件和目标 函数三个基本的的要素。下面我们来在具体分析一下：（1）变量：大多数情况 下都是指在最优化问题中一些未确定的某些量，通常我们可以用 x=(x1，x2,xn)t 来进行表示；（2）约束条件：通常是指我们在求解最优解 的过程中对我们问题中的变量的一些包括时间上、技术上、和原料的限制等， 形象生动的说，就好比有人给你布置一道任务，要求你在一天之内就要完成， 其中这个一天之内就是一种约束条件。针对约束条件我们的原则是越接近实际 情况越好，因为只有这样才能让我们得出最贴近实际的最优解。约束条件在这 我们可以用 gi(x)0 表示 i=（1,2，m） ，m 表示约束条件数；或 xr(r 表示可行集合)。 （3）目标函数：所谓目标函数就是我们针对这个最优化问题到 底要达到一种什么样的程度达到一种什么样的标准，而目标函数就是把实际问 题数学化了在计算式更加符合数学的描述方式，一般我们可以用 f(x)来表示， 即 f(x)=f(x1，x2,xn)。目标函数总归还是目标函数，它还是必须要在规定 的约束条件的前提下，达到系统功能的最大值或者最小值。 针对最优化问题我们还可以有一些的分类 ：可以 根据其最优化问题中的 变量、约束条件、目标函数、问题的性质、时间的因素和函数关系等不同的情 况，又可以将最优化问题分成许多种不同的类型。 根据我们知道的一些函数功 能的解析性质，我们还可以进一步对各种方法进行一些分类。例如，若目标函 数和约束条件都是线性的，那么也就是说形成了线性规划。针对线性规划，我 们有专门的解法：例如单纯形法、椭球法、解乘数法等。如果当目标函数或约 束条件中有一为非线性函数时,那么，这个时候就形成非线性规划。而当目标函 数是二次的时候,而约束条件是线性的时候，那么这个时候，则称为二次规划。 现在来说二次规划的理论和方法都已经比较成熟。当我们遇到目标函数具有某 些函数的平方和的形式，则那时就又有专门用于求解平方和问题的优化方法了。 第 7 页 共 21 页 而当我们碰到目标函数具有多项式的形式时，又可以形成一类几何规划了。 2.3.2 最优解的概念 当我们遇到一个问题，我们就会想到要想办法去解决他，也就是说要求出 它的答案求出它的解。同样的最优化问题也是要求得解的，它的解我们通常叫 做最优解。在这我们就来说一下最优解的问题。最优解也分很多情况，当我们 只考虑约束集合中的一些局部范围内的情况时，这时候的最优解我们就称为局 部最优解；然而相反的当我们以考察整个约束集合为对象时，这时候的解我们 叫做总体最优解。当我们针对各种不同的最优化问题时，这时最优解也会被赋 予各种不同的含义，并且还会使用专用的名词来进行阐述。下面举个例子，就 像在对策论和数理经济模型里的解我们又称为平衡解；而当我们在控制类的问 题里我们又称为最优控制；还有当我们在多目标的决策问题里我们称为非劣解。 理想很丰满，但是现实很骨感！当在我们解决现实中的实际问题时，并不会像 理想里的那样标准，往往现实中遇到的实际问题都是非常的错综复杂，而那种 我们理想状态的最优解一般都不是那么容易去求得，即使是可以求解到也是要 付出非常高的代价的，所以在我们求解现实中问题最优解时往往要根据具体问 题具体分析的方法，只要求的解在一定可以承受的范围内条件下，也不一定非 要过分的来强调一定要最优，只要是能最接近最优就可以了，因为模型是理想 的，但是现实的实际是有误差的，所以无法确定一定最优。相应的针对这种情 况的存在，在最优化问题研究的早期，大约五十年代初，就有人先见的提到了 次优化这一概念和他相对应的次优解的概念。以上关于解的这些发现与讨论都 引出一个问题，那就是我们在提出这些概念时关于最优化所创建的模型只是一 种近似的模型，再另外加上在现实的实际问题里又有很多不确定的因素，尤其 是当含有非定量因素时很难在一个模型里都全部的考虑进去。从方法层面来说， 在处理这些问题上，目前我们还没有一些很有效的办法用来解决这些复杂的模 第 8 页 共 21 页 型。 2.4 最优化方法的应用 有的人会问，我们为什么要学习知识，我们为什么要研究一个问题，我想 那是因为学以致用的原因，应为我们要使用它所以我们去学习去研究。当然话 说回来了，我们研究最优化问题不也是为了应用吗？所以在这一段我们就来探 讨一下最优化问题的应用。通常我们针对最优化先进行一些大概总体方面的分 析，我们现在可以从最优的控制、最优的设计、最优的管理、最优的规划这些 大的方面来一点点的着手分析他的应用。 （1）我们先来说一下最优控制的应用 有哪些，一般主要我想应该集中在对各种人类构建的控制系统的优化。可以举 一些常见例子，像马上就要进行的俄罗斯的卫国战争的阅兵式上我们从彩排中 可以看到很多型号的导弹，在军事上用到的优化设计就是导弹系统的最优化设 计，也就是说在保证完成任务的前提下，我们可以用最优控制使用尽可能少的 燃料来完成相同的任务。还有我们国家的航天，航空母舰，飞机等系统也都是 需要用到最优化控制来掌控整个系统的调配；即便是民用的一些行业，像工厂， 电力调度等也是需要合理地运用最有设计来解决问题的；（2）第二个我们来说 一下最优设计的一些应用，目前世界上很多国家在工程制造领域都将最优设计 用在其中，像在飞机，轮船，汽车的外观设计上都追求在外形上怎么减少他们 在运动中所遇到的阻力，怎么设计能让他的能耗最低，能节能减排，促进环保， 美化自然。还有在我们学的电子电路这一块，电子原件怎么最优设计，才能制 作出即功能全面又携带方便，怎么能更符合人体工学让我们人类感到更满意都 等待着最优设计来解决这一问题。还有在一些工业生产方面，我们可以用最优 设计来设计出最优的原料配比，来让产品最优的服务于大众，更好的促进我们 人类文明又好又快的进步；（3）最优管理这个也是很好理解的，我们无论是个 人还是一个企业都要学会管理自己的一些东西，个人来说，你要自己来管理你 的时间、工作、生活等各个方面，然而只有你运用了最优化管理才能使自己的 生活得到一个提升，自己只是一个小的方面，我们来看看企业上，一个企业的 管理层如果懂得了使用最优管理的方法来管理企业员工，那他们的企业一定会 第 9 页 共 21 页 非常的高效率，在日常公司管理中制定详细科学的计划，合理调度，合理管理 运营，还有随着现在计算机信息技术在管理中的运用，更让最优管理如虎添翼， 插上了腾飞的翅膀；（4）这一点我们说一下最优规划，并不是因为太在后面提 到他就不重要了，恰恰相反我感觉规划还是挺重要的，正如俗话说的凡是预则 立，不预则废；这就说明了规划还是挺重要的。我们应该宜未雨而绸缪，勿临 渴而掘井。同样告诫我们规划的重要性。规划在我们国家可以说非常常见，大 家耳熟能详的就有十一五规划，十二五规划等，这就说明最优规划在我们的现 代国家部门有着举足轻重的地位，在实际的现实生活里，无论是国家部门还是 农业，工业，能源资源等的方面都需要一个长远而合理的最优规划。因为一个 重要的最优规划决定了整个社会的发展方向！所以我们不容忽视最优化问题在 我们生活里的一些应用，因为他和我们的生活息息相关！ 第 10 页 共 21 页 第三章基于单纯形法的最优化方法 3.1 单纯形法方法及其特点 现在，本章我们是基于单纯形法的方面来解析一下最优化方法。首先我们 既然提到单纯行法，就要大概知道它是什么，虽然在前面的段落也有提到，但 在这里我们可以简单的说，单纯形法就是求解线性规划问题的一般方法。关于 单纯形法的理论依据是这样定义的：也就是说，在给定的线性规划问题里，当 可行域是 n 维向量空间 rn 中的多面凸集，它的最优值假如存在则必在该凸集的 某顶点处达到。而这个顶点它所对应的解决方法的可行解我们就称它为基本可 行解。并且在这还要提一下，单纯形法，它是一种直接、快速搜索求得最小值 的方法，它最大的优点就是在于对目标函数的解析性没有太多的要求，并且收 敛速度快，还有就是应用范围较广。 3.2 单纯形方法的基本思想 人是一棵会思考的芦苇，人和动物的区别就在于人是有思想的动物。现在 我们就针对我们的研究对象单纯形法来说一下它在解决问题的时候的主要基本 的思想。首先，要知道单纯行法是一种多变量函数来寻找最优化的方法，它的 基本主要思想是这样的：第一步，我们要找到一个基本的可行解，然后要对这 个解进行判定，看看它是否是最优解；如果是那就好解决了，但是当如果不是 的时候，我们就要遵循一定的规则转换到另一个改善的基本可行解，然后再接 第 11 页 共 21 页 着对它进行判定，如果是最优解就可以了，如果还是不是最优解，那就再进行 转换判断，不断重复的遵循这个方法进行判定，直到得到最优解再结束。由于 存在的基本可行解的个数是有限的，所以我们通过有限次数的转换肯定可以得 出问题所要求的最优解。反正只要遵循这个方法就可以求出最优解。就算当出 现问题没有最优解的那种情况也能使用这种方法来进行判断。因为我们可以根 据最优化理论及时的发现，并且停止计算，来避免错误及无效运算。 3.2.1 单纯形法的迭代原理 枚举法：如果线性规划问题存在最优解，则肯定可以在某个顶点上达到， 即在某个基本可行解上可以取得最优解。因此，针对线性规划问题，就是把所 有基本可行解都找出来，然后逐一进行比较，从而可以求出最优解。 逐步改善法：针于线性规划的问题，我们第一步要找出一个基本的可行解， 再判断其对应的是否为最优解，如果求得的不是最优解，则就应该再去寻求一 个更好的基本可行解，直到我们找到最优解为止，但是当我们使用这种逐步改 善的求解方法时，我们就需要解决以下三个问题： （1）我们怎么来判断当前的基本可行解是否已经达到了最优解 （2）如果当前解不是最优解，以及我们如何去寻找一个比当前解更好 的基本可行解 （3）还有在开始的时候，我们如何得到一个初始的基本可行解。 下面具体举一个关于单纯形法的线性规划的例子： 例题 求解下列线性规划问题的最优解 00 4 155 1602030 25max 21 1 21 21 21 xx x xx xx xxz 解：把上面的式子化成为标准形式 第 12 页 共 21 页 0 4 155 1602030 00025max 51 51 421 321 54321 x xx xxx xxx xxxxxz 第一步：首先要确定一个初始基本可行解；基本可行解就是满足非负条件 的基本解，因此要在约束矩阵 a 中找出一个可逆的基矩阵。 10001 01015 0012030 a 这里 m=3，3 阶可逆方阵，可以看出 x3,x4,x5 的系数列向量是线性独立的， 这些向量构成一个基 ，对应的基变量为 x3,x4,x5，x1,x2 为非基),( 100 010 001 543 )0( pppb 变量。 将基变量用非基变量表示，由(2)得： 将(3)代入目标函数得 z=5x1+2x2+0 令非基变量 x1=x2=0,代入(3),得到一个基可行解 x(0) x(0)=(0,0,160,15,4) 第二步：从当前基可行解转换为更好的基可行解； 从数学角度看，x1,x2 的增加将会增加目标函数值，从目标函数值中 x1,x2 前的系数看，x1 前的系数大于 x2 前的系数，所以让 x1 从非基变量转为基变量， 称为进基变量，怎样确定离基变量： 因为 x2 仍为非基变量，故 x2=0 第 13 页 共 21 页 则(3)式变为 min=3，所以当 x1=3 时，x4 第一个减少到 0，所以 x4 出基 则 此时非基变量为 x2,x4,用非基变量表示基变量，代入(3) 将(4)代入目标函数得 z=15+x2-x4 第三步：继续迭代 x2 进基，x4 仍为非基变量，令 x4=0，则(4)式表示为 min=5，所以当 x2=5 时，x3 首先减少到 0，所以 x3 出基 则 此时非基变量为 x3,x4,用非基变量表示基变量，代入(4) 第 14 页 共 21 页 将(5)代入目标函数得 此时若非基变量 x3,x4 的值增加，只能使 z 值下降 所以 x(2)为最优解，z*=20, x*=(2,5, 0,0,2) 3.3 基于单纯形法的最优化设计 3.3.1 单纯形法处理最优化的一般解题设计步骤可归纳如下： （1）.把线性规划问题的约束方程组表达成典范型方程组，找出基本可行 解作为初始基本可行解。 （2）.如果基本可行解不存在，即约束条件有矛盾，则这个问题无解。 （3）.如果基本可行解存在，从初始基本可行解作为出发点，根据最 优性条件和可行性条件，引入非基本变量取代某一基本变量，找出目标函数值 更优的另一基本可行解。 (4).按照步骤 3 进行迭代,直到找到对应检验数满足最优性条件（这时 目标函数值不能再改善） ，即解得问题的最优解。 (5).如果迭代过程中发现问题的目标函数值无界，则终止迭代。 计算步骤流程图可以简单表述如下（如图 3-1） 第 15 页 共 21 页 图 3-1 算法流程图 3.3.2最优解可能出现下列的情况： 运用单纯形法可以很好的解决好最优化问题，在解决问题求得结果后，它 的解可能出现的情况一般有这几种情况：（1）存在着一个最优解；（2）无穷 多个最优解存在着；（3）不存在最优解，这只在三种情况下发生，即没有可行 解或各项约束条件不限制目标函数的值无限增大（或向负的方向无限增大） 。 第 16 页 共 21 页 第四章软件仿真实验 4.1 软件简介 mldemos 是一个开源的可视化工具 ，用机器算法来帮助人们学习和了解几 种算法的功能，软件可以解决在 分类，回归，聚类等方面的问题， mldemos 是开源和免费的，用于个人和学术用途。软件图形如下（图 4-1） 图 4-1 mldemos 软件图标 本次实验仿真图就是根据这个软件对单纯行法的方法进行更真实的软件仿 真，让大家能更生动的看到单纯形法求最优化的图形过程。 4.2 实验仿真 （1）首先，打开软件就就会进入如下开始界面（如图 4-2）： 第 17 页 共 21 页 图 4-2 开始界面 （2）下面开始画图，具体做法：用鼠标左键单击会形成深浅不同的层次， 表示目标函数的等高图，然后画成如下所示图形（如图 4-3） 图 4-3 软件画图 （3）画好图形以后打开本次所要仿真的选项：在最优化选项里的单纯形法 选项，打开仿真选项然后，再进行仿真（如图 44）和仿真软件选项放大图 （如图 4-5） 第 18 页 共 21 页 图 4-4 打开仿真选项 图 4-5 仿真软件选项放大图 （4）在打开仿真选项后，用鼠标选好初始点，然后就确定仿真，软件会自 动生成仿真的结果。 （如图 4-6） 第 19 页 共 21 页 图 4-6 仿真结果 图形分析：我们通过图形可以看到图形从开始选定的初始点，由单纯形法 依次迭代慢慢的沿着等高线逐渐爬升知道找到最优点为止。 仿真实验总结：理论是实践的基础，但是只有实践才能更好的对理论进行 深入的表达。所以我们这次仿真实验就是对理论单纯形法方法下的最优化的最 好的展现。 第五章结论 通过近三个多月的努力工作，基于单纯行法的最优化问题的毕业设计论文 终于在我的不懈努力下圆满的完成了。在这次毕业设计论文的写作过程中，遇 到了很多的问题，也有很多的困惑，但是，都在老师和同学的悉心帮助下，以 及我本人的努力下一一顺利解决了，并且在学习过程，我收获到了很多，也有 了一些亲身的感悟： 首先，论文写作的过程我认为是一个不断进步不断学习的过程，从刚一开 始，论文写作时对最优化问题的认识不是很清楚到渐渐的了解，以及到最后对 第 20 页 共 21 页