Simplex Method Examples
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.
Maximize z = 3x1 + 2x2
subject to
-x1 + 2x2 ≤ 4
3x1 + 2x2 ≤ 14
x1 – x2 ≤ 3
x1, x2 ≥ 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
-x1 + 2x2 + x3 = 4
3x1 + 2x2 + x4 = 14
x1 – x2 + x5 = 3
x1, x2, x3, x4, x5 ≥ 0
Where x3, x4 and x5 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 = 3x1 + 2x2 + 0x3 + 0x4 + 0x5
Initial basic feasible solution
Now we assume that nothing can be produced. Therefore, the values of the decision variables are zero.
x1 = 0, x2 = 0, z = 0
When we are not producing anything, obviously we are left with unused capacity
x3 = 4, x4 = 14, x5 = 3
We note that the current solution has three variables (slack variables x3, x4 and x5) with non-zero solution values and two variables (decision variables x1 and x2) 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
a11 = -1, a12 = 2, a13 = 1, a14 = 0, a15 = 0, b1 = 4
a21 = 3, a22 = 2, a23 = 0, a24 = 1, a25 = 0, b2 = 14
a31= 1, a32 = -1, a33 = 0, a34 = 0, a35 = 1, b3 = 3
Calculating values for the index row (zj – cj)
z1 – c1 = (0 X (-1) + 0 X 3 + 0 X 1) - 3 = -3
z2 – c2 = (0 X 2 + 0 X 2 + 0 X (-1)) - 2 = -2
z3 – c3 = (0 X 1 + 0 X 0 + 0 X 0) - 0 = 0
z4 – c4 = (0 X 0 + 0 X 1 + 0 X 0) - 0 = 0
z5 – c5 = (0 X 0 + 0 X 0 + 0 X 1) – 0 = 0
Choose the smallest negative value from zj – cj (i.e., – 3). So column under x1 is the key column.
Now find out the minimum positive value
Minimum (14/3, 3/1) = 3
So row x5 is the key row.
Here, the pivot (key) element = 1 (the value at the point of intersection).
Therefore, x5 departs and x1 enters.
We obtain the elements of the next table using the following rules:
1. If the values of zj – cj 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 zj – cj 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
x3 row
a11 = -1 – 1 X ((-1)/1) = 0
a12 = 2 – (-1) X ((-1)/1) = 1
a13 = 1 – 0 X ((-1)/1) = 1
a14 = 0 – 0 X ((-1)/1) = 0
a15 = 0 – 1 X ((-1)/1) = 1
b1 = 4 – 3 X ((-1)/1) = 7
x4 row
a21 = 3 – 1 X (3/1) = 0
a22 = 2 – (-1) X (3/1) = 5
a23 = 0 – 0 X (3/1) = 0
a24 = 1 – 0 X (3/1) = 1
a25 = 0 – 1 X (3/1) = -3
b2 = 14 – 3 X (3/1) = 5
x1 row
a31 = 1/1 = 1
a32 = -1/1 = -1
a33 = 0/1 = 0
a34 = 0/1 = 0
a35 = 1/1 = 1
b3 = 3/1 = 3
Table 2
| cj | 3 | 2 | 0 | 0 | 0 |
|
cB | Basic variables | x1 | x2 | x3 | x4 | x5 | Solution values |
0 | x3 | 0 | 1 | 1 | 0 | 1 | 7 |
0 | x4 | 0 | 5 | 0 | 1 | -3 | 5 |
3 | x1 | 1 | -1 | 0 | 0 | 1 | 3 |
zj-cj |
| 0 | -5 | 0 | 0 | 3 |
|
Calculating values for the index row (zj – cj)
z1 – c1 = (0 X 0 + 0 X 0 + 3 X 1) - 3 = 0
z2 – c2 = (0 X 1 + 0 X 5 + 3 X (-1)) – 2 = -5
z3 – c3 = (0 X 1 + 0 X 0 + 3 X 0) - 0 = 0
z4 – c4 = (0 X 0 + 0 X 1 + 3 X 0) - 0 = 0
z5 – c5 = (0 X 1 + 0 X (-3) + 3 X 1) – 0 = 3
Key column = x2 column
Minimum (7/1, 5/5) = 1
Key row = x4 row
Pivot element = 5
x4 departs and x2 enters.
Calculating values for table 3
x3 row
a11 = 0 – 0 X (1/5) = 0
a12 = 1 – 5 X (1/5) = 0
a13 = 1 – 0 X (1/5) = 1
a14 = 0 – 1 X (1/5) = -1/5
a15 = 1 – (-3) X (1/5) = 8/5
b1 = 7 – 5 X (1/5) = 6
x2 row
a21 = 0/5 = 0
a22 = 5/5 = 1
a23 = 0/5 = 0
a24 = 1/5
a25 = -3/5
b2 = 5/5 = 1
x1 row
a31 = 1 – 0 X (-1/5) = 1
a32 = -1 – 5 X (-1/5) = 0
a33 = 0 – 0 X (-1/5) = 0
a34 = 0 – 1 X (-1/5) = 1/5
a35 = 1 – (-3) X (-1/5) = 2/5
b3 = 3 – 5 X (-1/5) = 4