An overview on the simplex algorithm

In this paper, the simplex algorithm and its variants are investigated. First, we define a new concept called formal tableau, which leads to derive easily the dual solution from the latest primal table; without any distinction between the original variables and the slack ones. Second, we propose a new method for initializing the simplex algorithm. Unlike the two-phase and the big-M methods, our technique does not involve artificial variables. The computational results reveal that this new method is very favorable especially when the number of artificial variables is significant. Finally, this method will be combined with the notion of formal tableau leading naturally to a second new approach.     

George Dantzig’s impact on the theory of computation

George Dantzig created the simplex algorithm for linear programming, perhaps the most important algorithm developed in the 20th century. This paper traces a single historical thread: Dantzig’s work on linear programming and its application and extension to combinatorial optimization, and the investigations it has stimulated about the performance of the simplex algorithm and the intrinsic complexity of linear programming and combinatorial optimization.     

基于指数型核函数的线性规划原始对偶内点算法

给出线性规划原始对偶内点算法的一个单变量指数型核函数.首先研究了这个指数型核函数的性质以及其对应的障碍函数.其次,基于这个指数型核函数,设计了求解线性规划问题的原始对偶内点算法,得到了目前小步算法最好的理论迭代界.最后,通过数值算例比较了基于指数型核函数的原始对偶内点算法和基于对数型核函数的原始对偶内点算法的计算效果.