Finite Mathematics Lesson 4
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


Construct
the simplex tableau (table)


Choosing the pivot COLUMN.




Choosing the pivot element.


Pivot
around selected element


Pivot around selected
element cont...


Pivot around selected
element cont...


Are we done yet?


The left part of the bottom row contains
no negative entries. So we are done pivoting. Lets write the solution. 

The
solution.


Verify the solutions in the original inequalities and objective function.  
Check the solutions in the
original inequalities.


M = 60x + 90y + 300z  Check the solutions in the
objective function.


A note about graphing with 3 variables  
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.  
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. 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. Brands A, B, and C generate sales commissions of $40, $20, and $30,
respectively, and $3200 is available to pay the sale commissions. 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? 



Construct
the simplex tableau (table)


Choosing the pivot COLUMN.




Choosing the pivot element.


Pivot
around selected element


Pivot around selected
element cont...


Pivot around selected
element cont...


Are we done yet?


The left part of the bottom row contains no
negative entries. So we are done pivoting. Lets write the solution. 

The
solution.


What
does this solution mean? The maximum
profit is $21,000 when 100 brand B systems are sold (no brand A or C) . 
When you are ready, click here for the assignment for this section.
Please notify me of any errors on this page joe@joemath.com
09/23/10