This activity is designed to help you understand the process of solving linear programming problems using matrix methods. The Simplex Method formalizes the minimum ratio rule and the other algebraic processes from section 3.2. The Simplex Method can be automated, and we will look at its implementation in Maple and in UNIX in the next few weeks. There are many sophisticated powerful computerized tools which are used in consulting and engineering design firms to implement the Simplex Method.
| 1. Put in Standard Form | Add slack or subtract surplus variables to put the problem in the form: Minimize C'X subject to AX = b, X >= 0. |
| 2. Form Initial Tableau | Append b to the right of A and insert the negatives of the objective function coefficients in the bottom row. |
| 3. Compute the Row Ratios | Divide column with a positive bottom row entry into the rightmost column. |
| 4. Identify Pivot Element | Find an element in both the column from step 3 and the row containing the minimum ratio. |
| 5. Pivot to form new Basis | Perform a Gauss Elimination pivot operation using the element from Step 4 as the pivot. |
| 6. Write new Basis Matrix | Copy the columns from the A matrix which correspond to the Identity columns in the tableau to form a basis matrix. Write out the new Basic Feasible Solution. |
| 7. Repeat Steps 3-6 | Check bottom row of simplex tableau for another positive entry. If all other entries <= 0 in column with positive bottom row entry the problem is unbounded and there is no finite solution. If all bottom row entries are <= 0 the optimal solution has been reached. |
minimize -3x1 - 2x2 C = [-3 -2]'
subject to b = [80 50]'
2x1 + x2 <= 80 X = [x1 x2 x3 x4]'
x1 + x2 <= 50
x1 >= 0, x2 >= 0 | 2 1 1 0 |
A = | 1 1 0 1 |
Initial B = | 1 0 |
| 0 1 |
Note that the matrix forms for the standard form are given above.
minimize -3x1 - 2x2
subject to 2x1 + x2 + x3 = 80
x1 + x2 + x4 = 50
x1 >= 0, x2 >= 0, x3 >= 0, x4 >= 0
x1 x2 x3 x4 z
| 2 1 1 0 | 0 | 80 |
Initial tableau = | 1 1 0 1 | 0 | 50 |
|---------------------|
| 3 2 0 0 | 1 | 0 |
The initial basic feasible solution is [0 0 80 50]'. The basic variables are x3 and x4 since the Identity submatrix of the coefficient matrix corresponds to these variables. The nonbasic variables are x1 and x2. The objective function value is 0 for this solution.
The first column has a positive bottom row entry. Dividing the first column into the last column we get the following ratios: 80/2 and 50/1. The minimum ratio is in the first row (80/2 = 40). Note that we do not divide the last row entries.
The pivot element is the 2 in position a11.
| 1 0.5 0.5 0 | 0 | 40 |
The new tableau is | 0 0.5 -0.5 1 | 0 | 10 |
|-------------------------|
| 0 0.5 -0.5 0 | 1 |-120|
| 2 0 |
| 1 1 |
The basic feasible solution is [40 0 0 10]' and the value of the objective function is -120.
There is a positive entry in the second column bottom entry of the
current tableau, so we bring x2 into
the basis. The ratios obtained by dividing the last column by the
second column are 40/.5 and 10/.5. The
smaller ratio goes with the second row (10/.5 = 20). Thus, the pivot
element is the 0.5 in the a22 position.
| 1 0 1 -1 | 0 | 30 |
The next tableau is | 0 1 -1 2 | 0 | 20 |
|---------------------|
| 0 0 -1 -1 | 1 |-130|
| 2 1 |
Thus the next B matrix becomes | 1 1 |
and the new basic feasible solution is [30 20 0 0]' with an objective function value -130. This solution is optimal because there are no positive entries in the bottom row of the final tableau. Note, we are talking only about the bottom row entries under the transformed columns of A.
In order to solve a problem using the simplex method we must replace the constraint inequalities by equalities. This is what is done by converting the problem to standard form. Doing this increases the dimension of the feasible region, but there is a 1-1 correspondence between the extreme points of the original feasible region and those of the new feasible region. Thus, solutions to the problem in standard form yields solutions to the original problem.
If we set z = C'X, we can treat the objective function as another constraint -C'X + z = 0. We need to add a z column to the A matrix and then adjoin the b vector to get the initial tableau as follows:
X z | A | 0 | b | |-----------| |-C'| 1 | 0 |
Our goal is to minimize the objective function, so we try to increase variables which have negative coefficients. Note: The corresponding entries in the bottom row will be positive. The column with the largest positive bottom row entry is usually chosen for insertion into the basis, but any column with a positive bottom row entry can be brought into the basis. We then divide the entries in the pivot column into the corresponding entries in the augmented column to find the minimum ratio. Note that we do not divide the last row entries.
The element in the pivot column and the minimum ratio row is called the pivot element because it is used to perform one Gauss-Jordan elimination operation on the tableau. Note the similarity between this matrix procedure and the minimum ratio rule of the last section.
Once we complete the Gauss-Jordan pivot operation, the pivot column will be transformed into a column of the identity matrix, and the column corresponding to the variable we are removing from the basis will no longer contain a pivot.
The new basis matrix will be the columns of the original A matrix which correspond to the identity columns in the new simplex tableau. The new basic feasible solution can be read off the new simplex tableau by setting the basic variables equal to their corresponding entries in the rightmost column and the nonbasic variables to zero.
Often, there are other positive bottom row entries in the revised simplex tableau. Chooose one of these as a pivot column and repeat the above matrix manipulation process. If all other entries are <= 0 in a column with a positive bottom row entry, the problem is unbounded and there is no finite solution. If all bottom row entries are <= 0 the optimal solution has been reached.
minimize x1 - 2x2 - x3 C = [1 -2 -1 0 0 0]'
subject to b = [5 6 4]
x1 + x2 + x3 <= 5 X = [x1 x2 x3 x4 x5 x6]'
4x1 - x2 + x3 <= 6
x1 + x2 <= 4 | 1 1 1 1 0 0 |
x1 >= 0, x2 >= 0, x3 >= 0, x4 >= 0 A = | 4 -1 1 0 1 0 |
| 1 1 0 0 0 1 |
| 1 0 0 |
Initial B = | 0 1 0 |
| 0 0 1 |
Note that the matrix forms of the standard form are given above
minimize x1 - 2x2 - x3
subject to x1 + x2 + x3 + x4 = 5
4x1 - x2 + x3 + x5 = 6
x1 + x2 + x6 = 4
x1 >= 0, x2 >= 0, x3 >= 0, x4 >= 0, x5 >= 0, x6 >= 0
x1 x2 x3 x4 x5 x6 z | 1 1 1 1 0 0 | 0 | 5 | | 4 -1 1 0 1 0 | 0 | 6 | | 1 1 0 0 0 1 | 0 | 4 | |--------------------------| |-1 2 1 0 0 0 | 1 | 0 |
The initial basic feasible solution is [0 0 0 5 6 4]'. The basic variables are x4, x5 and x6 since the Identity submatrix of the coefficient matrix corresponds to these variables. The nonbasic variables are x1, x2 and x3. The objective function value is 0 for this solution.
The pivot element is the 1 in column 2 row 3.
The new tableau is
| 0 0 1 1 0 -1 | 0 | 1 | | 5 0 1 0 1 1 | 0 | 10 | | 1 1 0 0 0 1 | 0 | 4 | |---------------------------| |-3 0 1 0 0 -2 | 1 | -8 |
| 1 0 1 | | 0 1 -1 | | 0 0 1 |
The basic feasible solution is [0 4 0 1 10 0]'. The new basic variables are x4, x5 and x2. The nonbasic variables are x1, x3 and x6. The objective function value is -8 for this solution.
There is a positive entry in the third column bottom entry of the current tableau, so we bring x2 into the basis. The ratios obtained by dividing the last column by the third column are 1/1 and 10/1. The smaller ratio goes with the first row (1/1). Thus, the pivot element is the 1 in the a13 position.
The next tableau and corresponding B matrix are
| 0 0 1 1 0 -1 | 0 | 1 | | 5 0 0 -1 1 2 | 0 | 9 | | 1 0 1 | | 1 1 0 0 0 1 | 0 | 4 | B = | 1 1 -1 | |---------------------------| | 0 0 1 | |-3 0 0 -1 0 -1 | 1 | -9 |
Thus the new BFS is [0 4 1 0 9 0]' with an objective function value -9. This solution is optimal because there are no positive entries in the bottom row of the final tableau.
These will be provided in class.
Return to the
List of Activities