Numerical Methods and Optimization

The Simplex Method for Linear Programming 245

the basic variable representing a row that wins the ratio test. However, if all

coefficients in the pivot column of the dictionary are positive, the ratio test

produces no result. For example, consider the following dictionary:

z =90− 25x

1

+4x

2

s

1

=25− 14x

1

+ x

2

s

2

=30− x

1

s

3

=12+ 5x

1

+14x

2

s

4

=22− 4x

1

+7x

2

.

The only entering variable candidate is x

2

. However, when we try to do the

ratio test, none of the rows participates. Because the coefficient for x

2

is

nonnegative in each row, we can increase x

2

to +∞ without violating any

of the constraints. When x

2

increases to +∞,sodoesz, thus the problem is

unbounded. The tableau