In the previous page we introduced slack variables into the constraints of a standard maximizing problem. This changes the system of linear inequalities into a system of linear equations. The resulting system has infinitely many solutions but we are only interested in a few of them. These are the basic feasible solutions which give us the location of the corner points. The purpose of this page is to practice finding these basic feasible solutions. At the bottom of the page you will find an interactive "widget" to help you explore finding solutions. Don't go there yet. First we have to do some thinking.
It is useful to remind ourselves of the method we learned in Chapter 2 to find the solution(s) of a system of linear equations, namely Gauss-Jordan. We shall not go through the fine details of this procedure but rather focus on its basic approach. Furthermore, we shall do this in an environment that is very much influenced by the type of systems we encounter in Linear Programming.
Our main task will be to explain how this procedure is modified so as to take care of the fact that in a standard maximizing linear programming problem we do not merely solve a system of linear equations. There are some complicating factors:
Here is once again our example:
| 2x1 | + | x2 | + | s1 | = | 40 | ||
| x1 | + | x2 | + | s2 | = | 30 | ||
| x1 | + | s3 | = | 15 |
And if we ignore the decorations and focus on the coefficients themselves, then we have the augmented matrix. Note that typographical limitations prevent us from displaying the vertical line you are use to seeing.
| 2 | 1 | 1 | 0 | 0 | 40 |
| 1 | 1 | 0 | 1 | 0 | 30 |
| 1 | 0 | 0 | 0 | 1 | 15 |
We begin the Gauss-Jordan process by reducing the first column. You do remember how to do this, don't you? The row operations we use are -1·R1+2·R2 ® R2 and -1·R1+2·R3 ® R3. The new augmented matrix is
| 2 | 1 | 1 | 0 | 0 | 40 |
| 0 | 1 | -1 | 2 | 0 | 20 |
| 0 | -1 | -1 | 0 | 2 | -10 |
We next reduce the second column using -1·R2+1·R1 ® R1 and 1·R2+1·R3 ® R3 which yields
| 2 | 0 | 2 | -2 | 0 | 20 |
| 0 | 1 | -1 | 2 | 0 | 20 |
| 0 | 0 | -2 | 2 | 2 | 10 |
We now reduce the third column using 1·R3+1·R1 ® R1 -1·R3+2·R2 ® R2 which produces
| 2 | 0 | 0 | 0 | 2 | 30 |
| 0 | 2 | 0 | 2 | -2 | 30 |
| 0 | 0 | -2 | 2 | 2 | 10 |
The last thing we have to do is get 1s along the diagonal. This is accomplished by dividing the first and second rows by 2 and the third row by -2. Our final, fully row-reduced matrix is
| 1 | 0 | 0 | 0 | 1 | 15 |
| 0 | 1 | 0 | 1 | -1 | 15 |
| 0 | 0 | 1 | -1 | -1 | -5 |
That was fun. How do we read the basic solution from this matrix? For convenience, I've labeled the columns with the variable names. For obvious reasons we shall refer to the last column of this matrix as the right-hand side (RHS) column.
| x1 | x2 | s1 | s2 | s3 | RHS |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 1 | 15 |
| 0 | 1 | 0 | 1 | -1 | 15 |
| 0 | 0 | 1 | -1 | -1 | -5 |
If we ignore the s2 column and the s3 column, then the matrix looks like
| x1 | x2 | s1 | s2 | s3 | RHS |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 15 | ||
| 0 | 1 | 0 | 15 | ||
| 0 | 0 | 1 | -5 |
The 'solution' is now easy to read. It is x1 = 15, x2 = 15, and s1 = -5. But what are s2 and s3 equal to? They are given the value 0. We are looking at a basic solution. The solution in its entirety is (15,15,-5,0,0). This is the basic but not feasible solution we saw in the previous page. The variables we solved for (x1, x2, and s1 ) are called basic variables. The variables given the value zero (s2 and s3) are called nonbasic variables.
How are other basic solutions found? By doing Gauss-Jordan in a more flexible way. The end result is another matrix that has three columns that come from the identity matrix. These three columns may not be in their usual positions. You have to hunt for them. In the matrix below which three columns are the special ones? That is, which variables are the basic variables and what are the values of these basic variables?
| x1 | x2 | s1 | s2 | s3 | RHS |
|---|---|---|---|---|---|
| 1 | 0 | 1 | -1 | 0 | 10 |
| 1 | 1 | 0 | 1 | 0 | 30 |
| 1 | 0 | 0 | 0 | 1 | 15 |
| Basic | x1 | x3 | x4 | x5 | RHS | |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | -2 | 10 | |
| x1 | 1 | 0 | 0 | 0 | 1 | 15 |
| x4 | 0 | 1 | 0 | 1 | -1 | 15 |
This operation of having a nonbasic variable enter (x2) and a basic variable leave (x3) is called pivoting. The actual value of the pivot is displayed in blue to the right. The process of pivoting involves using the Gauss-Jordan method (row-reducing) to get zeros above and below the pivot and a one where the pivot lives. Is there only one possible pivot available? No. We could have chosen x5 to enter and x3 to leave, or x2 to enter and x4 to leave, or x5 to enter and x1 to leave ...
If there are so many choices available, then how do we know which variable to enter and which to leave? We will eventually concern ourselves with this (next lesson). The answer lies in ensuring that the solution be a basic feasible solution and that the objective function should get bigger. But for now we concern ourselves only with pivoting.
The "widget" below allows you to pivot without having to perform the row-reducing yourself. What a wonderful little gadget. You must, however, select a leaving basic variable and an entering nonbasic variable. Click on the appropriate 'radio buttons' to make your selections. Once you have made your selections, click on the 'pivot' button. Note that the matrix is our original system of equations except that the slack variables have been renamed to x3, x4, and x5. Begin by choosing x1 to enter and x3 to leave. Play around with the widget, that's what it is for. When you are done playing, be sure and do the exercises that follow.
|
|