Page 233 -

AN ALGEBRAIC OVERVIEW OF THE SIMPLEX METHOD 213

To develop a linear programming model for the HighTech problem, we will use
the following decision variables:
x 1 ¼ number of units of the Deskpro
x 2 ¼ number of units of the UltraPortable
The complete mathematical model for this problem is then:
Max 50x 1 þ 40x 2
s:t:
3x 1 þ 5x 2 150 Assembly time
1x 2 20 Portable display
8x 1 þ 5x 2 300 Warehouse capacity
x 1 ; x 2 0
Adding a slack variable to each of the constraints allows us to write the problem
in standard form.

Max 50x 1 þ 40x 2 þ 0s 1 þ 0s 2 þ 0s 3 (5:1)
s:t:
3x 1 þ 5x 2 þ 1s 1 ¼ 150 (5:2)
¼ 20 (5:3)
1x 2 þ 1s 2
8x 1 þ 5x 2 þ 1s 3 ¼ 300 (5:4)
x 1 ; x 2 ; s 1 ; s 2 ; s 3 0 (5:5)

The Simplex method was Algebraic Properties of the Simplex Method
developed before
computers were readily Constraint Equations (5.2) to (5.4) form a system of three simultaneous linear equa-
available. Dantzig tested
the method on a diet tions with five variables. Whenever a system of simultaneous linear equations has more
problem. Using desk variables than equations, we can expect an infinite number of solutions. The Simplex
calculators it took 120 method can be viewed as an algebraic procedure for finding the best solution to such a
person days of time to system of equations. In our example, the best solution is the solution to Equations (5.2)
find a solution. The
method was judged a to (5.4) that maximizes the objective function (5.1) and satisfies the nonnegativity
success! conditions given by (5.5). This is the solution the Simplex method aims to find.

Determining a Basic Solution
For the HighTech Industries constraint equations, which have more variables (five)
than equations (three), the Simplex method finds solutions for these equations by
assigning zero values to two of the variables and then solving for the values of the
remaining three variables. For example, if we set x 2 ¼ 0 and s 1 ¼ 0, the system of
constraint equations becomes:

3x 1 ¼ 150 (5:6)
1s 2 ¼ 20 (5:7)
þ 1s 3 ¼ 300 (5:8)
8x 1
Using Equation (5.6) to solve for x 1 , we have:

3x 1 ¼ 150

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.