Simplex method:
Standard Maximization Problems

Introduction

Standard Maximization Problem

  1. The objective function is to be maximized
  2. All the variables in the problem are nonnegative.
  3. Each linear constraint is written as an expression involving the variables set less than or equal to a nonnegative constant.

Simplex Method

  1. Set up the initial table or matrix
  2. Determine if an optimal solution has been reached
    If all the entries in the last row of the matrix (except the entry in the rhs vector) are nonnegative then an optimal solution has been reached. If one or more of entries is negative the optimal solution has not been reached.
  3. Perform the pivoting operation
  4. Determine the optimal solution.
    The value of the variable heading each unit column is given by the entry in the rhs vector in the row containing the 1. The variables in columns not in unit form are assigned a value of 0.

Example:     Maximize P = 10x + 12y subject to the constraints
æ  x + 2y  £  12 ö
ç 3x + 2y  £  24 ÷
ç       x  ³  0  ÷
è       y  ³  0  ø

(1) SET UP AN INITIAL TABLE

Introduce slack variables u and v to replace the inequalities with equations.
 x + 2y + u = 12
3x + 2y + v = 24
Rewrite the objective function.
-10x - 12y + P = 0
Form augmented matrix with the constraints first and the objective function last.
   x    y    u    v    P    RHS 
é  1    2    1    0    0 |  12  ù
ê  3    2    0    1    0 |  24  ú
ë -10 -12    0    0    1 |  0   û
(2) PERFORM A PIVOT OPERATION

We need to perform a pivot operation since there are negative entries in the last row. Column 2 is the pivot column since -12 is the most negative entry in the last row. Form ratios 12/2 = 6 and 24/2 = 12. Row 1 is the pivot row since it has the smallest ratio. The pivot element is the intersection of the pivot row and the pivot column and is colored red.

é  1    2    1    0    0 |  12  ù
ê  3    2    0    1    0 |  24  ú
ë -10 -12    0    0    1 |  0   û
 R1   > R1/2 
We make the pivot element into a 1 by dividing row 1 through by 2. The fractions are unavoidable in this setting, unlike Gaussian elimination.

é  1/2    1      1/2  0    0 |  6   ù
ê  3      2      0    1    0 |  24  ú
ë -10   -12      0    0    1 |  0   û
 R2   > R2 - 2 R1 
 R3   > R3 + 12 R1 
Eliminate the entries directly below pivot element.

é  1/2  1    1/2  0    0 |  6   ù
ê  2    0   -1    1    0 |  12  ú
ë -4    0    6    0    1 |  72  û
(3) PERFORM A SECOND PIVOT OPERATION

We need to perform a second pivot operation since there are are negative entries in the last row. Column 1 is the pivot column since -4 is the most negative entry in the last row. Form ratios 6/(1/2) = 12 and 12/2 = 6. Row 2 is the pivot row since it has the smallest ratio. The pivot element is colored red.

é  1/2  1    1/2  0    0 |  6   ù
ê  2    0   -1    1    0 |  12  ú
ë -4    0    6    0    1 |  72  û
 R2   > R2/2 
We make the pivot element into a 1 by dividing row 2 through by 2.

é  1/2  1    1/2  0    0 |  6   ù
ê  1    0   -1/2  1/2  0 |  6   ú
ë -4    0    6    0    1 |  72  û
 R1   > R1 - 1/2 R2 
 R3   > R3 + 4 R2 
Eliminate the entries above and below pivot element.

   x    y    u    v    P    RHS 
é  0    1    3/4 -1/4   0 |  3   ù
ê  1    0   -1/2  1/2   0 |  6   ú
ë  0    0    4    2     1 |  96  û
(4) READ THE OPTIMAL SOLUTION

To find the optimal value of x: Locate the x-column; this is the first column; find the row containing a 1; this is the second row; read off the value of x from the RHS; this is 6. To find the optimal value of y: Locate the y-column; this is the second column; find the row containing a 1; this is the first row; read off the value of y from the RHS; this is 3. To find the optimal value of P: Locate the P-column; this is the fifth column; find the row containing a 1; this is the third row; read off the value of P from the RHS; this is 96. Hence, the optimal solution is
 
æ x = 6  ö
ç y = 3  ÷
è P = 96 ø

Exercise

(1) Maximize P = 5x + 4y
subject to the constraints
æ 3x + 5y  £  78 ö
ç 4x +  y  £  36 ÷
ç       x  ³  0  ÷
è       y  ³  0  ø
 Initial table
 Table after first pivot operation
 Table after second pivot operation
 Answer

| Table of Contents | | Previous | | Next |