Degeneracy
Degeneracy refers to the concept of getting a degenerate basic feasible solution in a LPP. The degeneracy in a LPP may occur
At the starting stage, when at least one basic variable is zero in the initial basic feasible solution.
At any following iteration when more than one basic variable is suitable to leave the basic and therefore one or more variables becoming zero in the subsequent iteration and the problem is said to be degenerate. There is no guarantee that the value of the objective function will get better, as the new solutions may stay degenerate. Consequently, it is possible to repeat the identical sequence of simplex iterations continuously without improving the solutions. This concept is called as cycling or circling.
Rules to avoid cycling
Divide every element in the tied rows with the positive coefficients of the key column in that particular row.
Compare the resultant ratios, column by column, first of all in the identity and then in the body, from left to right.
The row which firstly consists of the smallest algebraic ratio now contains the leaving variable.
Example 1
Max Z = 3x1 + 9x2
Subject to
x1 + 4x2 ≤ 8
x1 + 2x2 ≤ 4
& x1 ≥ 0, x2 ≥ 0
Answer
Standard LPP
Max Z = 3x1 + 9x2 + 0s1 + 0s2
x1 + 4x2 + s1 = 8
x1 + 2x2 + s2 = 4
x1 , x2 , s1, s2 ≥ 0
Cj→
3
9
0
Basic Variables
CB
XB
X1
X2
S1
S2
XB / XK
S1 / X2
s1
8
1
4
1/4
s2
2
0/2→
Z = 0
-3
↑
-9
←Δj
-1
x2
1/2
Z =18
3/2
9/2
As all Δj ≥ 0, optimal basic feasible solution is achieved. Thus the solution is Max Z = 18, x1 = 0, x2 = 2
Note - As there is a tie in minimum ratio (degeneracy), we determine minimum of s1 /xk for these rows for which the tie exists.
Example 2
Max Z = 2x1 + x2
4x1 + 3x2 ≤ 12
4x1 + x2 ≤ 8
4x1 - x2 ≤ 8
Max Z = 2x1 + x2 + 0s1 + 0s2 + 0s3
4x1 + 3x2 + s1 = 12
4x1 + x2 + s2 = 8
4x1 - x2 + s3 = 8
x1 , x2 , s1, s2, s3 ≥ 0
Basic Varibles
S3
S1 / X1
S2 / X1
12
12/4=3
8/4=2
4/0=0
s3
0/4=0→
-2
4/4=1
0→
x1
-1/4
-
Z = 4
-3/2
-1/2
1/8
16
3/4
0 4
1 2
2 3/2
-1/8
3/8
Z = 5
As all Δj ≥ 0, optimal basic feasible solution is achieved. Hence the solution is Max Z = 5, x1 = 3/2, x2 = 2
satellites can be categorized through their functions. satellites are launched into space to perform a particular task.
Structure and Bonding in semiconductors tutorial all along with the key concepts of Crystal structure and bonding, Bonding structure, Intrinsic Semiconductors, Impurity states and Acceptors
Top-rated Nonlinear Dynamics Assignment Help tutors are at your service 24/7 offering plagiarism free solutions ensuring A++ grades at low prices.
Theory and lecture notes of MATLAB function and its DATA types all along with the key concepts of functions and data, MABLAB function, MATLAB DATA types. Tutorsglobe offers homework help, assignment help and tutor’s assistance on MATLAB function and its DATA types.
tutorsglobe.com electroencephalography assignment help-homework help by online cerebral cortex tutors
tutorsglobe.com clinical manifestations assignment help-homework help by online cryptococcus neoformans tutors
Reactions of Alcohols tutorial all along with the key concepts of Acidity of Alcohols, Reactions of Alcohols, Reactions involving R-OH cleavage, Reactions involving cleavage of RO-H, Difference between Primary, secondary and tertiary alcohol
Nuclear Structure tutorial all along with the key concepts of nuclides with same Isotopes, nuclides with same Isobars, nuclides with same Isotones, uncertainty in momentum of electron, Excess mass and packing fraction, Nucleus, Nuclear Binding Energy and Separation Energy
standardization of non-standard solution tutorial all along with the key concepts of acid-base titration, indicators, ph scale, choice of indicator in acid-base titrations, wrong use of indicator, problem solving in acid-base titration, calculation of molar concentration
www.tutorsglobe.com offers retained earnings statement homework help, retained earnings statement assignment help, retained earnings statement projects help, accounting solutions by tutors.
to learn the two inputs of the arithmetic circuits of half adder, full adder and flip flops using ics.
Get a strong hold over the subject with Virology and Tissue Culture Assignment Help and ace your grades with PhD tutors at feasible prices!
Theory and lecture notes of Tracking the Macroeconomy all along with the key concepts of Tracking the macroeconomy, Economic Statistics, Economic Activity and Six Key Indicators. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Tracking the Macroeconomy.
tutorsglobe.com nitrate assimilation assignment help-homework help by online nitrogen cycle tutors
tutorsglobe.com classification of production function assignment help-homework help by online production function tutors
1951479
Questions Asked
3689
Tutors
1485566
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!