5-3 Introduction to the Simplex Method

The nature of and reason for the Simplex Method

The geometric method for solving linear programming problems shown in 5-2

• only works for two-dimensional problems, i.e.
• problems that have two variables
• it requires solving a system of equations for every corner point
Real-life optimization problems:
• may have thousands of variables
• and thousands of constraints
• which means astronomical numbers of corner points
• making the above technique impossible ...
• even on super-computers
The Simplex Method:
• provides an efficient procedure for solving such large problems
• it uses methods from linear algebra
• the study of systems of linear equations
• using matrices
It was invented by
George Dantzig
Born: 8 Nov 1914 in Portland, Oregon, USA

For more on Dantzig, click here.  The following is an excerpt from that page:

In 1947 Dantzig made the contribution to mathematics for which he is most famous, the simplex method of optimisation. It grew out of his work with the U.S. Air Force where he become an expert on planning methods solved with desk calculators. In fact this was known as "programming", a military term that, at that time, referred to plans or schedules for training, logistical supply or deployment of men.

Dantzig mechanised the planning process by introducing "linear programming", where "programming" has the military meaning explained above. The importance of linear programming methods was described, in 1980, by Laszlo Lovasz who wrote:-

If one would take statistics about which mathematical problem is using up most of the
computer time in the world, then ... the answer would probably be linear programming.

Also in 1980 Eugene Lawler wrote:-

[Linear programming] is used to allocate resources, plan production, schedule workers,
plan investment portfolios and formulate marketing (and military) strategies.   The versatility  and economic impact of linear programming in today's industrial world is truly awesome.

Dantzig however modestly wrote:-

The tremendous power of the simplex method is a constant surprise to me.

This section introduces:

• concepts and vocabulary associated with the Simplex Method
It does not:
• teach the Simplex Method algorithm (computational procedure) per se

An example

We will use the following example (from the book):

Constraints:

x1 + 2x2£ 32
3x1 + 4x2 £ 84
x1, x2³ 0
Objective function:            P = 50x1 + 80x2

Although the Simplex Method does not rely on graphing, the basic concepts of the method can be illuminated by examining the geometric solution of the system:

Slack variables
• since the constraints are in terms of inequalities
• and since the linear algebra methods used by the Simplex Method deal in equations
• we will rewrite the £ constraints as equations
• by introducing slack variables, s1 and s2 (one for each inequality):
x1 + 2x2£ 32
3x1 + 4x2 £ 84
become x1 + 2x2+ s1 = 32
3x1 + 4x2+ s2 = 84
(notice that we must have s1³ 0 and s2 ³ 0)
• s1 and s2 are new variables that "take up the slack"
• between the left- and right-hand sides of the inequalities
• turning them into equalities (equations)

Using slack variables to find corner points

An interesting observation

x1 + 2x2+ s1 = 32
3x1 + 4x2+ s2 = 84
• think of this as a system of 2 equations with 4 variables: x1, x2, s1, s2
• let s1= 0 and s2= 0 and solve the resulting system
• we (of course) get x1= 20, x2= 6, a corner point!
• let’s construct a Basic Solutions table that shows variables x1, x2, s1, s2
• set to 0 in all possible pairs
• with the tesulting system solved
Basic Solutions
 x1 x2 s1 s2 corner point? 0 0 0 0 0 0 0 0 0 0 0 0

Now, using our equations, we solve for the other two variables, getting

Basic Solutions

 x1 x2 s1 s2 corner point? 0 0 ·· ·· ·· 0 ·· 0 ·· ·· 0 ·· ·· 0 ·· 32 0 0 -12 ·· 28 0 4 0 ·· 20 6 0 0 ··
• notice that some basic solutions include negative slack variables
• slack variables have to be positive
• it can be shown that . . .
• only those solutions with all positive slack variables will be corner points
• such solutions are called basic feasible solutions
• this method for finding corner points works …
• even when there are more than 2 variables
• or more than 2 inequalities
It can be shown mathematically that:

 in a constraint system that has n variables and m inequalities if you introduce m slack variables, creating m equations with n + m variables and  you set the variables  (including the slack variables)  equal to 0, n at a time and solve for the other m variables then the corner points of the system will be exactly those solutions having no negative slack variables this result gives us an algebraic (no graphing needed!) method for finding corner points

Terminology
• the variables you set to 0 are called nonbasic variables
• the variables you solve for are called basic variables
• a solution is called a basic solution
• a solution that represents a corner point (no negative slacks) is called a basic feasible solution

Summary and caveat
• we have described a way to organize the math without using graphs, that is
• we have demonstrated an algebraic way to find corner points
• we can now finish the solution as before
• by finding which corner point maximizes (or minimizes) the objective function
• and we are done!
• isn't this good?
this is still not good, and here's why:
• if you have 5 inequalities and 3 variables
• you will introduce 5 slack variables
• creating a system of 5 equations with 8 variables
• you set 3 of the variables to 0 at a time, and solve
• reducing the system to a system of 5 equations with 5 variables
• to obtain a basic solution
• you will have to do this (8)(7)(6)÷(3)(2)(1) = 56 times (whew!) to get
• 56 basic solutions
• (where does the (8)(7)(6)÷(3)(2)(1) come from? see chapter 6!!!)
• 56 basic solutions would take a lot of time by hand
• but for a computer, it's a snap
• a few seconds, at most
BUT
• suppose we have a larger system: 100 inequalities and 200 variables?
• but still small
• compared to most real situations for which the Simplex Method is used
• that's going to be 100 equations and 300 variables
• which will give 300C200 = 4 x 1081 basic solutions
• if a computer computes one basic solution every millionth of a second
• it would take ~ 4 x 1075 seconds to find them all
• now, # seconds in a year = 60 x 60 x 24 x 365 = 31536000 = ~ 3 x 107
• so it will take ~ 4/3 x 1068 years to complete the calculation
• the age of the universe is about 20 billion = 20,000,000,000 = 2 x 1010 years
1058 ages of the universe to solve one small problem?
• well . . .
• the Simplex Method makes use of the above ideas
• but provides a method for getting to the optimum solution
• without having to find every corner point! (WHEW!)
• unfortunately, we lack the time necessary to develop the complete Simplex Method
• at least with any kind of understanding of how it works!