X hits on this document

402 views

0 shares

0 downloads

0 comments

28 / 63

A-28

Module A

The Simplex Solution Method

A tie for the pivot row is broken arbitrarily and can lead to degeneracy.

the leaving basic variable will have a quantity value of zero in the next tableau. This condi- tion is commonly referred to as degeneracy because theoretically it is possible for subse- quent simplex tableau solutions to degenerate so that the objective function value never improves and optimality never results. This occurs infrequently, however.

In general, tableaus with ties for the pivot row should be treated normally. If the simplex steps are carried out as usual, the solution will evolve normally.

The following is an example of a problem containing a tie for the pivot row:

maximize Z = 4x1 + 6x2

subject to

x 1 , x 2 Ú 0 5 x 1 + 1 0 x 2 4 0 x 2 3 6 x 1 + 4 x 2 2 4

The Second Simplex Tableau

Basic

4

6

0

0

0

with a Tie for the Pivot Row

j c

Variables

Quantity

x1

x2

s1

s2

s3

Table A-29

For the sake of brevity we will skip the initial simplex tableau for this problem and go directly to the second simplex tableau in Table A-29, which shows a tie for the pivot row between the s1 and s3 rows.

12

6

0

1

-4

0

3

0

1

0

1

0

10

5

0

0

- 10

1

18

0

6

0

6

0

4

0

0

-6

0

12 , 6 = 2

10 , 5 = 2

f

Tie

0

s1

6 0

x s

2 3

j

j

z c -z

j

4

6

0

0

0

Quantity

x1

x2

s1

s2

s3

0

0

0

1

8

-6>5

3

0

1

0

1

0

2

1

0

0

-2

1/5

26

4

6

0

-2

4/5

0

0

0

2

-4>5

The s3 row is selected arbitrarily as the pivot row, resulting in the third simplex tableau, shown in Table A-30.

z j

c j - z j

x

2

x

1

Basic Variables

Table A-30

0 6 4

s

1

The Third Simplex Tableau with Degeneracy

c j

Note that in Table A-30 a quantity value of zero now appears in the s1 row, representing the degenerate condition resulting from the tie for the pivot row. However, the simplex process should be continued as usual: s2 should be selected as the entering basic variable and the s1 row should be selected as the pivot row. (Recall that the pivot row value of zero is the minimum nonnegative quotient.) The final optimal tableau is shown in Table A-31.

Document info
Document views402
Page views402
Page last viewedFri Dec 09 14:10:22 UTC 2016
Pages63
Paragraphs3770
Words30893

Comments