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

• 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

• provides an efficient procedure for solving such large problems
• it uses methods from linear algebra
• the study of systems of linear equations
• using matrices

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

• teach the Simplex Method algorithm (computational procedure) per se

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

Constraints:

x₁ + 2x₂£ 32
3x₁ + 4x₂ £ 84
x₁, x₂³ 0

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:

• 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, s₁ and s₂ (one for each inequality):

x₁ + 2x₂£ 32
3x₁ + 4x₂ £ 84

• s₁ and s₂ are new variables that "take up the slack"
• between the left- and right-hand sides of the inequalities
• turning them into equalities (equations)

An interesting observation

We start with our system of equations:

• think of this as a system of 2 equations with 4 variables: x₁, x₂, s₁, s₂
• let s₁= 0 and s₂= 0 and solve the resulting system
• we (of course) get x₁= 20, x₂= 6, a corner point!

• let’s construct a Basic Solutions table that shows variables x₁, x₂, s₁, s₂
• set to 0 in all possible pairs
• with the tesulting system solved

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

• 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

• 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

• 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?

• 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

• 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 ₃₀₀C₂₀₀ = 4 x 10⁸¹ basic solutions
• if a computer computes one basic solution every millionth of a second
• it would take ~ 4 x 10⁷⁵ seconds to find them all
• now, # seconds in a year = 60 x 60 x 24 x 365 = 31536000 = ~ 3 x 10⁷
• so it will take ~ 4/3 x 10⁶⁸ years to complete the calculation
• the age of the universe is about 20 billion = 20,000,000,000 = 2 x 10¹⁰ years

• 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!