关于“线性规划的符号跟踪算法”的注记

唐沧新，高培旺

（1.广西财经学院 信息与统计学院，广西 南宁 530003；2.闽江学院 数学系，福建 福州 350121）

0 引言

单纯形法因其在枢轴主元选择中的灵活性而引起许多研究者的兴趣，进而产生了许多变式，如MBU单纯形算法［1］、梯度单纯形算法［2-3］、原始——对偶单纯形算法［4］。文献［5］也提出了一种单纯形算法的变式，称其为符号跟踪算法，其思想受到一个约束条件的最简单情形的启发而产生，即对某个约束条件而言，正系数所对应的变量中必有一个是最优基变量，因而正系数是寻找最优基变量的有效途径之一。应注意到的是含多个约束条件的线性规划问题远比只含一个约束条件的简单情形复杂得多。

针对文献［5］中提出的问题，本文指出“线性规划的符号跟踪算法”所获得的初始基并不一定是原问题的最优基，实际上是第一阶段单纯形算法的一种变式，只不过辅助目标函数没有写出来而加入了原问题的目标函数。由于在入基变量的选择中没有遵循最小列检验比准则，右手边有可能产生负数项，因而该初始基还有3种其他情况。文献［6］给出的算法也存在这个问题，文献［7-8］对此进行了指正。尽管如此，本文拟探讨由此初始基出发，对符号跟踪算法的步骤进行适当修正和补充后，能否更快地到达原问题的最优顶点（如果存在）。为此，我们从线性规划标准测试库NETLIB［9］和混合整数规划标准测试库MIPLIB［10］中选取了 26 个典型算例，通过 MAT⁃LAB编程在计算机上实现大规模数值试验，以此检测该算法的计算效率。

1 符号跟踪算法的描述及补正

考虑如下形式的线性规划问题：

这里，A∈Rm×n（m＜n），且假定 rank(A)=m，c、b是相应维数的向量，且b≥0。

不妨设B、N分别是（LP）系数矩阵的基与非基子矩阵，cB、cN分别是基与非基相应的费用系数向量。众所周知，当=B-1b≥0时，基B是原始可行的；当判别检验数σ=cBB-1A-c≥0时，基 B是对偶可行的；而当≥0且σ≥0时，基 B既是原始可行又是对偶可行的，因而是最优的。

符号跟踪算法的原理可简述为：基于“在正系数个数最少的约束条件中，正系数所对应的变量中必有一个为最优基变量”的推断，在所有约束条件中找出正系数个数最少的约束（所在行）作为枢轴行，然后通过判别检验数与该约束的正系数之比的最小值确定枢轴列，以搜寻可能的最优基变量。然而，这个推断是基于一个约束条件的简单情形，由此推广到含多个约束条件的复杂问题并没有理论支持。实际上，符号跟踪算法的枢轴准则是使正系数对应的判别检验数在迭代之后转化为非负值，仅此而已。因此，符号跟踪算法不能保证右手边向量非负，也不能保证在初始基产生后，所有判别检验数全部转化为非负值。具体来说，符号跟踪算法获得的初始基（用B表示）有下列4种可能情形：

由此可见，符号跟踪算法仅仅求得原问题的一个初始基而非最优基（当然这个初始基有可能是最优基），是第一阶段单纯形算法的变式。由于忽略了这个事实，导致符号跟踪算法第一步的步骤（3）的结论是错误的。当原问题的初始基还未产生，亦即还存在人工基变量时，若存在某个σs＜0，且该列所有系数ais≤0，并不意味着“原问题有无界解”。如果把第一阶段辅助目标函数写出来，该列所对应的辅助目标函数的判断检验数肯定大于或等于零，因为第一阶段问题总是有界的。旋转迭代过程按照第一阶段单纯形算法可以继续进行下去，直到获得原问题的一个初始解或无可行解的结论。另外，为算法编程处理方便起见，在未产生基决策变量（即含人工基变量）但右端项为负的约束中，以负系数作为搜寻“最优基变量”的基准，这与“方程两边乘以-1，再以正系数为基准选择最优基变量”是等价的。

根据上述对符号跟踪算法的分析，我们对符号跟踪算法步骤给出适当修正和补充，详细描述如下：

步骤1 记Arf代表还未产生基决策变量的行标集合，一开始，Arf={1，2，…，m}，转下一步。

步骤2 若Arf=∅，原问题的初始基B产生，转步骤3。否则，对任意 i∈Arf，如果≥0，计算第 i个约束中正系数的个数 numi，转步骤4；如果＜0，计算第i个约束中负系数的个数numi，转步骤5。

步骤4 如果 numi=0，当＞0时，原问题无可行解，算法结束；当i=0，该约束为冗余约束，置Arf=Arf{i}，将其去掉。否则，有numi＞0，转步骤6。

步骤5 如果numi=0，原问题无可行解，算法结束。否则，有numi＞0，转下一步。

步骤6 求得所有numi后，取指标r=arg min{numi}作为枢轴行，转下一步。

通过执行上述算法步骤，我们或者获得（LP）的一个基本可行解，或者得到一个没有可行解的事实。

