Simplex Method Using Artificial Variables

Once a basic feasible solution to a linear programming problem is known, then one can create a canonical tableau for the problem with little or no effort. The system of constraints for many linear programming problems contain no obvious basic feasible solutions. By introducing into the problem a sufficient number of variables, called artificial variables, we put the system of constraints into canonical form with these variables as the basic variables. Then we apply the simplex method, not to the objective function of the original problem, but to a new objective function. We illustrate the method with the next problem.

Consider the following Linear Programming Problem and its artificial canonical form (a canonical form where at least one basic variable is an artificial variable; it also contains an extra objective function w, where w is equal to the sum of all the artificial variables).

Minimize z = 2 x1 - 3 x2 + x3 + x4
subject to:
 x1 - 2 x2 - 3 x3 - 2 x4 = 3 x1 - x2 + 2 x3 +   x4 = 11
x1, x2, x3, x4 > = 0
 x1 - 2 x2 - 3 x3 - 2 x4 + x5 = 3 x1 -   x2 + 2x3 +   x4 + x6 = 11 2 x1 - 3 x2 +   x3 + x4 = z x5 + x6 = w
x1, x2, x3, x4 x5, x6 > = 0,
where z and w are minimum.

The minimum value of w is reached at x5 = x6 = 0. A basic solution to the system with artificial variables is
x1 = x2 = x3 = x4 = 0 , x5 = 3 and x6 = 11.
To obtain a canonical form for both z and w, we must subtract the sum of the rows with artificial variables from the row with w.
We will use Simplex method to minimize w. Once w is minimized, by deleting the row with w and columns with artificial variables, we obtain a canonical form for the original problem. Also note that if our original problem has a feasible solution, then a canonical tableau for the original problem has no artificial variables. This means that although we are using x5 and x6 in order to obtain a canonical tableau for our original problem, all the values in the artificial tableaux under these two variables are not important to us.

In the tableaux on the right side, all the row operations are the same as the ones on the left side, but values for the artificial variables are not shown.

 A b c z w 0
 x1 x2 x3 x4
 x5 x6
b
 x5 x6
 1 -2 -3 -2 1 -1 2 1
 1 0 0 1
 3 11
c0
 2 -3 1 1
 0 0
0
w0
 0 0 0 0
 1 1
0
 x5 x6
 1* -2 -3 -2 1 -1 2 1
 1 0 0 1
 3 11
c1
 2 -3 1 1
 0 0
0
w1
 -2 3 1 1
 0 0
-14
 x1 x6
 1 -2 -3 -2 0 1* 5 3
 1 0 -1 1
 3 8
c2
 0 1 7 5
 -2 0
-6
w2
 0 -1 -5 -3
 1 -1
-8
 x1 x2
 1 0 7 4 0 1 5 3
 -1 2 -1 1
 19 8
c3
 0 0 2 2
 -1 -1
-14
w3
 0 0 0 0
 0 0
0
 A b c z w 0
 x1 x2 x3 x4
b
 x5 x6
 1 -2 -3 -2 1 -1 2 1
 3 11
c0
 2 -3 1 1
0
w0
 0 0 0 0
0
 x5 x6
 1* -2 -3 -2 1 -1 2 1
 3 11
c1
 2 -3 1 1
0
w1
 -2 3 1 1
-14
 x1 x6
 1 -2 -3 -2 0 1* 5 3
 3 8
c2
 0 1 7 5
-6
w2
 0 -1 -5 -3
-8
 x1 x2
 1 0 7 4 0 1 5 3
 19 8
c3
 0 0 2 2
-14
w3
 0 0 0 0
0

Tableau 1. The initial tableau is canonical for z but not w, so we need to obtain a canonical tableau for both z and w.

Tableau 2. We subtract from the last row, the sum of the rows of the matrix A with artificial variables.
In this problem both rows contain artificial variables.
The pivot entry is selected by using w11 = - 2 and not c12 = - 3.

Tableau 3. Instead of using w23 = - 5 as it is suggested, we choose w22 = - 1 > -5 = w23, just because it involves less computations.

Tableau 4. If we delete the last row (the row with w3), we get a canonical tableau for our original problem.
In this example, the final tableau for w also gives us an optimal solution z* = - ( -14 ) = 14 to the original problem at

x1 = 19 , x2 = 8 , x3 = 0 and x4 = 0.

Redundant System. A linear programming problem could very well have feasible solutions but some of the equations in the system of constraints could be linear combinations of the remaining equations. This often when, more than the minimal number of necessary equations are introduced into a problem. It is important to note that the redundancy never occurs when there are no equalities in the system of constraints.

Here is an example.

Minimize z = 4 x1 + x2 + 3 x3 + 2 x4
subject to:
 R1 : 2x1 + x2 +x4 = 20 R2 : x1 +2x2 + x3 = 10 R3 : 4x1 -   x2 - 2x3 + 3x4 = 40
x1, x2, x3, x4 > = 0
Notice that
R3 = 3 R1 - 2 R2 .
This means that the third row is redundant, so we only need the first two rows.

 A b c z w 0
 x1 x2 x3 x4
b
 x5 x6 x7
 2 1 0 1 1* 2 1 0 4 -1 -2 3
 20 10 40
c0
 4 1 3 2
0
w0
 -7 -2 1 -4
-70
 A b c z w 0
 x1 x2 x3 x4
b
 x5 x1 x7
 0 -3 -2 1* 1 2 1 0 0 -9 -6 3
 0 10 0
c1
 0 -7 -1 2
-40
w1
 0 12 8 -4
0
 A b c z w 0
 x1 x2 x3 x4
b
 x4 x1 x7
 0 -3 -2 1 1 2 1 0 0 0 0 0
 0 10 0
c2
 0 -1 3 0
-40
w2
 0 0 0 0
0
The canonical tableau is :

 A b c z
 x1 x2 x3 x4
b
 x4 x1
 0 -3 -2 1 1 2 1 0
 0 10
c
 0 -1 3 0
-40