Simplex method of solving linear programs

George Dantzig, the author of the paper mentioned in the previous post, developed the simplex method for solving linear programs. The algorithm exploits the fact the optimum point in a system of linear inequalities is always on the edge and never in the interior. For example, the system 0

The first step in the method is to find the edge. Once you’re there, you walk your way around the edge until you find the optimal point.

It turns out that this method is very efficient in most useful cases, but it gets bogged down in some special cases (i.e. when there are lots of variables and lots of conditions, but each condition only deals with a few variables… aka sparse matrices). There is ongoing research to determine algorithms that are more efficient in those special cases.


0 Responses to “Simplex method of solving linear programs”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s


%d bloggers like this: