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
tutorsglobe.com translocation of solutes assignment help-homework help by online mineral nutrition tutors
tutorsglobe.com use of chromium assignment help-homework help by online occurrence and principles of extraction of chromium tutors
Simple Harmonic Motion II tutorial all along with the key concepts of Mass Hanging from a Coiled Spring, Period of Oscillation, Simple Pendulum, Energy of Simple Harmonic Motion, Kinetic Energy, Potential Energy
how transactions impact the accounting equation, and distinguishing between revenue and income, www.tutorsglobe.com offers assignment help, homework help and online tutoring.
introduction to petroleum chemistry tutorial all along with the key concepts of crude oil reserves, refining process, fractional distillation, quality of petrol - octane number, conversion processes, petrochemicals
tutorsglobe.com nuclear reactions occurring in sun assignment help-homework help by online nuclear reaction tutors
theory and lecture notes of semiconductor materials and diode all along with the key concepts of conductors, insulators, reverse-bias and forward-bias.tutorsglobe offers homework help, assignment help and tutor’s assistance on theory of semiconductor materials and diode.
Maintenance of Accounts - The finance department is accountable for maintaining the financial ledgers (General ledger, Debtors Ledger, Creditors Ledger, Work-in-progress ledger, Cost ledger).
tutorsglobe.com oxidation of sulphur compounds assignment help-homework help by online sulphur cycle tutors
Biodegradations and Recycling of Polymers tutorial all along with the key concepts of Biodegradations in polymers, Recycling, Chlorine attack acetal resin plumbing joints, Ozone cracking in natural rubber tubing
TutorsGlobe.com Chemical Equilibrium-Reversible Reactions Assignment Help-Homework Help by Online Access Chemistry Tutors
www.tutorsglobe.com offers periodic table and its properties homework help, periodic table and its properties assignment help, online tutoring assistance, inorganic chemistry solutions by online qualified tutor's help.
www.tutorsglobe.com offers Factory Overheads homework help, assignment help, case study, writing homework help, online tutoring assistance by accounting tutors.
Synthesis and Reactions of Dibenzopyrilium Salts tutorial all along with the key concepts of Properties of Benzopyrilium Salts, Synthesis of Pyrilium Salts, Synthesis of Anthocyanidin and Cyanidin Chloride, Synthesis of Cyanidin Chloride
tutorsglobe.com bacterial biofertilizers assignment help-homework help by online biofertilizer tutors
1947451
Questions Asked
3689
Tutors
1449760
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!