How do you find a basic feasible solution?
The initial simplex tableau allows us to calculate the locations of the corner points as well as any other points where the lines corresponding to the equations cross or cross the axes. Let’s start with the initial simplex tableau
Since there are more variables than equations, there is not a unique solution to the system of equations represented by the tableau. There are five variables and three equations so we need or 2 parameters to write the solution. Any two of the variables may be parameters, but in the case of the initial simplex tableau it is convenient to choose the parameters as x and y.
To see why, rewrite the augmented matrix as a system of equations,
The variables s1, s2, and z each have a coefficient of 1 and appear nowhere else in the system. In the matrix, this corresponds to the columns consisting of all zeros except for a single entry of 1. These variables are the basic variables for the initial simplex tableau. The other variables, x and y, are the nonbasic variables for the initial simplex tableau. To find possible corner points, we’ll solve for the basic variables in term of the nonbasic variables.
Solve for the basic variables variables in terms of x and y:
One possible solution to this system is found by setting the nonbasic variables x and y equal to zero. In this situation,
This situation corresponds to the corner point of the feasible region at (x, y) = (0, 0) with an objective function value of z = 0. At this corner point, the slack variables take on the values s1 = 4 and s2 = 4.
Figure 1 – The corner point corresponding to a solution of the initial simplex tableau with s1 = 4, s2 = 4 and z = 0.
Other corner points can be obtained by using row operations to make other variables basic instead of s1, s2, and z. In general, z should always be a basic variable so that it is easy to determine the value of the objective function.
Suppose we start from the initial simplex tableau
and multiply the second row by 1/2 and place the result in the second row (1/2 R2 becomes R2). This gives us a 1 in the second row, second column:
If we make the rest of the second column zeros, the variable y will become a basic variable. To do this, we’ll use two row operations.
First, multiply the second row by -1 and add it to the first row:
This sum will be placed in the first row. Second, multiply the second row by 6 and add it to the third row:
This sum is placed in the third row. Putting these rows into the tableau yields
In this tableau, the variables y, s1, and z are basic. The variables x and s2 are nonbasic variables. Notice that by placing the 1 in the second column in the second row, the second slack variable (which originally was in the second row) became nonbasic. In general, when a 1 is placed in a column to make a variable basic, the slack variable corresponding to the row it was placed in becomes nonbasic. As with the initial simplex tableau, we’ll write this matrix as a system of equations and set the nonbasic variables equal to zero.
The corresponding system of equations is
If we solve each equation for a different basic variable we get
If we set the nonbasic variables x and s2 equal to zero, we find that s1 = 2, y = 2, and z = 12. This corresponds to the corner point at (x, y) = (0, 2) with an objective function value of z = 12.
Figure 2 – The corner point at (0,2) corresponding to s1 = 2, y = 2, and z = 12.
It is easier to find this corner point using the tableau without transforming it to a system of equations. The key is to realize that when nonbasic variables are set equal to zero, their coefficients in the matrix disappear. For instance, if we take the tableau we transformed with row operations and cross out the columns of the nonbasic variables we get:
By ignoring these columns, we can see that s1 = 2, y = 2, and z = 12. Combining this observation with our knowledge of setting the nonbasic variables equal to zero gives us the corner point at (0, 2) and objective function value z = 12.
We cannot arbitrarily make a variable into a basic variable. For instance, we might make x a basic variable by putting a 1 in the second row and first column and zeros in the rest of the column. Starting from the original simplex tableau, we must carry out two row operations:
To find the corner point corresponding to this matrix, cover the nonbasic variables and read off the values of the basic variables:
Figure 3 – A solution to the tableau that is not a corner point of the feasible region.
On the surface this might not seem all that different from earlier tableaus, but this one violates one of the assumptions for slack variables. In a standard maximization problem, the slack variables are assumed to be non-negative. In the solution we found from this tableau, the value for s1 is negative. This tells us that this solution does not correspond to a corner point of the feasible region.
The solution we have just found, (0, 4), matches a point on a line, but is not along the border of the feasible region. If we are not careful about picking the basic and nonbasic variables, we may obtain a point that is not related to the solution.
If we want to make the variable x a basic variable, it is better to use row operations to transform the original matrix
By covering the columns under y and s1, we observe that this new tableau corresponds to the solution x = 2 and y = 0 and the objective function value z = 10. This does match the corner point (2, 0) on the feasible region.
Example 2 Change Basic Variables
The basic variables for the initial simplex tableau
are s1, s2, and z. Use row operations to change the tableau so that the basic variables are y, s1, and z. What corner point of the basic feasible solution does this new tableau correspond to?
Solution We want to change the basic variables from s1, s2, and z to y, s1, and z. This means we need to make s2 nonbasic and y basic. The other two variables, s1 and z, should remain basic variables.
To make y a basic variable, we need to place two 0’s and a 1 in the column corresponding to y. The only question is where should we put the one? The first row of the second column already has a one so all we need to do is to use row operations to place zeros in the rest of the column.
If you examine the new matrix, you’ll notice that y is a basic variable, but s1 is not. Instead, s2 is a basic variable.
If we place the one in the first row, the slack variable corresponding to that row, s1, becomes a nonbasic variable. Since we want s1 to remain basic and s2 to become nonbasic, the one should be placed in the second row of the first column. Start from the original tableau
In general, we get the one by multiplying the row by a constant:
Now we can add multiples of rows to put zeros in the rest of the second column.
Since the second, third, and fifth columns contains two zeros and a one, the basic variables are now y, s1, and z. The point in the feasible region corresponding to this tableau is found by covering the nonbasic variable columns x and s2. This shows the corner point to be at with an objective function value of z = 12.