Simplex method of solving linear programs George Dantzig, the author of the paper mentioned in the previous post, developed the simplex method for solving linear programs. The algorithm exploits the fact the optimum point in a system of linear inequalities is always on the edge and never in the interior. For example, the system 0 <= x <= 1 and 0 <= y <= 1 is a box. It can be shown that the optimum point is somewhere on 1X1 square (furthermore, the optimum is at one of the vertices... [0,0], [0,1], [1,0] or [1,1]).

The first step in the method is to find the edge. Once you're there, you walk your way around the edge until you find the optimal point.

It turns out that this method is very efficient in most useful cases, but it gets bogged down in some special cases (i.e. when there are lots of variables and lots of conditions, but each condition only deals with a few variables... aka sparse matrices). There is ongoing research to determine algorithms that are more efficient in those special cases.
  ¶ 9:35 PM