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 determinants of investment assignment help-homework help by online investment function tutors
Matrix Assignment Help service offer ideal papers at affordable prices to secure A++ grades with 24x7 accessible PhD experts.
tutorsglobe.com virulence factors assignment help-homework help by online pathogenic attributes of bacteria tutors
Avail the best Discrete Mathematics Assignment Help and meet up the expectations of your professors and score A++ at feasible prices.
The issued share capital or allotted share capital is share capital that has been issued to shareholders.
tutorsglobe.com diseases caused by mycoplasmas assignment help-homework help by online mycoplasma tutors
tutorsglobe.com biosynthesis of phospholipids assignment help-homework help by online phospholipids tutors
how transactions impact the accounting equation, and distinguishing between revenue and income, www.tutorsglobe.com offers assignment help, homework help and online tutoring.
tutorsglobe.com factors affecting stomatal movement assignment help-homework help by online water transport tutors
www.tutorsglobe.com offers representation format of an object homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
tutorsglobe.com root modifications assignment help-homework help by online root system tutors
www.tutorsglobe.com offers leveling of dfd homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
www.tutorsglobe.com offer theory and concepts of the journal, journal entries assignment help, journal entries homework help and preparing journal entries based questions answers.
tutorsglobe.com method of computing cost of capital assignment help-homework help by online cost of capital tutors
Theory and Concept about Parametric Equations all along with the key concepts of parametric equations, Orientation or Direction, Graphing Calculator, Window Settings, Eliminating the Parameter. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Concept about Parametric Equations.
1961854
Questions Asked
3689
Tutors
1441251
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!