Get ready for a few **solved examples of simplex method in operations research**. In this section, we will take **linear programming (LP) maximization problems** only.

Do you know how to divide, multiply, add, and subtract? Yes. Then there is a good news for you. About 50% of this technique you already know.

Now, open the door and windows of your mind and concentrate on the following example.

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

subject to

-x_{1} + 2x_{2} ≤
4

3x_{1} + 2x_{2 } ≤ 14

x_{1} – x_{2} ≤
3

x_{1}, x_{2} ≥ 0

Solution.

First, convert every inequality constraints in the LPP into an equality constraint, so that the problem can be written in a standard from. This can be accomplished by adding a slack variable to each constraint. Slack variables are always added to the less than type constraints.

Converting inequalities to equalities

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

3x_{1} + 2x_{2} + x_{4} = 14

x_{1} – x_{2} + x_{5} = 3

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

Where x_{3}, x_{4} and x_{5} are slack variables.

Since slack variables represent unused resources, their contribution in the objective function is zero. Including these slack variables in the objective function, we get

Maximize z = 3x_{1} + 2x_{2} + 0x_{3} + 0x_{4} + 0x_{5}

Initial basic feasible solution

Now we assume that nothing can be produced. Therefore, the values of
the decision variables are zero.

x_{1} = 0, x_{2} = 0, z = 0

When we are not producing anything, obviously we are left with unused
capacity

x_{3} = 4, x_{4} = 14, x_{5} = 3

We note that the current solution has three variables (slack variables
x_{3}, x_{4} and x_{5}) with non-zero solution
values and two variables (decision variables x_{1} and x_{2})
with zero values. Variables with non-zero values
are called basic variables. Variables with zero values are called non-basic
variables.

Simplex Method: Table 1

a_{11} = -1, a_{12} = 2, a_{13} = 1, a_{14} = 0, a_{15} = 0, b_{1} = 4

a_{21} = 3, a_{22} = 2, a_{23} = 0, a_{24 }= 1, a_{25} = 0, b_{2} = 14

a_{31}= 1, a_{32} = -1, a_{33} = 0, a_{34} = 0, a_{35} = 1, b_{3 }= 3

Calculating
values for the index row (z_{j }– c_{j})

z_{1 }– c_{1} = (0 X (-1) + 0 X 3 + 0 X 1) - 3
= -3

z_{2 }– c_{2} = (0 X 2 + 0 X 2 + 0 X (-1)) - 2
= -2

z_{3 }– c_{3} = (0 X 1 + 0 X 0 + 0 X 0) - 0 = 0

z_{4 }– c_{4} = (0 X 0 + 0 X 1 + 0 X 0) - 0 = 0

z_{5 }– c_{5} = (0 X 0 + 0 X 0 + 0 X 1) –
0 = 0

Choose the smallest negative value from z_{j} – c_{j }(i.e., – 3). So column under x_{1} is the key column.

Now find out the minimum positive value

Minimum (14/3, 3/1) = 3

So row x_{5} is the key row.

Here, the pivot (key) element = 1 (the value at the point of intersection).

Therefore, x_{5} departs and x_{1 }enters.

We obtain the elements of the next table using the following rules:

1. If the values of z_{j }– c_{j} are positive,
the inclusion of any basic variable will not increase the value of
the objective function. Hence, the present solution maximizes the
objective function. If there are more than one negative values, we
choose the variable as a basic variable corresponding to which the
value of z_{j }– c_{j} is least (most negative)
as this will maximize the profit.

2. The numbers in the replacing row may be obtained by dividing the key row elements by the pivot element and the numbers in the other two rows may be calculated by using the formula:

New number= | old number- | (corresponding no. of key row) X (corresponding no. of key column) |

pivot element |

Calculating values for table 2

x_{3} row

a_{11} = -1 – 1 X ((-1)/1) = 0

a_{12} = 2 – (-1) X ((-1)/1) = 1

a_{13} = 1 – 0 X ((-1)/1) = 1

a_{14} = 0 – 0 X ((-1)/1) = 0

a_{15} = 0 – 1 X ((-1)/1) = 1

b_{1} = 4 – 3 X ((-1)/1) = 7

x_{4} row

a_{21} = 3 – 1 X (3/1) = 0

a_{22} = 2 – (-1) X (3/1) = 5

a_{23} = 0 – 0 X (3/1) = 0

a_{24} = 1 – 0 X (3/1) = 1

a_{25} = 0 – 1 X (3/1) = -3

b_{2} = 14 – 3 X (3/1) = 5

x_{1} row

a_{31} = 1/1 = 1

a_{32} = -1/1 = -1

a_{33} = 0/1 = 0

a_{34} = 0/1 = 0

a_{35} = 1/1 = 1

b_{3} = 3/1 = 3

Table 2

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

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

0 | x_{3} |
0 | 1 | 1 | 0 | 1 | 7 |

0 | x_{4} |
0 | 5 | 0 | 1 | -3 | 5 |

3 | x_{1} |
1 | -1 | 0 | 0 | 1 | 3 |

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

Calculating
values for the index row (z_{j }– c_{j})

z_{1 }– c_{1} = (0 X 0 + 0 X 0 + 3 X 1) - 3 =
0

z_{2 }– c_{2} = (0 X 1 + 0 X 5 + 3 X (-1)) –
2 = -5

z_{3 }– c_{3} = (0 X 1 + 0 X 0 + 3 X 0) - 0
= 0

z_{4 }– c_{4} = (0 X 0 + 0 X 1 + 3 X 0) - 0 = 0

z_{5 }– c_{5} = (0 X 1 + 0 X (-3) + 3 X 1) –
0 = 3

Key column = x_{2 }column

Minimum (7/1, 5/5) = 1

Key row = x_{4} row

Pivot element = 5

x_{4} departs and x_{2 }enters.

Calculating values for table 3

x_{3} row

a_{11} = 0 – 0 X (1/5) = 0

a_{12} = 1 – 5 X (1/5) = 0

a_{13 }= 1 – 0 X (1/5) = 1

a_{14} = 0 – 1 X (1/5) = -1/5

a_{15} = 1 – (-3) X (1/5) = 8/5

b_{1} = 7 – 5 X (1/5) = 6

x_{2} row

a_{21} = 0/5 = 0

a_{22} = 5/5 = 1

a_{23} = 0/5 = 0

a_{24} = 1/5

a_{25} = -3/5

b_{2} = 5/5 = 1

x_{1} row

a_{31} = 1 – 0 X (-1/5) = 1

a_{32} = -1 – 5 X (-1/5) = 0

a_{33} = 0 – 0 X (-1/5) = 0

a_{34} = 0 – 1 X (-1/5) = 1/5

a_{35} = 1 – (-3) X (-1/5) = 2/5

b_{3} = 3 – 5 X (-1/5) = 4

Simplex Method: Final Optimal Table

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

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

0 | x_{3} |
0 | 0 | 1 | -1/5 | 8/5 | 6 |

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

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

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

Since all the values of zj – c_{j} are positive, this is the optimal solution.

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

z = 3 X 4 + 2 X 1 = 14.

The largest profit of Rs.14 is obtained, when 1 unit of x_{2} and 4 units of x_{1} are produced. The above solution also indicates
that 6 units are still unutilized, as shown by the slack variable x_{3} in the X_{B} column.