Page 263 -

SPECIAL CASES 243

Try Problem 18 for As shown, we have a different basic feasible solution: x 1 ¼ 30, x 2 ¼ 12, s 1 ¼ 0,
another example of s 2 ¼ 8 and s 3 ¼ 0. However, this new solution is also optimal because c j – z j 0 for
alternative optimal all j. Another way to confirm that this solution is still optimal is to note that the value
solutions.
of the solution has remained equal to 1500.
In summary, when using the Simplex method, we can recognize the possibility of
alternative optimal solutions if c j – z j equals zero for one or more of the non-basic
variables in the final tableau.

Degeneracy
A linear programme is said to be degenerate if one or more of the basic variables
have a value of zero. Degeneracy does not cause any particular difficulties for the
graphical solution procedure; however, degeneracy can theoretically cause difficul-
ties when the Simplex method is used to solve a linear programming problem.
To see how a degenerate linear programme could occur, consider a change in the
right-hand side value of the assembly time constraint for the HighTech problem. For
example, what if the number of hours available had been 175 instead of 150? The
modified linear programme is shown here.
Max 50x 1 þ 40x 2
s:t:
3x 1 þ 5x 2 175 Assembly time increased to 175 hours
1x 2 20 UltraPortable display
8x 1 þ 5x 2 300 Warehouse space
x 1 ; x 2 0
The simplex tableau after one iteration is as follows:

x 1 x 2 s 1 s 2 s 3
Basis c B 50 40 0 0 0

0 0 3.125 1 0 0.315 62.5
s 1
0 0 1 0 1 0 20
s 2
50 1 0.625 0 0 0.125 37.5
x 1
50 31.25 0 0 6.25 1 875
z j
0 8.15 0 0 6.25
c j – z j
The entries in the net evaluation row indicate that x 2 should enter the basis. By
calculating the appropriate ratios to determine the pivot row, we obtain:

b 1 62:5
¼ ¼ 20
a 12 3:125
b 2 20
¼ ¼ 20
a 22 1
37:5
b 3
¼ ¼ 60
a 32 0:625
We see that the first and second rows tie, which indicates that we will have a
degenerate basic feasible solution at the next iteration. Recall that in the case of a
tie, we follow the convention of selecting the uppermost row as the pivot row. Here,
it means that s 1 will leave the basis. But from the tie for the minimum ratio we see
that the basic variable in row 2, s 2 , will also be driven to zero. Because it does not
leave the basis, we will have a basic variable with a value of zero after performing
this iteration. The tableau after this iteration is as follows:

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.