--%>
Assignment Help - homework help

  Special cases in Simplex Method

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

    Subject to

                        x1 + 4x2 + s1 = 8

                        x1 + 2x2 + s2 = 4

                        x1 , x2 , s1, s2  ≥ 0

 

 

 

Cj→

3

9

0

0

 

 

Basic Variables

CB

XB

X1

X2

S1

S2

XB / XK

S1 / X2

s1

0

8

1

4

1

0

1/4

s2

0

4

1

2

0

1

0/2→

 

 

Z = 0

 

-3

↑

-9

 

0

 

0

 

 

←Δj

s1

0

0

-1

0

1

-1

 

 

x2

9

2

1/2

1

0

1/2

 

 

 

 

Z =18

 

3/2

 

0

 

0

 

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

Subject to

4x1 + 3x2 ≤ 12

4x1 + x2 ≤ 8

4x1 - x2 ≤ 8

    &     x1 ≥ 0, x2  ≥ 0

 

Answer

Standard LPP

Max Z = 2x1 + x2 + 0s1 + 0s2 + 0s3

    Subject to

                        4x1 + 3x2 + s1 = 12

                        4x1 + x2 + s2 = 8

4x1 - x2 + s3 = 8

                        x1 , x2 , s1, s2, s3  ≥ 0

 

 

 

Cj→

2

1

0

0

0

 

 

 

Basic Varibles

CB

XB

X1

X2

S1

S2

S3

XB / XK

S1 / X1

S2 / X1

s1

0

12

4

3

1

0

0

12/4=3

 

 

s2

0

8

4

1

0

1

0

8/4=2

4/0=0

1/4

s3

0

8

4

-1

0

0

1

8/4=2

4/0=0

0/4=0→

 

 

Z = 0

↑

-2

 

-1

 

0

 

0

 

0

 

←Δj

 

 

s1

0

4

0

4

1

0

-1

4/4=1

 

 

s2

0

0

0

2

0

1

-1

0→

 

 

x1

2

2

1

-1/4

0

0

1/4

-

 

 

 

 

Z = 4

 

0

↑

-3/2

 

0

 

0

 

1/2

 

←Δj

 

 

s1

0

4

0

0

1

-2

1

0→

 

 

x2

1

0

0

1

0

1/2

-1/2

-

 

 

x1

2

2

1

0

0

1/8

1/8

16

 

 

 

 

Z = 4

 

0

 

0

 

0

 

3/4

↑

-1/4

 

←Δj

 

 

s3

   0         4

0

0

1

-2

1

 

 

 

x2

   1         2

0

1

1/2

-1/2

0

 

 

 

x1

   2        3/2

1

0

-1/8

3/8

0

 

 

 

 

 

Z = 5

 

0

 

0

 

1/4

 

1/4

 

0

 

←Δj

 

 

 

As all Δj ≥ 0, optimal basic feasible solution is achieved. Hence the solution is Max Z = 5, x1 = 3/2, x2 = 2