Big M Simplex Method
Let's solve the following linear programming (LP) example with the help of this method.
We will use the same process as used in previous example.
Big M Simplex Method Example: LPP
Maximize z = -4x1 - 2x2
subject to
3x1 + x2 ≥ 27
x1 + x2 ≥ 21
x1 + 2x2 ≥ 30
x1, x2 ≥ 0
Solution.
By introducing surplus and artificial variables, the standard form of LPP becomes
Maximize z = -4x1 - 2x2 + 0x3 + 0x4 + 0x5 – MA1 – MA2 – MA3
3x1 + x2 - x3 + A1 = 27
x1 + x2 - x4 + A2 = 21
x1 + 2x2 - x5 + A3 = 30
x1 ,x2, x3, x4, x5, A1, A2 ≥ 0
Where:
x4 and x5 are surplus variables
A1 and A2 are artificial variables.
Table 1
| cj | -4 | -2 | 0 | 0 | 0 | –M | –M | –M | ||
|---|---|---|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | x5 | A1 | A2 | A3 | Solution values b (= XB) |
| –M | A1 | 3 | 1 | -1 | 0 | 0 | 1 | 0 | 0 | 27 |
| -M | A2 | 1 | 1 | 0 | -1 | 0 | 0 | 1 | 0 | 21 |
| –M | A3 | 1 | 2 | 0 | 0 | -1 | 0 | 0 | 1 | 30 |
| zj–cj | -5M + 4 | -4M + 2 | M | M | M | 0 | 0 | 0 |
As -5M < -4M, x1 becomes a basic variable in the
next iteration
Key column = x1 column.
Minimum (27/3, 21/1, 30/1) = 9
Key row = A1 row
Pivot element = 3.
A1 departs and x1 enters.
Table 2
| cj | -4 | -2 | 0 | 0 | 0 | –M | –M | ||
|---|---|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | x5 | A2 | A3 | Solution values b (= XB) |
| –4 | x1 | 1 | 1/3 | -1/3 | 0 | 0 | 0 | 0 | 9 |
| -M | A2 | 0 | 2/3 | 1/3 | -1 | 0 | 1 | 0 | 12 |
| –M | A3 | 0 | 5/3 | 1/3 | 0 | -1 | 0 | 1 | 21 |
| zj–cj | 0 | -7M/3 + 2/3 | -2M/3 - 4/3 | M | M | 0 | 0 |
Table 3
| cj | -4 | -2 | 0 | 0 | 0 | –M | ||
|---|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | x5 | A2 | Solution values b (= XB) |
| –4 | x1 | 1 | 0 | -2/5 | 0 | 1/5 | 0 | 24/5 |
| –M | A2 | 0 | 0 | 1/5 | -1 | 2/5 | 1 | 18/5 |
| -2 | x2 | 0 | 1 | 1/5 | 0 | -3/5 | 0 | 63/5 |
| zj–cj | 0 | 0 | -M/5 + 6/5 | M | -2M/5 + 2/5 | 0 |
Final Optimal Table: Big M Simplex Method
| cj | -4 | -2 | 0 | 0 | 0 | ||
|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | x5 | Solution values b (= XB) |
| –4 | x1 | 1 | 0 | -1/2 | 1/2 | 0 | 3 |
| 0 | x5 | 0 | 0 | 1/2 | -5/2 | 1 | 9 |
| -2 | x2 | 0 | 1 | 1/2 | -3/2 | 0 | 18 |
| zj–cj | 0 | 0 | 1 | 1 | 0 |
The optimal solution is
x1 = 3, x2 = 18
z = -4 X 3 - 2 X 18 = -48
