Simplex Method: Unbounded Solution
First we will talk about the Unbounded Solution in linear programming (LP) with the help of an example and after that we will take an example of No Feasible Solution in next section.
If in course of simplex computation zj - cj < 0, but minimum positive value is ≤ 0 then the problem has an unbounded solution.
Unbounded Solution Example: LPP
Maximize 5x1 + 4x2
subject to
x1 ≤ 7
x1 - x2 ≤ 8
x1, x2 ≥ 0.
Solution.
Converting inequalities to equalities
x1 + x3 = 7
x1 - x2 + x4 = 8
x1, x2, x3, x4 ≥
0.
Where x3 and x4 are slack variables.
Table 1: Simplex Method
| cj | 5 | 4 | 0 | 0 | ||
|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | Solution values b (=XB) |
| 0 | x3 | 1 | 0 | 1 | 0 | 7 |
| 0 | x4 | 1 | -1 | 0 | 1 | 8 |
| zj-cj | -5 | -4 | 0 | 0 |
Table 2
| cj | 5 | 4 | 0 | 0 | ||
|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | Solution values b (=XB) |
| 5 | x1 | 1 | 0 | 1 | 0 | 7 |
| 0 | x4 | 0 | -1 | -1 | 1 | 1 |
| zj-cj | 0 | -4 | 5 | 0 |
Since minimum positive value is infinity, it is not possible to proceed with the simplex computation any further. This is the criterion for unbounded solution.
