Dual Simplex Algorithm

Consider the following linear Linear Programming Problem in two different forms.

Minimize z = 2 x1 + 15 x2 + 18 x3
   subject to:
- x1 + 2 x2 - 6 x3 < = -10
x2 + 2 x3 < =   6
2 x1 +11x3 < = 19
- x1 + x2 < = - 2
            x1, x2, x3 > = 0 		    Solve:
- x1 + 2 x2 - 6 x3 + x4   = -10
x2 + 2 x3 + x5   =   6
  2x1 +11x3 + x6   = 19
- x1 + x2 x7   = - 2
2x1 +15x2 +18x3   = z
            x1, x2, x3, x4, x5, x6, x7 > = 0
    where z is minimum.

Note that some of the components of the constant vector b are negative but all the components of the ojective vector c are nonnegative. To solve this problem without the use of artificial variables we use a method known as the Dual Simplex Method. This method is very similar to the Simplex method and uses some of the negative components of the constant vector b to obtain a pivot entry. The method is explained in the following three tableaux.

A b
cz
x1x2x3
x4 x5 x6 x7
b
x4
x5
x6
x7
-1* 2 -6
0 1 2
2 011
-1 1 0
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
-10
6
19
-2
c0
2 15 18
0000
0
x1
x5
x6
x7
1 -2 6
0 1 2
0 4-1*
0 19 6
-1 0 0 0
0 1 0 0
2 0 1 0
-1 0 0 1
10
6
-1
8
c1
0 19 6
2000
-20
x1*
x5*
x3*
x7*
1 22 0
0 9 0
0 -41
0 23 0
11 0 6 0
4 1 2 0
-2 0 -1 0
11 0 6 1
4
4
1
2
c*
0 43 0
14060
-26
 Tableau 1.
The vector b has two negative component b1 = - 10
and b4 = - 2 , we choose b1 = - 10.
( In general we should select the smallest component).
Next we choose an entry of the matrix A which produces the largest value of c0j/a1j with negative a1j.

max { c0/a11 = 2/(-1) , c03/a31 = 18/(-6) } = -2

Thus a11 is the pivot entry. Now we use some row operations to change the non-basic variable x1 into a basic variable
e1 = ( 1 , 0 , 0 , 0 )t.
Tableau 2.
The only negative component of b is b3 = - 1, and only
a33 < 0. Thus a33 is the pivot entry. The non-basic variable x3 must be changed into
e3 = ( 0 , 0 , 1 , 0 )t.
Tableau 3.
Since all the components of the vector b* are nonnegative, this is the final tableau; it indicates that the minimum value of z = - ( - 26 ) = 26 and the optimal solution is
X* = ( 4 , 0 , 1 , 0 , 4 , 0 , 2 )t.

The following problem obviously has no solution.

A b
cz
x1x2x3
x4 x5 x6 x7
b
x4
x5
x6
x7
-1 2 -6
0 1 2
2 011
1 1 0
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
-10
6
19
-2
c
2 15 18
0000
0

Note. The condition max { cij/aij : aij < 0 } was needed in order to preserve the nonnegativity of the vector c.

Modified Dual Simplex Method

Suppose an initial non cononical tableau contains e1 , e2 , . . . , en but some of the components of the contant vector b, and the objective vector c are negative, then to avoid using artificial variables, we apply the dual simplex method by choosing a row with the smallest bi and then selecting a negative aij in this row as a pivot entry.
The condition max { cij/aij : aij < 0 } that was used to guarantee that all the components of c remain nonnegative is not an important factor anymore but choosing the smallest component of the vector b is still a good strategic choice.
Once all the components of the constant vector b are nonnegative, the resulting tableau is in canonical form. Then we can use the simplex method, if necessary to obtain an optinal solution.

Here is an example of the modified dual simplex method.

A b
cz
x1x2x3
x4 x5 x6 x7
b
x4
x5
x6
x7
-1* 2 -6
0 1 2
2 011
-1 1 0
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
-10
6
19
-2
c0
-2 5 -18
0000
0
x1
x5
x6
x7
1 -2 6
0 1 2
0 4-1*
0 19 6
-1 0 0 0
0 1 0 0
2 0 1 0
-1 0 0 1
10
6
-1
8
c1
0 1 -6
-2000
20
x1
x5
x3
x7
1 22 0
0 9 0
0 -41
0 23 0
11 0 6 0
4 1 2 0
-2 0 -1 0
11 0 6 1
4
4
1
2
c2
0 -23 0
-140-60
26