Lecture_9_Linear programming : Special cases in Simplex Method

9.1 Unbounded Solution

In some cases if the value of a variable is increased indefinitely, the constraints are not violated. This indicates that the feasible region is unbounded at least in one direction. Therefore, the objective function value can be increased indefinitely. This means that the problem has been poorly formulated or conceived.

In simplex method, this can be noticed if ?j value is negative to a variable (entering) which is notified as key column and the ratio of solution value to key column value is either negative or infinity (both are to be ignored) to all the variables. This indicates that no variable is ready to leave the basis, though a variable is ready to enter. We cannot proceed further and the solution is unbounded or not finite.

Example 1
Max Z = 6x1 - 2x2 Subject to
2x1 - x2 ? 2
x1 ? 4
and x1 ? 0, x2 ? 0

Solution
Standard LPP
Max Z = 6x1 - 2x2 + 0s1 + 0s2 Subject to
2x1 - x2 + s1 = 2 x1 + s2 = 4
x1 , x2 , s1, s2 ? 0
The optimal solution is x1 = 4, x2 = 6 and Z =12

In the starting table, the elements of x2 are negative and zero. This is an indication that the feasible region is not bounded. From this we conclude the problem has unbounded feasible region but still the optimal solution is bounded.


Example 2

Max Z = -3x1 + 2x2 Subject to
x1 ? 3
x1 - x2 ? 0
and x1 ? 0, x2 ? 0

Solution
Standard LPP
Max Z = -3x1 + 2 x2 + 0s1 + 0s2
Subject to
x1 + s1 = 3
x1 - x2 + s2 = 0 x1 , x2 , s1, s2 ?0