唐沧新，高培旺

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

0 引言

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

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