|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Simplex Method |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Some Special Cases | 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.
3. No Feasible Solution
If in course of simplex 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. For example, let us consider the following problem.
Example
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
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
| 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 problem has no feasible solution.
