单纯形法及其定理.doc

PAGE PAGE 3 单纯形法及其定理 摘要 二十世纪的时候人们开始关注线性规划问题，从那个时候开始，这个和实际问题有着巨大联系是数学问题就已经显现出了其重要性。今天，单纯形法作为一个标准工具，不管是公司的生产，经营，运输等各方面都会应用这种办法谋取最大的利益，最小的风险。它在社会其他领域的应用也已经迅速的开展。现在我们就来了解一下这个特别的工具。可以看到利用这种办法去求解“线性规划”的最优方案虽然已经是比较简单的了，但是还是能够通过各种途径去进一步优化计算过程，提升效率。不难发现，单纯形法中有好多步骤是可以省略的，因此当利用线性规划处理大型问题时矛盾便显得十分突出。比如对于成千上万个变元和约束条件时，单纯形表格占用的时间和空间，都将十分巨大。所以很多人开始付诸努力，也取得了一定的成绩，让单纯形法能够得到进一步地优化，比如说让运算量降低，或者说让存储空间更小化。改善的单纯形法大大降低了时间复杂度，而且还将看出其空间复杂性变化不大，计算量小，存储量小，我们有必要学会运用这种行之有效的运算方法，使它发挥出最大的力量。不过有一点需要注意，可以看到想要利用单纯形法，那么比如先给定初始可行基。所以说要是这个前提没有给定的时候，其实我们就必须人工添加。 关键字：单纯形法；定理；线性代数 目录 TOC \o 1-3 \h \z \u 1绪论 2 1.1研究背景 2 1.2研究意义 2 1.3国内外研究现状 3 2线性规划 4 2.1线性规划的本质 4 2.2线性规划的标准型 5 2.3任意模型化为标准型的方法 6 3线性规划的解法 7 3.1图解法 7 3.2线性规划问题的单纯形法的基本思路 8 3.3单纯形表 16 3.4改进的单纯形法 19 4结束语 28 参考文献 29 致谢 30 1绪论 1.1研究背景 运筹学是近年发展起来的一门学科。可以看到社会生活的方方面面其实都离不开运筹学，我们通过这种办法能够获取到最优的方案。这里面一个非常关键的部分就是线性规划。可以看到这是一种和实际生活有着极其密切联系的问题。其实这是就是说如果资源有限的情况下，我们到底要怎么做才能够最优配置，让资源能够发挥出尽可能多的价值，帮助我们回避风险，攫取利益。我们把这个问题和数学模型进行结合的话，其实就是说给定一些限制条件，可以通过不等式、等式这样的方式给出，希望能够让目标函数取到我们想要的最值。 和数学别的分支比较的话，其实能够看到线性规划相对来说研究时间比较短，但是和实际问题结合极其紧密。特别是提出“单纯形法”之后，可以看到线性规划逐渐开始系统化和完整化，而且有了更多地实际应用。实际问题的线性规划问题多种多样，它的约束条件可以有不同的形式，它可以是小于或等于形式的不等式，或者是大于或等于的不等式，也可以是等式，目标函数也有求最大值和最小值两种类型。线性规划问题在求解最优解的过程中，有时也会出现一些特殊情况。有无穷多个最优解的情况，有可行域误解的情况，还有约束条件无可行域的情况。单纯形法对于这些问题都能够适用。而且我们掌握了单纯形法在线性规划问题中的使用方法以后，就可以应用于许多复杂的、大型的问题，解决实际生活当中的问题。它在社会其他领域的应用也已经迅速的开展。现在我们就来了解一下这个特别的工具。这个特别的工具本质是什么？它能够解决什么类型的问题？所以本文为了能够给更方便理解，给出了一些例题，让我们通过例子，来了解线性规划，了解单纯形法。 1.2研究意义 二十世纪的时候人们开始关注线性规划问题，从那个时候开始，这个和实际问题有着巨大联系是数学问题就已经显现出了其重要性。今天，单纯形法作为一个标准工具，不管是公司的生产，经营，运输等各方面都会应用这种办法谋取最大的利益，最小的风险。它在社会其他领域的应用也已经迅速的开展。现在我们就来了解一下这个特别的工具。可以看到利用这种办法去求解“线性规划”的最优方案虽然已经是比较简单的了，但不难发现，单纯形法中有好多步骤是可以省略的，因此当利用线性规划处理大型问题时矛盾便显得十分突出。比如对于成千上万个变元和约束条件时，单纯形表格占用的时间和空间，都将十分巨大。我们能够通过各种途径去进一步优化计算过程，提升效率。所以很多人开始付诸努力，也取得了一定的成绩，让单纯形法能够得到进一步地优化，比如说让运算量降低，或者说让存储空间更小化。改善的单纯形法大大降低了时间复杂度，而且还将看出其空间复杂性变化不大，计算量小，存储量小，我们有必要学会运用这种行之有效的运算方法，使它发挥出最大的力量。而且因为计算机技术越来越发达，使其实用性逐步得到增强。 1.3国内外研究现状 1983年，S.Smale再次给出了Borgwardt在19