2 符号跟踪算法的数值试验

尽管符号跟踪算法求得的初始基不一定是原问题的最优基，但如果由此获得的初始解位于最优顶点的附近，就可以通过更少的迭代次数到达最优顶点。然而，符号跟踪算法的枢轴准则增加了计算的复杂性，如果这种计算复杂性能通过减少迭代次数得到弥补，使耗费的总的计算时间更少，那么符号跟踪算法是有意义的。因此，有必要通过大规模数值试验对符号跟踪算法的计算效率进行检验。

笔者从线性规划标准测试库NETLIB［9］和混合整数规划标准测试库MIPLIB［10］中选取了26个典型算例，其中，问题 air01、enigma、lp41、mod010属于整数规划问题，我们只求其相应的线性规划松弛问题的解。接下来，使用MATLAB V7.1语言对经典单纯形算法和符号跟踪算法进行编程，在Lenovo ThinkCenter M9201z计算机上执行对所选取的26个算例的数值试验，以对两种算法的计算效率进行比较。数值试验的环境是完全相同的，计算结果如表1所示，其中，Iters表示求解线性规划问题所需要的枢轴（迭代）数，Time表示所耗费的总的计算时间（单位为s）。另外，用Type表示在符号跟踪算法中所获得的初始基的类型，看看出现第一种类型的问题有多少。

从表1看到，符号跟踪算法求解26个算例产生的初始基没有第一种类型的，这再一次印证了本文前面的分析。在迭代求解过程中，符号跟踪算法在18个算例中所使用的迭代次数确实比经典单纯形算法少，甚至在问题air01、scsd1、lp41、mod010中所用迭代次数远远少于经典单纯形算法，这说明符号跟踪算法获得的初始解一般都比较靠近原问题的最优顶点。然而，由于在枢轴行和枢轴列的选择中耗费了过多的计算时间，除问题israel、air01外，符号跟踪算法在其他24个问题上所耗用的总的计算时间比经典单纯形算法还要多。特别是，符号跟踪算法在问题scsd1、lp1、mod010上所使用的迭代次数不及经典单纯形算法的一半，却耗用了比经典单纯形算法更多的计算时间。可见，符号跟踪算法枢轴准则的计算复杂性不能从迭代次数的减少中得到补偿。一般地，符号跟踪算法平均每次迭代要花费更多的执行时间，导致符号跟踪算法的计算效率较低。

表1 经典单纯形算法与符号跟踪算法的计算比较

3 结论

修正（对偶）单纯形算法在枢轴列（行）的选择计算中是最简单的枢轴准则之一，且在每次迭代之后，只需计算基逆矩阵和枢轴列（行）的系数，计算过程简单而方便，旋转迭代计算对所有单纯形变式都是一样的。因此，修正（对偶）单纯形算法的运算量相对而言是较小的。经典单纯形算法的缺陷之一是从一个顶点迭代到另一个与之相邻的顶点，导致迭代进程太慢，尤其是接近最优顶点的时候。

Enge和Huhn［11］指出，逐列（行）搜寻枢轴主元的过程会带来指数时间的计算工作量，从而造成总的计算效率下降。本文通过对中大规模问题的数值试验证实了这一点。可见，要找到一个好的单纯形枢轴准则和计算方法，以进一步改进经典单纯形算法的计算效率并不是一件容易的事情，需要我们不断地思考和尝试，进行严谨的理论分析和大规模数值试验。

［1］Anstreicher K M，Terlaky T.A monotonic build-up sim⁃plex algorithm for linear programming［J］.Operations Research，1994，42（3）：556-561.

［2］Forrest J，Goldfarb D.Steepest-edge simplex algorithm for linear programming［J］.Mathematical Program⁃ming，1992，57（1）：341-374.

［3］Vemuganti R R.On gradient simplex methods for linear programs［J］.Journal of Applied Mathematics and Deci⁃sion Sciences，2004，8（2）：107-129.

［4］Curet N D.A primal-dual simplex method for linear programs［J］.Operations Research Letters，1993，13（5）：233-237.

［5］唐建国.线性规划的符号跟踪算法［J］.运筹与管理，2005，14（3）：55-59.

［6］唐建国.线性规划的目标函数最速递减算法［J］.运筹与管理，2005，14（4）：55-59.

［7］夏少刚，郑直，费威.与“求线性规划问题可行基的一种方法”的再商榷［J］.运筹与管理，2006，15（3）：16-24.

［8］夏少刚.线性规划联合算法的理论和应用［J］.运筹与管理，2004，13（1）：3-8.

［9］Browne S，Dongarra J，Grosse E，et al.The Netlib mathematical software repository［J］.D-Lib magazine，1995，1（9）：1-3.

［10］Bixby R E，Ceria S，McZeal C M，et al.An updated mixed integer programming library：MIPLIB 3.0［J］.Optima，1998，54（1）：12-15.

［11］Enge A，Huhn P.A counterexample to H Arsham's“Ini⁃tialization of the simplex algorithm：an artificial-free approach”［J］.SIAM Review，1998，40（4）：1-6.