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
online mcat exam preparation course and online mcat tutoring package offered by tutorsglobe are the most comprehensive and customized collection of study resources on the web, offering best collection of mcat practice papers, quizzes, mcat test papers, and guidance.
Microwave transmission considers to the technology of transmitting information through the make use of the radio waves which wavelengths are measured conveniently in small numbers of centimetres, via using several electronic technologies.
tutorsglobe.com applications of plant tissue culture assignment help-homework help by online plant tissue culture tutors
Theory of Breadth First Search including the key concepts of JAR Problem, Uninformed Search, Assignment help and Homework help
Benzopyridines tutorial all along with the key concepts of Quinoline, Skraup Synthesis, Friedlander Synthesis, Methylquinolines, Aminoquinolines, Conrad-Limpach-Knorr Synthesis, Isoquinoline, Bischler-Napieralski Synthesis and Pictet-Spengler Synthesis
Theory and lecture notes of Structure of Data management system all along with the key concepts of structure of data management system, Dictionary, Data Base manager, Data Communications, Transaction Management. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Structure of Data management system.
Lens Formula and Spectra tutorial all along with the key concepts of Lens Formula, Lens Makers' Equation, Dispersion and Spectra, Emission spectra, Kinds of Spectra, Line Spectra, Band Spectra, Continuous Spectra, Absorption Spectra
Nature of Operating Costing - The major purpose of operating costing is to calculate the cost of the services that are offered by the organization.
www.tutorsglobe.com offers answering questions to types of barriers and curves of monopoly, economics assignment help- homework help.
www.tutorsglobe.com offers Function and Procedure sub program homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
tutorsglobe.com meaning of production assignment help-homework help by online economies of large scale production tutors
Get Un-Matched Custom Research Papers Assignment Help by PhD tutors at rational prices that you need today for securing top grades!
www.tutorsglobe.com offers workshop planning approach homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
Theory and lecture notes of International Economic Policy all along with the key concepts of Classical Gold Standard, Contractionary Policies, Collapse of Gold Standard, Bretton Woods System. Tutorsglobe offers homework help, assignment help and tutor’s assistance on International Economic Policy.
Synthetic Dyes-Fibres tutorial all along with the key concepts of Advantages and Disadvantages of Synthetic Fibre, properties of synthetic substances, tensile strengths
1959105
Questions Asked
3689
Tutors
1496396
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!