Skip to content

Operations Management and Strategic Management · Optimum Allocation of Resources - LPP

Simplex Method for LPP: Step-by-Step Solution

Updated 10 October 2026 · Fact-checked

The simplex method solves a linear programming problem by moving from one corner point of the feasible region to a better one. You convert constraints to equations using slack, surplus and artificial variables, build a tableau, and repeat pivots until no Cj − Zj value shows further improvement.

Understand Simplex Method

The graphical method works only for two variables. The simplex method handles any number of variables. It starts at a basic feasible solution, which is a corner point of the feasible region. It then moves to an adjacent corner that improves the objective, and stops when no move helps.

To start, every constraint must become an equation with non-negative right-hand side. A slack variable is added to a ≤ constraint. It stands for unused capacity and has zero cost in the objective. A surplus variable is subtracted from a ≥ constraint. It stands for the excess over the minimum requirement and also has zero cost. An artificial variable is added to a ≥ or = constraint only to give a starting basis. It has no real meaning and must leave the solution.

In the Big M method, each artificial variable gets a very large penalty M in the objective. M is a large positive number. It is subtracted in a maximisation problem and added in a minimisation problem. The penalty forces artificial variables out of the basis. If one stays in the final basis at a positive value, the problem is infeasible.

Each iteration of the tableau picks an entering variable, which is the one that improves Z most. It then picks a leaving variable using the minimum ratio test. A pivot operation makes the entering column a unit column. You stop when the Cj − Zj row shows no improvement.

Key rules to remember

Slack variable (≤ constraint)
a1x1 + a2x2 ≤ b becomes a1x1 + a2x2 + s = b, s ≥ 0
Slack has coefficient 0 in Z and can start in the basis.
Surplus and artificial (≥ constraint)
a1x1 + a2x2 ≥ b becomes a1x1 + a2x2 − s + A = b, s, A ≥ 0
Surplus alone has a coefficient of −1, so it cannot start in the basis. Add A.
Equality constraint
a1x1 + a2x2 = b becomes a1x1 + a2x2 + A = b
Only an artificial variable is added.
Big M objective
Max Z = Σ cjxj − M·A (Min Z = Σ cjxj + M·A)
M is larger than any other number in the problem.
Net evaluation row
Cj − Zj, where Zj = Σ (CB × column entry)
Maximisation: optimal when all Cj − Zj ≤ 0. Minimisation: optimal when all Cj − Zj ≥ 0.
Entering variable
Largest positive Cj − Zj (max) or most negative Cj − Zj (min)
This fixes the key column.
Minimum ratio test
θ = solution value ÷ key column entry, for entries > 0
The smallest θ gives the leaving variable and the key row.
Pivot operations
New key row = old key row ÷ pivot element; other row = old row − (its key column entry × new key row)
Do this for every row, including the solution column.

How to solve Simplex Method questions

Use this method for any simplex question. Convert a minimisation problem to maximisation only if you want one rule, or keep it and reverse the optimality test.

  1. 1Make every right-hand side non-negative. If a constraint has a negative RHS, multiply it by −1 and reverse the inequality.
  2. 2Add a slack variable for each ≤ constraint, subtract a surplus and add an artificial variable for each ≥ constraint, and add an artificial variable for each = constraint.
  3. 3Write the objective with zero cost for slack and surplus variables. Give artificial variables −M (maximise) or +M (minimise).
  4. 4Build the initial tableau with the slack and artificial variables as the basis. Fill Cj, CB, Zj and the Cj − Zj row.
  5. 5Check optimality using the Cj − Zj row. If it is not optimal, choose the entering variable (key column).
  6. 6Apply the minimum ratio test on positive entries to find the leaving variable (key row). If no entry is positive, the problem is unbounded.
  7. 7Pivot to get the new tableau. Recompute Zj and Cj − Zj. Repeat steps 5 to 7 until optimal.
  8. 8Read the answer: basic variables take the solution column values and non-basic variables are zero. Compute Z, and state that no artificial variable remains in the basis.

Quickest way: Fast tableau routine under time pressure

When to use it: Use it for ≤ constraints with 2 to 3 variables, where no artificial variable is needed.

  1. Write the tableau neatly once, with a ruled row for Cj − Zj. For all-slack starts, Zj = 0 so Cj − Zj = Cj.
  2. Circle the pivot element before doing arithmetic.
  3. Find the new key row first. Then update each other row using: old entry − (key column entry × new key row entry).
  4. Since the starting basis has CB = 0, compute Cj − Zj for each column as Cj − Σ(CB × column).
  5. After the last tableau, check Z = Σ(CB × solution). Substitute the values in the original constraints to catch arithmetic slips.

Common mistakes in Simplex Method

  • Adding a slack variable to a ≥ constraint

    Students remember 'add slack' without checking the inequality direction.

    Fix: ≤ takes +s. ≥ takes −s and +A. = takes +A only.

  • Choosing the leaving variable using a zero or negative key column entry

    Students divide every row without checking signs.

    Fix: Take the ratio only for strictly positive entries in the key column. Pick the smallest.

  • Stopping at the wrong optimality condition

    The rule differs for maximisation and minimisation.

    Fix: Maximisation stops when all Cj − Zj ≤ 0. Minimisation stops when all Cj − Zj ≥ 0 (with Cj as given in the Min form).

  • Not updating the solution column in the pivot

    Students update only the coefficients.

    Fix: Treat the solution column like any other column. Divide the key row and subtract from the others.

  • Ignoring an artificial variable that stays in the final basis

    Students read off Z without checking the basis.

    Fix: If an artificial variable remains in the basis at a positive value, state that the problem has no feasible solution.

  • Forgetting M in Zj for the artificial row

    M terms look awkward, so students drop them.

    Fix: Keep M symbolically. Compare Cj − Zj entries by looking at the coefficient of M first, then the constant.

