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
Theory and lecture notes of Stock Market all along with the key concepts of the stock market, Six Key Indicators of Macroeconomics and level of stock market. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Stock Market.
Insulating materials are exists in dissimilar shapes and sizes. Insulating materials are presented like Tapes, rolls, sleeves, paper and cloth.
tutorsglobe.com determinant of income and employment assignment help-homework help by online simple theory of income determination tutors
tutorsglobe.com harmful effects of algae assignment help-homework help by online algae tutors
Theory and lecture notes of Change in Price all along with the key concepts of change in price, Slutzky Equation, Slutzky Decomposition, Labor Supply application. Tutorsglobe offers homework help, assignment help and tutor’s assistance on change in price.
Coordination Chemistry tutorial all along with the key concepts of photosynthesis in plants, ionizable valence, electrostatic attraction, Ammonia-borane complexes, Coordinate covalent bonds
tutorsglobe.com film theory assignment help-homework help by online humanities tutors
www.tutorsglobe.com offers labor efficiency variance homework help, labor efficiency variance assignment help, answering questions to labor efficiency variance, accounting tutoring by online tutors.
Linear Collision tutorial all along with the key concepts of Classification of Collisions, Perfectly Inelastic Collision, Equations for Kinetic Energy and Linear Momentum, Energy lost in perfectly inelastic collisions, Explosions, Elastic and Inelastic Collisions, Elastic Collision Formula
periodic table-gradations of atomic properties tutorial all along with the key concepts of electronic configuration, periodic table and atomic properties, ionization energy, electron affinity and electronegativity
the various types of classification proposed through earlier taxonomists can be generally categorized into three systems– artificial, natural and phylogenetic.
Factors Affecting Strengths of Acids-Bases tutorial all along with the key concepts of Inductive effect, acidity of ethanoic acid, substitution X electron withdrawing, substituent X electron donating
www.tutorsglobe.com offers online brand management assignment help, brand management homework help, case study help, brand management coursework help, marketing question's answers and online tutoring by online tutors.
A report is a vehicle that carrying information. So, good reporting is essential for effective communication. You should know the requisites of a good report.
www.tutorsglobe.com offers coordination chemistry homework help, coordination chemistry assignment help, online tutoring assistance, inorganic chemistry solutions by online qualified tutor's help
1951073
Questions Asked
3689
Tutors
1469644
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!