Two Phase Simplex Method: Linear Programming
Let's solve the following problem with the two phase simplex method. We will use the same process as used in the last example.
Two Phase Simplex Method Example
Maximize z = 12x1 + 15x2 + 9x3
subject to
8x1 + 16x2 + 12x3 ≤
250
4x1 + 8x2 + 10x3 ≥
80
7x1 + 9x2 + 8x3 = 105
x1, x2, x3 ≥ 0
Solution.
Introducing slack, surplus & artificial variables
8x1 + 16x2 + 12x3 + x4 = 250
4x1 + 8x2 + 10x3 – x5 + A1 = 80
7x1 + 9x2 + 8x3 + A2 = 105
Where:
x4 is a slack variable.
x5 is a surplus variable.
A1& A2 are artificial variables.
Phase 1
Maximize 0x1 + 0x2 + 0x3 + 0x4 + 0x5 + (–A1) + (–A2)
subject to
8x1 + 16x2 + 12x3 + x4 = 250
4x1 + 8x2 + 10x3 – x5 + A1 = 80
7x1 + 9x2 + 8x3 + A2 = 105
x1, x2, x3, x4, x5, A1, A2 ≥ 0
Equating x1, x2, x3, x5 to zero.
Initial basic feasible solution
x4 = 250, A1= 80 , A2 = 105
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) |
| 0 | x4 | 8 | 16 | 12 | 1 | 0 | 0 | 0 | 250 |
| -1 | A1 | 4 | 8 | 10 | 0 | -1 | 1 | 0 | 80 |
| -1 | A2 | 7 | 9 | 8 | 0 | 0 | 0 | 1 | 105 |
| zj–cj | -11 | -17 | -18 | 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 | x4 | 16/5 | 32/5 | 0 | 1 | 6/5 | 0 | 154 |
| 0 | x3 | 2/5 | 4/5 | 1 | 0 | -1/10 | 0 | 8 |
| -1 | A2 | 19/5 | 13/5 | 0 | 0 | 4/5 | 1 | 41 |
| zj-cj | -19/5 | -13/5 | 0 | 0 | -4/5 | 0 |
Here, Phase 1 terminates because both the artificial variables have been removed from the basis.
Phase 2 of Two Phase Simplex Method
Table 3
| cj | 12 | 15 | 9 | 0 | 0 | ||
|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | x5 | Solution values b (= XB) |
| 0 | x4 | 0 | 80/19 | 0 | 1 | 10/19 | 2270/19 |
| 9 | x3 | 0 | 10/19 | 1 | 0 | -7/38 | 70/19 |
| 12 | x1 | 1 | 13/19 | 0 | 0 | 4/19 | 205/19 |
| zj-cj | 0 | -39/19 | 0 | 0 | 33/38 |
Table 4
| cj | 12 | 15 | 9 | 0 | 0 | ||
|---|---|---|---|---|---|---|---|
| cB | Basic variables B |
x1 | x2 | x3 | x4 | x5 | Solution values b (= XB) |
| 0 | x4 | 0 | 0 | -8 | 1 | 2 | 90 |
| 15 | x2 | 0 | 1 | 19/10 | 0 | -7/20 | 7 |
| 12 | x1 | 1 | 0 | -13/10 | 0 | 9/20 | 6 |
| zj-cj | 0 | 0 | 39/10 | 0 | 3/20 |
The optimal solution is:
x1 = 6, x2 = 7, x3 = 0
z = 12 X 6 + 15 X 7 + 9 X 0 = 177.
Well, after going through this section you
definitely deserve 
some food. Before moving to the next section, you must take a break
because you really deserve it.
