下载文档原格式
运筹学单纯形法
运筹学单纯形法，又称单纯性法，是一种用于求解线性规划问题的数学方法，它在运筹学中发挥着重要作用。
它主要应用于决策及资源分配问题，可以帮助决策者更好地把握资源的优化配置，并寻求最优解。
单纯性法是以线性规划问题作为理论基础，它是将该问题转化为一系列形如Ax=b的线性方程组的运筹学方法。
在这个方程组通过调整方程中的系数和右面常数而变换为形如Cx≤d的不等式形式，而这种不等式系统称为单纯性约束条件。
单纯性法从不等式中寻找一系列基向量，并通过改变基向量来实现改变不等式的求解方程之间的关系，从而求出最优解的问题。
传统的单纯性法分为有界单纯性和无界单纯性两种情形。
无界单纯性以简单费用曲线方法、扩展的简单费用曲线方法和增广次数法三大类。
有界单纯性主要是对对角单纯性和非对角单纯性这两类单纯性系统分别使用不同的方法进行求解。
单纯性求解方法在线性规划问题求解中具有重要应用，它能通过求解线性规划问题中的一系列互不相关的子问题来求出最优解。
使用该方法，可以以最少的成本达到最优的收益，它包括费用最低优化、网络流优化、全格研究和数学优化模型等。
线性规划中的单纯形法性能优化思路研究线性规划作为一种常见的数学优化方法，广泛应用于运筹学、经济学、工程管理等领域。
而单纯形法作为解决线性规划问题的经典算法，其性能的优化一直是研究的焦点。
本文将探讨在单纯形法中，如何优化算法的性能。
一、算法复杂度分析单纯形法作为一种迭代算法，其性能主要取决于迭代次数和每次迭代的计算量。
因此，为了优化算法的性能，我们可以从这两个方面入手进行研究。
1. 迭代次数优化在单纯形法中，每次迭代都要经过两个关键步骤：选择进入变量和选择离开变量。
不同的选择策略会导致不同的迭代次数，因此优化选择策略可以减少迭代次数，从而提高算法的性能。
一种常见的优化策略是使用人工变量的初始基解来选择进入变量。
通过合理的选择人工变量，可以使得初始基解更接近最优解，从而减少迭代次数。
此外，还可以利用对偶问题的信息来优化迭代次数。
通过对原始问题和对偶问题进行对偶互换，可以得到新的线性规划问题。
在新问题中，由于对偶互换，原问题中的非基变量在新问题中成为基变量，而原问题中的基变量在新问题中成为非基变量。
通过对新问题进行求解，可以获得原问题的最优解。
这种方法可以减少迭代次数，尤其在原问题的基变量数量较多时效果更为显著。
2. 计算量优化单纯形法中的计算量主要集中在两个方面：计算基解和计算进入变量对应的离开变量。
优化这两个计算过程可以有效减少算法的时间复杂度。
在计算基解时，我们可以利用特殊结构或者概率分布等信息来简化计算过程。
例如，如果问题具有稀疏性质，我们可以利用稀疏矩阵的性质，避免对全部元素进行计算。
在计算进入变量对应的离开变量时，可以使用快速计算方法来减少计算量。
一种常见的方法是利用矩阵运算，通过向量化计算，将多个计算过程合并为一个矩阵运算，从而减少了计算的时间复杂度。
二、启发式算法优化除了以上基于数学理论的优化方法，我们还可以借鉴启发式算法的思想来提高单纯形法的性能。
启发式算法通过模拟人类的思维方式，通过一系列规则和策略来寻找问题的最优解。
探讨单纯形法的改进单纯形法是一种常见的线性规划求解算法，其基本思路是通过构建初始可行解和不断进行单纯形变换来逐步优化目标函数值。
尽管单纯形法具有一定的优越性和适用性，但在实际问题中，其存在一些问题，如对初始可行解的依赖性、极端点模糊等。
因此，对单纯形法进行改进是非常必要的。
一、基于初始点优化的单纯形法改进传统的单纯形法在构建初始可行解时通常采用随机选取变量赋初值，但这种方法存在依赖性和不确定性，容易导致求解结果出现错误。
因此，提出了一种基于初始点优化的改进方法，即将常用的预处理算法与单纯形法相结合，利用已知的问题结构和性质，从而能够更准确地构建初始可行解，并快速找到最优解。
二、非正则化单纯形法改进传统的单纯形法在处理极端点问题时存在一定的缺陷，其主要原因除了初始可行解的问题之外，还与算法本身的局限性有关。
为了克服这些问题，可以通过非正则化单纯形法来进行改进。
这种方法不仅可以克服传统单纯形法无法处理的极端点问题，还可以有效减少目标函数下降的步骤，从而提高算法的效率和可靠性。
三、随机游走单纯形法改进在应用单纯形法解决实际问题时，如果问题本身具有复杂性和难以预测性，传统的单纯形法可能会出现效率低下和求解结果不稳定等问题。
针对这些问题，可以采用随机游走单纯形法进行改进。
该方法通过随机游走和概率转移等操作，将求解过程从搜索解空间的确定性过程转变为概率性的过程，从而能够更有效地避免局部最优解，并提高算法的稳定性和可靠性。
双端单纯形法是一种新颖的基于单纯形法的优化算法，其基本思路是同时从两个端点开始进行求解，分别向另一个端点移动，直到找到最优解为止。
相较于传统的单端单纯形法，双端单纯形法具有更强的适应性和搜索能力，能够更好地应对复杂性和非线性性问题，从而提高算法的求解效率和质量。
综上所述，单纯形法的改进是一个不断完善和发展的过程，不同的改进方法可以针对不同的问题和应用场景，有效提高算法的效率和可靠性，并在实际问题中得到广泛应用。
学习运筹学的体会与心得运筹学学习总结古人云“运筹帷幄之中，决胜千里之外”，运筹学是20世纪三四十年代发展起来的一门新兴交叉学科，它主要研究人类对各种资源的运用及筹划活动，以期通过了解和发展这种运用及筹划活动的基本规律，发挥有限资源的最大效益，达到总体最优的目标。
经过这一个学期的学习，我们应该熟练地掌握、运用运筹学的精髓，用运筹学的思维思考问题，即：应用分析、试验、量化的方法，对实际生活中的人力、财力、物力等有限资源进行合理的统筹安排。
本着这样的心态，在本学期运筹学课程将结束之际，我对本学期所学知识作出如下总结。
一、线性规划线性规划解决的是：在资源有限的条件下，为达到预期目标最优，而寻找资源消耗最少的方案。
而线性规划问题指的是在一组线性等式或不等式的约束下，求解一个线性函数的最大或最小值的问题。
其数学模型有目标函数和约束条件组成。
解决线性规划问题的关键是找出他的目标函数和约束方程，并将它们转化为标准形式。
解决线性规划问题的主要方法有：图解法、单纯型法、两阶段法、对偶单纯型法、计算机软件求解等方法。
自19xx 年苏联数学家康托罗维奇提出线性规划问题和19xx年美国数学家丹齐格求解线性规划问题的通用方法──单纯形法以来，线性规划可以说是研究得最为透彻的一个研究方向。
单纯形法统治线性规划领域达40年之久，而且至今仍是最好的应用最广泛的算法之一。
简单的设计2个变量的线性规划问题可以直接运用图解法得到。
但是往往在现实生活中，线性规划问题涉及到的变量很多，很难用作图法实现，但是运用单纯形法记比较方便。
单纯形法的发展很成熟应用也很广泛，在运用单纯形法时，需要先将问题化为标准形式，求出基可行解，列出单纯形表，进行单纯形迭代，当所有的变量检验数不大于零，且基变量中不含人工变量，计算结束。
将所得的量的值代入目标函数，得出最优值。
利用单纯形表我们可以：（1）直接找出基本可行解与对应的目标函数值；（2）通过检验数判断原问题解的性质以及是否为最优解。
学习运筹学的总结与心得领悟祖先云“夫运筹决胜之中，决胜千里之外” ，怀着对运筹学的神往与崇拜之情，这学期我选择了运筹学这门课程。
经过学习，我知道了运筹学是一门拥有多科学交织特点的边缘科学，是一门以数学为主要工具，追求各种问题最优方案的优化学科。
经过一个学期的学习，我们应该熟练地掌握、运用运筹学的精髓，用运筹学的思想思虑问题，即：应用解析、试验、量化的方法，对本质生活中的人力、财力、物力等有限资源进行合理的兼备安排。
本着这样的心态，在本学期运筹学课程将结束之际，我对本学期所学知识作出以下总结。
一、线性规划线性规划解决的是：在资源有限的条件下，为达到预期目标最优，而搜寻资源耗资最少的方案。
而线性规划问题指的是在一组线性等式或不等式的拘束下，求解一个线性函数的最大或最小值的问题。
其数学模型有目标函数和拘束条件组成。
解决线性规划问题的要点是找出他的目标函数和拘束方程，并将它们转变为标准形式。
解决线性规划问题的主要方法有：图解法、单纯型法、两阶段法、对偶单纯型法、计算机软件求解等方法。
简单的设计 2 个变量的线性规划问题可以直接运用图解法获取。
但是经常在现实生活中，线性规划问题涉及到的变量很多，很难用作图法实现，但是运用单纯形法记比较方便。
单纯形法的发展很成熟应用也很广泛，在运用单纯形法时，需要先将问题化为标准形式，求出基可行解，列出单纯形表，进行单纯形迭代，当全部的变量检验数不大于零，且基变量中不含人工变量，计算结束。
将所得的量的值代入目标函数，得出最优值。
利用单纯形表我们可以（1）直接找出基本可行解与对应的目标函数值；（2）经过检验数判断原问题解的性质以及可否为最优解。
每一个线性规划问题都有和它陪同的另一个问题，若一个问题称为原问题，则另一个称为其对偶问题，原问题和对偶问题有着特别亲近的关系，以致于可以依照一个问题的最优解，得出另一个问题的最优解的全部信息。
对偶问题有：对称形式下的对偶问题和非对称形式下的对偶问题。
第３０卷第１Ｏ期 Ｖｏ１．３Ｏ Ｎ０．１０ 重庆工商大学学报（自然科学版） Ｊ Ｃｈｏｎｇｑｉｎｇ Ｔｅｃｈｎｏｌ Ｂｕｓｉｎｅｓｓ Ｕｎｉｖ．（Ｎａｔ Ｓｃｉ Ｅｄ） ２０１３年１０月 Ｏｃｔ．２０１３
文章编号：１６７２—０５８Ｘ（２０１３）１０－００９１－０５
运筹学课程中单纯形法教学的几点思考木 孙祥凯 （重庆工商大学数学与统计学院，重庆４０００６７）
摘要：线性规划问题的单纯形法一直是运筹学课程教学的重点和难点，通过对线性规划问题单纯形 法计算原理的分析和研究，指出了线性规划问题的单纯形法思想与运输问题的表上作业法以及目标规划问 题的单纯形法之间的区别与联系，给出了一种求解目标规划问题的更简便方法；教学实践证明这些方法更 能够加深学生对单纯形法的算法逻辑的认识和理解。 关键词：线性规划；单纯形法；运输问题；目标规划；教学改革 中图分类号：Ｇ５２１ 文献标志码：Ａ
运筹学是２０世纪新兴的一门应用学科，它能够帮助决策者解决那些可以用定量方法和相关理论方法来 处理的问题。它在诸如经济规划、计划管理、金融决策、能源开发、工程设计、农业种植、卫生保健以及军事 科学等领域有着重要的应用。不仅如此，运筹学问题也常常涉及经济学、对策论、系统工程和控制论等学科 的研究领域＿１ ］。作为运筹学的一个重要分支，线性规划的应用极其广泛，其作用已为越来越多的人所重 视。特别是美国数学家Ｇ．Ｂ．Ｄａｎｔｚｉｇ在１９４７年提出了求解一般线性规划问题的求解方法，即单纯形法之 后，线性规划在理论上更进一步趋于成熟。至今，单纯形法仍然是行之有效且被广泛应用的求解线性规划 问题的方法。除此之外，单纯形法在运筹学中的运输问题以及目标规划问题中也有着十分重要的作用。因 此深入理解单纯形法的基本思想以及求解步骤，对运筹学后续学习有着十分重要的作用。 本文主要从单纯形法的基本思想出发，进一步阐述单纯形法的求解步骤，同时分别比较求解运输问题 的表上作业法以及求解目标规划问题的单纯形法与线性规划问题的单纯形法之间的区别与联系。不仅加 深了学生对单纯形法的理解和认识，而且增强了学生对运筹学学习的兴趣。
１ 单纯形法的基本思想及其直观理解 线性规划问题的所有可行解构成的集合（即可行域）是凸集，它们有有限个顶点，并且其最优值如果存 在必在该凸集的某顶点处达到。这里顶点所对应的可行解，称为基本可行解。单纯形法是解线性规划的一 种传统而且有效的方法，其基本思想 ， ：先找出一个基本可行解，对它进行判断，看是否是最优解；若不是， 则按照一定法则转换到另一个使目标函数能增加的基本可行解，重复这一迭代过程，直到求得问题最优解。 因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。 在学习单纯形法求解线性规划时，我们首先需要十分清楚单纯形表中的相关概念及其直观的图形解
收稿日期：２０１３－０３－１３；修回日期：２０１３－０４－２５． 基金项目：国家自然科学基金（１１１７１３６２和１１２０１５０９）；重庆市自然科学基金（ｃｓｔｃ２０１２ｊｊＡ０００３３）． 作者简介：孙祥凯（１９８４一），男，山东青州人，在站博士后，讲师，从事最优化理论与应用的研究． ９２ 重庆工商大学学报（自然科学版） 第３０卷 释。例如，线性规划问题的基可行解实际上就是其可行域的顶点，所谓的单纯形实际上指的是一维空间中 的线段、二维空间中的三角形，三维空间中的四面体以及ｎ维空间中的含有ｒｔ＋１顶点的多面体。其次，也要 善于将单纯形法每一步所得结果与线性规划问题的图解法做一个比较，进一步的理解其几何意义。这样， 学生不仅可以很容易的理解单纯形法的含义，而且对单纯形法的后续学习也有一个良好的铺垫。
２单纯形法的求解步骤及注意事项 由上一节所介绍的单纯形法基本思想可知，首先在线性规划问题的系数矩阵中构造一个单位矩阵作为 初始可行基，然后逐步进行迭代，进而判断解的类型以及解的存在与否，最终找到最优解。为了学生在学习 中能够对单纯形法有一个更加简洁明了、深刻的理解，下面进一步阐述单纯形法的求解步骤。给定一个线 性规划问题（此处假定是对目标函数求最大的线性规划问题），用单纯形法对其求解，具体步骤如下： （１）确定初始基可行解。首先找出初始基矩阵，通常选取系数矩阵中的单位方阵为初始基矩阵。然后 选取初始基矩阵对应的变量为初始基变量，剩余的变量为非基变量。最后只需令非基变量为零，则就可以 得到一组初始基可行解。 （２）最优检验。首先求解非基变量的检验数（基变量的检验数无需求解，都为零）。若非基变量的检验 数全为负数，则达到最优解，停止计算。若存在某个检验数为正数，并且其对应的列向量为负，则此问题无 界，停止计算。否则进行下一步。 （３）迭代。确定换人变量以及换出变量，重新建立新的基矩阵，基变量以及非基变量，从而得到新的基 可行解。按照上述步骤重新计算，直到找到最优解为止。 单纯形法的求解步骤思想十分简单，然而由于在求解过程中，需要列大量的单纯形表，计算量很大。若 个地方出错，整个计算就前功尽弃。所以在实际操作中，我们需要加强学生对单纯形法表的计算。这样 不仅可以加深学生对单纯形法的理解，而且可以使得学生对单纯形表中的相关概念有更准确的把握。
３运输问题的表上作业法 运输问题作为一类特殊的线性规划问题，其在现实世界中有着广泛的应用。目前求解运输问题的一种 常用方法是表上作业法。表上作业法是单纯形法在求解运输问题的一种简化方法，其实质是单纯形法。但 是两者之间在具体的计算和术语上有一定的差别。为了让读者对表上作业法有更清晰的认识和理解。将 表上作业法的几点注意事项归纳如下： （１）确定运输问题的初始基可行解，求出运输问题的初始调运方案。运输问题的初始基可行解是在 （ｍ×ｎ）产销平衡表上给出ｒｅ＋ｎ－１个数字格。通常的方法有最小元素法和伏格尔法。 （２）求解运输问题非基变量的检验数，就是求解产销平衡表上空格的检验数。然后进行最优判定。通 常求解检验数的方法有闭回路法和位势法。此处要特别的注意，前面所阐述的线性规划问题都假定目标函 数实现最大化，而运输问题的目标函数是要求实现最小化，故此时我们要保证所有的检验数不小于零。 （３）在利用表上作业法求解计算时，一定要区分好何处利用表格中运量的数据、何处利用表格中运价的 数据。例如在利用闭回路法求解检验数时，利用的是空格处的运价进行计算。而在利用闭回路调整法确定 换入变量以及换出变量时，考虑的是相应基变量（数字格）处的运量。所有这些就需要我们深刻理解表上作 业法的本质含义。 第１０期 孙祥凯：运筹学课程中单纯形法教学的几点思考 ９３ ４ 目标规划问题的单纯形法及其直接求解方法 目标规划是目前处理多个目标决策的一种方法。它是针对线性规划目标单一的局限性而提出的，是线 性规划的应用的进一步拓展，也是解决现实实际问题的一种行之有效的方法。由于目标规划的多个目标之 间不仅有主次先后之分，而且有时会互相矛盾，相互制约。因此求解目标规划所用的单纯形法主要是利用 了分层的思想，即在建立单纯形表时，需要对检验数行按照优先因子的个数分别列成多行，然后首先考虑第 个优先因子系数的正负，以此类推，直到求出最优解（满意解）为止。具体计算步骤可参考清华大学出版 社出版的《运筹学》（本科版）教材 ｊ。 目前针对目标规划的单纯形法的计算过程，大多数教材是直接给出相应例题的单纯形表中检验数的取 值，而具体的求解过程却没有。这对初学者就会造成一定的困惑，不知检验数是如何求出的。针对这一问 题，借助一个例子给出求解目标规划问题的一种直接单纯形求解方法，并阐述了教材中检验数的求解过程。 例：试用单纯形法求解下述目标规划问题： ｍｉｎ Ｚ＝Ｐ】ｄ ＋Ｐ２（ｄ；＋ ；）＋Ｐ３ｄ； ２ ｌ＋ ２＋ ３＝１１ １一 ２＋ｄ —ｄ ＝０ １＋２ ２＋ｄ；一ｄ；＝１０ ８ １＋ｌＯｘ２＋ｄ；一ｄ；＝５６ 。一３≥０， ． ≥Ｏ（ｊ＝１，２，３） 分析：由于目标规划问题的数学模型结构和线性规划问题的数学模型结构没有本质区别，所以按照求 解线性规划问题的单纯形法进行求解。在求解过程中只需假设Ｐ。》Ｐ 》Ｐ，即可。当然如果目标函数中含 有 个优先因子，只需假设Ｐ。》Ｐ：》…》 即可。只有这样假设，才能保证在计算过程中按照优先因子的 先后顺序来考虑。 解：取 ，，ｄ ，ｄ；，ｄ；为初始基变量，列初始单纯形表。 表１初始单纯形表
由表１以及Ｐ 》尸：》Ｐ，可知： 。和 ：的检验数为负数。进一步的，结合表一最右端的０值可得： 为 换人变量，ｄ；为换出变量。下面我们完全按照线性规划问题单纯形法的求解步骤继续迭代得到新的单纯形 表。重复上述步骤，最终一定可以得到目标规划问题的满意解。为节省篇幅，仅给出迭代后得到的表２，即 重庆工商大学学报（自然科学版） 第３Ｏ卷 最终单纯形表。 表２最终单纯形表
表２的检验数全为正数，所以目标规划问题达到满意解。满意解为（２，４，３）。通过上述解法不难发现： 由于目标规划问题的数学模型结构和线性规划问题的数学模型结构没有本质区别，所以可以完全按照求解 线性规划问题的单纯形法进行求解目标规划问题，并且求解更加方便易懂。通过观察教材上关于目标规划 单纯形表中的检验数行，容易发现其检验数行Ｐ ，Ｐ：，Ｐ 对应的数字实际上就是表１以及表２中所得检验数 行的Ｐ。，Ｐ ，Ｐ，的系数。
５结束语 作为运筹学的一个重要分支，线性规划问题已经广泛应用到工业、商业、农业、交通运输业等各个领域。 而单纯形法作为求解线性规划问题模型的一种行之有效的方法，其可以广泛应用到求解运输问题以及目标 规划问题等模型中。因此深刻理解线性规划问题单纯形法的基本原理以及解题思路对运筹学相关问题模 型的求解，特别是运输问题以及目标规划问题的求解有着十分重要的作用。本文通过对线性规划单纯形法 的进一步阐述，阐明了单纯形法在运筹学课程中各种问题模型求解术语的区别与联系，加深了学生对运筹 学相关问题的的求解方法和原理，消除了学生对各种问题模型中单纯形法求解的困惑。
参考文献： ［１］《运筹学》教材编写组．运筹学［Ｍ］．本科版．北京：清华大学出版社，２００５ ［２］胡运权．运筹学基础及运用［Ｍ］．北京：高等教育出版社，２００４ ［３］杨盛昌．目标规划问题的建模方法探析［Ｊ］．云南民族学院学报：自然科学版，２００１，１０（２）：３５１—３５５ ［４］褚淑贞．运筹学课程教学模式确定［Ｊ］．教学教育，２００３（３）：３８—３９ ［５］张杰，郭丽杰．运筹学课程的改革与数学建模教育［Ｊ］．高等数学研究，２００７（１）：１０３－１０５ ［６］陈修素，丁宣浩，陈义安．基于创新能力培养的《运筹学》课程改革与数学建模实践［Ｊ］．计算数学，２０１２，２２（２）：１０９—１１３
