Prev Next Top BlandExample

Example Application of Bland's Smallest Pivot Rule

Original Problem
The initial dictionary at the top of page 31 of the text is equivalent to the following tableau form:
       x1    x2    x3    x4    x5    x6    x7    z    b
      0.5  -5.5  -2.5     9     1     0     0    0    0
      0.5  -1.5  -0.5     1     0     1     0    0    0
        1     0     0     0     0     0     1    0    1
       10   -57    -9   -24     0     0     0   -1    0

Cycling Example
In this example, the rule used to choose the variable entering the basis was the variable with largest coefficient in the objective function. The rule used to choose the leaving variable was the same as for Bland's pivot method; i.e., the smallest subscript. On the sixth iteration of this example, it returns to the original dictionary; i.e., it cycles.

Bland's Pivot Choice
The rule above used to choose the entering variable choose the smallest subscript for the first five iterations; i.e., it agreed with Bland's pivot rule. On page 32 of the text, the tableau corresponding to the result of the fifth iteration is
       x1    x2    x3    x4    x5    x6    x7    z    b
       -4     8     2     0     1    -9    0     0    0
      0.5  -1.5  -0.5     1     0     1    0     0    0
        1     0     0     0     0     0    1     0    1
       22   -93   -21     0     0    24    0    -1    0
Suppose that we use Bland's rule to choose the next pivot (instead of the largest objective coefficient rule). The variables with positive objective coefficients are  x6 and  x1. Of these, the one with the smaller index is  x1. Hence Bland's rule chooses  x1 as the new variable to enter the basis. The corresponding pivot ratios are
     -- , 0 / 0.5 , 1 / 1
and the minimum ratio occurs in the second row. Thus, there is only one choice for the variable to leave the basis; namely  x4.

Sixth Iteration
Dividing the corresponding row of the tableau by the coefficient of  x1 we obtain
       x1    x2    x3    x4    x5    x6    x7    z    b
       -4     8     2     0     1    -9    0     0    0
        1    -3    -1     2     0     2    0     0    0
        1     0     0     0     0     0    1     0    1
       22   -93   -21     0     0    24    0    -1    0
Row reducing the  x1 column of the tableau we have
       x1    x2    x3    x4    x5    x6    x7    z    b
        0    -4    -2     8     1    -1    0     0    0
        1    -3    -1     2     0     2    0     0    0
        0     3     1    -2     0    -2    1     0    1
        0   -27     1   -44     0   -20    0    -1    0
This is the result of the sixth iteration using Bland's pivot rule.

Seventh Iteration
Now there is only on choice for the entering variable  x3 and the leaving variable  x7. The corresponding new tableau is
       x1    x2    x3    x4    x5    x6    x7    z    b
        0     2     0     4     1    -5    2     0    2
        1     0     0     0     0     0    1     0    1
        0     3     1    -2     0    -2    1     0    1
        0   -30     0   -46     0   -18   -1    -1   -1
The basic solution corresponding to this representation is also optimal (because all the  z coefficients, with the possible exception of  b, are negative).
Input File: BlandExample.omh