(Page 1 of 1)

 

In the previous section, we looked at the geometry of linear programming. Without going into an elaborate proof, we provided some intuition to why "normal" linear programs have optimal solutions at corners. We say "normal" because we need to ignore infeasible or unbounded LPs which don't have optimal solutions at all.

This leads us to believe that if we could list all the corner points of our feasible region, we could calculate the objective value at each and take the best one. Given that there is always a corner point optimal solution, we would be assured that this process would give us an optimal solution. Note that there may be others (as we saw in the second example) but we would have found one optimal solution.

This raises two questions: 1) How do we find the corners? and 2) What if there are a lot of corners?

Well, like many things there are short answers to these questions and long ones. We will provide short answers here, but there is a wealth of insight that can be gained by understanding the longer, more formal answers.

First, how do we find the corner points? You should notice that corners occur where constraints intersect. In 2-dimensions, they occur where 2 constraints intersect. In 3-dimensions, they occur where 3 constraints intersect. And, you guessed it, in n-dimensions, they occur where n constraints intersect.

 

Finding where n constraints intersect is a matter of solving a system of n equations which we can do efficiently using Gaussian elimination. Therefore, we can find our corner points by solving a series of systems of n equations.

 

But what if there are a lot of corners? You can imagine even in 3-dimensions a polyhedron with hundreds or even thousands of corner points. Surely we don't need to find them all. We would like to be intelligent about which corners we consider.

This brings us to the Simplex Method. This is an efficient approach for solving linear programs and is currently the method used in most commercial solvers.

In essence, the simplex method intelligently moves from corner to corner until it can be proven that it has found the optimal solution. Each corner that it visits is an improvement over the previous one. Once it can't find a better corner, it knows that it has the optimal solution.

 

Needless to say, this is a quick description and there are many interesting features of the algorithm, but we will leave it at this. For the purpose of solving most LPs with commercial solvers, this basic understanding of the algorithm will suffice.