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/