No Feasible Solution: Simplex Method
If in course of simplex method computation, one or more artificial variables remain in the basis at positive level at the end of phase 1 computation, the problem has no feasible solution (Infeasible Solution).
For example, let us consider the following linear program problem (LPP).
No Feasible Solution Example (Infeasible Solution): LPP
Maximise -200x1 - 300x2
subject to
2x1 + 3x2 ≥ 1200
x1 + x2 ≤ 400
2x1 + 3/2x2 ≥
900
x1, x2 ≥ 0
Solution.
After introducing slack, surplus and artificial variables the problem can be presented as
Maximise -200x1 - 300x2
subject to
2x1 + 3x2 - x3 + A1 = 1200
x1 + x2 + x4 = 400
2x1 + 3/2x2 - x5 + A2 =
900
Where:
A1 and A2 are artificial variables.
x4 is a slack variable.
x3 and x5 are surplus variables.
The problem is solved by two phase method.
Phase 1 of two phase method
Maximise -A1 - A2
subject to
2x1 + 3x2 - x3 + A1 = 1200
x1 + x2 + x4 = 400
2x1 + 3/2x2 - x5 + A2 =
900
x1, x2, x3, x4, x5, A1, A2 ≥ 0
Table 1: Simplex Method
| cj | 0 | 0 | 0 | 0 | 0 | -1 | -1 | ||
|---|---|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | x5 | A1 | A2 | Solution values b (=XB) |
| -1 | A1 | 2 | 3 | -1 | 0 | 0 | 1 | 0 | 1200 |
| 0 | x4 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 400 |
| -1 | A2 | 2 | 3/2 | 0 | 0 | -1 | 0 | 1 | 900 |
| zj-cj | -4 | -9/2 | 1 | 0 | 1 | 0 | 0 |
Table 2
| cj | 0 | 0 | 0 | 0 | 0 | -1 | ||
|---|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | x5 | A2 | Solution values b (=XB) |
| 0 | x2 | 2/3 | 1 | -1/3 | 0 | 0 | 0 | 400 |
| 0 | x4 | 1/3 | 0 | 1/3 | 1 | 0 | 0 | 0 |
| -1 | A2 | 1 | 0 | 1/2 | 0 | -1 | 1 | 300 |
| zj-cj | -1 | 0 | -1/2 | 0 | 1 | 0 |
Table 3
| cj | 0 | 0 | 0 | 0 | 0 | -1 | ||
|---|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | x5 | x6 | Solution values b (=XB) |
| 0 | x2 | 0 | 1 | -1 | -2 | 0 | 0 | 400 |
| 0 | x1 | 1 | 0 | 1 | 3 | 0 | 0 | 0 |
| -1 | A2 | 0 | 0 | -1/2 | -3 | -1 | 1 | 300 |
| zj-cj | 0 | 0 | 1/2 | 3 | 1 | 0 |
In the above table, the optimum solution still contains the artificial variable A2 in the basis at positive level, this indicates that the linear program problem has no feasible solution (Infeasible Solution).
