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 types of senescence assignment help-homework help by online senescence tutors
Stop the anxiety of scary deadlines & get impeccable Genetics Assignment Help service from 24x7 support of native tutors and score high.
Transformation of alcohols and arenes tutorial all along with the key concepts of Oxidation of primary alcohols, Oxidation of secondary alcohols, Oxidation of tertiary alcohols and Transformation of arenes
Evolution and variation tutorial all along with the key concepts of Natural Selection, Variation, Types of variation, Genetic Variation, Morphological Level, Cellular Level and DNA Level
Genetic variation tutorial all along with the key concepts of Types of variation, Discontinuous Variation, Continuous Variation, Influence of the Environment and Sources of Variation
difference between pal and ntsc - channel bandwidth, video bandwidth, video if, sound if, horizontal frequency, frame frequency
to learn the two inputs of the arithmetic circuits of half adder, full adder and flip flops using ics.
tutorsglobe.com microbiology assignment help-homework help by online zoology tutors
tutorsglobe.com acquired immunity assignment help-homework help by online immunology tutors
Introduction to Marginal Costing and Break Even Analysis - Marginal Costing is not a technique of costing such as job, batch or contract costing. It is actually a method of costing where only variable manufacturing costs are taking into account when determining the cost of goods that are sold and also for valuation of inventories.
tutorial all along with the key concepts of Seismic Reflection Method, Seismic Refraction Methods, Seismic Waves , Types of Elastic Wave, Seismic Velocities, Velocities and the Time-Average Equation, Ray-Path Diagrams , Reflection and Refraction
The theory of strategic thinking along with the key concepts of strategy, coopetition, game theory, dominated strategy, nash equilibrium, network effect strategy, coopetition, game theory, dominated strategy, nash equilibrium, network effect and zero-sum game, get tutor's answer for managerial economics problems, homework help, assignment help.
tutorsglobe.com aggregate demand assignment help-homework help by online demand tutors
tutorsglobe.com operating cycle concept of working capital assignment help-homework help by online concept of working capital tutors
tutorsglobe.com relationship between kp and kc assignment help-homework help by online attainment of equilibrium in chemical reactions tutors
1950447
Questions Asked
3689
Tutors
1459341
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!