X hits on this document

242 views

0 shares

29 / 63

c

j

Basic Variables

Quantity

4 x1

6 x2

0 s1

0 s2

0 s3

0 6 4

s x x

2 2 1

0 3 2

0 0 1

0 1 0

1/8 -1>8 1/4

1 0 0

-3>20 3/20 -1>10

z

j

26

4

6

1/4

0

1/2

Table A-31

The Optimal Simplex Tableau for a Degenerate Problem

Irregular Types of Linear Programming Problems

A-29

c j - z j

• 0

0

• -

1>4

0

• -

1>2

Notice that the optimal solution did not change from the third to the optimal simplex tableau. The graphical analysis of this problem shown in Figure A-8 reveals the reason for this.

Figure A-8 Graph of a degenerate solution

x2

8

6

6 x 1 + 4 x 2 = 2 4

4

A

B

x2 = 3

2

5 x 1 + 1 0 x 2 = 4 0

0

2

C 4

6

8

x1

Degeneracy occurs in a simplex problem when a problem continually loops back to the same solution or tableau.

Notice that in the third tableau (Table A-30) the simplex process went to point B, where all three constraint lines intersect. This is, in fact, what caused the tie for the pivot row and the degeneracy. Subsequently, the simplex process stayed at point B in the optimal tableau (Table A-31). The two tableaus represent two different basic feasible solutions correspond- ing to two different sets of model constraint equations.

Negative Quantity Values Occasionally a model constraint is formulated with a negative quantity value on the right side of the inequality sign—for example,

Standard form for simplex solution requires positive right- hand-side values.

A negative right-hand-side value

is changed to a positive by multiplying the constraint by -1, which changes the direction of the

inequality.

• -

6x1 + 2x2 Ú -30

This is an improper condition for the simplex method, because for the method to work, all quantity values must be positive or zero.

This difficulty can be alleviated by multiplying the inequality by -1, which also changes the direction of the inequality:

6 x 1 - 2 x 2 3 0 ( - 1 ) ( - 6 x 1 + 2 x 2 Ú - 3 0 )

 Document views 242 Page views 242 Page last viewed Sat Oct 22 03:50:00 UTC 2016 Pages 63 Paragraphs 3770 Words 30893