Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

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.

-Doctor Daniel,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/

```
Associated Topics:
College Algorithms
College Definitions
High School Definitions

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search