A Simplex Iteration

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^{-1}b:

Thus, we have a basic feasible solution x^{1} = [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 x_{4} is negative in this formulation and x_{4} is
currently zero, we can try to improve the solution by increasing x_{4}. The first constraint tells us
that we have (with x_{2} = 0)

so we can’t make x_{4} any bigger than 3 without violating the nonnegativity restriction on x_{1}.
Similarly, the second constraint tells us that we have

so we can’t make x_{4} any bigger than 1 without violating the nonnegativity restriction on x_{3}. (This
examination to find the largest possible increase in the variable entering the basis is
known as the minimum ratio test.) Thus, we set x_{4} to 1 and remove x_{3} from the basis,
giving a new basis of x_{1} and x_{4}. (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^{-1}b:

Thus, we have the basic feasible solution x^{2} = [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 + 8x_{1} + 4x_{2} + 5x_{3} + 6x_{4} = 0. Then the pivot we
performed can be calculated exactly like a pivot in Gaussian elimination, by pivoting on x_{4} 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.