Solving linear programming problems via linear minimax problems

摘要

This paper gives a new method to solve a class of linear programming problems. We transform the problem to a linear minimax problem, and introduce the concept of weighted center, which is on the intersection of two planes. Using this property of the weighted center, we can find successively the intersections of the 2, 3,..., n + 1 top planes. The last intersection is just the solution of the linear minimax problem. We can then obtain the solution of the linear programming problem by transforming the solution back to the original space. However, the transformation is not necessary, and we can find the solution of the linear programming problem directly. The complexity of this method is less than O(n4), and so it is a polynomial algorithm. Numerical examples are given to show its efficiency.