Simplex Method: Steps, Slack Variables and the Tableau
The simplex method solves LPs with many variables by moving between corner points. Learn slack variables, the pivot column and row rules, and the optimality test.
The simplex method solves linear programs with more than two variables by moving from one corner point of the feasible region to a better adjacent one until no improvement is possible. First write the problem in standard form: for a maximize problem with <= constraints, add one slack variable to each constraint to turn it into an equation, and rewrite the objective as Z - c1 x1 - c2 x2 = 0. The slack variables form the starting basic feasible solution, with all decision variables at zero.
Each iteration of the tableau has three steps. One, choose the pivot column: the column with the most negative coefficient in the objective row (the entering variable). If no negative coefficient remains, the current solution is optimal. Two, choose the pivot row with the minimum ratio test: divide each right-hand side by the positive entry in the pivot column and take the smallest ratio (the leaving variable). If no entry is positive the problem is unbounded. Three, pivot: divide the pivot row by the pivot element and use row operations to make all other entries in the pivot column zero.
Read the answer from the final tableau. Basic variables take the value in the right-hand side column and non-basic variables are zero. The top-right entry is the optimal value of Z. For minimize problems you can maximize the negative of the objective, or use the Big M or two-phase method when there are >= or = constraints, which need artificial variables. A tie in the minimum ratio gives a degenerate solution.
Key points
- Add slack variables to turn <= into equations.
- Entering variable: most negative objective-row entry.
- Leaving variable: minimum ratio (RHS / positive pivot-column entry).
- Stop when the objective row has no negative entries.
- Big M or two-phase handles >= and = constraints.
Worked example
Maximize Z = 3x + 2y with x + y <= 4 and x + 3y <= 6. Add slacks s1, s2. Initial rows: s1: x + y + s1 = 4; s2: x + 3y + s2 = 6; Z - 3x - 2y = 0. Entering variable x (most negative, -3). Ratios: 4/1 = 4 and 6/1 = 6, so s1 leaves. After pivoting, x = 4, s2 = 2, Z = 12 and the objective row becomes y: +1, s1: +3, all non-negative. The optimum is Z = 12 at x = 4, y = 0.
Common questions
What is a slack variable?
A non-negative variable added to a <= constraint to turn it into an equation; it measures the unused amount of the resource.
How do you know a simplex tableau is optimal?
For a maximize problem, when every entry in the objective row is zero or positive.
Related topics
- Linear Programming: Formulation and the Graphical Method
- Transportation Problem: Northwest Corner, Least Cost and Vogel
- Assignment Problem: The Hungarian Method Step by Step
- All topics: Operations Research
BASMAGLY is an independent student project, not an official Delta University site. Check lectures and your instructor for the final word.