检验数替换价值系数单纯形法的若干讨论

Discussions on the Simplex Method Based on Replacing Cost Coefficients with Reduced Costs

用检验数替换价值系数来实施单纯形法是新近提出的一种方法,可以有效提高求解线性规划的计算效率,能够使单纯形法的一些性质和特征变得显而易见。本文将给出该方法的三个应用:(1)揭示原模型和对偶模型之间的直接联系,更深入地诠释对偶理论的无界性;(2)提出新的列消除规则,可有效降低单纯形法的计算规模,改进了计算大规模线性规划的列生成方法;(3)可以简化表上作业法之位势方法,使得其计算效率总可提升一倍。因此,这种新方法极大地丰富了单纯形法的理论,而且还可提高单纯形法的计算效率。

Linear programming is a basic research field of operations research.Since 1947,numerous algorithms have been proposed,which are mainly divided into three categories:Simplex method,ellipsoid method and interior point algorithm.In view of the inherent warm start technique of simplex algorithm and its natural advantages in solving integer programming,it still has competitive advantages compared to the interior point algorithm.This shows that the improved simplex algorithm still has important theoretical and practical value.At present,simplex method mainly has three variants,namely,the primal simplex algorithm,the dual simplex method and the primal-dual simplex method.Compared with the traditional simplex algorithm,the newly simplex method based on replacing cost coefficients with reduced costs neither changes the computed results nor the number of iterations,but it improves the efficiency of computing reduced costs.In fact,as an improvement of simplex methods,this method doesn’t change existing pivoting rules,which is its prominent feature.It can also make some properties and characteristics of the simplex algorithm become obvious.Furthermore,the new algorithm helps to develop or improve algorithms for some operations research problems,and it can make the computational process simple.In the paper,the new algorithm will further be investigated.Firstly,the new algorithm can not only reveal the inner relationship between primal models and dual models more deeply,but also provide intuitive proof and explanation for the boundedness property of dual theory of linear programming,which is often proved by contradiction.Secondly,a new column elimination rule is proposed.For a variable,if its reduced cost is negative in the k-th simplex tableau and its column vector is non-negative in the r-th simplex tableau,we can eliminate the column of this variable from the model which make the new model with the column deleted have the same optimal solution as the original model.It can effectively reduce the computational scale of linear programming.Thirdly,we can apply the above column elimination technique to improve the column generation method to solve effectively large-scale linear programming models.The new column generation method is very suitable for linear programming problems where most column vectors are nonnegative.Our experiments show that the algorithm only costs three iterations to eliminate approximately 75%variables from the original linear programming model for 100 random generated models with 20 basic variables and 80 non basic variables.Finally,the new algorithm can also simplify the potential method of transportation simplex method and computational efficiency can always be doubled at least.In fact,transportation simplex method is known to be the most competitive algorithm for transportation problem in practice.The new potential method provides a new formula for computing reduced costs,in which the cost of variable is always replaced by the last iteration’s reduced cost of variable.Generally,we still use the given costs to compute reduced costs of variables in the first iteration.It means that only one dual variable is nonzero in m+n dual variables,which help to explain why reduced costs of many variables don’t change.In conclusion,as a variant,the simplex method based on replacing cost coefficients with reduced costs can not only directly improve the computational efficiency of the primal simplex method,dual simplex method,primal-dual simplex method and other simplex methods,but also it can improve goal simplex method,transportation simplex method,branch and bound method and other algorithms based on the simplex method.Therefore,the new method not only greatly enriches the theory of simplex method and dual theory in linear programming,but also improves the computational efficiency of simplex method.It should be pointed that the method helps to propose new pivoting rules for simplex method.