Finite Mathematics Lesson 4

Section 4.1 and Section 4.2 Example 1
Example 2

Chapters 4.1, 4.2

You just learned a method for solving linear programming problems using a graphical approach.  This method is not practical if there are more than 2 variables in the the problem.  Many business or economics problems may involve thousands  or millions of variables.  Chapter 4 introduces a new method to handle these problems more efficiently.  The simplex method is an algorithmic approach and is the principle method used today in solving complex linear programming  problems.  Computer programs are written to handle these large problems using the simplex method.

Just a little history on the simplex method
   George Dantzig 'invented' the simplex method while looking for methods for solving optimization problems.  He used a primitive computer in 1947 to achieve his success in developing the simplex method.  Dantzig is currently a professor of operations research and computer science at Stanford. 

    In 1984, Narenda Karmarker, a research mathematician at Bell Laboratories,  invented a powerful new linear programming  algorithm that is faster and more efficient than the simplex method.  I think this may be "owned" by AT&T and is said to have  "a direct impact on the efficiency and profitability of of numerous industry".

Course Notes

Section 4.1   and  4.2  Slack Variables and the Simplex Tableau   and The Simplex Method

Read both section sections first.  What are we trying  to accomplish by using the simplex method?  This method gives the maximum or minimum value of a system that has many variables. We will limit our discussion to chapters 4.1 and 4.2 (maximizing problems). 

Important Remarks

  1. Pivoting around a selected element means to make all the entries above and below it 0
  2. Verify the solutions in the original inequalities and objective function is not easy when dealing with 3 or more values.  Although we can actually verify solutions for 2 variable problems,  we will just accept that the theory works for higher dimensional problems. 
  3. Objective function:  This is the function you are trying to minimize or maximize.
  4. Slack variables: These are the 'extra' variables put into the table (tableau).   They will form a diagonal of 1's

Example 1
  • Lets go through an entire problem from start to finish.
  • These are the constraints.  Note:  Each variable has to be positive.
  • 60x + 90y + 300z  is the objective function to be maximized
Construct the simplex tableau  (table)
  • The top row identifies the variables. 
  • u,v,w, and M are slack variables
  • The numbers in bold are from the original constraints.
  • The bottom row comes from setting the equation
    M = 60x + 90y + 300z  to 0 
    -60x - 90y - 300z + M = 0
Choosing the pivot COLUMN.
  • Determine if the left part of the bottom row contains negative entries.
    If none, problem solved.
  • If yes,  the pivot column  is the column with the most negative entry in the last row.  In this case it is column z
  • The left part is columns x, y  or  z
Choosing the pivot ROW.
  • Divide the last column by the entries in each pivot column.
  • The pivot row is the row with the least non-negative ratio.  negative values or undefined values are ignored
  • The pivot row is the row in bold (600 is least)
Choosing the pivot element.
  • The pivot element is the entry where the pivot column and pivot row intersect.
  • The pivot element is the number in bold (1)
Pivot around selected element
  • Make all the numbers above or below the pivot element 0.
  • The entry directly below pivot element is already 0
  • We need to make the other entries 0
Pivot around selected element cont...
  • Multiply -1 times ROW 1  and  add it to ROW 3
  • ROW 1 is the first row containing numbers
Pivot around selected element cont...
  • Multiply 300 times ROW 1  and  add it to ROW 4
  • ROW 1 is the first row containing numbers
  • Pivoting this element is complete
Are we done yet?
  • Determine if the left part of the bottom row contains negative entries.
    If none, problem solved.
  • If yes,  the pivot column  is the column with the most negative entry in the last row.  In this case it is column z
  • The left part is columns x, y  or  z
The left part of the bottom row contains no negative entries.
So we are done pivoting.  Lets write the solution.

The solution.
x = 0, y = 0, z = 600, u = 0
v = 600, w = 300,  M = 180,000

  • The only columns of interest to us are x,y,z and M
  • Columns z,v,w,and M are the only columns pivoted
  • Columns not pivoted are set equal to 0
