The first method proposed to solve linear programming problem is the well known Simplex method developed by G.B. Dantzig in the early fifties. As we will soon see, this method uses essentially a combinatorial approach.
Later on important results were obtained by studying the behavior of algorithms already known for general convex programming when applied to the particular case of linear programming.
The first result in this sense was obtained by Khachian who proposed a theoretical method, called ellipsoid method, which even if not effective for practical purposes, allowed him to prove that Linear Programming could be solved in polynomial time.
A few years later Karamakar proposed a projective interior point algorithm which is radically different from the simplex method and that appears to have a great efficiency in solving very large size instances.
We will now briefly describe the first of these methods, the simplex method. To introduce it we firstly need to go over some definitions and geometric properties of linear programming.