第二章 单纯形法
由上一章定理5，线性规划问题的最优解可以只限于在基可行解中去挑选。由于基可行解有限,故原则上可采用枚举法。但从算法的角度看,这显然不是简便有效的。当m、n较大时,根本行不通。事实上m、n在100左右的线性规划问题属于小型的。而此时基可行解的数目可能多达2（m=50,n=100）以上,故必须寻找有效算法。Danzig首先提出的单纯形算法被实践证明是异常有效和普遍适用的。其基本思想是从一个基可行解出发,寻找一个比之更“好”的。由此不断改进,最后得到最优解。
单纯形法可分为两阶段。第一阶段是寻求第一个基可行解。第二阶段是通过换基迭代寻找最优解。下面先介绍第二阶段，然后再讲第一阶段。
§1 典式及单纯形表
典式考虑标准形式的线性规划
设已知一个可行基B是m阶单位矩阵。不失一般性,可假定B位于A的前m 列。这时约束方程（1）的形式为
其中，显然对应基可行解，将代入目标函数（3）,得
记
（4）
（5）
则原问题（LP）变为
（* ）
这种形式叫作线性规划问题的典式。它显然与（LP）(1)-(3)等价。
对于任何一可行基B，亦可把（LP）化为典式形式。化法如下：
仍设B位于A的前m列，即A=（B、N）。其中B=， 。相应地向量X和C可分为 。于是（1）可写成
（6）
或
其中
把（6）代入目标函数（3）。得
（7）
即
（7）
其中仍为基可行解对应的目标函数值。仍为目标函数中非基变量系数之相反数。这样我们得到一般典式的矩阵形式：
** （8）
单纯形表设对某初始可行基B，已求得（LP）的典式为,
（9）
为了计算方便，将式中的系数分离出来，象形成增广矩阵那样列成表格，称为对应于基B的初始单纯形表：
基变量
1 0 0
0 1 0
0 0 1
f
0 0 0
注意表中最后一行实际上是等式：的简化和变形。我们将看到这样写不会影响以后的运算，反而带来很多方便。
上述单纯形表又可写成矩阵形式：
基变量
I BN
f
0
因
- （10）
故这个表又可进一步简写为
基变量
f
-
单纯形表的这种矩阵形式在线性规划的理论与计算中都是十分重要的。应该指出，这里给出的表是对一个特殊的可行基而言。但所得结果具有普遍适用性。如不限制基变量是前m个，引入以下符号：设S是基变量下标集合，R=/S是非基变量下标集合，这样基变量 的典式可以写成
（11）
§2 判别定理与换基迭代
判别定理
对于给定的基B及相应的基可行解，可针对典式作出如下判断。
定理1 若所有的,则是最优解。
证明：因,,故对任意可行解X，有，故是最优解。
可见，在进行最优性检验时，数起着重要的判别作用,称之为检验数。为明确起见称为相应于变量的检验数,基变量的检验数均视为0。
定理2 若有某个且，则（LP）无最优解证明：根据典式（*）可作一新的可行解:,
将代入，得
当时，因,故。由此可知f在可行解集合中无下界。所以（LP）无最优解。
换基迭代设初始基可行解不满足定理1和2的条件。即存在某，且对某一i()有。则根据典式可造一新的基可行解：
这样的自然满足（1），为了满足非负性条件（2），的取法应满足
取尽量大，即
（12）
这时为可行解。且其中至少有一个变量。从而的非0分量至多是，。以下往证为基可行解。且在非退化情形下使目标函数值严格下降。
1、证 是基可行解。这只要证线性无关。因已知线性无关。故只须证明后面的向量组可由前一个线性表示就行了。首先由的典式有
（13）
（注意都是单位向量）。因，故有
注意到，故以B乘上式两边就得到
即能被线性表示，故是基可行解。
2、证 在非退化情形是改进的基可行解。由（7）可得
而当为非退化的基可行解时，由（12）知。于是 。即目标函数严格下降。
以上到的更换基变量的过程，可以完全通过矩阵的初等交换，即Guass消去法来实现。其实质就是把进基变量所对应的列向量变为单位向量（它的非0分量1位于离基变量 所在的行）。沿用Guass消元的术语，元素称为主元（在单纯形表上常用*号来标识），称为主元列。上述变换亦称转轴变换，或旋转变换。以上过程完全可以在单纯形表中进行，其中目标函数行可看作是第m+1个约束方程，同样参加消元变换。
这样，对改进解。用定理1和2加以考察。若仍不满足，则继续重复上述换基过程。如此迭代下去，便得一基可行解序列。其目标函数值在非退化情形，依次严格下降，因而序列中不可能有重复的项。由于基可行解是有限的,故迭代至有限步必满足定理1或2。
这个迭代过程可以用粗略的框图表示如下：
例1
此即第一章例1的标准形式。
列表迭代如下：
5 3 1 0 0
1 1 0 1 0
3 5 0 0 1
200
50
220
f
4 3 0 0 0
0
（检验数中，若有两个以上大于0，以往的迭代一般取其中最大的）
x1
1 0 0
0 * 1 0
0 0 1
40
100
f
0 0 0
x1
x2
1 0 0
0 1 0
0 0 1 1
25
20
f
0 0 0
-175
表3已是最优表，故最优解和最优值分别为
,
此与用图解法得到的结果相同。
§3 初始基可行解的求法
回过头来，研究初始基可行解的求法，在这里我们给出两种处理方法。它们都是通过引入所谓人工变量的办法来实现的。
大M法
设问题是标准的：
(14)
为了获得一个初始基可行解。引入人工变量令。考察另一个线性规划问题
(15)
其中是一个充分大的数，E=(1,1,,1)。
定理2 设是问题（15）的最优解。若y=0,则是问题（14）的最优解。若y0，则问题（14）无可行解。反之，若是问题（14）的最优解，则是问题（15）的最优解。
证明 设x是（14）的任一可行解，则是（15）的一个可行解。于是当y=0时，因是（15）的最优解，而是（15）的可行解。故
CX0=CX0+MEY0≤CX+ME0=CX
所以是（14）的最优解。
若y0,设（14）有一可行解X，则是（15）的一个可行解。于是
因y0,故当M充分大时，上式不可能成立。所以这时（14）没有可行解。
反之，若是（14）的最优解。设是（15）的任一可行解，则
1、若y=0，则X是(14）的一个可行解。于是
2、若y 0，由于M>0可以充分大，所以必有
因此是（15）的最优解。
推论 若问题（15）无最优解，则问题（14）亦无最优解。
上述定理说明，为了获得（14）的最优解，可直接去求解（15）。而（15）的初始基可行解是明显的。此法的缺点是，其中M较难确定，给上机计算带来麻烦。但手算时不必具体给出，只要把它作为一个足够大的正参数来处理就行了。
例2
添加的人工变量不必非要m个，其实根据问题具体情况，只要在初始表中能凑成一个单位矩阵I就可以了。此例只须增加二个人工变量即可。具体迭代过程如下：
x4
1 2 1 1 0 0
1 2 3 0 1 0
2 1 5 0 0 1
10
15
20
f
1 3 3 -1 -M -M
0
x4
y1
y2
1 2 1 1 0 0
1 2 3 0 1 0
2 1 5 0 0 1
10
15
20
f
3M+2 3M+4 8M+4 0 0 0
35M+10
0 1 0
0 0 1
1 0 0
6
3
4
f
0 0 0
3M-6
0 0 1
1 0 0
0 1 0
f
0 0 0
1 0 0
0 1 0
0 0 1 0
f
0 0 0 -1
-15
至此，最优解和最优值分别是
T,
（二）二阶段法
构造一个辅助问题：
(16)
问题（14）和（16）的解之间有如下关系
定理4 若（16）的最优基可行解为，则是（14）的一个可行解。若（16）的最优基可行解为，且，则（14）没有可行解。
证明 前一结论显然成立，下面只证后者。用反证法。设X为（14）的一个可行解，则是（16）的一个可行解。它使目标函数z取0值。但此时（16）的最优值z=>0。产生矛盾。故（14）不可能有可行解。
定理4的一个前提是（16）有最优解。这是不成问题的。显然，（16）有一个现成的基可行解，X=0，又因目标函数值z0。它在可行解集合上显然有下界0。故必有最优解（单纯形迭代只有两种结果：一是有最优解。一是可行解无下界）。
（16）的初始单纯形表具如下形式：
… …
1 …
… … …
1 …
z
0 … 0 …
用单纯形法求其最优解，得min z=z*。则
（ⅰ）若，由定理4，原问题（14）无可行解。
（ⅱ）若，由定理4,是（14）的一个可行解。此时若最后一个表中基变量里不含人工变量，则即是（14）的一个基可行解。故只要去掉们对应的列，去掉关于（16）的Z目标函数行，换上用非基变量表示的（14）的目标函数行，即可得（14）的初始单纯形表。
若前一阶段最优表中基变量含有人工变量，例如。设所对应的方程（表中第r行）为
(17)
其中为基变量，分别为变量Y,X中非基变量的指标集合，以下又可分为两种情形
1、在（17）中所有均为0，即有
则说明原问题（14）的约束方程组AX=b中有一个方程是多余的，应该删去（删掉r行即可）。
2、（17）中不全为0，则去掉Z目标函数行，并任取；以为主元实行Gauss消元一次。结果进基离基。若还有人工变量留在基内，则可续行此法。有限步后必可得到（14）的一个基可行解。
综上所述，对任一线性规划问题（14），可以先解它的辅助问题（16）。解的结果，或者说明（14）无可行解，或者找到（14）的一个基可行解，然后再求它的最优解。这种解法通常称为二阶段法。
例3
引入人工变量。作单纯形表如下（这里添加原目标函数f一行是为过渡到第二阶段作好准备）：
x
2 3* -1 5 6 -3 1 0
1 2 2 -2 -3 2 0 1
10
15
z
3 5 1 3 3 -1 0 0
25
f
5 3 4 -1 -2 1 0 0
0
1 2 -1 0
0 -7 1
z
0 -7 4 0
f
3 0 5 -6 -8 4 -1 0
-10
1 0
0 1
z
0 0 0 0 0 0 -1 -1
0
f
0 -1 0 -1
去掉人工变量列和Z目标函数行，继续迭代二次得最优解
注意：人工变量的个数有时可以少于约束方程的个数。此外在第一阶段迭代过程中，人工变量一旦离基之后，可以不再进基，故可从表中删去。这一点是能严格证明的。
§4 退化与循环
以上是在非退化的前提下，证明了单纯形法有限步收敛到最优解。然而，据退化的定义可知，问题退化与否事先是无法判断的。倘若问题是退化的，即某个基可行解的个别基变量取0值。这样就可能取0值，至使新目标函数值不严格下降，从而可能导致迭代中出现循环:，得不到最优解。事实上早就有人构造出出现循环的例子。例如E.Beale于55年给出的出现循环的例子如下：
例4、所给问题的初始单纯形表为
x
-60 9 1 0 0
-90 3 0 1 0
0 0 1 0 0 0 1
0
0
1
f
-150 -6 0 0 0
0
迭代规则：①若有几个检验数λ都大于0,则选其中较大的进基。②若有几个基变量同时使最小比值达最小。就取变量下标较小的那个作为离基变量,结果迭代6次以后，又得到上面的初始表。
于是产生了避免循环的理论和方法。这主要是摄动法（或称字典序法）和Bland方法。
（一）摄动法
（ⅰ）先找（L P）(14)的一个初始基可行解，然后把基变量的下标换一下，让基变量的下标是。
（ⅱ）假定，选定为进基变量（可见进基变量的选法不变）。仍考虑
若唯一，则离基变量已确定；否则，考虑
若唯一，则据之确定离基变量；否则，继续考虑
直到选得唯一一个极小值，并据之确定离基变量为止。就是说，若求得唯一极小值为则即为离基变量。注意一定有u<n,否则AX=b中必有多余方程,应去之。上述比较大小亦称按字典式比较大小,故方法也叫字典序法。
下边对摄动法的正确性给予说明解释。
对（14）的典式作如下摄动：
(18)
式中的理解为充分小的正数。由于对初始基可行解如(ⅰ)，从而。故由摄动后的典式（18）得到的基解也是可行的。即；反之，若得到（18）的基可行解，由于 可以充分小，故必（否则，若某，由，必有。与可行性矛盾）。从而令，必得（14）的一个基可行解。以下说明理论上存在，使对任意。由典式（18）得到的基可行解均非退化（从而对这样的，迭代终止于有限步）。这是因为形如
即出现退化基可行解的值只能有有限个，加之方程个数和基本解的有限性，故上述存在。
最后由（18）的构造上可知的常数项中诸的系数，恰好是单纯形表中基变量这一行的系数，从而不必具体写出。并且由于可以充分小，故在比较大小时，若有，那么谁大谁小自然由比值和的大小决定了，这便是(ⅱ）
(二)、Bland方法
1976年Bland提出并证明[13]了一种用单纯形法进行计算时，避免循环的新方法，规则如下：
1、选取指标k=min{j|λj﹥0}，由此确定进基。
2、选取指标，由此确定离基。
Bland方法在理论上很有价值，而且规则简单，但具体计算时，迭代次数比摄动法要多。
§5 几点改进意见本节对单纯形算法提出以下几点改进意见.（一）按照使目标函数下降最多的原则确定进基和离基变量。这既能避免循环,又常减少迭代次数。（二）不直接引入人工变量求初始基可行解，并从寻基一开始就考虑目标函数的影响,从而使得到的初始基可行解尽可能地好。（三）把“两阶段法”简化为单阶段算法。
（一）新换基规则设所论问题由§1的初始单纯形表给出，据之，新换基规则可叙述如下：
(A)设，对每一，计算最小比值：
(19)
若不止一个，则取行下标最小的，转（B）。
(B)对满足（19）的所有，计算
(20)
若不止一个。则取列下标最小的，转（C）。
(C)以为主元实行Gauss消元，然后返回（A），直到R为空集或对某一，皆有，i=1,2,…m,为止。
可以证明[18]、[19]，对上述新规则，有以下性质定理5 对于每步迭代所面临的一切换基选择中，新规则是使目标函数下降最大者。
定理6 对于非退化问题（14），假定按新规则应选为主元，若主元所在的行还有其它元素满足最小比值（19），则有
（ⅰ）若以 为主元迭代一次后。相应的新检验数
（ⅱ）若以为主元迭代一次后，则至少
（ⅲ）若主元选在这一行，则最小比值的性质迭代后保持不变，即新比值及 t=1P仍满足（19）。
（ⅳ）若以为主元迭代一次，则新的基变量至少在下次迭代中不会离基。
当n>>m时，定理6的条件常被满足。
据定理6，可对新换基规则作如下进一步的说明：
设某行存在P>2个最小比值（当n>m时，此事总发生） t=1P，按单纯形法，迭代中可据任一正检验数确定进基变量。倘若限于在 中选取。则由定理6知。取使目标函数下降最大的为离基变量（设为）则迭代次数最少（仅一次）若执意不让 进基,而取别的，则变量将象走马灯一样换进换出，直到最后不得不让 进基为止,这期间增加的迭代次数,少则一步.多则可达P步。大家知道这种进基又离基（有的进去后马上离开）现象的多次出现，正是有时收敛慢的重要原因。由定理6，新换基规则避免或大大减少了这种现象的出现。
诚然，目标函数每步下降最多不能保证整体迭代次数一定最少，事实上对于存在最优解的任何一个（L P），从某一基可行解出发,都有一个步数最少的迭代程序，只是由于问题本身的五花八门，数据几乎又可以随机地任意选取，人们完全可以举出按最大正检验数确定进基变量迭代步数最少的例子；也能举出按Bland规则确定时迭代步数最少的问题。因此，试图找一个对任何具体问题迭代次数都最少的统一规则是根本办不到的。只能退而求其次，根据平均性态来区别优劣,大量事实例表明，按最大正检验数选进基变量比以往的其它方式效果好。这是因每迭代一步（以为主元）目标函数将下降。
(21)
因此，平均说来，与一般的相比，最大正检验数常使目标函数下降更大些，进而使总的迭代次数少些。但同时，由（21）知检验数最大，并不总能保证使（21）最大( 只是其中的一个因子)。可见就敛速说来新换基规则是平均性态下的最佳选择。
进一步还有定理7[18] 按新换基规则进行迭代，在任何情况下均不会出现循环，从而迭代终止于有限步。
我们已经知道，事先判断一个（LP）退化与否是十分困难的，因而在选择换基规则上常有顾此失彼之感：按最大正检验数换基吧，虽说一般效果好些，又怕万一出现循环；采用Bland规则或其它避免循环的方法，如摄动法吧，又顾虑问题本不会出现循环而白白增加迭代次数（或程序）。现在新换基规则既避免循环,又常能减少迭代次数，两方面都照顾到了，足见改进是实质性的。下面针对Beale给出的例4，用新换基规则求解：
x
-60 9 1 0 0
-90 3 0 1 0
0 0 0 0 0 1
0
0
1
f
-150 -6 0 0 0
0
-60 0 9 1 0
-90 0 3 0 1
0 0 0 0 0 1
1
f
-150 0 -6 0 0
0 -15 0 1
1 -180 0 6 0 2
0 0 0 0 0 1
1
f
0 -15 0 0
这里只迭代二次即得最优解，而若用Bland规则迭代6次才能得到最优解。
当然，按新换基规则每步要增加一些计算量，但这与减少一步迭代的计算量相比，一般要差个数量级。
（二）求初始基可行解的简化
引入人工变量求初始基可行解，虽然从程序上看与单纯形法无异，但一来导致系数矩阵扩大（一般要增加m列）引起存储和计算量增加，对大型问题可能使计算机容纳不下。二来没有考虑原目标函数的影响，致使得到的初始基可行解可能很“差”，徒增迭代次数。以下与新换基规则有关的改进程序，既不须明显地引进人工变量（不必增加系数矩阵的列），又能让迭代与原目标函数f挂钩，使得到的初始解尽可能地接近最优解，从而把两个阶段有机地结合起来。具体迭代步骤如下：
先针对（14）建立如下初始表
… …
… …
… …
… …
z
… …
f
… …
0
设R=，对每一jR，计算
(22)
对满足（22）的所有，计算
(23)
则为一基变量
4、以 为主元实行Gauss消元，并在 这行的最左端标以,然后返回2,直到R为空集为止，这时，如Z这行最右端的（一阶段的）目标函数值大于0，则原问题无解；若等于0，删之又会有两种可能。
（ⅰ）所选基变量的个数恰为m，则已得初始基可行解。
（ⅱ）所选基变量的个数,此时右端常数项列中必有m- 个0，且这些0所在的行左端未标出基变量（它们就是未被替换出来的那些人工变量）任取其中一行，然后以该行任一非0元素（若无非0元素，则删掉该行，说明有多余方程）为主元，实行Gauss消元，即增加一基变量，如此进行下去，最后必可得一基可行解。
根据两阶段法的理论，很容易看出程序的合理性。其关键在于这样一点：由于人工变量离基后，将它与相应的列去掉，不影响以后的寻优迭代，从而一开始就可以不必把它们留在单纯形表中。
由（22）、（23）的选基规则可以看出，我们的具体挂钩方法就是：在Z行的所有正检验数中每次选择使f下降最大者（若（23）为负实为上升最小者）为基变量。
用简化方法求解例3，迭代如下：
x
2 3 -1 5 6 -3
1 2 2 -2 -3 2
10
15
z
3 5 1 3 3 -1
25
f
5 3 4 -1 -2 1
0
4 0 4 -2
1 1 -1 - 1
z
4 0 4 -2
f
3 -1 0 3 4 -3
-30
1 0
0 1
7
4
z
0 0 0 0 0 0
0
f
0 0
-51
迭代二次所得的初始基可行解（7、0、4、0、0、0）即为最优解。比用二阶段法减少一半迭代次数。值得一提的是，上述所求初始基可行解即是最优解的现象，并非碰巧，许多计算实例表明，这是常有的现象，可见，这种简化处理是卓有成效的。
（三）单阶段算法考虑线性规划的标准型问题（14）：
对于这一问题，无论是“大M法”还是“两阶段法”，都要增加人工变量，这无疑扩大了问题的规模，增加存储。特别是常用的“两阶段法”，在一阶段的迭代中，仅仅是为了得到一个基可行解，而无暇顾及和考虑使目标函数下降这一重要环节。本文采用一定技巧，把求解线性规划的两阶段法转化成单阶段法，既略去了 人工变量减 少存储，又从一开始就可考虑目标函数的因素，往往能减少迭代次数和计算量。
算法迭代步骤
（）对目标函数系数由小到大排队，不妨设，依次选取为基变量，则经过（m-1）次Guass消元后，可得类似于下面的初始表：
表1
… …
…
1 0 … 0 …
0 1 … 0 …
… …
0 0 … 1 …
0 0 … 0 …
…
f
0 0 … 0 …
假设常数项（若，可用（-1）乘第m行，若，可用m行左边第一个非0系数，例如为主元实行一次Guass消元，然后再将m行与常数项不为0的行，例如m-1行交换即可），取适当大的正数M>0，使得以m行的M倍加于前面各行后，其常数项变为正数。这样做对前面已选的(m-1)个基变量无影响。因此，不妨假定这样处理后的结果仍如表1。
（）因，故若，则问题（1）无可行解，结束。否则，必有某j,mjn，使。对每一，计算最小比值，确定准主元。
(24)
再按最速下降规则选择主元，即对满足上式的i计算
(25)
然后以为主元实行一次Guass消元。继续上述过程直到选得的s=m时为止，转
（）按照通常单纯形法，继续迭代求优。
简单算例例1求解线性规划问题
解：构成初始表，依次迭代求解
x1 x2 x3 x4 x5
1* 1 1 1 1
-1 1 -1 1 0
2 0 3 0 -2
10
2
1
f
1 -1 -2 -3 -4
0
x1
1 1 1 1 1
0 2* 0 2 1
0 -2 1 -2 -4
10
12
-19
f
0 -2 -3 -4 -5
-10
x1
x2
1 0 1 0 1/2
0 1 0 1 1/2
0 0 1 0 -3
4
6
-7
f
0 0 -3 -2 -4
2
x1
x2
1 0 1 0 1/2
0 1 0 1 1/2
0 0 -1 0 3*
4
6
7
f
0 0 -3 -2 -4
2
x1
x2
x3
1 0 7/6 0 0
0 1 1/6 1 0
0 0 -1/3 0 1
17/6
29/6
7/3
f
0 0 -13/3 -2 0
34/3
由此知，
例2求解线性规划问题
解：构成初始表，依次迭代求解
x1 x2 x3 x4 x5
1 1 1 1 1
-1 -1 1 3 2
4 4 2 -2 6
10
6
28
f
-2 -3 1 1 -1
0
x3
1 1 1 1 1
-2 -2 0 2* 1
2 2 0 -4 4
10
-4
8
f
-3 -4 0 0 -2
-10
x3
x4
2 2 1 0 1/2
-1 -1 0 1 1/2
-2 -2 0 0 6*
12
-2
0
f
-3 -4 0 0 -2
-10
x3
x5
13/6 13/6 1 0 0
-1/3 -1/3 0 0 1
5/6* 5/6 0 -1 0
12
0
2
f
-11/3 -14/3 0 0 0
-10
x3
x5
x1
0 0 1 13/5 0
0 0 0 -2/5 1
1 1 0 -5/6 0
34/5
4/5
12/5
f
0 -1 0 -22/5 0
-6/5
由此知，
理论依据针对表1，添加人工变量，并引入一阶段的目标函数，准备实施“两阶段法”，则得如下之表（若考虑实行大M法，可类似的证明）：
表2
… … y
…
y
1 0 … 0 … 0
0 1 … 0 … 0
… …
0 0 … 1 … 0
0 0 … 0 … 1
…
z
0 0 … 0 … 0
易见，表（2）中第m行与一阶段的目标函数行（（m+1））行），如果不看人工变量，则是一样的，而且除非主元选在第m行，不然，则上述情形保持不变。因此，一阶段的迭代中，作为检验数的第m+1行可由第m行来代替而不必出现。而主元一旦选在第m行，易见，迭代后一阶段的目标函数全小于或等于0，这意味着已得到一阶段的最优解，同时亦得到原问题的一个基可行解，可以开始第二阶段的寻优迭代了。由于表面上的一阶段的目标函数行不出现，因而也省去了去掉的步骤。这样，我们便把两阶段迭代过程，通过单阶段加以实现，做到了最大限度的简化。
第六节 一种改型算法单纯形算法虽然不是多项式算法，却十分有效，且正普遍使用。人们还认识到复杂性概念只涉及到算法在最坏情况下的性态，而这种最坏情况在实际问题中发生的概率究竟有多大，并未予以考虑。这说明用算法在最坏情况下的性态来区别好坏不是最科学的，而算法的平均性态如何才是衡量算法好坏的更有说服力的标志。
有人于1982年证明，单纯形法是平均多项式算法。进一步，人们提出，能否存在单纯形法的某种改型，它是多项式算法，这是一个很有意义的问题，然而至今尚无定论。下面介绍一种改型算法，它在概率上是多项式的，但已十分接近多项式算法。
求基可行解经简单处理可将一般问题（14）写成如下形式：
（26）
对于（26）不必用计算最小比值求准主元，即可用Gauss消元求出n-1个基变量。此时（26）的约束方程的增广矩阵具如下形式：
（27）
对于（27），若，则问题（27）显然没有可行解。否则，至少
。进一步，如果还有：
(28)
则以为主元实行一次Gauss消元，即得问题（14）一个基可行解。
如果对（28）均不成立，说明以m行的任何非0元素为主元，实行Gauss消元后，都不会得到一个基可行解。因此必须在前(m-1) 行中先选一主元迭代一次后，再检查是否有（28）式成立。那么如何选择主元，以保证迭代后必有（28）式成立呢？经分析发现，如果主元选择，它应满足以下条件：
(29)
(30)
就是说，若（29），（30）均成立，则先后以和为主元，实行两次Gauss消元，即得问题（14）的一个基可行解。
若（29）和（30）不同时成立，则有以下几种可能：
一是对某一i，（29）不成立。这又分两种情形：一是该行没有异号的系数，即要么，要么，遇此情形只需令其中的非0系数对应的变量为0，即若，则令，结果第i个方程成为0=0的恒等式，故可去之，同时因，故其对应的系数列可去之（显然，若，则问题无可行解）。此举称为置0处理。可见问题经置0处理后，对剩下的，便总有>0及<0同时成立了。为简单计，不妨设问题事先已经置0处理了。故这时若对某一i，（29）不成立只能是下边的情形,
(31)
可以证明：若(31)成立,则问题一般无可行解[21];若（14）的数据是随机给出的，则于状态（27），存在满足（29）、（30）的列标j,s之概率一般已达到0.99[21]-[23]。这显然是理想的结果。
1 下面给出寻找满足（29）、（30）的列标j,s的一种方法。
容易看出，考察（29）、（30）的计算量主要在验证（30）成立上，注意对确定的i，（30）等价于，
（32）
采用（32）的好处在于，对指定的i,j,s,是固定不变的，只需计算一次，这样每次比较时只需计算就可以了，既方便又快捷，可节省一半计算量。
进一步，每每先固定i再寻找j和s也不是必要的、科学的，亦应有所选择，分析结果，按以下顺序和条件考察既方便又可使计算量最少，因而是最合理的。其中，当分母为0时，记
现任取一列，然后对其他列，依次筛选，满足以下条件的s,i
(33)
(34)
(35)
容易验证条件（29）、（30）与条件（33）、（34）、（35）是等价的。注意（33）式成立意味着，对于取定的一列j，则与j列正系数同行的其他列必为负，方可入选，这既容易判断，又不必计算分数值，我们称此条件为异号条件。具体考察时，宜先据（33），去掉不合异号条件的列，然后在余下的列任取一列，求出满足（33）的i，之后再检验（34）（它与（29）等价）是否成立；若不成立，弃之，另取一满足异号条件的列，重复求i的过程；若成立，最后再检验（35），直到找到满足（33）-（35）的i,j,s为止。
按上述过程寻找满足（29）、（30）的i,j，s可使计算量减少一个数量级。
求最优解
运用上述全搜索方法以往总是在求得一个基可行解后，再考虑按最小比值确定列准主元(即)，然后于i行令
(36)
(37)
容易验证，若成立如下最优性条件
(38)
则以为主元实行一次Guass消元，即得最优解。
若（38）不成立，则至少有一t，使,或,，进而迭代一次后，t列的新检验数必为正，称这样的t列为不谐列，并且选不谐列最少的为主元作为换基规则。这样做虽然效果很好，但求基可行解与寻最优解截然分开似不可取，应该将这两阶段有机结合起来，则效果会更好。事实上，当寻找基可行解时，一般会有多个满足（28）或有多对i,j,s满足（29）（30），应在其中选择不谐列最少的作为主元，则可减少迭代次数增加敛速。具体说来，就是对（它是准主元不成问题）考察使（38）不成立的不谐列数，选不谐列最少的作为主元，实行Guass消元。
[22]中指出，若不谐列只有一个，比如第t列，则该不谐列对应的变量一定是最优基变量，于是可优先安排该变量进基，并且不再离基。确切的说，若的检验数时，立即进基；若，下次迭代进基。
例子例 1 求解线性规划问题
（39）
解 把（39）化成形式（27），得如下初始表，然后按目标函数较小系数优先进基的原则迭代如下：
x
0 2 -2* 2 -3 0
0 1 -2 3 -2 1
-2 1 -1 0 0 1
0 -1 1 -1 3 1
0
0
0
1
f
-1 -1 2 -1 1 0
0
x3
0 -1 1 -1 3/2 0
0 -1* 0 1 1 1
-2 0 0 -1 3/2 1
0 0 0 0 3/2 1
0
0
0
1
f
-1 1 0 1 -2 0
0
x3
x2
0 0 1 -2 1/2 -1
0 1 0 -1 -1 -1
-2 0 0 -1* 3/2 1
0 0 0 0 3/2 1
0
0
0
1
f
-1 0 0 2 -1 1
0
x3
x2
x4
4 0 1 0 -5/2 -3
2 1 0 0 -5/2 -2
2 0 0 1 -3/2 -1
0 0 0 0 3/2 1*
0
0
0
1
f
-5 0 0 0 2 3
0
x3
x2
x4
x
4 0 1 0 1 0
2 1 0 0 1/2 0
2 0 0 1 0 0
0 0 0 0 3/2 1
3
2
1
1
f
-5 0 0 0 -5/2 0
-3
故有表中最后一步迭代虽然由于满足（28）,与均可为进基变量，但考虑到最优性条件（38）应选不谐列最少的，则宜选进基（此例中不谐列为0）
例2
（40）
把（40）化成形式（27），得如下初始表：
x
x4
x5
1 1 -1 1 0 -2
-2 -3 2 0 1 -1
2 1 2 0 0 1
0
0
5
f
10 15 12 0 0 0
0
初始表中已有2个现成的基变量和，故可直接考察满足（33）-（35）之i,j,s。容易验证，当j=1时，有s=3,6及i=1; 当j=2时，有s=3,6及i=1。再由最优性条件（38），检查它们的不谐列数，知当j=1时，即取为主元，不谐列数为3，而取为主元时，不谐列数为2，故取为主元实行Guass消元，结果如下：
x
x2
x5
1 1 -1 1 0 -2
1 0 -1 3 1 -7
1 0 3 -1 0 3*
0
0
5
f
-3 0 27 -15 0 30
0
x2
x5
x6
5/3 1 -1 1/3 0 0
10/3 0 6 2/3 1 0
1/3 0 1 -1/3 0 1
10/3
35/3
5/3
f
-13 0 -3 -5 0 0
-50
故有，其中最后一步迭代选择进基的理由与例1的相同，即它满足最优性条件（38）。
迭代次数分析对问题（26）的增广矩阵（27），若假定（29）成立，则对任一，易见存在，当把第i行的M倍加于各行后，可使s列的新系数（仍记为）
在作了上述处理后，容易验证，对满足（29）的j，s，条件（30）成立等价于
(41)
假定问题（26）的数据是随机给出的，则可认为最大比值（41）取集合中每个值的可能性是一样的，若该集合中有个元素，则（41）成立的概率，设想对(27),取一组满足(29)的j,s，检查它们是否满足（41），若不满足再另取一组检查，则（41）成立恰在第k次检查发生的概率为
若设，则进一步有
（42）
于是可算得下表：
h = 1 2 3 4 5 6 7 …
= 0.63 0.86 0.95 0.982 0.993 0.9975 0.9991 …
据上表可知，若检查5(m-1)组满足（29）的列j,s，则其中遇到使（41）成立从而得到可行解的概率已超过0.99。
那么（27）中最少能有多少组（设为Q）因满足（29）而可供检查的列j,s呢？（据此可算出为达到上述概率最多还需迭代）次。
仿照置0处理可证，若（27）中第i行里仅有一个正（或负）数，则与此系数对应的变量必为基变量，进而使问题简化。故按最坏情形考虑第i行至少应有2个正（或负）数，从而有(n-m-1)个负（或正）数（由于假定数据是随机选取的，故第i行m列以后出现事先指定数（比如0或两相同数）的概率为0 而不予考虑）。故至少可对应产生2(n-m)个不同的分数组
令，则分数组至少可达个。另外在随机的情况下，与这两种状态是等可能的，从而可以认为前者成立的概率为，现在检查上述N=2(m-1)(n-m)个数组中，使（29）成立的数组，则其不少于的概率按二项分布计算:
(44)
当N较大时，如N>36，可用德莫佛定理计算
(45)
总结以上知（27）中至少有个可供检查的数组，其中满足（29）的不少于的概率为，因此至多再迭代的次数为，若，则说明不必迭代。为使（29）、（30）同时成立的概率，若n-m，则至多需迭代一次；若n-m，则已不必迭代，并且仅要求m。
如果不从最坏情况考虑，而假定（27）第i行每一系数取正与取负的概率相等，即均为，则从中任取两数，其为异号的概率亦为，易见从(n-m+2)个数中任取两数成一组，共有种不同组合，其中异号的应占一半,而对，依照的计算可知其中异号数组不少于的概率为
这时可算得只需再迭代（用（44）式计算的）
次即可使（29）、（30）成立的概率达到0.99，若n-m,则不必迭代，并且只要求。简言之，通常在状态（27）下，即可搜索到满足（29）、（30）的，继之先后以为主元迭代两次，便可得一基可行解。
由上一章定理5，线性规划问题的最优解可以只限于在基可行解中去挑选。由于基可行解有限,故原则上可采用枚举法。但从算法的角度看,这显然不是简便有效的。当m、n较大时,根本行不通。事实上m、n在100左右的线性规划问题属于小型的。而此时基可行解的数目可能多达2（m=50,n=100）以上,故必须寻找有效算法。Danzig首先提出的单纯形算法被实践证明是异常有效和普遍适用的。其基本思想是从一个基可行解出发,寻找一个比之更“好”的。由此不断改进,最后得到最优解。
单纯形法可分为两阶段。第一阶段是寻求第一个基可行解。第二阶段是通过换基迭代寻找最优解。下面先介绍第二阶段，然后再讲第一阶段。
§1 典式及单纯形表
典式考虑标准形式的线性规划
设已知一个可行基B是m阶单位矩阵。不失一般性,可假定B位于A的前m 列。这时约束方程（1）的形式为
其中，显然对应基可行解，将代入目标函数（3）,得
记
（4）
（5）
则原问题（LP）变为
（* ）
这种形式叫作线性规划问题的典式。它显然与（LP）(1)-(3)等价。
对于任何一可行基B，亦可把（LP）化为典式形式。化法如下：
仍设B位于A的前m列，即A=（B、N）。其中B=， 。相应地向量X和C可分为 。于是（1）可写成
（6）
或
其中
把（6）代入目标函数（3）。得
（7）
即
（7）
其中仍为基可行解对应的目标函数值。仍为目标函数中非基变量系数之相反数。这样我们得到一般典式的矩阵形式：
** （8）
单纯形表设对某初始可行基B，已求得（LP）的典式为,
（9）
为了计算方便，将式中的系数分离出来，象形成增广矩阵那样列成表格，称为对应于基B的初始单纯形表：
基变量
1 0 0
0 1 0
0 0 1
f
0 0 0
注意表中最后一行实际上是等式：的简化和变形。我们将看到这样写不会影响以后的运算，反而带来很多方便。
上述单纯形表又可写成矩阵形式：
基变量
I BN
f
0
因
- （10）
故这个表又可进一步简写为
基变量
f
-
单纯形表的这种矩阵形式在线性规划的理论与计算中都是十分重要的。应该指出，这里给出的表是对一个特殊的可行基而言。但所得结果具有普遍适用性。如不限制基变量是前m个，引入以下符号：设S是基变量下标集合，R=/S是非基变量下标集合，这样基变量 的典式可以写成
（11）
§2 判别定理与换基迭代
判别定理
对于给定的基B及相应的基可行解，可针对典式作出如下判断。
定理1 若所有的,则是最优解。
证明：因,,故对任意可行解X，有，故是最优解。
可见，在进行最优性检验时，数起着重要的判别作用,称之为检验数。为明确起见称为相应于变量的检验数,基变量的检验数均视为0。
定理2 若有某个且，则（LP）无最优解证明：根据典式（*）可作一新的可行解:,
将代入，得
当时，因,故。由此可知f在可行解集合中无下界。所以（LP）无最优解。
换基迭代设初始基可行解不满足定理1和2的条件。即存在某，且对某一i()有。则根据典式可造一新的基可行解：
这样的自然满足（1），为了满足非负性条件（2），的取法应满足
取尽量大，即
（12）
这时为可行解。且其中至少有一个变量。从而的非0分量至多是，。以下往证为基可行解。且在非退化情形下使目标函数值严格下降。
1、证 是基可行解。这只要证线性无关。因已知线性无关。故只须证明后面的向量组可由前一个线性表示就行了。首先由的典式有
（13）
（注意都是单位向量）。因，故有
注意到，故以B乘上式两边就得到
即能被线性表示，故是基可行解。
2、证 在非退化情形是改进的基可行解。由（7）可得
而当为非退化的基可行解时，由（12）知。于是 。即目标函数严格下降。
以上到的更换基变量的过程，可以完全通过矩阵的初等交换，即Guass消去法来实现。其实质就是把进基变量所对应的列向量变为单位向量（它的非0分量1位于离基变量 所在的行）。沿用Guass消元的术语，元素称为主元（在单纯形表上常用*号来标识），称为主元列。上述变换亦称转轴变换，或旋转变换。以上过程完全可以在单纯形表中进行，其中目标函数行可看作是第m+1个约束方程，同样参加消元变换。
这样，对改进解。用定理1和2加以考察。若仍不满足，则继续重复上述换基过程。如此迭代下去，便得一基可行解序列。其目标函数值在非退化情形，依次严格下降，因而序列中不可能有重复的项。由于基可行解是有限的,故迭代至有限步必满足定理1或2。
这个迭代过程可以用粗略的框图表示如下：
例1
此即第一章例1的标准形式。
列表迭代如下：
5 3 1 0 0
1 1 0 1 0
3 5 0 0 1
200
50
220
f
4 3 0 0 0
0
（检验数中，若有两个以上大于0，以往的迭代一般取其中最大的）
x1
1 0 0
0 * 1 0
0 0 1
40
100
f
0 0 0
x1
x2
1 0 0
0 1 0
0 0 1 1
25
20
f
0 0 0
-175
表3已是最优表，故最优解和最优值分别为
,
此与用图解法得到的结果相同。
§3 初始基可行解的求法
回过头来，研究初始基可行解的求法，在这里我们给出两种处理方法。它们都是通过引入所谓人工变量的办法来实现的。
大M法
设问题是标准的：
(14)
为了获得一个初始基可行解。引入人工变量令。考察另一个线性规划问题
(15)
其中是一个充分大的数，E=(1,1,,1)。
定理2 设是问题（15）的最优解。若y=0,则是问题（14）的最优解。若y0，则问题（14）无可行解。反之，若是问题（14）的最优解，则是问题（15）的最优解。
证明 设x是（14）的任一可行解，则是（15）的一个可行解。于是当y=0时，因是（15）的最优解，而是（15）的可行解。故
CX0=CX0+MEY0≤CX+ME0=CX
所以是（14）的最优解。
若y0,设（14）有一可行解X，则是（15）的一个可行解。于是
因y0,故当M充分大时，上式不可能成立。所以这时（14）没有可行解。
反之，若是（14）的最优解。设是（15）的任一可行解，则
1、若y=0，则X是(14）的一个可行解。于是
2、若y 0，由于M>0可以充分大，所以必有
因此是（15）的最优解。
推论 若问题（15）无最优解，则问题（14）亦无最优解。
上述定理说明，为了获得（14）的最优解，可直接去求解（15）。而（15）的初始基可行解是明显的。此法的缺点是，其中M较难确定，给上机计算带来麻烦。但手算时不必具体给出，只要把它作为一个足够大的正参数来处理就行了。
例2
添加的人工变量不必非要m个，其实根据问题具体情况，只要在初始表中能凑成一个单位矩阵I就可以了。此例只须增加二个人工变量即可。具体迭代过程如下：
x4
1 2 1 1 0 0
1 2 3 0 1 0
2 1 5 0 0 1
10
15
20
f
1 3 3 -1 -M -M
0
x4
y1
y2
1 2 1 1 0 0
1 2 3 0 1 0
2 1 5 0 0 1
10
15
20
f
3M+2 3M+4 8M+4 0 0 0
35M+10
0 1 0
0 0 1
1 0 0
6
3
4
f
0 0 0
3M-6
0 0 1
1 0 0
0 1 0
f
0 0 0
1 0 0
0 1 0
0 0 1 0
f
0 0 0 -1
-15
至此，最优解和最优值分别是
T,
（二）二阶段法
构造一个辅助问题：
(16)
问题（14）和（16）的解之间有如下关系
定理4 若（16）的最优基可行解为，则是（14）的一个可行解。若（16）的最优基可行解为，且，则（14）没有可行解。
证明 前一结论显然成立，下面只证后者。用反证法。设X为（14）的一个可行解，则是（16）的一个可行解。它使目标函数z取0值。但此时（16）的最优值z=>0。产生矛盾。故（14）不可能有可行解。
定理4的一个前提是（16）有最优解。这是不成问题的。显然，（16）有一个现成的基可行解，X=0，又因目标函数值z0。它在可行解集合上显然有下界0。故必有最优解（单纯形迭代只有两种结果：一是有最优解。一是可行解无下界）。
（16）的初始单纯形表具如下形式：
… …
1 …
… … …
1 …
z
0 … 0 …
用单纯形法求其最优解，得min z=z*。则
（ⅰ）若，由定理4，原问题（14）无可行解。
（ⅱ）若，由定理4,是（14）的一个可行解。此时若最后一个表中基变量里不含人工变量，则即是（14）的一个基可行解。故只要去掉们对应的列，去掉关于（16）的Z目标函数行，换上用非基变量表示的（14）的目标函数行，即可得（14）的初始单纯形表。
若前一阶段最优表中基变量含有人工变量，例如。设所对应的方程（表中第r行）为
(17)
其中为基变量，分别为变量Y,X中非基变量的指标集合，以下又可分为两种情形
1、在（17）中所有均为0，即有
则说明原问题（14）的约束方程组AX=b中有一个方程是多余的，应该删去（删掉r行即可）。
2、（17）中不全为0，则去掉Z目标函数行，并任取；以为主元实行Gauss消元一次。结果进基离基。若还有人工变量留在基内，则可续行此法。有限步后必可得到（14）的一个基可行解。
综上所述，对任一线性规划问题（14），可以先解它的辅助问题（16）。解的结果，或者说明（14）无可行解，或者找到（14）的一个基可行解，然后再求它的最优解。这种解法通常称为二阶段法。
例3
引入人工变量。作单纯形表如下（这里添加原目标函数f一行是为过渡到第二阶段作好准备）：
x
2 3* -1 5 6 -3 1 0
1 2 2 -2 -3 2 0 1
10
15
z
3 5 1 3 3 -1 0 0
25
f
5 3 4 -1 -2 1 0 0
0
1 2 -1 0
0 -7 1
z
0 -7 4 0
f
3 0 5 -6 -8 4 -1 0
-10
1 0
0 1
z
0 0 0 0 0 0 -1 -1
0
f
0 -1 0 -1
去掉人工变量列和Z目标函数行，继续迭代二次得最优解
注意：人工变量的个数有时可以少于约束方程的个数。此外在第一阶段迭代过程中，人工变量一旦离基之后，可以不再进基，故可从表中删去。这一点是能严格证明的。
§4 退化与循环
以上是在非退化的前提下，证明了单纯形法有限步收敛到最优解。然而，据退化的定义可知，问题退化与否事先是无法判断的。倘若问题是退化的，即某个基可行解的个别基变量取0值。这样就可能取0值，至使新目标函数值不严格下降，从而可能导致迭代中出现循环:，得不到最优解。事实上早就有人构造出出现循环的例子。例如E.Beale于55年给出的出现循环的例子如下：
例4、所给问题的初始单纯形表为
x
-60 9 1 0 0
-90 3 0 1 0
0 0 1 0 0 0 1
0
0
1
f
-150 -6 0 0 0
0
迭代规则：①若有几个检验数λ都大于0,则选其中较大的进基。②若有几个基变量同时使最小比值达最小。就取变量下标较小的那个作为离基变量,结果迭代6次以后，又得到上面的初始表。
于是产生了避免循环的理论和方法。这主要是摄动法（或称字典序法）和Bland方法。
（一）摄动法
（ⅰ）先找（L P）(14)的一个初始基可行解，然后把基变量的下标换一下，让基变量的下标是。
（ⅱ）假定，选定为进基变量（可见进基变量的选法不变）。仍考虑
若唯一，则离基变量已确定；否则，考虑
若唯一，则据之确定离基变量；否则，继续考虑
直到选得唯一一个极小值，并据之确定离基变量为止。就是说，若求得唯一极小值为则即为离基变量。注意一定有u<n,否则AX=b中必有多余方程,应去之。上述比较大小亦称按字典式比较大小,故方法也叫字典序法。
下边对摄动法的正确性给予说明解释。
对（14）的典式作如下摄动：
(18)
式中的理解为充分小的正数。由于对初始基可行解如(ⅰ)，从而。故由摄动后的典式（18）得到的基解也是可行的。即；反之，若得到（18）的基可行解，由于 可以充分小，故必（否则，若某，由，必有。与可行性矛盾）。从而令，必得（14）的一个基可行解。以下说明理论上存在，使对任意。由典式（18）得到的基可行解均非退化（从而对这样的，迭代终止于有限步）。这是因为形如
即出现退化基可行解的值只能有有限个，加之方程个数和基本解的有限性，故上述存在。
最后由（18）的构造上可知的常数项中诸的系数，恰好是单纯形表中基变量这一行的系数，从而不必具体写出。并且由于可以充分小，故在比较大小时，若有，那么谁大谁小自然由比值和的大小决定了，这便是(ⅱ）
(二)、Bland方法
1976年Bland提出并证明[13]了一种用单纯形法进行计算时，避免循环的新方法，规则如下：
1、选取指标k=min{j|λj﹥0}，由此确定进基。
2、选取指标，由此确定离基。
Bland方法在理论上很有价值，而且规则简单，但具体计算时，迭代次数比摄动法要多。
§5 几点改进意见本节对单纯形算法提出以下几点改进意见.（一）按照使目标函数下降最多的原则确定进基和离基变量。这既能避免循环,又常减少迭代次数。（二）不直接引入人工变量求初始基可行解，并从寻基一开始就考虑目标函数的影响,从而使得到的初始基可行解尽可能地好。（三）把“两阶段法”简化为单阶段算法。
（一）新换基规则设所论问题由§1的初始单纯形表给出，据之，新换基规则可叙述如下：
(A)设，对每一，计算最小比值：
(19)
若不止一个，则取行下标最小的，转（B）。
(B)对满足（19）的所有，计算
(20)
若不止一个。则取列下标最小的，转（C）。
(C)以为主元实行Gauss消元，然后返回（A），直到R为空集或对某一，皆有，i=1,2,…m,为止。
可以证明[18]、[19]，对上述新规则，有以下性质定理5 对于每步迭代所面临的一切换基选择中，新规则是使目标函数下降最大者。
定理6 对于非退化问题（14），假定按新规则应选为主元，若主元所在的行还有其它元素满足最小比值（19），则有
（ⅰ）若以 为主元迭代一次后。相应的新检验数
（ⅱ）若以为主元迭代一次后，则至少
（ⅲ）若主元选在这一行，则最小比值的性质迭代后保持不变，即新比值及 t=1P仍满足（19）。
（ⅳ）若以为主元迭代一次，则新的基变量至少在下次迭代中不会离基。
当n>>m时，定理6的条件常被满足。
据定理6，可对新换基规则作如下进一步的说明：
设某行存在P>2个最小比值（当n>m时，此事总发生） t=1P，按单纯形法，迭代中可据任一正检验数确定进基变量。倘若限于在 中选取。则由定理6知。取使目标函数下降最大的为离基变量（设为）则迭代次数最少（仅一次）若执意不让 进基,而取别的，则变量将象走马灯一样换进换出，直到最后不得不让 进基为止,这期间增加的迭代次数,少则一步.多则可达P步。大家知道这种进基又离基（有的进去后马上离开）现象的多次出现，正是有时收敛慢的重要原因。由定理6，新换基规则避免或大大减少了这种现象的出现。
诚然，目标函数每步下降最多不能保证整体迭代次数一定最少，事实上对于存在最优解的任何一个（L P），从某一基可行解出发,都有一个步数最少的迭代程序，只是由于问题本身的五花八门，数据几乎又可以随机地任意选取，人们完全可以举出按最大正检验数确定进基变量迭代步数最少的例子；也能举出按Bland规则确定时迭代步数最少的问题。因此，试图找一个对任何具体问题迭代次数都最少的统一规则是根本办不到的。只能退而求其次，根据平均性态来区别优劣,大量事实例表明，按最大正检验数选进基变量比以往的其它方式效果好。这是因每迭代一步（以为主元）目标函数将下降。
(21)
因此，平均说来，与一般的相比，最大正检验数常使目标函数下降更大些，进而使总的迭代次数少些。但同时，由（21）知检验数最大，并不总能保证使（21）最大( 只是其中的一个因子)。可见就敛速说来新换基规则是平均性态下的最佳选择。
进一步还有定理7[18] 按新换基规则进行迭代，在任何情况下均不会出现循环，从而迭代终止于有限步。
我们已经知道，事先判断一个（LP）退化与否是十分困难的，因而在选择换基规则上常有顾此失彼之感：按最大正检验数换基吧，虽说一般效果好些，又怕万一出现循环；采用Bland规则或其它避免循环的方法，如摄动法吧，又顾虑问题本不会出现循环而白白增加迭代次数（或程序）。现在新换基规则既避免循环,又常能减少迭代次数，两方面都照顾到了，足见改进是实质性的。下面针对Beale给出的例4，用新换基规则求解：
x
-60 9 1 0 0
-90 3 0 1 0
0 0 0 0 0 1
0
0
1
f
-150 -6 0 0 0
0
-60 0 9 1 0
-90 0 3 0 1
0 0 0 0 0 1
1
f
-150 0 -6 0 0
0 -15 0 1
1 -180 0 6 0 2
0 0 0 0 0 1
1
f
0 -15 0 0
这里只迭代二次即得最优解，而若用Bland规则迭代6次才能得到最优解。
当然，按新换基规则每步要增加一些计算量，但这与减少一步迭代的计算量相比，一般要差个数量级。
（二）求初始基可行解的简化
引入人工变量求初始基可行解，虽然从程序上看与单纯形法无异，但一来导致系数矩阵扩大（一般要增加m列）引起存储和计算量增加，对大型问题可能使计算机容纳不下。二来没有考虑原目标函数的影响，致使得到的初始基可行解可能很“差”，徒增迭代次数。以下与新换基规则有关的改进程序，既不须明显地引进人工变量（不必增加系数矩阵的列），又能让迭代与原目标函数f挂钩，使得到的初始解尽可能地接近最优解，从而把两个阶段有机地结合起来。具体迭代步骤如下：
先针对（14）建立如下初始表
… …
… …
… …
… …
z
… …
f
… …
0
设R=，对每一jR，计算
(22)
对满足（22）的所有，计算
(23)
则为一基变量
4、以 为主元实行Gauss消元，并在 这行的最左端标以,然后返回2,直到R为空集为止，这时，如Z这行最右端的（一阶段的）目标函数值大于0，则原问题无解；若等于0，删之又会有两种可能。
（ⅰ）所选基变量的个数恰为m，则已得初始基可行解。
（ⅱ）所选基变量的个数,此时右端常数项列中必有m- 个0，且这些0所在的行左端未标出基变量（它们就是未被替换出来的那些人工变量）任取其中一行，然后以该行任一非0元素（若无非0元素，则删掉该行，说明有多余方程）为主元，实行Gauss消元，即增加一基变量，如此进行下去，最后必可得一基可行解。
根据两阶段法的理论，很容易看出程序的合理性。其关键在于这样一点：由于人工变量离基后，将它与相应的列去掉，不影响以后的寻优迭代，从而一开始就可以不必把它们留在单纯形表中。
由（22）、（23）的选基规则可以看出，我们的具体挂钩方法就是：在Z行的所有正检验数中每次选择使f下降最大者（若（23）为负实为上升最小者）为基变量。
用简化方法求解例3，迭代如下：
x
2 3 -1 5 6 -3
1 2 2 -2 -3 2
10
15
z
3 5 1 3 3 -1
25
f
5 3 4 -1 -2 1
0
4 0 4 -2
1 1 -1 - 1
z
4 0 4 -2
f
3 -1 0 3 4 -3
-30
1 0
0 1
7
4
z
0 0 0 0 0 0
0
f
0 0
-51
迭代二次所得的初始基可行解（7、0、4、0、0、0）即为最优解。比用二阶段法减少一半迭代次数。值得一提的是，上述所求初始基可行解即是最优解的现象，并非碰巧，许多计算实例表明，这是常有的现象，可见，这种简化处理是卓有成效的。
（三）单阶段算法考虑线性规划的标准型问题（14）：
对于这一问题，无论是“大M法”还是“两阶段法”，都要增加人工变量，这无疑扩大了问题的规模，增加存储。特别是常用的“两阶段法”，在一阶段的迭代中，仅仅是为了得到一个基可行解，而无暇顾及和考虑使目标函数下降这一重要环节。本文采用一定技巧，把求解线性规划的两阶段法转化成单阶段法，既略去了 人工变量减 少存储，又从一开始就可考虑目标函数的因素，往往能减少迭代次数和计算量。
算法迭代步骤
（）对目标函数系数由小到大排队，不妨设，依次选取为基变量，则经过（m-1）次Guass消元后，可得类似于下面的初始表：
表1
… …
…
1 0 … 0 …
0 1 … 0 …
… …
0 0 … 1 …
0 0 … 0 …
…
f
0 0 … 0 …
假设常数项（若，可用（-1）乘第m行，若，可用m行左边第一个非0系数，例如为主元实行一次Guass消元，然后再将m行与常数项不为0的行，例如m-1行交换即可），取适当大的正数M>0，使得以m行的M倍加于前面各行后，其常数项变为正数。这样做对前面已选的(m-1)个基变量无影响。因此，不妨假定这样处理后的结果仍如表1。
（）因，故若，则问题（1）无可行解，结束。否则，必有某j,mjn，使。对每一，计算最小比值，确定准主元。
(24)
再按最速下降规则选择主元，即对满足上式的i计算
(25)
然后以为主元实行一次Guass消元。继续上述过程直到选得的s=m时为止，转
（）按照通常单纯形法，继续迭代求优。
简单算例例1求解线性规划问题
解：构成初始表，依次迭代求解
x1 x2 x3 x4 x5
1* 1 1 1 1
-1 1 -1 1 0
2 0 3 0 -2
10
2
1
f
1 -1 -2 -3 -4
0
x1
1 1 1 1 1
0 2* 0 2 1
0 -2 1 -2 -4
10
12
-19
f
0 -2 -3 -4 -5
-10
x1
x2
1 0 1 0 1/2
0 1 0 1 1/2
0 0 1 0 -3
4
6
-7
f
0 0 -3 -2 -4
2
x1
x2
1 0 1 0 1/2
0 1 0 1 1/2
0 0 -1 0 3*
4
6
7
f
0 0 -3 -2 -4
2
x1
x2
x3
1 0 7/6 0 0
0 1 1/6 1 0
0 0 -1/3 0 1
17/6
29/6
7/3
f
0 0 -13/3 -2 0
34/3
由此知，
例2求解线性规划问题
解：构成初始表，依次迭代求解
x1 x2 x3 x4 x5
1 1 1 1 1
-1 -1 1 3 2
4 4 2 -2 6
10
6
28
f
-2 -3 1 1 -1
0
x3
1 1 1 1 1
-2 -2 0 2* 1
2 2 0 -4 4
10
-4
8
f
-3 -4 0 0 -2
-10
x3
x4
2 2 1 0 1/2
-1 -1 0 1 1/2
-2 -2 0 0 6*
12
-2
0
f
-3 -4 0 0 -2
-10
x3
x5
13/6 13/6 1 0 0
-1/3 -1/3 0 0 1
5/6* 5/6 0 -1 0
12
0
2
f
-11/3 -14/3 0 0 0
-10
x3
x5
x1
0 0 1 13/5 0
0 0 0 -2/5 1
1 1 0 -5/6 0
34/5
4/5
12/5
f
0 -1 0 -22/5 0
-6/5
由此知，
理论依据针对表1，添加人工变量，并引入一阶段的目标函数，准备实施“两阶段法”，则得如下之表（若考虑实行大M法，可类似的证明）：
表2
… … y
…
y
1 0 … 0 … 0
0 1 … 0 … 0
… …
0 0 … 1 … 0
0 0 … 0 … 1
…
z
0 0 … 0 … 0
易见，表（2）中第m行与一阶段的目标函数行（（m+1））行），如果不看人工变量，则是一样的，而且除非主元选在第m行，不然，则上述情形保持不变。因此，一阶段的迭代中，作为检验数的第m+1行可由第m行来代替而不必出现。而主元一旦选在第m行，易见，迭代后一阶段的目标函数全小于或等于0，这意味着已得到一阶段的最优解，同时亦得到原问题的一个基可行解，可以开始第二阶段的寻优迭代了。由于表面上的一阶段的目标函数行不出现，因而也省去了去掉的步骤。这样，我们便把两阶段迭代过程，通过单阶段加以实现，做到了最大限度的简化。
第六节 一种改型算法单纯形算法虽然不是多项式算法，却十分有效，且正普遍使用。人们还认识到复杂性概念只涉及到算法在最坏情况下的性态，而这种最坏情况在实际问题中发生的概率究竟有多大，并未予以考虑。这说明用算法在最坏情况下的性态来区别好坏不是最科学的，而算法的平均性态如何才是衡量算法好坏的更有说服力的标志。
有人于1982年证明，单纯形法是平均多项式算法。进一步，人们提出，能否存在单纯形法的某种改型，它是多项式算法，这是一个很有意义的问题，然而至今尚无定论。下面介绍一种改型算法，它在概率上是多项式的，但已十分接近多项式算法。
求基可行解经简单处理可将一般问题（14）写成如下形式：
（26）
对于（26）不必用计算最小比值求准主元，即可用Gauss消元求出n-1个基变量。此时（26）的约束方程的增广矩阵具如下形式：
（27）
对于（27），若，则问题（27）显然没有可行解。否则，至少
。进一步，如果还有：
(28)
则以为主元实行一次Gauss消元，即得问题（14）一个基可行解。
如果对（28）均不成立，说明以m行的任何非0元素为主元，实行Gauss消元后，都不会得到一个基可行解。因此必须在前(m-1) 行中先选一主元迭代一次后，再检查是否有（28）式成立。那么如何选择主元，以保证迭代后必有（28）式成立呢？经分析发现，如果主元选择，它应满足以下条件：
(29)
(30)
就是说，若（29），（30）均成立，则先后以和为主元，实行两次Gauss消元，即得问题（14）的一个基可行解。
若（29）和（30）不同时成立，则有以下几种可能：
一是对某一i，（29）不成立。这又分两种情形：一是该行没有异号的系数，即要么，要么，遇此情形只需令其中的非0系数对应的变量为0，即若，则令，结果第i个方程成为0=0的恒等式，故可去之，同时因，故其对应的系数列可去之（显然，若，则问题无可行解）。此举称为置0处理。可见问题经置0处理后，对剩下的，便总有>0及<0同时成立了。为简单计，不妨设问题事先已经置0处理了。故这时若对某一i，（29）不成立只能是下边的情形,
(31)
可以证明：若(31)成立,则问题一般无可行解[21];若（14）的数据是随机给出的，则于状态（27），存在满足（29）、（30）的列标j,s之概率一般已达到0.99[21]-[23]。这显然是理想的结果。
1 下面给出寻找满足（29）、（30）的列标j,s的一种方法。
容易看出，考察（29）、（30）的计算量主要在验证（30）成立上，注意对确定的i，（30）等价于，
（32）
采用（32）的好处在于，对指定的i,j,s,是固定不变的，只需计算一次，这样每次比较时只需计算就可以了，既方便又快捷，可节省一半计算量。
进一步，每每先固定i再寻找j和s也不是必要的、科学的，亦应有所选择，分析结果，按以下顺序和条件考察既方便又可使计算量最少，因而是最合理的。其中，当分母为0时，记
现任取一列，然后对其他列，依次筛选，满足以下条件的s,i
(33)
(34)
(35)
容易验证条件（29）、（30）与条件（33）、（34）、（35）是等价的。注意（33）式成立意味着，对于取定的一列j，则与j列正系数同行的其他列必为负，方可入选，这既容易判断，又不必计算分数值，我们称此条件为异号条件。具体考察时，宜先据（33），去掉不合异号条件的列，然后在余下的列任取一列，求出满足（33）的i，之后再检验（34）（它与（29）等价）是否成立；若不成立，弃之，另取一满足异号条件的列，重复求i的过程；若成立，最后再检验（35），直到找到满足（33）-（35）的i,j,s为止。
按上述过程寻找满足（29）、（30）的i,j，s可使计算量减少一个数量级。
求最优解
运用上述全搜索方法以往总是在求得一个基可行解后，再考虑按最小比值确定列准主元(即)，然后于i行令
(36)
(37)
容易验证，若成立如下最优性条件
(38)
则以为主元实行一次Guass消元，即得最优解。
若（38）不成立，则至少有一t，使,或,，进而迭代一次后，t列的新检验数必为正，称这样的t列为不谐列，并且选不谐列最少的为主元作为换基规则。这样做虽然效果很好，但求基可行解与寻最优解截然分开似不可取，应该将这两阶段有机结合起来，则效果会更好。事实上，当寻找基可行解时，一般会有多个满足（28）或有多对i,j,s满足（29）（30），应在其中选择不谐列最少的作为主元，则可减少迭代次数增加敛速。具体说来，就是对（它是准主元不成问题）考察使（38）不成立的不谐列数，选不谐列最少的作为主元，实行Guass消元。
[22]中指出，若不谐列只有一个，比如第t列，则该不谐列对应的变量一定是最优基变量，于是可优先安排该变量进基，并且不再离基。确切的说，若的检验数时，立即进基；若，下次迭代进基。
例子例 1 求解线性规划问题
（39）
解 把（39）化成形式（27），得如下初始表，然后按目标函数较小系数优先进基的原则迭代如下：
x
0 2 -2* 2 -3 0
0 1 -2 3 -2 1
-2 1 -1 0 0 1
0 -1 1 -1 3 1
0
0
0
1
f
-1 -1 2 -1 1 0
0
x3
0 -1 1 -1 3/2 0
0 -1* 0 1 1 1
-2 0 0 -1 3/2 1
0 0 0 0 3/2 1
0
0
0
1
f
-1 1 0 1 -2 0
0
x3
x2
0 0 1 -2 1/2 -1
0 1 0 -1 -1 -1
-2 0 0 -1* 3/2 1
0 0 0 0 3/2 1
0
0
0
1
f
-1 0 0 2 -1 1
0
x3
x2
x4
4 0 1 0 -5/2 -3
2 1 0 0 -5/2 -2
2 0 0 1 -3/2 -1
0 0 0 0 3/2 1*
0
0
0
1
f
-5 0 0 0 2 3
0
x3
x2
x4
x
4 0 1 0 1 0
2 1 0 0 1/2 0
2 0 0 1 0 0
0 0 0 0 3/2 1
3
2
1
1
f
-5 0 0 0 -5/2 0
-3
故有表中最后一步迭代虽然由于满足（28）,与均可为进基变量，但考虑到最优性条件（38）应选不谐列最少的，则宜选进基（此例中不谐列为0）
例2
（40）
把（40）化成形式（27），得如下初始表：
x
x4
x5
1 1 -1 1 0 -2
-2 -3 2 0 1 -1
2 1 2 0 0 1
0
0
5
f
10 15 12 0 0 0
0
初始表中已有2个现成的基变量和，故可直接考察满足（33）-（35）之i,j,s。容易验证，当j=1时，有s=3,6及i=1; 当j=2时，有s=3,6及i=1。再由最优性条件（38），检查它们的不谐列数，知当j=1时，即取为主元，不谐列数为3，而取为主元时，不谐列数为2，故取为主元实行Guass消元，结果如下：
x
x2
x5
1 1 -1 1 0 -2
1 0 -1 3 1 -7
1 0 3 -1 0 3*
0
0
5
f
-3 0 27 -15 0 30
0
x2
x5
x6
5/3 1 -1 1/3 0 0
10/3 0 6 2/3 1 0
1/3 0 1 -1/3 0 1
10/3
35/3
5/3
f
-13 0 -3 -5 0 0
-50
故有，其中最后一步迭代选择进基的理由与例1的相同，即它满足最优性条件（38）。
迭代次数分析对问题（26）的增广矩阵（27），若假定（29）成立，则对任一，易见存在，当把第i行的M倍加于各行后，可使s列的新系数（仍记为）
在作了上述处理后，容易验证，对满足（29）的j，s，条件（30）成立等价于
(41)
假定问题（26）的数据是随机给出的，则可认为最大比值（41）取集合中每个值的可能性是一样的，若该集合中有个元素，则（41）成立的概率，设想对(27),取一组满足(29)的j,s，检查它们是否满足（41），若不满足再另取一组检查，则（41）成立恰在第k次检查发生的概率为
若设，则进一步有
（42）
于是可算得下表：
h = 1 2 3 4 5 6 7 …
= 0.63 0.86 0.95 0.982 0.993 0.9975 0.9991 …
据上表可知，若检查5(m-1)组满足（29）的列j,s，则其中遇到使（41）成立从而得到可行解的概率已超过0.99。
那么（27）中最少能有多少组（设为Q）因满足（29）而可供检查的列j,s呢？（据此可算出为达到上述概率最多还需迭代）次。
仿照置0处理可证，若（27）中第i行里仅有一个正（或负）数，则与此系数对应的变量必为基变量，进而使问题简化。故按最坏情形考虑第i行至少应有2个正（或负）数，从而有(n-m-1)个负（或正）数（由于假定数据是随机选取的，故第i行m列以后出现事先指定数（比如0或两相同数）的概率为0 而不予考虑）。故至少可对应产生2(n-m)个不同的分数组
令，则分数组至少可达个。另外在随机的情况下，与这两种状态是等可能的，从而可以认为前者成立的概率为，现在检查上述N=2(m-1)(n-m)个数组中，使（29）成立的数组，则其不少于的概率按二项分布计算:
(44)
当N较大时，如N>36，可用德莫佛定理计算
(45)
总结以上知（27）中至少有个可供检查的数组，其中满足（29）的不少于的概率为，因此至多再迭代的次数为，若，则说明不必迭代。为使（29）、（30）同时成立的概率，若n-m，则至多需迭代一次；若n-m，则已不必迭代，并且仅要求m。
如果不从最坏情况考虑，而假定（27）第i行每一系数取正与取负的概率相等，即均为，则从中任取两数，其为异号的概率亦为，易见从(n-m+2)个数中任取两数成一组，共有种不同组合，其中异号的应占一半,而对，依照的计算可知其中异号数组不少于的概率为
这时可算得只需再迭代（用（44）式计算的）
次即可使（29）、（30）成立的概率达到0.99，若n-m,则不必迭代，并且只要求。简言之，通常在状态（27）下，即可搜索到满足（29）、（30）的，继之先后以为主元迭代两次，便可得一基可行解。
