# 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 = 4x_{1 }+ 6x_{2 }

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

x_{1 }

x_{2 }

s_{1 }

s_{2 }

s_{3 }

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 s_{1 }and s_{3 }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

s_{1 }

6 0

x s

2 3

j

j

z c -z

j

4

6

0

0

0

Quantity

x_{1 }

x_{2 }

s_{1 }

s_{2 }

s_{3 }

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 s_{3 }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 s_{1 }row, representing the degenerate condition resulting from the tie for the pivot row. However, the simplex process should be continued as usual: s_{2 }should be selected as the entering basic variable and the s_{1 }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.