LP問題におけるKarmarkar法について

概要

論文の詳細を見る
Since G.B.Dantzig proposed Simplex Method for solving the linear programming problems, a lot of extensions and versions of the simplex method have been presented. However the simplex method is basically considered to be most efficient and stout algorithm at the point of pratical algorithm. Nevertheless, the simplex method is said to be the exponential type algorithm esentially for the large scale linear programs. In 1984,Karmarkar proposed a polynomial type algorithm. In these days, the polynomial type algorithm is very attractive algorithm comparing with the exponential one. In this paper, we present the basic concept of Karmarkar s algorithm and discuss the efficiency of the classical simplex method and Karmarkar's one as a actual use of practical algorithm. As a results of our numerical simulation, we conclude that Karmarkar s algorithm is not so good at the points of practical usgein spite of its attractiveness in theory.
岡山理科大学の論文