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.
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.
Simplex Method Example-1, Example-2
"Minds are like parachutes; they work best when open." -Lord Thomas Dewar
Simplex Method: Example 1
Maximize z = 3x 1 + 2x 2
-x 1 + 2x 2 ≤ 4 3x 1 + 2x 2 ≤ 14 x 1 – x 2 ≤ 3
x 1 , x 2 ≥ 0
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
On small screens, scroll horizontally to view full calculation
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:
Calculating values for table 2
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
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
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
Use horizontal scrollbar to view full calculation
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
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
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
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
Don't convert the fractions into decimals, because many fractions cancel out during the process while the conversion into decimals will cause unnecessary complications.
Simplex Method: Final Optimal Table
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.
Real life complex applications usually involve hundreds of constraints and thousands of variables. So virtually these problems can not be solved manually. For solving such problems, you will have to rely on employing an electronic computer.
Share This Article
Operations Research Simplified Back Next
Goal programming Linear programming Transportation Problem Assignment Problem
IMAGES
VIDEO