# Irregular Types of Linear Programming Problems

A-27

Figure A-7 An unbounded problem

x_{2 }

12

10

8

6

4

Z = 4x + 2x

1

2

2

0

2

4

6

8

10

12

x_{1 }

4

2

0

0

Quantity

x_{1 }

x_{2 }

s_{1 }

s_{2 }

4

0

0

-1

0

2

1

1

0

1

16

4

0

-4

0

0

2

4

0

c

j

Basic Variables

4 0

x s

1 2

z c -z

j

j

j

In Figure A-7 the objective function is shown to increase without bound; thus, a solution is never reached.

Table A-28 The Second Simplex Tableau

4 , -1 = -4 2,0= q

Unlimited profits are not possible in the real world; an unbounded solution, like an infeasible solution, typically reflects an error in defining the problem or in formulating the model.

A pivot row cannot be selected for an unbounded problem.

The second tableau for this problem is shown in Table A-28. In this simplex tableau, s_{1 }is chosen as the entering nonbasic variable and pivot column. However, there is no pivot row or leaving basic variable. One row value is -4 and the other is undefined. This indicates that a “most constrained” point does not exist and that the solution is unbounded. In gen- eral, a solution is unbounded if the row value ratios are all negative or undefined.

A tie for the pivot column is broken arbitrarily.

( o r ) Tie for the Pivot Column Sometimes when selecting the pivot column, you may notice that the greatest positive r o w v a l u e s a r e t h e s a m e ; t h u s , t h e r e i s a t i e f o r t h e p i v o t c o l u m n . W h e n z j - c j c j - z j this happens, one of the two tied columns should be selected arbitrarily. Even though one choice may require fewer subsequent iterations than the other, there is no way of knowing this beforehand.

Tie for the Pivot Row—Degeneracy It is also possible to have a tie for the pivot row (i.e., two rows may have identical lowest nonnegative values). Like a tie for a pivot column, a tie for a pivot row should be broken arbitrarily. However, after the tie is broken, the basic variable that was the other choice for