Math 438 ACTIVITY 10: Matrix algebra concepts for solving LP problems
WHY: The graphical method for solving LP problems is not a practical solution method because of the limitation of our graphs to two (or at most three ) variables. A general solution method will require an algebraic approach that relies on the Extreme Point Theorem. We begin with a partial method that introduces a number of the concepts we will need -- in particular, an algebraic approach to describing [finding] the extreme points in vector and matrix terms. The major ideas introduced are the notions of a basic solution and basic feasible solution, basis matrix and basic variables, which are essential to understanding the simplex algorithm.
LEARNING OBJECTIVES:
1. Discover the meaning of basic feasible solutions and the relation to extreme points of the feasible region.
2. Become familiar with the construction of the basis matrix and the meaning of basic and non-basic variables in a basic feasible solution
3. Understand the role of visualization in learning.
CRITERIA:
1. The depth of understanding of the solution methodology demonstrated in your answers to the Critical Thinking Questions.
2. Success in applying the methodology to homework and quiz problems.
VOCABULARY:
Basis Matrix
A Basis Matrix B is a nonsingular m x m submatrix of the m x n matrix A of coefficients in a linear programming problem in standard form; each basis matrix corresponds to an intersection of m of the hyperplanes bounding the feasible region. The variables corresponding to the columns of B are called basic variables for that basis matrix; the other variables are called nonbasic variables. A vector whose entries corresponding to nonbasic variables are zero and whose entries corresponding to the basic variables are obtained from the solution to BX = b is called a basic solution; if it is feasible (satisfies all the constraints) it is a basic feasible solution (BFS). The set of basic feasible solutions is the same as the set of extreme points of the feasible region for the standard form of the problem. [The values of the variables – with nonbasic variables set to 0 - give exactly the coordinates of an extreme point of the extended feasible region]
METHODOLOGY:
1. Convert constraints to equalities Add slack/surplus variables as needed
2. Write the extended matrix Write the augmented matrix for the system of equations representing the constraints
3. Determine all basic solutions For each basis matrix (each set of m columns) in the augmented matrix, find the corresponding values of the [corresponding] basic variables
4. Identify feasible basic solutions Determine which of the points from 3 are in the feasible region
5. Determine the optimal solution Evaluate the objective function at the points selected in 4 and identify the basic feasible solution that gives the optimal (max or min - as required ) value
RESOURCES:
1. Section 3.2: Strategic Mathematics.
2. 30 minutes
3. Maple 10 and the worksheet Activity10.mw at public/courses/math/Math438
PLAN:
Work through the model and the Exercise and answer the Critical Thinking Questions [You may assume for this exercise that the objective is appropriately bounded, even if the feasible region is unbounded. This method is not a practical solution method – it does not test for boundedness and it involves calculation with far too many basis matrices that give infeasible solutions]
MODEL and DISCUSSION:
We will apply the methodology (taking advantage of Maple - especially the "gaussjord" command which reduces a matrix to reduced row-echelon form) to solve the problem
minimize f(X) = 4x1 - 5x2
subject to: x 1 -4 x2 ≥ 8
x1 + 2 x2 ≤ 20
x1 ≥ 0, x2 ≥ 0
1. Convert constraints to equalities Add slack/surplus variables as needed
minimize f(X) = 4x1 - 5x2 + 0x3 + 0x4
subject to: x 1 -4 x2 -x3 = 8
x1 + 2 x2 +x4 = 20
x1 ≥ 0 ,x2 ≥ 0, x3 ≥ 0 ,x4≥ 0
[x3 is a surplus variable, x4 is a slack variable. The "nonnegative" constraints are often not written because they are assumed - that's why we have to fix any variables that aren't restricted to non-negative]
2. Write the extended matrix Write the augmented matrix for the system of equations representing the constraints [with slack & surplus variables included]
Our original problem had constraints (besides the nonnegativity constraints) AX ≥ b with
With the added variables, we have and constraints
The augmented matrix, then, is
3. Determine all basic solutions For each basis matrix in the augmented matrix, find the corresponding values of the basic variables
Since there are two rows in the matrix, each basis matrix will be a 2x2 matrix - we need all pairs of variables to form bases for the basis matrices (there are four variables, so there are C(4,2) = 6 pairs of variables)
We use the Maple worksheet public/courses/math/Math438/ Activity10.mw
I have entered the matrix.
Now we enter the column numbers (numbers of the variables) as col1 and col2 to obtain the basis matrix and execute the "gaussjord" command to obtain the values for the basic variables (the non-basic variables have value 0) - repeated use of this sequence gives all the basic solutions:
Basic variables Basis matrix (B) point in R4
x1 , x2 [ 16 2 0 0 ]T
x1 , x3 [20 0 12 0]T
x1 , x4 [8 0 0 12]T
x2 , x3 [0 10 -48 0]T
x2 , x4 [0 -2 0 24]T
x3 , x4 [0 0 -8 20]T
4. Identify feasible basic solutions Determine which of the points from 3 are in the feasible region
We test each basic solution in the constraints to see which represent feasible solutions (and so are basic feasible solutions- representing extreme points of the feasible region). The basic solutions with negative values represent hyperplane intersections that are outside the feasible region - we discard them. [The "nonnegative" requirement in all our setups proves its value here] Our technique guarantees that , so we only need to check that all variables take on non-negative values.
We can set up a table limited to the basic feasible solutions: (recall that f(X) = CTX with CT = [4 -5 0 0 ] )
Basic variables Point Feasible? If feasible, value of f (obtained as CTX)
x1 , x2 [ 16 2 0 0 ]T Yes 54
x1 , x3 [20 0 12 0]T Yes 80
x1 , x4 [8 0 0 12]T Yes 32
5. Determine the optimal solution Evaluate the objective function at the points selected in 4
Since the function is bounded on the feasible region [not checked in this document, but can be checked] the minimum value of the objective function is 32 and
the optimal solution is x1 = 8 , x2 = 0
[We do not usually bother stating the values of the slack and surplus variables - or of any other auxiliary variables not in the original problem - but sometimes they are useful]
EXERCISE
Use the methodology given here (and the Maple worksheet, for calculations) to solve the following
[You may assume the objective function is bounded below on the feasible region – this method doesn’t check]:
Minimize 3x1 + 5x2
Subject to 5x1 + 2x2 ≥ 10
5x1 + 4x2 ≤ 40
x1 ≥0, x2≥0
[Show a table, as in steps 3 & 4]
CRITICAL THINKING QUESTIONS:
1. Why do we need to replace the graphical solution method of LP problems with an algebraic method?
2. If an LP problem has three decision variables and four constraints (all inequalities), what will be the size of a basis matrix? Why?
3. For a problem with three decision variables and four (inequality) constraints, how many basic solutions (not necessarily feasible) will we have to consider with the algebraic method used here?
4. What part of the theory in your reading (in chapter3) guarantees that the optimal solution of the extended (with slack/surplus/etc. variables) problem gives an optimal solution to the original problem?
5. In solving a system of m equations with n variables (n > m), we found that if the equations were independent the description of the solution set involved n-m "free variables" and m “dependent” variables whose value was expressed in terms of those free variables [these came from the pivots in the row-echelon form of the matrix]. In one exercise, you were asked to give the values for these m variables when we chose to set the free variables equal to 0. How does this relate to the finding of basic solutions, as in the method of this activity?
6. Which was the most difficult step in the methodology to understand? Can you reword it and its discussion to make it clearer?