The Simplex Method
Date: 11/2/96 at 4:42:29 From: Reinier Broker Subject: What is the simplex-method? I've heard about something called the simplex method. It was developed by a Russian during World War II. My teacher can't tell me the method, so I was hoping that you could. Regards, Reinier PS: Could you also explain it?
Date: 11/2/96 at 19:12:15 From: Doctor Rob Subject: Re: What is the simplex-method? Reinier, The simplex method is an algorithm for solving the Linear Programming Problem. The problem is to find a set of nonnegative real numbers satisfying a set of linear inequalities which maximize a linear function. As an example, I might want to find a simultaneous solution to the inequalities x >= 0 y >= 0 z >= 0 x + 2y + 3z =< 30 3x + y + 2z =< 30 2x + 3y + z =< 30 which makes the value of F = x + y + z as large as possible. The region of common solutions forms a convex solid in the first octant in real 3-space. The equation F = constant represents a family of parallel planes. The one farthest from the origin which just touches the solid will give the greatest value of F. The trick is to find it. The first observation is that if one of the planes just touches the solid, then it will touch it at a vertex or corner. The simplex method is a way of moving from one vertex of the solid to another, to another, always increasing the value of F. When this can't be done any more, the solution has been found. The coordinates of the vertex reached give the values ofthe variables (x, y, z). In the example, (5, 5, 5) is the solution, with F = 15. The details of the method are too lengthy to give here. -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Date: 11/3/96 at 10:56:53 From: R. Broker Subject: Re: What is the simplex-method? Thanks for your quick response, but I already know that part. It becomes nice with 4 parameters instead of 3. You can't draw it any more, so I've heard that you should start with using a matrix. How does that work??
Date: 12/13/96 at 16:47:37 From: Doctor Daniel Subject: Re: What is the simplex-method? To do a quick review, the simplex method is an algorithm which solves a linear programming problem. (Incidentally, it wasn't, to the best of my knowledge, developed by a Russian. Its developer is Prof. Dantzig, who's still a rather old professor in the Dept. of Operations Research at Stanford.) The simplex method relies on noticing that the maximum of the objective function must occur on a corner of the space bounded by the constraints (the "feasible region"). It then starts at a corner of the feasible region and keeps trying to increase the objective function by finding an edge to move in which the function will increase, and does this until there is no direction to go, at which point it's at the optimum. Probably the best way for you to find a good explanation of the method is to look at an introductory text on operations research. A good standard text is Winston's _Operations Research_, but any book on the field will spend quite some time on simplex. (Several whole books on the topic exist!) This is especially true since a good explanation will include pictures, several examples, etc. It's a really important problem, actually; linear programming ranks as probably one of the ten most common problems solved by scientific computation programs. Here's a quick answer to your second question: Suppose that your constraints are something like maximize: c1 x1 + c2 x2 + ... + cn xn subject to: a11 x1 + a12 x2 + ... a1n xn <= b1 a21 x1 + a22 x2 + ... a2n xn <= b2 ... am1 x1 + am2 x2 + ... amn xn <= bm Then, if you think about the matrix A, whose i,j-th entry is aij, the column vector x, whose ith entry is xi, the column vector c, whose ith entry is ci, and the column vector b, whose ith entry is bi, you can see that this problem can be written as: max c' * x subject to: A * x <= b, where c' is the transpose of c (that's a row vector). It's also not hard to show that a problem of this form can actually be turned fairly easily into a problem of the form: max c' * x subject to A * x = b, x >= 0 (the A matrix, x vector, c vector and b vector change, but the general rule holds; if we solve the related problem of this form, getting back to the x vector we're looking for is trivial.) Again, though, this will take quite a while to explain. I'd really recommend going to the library and finding a book. Seeing examples helps a lot. Thanks for your question, -Doctor Daniel, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.