单纯形法的综述及其应用-[开题报告]

单纯形法及其应用摘要单纯形法是一种主要的解决线性规划问题的方法，它在生活的成本问题、交通选择或规划学术问题等方面得到广泛应用.本文系统的研究了单纯形法的相关概念以及原理.并阐述了用单纯形法解决线性规划问题的步骤与方法及不同方法的特殊性.正确的应用单纯形法解决问题能够提高准确率，从而进行合理的规划安排，使得效果或收益达到期待化或最优化.关键词：单纯形法；单纯形表；最优性The Simplex Method and its ApplicationAbstract:Simplex method is a main to solve linear programming problems, it in life cost, the choice of traffic or academic planning problems are widely used. This paper study the simplex method of the related concepts and principles. It describes the steps and methods to use simplex method to solve linear programming problems, and the different method. Correct application of the simplex method problem solving is able to improve the accuracy, in order to carry out reasonable planning arrangements, makes the effect or income reached expectations or optimization.Keywords:simplex method;simplex tableau;optimality目录1引言 (1)2文献综述 (1)2.1国内外研究现状 (1)2.2国内外研究现状评价 (2)2.3提出问题 (2)3单纯形法的相关概念及原理 (2)3.1线性规划问题解的相关概念 (2)3.2初始基可行解的确定 (4)3.3最优性检验与解的判定 (4)4单纯形法的计算 (5)4.1单纯形表的计算步骤 (5)4.1.1单纯形表 (5)4.1.2计算步骤 (7)4.2人工变量 (9)4.2.1大M法 (10)4.2.2两阶段法 (12)4.3单纯形法的改进——对偶单纯形法 (15)5单纯形法在实际问题中的应用 (17)6结论 (19)6.1主要发现 (19)6.2启示 (19)6.3局限性 (19)6.4努力方向 (20)参考文献 (21)1引言线性规划问题算运筹学中比较早开始研究，在研究过程中发展比较快，在现实生活和学术领域应用比较广泛，研究、解决方法比较成熟的一个不可缺少的分支,随着社会的发展，线性规划也成了人们在解决问题时应用的一种数学方法，它主要应用于数学管理问题的解决中.例如社会经济、交通选择、工业、农业生产等活动中.人们为了提高回报或收益从而对已有的人力、资源、物力等进行合理的的规划安排，使得效果或收益达到期待化或最优化.在解决线性规划问题时，通常应用的方法有图像法和单纯形法等.而应用最多、最有效的方法为单纯形法.单纯形法是一种解决线性规划问题的有效方法，它的应用原理方法为：把线性规划问题的解的可实施部分看做一个n维向量空间Rn中的凸集，由此可得线性规划问题存在最优值那么此最优值只能在凸集的顶点处.既然最优值在顶点处，我们就把所有顶点看做一个集合，先在这个集合里面挑选出一个顶点的值，对它进行判别，判别是否为最优值；如果判别结果不是最优值，那么就用一些方法把这个顶点的值转换为另外一个更可能为最优值的顶点值，依次进行判别，因为顶点有限，所以都可以转换出最终的结果，从而达到解决问题的要求，线性规划问题中没有最优的解也可以利用单纯形法进行计算判别.因此，单纯形法对于解决线性规划有非常重要的地位.单纯形法是一种解决线性规划的方法，只有在线性规划问题中才能更好展现，在本文中，我首先就单纯形法所涉及到的一些线性规划的基本概念、解的定义、专业名词等做出简要说明，然后在典型的线性规划中充分揭示单纯形法的步骤、方法及应用，旨在开阔人们分析线性规划问题的思路，加强人们实施实际问题的能力.2文献综述2.1国内外研究现状现查阅到的参考文献中，分别就单纯形法的综述及其在解决线性规划问题中的应用做出说明.敖特根、章学仁在[1-2]中强调单纯形法在线性规划中的产生与发展的重要性.燕子宗等在[3]中给出了一种新的原对偶单纯形法.郭照庄等在[4-5]中详细阐述单纯形法的基本原理.赵娜、唐帅等在 [6-7]中针对如何使用大M法和两阶段法实现某一线性目标最优化问题作出详细说明.胡运权在文献[8]中针对单纯形法的基本知识和应用做出阐述．文献[9]中，马振华举例说明单纯形法在解决不同线性规划问题中的应用及规律.文献[10]中刘红英等对单纯形法的计算机算法进行了说明．邓成梁等在[11-15]中对单纯形法的迭代步骤与解的讨论进行研究，而且也对单纯形法的具体求解做出的研究.2.2国内外研究现状评价文献[1-15]分别就单纯形法的解题步骤及单纯形法在线性规划问题解题中的意义举例作了说明，文献中主要阐述一种或几种单纯形法在线性规划解题中的应用，没有全面地介绍常用单纯形法在不同线性规划问题的应用及解题步骤，而且文献中对怎样应用单纯形法解决线性规划问题提及甚少，对应用中存在的问题也未给出详细深入的说明，以及遇到现实问题时，单纯形法的具体用法及计算机应用方法未有太多涉及.2.3提出问题单纯形法的在线性规划中有广泛的应用，但是大部分书本只介绍了一些基础知识或讲解线性规划时一带而过.因此，除对解决线性规划问题过程中被一带而过单纯形法作出介绍外，还需要对应用单纯形法解决问题过程中可能遇到的困难、不理解及解决办法作出探讨，包括对使用不同单纯形法的目的、作用、要求作阐述．体会在不同题中单纯形法的不同应用，总结概括以指导方便快捷地解决问题．3单纯形法的相关概念及原理3.1线性规划问题解的相关概念线性规划问题是需要用单纯形法解决的一类问题，所以我们在研究讨论单纯形法时是基于线性规划的基础之上，利用单纯形法使线性规划问题简单、清楚的得出结果是我们的最终目的.一般线性规划问题化为标准式是利用单纯形法求解线性规划问题的基本步骤，对于单纯形法能否顺利得出结果，也有很大联系，在解题过程中，应该谨记变量，目标函数，约束条件的相关要求.线性规划问题的标准形式为：目标函数 1max nj j j z c x ==∑约束条件 ()()11,,..01,,nij j i j ja xb i m s t x j n =⎧==⎪⎨⎪≥=⎩∑ 我们不难看出上式的三个特点： （1）有决策变量：0;1,,j x j m ≥=.（2）有目标函数，：max min 或，一般多用max .两者可以互换，即()max min z z ⇔-. （3）有约束条件，通常为等式，对于“≤”或“≥”型的约束条件，可以添加变量转换成等式约束条件，添加的变量称为松弛变量，在目标函数中，松弛变量相对应的系数为0.例如:123123445154515x x x x x x x +-≤→+-+= 12312352632026320x x x x x x x -+≥→-+-=在利用单纯形法进行计算时，对于线性规划的解的相关概念也需要牢记，在接下来的单纯形法格式中，是以基本概念的求解为基础.线性规划解的概念对于不同元素的换入、换出等都有影响.下面将介绍线性规划问题解的概念:1、可行解:可以满足全部约束条件的解()1,,Tn X x x =，称为线性规划问题的可行解.可行解的集合，称为可行域.2、最优解:最符合题目要求的解，在可行域中，能够使目标函数取得最大值的可行解称为最优解.最优解一定是可行解.3、基:设A 为约束方程组的m n ⨯阶系数矩阵（设n m >），基为A 的满秩子矩阵m m ⨯ 矩阵.4、基可行解:满足变量非负约束条件的基解叫做基可行解，最优解一定是基可行解.5、可行基:对应于基可行解的基称为可行基.3.2初始基可行解的确定我们说单纯形法是一种迭代算法.所以我们在迭代时需要确定每一次迭代的对象，特别是在进行第一次迭代前，我们必须确定好对象才能使单纯形法的迭代顺利进行.第一次迭代的对象我们称为初始基可行解.为了确定初始基可行解，首先要找出初始可行基.找出初始可行基的方法为：（1）有的线性规划问题中能直接观察得到一个初始可行基：()12100010,,.001m B a a a ⎡⎤⎢⎥⎢⎥==⎢⎥⎢⎥⎣⎦（2）如果所有约束条件是“≤”的不等式，在化为标准形式后，可以 重新对变量和变量系数进行编号，得到一个m m ⨯的单位矩阵()12100010,,.001m B a a a ⎡⎤⎢⎥⎢⎥==⎢⎥⎢⎥⎣⎦此时单位矩阵B 可作为可行基.再将标准形式下的约束条件移项为12,,,m x x x 在同一边的等式，再令120m m n x x x ++==== ，可得()1,2,,i i x b i m ==，就此得到一个初始基可行解12,,,,0,,0Tm n m X b b b -⎛⎫= ⎪ ⎪⎝⎭.（3）如果所有约束条件是“≥ ”的不等式，及等式约束情况不存在单位矩阵时，就采用人工造基方法.即对不等式约束中减去一个非负的变量后，再加上一个非负的人工变量；对于等式约束一样加上一个非负的人工变量，就可以得到一个单位矩阵.3.3最优性检验与解的判定线性规划问题解的结果有以下四种情况：唯一最优解、无穷多最优解、无界解和无可行解.在用单纯形对线性规划进行迭代的过程中，对于什么样的情况使得线性规划有解或无解、什么样的情况线性规划达到最优，这就需要进行最优性检验与解的判定.所以对于线性规划的解需要建立判定准则. （1）最优解的判定 设()()0'''12,,,,0,,0Tm X b b b = 为一个基可行解，并且对于一切1,,j m n =+ 都有检验数{}max 1,2,,0j k k j j c z z c j n σ=-=-=≤，则可以判定在该线性规划问题中()0X 为最优解.（2）无穷多最优解的判定 设()()0'''12,,,,0,,0Tm X b b b =为一个基可行解，并且对于一切1,,j m n =+都有检验数{}max 1,2,,0j k k j j c z z c j n σ=-=-=≤，同时又存在某个非基变量的检验数0m k σ+=，则可以判定该线性规划问题有无穷多最优解. （3）无界解的判定 设()()0'''12,,,,0,,0Tm X b b b =为一个基可行解，有检验数0m k σ+>，并且对于1,2,,i m =有,0i m k a +≤ 则判定该线性规划问题有无界解也称之为无最优解.4单纯形法的计算利用单纯形表时，我们首先要了解什么是单纯形表，它有什么样的特点、规则等，其次，因为线性规划问题的多样性，我们针对不同类型的问题给出不同方法的单纯形法帮助我们更快的解决问题，例如人工变量法，对偶单纯形法等.4.1单纯形表的计算步骤用单纯形法求解线性规划问题时，正确、熟练的应用单纯形表能给我们带来更多的便捷计算.下面将介绍单纯形表的计算使用方法以及进一步的讨论单纯形法的其他方法应用.4.1.1单纯形表单纯形表是为了便于展现单纯形法中各种计算关系、使计算过程规范简单不杂乱所设计出的一种计算表格.它的功能、表达方式与增广矩阵类似，接下来，将为大家详细介绍单纯形法中的重要步骤单纯形表.已知线性规划问题的标准形式为1max nj j j z c x ==∑()()11,,..01,,nij j i j ja xb i m s t x j n =⎧==⎪⎨⎪≥=⎩∑ 为了在下面的运算中便于观察进行迭代，我们可以先将上述的线性规划问题的形式改写成增广矩阵的形式1211,112,12,112101000010000110m m nm n m n m m mn mm n zx x x x x ba ab a a b a a bc c c c c +++++-⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦已知z 不参加基变换，所以它与12,,,m x x x 的系数构成一个基，即可以采用行初等变换将12,,,m c c c 变换为零，使对应的系数矩阵为单位矩阵，即1211,112,12,11,11110100001000011000m m n m n m nm m mn m m m m i i m n i in i i i i i z x x x x x b a a b a a ba abc c a c c a c b ++++++===-⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥---⎢⎥⎢⎥⎣⎦∑∑∑ 根据上面的增广矩阵设计出以下单纯形表2mc2mx2mb1,1m m a +2nmnaj j c z -11mm i i i c c a +=-∑1mn i i c c a=-∑此表为初始单纯形表，在基列填入基变量，例如12,,,m x x x ；在B C 列中填入基变量的价值系数，例如12,,,m c c c ，它们与基变量相对应；b 列中填入约束方程组右端的常数；j c 行中填入基变量的价值系数12,,,n c c c ；最后一行为检验数行，对应各非基变量j x 的检验数.每迭代一次可构成一个新的单纯形表. 4.1.2计算步骤对于单纯形法，我们已经对其中的重点，单纯形表做出了基本说明，在我们了解了单纯形表的规格、用法等，现在我们对单纯形表的计算步骤加以说明整理. （1）根据目标方程，约束条件建立初始单纯形表. （2）找出初始可行基，确定初始基可行解. （3）算出非基变量j x 的检验数是否大于零.（4）若检验数全部小于等于零，则可停止计算，若检验数有大于零，取最大的检验数所对应的j x 为换入变量，以min 0i ik ik b a a ⎛⎫> ⎪⎝⎭ 为换出变量，重新列出单纯形法，进行迭代.下面用一个例题对单纯形表的应用做进一步说明.例1 用单纯形表解下面线性规划问题.12max 25z x x =+12121243..28,0x x s t x x x x ≤⎧⎪≤⎪⎨+≤⎪⎪≥⎩解：先将此线性规划问题化为标准式：12345max 25000z x x x x x =++++13141251234543..28,,,,0x x x x s t x x x x x x x x +=⎧⎪+=⎪⎨++=⎪⎪≥⎩ 列初始单纯形表从上表，我们可以看到检验数存在大于零的数，且最大检验数为5，同时计算换出变量为4x ，我们可以列出第二张单纯形表：类似的，可以得出第三张单纯形表：从上表中可看到,得到一组新的基本可行解()()22,3,2,0,0Tx = ，此时19z =在最后的检验数行中已无正值,说明已求出最优解.评注：在本例题中，我们可以清楚看到单纯形表的计算步骤的呈现.计算时经过了以上的四个步骤.4.2人工变量当线性规划问题的约束条件中本身构造不出单位矩阵时，我们就需要加入人工变量，使其线性规划问题能用单纯形法进行运算.现在，我们主要对人工变量的应用具体探讨.若线性规划问题中的约束条件为()()11,,..01,,nij j i j ja xb i m s t x j n =⎧==⎪⎨⎪≥=⎩∑ 现在给每一个约束条件加入一个人工变量，设加入的人工变量分别为1,,n n m x x ++ 可以得到111122111211222222112211,,0,,,0n n n n n n m m mn n n m mn n n m a x a x a x x b a x a x a x x b a x a x a x x bx x x x +++++++++=⎧⎪++++=⎪⎪⎨⎪++++=⎪≥≥⎪⎩,其中1,,n n m x x ++ 为初始基变量，通过单纯形表可以得到一个初始基可行解()()010,,0,,,Tm x b b =，还需要特别注意人工变量是后加入到原来的约束条件中的，所以人工变量是虚拟变量，在计算中应该经过基的变换将人工变量替换出来，在求解结果中，基变量如果不含有非零的人工变量，就表示原线性规划问题有解；基变量中如果含有某个非零人工变量，就表示原线性规划问题无可行解. 4.2.1大M 法大M 法属于人工变量法,针对线性规划问题中约束条件是大于等于形式的情况,不能直接找到初始基可行解（单位矩阵）,采用人造基的方法.在线性规划问题的约束条件中加入了人工变量，我们为了使人工变量对目标函数没有影响，可以给人工变量附加一个极大或极小的系数对人工变量进行控制，使人工变量从基变量中换出.例2 用大M 法求解下面线性规划问题123min 3z x x x =-++12312313123211423..21,,0x x x x x x s t x x x x x -+≤⎧⎪-++≥⎪⎨-+=⎪⎪≥⎩ 解：先将原问题化为标准式为：1234567min 300z x x x x x Mx Mx =-++++++（这里的M 是一个任意大的正数）1234123561371234567211423..21,,,,,,0x x x x x x x x x s t x x x x x x x x x x -++=⎧⎪-++-+=⎪⎨-++=⎪⎪≥⎩ 下面用单纯形表进行计算：由最终单纯形表可得最优解为12345674,1,9,0x x x x x x x =======最优目标函数值2z =- .评注：在本例题中添加了人工变量使得线性规划可以顺利转换为标准形式，使单纯形法更加简化.在一些看似复杂的线性规划问题中，适当的利用大M 法，可以简化运算方法，使思维更加开阔. 4.2.2两阶段法用单纯形法求解线性规划问题时，如果线性规划问题的约束矩阵中有一个单位矩阵，并且0b ≥ ，看似可以得出基本可行解.但是实际操作后却不能得出，因此还需要另外一种寻找初始可行解的方法即两阶段法.第一阶段引入人工变量，构造辅助线性规划问题，求初始可行解；第二阶段从初始基本可行解开始，去除人工变量，用单纯形法求解原问题.例3 用两阶段法求解下面线性规划问题123max 3z x x x =--()12312313211423..2101,2,3j x x x x x x s t x x x j -+≤⎧⎪-++≥⎪⎨-+=⎪⎪≥=⎩解：第一阶段先引入松弛变量45,x x 还需引入人工变量67,x x ，可以构造出辅助问题67max y x x =--()123412356137211423..2101,2,,7j x x x x x x x x x s t x x x x j -++=⎧⎪-++-+=⎪⎨-++=⎪⎪≥=⎩先用单纯形法求解出辅助问题的解求得辅助线性规划问题的最优解()0,1,1,12,0,0,0TX *= 现在人工变量全部换出，第一阶段运算结束，进入第二阶段，用单纯形表求解原问题第二阶段结束，从单纯形表中可以得出原线性规划问题的最优解为()4,1,9,0,0TT x = 可以算出目标函数的最优值为2z =.评注：两阶段的方法在解决比较难的、利用一次变换无法求出结果的线性规划问题中非常实用.但是，通过上题，可以发现两阶段法的构造运算也需要大家对单纯形法有很深了解才不容易出错.4.3单纯形法的改进——对偶单纯形法在前面一章中介绍的单纯形法是从一个欠优化的基本可行解开始，在求解过程中保持解的可行性并且逐渐完善解的优化性的方法.对偶单纯形法却是从一个超优的不可行解开始，在求解过程中保持解的优化性并且逐渐完善解的可行性的方法.本节主要以例题分析的形式了解对偶单纯形法的应用步骤.例4 给出线性规划的数学模型123min 15245z x x x =++2312312362..521,,0x x s t x x x x x x +≥⎧⎪++≥⎨⎪≥⎩ 以上线性规划问题的对偶标准化模型可以写为12345max 1524500z x x x x x *=---++()234123562..52101,,5jx x x s t x x x x x j ⎧--+=-⎪---+=-⎨⎪≥=⎩ 比较上面线性规划问题及它的对偶问题的特征，可以发现：在对偶单纯形法中，现行解超优但是不可行，所以先选择最不可行的基变量换出，也就是说换出变量是取负值且绝对值最大的基变量，可以列出从表格中可以看出用对偶单纯形法求解时，当约束条件为大于等于时，可以不必引入人工变量，使计算得到简化.评注：本题完整、充分的展示了对偶单纯形法的优点，在原问题利用单纯形法困难时，可以利用对偶单纯形法使计算简便.5单纯形法在实际问题中的应用利用数学计算工具来求解单纯形法中的问题，其价值和推广是可观的，不仅可以提高计算速度还可以保证计算的准确性.用计算机辅助运算单纯形法的方法有利用Excel 软件或利用MATLAB 实现. 案例分析：一个食堂经理Jick 想降低食堂成本，他发现在原材料中蚕豆和红薯为主要配料。

运筹学单纯形法
运筹学单纯形法，又称单纯性法，是一种用于求解线性规划问题的数学方法，它在运筹学中发挥着重要作用。

它主要应用于决策及资源分配问题，可以帮助决策者更好地把握资源的优化配置，并寻求最优解。

单纯性法是以线性规划问题作为理论基础，它是将该问题转化为一系列形如Ax=b的线性方程组的运筹学方法。

在这个方程组通过调整方程中的系数和右面常数而变换为形如Cx≤d的不等式形式，而这种不等式系统称为单纯性约束条件。

单纯性法从不等式中寻找一系列基向量，并通过改变基向量来实现改变不等式的求解方程之间的关系，从而求出最优解的问题。

传统的单纯性法分为有界单纯性和无界单纯性两种情形。

无界单纯性以简单费用曲线方法、扩展的简单费用曲线方法和增广次数法三大类。

有界单纯性主要是对对角单纯性和非对角单纯性这两类单纯性系统分别使用不同的方法进行求解。

单纯性求解方法在线性规划问题求解中具有重要应用，它能通过求解线性规划问题中的一系列互不相关的子问题来求出最优解。

使用该方法，可以以最少的成本达到最优的收益，它包括费用最低优化、网络流优化、全格研究和数学优化模型等。

单纯形优化法的应用摘要：介绍单纯形法，并将其应用于高速卷烟胶的研发，进而对该方法的使用及寻优过程进行探讨。

关键词：单纯形优化法；高速卷烟胶绪论单纯形优化法又称为单纯形法(Simplex)。

1962年W．Spendley等首先提出了基本单纯形优化法，并将其应用于化学领域。

1965年J．A．Nelder等提出了改进单纯形优化法，变固定步长为可变步长，并引入了反射、扩大与收缩规则，加速了优化过程。

单纯形法是一种动态寻优方法。

它能在交互作用复杂、因素较多的场合使用，对实验有全面优化的效果，克服了单因素优化法无法考虑各因素间的交互影响、准确性低、工作量大的缺点。

它能在实验次数较少的情况下，快速地找出接近最佳分析条件组合，综合优化性能指标。

1、理论部分1.1单纯形优化法的定义所谓单纯形优化法是指首先根据n个因素组成初始单纯形，然后逐步调整到最佳状态的寻优方法。

初始单纯形是指一个n+l个顶点构成的凸形多面体，对其各个顶点按照一定规则进行试探性搜索，其试验点根据试验情况逐步调整到最佳条件，是一种动态调优的方法。

改进单纯形是在基本单纯形的基础上，调整反射距离，即将固定步长改为可变步长，加速新试验点的优化过程，同时又满足一定的精度要求。

1.2基本思想若实验因素有两个，则在二维空间中，单纯形为三角型，就是说须确立三个试验点来完成初始单纯形的建立。

图a中三角型为初始单纯形，P A、P B、Pc为实验者最初确定的实验点。

（1）若由实验结果得出P A点收率最高，Pc点最低。

接下去的做法是去掉Pc点，将P B和P A的中点P E与点Pc连接并延长至P D，使P E P C=P E P D，P D即是新的试验点。

P D、P B和P A三点又构成了一个新的单纯形，这样就实现了单纯形的推移，随之实验条件也不断改变，直到收率满意为止。

这里P D点称为Pc关于P E的反射点，这种做法称作反射。

（2）若反射点P D的试验结果Y D小于最坏点Pc的试验结果Yc，即Y D< Y C，则用次坏点P B进行P B关于新单纯形P B P A P D反射，反射点为P D’，若Y D’>Yc，说明反射方向正确，这时新试验点P D'可做“收缩”处理，0<α<1。

运用单纯形法最优化气相色谱操作条件单纯形是指多维空间的一种凸图形，它的定点数仅比空间的维数多1。

例如，二因素单纯形是一个三角形，三因素空间的单纯形为一四面体。

n 个因素空间的单纯形是n+1个点构成的超多面体。

自从从1962年Spendley 等首先将基本单纯形发（BSM ）引入化学领域手，不少学者从不同角度对单纯形优化方法做了进一步研究，相继提出了改进单纯形法（MSM ），超改进单纯形发（SMS ）、控制加权形心超改进单纯形法（CWCSMS ），加权形心单纯形法（WCM ）、体积不变单纯形法、超改进控制加权形心单纯形法（SMCWC ）和新改进单纯形优化方法（NMS ）[1]，上述各种方法各有特点。

在目前气相色谱中应用最多的是改进单纯形法（MSM ）[2]。

下面我们主要应用改进单纯形法对以柱温为主要操作条件的气相色谱进行优化。

先在初始单纯形BNW ，如图1，的三个顶点所对应的条件下进行实验，所得到的响应以B 点最好，N 点次之，W 点最差。

图1 MSM 单纯形的移动 为了寻找最佳点，我们向最差点的反对称方向进行搜索。

以P 为除W 点以外所保留各点的重心（此处即BN 的中点），在W P 的延长线上取一新点R ，使得： ()R P P W α=+- (1-1) 式中，α称为反映系数，一般取一；R 称为W 点于P 的反射点。

此步骤称为“反映”。

在R 点进行实验，其测得的响应值有三种可能。

1. 在R 点的响应比B 点的响应更好，则“扩大”产生新点E,使 ()E P r P W =+- (1-2) 式中，r 称为扩大系数，一般取r ＝1.2～2.0，当r ＝2， 2()E P P W =+- (1-3) 若E 点的响应比B 点的响应好，则保留E ，以BNE 为新的单纯形再开始，如果E 点的响应不比B 的好，扩大失败，则以BNR 为新的单纯形开始。

2. 若R 点的响应处于B 点和N 点的响应之间，既不扩大也不缩小，则以BNR 为新单纯形再开始。

单纯形法1. 什么是单纯形法单纯形法（Simplex Method）是一种数学优化方法，用于在线性规划问题中寻找最优解。

其基本思想是通过不断地在可行解空间中移动，逐步优化目标函数的值，直到找到最优解。

单纯形法是由美国数学家乔治·达内策在20世纪40年代开发的，成为线性规划问题求解的一种经典方法。

2. 单纯形法的基本原理单纯形法的基本原理是通过构造一系列的顶点组合，这些顶点组合构成了可行解空间的一个多面体，称为单纯形。

每次移动都是在单纯形的边界上进行，直到找到最优解。

2.1 线性规划问题的标准形式在使用单纯形法求解线性规划问题之前，首先需要将问题转化为标准形式。

线性规划问题的标准形式包括以下特征：•最大化目标函数或最小化目标函数•约束条件为等式或不等式•决策变量为非负数2.2 单纯形法的步骤单纯形法的求解步骤如下：1.初始化：将线性规划问题转化为标准形式，并找到初始可行解。

2.检验最优性：计算当前基可行解对应的目标函数值，判断是否达到最优解。

3.寻找进入变量：通过计算目标函数的系数与约束条件中的系数之比，找到使目标函数值最大（或最小）增长的变量。

4.寻找离开变量：从进入变量所属列中选择合适的变量离开基，使得新的基可行解依然满足约束条件。

5.更新基：将进入变量换入基，将离开变量换出基，得到新的基可行解。

6.重复步骤 2-5，直到找到最优解或判断无界。

2.3 单纯形表在单纯形法的求解过程中，通过使用单纯形表（Simplex Table）来记录每一步的计算结果和变量的取值。

单纯形表是一个矩阵，包含基变量、非基变量、目标函数系数、约束条件左边的系数等信息，方便进行计算和调整。

3. 单纯形法的优缺点3.1 优点•单纯形法是一种简单直观的求解线性规划问题的方法，容易理解和实现。

•单纯形法对于规模较小的问题，可以得到精确的最优解。

•单纯形法可以处理带有不等式约束的问题，适用范围广。

3.2 缺点•单纯形法在解决大规模问题时，计算复杂度较高，效率较低。

线性规划中的单纯形法研究线性规划是一种常见的优化问题求解方法，而单纯形法则是其中最重要且被广泛应用的算法之一。

本文将对线性规划中的单纯形法进行研究，并探讨其应用和优化。

一、线性规划简介线性规划是一种以线性约束条件和线性目标函数为特征的优化问题，其目标是在满足一系列约束条件的前提下，找到使目标函数值最大或最小的决策变量取值。

线性规划广泛应用于生产、运输、资源分配等实际问题中，具有重要的理论和实践价值。

二、单纯形法原理单纯形法是由乔治·丹齐格于1947年提出的，是一种通过逐步优化目标函数值的方法。

其基本原理是通过在可行域内不断移动，以找到目标函数值的最大或最小值。

单纯形法的核心步骤包括：1. 构建初始单纯形表：将线性规划标准形式转化为单纯形表，其中包括目标函数、约束条件以及决策变量等。

2. 选择主元素：在单纯形表中选择一个入基变量和一个出基变量，并进行主元素系数比对，以确定如何更新单纯形表。

3. 更新单纯形表：通过主元素系数比对的结果，对单纯形表进行更新，并计算新的基变量取值。

4. 判断是否达到最优解：通过判断单纯形表中的目标函数系数是否满足最优性条件，决定是否达到最优解。

若满足最优性条件，则停止迭代，得到最优解；否则，返回步骤2，继续迭代。

三、单纯形法的优化尽管单纯形法在解决线性规划问题中非常有效，但也存在一些优化方法可以提高其求解效率。

以下是一些常见的单纯形法优化技巧：1. 人工变量技巧：将含有不等式约束的线性规划问题转化为标准形式时，引入了人工变量。

而通过合理选择人工变量的初始值，可以减少单纯形法的迭代次数，提高求解效率。

2. 大M法：在单纯形法中，人工变量的引入会导致初始基可行解的搜索空间很大，从而增加迭代的次数。

大M法通过引入一个大的M值来改变迭代的方向，将大M法用于单纯形法求解可以减少迭代次数，提高计算效率。

3. 双目标法：当线性规划问题存在多个优化目标时，可以利用双目标法将多个目标合并为一个目标，从而改进单纯形法的求解效果。

毕业论文文献综述数学与应用数学单纯形法的综述及其应用一、 前言部分（说明写作的目的，介绍有关概念、综述范围，扼要说明有关主题争论焦点）1.写作目的本文主要在于介绍单纯形法的历史背景，基本计算方法，改进的计算方法，以及单纯形法的应用．目的在于对单纯形法的历史背景，计算方法等进行综述，并总结单纯形法在生活各个领域的应用，单纯形法是求解线性规划问题很有效的方法，通过对单纯形法的进一步了解，最后提出一实际问题利用单纯法进行分析求解．2.有关概念LP 问题的一般形式[1]()1122. Max min n n ob Z c x c x c x =+++L()()()1111221121122222112212..: ,,,0 n n n n m m mn n m n a x a x a x b a x a x a x b s t a x a x a x b x x x +++≤≥⎧⎪+++≤≥⎪⎪⎨⎪+++≤≥⎪⎪≥⎩L L LL L 线性规划问题的标准型为[2]()()()11221111221121122222m112212min a a s.t.a 01,2,,,,,n n n n n n m mn n m j n S c x c x c x S x a x a x b x a x a x b x a x a x b x j n x x x =+++⎧+++=⎪+++=⎪⎪⎨⎪+++=⎪⎪≥=⎩L L L L L L 为目标函数（1）为决策变量 其矩阵形式为min s.t.0S CXAX b X ==⎧⎨≥⎩（2）其中，()12,,,n C c c c =L ，决策向量()()1212,,,,,,,T T n m X x x x b b b b ==L L ．A 为约束条件中的系数矩阵, 即111212122212n n m m mm a a a a a a A a a a ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦L L M M M M L 本文除了介绍线性规划问题的一般形式、标准形式和矩阵形式以外还列举了一些定义. 定义1[3]：设矩阵A 的秩为m ，矩阵B 是A 中的一个m 阶满秩子方阵，则B 为一个基矩阵．矩阵A 中剩余元素组成的子阵为N ,即[]A BN =.把x 的分量相应地分成两部分，记成B x 和N x ，B x 的分量与B 的列对应，称为基变量；N x 的分量与N 中的列对应，称为非基变量．在约束Ax b =中令所有的非基变量取值为零时，得到解10B N x B b x x -⎡⎤⎡⎤==⎢⎥⎢⎥⎣⎦⎣⎦，称为相应于B 的基本解．定义2[3]：基本解得基变量都取非负值时，即满足10B x B b -=≥的基本解为基本可行解．定义3[4]：满足式（1）各约束条件的解()12,,,T n X x x x =L 称为可行解.全部可行解的集合称为可行域.目标函数1min n j j j Z c x ==∑达到最大值的可行解称为最优解.定义4[4]：设A 为约束方程组1(1,...,)n ij j i j a x b i m ===∑的m n ⨯阶系数矩阵，设(n m >),其秩为m ，B 为矩阵A 中的一个m m ⨯阶的满秩子矩阵，称B 为线性规划问题的一个基.不失一般性，设11111...(,...,)...m m m mm a a B a a αα⎡⎤⎢⎥==⎢⎥⎢⎥⎣⎦M M B 中每一个向量(1,..,)j j m α=称为基向量；与基向量j α对应的变量j x 称为基变量.基变量以外的的变量称为非基变量.定义5[4]：在约束方程组1(1,...,)n ijj i j a x b i m ===∑中，令所有非基变量12...0m m n x x x ++====.此时约束方程组有唯一解()12,,,TB m X x x x =L .将此解加上非基变量取０的值，有()12,,,,0, 0m X x x x =L ，称X 为线性规划问题的基本解.基本解总数不超过m n C 个.3.综述范围通常，求解LP 模型时，常用基本单纯形方法、大M 法、两阶段法等，所以在文献[5-8]具体介绍了求解线性规划的单纯形法的一些计算方法．根据对模型中是否存在单位基矩阵、存在怎么样的基矩阵等特征的判断来选择方法或判断解的存在与否等情况．这就是说，在求解线性规划的单纯形法中，初始基(矩阵)的确定是一个基本问题．通常使用大M 法和两阶段法，通过人工构造，人为地在系数矩阵中形成一个单位矩阵作为初始基，再进行单纯形法的迭代[9]．由于越来越多的领域借助于线性规划来做出最优决策，完善线性规划理论及其有效解法已成为重要研究课题．单纯形法作为求解线性规划问题较实用而有效的算法已在实际中得到广泛应用．本文在文献[10-11]简述关于单纯形算法的讨论、优化设计与实现，分析了单纯形算法的主要特点．最后本文例举一些单纯形法在实际问题应用例子来说明单纯形法是处理运筹学模型的一种重要方法．4.主题的争论各种资源的最优配置已成为当今节约型社会的研究热点．它广泛应用于国防、科技、工业、农业、交通运输、环境工程、教育、经济及社会科学等领域，是指在一定的人力、物力、财力等资源条件下，如何合理利用这些资源完成最多任务或得到最大效益的方法．线性规划的资源最优配置是研究在一组线性约束之下，目标线性函数的最小值或最大值问题[3]．Dantzig 在1947年提出了求解线性规划问题的单纯形算法．单纯形算法是寻找最优基本可行解的一种行之有效的算法[12].二、主体部分（阐明有关主题的历史背景、现状和发展方向，以及对这些问题的评述）（一）历史背景单纯形法是求解线性规划问题的通用方法．它是是美国数学家G.B.丹齐克于1947年首先提出来的．它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到．顶点所对应的可行解称为基本可行解．单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行．因基本可行解的个数有限，故经有限次转换必能得出问题的最优解．如果问题无最优解也可用此法判别．（二）现状1.基本定理下面主要介绍一下在单纯形法的综述及其应用中所涉及的一些基本定理.定理1[3]：若式（1）存在有界最优解，则必从基本可行解中得到．定理2[9]:若矩阵A经过有限次初等行（列）变换变换成矩阵B则，A的行（列）向量组与B的行（列）向量组等价，而A的任意k个列（行）向量与B中对应的k个列（行）向量有相同的线性相关性．定理3[4]:若线性规划问题存在可行解，则问题的可行域为凸集.定理4[4]:线性规划问题的基本可行解X对应线性规划问题可行域的顶点.定理5[4]:若线性规划问题有最优解，一定存在一个基本可行解是最有解.2．单纯形法的计算（1）计算步骤单纯形表X列依次标明各方程的基变量；BB C 是基变量相应的价值系数，它们是与基变量相对应的；b 列是约束方程组右端的常数；j c 行是基变量的价值系数；i θ列的数字是在确定换入变量后，按θ规则计算后填入；最后一行称为检验数行，对应各非基变量i x 的检验数是,1,1,2,...,m j i i j i c c a j n =-=∑．现在把单纯性法的的计算步骤归纳如下： 第一步 对于一个已知的可行基12B ,,...,)j j jn p p p =（，写出B 对应的典式以及B 对应的基可行解(0)x ，(0)110200(,,...,)T B m x B b b b b -==第二步 检查检验数，如果所有检验数 0j λ≤ （j=1,2,…,n ）则(0)x 便是最优解，计算结束，否则转下一步．第三步 如果有检验数0r λ>，而112(,,...,)0T r r r mr B p b b b -=≤，则问题无最优解，计算结束，否则转下一步．第四步 如果有检验数0r λ>，且12(,,...,)T r r mr b b b 中有正数，则取r x 为进基变量（若有多个正检验数，可任选一个，一般来说选取最大的检验数有利于提高迭代效率），并求最小比值00min i s ir srb b b b ⎧⎫=⎨⎬⎩⎭ 由此来确定js x 为离基变量（若上述最小比值同时在几个比值上达到，则选取其中下标最小的变量为离基变量），然后用r P 代换js p 得新基B ，再接下一步．第五步 求出新基B 的典式（计算或直接通过初等行变换来实现）以及B 对应的基可行解，1(1B 10200B (,,...,)Tm x b b b b -==） 然后，以B 取代B ，(1)x 取代(0)x ，返回第二步[13]．（2）单纯形法的进一步讨论人工变量：大M 法和两阶段法为了解线性规划问题 min .0CX s t AX b X ⎧⎨=≥⎩ 需要一个初始基可行解，为此常常借助于大M 法或两阶段法． 大M 法：在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，为此假定人工变量在目标函数中的系数为（-M ）（M 为任意大的正数），这样目标函数要实现最大化时，必须把人工变量从基变量换出．否则目标函数不可能实现最大化．在许多线性规划问题中，引进松弛变量化成标准形式后，约束条件方程组的系数矩阵并不含m 阶单位矩阵，这样就给单纯形解法的换基迭代带来了困难，为了很快找到第一个可行基，在利用单纯形法求解时，首先要在线性规划问题中引入人工变量，把问题变为约束方程组的系数矩阵中含有单位阵，用以作为人造基，然后再按照单纯形法进行换基迭代，求得最优解或判定无最优解．这种方法就称为两阶段法．第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化．如11111122111211222222m112212min 0...0a a s.t.a ,,...,0n n m nn n n n n n m mn n n m m n m x x x x x a x a x x b x a x a x x b x a x a x x b x x x ω++++++=+++++++++=⎧⎪++++=⎪⎪⎨⎪++++=⎪≥⎪⎩L L L LL 然后用单纯形法求解上述模型，若得到0ω=，这说明原问题存在基可行解，可以进行第二段计算．否则原问题无可行解，应停止计算．第二阶段：将第一阶段计算得到的最终表，除去人工变量．将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表．大M 法与两阶段法都是从寻求线性规划问题的一个初始可行基引入的．从形式上看，它们是两种不同的方法，但在本质上是一致．3．单纯形法的算法（1）改进单纯形算法通常使用大M 法和两阶段法，通过人工构造，人为地在系数矩阵中形成一个单位矩阵作为初始基，再进行单纯形法的迭代．这样，往往无意中扰乱了思想主线，增加了计算量．特别对于人工计算显得运算操作繁杂而偏离了主体，在理解和教学中常常带来不便．通过对单纯形法求解法的实质的分析和认识，提出了基于矩阵初等变换初始可行基的获得方法，进而得到基于单纯形法的求解线性规划模型的直接方法使单纯法的运用简单明白．利用这种确定初始可行基的方法求解线性规划问题时，首先，对线性规划模型()2的系数增广矩阵进行上述的初等行变换而得到r r ⨯阶的初始可行基()r m ≤，接着，将所得初始可行基安排入单纯形表，然后，进行单纯形表的表上作业程序．这样做的优点不仅在于可以给出初始可行基()r m =，而且可以方便地发现不独立的约束()r m <，并将其提前剔除，以减少单纯形法的计算量．具体步骤为:步骤 1 对增广矩阵B 施行一系列的初等行变换，并始终保持可行性(即：b 列非负)，直到B 中含有单位矩阵；这里需要注意的是当变换到可以使某一行元素全部为0时，说明约束方程组不独立，B 可以降维为()()11m n -⨯+，那么，所得到的单位矩阵也就是()()11m n -⨯+阶的，并非一定要得到B 的m m ⨯阶的单位矩阵作为基．步骤 2 将步骤1的结果安排到一个单纯形表中，并以B 中的单位矩阵的列所相应的变量为基变量而得到初始单纯形表；步骤 3 在步骤2的所得的单纯形表上按照通常的单纯形表上作用法进行求解．需要说明的是，在步骤1中完全可以不用第一类初等行变换(交换任两行的位置)，而只用第二、三类初等行变换就可以实现．该方法的优势在于思想清晰，方法简明，计算量减小．有了初始可行基，就可从这个可行基相应的基本可行解出发进行换基迭代，从而，求得目标函数的最优解或判断其无最优解[9]．（2）计算机算法利用数学计算工具来解决单纯形法中计算的难题，其应用价值和推广价值是可观的，不仅可以提高计算速度，而且可以大大提高计算的准确性．求解思路：首先把它变为如下(左式) 标准形式:11221111221121122222m112212max a a s.t.a ,,...,2n n n n n n m mn n m n Z c x c x c x x a x a x b x a x a x b x a x a x b x x x =++++++=⎧⎪+++=⎪⎪⎨⎪+++=⎪≥⎪⎩L L L L L 1231112131121222322123...0.........n n n m m m mn m c c c c a a a a b p a a a a b a a a a b ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦M M 然后对p 进行标准化, 记[]123...T i i i i mi a a a a a =,如果i a 是只有一个分量为1 的单位向量，那么把p 第一行中的i c 通过矩阵变换， 变成0， 标准化完成.．标准化的目的是将第一行中的系数12,,...,n c c c 变为检验数, 其中非基变量系数均为0，基变量的系数则未必为0．接着对p 进行变换, 首先在p 矩阵的第一行第1到第n 个分量中找出一个最大数，如果这个最大数不大于0 ，则不用进行再次迭代，直接得到最终变换矩阵g ．反之，用k 记下最大数所对应的列.．然后进行判断： 如果p 的第k 列的第2 至第m 个数全都小于或等于0 ，那么此线性规划问题无界，迭代结束．反之， 用p 的最后一列的第2 至第m 个分量分别除以第k 列对应的数，如果碰到除数小于或等于0 则跳过. 在所得结果中找出最小的那个数，用j 记下该数所对应的行．于是得到主元素(,)p j k 接下来是对第j 行进行行变换，将P( j , k) 变为1．然后对其他行进行行变换，使p 矩阵的第k 列的其他分量都变为0 ， 于是第一轮变换结束．接下来回到变换过程的开始，重复迭代过程至到跳出迭代过程为止，最后对结果矩阵进行智能分析． 其中需要人工进行的步聚是构造计算矩阵p 和分析迭代结果两步， 以使求解过程比较简便且可靠性高[14]．4．单纯形法的应用一个经济、管理问题凡满足一下条件时，才能建立线性规划的模型．（1）要求解问题的目标函数能用数值指标来反映，且为线性函数：（2）存在多种方案及有关数据：（3）要求达到的目的是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述．一般满同时足上面几个条件的实际生活中的难解问题都可以用线性规划问题来解决．所以越来越多的领域借助于线性规划来做出最优的决策．单纯形法在实际中的应用最常使用于资源的配置．人力、时间和物质资源的优化配置问题是制定企业生产计划时考虑的重要问题，线性规划模型可以考虑各类资源的变动对其造成的影响并寻求最佳方案.在企业生产和经济管理等领域中，人们常会遇到这样的问题，如何从一切可能的方案中选择最好、最优的方案，在数学上把这类问题称为最优化问题．如何解决这类问题，在当今商品经济的环境下，是一个关系到国计民生的重要问题．线性规划是理论和方法都比较成熟，并具有广泛应用价值的一个运筹学分支．如果一个问题的限制条件可以写成某些决策变量的线性方程组或线性不等式组，目标可以写成决策变量的线性函数，那么这个问题的数学模型就是线性规划问题．线性规划法是研究如何将有限的人力、物力、设备、资金等资源进行最优计划和分配的理论方法．线性规划是企业生产过程中决策制定的理论依据，决策的合理与否直接影响到企业的经济效益，文献[15]介绍了线性规划理论，阐述了线性规划函数中各要素以及各变量的变化对分析造成的影响，通过单纯形法案例进行了计算，针对大型、复杂的模型，需要选择更为有效的手段来进行计算．能源紧缺是人类社会面临的重要问题．现代城市轨道交通系统通过轨道上方的直流接触网供电，因电动车组往往牵引功率巨大，需消耗大量电能，因此，有效利用牵引能源至关重要．单列车牵引策略优化对于节约牵引能耗具有极其重要意义.在文献[16-17]讨论了单纯形优化算法在城市轨道交通列车惰行点搜索方面的应用，列车运行因受多重因素影响，确定必要的惰行起点在实际情况的约束下并不容易．通过分析列车站内运行惰行点搜索特点、约束条件及寻解空间等．详细介绍了二维空间中单纯形法寻找合适列车惰行点的实现过程．借助于单列车仿真系统的帮助，通过问题的寻优结果分析，研究了这种启发式搜索方法在确定惰行点方面的可行性和性能表现．借助于单纯形法在城市勒道交通列车站问运行惰行点搜索方面的应用，在综合考虑运行时间和能量消耗不同要求的情况下，应用该搜索方法得到的惰行点可以为优化列车运行提供满意解．启发式的搜索方法，通过较低的迭代次数，为列车运行的惰行点搜索提供了解决方案．然而，在站间运行时，首先要关注两站之间的距离有没有足够的空间容纳多个惰行点，从而合理选择惰行点数量．从应用角度看，根据整条线路的总运行时间搜索多个站点间的惰行点，会使搜索更复杂．这将在今后进一步研究[16]．三、总结部分（将全文主题进行扼要总结，提出自己的见解并对进一步的发展方向做出预测）线性规划是运筹学的一个重要分支，早在20世纪30年代末，前苏联著名的数学家康托洛维奇就提出了线性规划的数学模型，越来越来受到人们的重视．而后于1947 年由美国数学家G. B. Duntzg提出一般线性规划问题的求解方法——单纯形法，它是线性规划问题的通用解法．从而使得线性规划的应用领域更加的广泛．线性规划这一学科也因此开始形成并迅速地发展起来．单纯形方法与经典分析的方法很不相同，它利用了矩阵的初等变换，通过部分枚举的方法来寻求线性规划问题的最优基可行解，从而求得值．由于这种方法运算简单又有规则，且适用性广泛．所以它的应用迅速得到发展，根据它而编制的程序已在一些计算机上开发实现．值得指出的是，尽管单纯形法避开了经典极值问题常用的微分法，但是单纯形法的最优性条件仍可用微分法导出[18]．四、参考文献（根据文中参阅和引用的先后次序按序编排）[1]田学民.利用单纯形法解线性规划问题的机理[J].中国科技论文在线,2010.[2]贺学海.单纯形法解决LP问题的研究[J].沈阳师范大学报(自然科学版).2010,28(1):14-16.[3]王东雷.基于单纯算法的优化设计与实现[J].安徽农业科学.2007,35(36):11727-11728.[4]蔡海涛等.运筹学[M].湖南长沙.国防科技大学出版社.2003.[5]张毅.谈两阶段法与大M法的统一处理方法[J].陕西理工学院学报(自然科学版).2009,25(2):85-86.[6]白岩.线性规划中两阶段法德简便计算法[J].长春师范学院学报自然科学版).2005,24(5):1-3.[7]Hamdy A.Taha.运筹学(英文版) [M].北京:人民邮电出版社.2007.[8]拉塞尔C.沃克.数学规划导论(英文版)[M].北京.机械工业出版社.2005.[9]申卯兴,许进.求解线性规划的单纯形法的直接方法[J].华东科技大学.2007,43(30):94-96.[10]高引民,杜晓马.关于单纯形算法的讨论[J].太原机械学院学报.1994,15(1):70-75.[11]陈英霞,朱维钧.关于单纯形算法的两点思考[J].怀化学院学报.2008,11(11):26-27.[12]王东雷,张耀中.一种改进的单纯算法实现及其应用[J].安徽农业科学.2007,35(35):11601-11602.[13]张干宗.线性规划[M].武汉.武汉大学出版社.2004.[14]毕春丽,曾强,王荣文.线性规划问题中单纯形法的计算机求解[J].焦作工学院学报(自然科学版).2002,21(6):472-474.[15]王树祥,武新霞,卜少利.线性规划在企业生产计划中的应用及模型的建立和求解[J].中国电力教育.2007,21:195-197.[16]赵亚辉,朱琴跃.基于单纯形法的城轨列车惰行点搜索[J].同济大学(自然科学版).2010,38(1):81-85.[17]赵亚辉,谢维达.单纯形法在城轨列车惰行点搜索中的应用[J].同济大学(自然科学版).2009,45(14):217-220.[18]毛东明,许风.单纯形法最优性条件的经典证明[J].辽东学刊(自然科学版).1994, 3:12-14.。

单纯形法综述zy1415104-曹文亮单纯形法是1947年由George Bernard Dantzing(1914-2005)创建的，单纯形法的创建标志着线性规划问题的诞生。

线性规划问题是研究在线性约束条件下，求线性函数的极值问题。

然而，对这类极值问题，经典的极值理论是无能为力的，只有单纯形法才能有效解决这类极值问题的求解。

线性规划是数学规划的一个重要分支，也是最早形成的一个分支，线性规划的理论与算法均非常成熟，在实际问题和生产生活中的应用非常广泛；线性规划问题的诞生标志着一个新的应用数学分支——数学规划时代的到来。

过去的60年中，数学规划已经成为一门成熟的学科。

其理论与方法被应用到经济、金融、军事等各个领域。

数学规划领域内，其他重要分支的很多问题是在线性规划理论与算法的基础上建立起来的，同时也是利用线性规划的理论来解决和处理的。

由此可见，线性规划问题在整个数学规划和应用数学领域中占有重要地位。

因此，研究单纯形法的产生与发展对于认识整个数学规划的发展有重大意义。

单纯形法是从某一基可行解出发，连续地寻找相邻的基可行解，直到达到最优的迭代过程，其实质是解线性方程组。

概述：根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。

使目标函数达到最大值（或最小值）的可行解称为最优解。

这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。

求解线性规划问题的目的就是要找出最优解。

最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。

无最优解与无可行解是两个不同的概念。

无可行解是指原规划不存在可行解，从几何的角度解释是指线性规划问题的可行域为空集；无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。