Index-> contents reference index search external

Prev

Next

Top

home-> Chapter1 Chapter2 Software Chapter3 Chapter5 Part2 Test Bib

Chapter3-> Degeneracy TwoPhase Problem3_9a Quiz0706 Bland BlandExample Quiz0713

Degeneracy

Headings-> Definition Example First Pivot Second Pivot Third Pivot Fourth Pivot

Degeneracy
Definition
When the basic feasible solution has some of the basic variables equal to zero, the solution is called degenerate.

Example
We consider the Tableau corresponding to the problem at the bottom of page 29 of the text:
      x1   x2   x3   x4   x5   x6    z    b
       0    0    2    1    0    0    0    1 
       2   -4    6    0    1    0    0    3 
      -1    3    4    0    0    1    0    2 
       2   -1    8    0    0    0   -1    0
The corresponding basic feasible solution is
     x1 = 0, x2 = 0, x3 = 0, x4 = 1, x5 = 1, x6 = 1, z = 0
Note that if we choose  x3 for the new basic variable, its value after the pivot will be
     x3 = min (1/2, 3/6, 2/4)  = 1/2
The important point here is that if we increase  x3 to  1/2, the basic variables  x4, x5, x6 will all be zero and hence we could choose any one of them for the new non-basic variable.

First Pivot
As in the text, we choose the pivot pair  (x3, x4). The resulting tableau is:
      x1   x2   x3   x4   x5   x6    z    b
      0,   0,    1,  .5,   0,   0,   0,  .5
      2,  -4,    0,  -3,   1,   0,   0,   0
     -1,   3,    0,  -2,   0,   1,   0,   0
      2,  -1,    0,  -4,   0,   0,  -1,  -4
The corresponding basic feasible solution is
     x1 = 0, x2 = 0, x3 = .5, x4 = 0, x5 = 0, x6 = 0, z = 4
Note that  x1 is the only possible choice for the new basic variable, its value after the next pivot will be
     x1 = 0/2  = 0
The important point here is that  x1 will not increase when we change the basis. Hence the objective function value corresponding to the basic solution for the new basis will be the same as the objective function value for this basis.

Second Pivot
As in the text, this pivot pair is  (x1, x5). The resulting tableau is:
      x1   x2   x3    x4   x5   x6    z    b
       0    0    1    .5    0    0    0   .5
       1   -2    0  -1.5   .5    0    0    0
       0    1    0  -3.5   .5    1    0    0
       0    3    0    -1   -1    0   -1   -4
The corresponding basic feasible solution is
     x1 = 0, x2 = 0, x3 = .5, x4 = 0, x5 = 0, x6 = 0, z = 4
Note that  x2 is the only possible choice for the new basic variable, its value after the next pivot will be
     x2 = 0/1  = 0

Third Pivot
This pivot pair is  (x2, x6). The resulting tableau is:
      x1   x2   x3    x4    x5   x6    z    b
       0    0    1   0.5     0    0    0   .5
       1    0    0  -8.5   1.5    2    0    0
       0    1    0  -3.5    .5    1    0    0
       0    0    0   9.5  -2.5   -3   -1   -4
The corresponding basic feasible solution is
     x1 = 0, x2 = 0, x3 = .5, x4 = 0, x5 = 0, x6 = 0, z = 4
Note that  x4 is the only possible choice for the new basic variable, its value after the next pivot will be
     x2 = .5/.5  = 1

Fourth Pivot
This pivot pair is  (x4, x3). The resulting tableau is:
      x1   x2   x3   x4    x5   x6    z      b
       0   0     2    1     0    0    0      1
       1   0    17    0   1.5    2    0    8.5
       0   1     7    0    .5    1    0    3.5
       0   0   -19    0  -2.5   -3   -1  -13.5
The corresponding basic feasible solution is
     x1 = 8.5, x2 = 3.5, x3 = 0, x4 = 1, x5 = 0, x6 = 0, z = 13.5
Note that this is the optimal solution because none of the coefficients in the last row are greater than zero.

---

Input File: Degeneracy.omh