Monthly Archives: March 2012

The Simplex Method

I just added a script which generates a random linear programming problem and executes the Simplex Method Method on it. 

The Simplex Method, originally discovered by George Dantzig, is one of the most important algorithms in computer science. It literally connects computer scientists to problems in mathematics, engineering, business, economics, transportation, and a host of problems that are faced by everyday people. For many of these problems, no one has yet discovered a pattern or a simpler means of solving it, other than the Simplex Method. Each of these problems has its own difficulties that distinguish it from other problems. While some such problems are important enough to receive their own studies to improve upon the efficiency of the simplex method (Network Flow problems come to mind), there are just too many problems for each one to receive such consideration. Thus we see the importance of the Simplex Method because it can solve these problems as long as they can be formulated as linear programming problems.

To understand the power of the Simplex Method, we need to understand a class of problems: linear programming problems. A linear programming problem is a problem where we seek to minimize/maximize a linear objective function (over finitely many variables) subject to a finite set of linear inequality constraints over these variables. A general example of a linear programming problem is “The Transportation Problem”.

The Transportation Problem Suppose you own a manufacturing company and its your job to ship your product from warehouse locations all across the United States to a number of customers. Each customer has ordered a certain quantity of the item, and each warehouse can supply up to a certain amount. Then we define the following variables:

m = the number of warehouses
n = the number of customers
ai = the total amount of item available at warehouse i
bj the total requirement of customer j
xi, j = the amount of item shipped from warehouse i to customer j.

In order for things to work properly, we need that the total amount in supply is equal to the the total amount ordered. If we assumed that we have 3 customers and 2 warehouses, then the following constraints help formulate this problem.

x1, 1 + x1, 2 + x1, 3 = a1
x2, 1 + x2, 2 + x2, 3 = a2
x1, 1 + x2, 1 = b1
x1, 2 + x2, 2 = b2
x1, 3 + x2, 3 = b3

You also know the cost of shipping one unit of the item from warehouse i to customer j and label it ci, j.

Then the objective function which we seek to minimze is c1, 1x1, 1 + c1, 2x1, 2 + c1, 3x1, 3 + c2, 1x2, 1 + c2, 2x2, 2 + c2, 3x2, 3.

And we also have that xi, j is nonnegative since we are shipping (and not receiving) goods.

Because we can state this problem as a linear programming problem, we can solve it using the simplex method. Although this problem was very simple to formulate, the ability to formulate a problem as a linear programming problem is seen as a great accomplishment because there exists so much literature on linear programming problems, and a method on how to solve them, (i.e. the Simplex method). For this reason, much work is often dedicated to finding good linear programming representations of problems.

Another set of problems of interest are integer programming problems. These problems add the additional requirement to linear programming problems that some or all of these variables can only take on a discrete set of values instead of a continuous realm. Integer programming problems are generally thought to be more difficult to solve than linear programming problems. What makes integer programming problems special is the fact that many problems that are known to be just as difficult as integer programming problems can be formulated as integer programming problems. Although the Simplex Method does not promise to always solve these problems to optimality, it offers a way to approach integer programming problems, and thus every problems that is known to be just as hard these problems which is at least a starting point.