单纯形法（simplicial method）是求解线性规划问题的一种行之有效的方法。其基本思想是从一个基本可行解出发，求一个使目标函数值有所改善的基本可行解；通过不断改进基本可行解，力图达到最优基本可行解。

单纯形法起源于线性规划问题的研究，20世纪30年代末期，苏联数学家康托罗维奇（Leonid Kantorovich）和美国经济学家里昂惕夫（Wassily Leontief）分别在制造业、经济学领域做出了线性规划的初次尝试，但他们的工作没有受到重视。第二次世界大战期间，美国空军成立了研究小组来研究资源优化问题，1947 年，数学家丹齐格（George Bernard Dantzig）推导得出线性规划的标准形式和解决线性规划问题的单纯形法，并于两年后在最优化的第一次会议上做了报告。后来，计算机学家约翰·冯·诺依曼（John von Neumann）寄予了他肯定和支持，并提出了线性规划的对偶形式。但是，随着涉及更多变量复杂问题的尝试，对于单纯形法的改进需求越来越迫切。1974年，维利·勃兰特（R.G. Bland）通过提出一种简便的规则解决了最优解的循环问题，周勤学等学者针对该法则给出了改进的形式。2000年，美国物理学会和计算机协会推举单纯形法为“本世纪前十名的算法之一”，进一步肯定了其应用价值，该方法也许会适用于更大的模型。

单纯形法的求解可以通过变换单纯形表来实现，而对于选取初始可行基这一关键步骤，通常采用大法和二阶段法这两种方法。单纯形法经过改进，可以节省计算机的储存量和计算量，提升求解效率。而对于求解模糊化的线性规划模型，也需对方法进行相应的调整。此外，单纯形法在现实世界中应用广泛，如在工程学中，通过建立土石方动态调配模型，采用单纯形法求出最优调配方案，可以满足施工强度在填筑、开采、运输等方面的各项要求。

单纯形法起源于线性规划问题的研究，20世纪上半叶，社会生产力飞速发展，资源分配工作成为企业管理面临的一大难题。20世纪30年代末期，苏联数学家康托罗维奇（Leonid Kantorovich）和美国经济学家里昂惕夫（Wassily Leontief）分别在制造业以及经济学领域做出了线性规划的初次尝试，但他们的工作没有受到重视。第二次世界大战期间，美国空军成立了研究小组来研究资源优化问题，1947 年，数学家丹齐格（George Bernard Dantzig）推导得出线性规划的标准形式和解决线性规划问题的单纯形法，并于两年后在最优化的第一次会议上做了报告。后来，计算机学家约翰·冯·诺依曼（John von Neumann）寄予了他支持和肯定，并提出了线性规划的对偶形式。

但是，随着涉及更多变量复杂问题的尝试，对于单纯形法的改进需求越来越迫切。1952年，丹齐格（Dantzig）和奥顿（Orden）提出了对偶问题相应的定理，后来，丹齐格（Dantzig）于1954年给出了改进的单纯形法。20世纪70年代之后，人们对于线性规划计算的时间复杂性进行了研究，克莱（Klee）和米尼什（Minth）指出单纯形法是具有指数时间复杂度的。1974年，维利·勃兰特（R.G. Bland）通过提出一种简便的规则解决了最优解的循环问题。后来，随着电子计算机的进步，莱斯大学的比克斯比（Bob Bixby）的CPLEX软件、IBM的佛利斯特（John Forrest）的OSL软件，提高了单纯形法的求解速度。1989年，周勤学等学者针对维利·勃兰特法则给出改进的形式。2000年，美国物理学会和计算机协会推举单纯形法为“本世纪前十名的算法之一”，进一步肯定了其应用价值，该方法也许会适用于更大的模型。

线性规划：最优化中理论成熟，方法有效，应用广泛的一个分支。它研究线性的目标函数的极值，而自变量必须满足一组线性等式与不等式组成的约束条件。

一般线性规划问题总可以写成下列标准形式：

（1.1.1）

或用矩阵表示：

（1.1.2）

其中是矩阵，是维行向量，是维列向量。

单纯形法的基本思想：若线性规划（标准形式）有最优解，则必存在最优基本可行解，因此求解线性规划问题归结为寻找最优基本可行解。单纯形方法的基本思想，就是从一个基本可行解出发，求一个使目标函数值有所改善的基本可行解；通过不断改进基本可行解，力图达到最优基本可行解。使用该方法求解需满足如下条件：

（1）最优性条件，即在求解问题的过程中，保证获得的新的基本可行解不会比原来的基本可行解更差。

（2）可行性条件，即在求解过程中，保证从一个基本可行解出发，在计算过程中只会碰到基本可行解。

对于线性规划标准模型的矩阵形式（1.1.2），，，， ，矩阵的秩。

矩阵 中任意一个阶的非奇异子阵称为线性规划问题的一个基，设

