As a prelude to the analysis of the Simplex Method it is extremely useful to remind ourselves of the method underlying a variety of techniques for the solution of systems of linear equations, namely the good old faithful Guassian Elimination procedure. 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 expalin how this procedure is modified so as to take care of the fact that in linear programming we do not merely solve a system of linear equations. There are two complicating factors:
So let us begin at the beginning, say with the following system of linear equations:
| 2x1 | + | x2 | + | x3 | = | 40 | ||
| x1 | + | x2 | + | x4 | = | 30 | ||
| x1 | + | x5 | = | 15 |
And if we ignore the decorations and focus on the coefficients themselves, the picture is this:
| 2 | 1 | 1 | 0 | 0 | 40 |
| 1 | 1 | 0 | 1 | 0 | 30 |
| 1 | 0 | 0 | 0 | 1 | 15 |
It is very easy to solve this system because the coefficient matrix of the variables contains a collection of columns that constitute an identity matrix. Thus, all we have to do is set the variables associated with these columns to the respective right-hand side values, and set all the other variables to zero. This will generate the following basic solution: x=(0,0,40,30,15). For obvious reasons we shall refer to the last column of this matrix as the right-hand side (RHS) column.
And to make it easier to relate the elements of the table to the elements of the original systems we shall append some headers to the table. The end product will look like this:
| x1 | x2 | x3 | x4 | x5 | RHS |
|---|---|---|---|---|---|
| 2 | 1 | 1 | 0 | 0 | 40 |
| 1 | 1 | 0 | 1 | 0 | 30 |
| 1 | 0 | 0 | 0 | 1 | 15 |
At this point you might be a bit disturbed about the fact that we exploit here a very pleasant situation where a collection of the columns of the coeffcient matrix constitutes an identity matrix. After all, this situation is not common in Nature, neither in end-of-year exams!
This is indeed a good comment, which unfortunately we cannot address right now. We shall do it later on. For the time being we shall assume that the system of linear equations we are dealing with is canonical in the sense that a collection of columns of the coefficient matrix constitutes an identity matrix. Typically these columns will not be nicely positioned together in one block, but rather will be spread all over the place. Nevertheless, they will be there ready to do their job.
Observe that in this environment is very easy to generate other basic solutions from a given one, if such beasts exist. All we have to do is replace one of the basic columns with a non-basic column and conduct a pivot operation to recreate the same elementary column in a new position. For example, suppose that we decide to take x4 out of the basis and put x2 in instead. All we have to do then is conduct a pivot operation at the row 2, column 2. The result is as follows:
| x1 | x2 | x3 | x4 | x5 | RHS |
|---|---|---|---|---|---|
| 1 | 0 | 1 | -1 | 0 | 10 |
| 1 | 1 | 0 | 1 | 0 | 30 |
| 1 | 0 | 0 | 0 | 1 | 15 |
The basic solution associated with this table is equal to x=(0,30,10,0,15). If you are a first year student make sure that you understand why this is so!!!
Now, to make our life even easier, let us append a column on the left-hand side of the table that will be used to list the basic variables associaed with the each one of the rows. This done, the last table will look something like this:
| BV | x1 | x2 | x3 | x4 | x5 | RHS |
|---|---|---|---|---|---|---|
| x3 | 1 | 0 | 1 | -1 | 0 | 10 |
| x2 | 1 | 1 | 0 | 1 | 0 | 30 |
| x5 | 1 | 0 | 0 | 0 | 1 | 15 |
If you are a visitor from out of space please note that here BV is used as an abbreviation for Basic Variables. In anycase, now it is very easy to read the values of the basic variables, recalling that all the nonbasic variables are equal to zero. Using this new column it is easy to compose the identity matrix corresponding to the current basis: In our example left-hand side column says that the identity matrix is composed of the columns of x3, x2 and x5 in this order! Life is beautiful!!!
In fact, since it is so beautiful how about taking a break for a moment or two! Let's play the Gaussian Game! The rules are simple: select the pivot row and pivot column using the respective radio buttons and when ready click the play button.
You are on your own now!
Back to the front page.