5-3 Introduction to the Simplex Method

Topics
The nature of and reason for the Simplex Method
An example
Slack variables
Using slack variables to find corner points
Terminology
Summary and caveat



The nature of and reason for the Simplex Method

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

Real-life optimization problems: The Simplex Method: 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:

It does not:
An example

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

Constraints:

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 become x1 + 2x2+ s1 = 32
3x1 + 4x2+ s2 = 84
(notice that we must have s1³ 0 and s2 ³ 0)



Using slack variables to find corner points

An interesting observation

We start with our system of equations:

x1 + 2x2+ s1 = 32
3x1 + 4x2+ s2 = 84
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
··
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
Summary and caveat
this is still not good, and here's why:
BUT
1058 ages of the universe to solve one small problem?