Let's solve the following problem with the **two phase simplex method**. We will use the same process as used in the last example.

Maximize z = 12x_{1} + 15x_{2} + 9x_{3}

subject to

8x_{1} + 16x_{2} + 12x_{3} ≤
250

4x_{1} + 8x_{2} + 10x_{3} ≥
80

7x_{1} + 9x_{2} + 8x_{3} = 105

x_{1}, x_{2}, x_{3} ≥
0

Solution.

Introducing slack, surplus & artificial variables

8x_{1} + 16x_{2} + 12x_{3} + x_{4} = 250

4x_{1} + 8x_{2} + 10x_{3} – x_{5} + A_{1} = 80

7x_{1} + 9x_{2} + 8x_{3} + A_{2 }= 105

Where:

x_{4} is a slack variable.

x_{5} is a surplus variable.

A_{1}& A_{2 }are artificial variables.

Maximize 0x_{1 }+ 0x_{2} + 0x_{3} + 0x_{4} + 0x_{5} +
(–A_{1}) + (–A_{2})

subject to

8x_{1} + 16x_{2} + 12x_{3} + x_{4} = 250

4x_{1} + 8x_{2} + 10x_{3} – x_{5} + A_{1} = 80

7x_{1} + 9x_{2} + 8x_{3} + A_{2 }= 105

x_{1}, x_{2}, x_{3}, x_{4}, x_{5},
A_{1}, A_{2} ≥ 0

Equating x_{1}, x_{2}, x_{3}, x_{5 }to
zero.

Initial basic feasible solution

x_{4} = 250, A_{1}= 80 , A_{2 }= 105

Table 1

c_{j} |
0 | 0 | 0 | 0 | 0 | -1 | -1 | ||
---|---|---|---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1} |
x_{2} |
x_{3} |
x_{4} |
x_{5} |
A_{1} |
A_{2} |
Solution values b (= X _{B}) |

0 | x_{4} |
8 | 16 | 12 | 1 | 0 | 0 | 0 | 250 |

-1 | A_{1} |
4 | 8 | 10 | 0 | -1 | 1 | 0 | 80 |

-1 | A_{2} |
7 | 9 | 8 | 0 | 0 | 0 | 1 | 105 |

z_{j}–c_{j} |
-11 | -17 | -18 | 0 | 1 | 0 | 0 |

Table 2

c_{j} |
0 | 0 | 0 | 0 | 0 | -1 | ||
---|---|---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1} |
x_{2} |
x_{3} |
x_{4} |
x_{5} |
A_{2} |
Solution values b (= X _{B}) |

0 | x_{4} |
16/5 | 32/5 | 0 | 1 | 6/5 | 0 | 154 |

0 | x_{3} |
2/5 | 4/5 | 1 | 0 | -1/10 | 0 | 8 |

-1 | A_{2} |
19/5 | 13/5 | 0 | 0 | 4/5 | 1 | 41 |

z_{j}-c_{j} |
-19/5 | -13/5 | 0 | 0 | -4/5 | 0 |

Here, Phase 1 terminates because both the artificial variables have been removed from the basis.

Table 3

c_{j} |
12 | 15 | 9 | 0 | 0 | ||
---|---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1} |
x_{2} |
x_{3} |
x_{4} |
x_{5} |
Solution values b (= X _{B}) |

0 | x_{4} |
0 | 80/19 | 0 | 1 | 10/19 | 2270/19 |

9 | x_{3} |
0 | 10/19 | 1 | 0 | -7/38 | 70/19 |

12 | x_{1} |
1 | 13/19 | 0 | 0 | 4/19 | 205/19 |

z_{j}-c_{j} |
0 | -39/19 | 0 | 0 | 33/38 |

Table 4

c_{j} |
12 | 15 | 9 | 0 | 0 | ||
---|---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1} |
x_{2} |
x_{3} |
x_{4} |
x_{5} |
Solution values b (= X _{B}) |

0 | x_{4} |
0 | 0 | -8 | 1 | 2 | 90 |

15 | x_{2} |
0 | 1 | 19/10 | 0 | -7/20 | 7 |

12 | x_{1} |
1 | 0 | -13/10 | 0 | 9/20 | 6 |

z_{j}-c_{j} |
0 | 0 | 39/10 | 0 | 3/20 |

The optimal solution is:

x_{1} = 6, x_{2} = 7, x_{3} = 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.