Verify the solutions in the original inequalities and objective function.
Check the solutions in the original inequalities.
  • 0 + 0 + 600 <= 600   true
  • 0 +3(0) <= 600 true
  • 2(0) + 600 <= 900  true
M = 60x + 90y + 300z  Check the solutions in the objective function.
  • 180,000 = 60(0) + 90(0) + 300(600)
A note about graphing with 3 variables
wpe1.jpg (12702 bytes) The graph to the right is the equation x + y + z = 600.  It doesn't form a line, but a plane instead. The feasible solution for this system of equations would be the area that satisfies all six constraints.   In this problem,  we would have 6 planes.

Example 2  

A store sells three brands of of stereo systems,  brands A,B, and C.  It can sell a total of 100 stereo systems per month.
First constraint  a + b + c <=  100     note:  <=   means less than or equal to.

Brands A, B, and C take up, respectively,  5, 4, and 4 cubic feet of warehouse space and a maximum of 480 cubic feet of warehouse space is available.
Second constraint  5a + 4b + 4c <=  480

Brands A, B, and C generate sales commissions of $40, $20, and $30, respectively, and $3200 is available to pay the sale commissions.
Third constraint  40a + 20b + 30c <=  3200

The profit generated from the sale of each brand is $70, $210, and $140, respectively.  How many of each brand of stereo system should be sold to maximize profit?
Objective function   70a + 210b + 140c
  • Lets go through an entire problem from start to finish.
  • These are the constraints.  Note:  Each variable has to be positive.
  • 70a + 210b + 140c  is the objective function to be maximized
Construct the simplex tableau  (table)
  • The top row identifies the variables. 
  • u,v,w, and M are slack variables
  • The numbers in bold are from the original constraints.
  • The bottom row comes from setting the equation
    M = 70a + 210b + 140c   to  0
    -70a - 210b - 140c + M = 0
Choosing the pivot COLUMN.
  • Determine if the left part of the bottom row contains negative entries.
    If none, problem solved.
  • If yes,  the pivot column  is the column with the most negative entry in the last row.  In this case it is column b
  • The left part is columns a,b  or  c
Choosing the pivot ROW.
  • Divide the last column by the entries in each pivot column.
  • The pivot row is the row with the least non-negative ratio.  negative values or undefined values are ignored
  • The pivot row is the row in bold (100 is least)
Choosing the pivot element.
  • The pivot element is the entry where the pivot column and pivot row intersect.
  • The pivot element is the number in bold (1)
Pivot around selected element
  • Make all the numbers above or below the pivot element 0.
  • The entry directly below pivot element is already 0
  • We need to make the other entries 0
Pivot around selected element cont...
  • Multiply -20 times ROW 1  and  add it to ROW 3
  • ROW 1 is the first row containing numbers
Pivot around selected element cont...
  • Multiply 210 times ROW 1  and  add it to ROW 4
  • ROW 1 is the first row containing numbers
  • Pivoting this element is complete
Are we done yet?
  • Determine if the left part of the bottom row contains negative entries.
    If none, problem solved.
  • If yes,  the pivot column  is the column with the most negative entry in the last row.  In this case it is column z
  • The left part is columns a, b or  c
The left part of the bottom row contains no negative entries.
So we are done pivoting.  Lets write the solution.

The solution.
a = 0, b = 100, c = 0, u = 0
v = 80, w = 1200,  M = 21,000

  • The only columns of interest to us are a, b, c, and M
  • Columns b,v,w,and M are the only columns pivoted
  • Columns not pivoted are set equal to 0
What does this solution mean?

The maximum profit is $21,000 when 100 brand B systems are sold (no brand A or C) .
We ignore the slack variables, except for M, but they are useful in determining other information not covered in these sections.

When you are ready, click here for the assignment for this section.

Please notify me of any errors on this page   joe@joemath.com

01/16/07