Simplex method:
Standard Maximization Problems
Introduction
- Method of corners
Requires us to evaluate the objective function at all the corner points. Not practical
for problems with a large number of variables or constraints. In fact we cannot graph
equations with more than three variables.
- Simplex method
Only requires us to investigate some of the corners. Uses methods from linear algebra that
are easily implemented on a computer. Effective tool for linear programming problems
arising in large industrial and military applications. The Simplex method is one of the
most important advances in mathematics in the 20'th century.
Standard Maximization Problem
- The objective function is to be maximized
- All the variables in the problem are nonnegative.
- Each linear constraint is written as an expression involving the variables set less than
or equal to a nonnegative constant.
Simplex Method
- Set up the initial table or matrix
- Transform the constraints to a system of linear equations with positive right hand sides
by introducing slack variables.
- Rewrite the objective function in the form
- Write the augmented matrix associated with this system.
First constraints and then objective function.
- 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.
- Perform the pivoting operation
- Locate the pivot element.
Find the most negative entry in last row of the matrix (except the entry in the rhs
vector). The column containing this entry is called the pivot column (If there is
more than one such column, choose any one). Divide each positive entry in the pivot
column into its corresponding entry in the rhs vector. The row with the smallest ratio is
called the pivot row (If there is more than one such row, choose any one). The
pivot element is the intersection of the pivot row and pivot column.
- Use elementary row operations to make the pivot column into a unit column.
In particular use the scaling and elimination operations to make the pivot element a 1 and
the remaining elements of the pivot column 0's.
- Return to step 2 to see if an optimal solution has been reached.
- 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 ø
|
| Table of Contents |
| Previous |
| Next |