An algebraic technique that applies to any number of variables and enables us to solve larger linear programming problems is called the simplex method.A linear programming problem may look like:
Maximize: z = 4x1 + 12x2, subject to
to solve this problem graphically, we graph the feasible region formed by the lines:3x1 + x2£ 180
x1 + 2x2£ 100
-2x1 + 2x2£ 40
x1 ³ 0, x2 ³ 03x1 + x2 = 180
x1 + 2x2 = 100
-2x1 + 2x2 = 40
x1 = 0, x2 = 0
we examine the boundary points: (0, 0), (60, 0), (52, 24), (20, 40), and (0, 20) and substitute these values for x1 and x2 into the equation: z = 4x1 + 12x2
Point | The value of z |
(0, 0) | 4(0) + 12(0) = 0 + 0 = 0 |
(60, 0) | 4(60) + 12(0) = 240 + 0 = 240 |
(52, 24) | 4(52) + 12(24) = 208 + 288 = 496 |
(20, 40) | 4(20) + 12(40) = 80 + 480 = 560 |
(0, 20) | 4(0) + 12(20) = 0 + 240 = 240 |
the maximum value of z is 560 corresponding to the point (20, 40). So our answer is x1 = 20, x2 = 40, and z = 560.Lets solve the same system using the simplex method:
The first step in the simplex method converts the constraints to linear equations by introducing additional variables called slack variables. The first constraint, 3x1 + x2 £ 180, is true for pairs of numbers such as x1 = 5 and x2 = 17 because 3(5)+17 £ 180. Also note that 3x1 + x2 + 130 = 180 when x1 = 10 and x2 = 20. The 130 in this case 130 is called the slack variable for the first constraint (denoted by s1). The objective function, z = 4x1 + 12x2, can be rewritten as: -4x1 - 12x2 + z = 0
With the addition of slack variables, the constraints become:
we now form the augmented matrix of this system:3x1 + x2 + s1 = 180
x1 + 2x2 + s2 = 100
-2x1 + 2x2 + s3 = 40
-4x1 - 12x2 + z = 0
x1 ³ 0, x2 ³ 0, s1 ³ 0, s2 ³ 0, s3 ³ 0
the second step is to find the pivot element. Look at the last row and pick out the most negative entry (-12). This selects the pivot column (1, 2, 2) above.We need to get the pivot row. Divide each constant (180, 100, 40) by the corresponding entries in the pivot column:
Select the smallest ratio (to get the pivot row):(i) Ignore all negative ratios.
(ii) If a zero ratio occurs, then if the zero was obtained by dividing a zero by a negative number
then ignore the zero.
(iii) If it was obtained by dividing a zero by a positive number, use that row for the pivot row.The smallest is 20 determining the pivot row. The pivot element is (2) in the second column third row.
The third step is pivoting, like matrices, make the pivot element a 1 and the rest of the pivot column 0's. So, divide the third row by 2 to get:
now we need zeros above and below the pivot element:
the forth step: is z maximized?If the last row contains any negative numbers, z is NOT maximized and we have to repeat steps 2, 3, and 4 again.
We need to find another pivot element. Look at the last row and pick out the most negative entry (-16). This selects the pivot column (4, 3, -1) above.
We need to get the pivot row. Divide each constant (160, 60, 20) by the corresponding entries in the pivot column:
The smallest ratio is 20 determining the pivot row. The pivot element is (3) in the first column second row.Then pivoting, make the pivot element a 1 and the rest of the pivot column 0's. So, divide the second row by 3 to get:
and get zeros above and below the pivot element:
Is z maximized?The last row contains no negative numbers so z is maximized.
What is the final answer?
Notice that the first, third and last columns' are unit columns; so the basic variables are x1, x2, s1, and z. The feasible solution is obtained by setting s2 and s3 = 0 and solving for the others:
x1=20, x2=40, s1=80, s2=0, s3=0, z=560
Notice also this is the same answer obtained in the first page.
Lets try to solve a Minimization problem:
Summary of the Simplex Method for Minimization Problems:Minimize: z = 3x1 + 5x2 + 2x3, subject to
6x1 + 9x2 + 12x3 £ 672
x1 - x2 + 2x3 = 92
5x1 + 10x2 + 10x3 ³ 480
x1 ³ 0, x2 ³ 0, x3 ³ 0
1. Maximize w = -z. |
To use the simplex method, we modify this problem to the following:Notice the changes in the marked rows (*).Maximize: w = -z = -3x1 - 5x2 - 2x3, subject to
6x1 + 9x2 + 12x3 £ 672
* x1 - x2 + 2x3 £ 92
* x1 - x2 + 2x3 ³ 92
* -5x1 - 10x2 - 10x3£ -480
x1 ³ 0, x2 ³ 0, x3 ³ 0Phase I. The initial tableau is
Pivot on -10 in Row 4, Column 2 to obtain
Pivot on -3 in Row 3 to obtain
Phase II. Pivot on the 1 in Row 2, Column 6 to obtain
The optimal solution is maximum w = -100 at x1 = 0, x2 = 4/3, x3 = 140/3. Thus the original problem has the optimal solution z = -w = 100 at x1 = 0, x2 = 4/3, x3 = 140/3.
Revised: Summer 1999
Student Learning Assistance Center (SLAC)
Southwest Texas State University