那么对应的变量称为基变量，而其余的变量称为非基变量。

对于基，在中，令非基变量全为零，可唯一地确定出一个解

称为线性规划问题（1.1.1）的一个基本解。

如果基本解又满足非负限制，即，则被称为基本可行解，基本可行解对应的基称为可行基。

单纯形表是应用单纯形法的基本工具，其功能与增广矩阵相似。

求解思路：方程组

与目标函数组成个变量，个方程的方程组

为了便于迭代运算，可将上述方程组写成增广矩阵

若将看作不参与基变换的基变量，它与的系数构成一个基，这时可采用行初等变换将变换为零，使其对应的系数矩阵为单位矩阵。得到

可根据上述增广矩阵设计计算表。

每迭代一步可以构造一个新的单纯形表。

（1）找出初始可行基，确定初始基可行解，建立初始单纯形表。

（2）检验各非基变量的检验数是

，若

则已得到最优解，可停止计算。否则转入下一步。

（3）在中，若有某个对应的系数列向量，则此问题是无界，停止计算。否则，转入下一步。

（4）根据，确定为换入变量，按规则计算

可确定为换出变量，转入下一步。

（5）以为主元素进行迭代（即用高斯消去法或称为旋转运算），把所对应的列向量

变换为第行

将列中的换为，得到新的单纯形表。重复（2）~（5），直至终止。

初始可行基的选取是单纯形法的关键步骤。以下为初始可行基的两种寻求方法，即大法和二阶段法。

基本思想：大法就是在约束方程中加入人工变量后，对于每一个人工变量，在目标函数中增加一项“”（是充分大的正数），构成一个新的目标函数，只要有一个人工变量取正值，则新的目标函数就不可能取得最大值，故可用这种方法来迫使所有人工变量的取值为零。

基本思想：如果约束不等式是“”或者是约束方程式，则初始可行基不能直接得到。对于如下形式的线性规划问题，不能直接应用单纯形法来求解。

为此，可引进松弛变量来把线性规划问题化为以下形式。

其中是足够大的数。然后利用单纯形法求出原问题的一个基本可行解，再利用单纯形法求出原问题的最优解。这样两次应用单纯形法求解线性规划问题的方法叫做二阶段法。

一般地，在一个线性规划问题的最优基对应的单纯形表中，如果非基变量对应的检验数都是负数，则最优解是唯一的；如果非基变量对应的检验数中有零，那么这一问题的最优解可能不只一个，而一旦求得另一个最优解，就可得到无穷多个最优解。

若某基变量的检验数是，且的系数列向量，则此问题属于解无界的情形，无最优解。

退化：线性规划的单纯形法计算中出现退化基可行解的现象就称为退化，在线性规划的求解过程中，退化是一种比较常见的现象。

循环：单纯形法计算中用规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。这时换出变量，迭代后目标函数值不变。这里不同基表示为同一顶点。可构造一个特例，当出现退化时，进行多次迭代，而基从又返回到，即出现计算过程的循环，便永远达不到最优解。

勃兰特规则：避免出现循环的一种方法。可表示为：

（1）选取中下标最小的非基变量为换入变量，即；

（2）当按规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。

单纯形法的计算是从初始单纯形表经过多次迭代，最后得到单纯形表的。每经过一次迭代，都要计算一个单纯形表，计算量很大。但是，采用单纯形法求解的最终目的是求得问题的最优解，而在迭代过程中出现的一系列单纯形表中某些数据的计算实际上是多余的。在利用计算机进行计算时，为了节省存储量和计算量，需要对单纯形法进行改进。此外，改进单纯形法的每次迭代是可以直接从原始数据出发进行计算的，这样还可以减少累积误差的产生。

基本步骤：

（1）确定初始可行基，并求出的逆矩阵。通常取单位矩阵为初始可行基，这时。

（2）求出

得到关于的基本可行解:。

（3）求出。若，则停止计算，上述基本可行解为最优解。否则转到（4）。

（4）若存在非基变量的检验数，且，则停止计算，问题无最优解。否则，若，则取为入基变量。

（5）求出主列：

（6）按法则求出:

