Page 261 -

SPECIAL CASES 241

Furthermore, because a i2 0 for all i, none of the current basic variables will be
driven to zero, no matter how many units of x 2 we introduce. So, we can introduce an
infinite amount of x 2 into solution and still maintain feasibility. Because each unit of
x 2 increases the objective function by 5, we will have an unbounded solution. Hence,
the way we recognize the unbounded situation is that all the a ij are less than or equal to
zero in the column associated with the incoming variable.
To illustrate this concept, let us consider the following example of an unbounded
problem.

Max 20x 1 þ 10x 2
s:t: 1x 1 2
1x 2 5
x 1 ; x 2 0
We subtract a surplus variable s 1 from the first constraint equation and add a slack
variable s 2 to the second constraint equation to obtain the standard-form representa-
tion. We then add an artificial variable a 1 to the first constraint equation to obtain the
tableau form. In the initial simplex tableau the basic variables are a 1 and s 2 .After
bringing in x 1 and removing a 1 at the first iteration, the tableau is as follows:

x 1 x 2 s 1 s 2
Basis c B 20 10 0 0

x 1 20 1 0 1 0 2
s 2 0 0 1 0 1 5
20 0 20 0 40
z j
0 10 20 0
c j – z j

Because s 1 has the largest positive c j – z j , we know we can increase the value of the
objective function most rapidly by bringing s 1 into the basis. But a 13 ¼ 1and a 23 ¼ 0;
hence, we cannot form the ratio b i /a i3 for any a i3 > 0 because no values of a i3 are
greater than zero. This result indicates that the solution to the linear programme is
unbounded because each unit of s 1 that is brought into solution provides one extra unit
of x 1 (since a 13 ¼ 1) and drives zero units of s 2 out of solution (since a 23 ¼ 0).
Because s 1 is a surplus variable and can be interpreted as the amount of x 1 over
the minimum amount required, the simplex tableau indicates we can introduce
as much of s 1 as we desire without violating any constraints; the interpretation is
that we can make as much as we want above the minimum amount of x 1
required. Because the objective function coefficient associated with x 1 is positive,
there will be no upper bound on the value of the objective function.
In summary, a maximization linear programme is unbounded if it is possible to
make the value of the optimal solution as large as desired without violating any of
the constraints. When employing the Simplex method, an unbounded linear pro-
gramme exists if at some iteration, the Simplex method tells us to introduce variable j
into the solution and all the a ij are less than or equal to zero in the jth column.
Try Problem 19 for We emphasize that the case of an unbounded solution will never occur in real cost
another example of an minimization or profit maximization problems because it is not possible to reduce costs
unbounded problem.
to minus infinity or to increase profits to plus infinity. So, if we encounter an
unbounded solution to a linear programming problem, we should carefully reexamine
the formulation of the problem to determine whether a formulation error has occurred.

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.