Degeneracy In Linear Programming

Introduction:

Linear programming is the method which deals lots of management problem via mathematical way easily. Mathematical programming includes many more optimization models known as Non - linear Programming, Stochastic programming, Integer Programming and Dynamic Programming - each one of them is an efficient optimization technique to solve the problem with a specific structure, which depends on the assumptions made in formulating the model.

Degeneracy in linear programming:

•          In the solution of linear programming problems we may come across two situations. One is Tie and the other is Degeneracy.
•         The tie occurs when two or more net evaluation row elements of variables are equal.
•          In maximization\ problem, we select the highest positive element to indicate incoming variable and in minimization we select lowest element to indicate incoming variable (or highest numerical value with negative sign).
•          When two or more net evaluation row elements are same, to break the tie, we select any one of them to indicate incoming variable and in the next iteration the problem of tie will be solved.
•          To select the outgoing variable, we have to select the lowest ratio or limiting ratio in the replacement ratio column. Here also, some times during the phases of solution, the ratios may be equal.  This situation in linear programming problem is known as degeneracy. To solve degeneracy, the following methods are used:

A.      Select any one row as you please. If you are lucky, you may get optimal solution, otherwise the problem cycles.

OR

B.      Identify the rows, which are having same ratios. Say for example, S1 and S3 rows having equal ratio. In such case select the row, which contains the variable with smaller subscript. That is select row containing S1 as the key row. Suppose the rows of variable x and z are having same ratio, and then select the row-containing x as the key row.

(a)   Divide the elements of unit matrix by corresponding elements of key column. Verify the ratios column-wise in unit matrix starting from left to right. Once the ratios are unequal, the degeneracy is solved. Select the minimum ratio and the row containing that element is the key row. (This should be done to the rows that are in tie).

(b)   If the degeneracy is not solved by 3 (a), then divide the elements of the main matrix by the corresponding element in the key column, and verify the ratios. Once the ratios are unequal, select the lowest ratios. (This should be done only to rows that are in tie).

Example:

A company manufactures two product A and B. These are machined on machines X and Y. A takes one hour on machine X and one hour on Machine Y. Similarly product B takes 4 hours on Machine X and 2 hours on Machine Y. Machine X and Y have 8 hours and 4 hours as idle capacity The planning manager wants to avail the idle time to manufacture A and B. The profit contribution of A is Rs. 3/– per unit and that of B is Rs.9/– per unit. Find the optimal product mix.

Solution: Maximize Z = 3a 9b 0S₁ 0S₂ s.t.    1a 4b ≤ 8     1a 2b ≤ 4
Simplex format is: Maximize Z = 3a 9b s.t. 1a 4b 1S₁ 0S₂ = 8both a and b is ≥ 0 1a 2b 0S₁ 1S₂ = 4 anda, b, S₁, S₂ all ≥ 0.