|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Simplex Method |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Some Special Cases
|
1. Unrestricted (unconstrained) Variables
Sometimes decision variables are unrestricted in sign (positive, negative or zero). In all such cases, the decision variables can be expressed as the difference between two non-negative variables. For example, if x1 is unrestricted in sign, then
Put x1 = x1' - x1''
Example
Maximize z = 2x1 + 3x2
subject to
-x1 + 2x2 £
4
x1 + x2 £ 6
x1 + 3x2 £ 9
x1, x2 are unrestricted in sign
Solution.
Since x1 and x2 are unrestricted in sign, we can replace them by non-negative variables x1' , x1'', x2' , x2'' .
Put x1 = x1' - x1''
x2 = x2' - x2''
The given problem can be written as
Max. z = 2(x1' - x1'') + 3(x2' - x2'')
subject to
-(x1' - x1'') + 2(x2'
- x2'') £ 4
(x1' - x1'') + (x2'
- x2'') £ 6
(x1' - x1'') + 3(x2'
- x2'') £ 9
Introducing slack variables
Max. z = 2x1' - 2x1'' + 3x2' - 3x2''
subject to
-x1' + x1'' + 2x2'
- 2x2'' + x3 = 4
x1' - x1'' + x2'
- x2'' + x4 = 6
x1' - x1'' + 3x2'
- 3x2'' + x5 = 9
Where x3, x4 and x5 are slack variables
Table 1
|
|
cj | 2 | -2 | 3 | -3 | 0 | 0 | 0 |
|
|---|---|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1' | x1'' | x2' | x2'' | x3 | x4 | x5 | Solution values b (=XB) |
| 0 | x3 | -1 | 1 | 2 | -2 | 1 | 0 | 0 | 4 |
| 0 | x4 | 1 | -1 | 1 | -1 | 0 | 1 | 0 | 6 |
| 0 | x5 | 1 | -1 | 3 | -3 | 0 | 0 | 1 | 9 |
| zj-cj |
|
-2 | 2 | -3 | 3 | 0 | 0 | 0 |
|
Key column = x2' column.
Minimum (4/2, 6/1, 9/3) = 2
Key row = x3 row.
Pivot element =
2
x3 departs and x2'
enters.
Table 2
|
|
cj | 2 | -2 | 3 | -3 | 0 | 0 | 0 |
|
|---|---|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1' | x1'' | x2' | x2'' | x3 | x4 | x5 | Solution values b (=XB) |
| 3 | x2' | -1/2 | 1/2 | 1 | -1 | 1/2 | 0 | 0 | 2 |
| 0 | x4 | 3/2 | -3/2 | 0 | 0 | -1/2 | 1 | 0 | 4 |
| 0 | x5 | 5/2 | -5/2 | 0 | 0 | -3/2 | 0 | 1 | 3 |
| zj-cj |
|
-7/2 | 7/2 | 0 | 0 | 3/2 | 0 | 0 |
|
Table 3
|
|
cj | 2 | -2 | 3 | -3 | 0 | 0 | 0 | |
|---|---|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1' | x1'' | x2' | x2'' | x3 | x4 | x5 | Solution values b (=XB) |
| 3 | x2' | 0 | 0 | 1 | -1 | 1/5 | 0 | 1/5 | 13/5 |
| 0 | x4 | 0 | 0 | 0 | 0 | 2/5 | 1 | -3/5 | 11/5 |
| 2 | x1' | 1 | -1 | 0 | 0 | -3/5 | 0 | 2/5 | 6/5 |
| zj-cj |
|
0 | 0 | 0 | 0 | -3/5 | 0 | 7/5 |
|
Table 4
|
|
cj | 2 | -2 | 3 | -3 | 0 | 0 | 0 | |
|---|---|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1' | x1'' | x2' | x2'' | x3 | x4 | x5 | Solution values b (=XB) |
| 3 | x2' | 0 | 0 | 1 | -1 | 0 | -1/2 | 1/2 | 3/2 |
| 0 | x3 | 0 | 0 | 0 | 0 | 1 | 5/2 | -3/2 | 11/2 |
| 2 | x1' | 1 | -1 | 0 | 0 | 0 | 3/2 | -1/2 | 9/2 |
| zj-cj |
|
0 | 0 | 0 | 0 | 0 | 3/2 | 1/2 |
|
The optimal solution is:
x1' = 9/2, x1'' = 0, x2'
= 3/2, x2'' = 0.
Solution of the original problem is:
x1 = x1' - x1'' = 9/2 -
0 = 9/2
x2 = x2' - x2'' = 3/2 -
0 = 3/2
z = 2 X 9/2 + 3 X 3/2 = 27/2.
