Revised Simplex Method: Steps and Solved Example in Matrix Form

The revised simplex method is the matrix version of the simplex method. It visits exactly the same corner points as the ordinary tableau method, but instead of updating the whole tableau after every pivot, it keeps only the basis inverse B⁻¹ and computes the few numbers it needs from it. For large problems with many more variables than constraints, this saves a lot of work, which is why practical LP solvers are built on it.

This guide explains the notation, lists the steps, and solves a small example so you can see every matrix. If the tableau method is new to you, start with how to solve an LPP by the simplex method.

Notation

Write the problem in standard form as maximize Z = c·x subject to A x = b, x ≥ 0, where A includes the slack columns.

Symbol	Meaning
B	The basis matrix: the columns of A belonging to the current basic variables
B⁻¹	Its inverse
c_B	Objective coefficients of the basic variables
x_B = B⁻¹ b	Current values of the basic variables
y = c_B B⁻¹	Simplex multipliers (also the dual values or shadow prices)
c_j − y a_j	Reduced cost of a non-basic column a_j; the same number as Cj − Zj in a tableau

Revised Simplex Method Steps

1. Start with a basis whose inverse is known. With slack variables, B = I, so B⁻¹ = I.
2. Price out: compute y = c_B B⁻¹, then the reduced cost c_j − y a_j for every non-basic column.
3. Optimality test: for maximization, if every reduced cost is ≤ 0, stop. Otherwise the column with the largest positive reduced cost enters.
4. Entering column: compute d = B⁻¹ a_j.
5. Ratio test: divide x_B by the positive entries of d. The smallest ratio picks the leaving variable. If no entry of d is positive, the problem is unbounded.
6. Update the basis and its inverse, then return to step 2.

Only one column, d, and one row of numbers, y, are computed per iteration. Nothing else in the tableau is needed.

Solved Example

Maximize Z = 2x1 + 3x2 subject to x1 + x2 ≤ 4, x1 + 3x2 ≤ 6, x1, x2 ≥ 0.

With slack variables s1 and s2:

• Columns: a1 = (1, 1), a2 = (1, 3), s1 = (1, 0), s2 = (0, 1)
• b = (4, 6)
• c = (2, 3, 0, 0)

Iteration 1

• Basis: s1, s2. B = I, so B⁻¹ = I and x_B = b = (4, 6).
• c_B = (0, 0), so y = (0, 0).
• Reduced costs: x1 gives 2 − 0 = 2; x2 gives 3 − 0 = 3. x2 enters.
• d = B⁻¹ a2 = (1, 3).
• Ratios: 4 / 1 = 4 and 6 / 3 = 2. The second basic variable, s2, leaves.

Iteration 2

• Basis: s1, x2. B has columns (1, 0) and (1, 3).
• B⁻¹ = [[1, −1/3], [0, 1/3]] (rows written in brackets).
• x_B = B⁻¹ b = (4 − 2, 2) = (2, 2), so s1 = 2, x2 = 2 and Z = 3(2) = 6.
• c_B = (0, 3), so y = c_B B⁻¹ = (0, 1).
• Reduced costs: x1 gives 2 − (0·1 + 1·1) = 1; s2 gives 0 − 1 = −1. x1 enters.
• d = B⁻¹ a1 = (1 − 1/3, 1/3) = (2/3, 1/3).
• Ratios: 2 / (2/3) = 3 and 2 / (1/3) = 6. s1 leaves.

Iteration 3

• Basis: x1, x2. B has columns (1, 1) and (1, 3); its determinant is 2.
• B⁻¹ = [[3/2, −1/2], [−1/2, 1/2]].
• x_B = B⁻¹ b = (3/2·4 − 1/2·6, −1/2·4 + 1/2·6) = (3, 1).
• c_B = (2, 3), so y = (2·3/2 + 3·(−1/2), 2·(−1/2) + 3·1/2) = (3/2, 1/2).
• Reduced costs of the non-basic slacks: s1 gives 0 − 3/2 = −3/2; s2 gives 0 − 1/2 = −1/2.
• All reduced costs are negative, so the solution is optimal.

Answer

• x1 = 3, x2 = 1, maximum Z = 2(3) + 3(1) = 9
• The simplex multipliers y = (3/2, 1/2) are the shadow prices: one more unit of the first resource would raise Z by 3/2, one more unit of the second by 1/2.

Check: 3 + 1 = 4 ✓ and 3 + 3(1) = 6 ✓, so both constraints are binding.

The Same Problem as a Tableau

If you solve this problem with the ordinary tableau method, you get exactly the same sequence: x2 enters and s2 leaves, then x1 enters and s1 leaves, ending at x1 = 3, x2 = 1, Z = 9. The final tableau’s slack columns contain B⁻¹, and its Zj row under the slack columns contains y = (3/2, 1/2). The two methods are the same algorithm organized differently.

Revised vs Standard Simplex Method

	Standard (tableau) method	Revised simplex method
Stored each iteration	Whole tableau, m rows × all columns	B⁻¹ (m × m) plus original data
Work per iteration	Update every entry	Price out, one column, update B⁻¹
Best for	Hand calculation and teaching	Large, sparse problems on computers
Shadow prices	Read from the Zj row	Available directly as y
Path to optimum	Same corners	Same corners

When the number of variables n is much larger than the number of constraints m, the revised method touches far fewer numbers per iteration, because it never updates columns that do not enter the basis. Computer implementations also avoid forming B⁻¹ explicitly and use factorizations instead, but the logic is the one shown here.

Common Mistakes

• Multiplying in the wrong order. y is a row vector: y = c_B B⁻¹, not B⁻¹ c_B.
• Mixing up the order of basic variables. The order of columns in B must match the order of entries in c_B and x_B.
• Recomputing B⁻¹ from scratch with errors. For 2 × 2 matrices, use the formula: swap the diagonal entries, change the sign of the off-diagonal entries and divide by the determinant.

Check Your Answer

The revised simplex method calculator solves the problem in tableau form, which visits the same basic solutions shown above. Enter 2x1 + 3x2 with the two constraints to confirm x1 = 3, x2 = 1 and Z = 9, and to see where B⁻¹ appears in the slack columns of each tableau.