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 cerebellum assignment help-homework help by online the brain tutors
Resonance effect and Hyperconjugation tutorial all along with the key concepts of nonbonding electrons, Resonance effects of various groups, Hyperconjugation, Hydrogen bonding, Tautomerism
Free SAT Study Guide, SAT Test Papers, SAT Practice papers, SAT Test pattern and general information, Find SAT exam information and resource, material free at Tutorsglobe.com
Osmotic Response in Marine Environment tutorial all along with the key concepts of need for Osmoregulation in Animals, Principle of Osmosis, Osmotic Responses of Animals, Marine Invertebrates and Marine Vertebrates
Human Evolution Assignment Help for personalized writing and for getting assured academic success.
theory and lecture notes of recovery protocols all along with the key concepts of recovery protocols, recovery management, recoverable operation. tutorsglobe offers homework help, assignment help and tutor’s assistance on recovery protocols.
identify the fault occurred in am radio receiver (50 hz hum sound) and rectified it
tutorsglobe.com microbial standards of drinking water assignment help-homework help by online air pollution tutors
Optical instruments tutorial all along with the key concepts of Microscope, Simple Microscope (in normal use), Simple Microscope with Image at Infinity, Compound Microscope, Astronomical Telescope in Normal Adjustment
The trend of genes / characters to be inherited together due to their position on similar chromosome is termed as linkage.
Theory and lecture notes of Sampling Lab all along with the key concepts of Sampling Lab, Random Sampling, Systematic Sampling, Convenience Sampling, Stratified Sampling and Cluster Sampling. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Theory of Sampling Lab.
www.tutorsglobe.com offers assignment problem, hungarian method in operation research assignment help - free tutorials on introduction to assignment problem and algorithm for assignment problem.
Let us recognize the main characteristics of computer. These characteristics can be discussed within the headings of speed, versatility, accuracy, diligence and memory.
tutorsglobe.com improved resistance to inspect microbial diseases assignment help-homework help by online transgenic plants tutors
www.tutorsglobe.com offers substitution of the hydroxyl group homework help, assignment help, online tutoring assistance, organic chemistry solutions by online qualified tutor's help.
1954394
Questions Asked
3689
Tutors
1482303
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!