关键词: 线性规划, 单纯形法, 列生成方法, 列消除, 表上作业法

Abstract: 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.

Key words: linear programming, simplex method, column generation method, column elimination, transportation simplex method