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 root-stem and leaf assignment help-homework help by online plant morphology tutors
tutorsglobe.com pathogenesis of hiv assignment help-homework help by online hiv tutors
electronic transfer tutorial all along with the key concepts of drude model, origin of collision time, thermal conductivity, motion in a magnetic field, cyclotron resonance and hall effect
tutorsglobe.com myxoedema assignment help-homework help by online thyroid gland and thyroxine tutors
Theory and lecture notes of Externalities and Public Goods all along with the key concepts of Market Failure, Resource Allocation, Market Performance, Imperfect Competition, Externalities. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Externalities and Public Goods.
tutorsglobe.com definition of market assignment help-homework help by online business economics tutors
theory and lecture notes of static characteristics iv, all along with the key concepts of drive capability, fan-out, assignment help and homework help. tutorsglobe offers homework help, assignment help and tutor’s assistance on static characteristics iv.
Refraction of Light tutorial all along with the key concepts of Refraction of Light through Rectangular Glass, Snell's law, Refraction of Light through Prism, Laws of Refraction, Real and Apparent Depths, total Internal Reflection
The ways by which unscrupulous directors can compute the financial statements are many and varied. Though, they generally include adopting novel or unorthodox practices for reporting main elements of the financial statements like revenue, expenses, assets and liabilities.
Reasons for Difference in Profit - Items of Financial Nature not recorded in Cost Accounts, Items Charged to Profit and Loss Account but not Recorded in Cost Accounts.
tutorsglobe.com industrial production of penicillin assignment help-homework help by online penicillin production tutors
For Soldering, electric irons are usually employed on small armatures and gas irons on the larger ones.
Free GCSE Study Guide, GCSE Test Papers, GCSE Practice papers, GCSE Test pattern and general information, Find GCSE exam information and resource, material free at Tutorsglobe.com
Theory and lecture notes of Building Blocks of the Flexible-Price Model all along with the key concepts of Potential Output, Real Wages, equilibrium level of real GDP, continue real GDP, composition of real GDP. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Building Blocks of the Flexible-Price Model.
tutorsglobe.com net present value assignment help-homework help by online capital budgeting and project planning tutors
1964427
Questions Asked
3689
Tutors
1460722
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!