The Simplex Algorithm

We have used simple problems to explain linear optimization models and the simplex solution technique. The power of linear programming, however, is in the solution of large scale problems and the key to their solution is the simplex algorithm. When the algorithm has been developed in a rigorous way, the computing effort can be further reduced by programming the algorithm for computers. Large scale problems of resource allocation can tem be formulated and solved at reasonable cost. Without the simplex algorithm and without computers, the solution of large scale problems would be impossible.

We will now present a more rigorous description of the simplex method. This description is based on an approach for solving several simultaneous linear equations.

In reducing the simplex algorithm to a set of rigorous rules, there is a risk that we may begin to think of it as a mechanical procedure and lose contact with what is being accomplished at each stage of solution. We will try to maintain contact with the meaning of each step by again using the chemical production problem as an example, and by relating our manipulations to the graphic solution shown,

The processing times for each unit of the two products on the mixing machine A and the packaging machine, B, are as follows:

Machine A Machine B
Product (hours/unit) (hours/unit)
Chemical X 2 3
Chemical Y 4 2

For the upcoming two week period, machine A has 80 hours of processing time available B has 60 hours available.

After the addition of the slack variables to account for idle time, our two restricting equations for machine A and B are

2x + 4y + WA = 80 —————-Eq (5)
3x + 2y + WB = 60 ————— Eq (6)

An initial solution to this set of equations is found by setting x = y = 0, which gives WA = 80 and WB = 60. This solution is easy to see, because WA has a coefficient of + 1 in Equation (5) but does not appear in Eq (6) and WB has a coefficient of +1 in Eq (6) but does appear in Eq (5).

The objective function for this problem cam be written as

Z = 60x + 50y + (0) WA + (0) WB ——–Eq (7)

Because idle time contributes nothing to profits or overhead Substituting the limited solution of WA = 80 and WB = 60 into Eq (7) gives

Z – 60x – 50y = (0)80 + (0)60 = 0 —————–Eq (8)

As the corresponding value of the objective function

We can combine Eq (8) with Eq (5) and (6) and write

Z – 60x – 50y= 0 (row 0)

2x + 4y + WA = 80 (row 1)

3 + 2y = WB = 60 (row 2)

Where, all the variables must always be positive. This is the set of initial equations that is associated with the initial solution x = y =0, WA = 80 and WB = 60.

Improving the Initial Solution:

To improve the initial solution, we use the test for optimality. Are there coefficients in the objective function that indicate that Z can be increased? If there are, we know that we substitute a variable in the solution that has a higher contribution rate to the objective function than one of the variables now in the solution. Variables with negative coefficients in row 0 will improve the objective function of they are brought into the solution.

Identifying the entering Variable and Key Column:

Any variable with a negative coefficient in row 0 will improve (increase) the objective function if its value is increased from 0. The following rule is useful in selecting the entering variable.

Rule 1: If there are variables with negative coefficients in row 0, choose the one with the most negative coefficient as the entering variable. If there are no variables with negative coefficients in row 0, the current solution is optimal.

In this example, we choose x as the entering variable according to Rule 1. This choice determines the “direction of change” in the solution.

The coefficients of the entering variable x, — 60 in row 0, 2 in row 1, and 3 in row 2, will play a key role in the computations of the simplex algorithm. Because these coefficients are arranged vertically as a column of numbers in rows 0, 1, and 2, we designate them as the key column.