一种改进的无人工变量单纯形算法

AN IMPROVED ARTIFICIAL-FREE SIMPLEX-TYPE ALGORITHM

对Arsham的算法作了重要改进以便使其运行得更好,目标使所有基人工变量之和最小。首先,对非基变量按其简约价值系数从大到小逐列向前搜寻,将满足条件的变量带入基变量集,当简约价值系数为非正时终止。然后,以目标当前值与最优值的均值作为临界值,应用经典单纯形算法求解,当目标值超过临界值时,重复上述过程,直至基变量集处于完全状态。在计算机上对24个标准测试问题进行初步数值试验,计算结果表明,本文提出的改进算法比经典单纯形算法所用的总迭代次数要少得多,在22个问题上耗费更少的计算时间,大大改进了Arsham算法的计算效率,比Gao的一种改进算法的计算性能更稳定,因而是有价值的。

We propose the improvement of Arsham＇s algorithm to make it work well. Firstly, our improvement is searching for the nonbasic variables into BVS column by column in only one pivot sequence from large to small according to the positive of the reduced costs of the nonbasic variables. Secondly, taking the average of current and optimal objective values as a threshold, we apply the ordinary simplex algorithm to the problem with the minimization of the sum of all artificial variables. When the objective value is larger than or equal to the threshold, continue the above process until a complete BVS is found. Finally, a computer implementation is accomplished to test the efficiency of our improvement comparing to the ordinary simplex algorithm on 24 standard test instances. The computational results show that our improved algorithm uses less iteration in total, and spends less executive time on 22 instances than the ordinary simplex algorithm, and has more stable computational performance than the GAO＇s algorithm, and thus is of interest.