After reading this article you will learn about the degeneracy in L.P problem and method to resolve it.
Degeneracy in L.P Problem:
Degeneracy is revealed when a basic variable acquires a zero value rather than a negative or positive value. In the final solution, either the number of basic variable is not equal to the number of constraints, or the number of zero variables does not equal the number of decision variables.
The instants of degeneracy is usually preceded by a tie for an existing variable and an arbitrary selection of for it. If this is resolved by a proper selection of the key element degeneracy can be avoided.
While solving an L.P problem, the situation may arise in which is a tie between two or more basic variables for leaving the basis i.e. the minimum ratio identify the basic variables to leave the basic is not unique or values of one or more basic variable in the column XB becomes equal of zero. This causes the problem of degeneracy.
ADVERTISEMENTS:
Degeneracy may occur at any iteration of the simplex table. In most of the cases when there is a tie in the minimum rates, selection is made arbitrary. At the state of improving the solution during simplex procedure, minimum ratio XB/Xk (Xk > 0) is determined in the last column of simplex table to find the key row.
But, sometimes this ratio may not be unique, i.e., the key element is not uniquely determined, or at the very first iteration the value of one or more basic variables in the XB column become equal to zero, this cause the problem of degeneracy.
Method to Resolve Degeneracy:
The following systematic procedure can be utilised to avoid cycling due to degeneracy in L.P problems:
Step 1:
ADVERTISEMENTS:
First pick up the rows for which the min, non-negative ratio is same (tie). To be definite, suppose such rows are first, third etc. for example
Step 2:
Now arrange the column of the usual simplex table so that the columns forming the original unit come first in proper orders.
Step 3:
ADVERTISEMENTS:
Then find the min of the Ratio
Only for the rows for which min-ratio was not unique, that is, for the rows first, third or as picked up in step to
(a) If this min is attained for third row (say) then this row will determine the key element by intersecting the key column.
(b) If this min is also not unique, then go to next
ADVERTISEMENTS:
Step 4:
Now compute the minimum of the ratio
[Element of third column of unit matrix/Corresponding elements of key column]
Only for the rows for which min ratio was not unique in step 3.
ADVERTISEMENTS:
(i) If this min. ratio is unique for the first row (say) then this row will determine the key element by intersecting the key column.
(ii) If this min. is still not unique, then go to next step.
Step 5:
Next compute the minimum of the ratio
[Element of third column of unit matrix/Corresponding elements of key column]
Only for the rows for which min ratio was not unique in step 4.
(i) If this min. ratio is unique for the third row (say) then this row will determine the key element by interacting the key column.
(ii) If this min. is still not unique, this go on repeating the above outlined procedure till the unique min. ratio is obtained to resolve the degeneracy. After the resolution of this tie, simplex method is applied to obtained the optimum solution.
Following example will make the procedure clear:
Example 1:
Maximize z= 3x1 + 9x2
Solution:
Introducing the slack variable S ≥ 0, the problem becomes
Since min ratio 2 in the last column of above table is not unique, both the slack variables S1, and S2 may leave the basis. This is an indication for the existence of degeneracy in the given L.P. Problem. So we apply the above outlined procedure to resolve degeneracy (Tie).
First arrange the column X1, X2, S1, and S2 in such a way that the initial identity (basis) matrix appears first. Thus the initial simplex table becomes.
Which occurs for the second row. Hence S2 must leave the basic, and the key element is 2 as shown above.
Since all Δj ≥ 0, on optimal solution has been reached. Hence the optimum basic feasible solution is x1 = 0
x2 = 2
and Max z = 18
Example 2:
Max z = 2x1 + x2
Solution:
Introduction the slack variables S1 ≥ 0 and S3 ≥ 0 and proceeding in the usual manner, the starting simplex table is given below
Since min ratio is the last column of above table is (2) Which is same for second and third rows. This is an indication of degeneracy. So arrange the column in such a way that the initial identity (basic) matrix comes first.
Thus starting simplex table becomes:
Using the procedure of degeneracy, compute
Only for second and third ro. Therefore min (0/4, 0/4) which is not unique. So again compute.
Only for second and third row therefore
Which occurs corresponding to the third row. Hence the key element is 4.
Now improve the simplex table in the usual manner.
Since all Δj ≥ 0, an optimum is obtained as:
x1 = 2/3, x2 = 2
Max z = 5
Example 3:
Solution:
Introducing the surplus variable S ≥ 0 slack variables S2 ≥ 0, S3 ≥ 0, and an artificial variable a1 ≥ 0 the constraints of the problems becomes.
and using Big M method objective function becomes
Max Z = 5x1 – 2×2 + 3x3 + OS1 + OS2 + OS3 – Ma1
In the usual manner, the starting simplex table is obtained as below:
Net evaluation Δj are computed by the formula Δj = CB Xj – Cj in the usual manner, since Δ1 is the most negative, X1 enter the basis . Further since the main ratio in the last column of above table is for the both first and second row’s therefore either A1 or S2 tends to leave the basis.
This is an indication of the existence of degeneracy. But A1 being artificial vector will be preferred to have the basis note that there is no need to apply the procedure for resolving degeneracy under such circumstance continuing the simplex routine the computation is presented in the following tabular from
