Now I will show you an example of primal problem.

Minimize z = 3x_{1} + 3x_{2}

subject to

2x_{1} + 4x_{2} ≥
40

3x_{1} + 2x_{2} ≥ 50

** **

x_{1}, x_{2} ≥ 0

Solution.

We use the M method to solve this problem.

After adding surplus & artificial variables, we have

Minimize z = 3x_{1} + 3x_{2} + 0x_{3} + 0x_{4} + MA_{1} + MA_{2}

2x_{1} + 4x_{2} - x_{3} + A_{1} = 40

3x_{1} + 2x_{2} - x_{4} + A_{2 }= 50

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

Where:

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

x_{3} and x_{4} are surplus variables.

x_{1} = 0, x_{2} = 0, x_{3} = 0, x_{4} = 0

A_{1} = 40, A_{2} = 50

c_{j} |
3 | 3 | 0 | 0 | M | M | ||
---|---|---|---|---|---|---|---|---|

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

M | A_{1} |
2 | 4 | -1 | 0 | 1 | 0 | 40 |

M | A_{2} |
3 | 2 | 0 | -1 | 0 | 1 | 50 |

z_{j}-c_{j} |
5M - 3 | 6M - 3 | -M | -M | 0 | 0 |

Choose the highest positive value from index row.

As 6M > 5M, x_{2} becomes a basic variable in the
next iteration.

Minimum (40/4, 50/2) = (10, 25) = 10

Key Row = A_{1} row.

Pivot element = 4.

A_{1} departs and x_{2 }enters.

Table 2

c_{j} |
3 | 3 | 0 | 0 | M | ||
---|---|---|---|---|---|---|---|

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

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

M | A_{2} |
2 | 0 | 1/2 | -1 | 1 | 30 |

z_{j}-c_{j} |
2M - 3/2 | 0 | M/2 - 3/4 | -M | 0 |

Table 3

c_{j} |
3 | 3 | 0 | 0 | ||
---|---|---|---|---|---|---|

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

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

3 | x_{1} |
1 | 0 | 1/4 | -1/2 | 15 |

z_{j}-c_{j} |
0 | 0 | -3/8 | -3/4 |

The optimal solution is

x_{1 }= 15, x_{2} = 5/2

z = 3 X 15 + 3 X 5/2= 105/2.