The simplex method is a general procedure for solving linear programming problems. This method is remarkably efficient, and it is capable of solving very large problems, involving several hundred or even several thousand variables and constraints, using computers. While a computer code is always used to solve linear programs, it is important to learn how the method works.
We will use a modification of the chemical production problem as a vehicle for discussion. Because we can represent the problem in graphic form and because we already know the optimal solution, we can readily see what is happening at each stage of the algorithm. We will simplify the problem slightly by eliminating the demand constraints. Recall that for the stated problem, these constraints were not effective in dictating the optimal solution anyway. Eliminating them allows a simpler, more direct explanation of the procedure.
The problem is one of allocating time on machines A and B to the two products, chemical X and chemical Y, in such a way that contribution to profit and overhead would be maximized. The time requirements of the two machines for each product were given and the total available time on the two machines was limited. Therefore, the resulting modified linear optimization model is
Maximize Z = 60x + 50y
2x + 4y ≤ 80 (machine A)
3x + 2y ≤60 (machine B)
x ≥ 0 (minimum production for chemical X)
y ≥0 ( minimum production for chemical Y)
A Graph shows the constraints plotted on a graph and identifies the feasible solution space, abcd, and the previously determined optimal allocation of machine time at point c; that is x = 10 units and y=15 units. Recall also that the contribution for the optimal solution was $1350.
When we have plotted the linear objective function for two values of total Z=$900 and Z= $1200. It is now rather obvious for this simple problem that if we substitute larger and larger values of Z in the objective function, lines parallel to the $900 and $1200 lines would result and a line through point c would define the combination of x and y with the maximum possible contribution within the feasible solution space. Figure then, provides us with a clear picture of the problem and the relationship among the various solutions of the objective function.
First, we note the physical meaning of the constraints on the available time for machines A and B. For machine A, because chemical X requires 2 hours per unit and chemical Y requires 4 hours per unit and we are limited to a total of 80 hours, we write the inequality constraint:
2x + 4y ≤ 80 —————– (1)
For machine B, we write the inequality constraint:
3x + 2y ≤ 60 —————— (2)
These inequalities state that the use of machines A and B is less than or equal to 80 and 60 hours respectively; that is there could be idle machine time. To account for any slack available, we could convert Inequalities 1 and 2 into equations by defining slack variables to represent the possible idle time. Therefore,
2x + 4y + WA = 80 ———– (3)
3x + 2y + WB = 60 ———— (4)
Where WA is the idle time for machine A, and WB is the idle tome for machine B. We also require WA and WB to be nonnegative (WA, WB ≥0). The constraints plotted in a graph are then lines that indicate the full use of machine A when WA = 0 and of machine B when WB =0. Solutions that involve some idle time are permissible and would fall below one or both of the constraint lines, which would be within the solution apace abcd.
The effect of solutions involving slack (idle machine time) is easy to see through examples. Assume that the production schedule is 9 units of chemical X and 14 units of chemical Y. Because 2 hours per unit of chemical X and 4 hours per unit of chemical Y are required of machine A time and because machine A has a total of 80 hours available, we have from equation (3)
WA =80 – (2) (9) – (4) (14) = 80 – 74 = 6 hours
Thus, there are 74 productive hours, so the slack idle time for machine A is 6 hours.
Similarly, the idle time for machine B, from Equation (4) would be
WB = 60 – (3) (9) – (2) (14) = 60 – 55 = 5 hours
Now examine Figure and note the point x =9, y =14 falls inside the feasible solution space but not on any of the constraint lines. This type of solution is called non-basic solution.
With the slack variables now included in the formulation, the objective function is actually
Maximize Z = 60x + 50y + (0) WA + (0) WB
The zero coefficients for the slack variables are appropriate because they make no contribution to profit. The total contribution of the non-basic solution is
Z= (60) (9) + (50) (14) + (0) (6) = (0) (5)
= 540 + 700 + 0+ 0 = 1240
Let us return to Equation (3) and (4) with four unknown variables plus the objective function. Now, recall from simple algebra that we can solve equations simultaneously if they contain the same number of unknowns as there are equations. If we set any two of the four variables to zero, we can solve the two equations simultaneously to find the values of the other two variables. This is exactly what we will be doing in the following step by step procedure.