A Simplex Iteration

John E. Mitchell

Consider the linear programming problem

We have

Columns 1 and 3 of A are linearly independent, so we initialize with B equal to these two columns:

and then

The corresponding basic solution is obtained by calculating B-1b:

Thus, we have a basic feasible solution x1 = [3, 0, 2, 0]T . The objective function value is

We next express the LP in the form

This requires the following calculations:

and

(This vector is the vector of reduced costs.) Thus we can express our original linear programming problem equivalently as

(Notice the order of the variables.) Since the cost of x4 is negative in this formulation and x4 is currently zero, we can try to improve the solution by increasing x4. The first constraint tells us that we have (with x2 = 0)

so we can’t make x4 any bigger than 3 without violating the nonnegativity restriction on x1. Similarly, the second constraint tells us that we have

so we can’t make x4 any bigger than 1 without violating the nonnegativity restriction on x3. (This examination to find the largest possible increase in the variable entering the basis is known as the minimum ratio test.) Thus, we set x4 to 1 and remove x3 from the basis, giving a new basis of x1 and x4. (This is a pivot from one basic feasible solution to another.)

We can now repeat the whole process over again from the new basic feasible solution. The matrix B now consists of columns 1 and 4 of A:

We have

The corresponding basic solution is obtained by calculating B-1b:

Thus, we have the basic feasible solution x2 = [2, 0, 0, 1]T . The objective function value is

which is indeed an improvement on the previous objective function value of 34. We next express the LP in the form

This requires the following calculations:

and

Thus, we have another equivalent formulation of our original linear programming problem:

Since the reduced costs are all nonnegative, this solution is actually optimal.

Note: Let z be the objective function, so -z + 8x1 + 4x2 + 5x3 + 6x4 = 0. Then the pivot we performed can be calculated exactly like a pivot in Gaussian elimination, by pivoting on x4 in the second constraint of the formulation:

becomes

after reordering the columns.

Note: In a practical implementation, only quantities that are actually needed are calculated, and the quantities are calculated more efficiently. For example, the inverse matrix B-1 is never calculated explicitly.