Worked examples

Example 1

Maximise Z = 5x1 + 4x2 subject to 6x1 + 4x2 ≤ 24 and x1 + 2x2 ≤ 6, with x1, x2 ≥ 0. Solve by the simplex method.

Show the solution
  1. Standard form: 6x1 + 4x2 + s1 = 24; x1 + 2x2 + s2 = 6. Z has zero coefficients for s1 and s2.
  2. Initial basis: s1 = 24, s2 = 6. Cj − Zj for x1, x2 is 5 and 4. The largest is 5, so x1 enters.
  3. Ratios: 24 ÷ 6 = 4 and 6 ÷ 1 = 6. The minimum is 4, so s1 leaves. The pivot is 6.
  4. Iteration 1: x1 row = (1, 2/3, 1/6, 0 | 4). s2 row = (0, 4/3, −1/6, 1 | 2). Z = 5 × 4 = 20.
  5. Cj − Zj: x2 = 4 − 5(2/3) = 2/3; s1 = 0 − 5(1/6) = −5/6. The x2 column is positive, so x2 enters.
  6. Ratios: 4 ÷ (2/3) = 6 and 2 ÷ (4/3) = 1.5. The minimum is 1.5, so s2 leaves. The pivot is 4/3.
  7. Iteration 2: x2 row = (0, 1, −1/8, 3/4 | 3/2). x1 row = (1, 0, 1/4, −1/2 | 3).
  8. Cj − Zj: s1 = 0 − (5 × 1/4 + 4 × (−1/8)) = −3/4; s2 = 0 − (5 × (−1/2) + 4 × 3/4) = −1/2. All are ≤ 0, so the solution is optimal.
  9. Z = 5 × 3 + 4 × 1.5 = 15 + 6 = 21. Check: 6(3) + 4(1.5) = 24 and 3 + 2(1.5) = 6, so both constraints are tight.

Answer: x1 = 3, x2 = 3/2 (1.5), maximum Z = 21.

Example 2

Minimise Z = 2x1 + 3x2 subject to x1 + x2 ≥ 4 and x1 ≤ 3, with x1, x2 ≥ 0. Solve by the Big M method.

Show the solution
  1. Standard form: x1 + x2 − s1 + A1 = 4; x1 + s2 = 3. Objective: Min Z = 2x1 + 3x2 + 0s1 + M·A1 + 0s2.
  2. To use the maximisation rule, write Max Z′ = −2x1 − 3x2 − M·A1, where Z′ = −Z.
  3. Initial basis: A1 = 4, s2 = 3. Zj: x1 = −M, x2 = −M, s1 = +M. Cj − Zj: x1 = M − 2, x2 = M − 3, s1 = −M. The largest is M − 2, so x1 enters.
  4. Ratios: 4 ÷ 1 = 4 and 3 ÷ 1 = 3. The minimum is 3, so s2 leaves.
  5. Iteration 1: x1 row = (1, 0, 0, 0, 1 | 3). A1 row = (0, 1, −1, 1, −1 | 1).
  6. Cj − Zj: x2 = −3 + M, which is positive; s1 = −M; s2 = 2 − M. So x2 enters.
  7. Ratio: only the A1 row has a positive entry, 1 ÷ 1 = 1. A1 leaves. The pivot is 1.
  8. Iteration 2: x2 row = (0, 1, −1, 1, −1 | 1). x1 row = (1, 0, 0, 0, 1 | 3).
  9. Cj − Zj: s1 = 0 − (−3)(−1) = −3; s2 = 0 − [(−2)(1) + (−3)(−1)] = −1; A1 = −M + 3. M is very large, so −M + 3 < 0. All are ≤ 0, so it is optimal, and A1 is out of the basis.
  10. Max Z′ = −2(3) − 3(1) = −9, so Min Z = 9. Check: x1 + x2 = 4 and x1 = 3, so both constraints are tight.

Answer: x1 = 3, x2 = 1, minimum Z = 9.

Exam tips

  • Show every tableau with Cj, CB, basis, solution and Cj − Zj rows. Step marks are given for each correct iteration.
  • State the standard form first. Name each slack, surplus and artificial variable and why it was added.
  • Write the entering variable, leaving variable and pivot element under each tableau. This earns marks even if arithmetic slips later.
  • In MCQs, look at the constraint signs. They tell you which variables are needed, and a ≥ or = constraint always means an artificial variable.
  • Finish with a clear statement of the optimal values and Z. Mention if an artificial variable remains, since that signals infeasibility.

Practice questions from Optimum Allocation of Resources - LPP

Simplex Method: frequently asked questions

What is the difference between slack, surplus and artificial variables?

A slack variable is added to a ≤ constraint and represents unused resource. A surplus variable is subtracted from a ≥ constraint and represents excess over the requirement. An artificial variable is added to ≥ or = constraints only to start the method, and it must leave the basis.

When do I need the Big M method?

You need it when a constraint is ≥ or =, because no slack variable can give a starting basic feasible solution. You add an artificial variable with a penalty M in the objective, which forces it out as the iterations proceed.

How do I know the simplex solution is optimal?

Look at the Cj − Zj row. In a maximisation problem, all values must be zero or negative. In a minimisation problem, all values must be zero or positive.

What does it mean if no ratio can be found?

If the entering column has no positive entry, the minimum ratio test fails. This shows that the objective can be improved without limit, so the problem is unbounded.