(为基变量的下标）

这时，取为出基变量，从而可以得到新的可行基，再返回到（1）。

对偶单纯形法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯形法。它和单纯形法的主要区别在于：单纯形法在整个迭代的过程中，始终保持原问题的可行性，即常数列0，而检验数（即）由有正分量逐步变为全部（即变为满足，是对偶问题的可行解），这样就同时得到原问题和对偶问题的最优解。对偶单纯形法则是在整个迭代过程中，始终保持对偶问题的可行性，即全部检验数，而常数列由有负分量逐步变为全部（即变为满足原问题的可行性），同时得到原问题和对偶问题的最优解。

基本步骤：

（1）根据线性规划问题，列出初始单纯形表。设检验数全都小于或等于零，检验列的数字，若全是非负数，则已得到最优解，停止计算。否则，转入下一步。

（2）确定换出变量，若

则确定对应的基变量为换出变量。

（3）确定换入变量，在单纯形表中检查所在行的各系数，若所有，则无可行解，停止计算。若存在，则计算：

于是按所对应的列确定为换入变量，这样才能保证所得的检验数仍都小于或等于零。

（4）以为主元素，按单纯形法在表中进行换基运算，得到新的单纯形表。

重复以上各步，直至为止，最后得到，即为所求的最优解。

多项式时间算法也可以用于线性规划问题的求解。如果存在和的一个多项式，使得该问题的任何实例都可以在计算时间（或次数）之内解出，则称该问题存在多项式时间算法，简称多项式算法，而称为算法的计算复杂性。

区别：单纯形法虽然操作简单易行，但不是求解线性规划问题的优良算法。由哈奇扬（Khachiyan）提出的求解线性规划的椭球法可以避免单纯形法最坏情形下的指数时间问题，但是，该方法在实际应用中比单纯形法慢。另一种多项式时间内点法由卡马卡（Karmarkar）提出，它避免了哈奇扬椭球算法的不可操作性。

下山单纯形法是一种直接搜索算法，主要用于无约束函数优化问题的局部搜索。其核心思想为：比较单纯形各顶点对应的适应度函数值，并以此作为判断各点好坏的依据，将通过反射、膨胀和收缩三种操作得出的新点替换原单纯形中最差的点，形成新的单纯形，从而通过迭代而逼近最优点。下山单纯形法具有高效的局部搜索能力，已经在很多领域取得了成功的应用。

联系：二者虽然名称相似，但单纯形法求解线性规划问题，而下山单纯形法求解无约束函数问题，它们是没有直接关联的两种算法。

对于经典的线性规划模型，其中的任何部分都可以用适当的方式将之模糊化。譬如状态系数可以是模糊数，约束条件可以写成模糊集，目标函数也可以表示为模糊集或模糊函数等。选取不同的模糊对象与模糊方式会导致不同类型的模糊线性规划问题（FLP）。

例：如下述模糊线性规划问题

这里，，向量，和有相应的维数且假设。模糊条件（2）是某种弹性约束，意指“近似小于等于”，也就是随着（2）式右端常数项（看作参变量）的变化增大，近似的模糊隶属度也会逐渐减少。于是，个约束条件可分别由个模糊集表达，其隶属函数单调递减。

关于求解模糊线性规划问题的一种新的单纯形算法，就是应用单纯形法先求解与（FLP）相应的普通线性规划问题；然后，通过模糊约束集与模糊目标集的隶属度的比较，获得的最优值；最后，将模糊约束集与模糊目标集的交集的最优隶属度代入最优单纯形表中，即可求得模糊线性规划问题的解。

例：用单纯形方法解下列问题：

解：引进松弛变量，把上述问题化成标准形式：

建立初始单纯形表：

初表中的判别数用定义式

算出。由于此例是极大化问题，判别数中有负数，因此可求改进的基本可行解。由于最小判别数

，

因此取第1列作为主列。根据最小比值规则，取第2行作为主行。以为主元，进行主元消去，得下表:

再以为主元，进行主元消去，得到

判别数均非负，达到最优。最优解

，

目标函数的最优值

。

脱氧合金化是钢铁冶炼的过程中最重要的工艺环节之一， 在保证钢水质量的同时，为了最大限度地降低合金钢的生产成本，基于数学模型建立一种自动配料模型是各个钢铁企业为了提高企业竞争力亟待解决的问题。选取代表元素C、Mn并利用参考炉次法对其收得率进行计算，通过对偶单纯形法对相关数据以及收得率的预测结果，可建立综合的单纯形法合金配料模型，再对数据进行计算分析，最终通过MATLAB软件求解，从而可以得到钢水脱氧合金化的最优配料方案。

土石方动态调配优化平衡是大型土石方工程施工中的核心问题。通过分析土石方平衡调配系统涉及到的各个影响因素，以全过程总调配费用最低为目标函数，综合考虑调配过程中定量和定性化的约束条件，可以构建出土石方动态调配模型，并采用单纯形法进行求解，从而求出最优调配方案。实例验证的结果表明，单纯形法简便易行，能够快速获得调配结果，最终得到的调配方案可以满足施工强度在填筑、开采、运输等方面的各项要求。

生产作业计划在企业竞争中尤为重要，企业需要加强自身生产计划管理水平，才能对可利用资源进行充分计划与统筹，满足客户对于产品的不同需求。在生产作业计划中，图解法是寻求最优解的一种有效方法。但是，对于三种以上产品的生产作业计划问题，图解法无能为力。单纯形法可以解决这一难题，基本思想是针对企业生产作业计划进行建模，编制出初始单纯形矩阵，对矩阵进行换基迭代，让其变成简单矩阵，这样可以提高运算效率。