Unbounded Solution

Unbounded Solution
The unbounded solution is explained in the following Example.
Example
Consider the following linear programming problem.
Maximize 5x1 + 4x2
Subject to:
x1 – x2 ? 8
x1 ? 7
x1, x2 ? 0.
Solution :
Introduce the slack variables s3 and s4, so that the inequalities becomes as equation as follows:
x1 + s3 = 7
x1 – x2 + s4 = 8
x1, x2, s3, s4 ? 0.
The calculation of simplex procedures and tables are as follows:



Note that z2 - c2 < 0 which indicates x2 should be introduced as a basic variable in the next iteration. However, both y12 ? 0, y22 ? 0.
Thus, it is not possible to proceed with the simplex method of calculation any further as we cannot decide which variable will be non-basic at the next iteration. This is the criterion for unbounded solution.
NOTE: If in the course of simplex computation zj-cj < 0 but yij ? 0 for all i then the problem has no finite solution.
But in this case we may observe that the variable x2 is unconstrained and can be increased arbitrarily. This is why the solution is unbounded.

The solutions of the exercises:
Exercise 1: Maximize f(x,y)=5x+y
Subject to
x+2y+z?6
4x+3y?120
x,y?0
Solution: