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
Acquire Environmental Conservation and Restoration Assignment Help by top professionals at pocket friendly prices with 24/7 support
Potentiometric Titration tutorial all along with the key concepts of Principle of Potentiometric Titration, Location of End Point in Potentiometric Titration, Types of Potentiometric Titration and Redox Titration of Manganese by Potentiometry
Parasitic helminths and lifecycles tutorial all along with the key concepts of Types of Host, Definitive Host, Intermediate Host, Accidental Host, Paratenic Host and Reservoir Host
to learn the two inputs of the arithmetic circuits of half adder, full adder and flip flops using ics.
tutorsglobe.com androecium assignment help-homework help by online position of flower tutors
tutorsglobe.com activation of adaptive immunity assignment help-homework help by online acquired immunity tutors
Recording Seismic Signals tutorial all along with the key concepts of Single-Channel Seismographs, Multi-Channel Seismographs
Explain inventory control - define Perpetual Inventory System, ABC System, Just in Time Inventory, VED Analysis, and FSND Analysis.
elastic properties of solids tutorial all along with the key concepts of concept of elasticity, statement of hooke's law, verification of hooke's law, young's modulus of elasticity and elastic potential energy
tutorsglobe.com runner assignment help-homework help by online sub-aerial modifications tutors
Theory of Searching and their types including the key concepts of Binary Search, Binary Search Tree, Variations on Binary Trees, Dictionary, Collision Handling and Hash Table variations
Blood and Tissue nematodes tutorial all along with the key concepts of Filarial worms, Wuchereria bancrofti, Onchocerca volvulus, Loa loa, Brugia malayi, characteristic and Pathology of Lymphatic filariasis and Trichinella spiralis
tutorsglobe.com functions of stem assignment help-homework help by online shoot system tutors
Theory and lecture notes of Demography and the Natural Rate all along with the key concepts of demography and the natural rate, homework help, assignment help. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Demography and the Natural Rate.
tutorsglobe.com vaccines assignment help-homework help by online immunology tutors
1946783
Questions Asked
3689
Tutors
1483335
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!