I.E. 2001   OPERATIONS RESEARCH

DEGENERACY and the Simplex Method - An Example

Consider the following LP:

    Maximize Z = 2X1 + 3X2
    st       X1  + X2  £ 3
              X1 + 2X2 £ 4
            4X1 + 3X2 £ 12
                X1, X2 ³ 0

Iteration 1
 
Row
Z
X1
X2
S1
S2
S3
RHS
Basic
0
1
-2
-3
0
0
0
0
Z
1
0
1
1
1
0
0
3
S1
2
0
1
2
0
1
0
4
S2
3
0
4
3
0
0
1
12
S3
X2 has a negative reduced cost, so let us bring it into the basis to improve Z
Min {3/1, 4/2, 12/3}=2 - pick S2 to leave basis and pivot

Iteration 2
 
Row
Z
X1
X2
S1
S2
S3
RHS
Basic
0
1
-0.5
0
0
 1.5
0
6
Z
1
0
 0.5
0
1
-0.5
0
1
S1
2
0
 0.5
1
0
 0.5
0
2
X2
3
0
 2.5
0
0
-1.5
1
6
S3
Now X1 enters the basis, and Min {1/0.5, 2/0.5, 6/2.5}=2 - so S1 leaves the basis. Pivot...
 
 
Row
Z
X1
X2
S1
S2
S3
RHS
Basic
0
1
 0
0
 1
 1
0
7
Z
1
0
 1
0
 2
-1
0
2
X1
2
0
 0
1
-1
 1
0
1
X2
3
0
 0
0
-5
 1
1
1
S3
 

All reduced costs are nonnegative so no further increase is possible in the objective Z - OPTIMUM obtained in 2 iterations.

Continue with next page...


  Back to IE 2001 Web Documents page.