Strategic Cost Management · Linear Programming

Simplex Method for Solving LPP Step by Step

Updated 11 October 2026 · Fact-checked

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

Understand Simplex Method

The graphical method works only for two decision variables. The simplex method works for any number. It is an algebraic way of visiting corner points of the feasible region, always moving to a corner that does not worsen the objective, and stopping when no neighbouring corner is better.

To start, every constraint must become an equation. A slack variable is added to a ≤ constraint. It stands for unused resource, such as idle machine hours. A surplus variable is subtracted from a ≥ constraint. It stands for the amount above the minimum requirement. Both have zero cost in the objective function.

A ≥ or = constraint gives no ready starting variable, because a surplus variable has a coefficient of −1. So you add an artificial variable. It is only a device to get a starting solution and has no real meaning. In the Big M method it carries a very large penalty M: −M in a maximisation, +M in a minimisation. This forces it out of the solution. If an artificial variable stays in the final solution at a positive value, the problem has no feasible solution.

The simplex table lists the basic variables, their Cj values, the coefficient columns, and the right-hand side (the solution values). Below it are the Zj and Cj − Zj rows. In each iteration one non-basic variable enters (the key column) and one basic variable leaves (the key row, found by the minimum ratio test). The row operations then produce a new table. You stop when the Cj − Zj row shows no further improvement.

Simplex and Big M are not rivals. Big M is the simplex method with artificial variables added and penalised. Plain simplex with only slack variables is enough when every constraint is ≤ with a non-negative right-hand side.

Key rules to remember

Slack variable (≤ constraint): a1x1 + a2x2 ≤ b becomes a1x1 + a2x2 + S = b, S ≥ 0; S has coefficient 0 in the objective. It can serve as a starting basic variable.
Surplus and artificial variables (≥ constraint): a1x1 + a2x2 ≥ b becomes a1x1 + a2x2 − S + A = b, S, A ≥ 0; S is surplus and A is artificial. The artificial variable is the starting basic variable. An = constraint gets only A.
Big M objective coefficients: Maximisation: −M for each A. Minimisation: +M for each A.; M is a very large positive number. Slack and surplus variables carry 0.
Zj and Cj − Zj rows: Zj = Σ (Cb × column coefficient); Cj − Zj = Cj − Zj; Cb is the objective coefficient of each basic variable. The value of Z is Σ (Cb × solution value).
Entering variable rule: Maximisation: largest positive Cj − Zj. Minimisation: most negative Cj − Zj.; This column is the key column.
Minimum ratio (leaving variable): Ratio = solution value ÷ key column coefficient, only where the coefficient > 0; The smallest ratio gives the key row. The element where key row and key column meet is the pivot.
Optimality condition: Maximisation: all Cj − Zj ≤ 0. Minimisation: all Cj − Zj ≥ 0.; Stop when this holds. Check that no artificial variable remains in the basis at a positive value.
Row operations: New key row = old key row ÷ pivot; other row = old row − (its key column element × new key row); After this, the key column becomes a unit column.

How to solve Simplex Method questions

This method works for maximisation and minimisation, with or without ≥ and = constraints. Write every step in the answer.

1Make every right-hand side non-negative. Multiply a constraint by −1 if needed, and reverse its inequality sign.
2Add a slack variable to each ≤ constraint, subtract a surplus and add an artificial variable for each ≥ constraint, and add an artificial variable for each = constraint.
3Rewrite the objective function with all variables. Slack and surplus carry 0. Artificial variables carry −M (maximise) or +M (minimise).
4Write the initial table using the slack or artificial variables as the starting basis. Compute Zj and Cj − Zj.
5Pick the entering variable from Cj − Zj. Divide the solution column by the positive key-column entries and pick the smallest ratio. That row's variable leaves.
6Divide the key row by the pivot, then update every other row. Recompute Zj, Cj − Zj and Z.
7Repeat until the optimality condition is met. Read the values of the basic variables from the solution column. Non-basic variables are zero.
8State the answer in business terms: product quantities, the optimal profit or cost, and any unused resource (slack) or excess (surplus).

Quickest way: Shortcut for a ≤ constraint maximisation

When to use it: Use when all constraints are ≤ and the question asks for the optimal mix and profit, with two or three variables.

Draw the table with only Cj − Zj. At the start it equals Cj, since every slack variable has Cb = 0.
Pick the largest Cj − Zj as the entering variable. Do the ratio test quickly in the margin.
Do the row operations with fractions, not decimals, to avoid rounding errors.
After each table, check the Z value. In a maximisation it should never fall.
When all Cj − Zj ≤ 0, read the answer. The Cj − Zj entries under the slack columns, with the sign reversed, are the shadow prices.
If the problem has two variables, check your answer against a quick corner-point calculation.

Common mistakes in Simplex Method

Adding a slack variable to a ≥ constraint.
Students apply the ≤ rule to every constraint.
Fix: For ≥, subtract a surplus variable and add an artificial variable. A slack variable belongs only to ≤.
Dividing by zero or negative key-column entries in the ratio test.
Students compute a ratio for every row without checking the sign.
Fix: Take ratios only where the key-column coefficient is positive. Ignore zero and negative entries.
Choosing the entering variable by the wrong sign in a minimisation.
The rule for maximisation (largest positive) is memorised and applied to every problem.
Fix: In minimisation with Cj − Zj, choose the most negative value and stop when all are ≥ 0. Write the rule at the top of your table.
Giving the final answer with an artificial variable still in the basis.
Students stop when the Cj − Zj row looks right.
Fix: Check the basis. A positive artificial variable at the optimum means the problem is infeasible.
Errors in updating rows after the pivot.
The key row is not divided by the pivot first, or the wrong multiplier is used.
Fix: First divide the key row by the pivot. Then, for each other row, subtract (its key-column entry × new key row). Check that the key column becomes a unit column.
Forgetting to apply the Big M coefficient of the artificial variable in Zj.
Students treat M as a small number or drop it.
Fix: Keep M symbolic. Compare coefficients of M first, then the constant terms.

Worked examples

Example 1

Pragati Auto Components makes two parts, A and B. Contribution is ₹40 per unit of A and ₹30 per unit of B. Machine time is limited to 40 hours: A needs 2 hours and B needs 1 hour. Labour is limited to 30 hours: each unit needs 1 hour. Find the product mix that maximises contribution using the simplex method.

Show the solution

Let x1 = units of A and x2 = units of B. Maximise Z = 40x1 + 30x2 subject to 2x1 + x2 ≤ 40, x1 + x2 ≤ 30, x1, x2 ≥ 0.
Add slack variables S1 and S2: 2x1 + x2 + S1 = 40 and x1 + x2 + S2 = 30. Initial basis: S1, S2. Z = 0.
Table 1: Cj − Zj is 40 for x1, 30 for x2, 0 for S1 and S2. Largest is 40, so x1 enters. Ratios: 40 ÷ 2 = 20 and 30 ÷ 1 = 30. Smallest is 20, so S1 leaves. Pivot = 2.
Table 2: x1 row = (1, 0.5, 0.5, 0 | 20). S2 row = old row − 1 × new x1 row = (0, 0.5, −0.5, 1 | 10). Z = 40 × 20 = 800.
Cj − Zj in Table 2: for x2 = 30 − 40 × 0.5 = 10. For S1 = 0 − 40 × 0.5 = −20. So x2 enters. Ratios: 20 ÷ 0.5 = 40 and 10 ÷ 0.5 = 20. S2 leaves. Pivot = 0.5.
Table 3: x2 row = (0, 1, −1, 2 | 20). x1 row = old x1 row − 0.5 × new x2 row = (1, 0, 1, −1 | 10).
Cj − Zj in Table 3: S1 = 0 − (40 × 1 + 30 × (−1)) = −10. S2 = 0 − (40 × (−1) + 30 × 2) = −20. Both are ≤ 0, so the solution is optimal.
Z = 40 × 10 + 30 × 20 = 400 + 600 = 1,000. Both S1 and S2 are non-basic, so both resources are fully used. The shadow prices are ₹10 per machine hour and ₹20 per labour hour.

Answer: Produce 10 units of A and 20 units of B. Maximum contribution = ₹1,000. Machine and labour hours are fully used. An extra machine hour is worth ₹10 and an extra labour hour ₹20.

Example 2

Minimise Z = 2x1 + 3x2 (cost in ₹ hundreds) subject to x1 + x2 ≥ 4, x1 + 3x2 ≥ 6, x1, x2 ≥ 0. Solve using the Big M method.

Show the solution

Subtract surplus variables S1, S2 and add artificial variables A1, A2: x1 + x2 − S1 + A1 = 4 and x1 + 3x2 − S2 + A2 = 6. Objective: Min Z = 2x1 + 3x2 + 0S1 + 0S2 + MA1 + MA2. Initial basis: A1, A2.
Table 1: Cj − Zj for x1 = 2 − 2M, for x2 = 3 − 4M, for S1 = M, for S2 = M. Most negative is for x2 (since 4M > 2M), so x2 enters. Ratios: 4 ÷ 1 = 4 and 6 ÷ 3 = 2. Smallest is 2, so A2 leaves. Pivot = 3.
Table 2: x2 row = (1/3, 1, 0, −1/3 | 2). A1 row = old A1 row − 1 × x2 row = (2/3, 0, −1, 1/3 | 2). A2 is dropped as it has left.
Cj − Zj in Table 2: for x1 = 2 − (M × 2/3 + 3 × 1/3) = 1 − 2M/3. For S2 = 0 − (M/3 − 1) = 1 − M/3. For S1 = M. Most negative is for x1, so x1 enters. Ratios: 2 ÷ (2/3) = 3 and 2 ÷ (1/3) = 6. A1 leaves. Pivot = 2/3.
Table 3: x1 row = (1, 0, −3/2, 1/2 | 3). x2 row = old x2 row − (1/3) × new x1 row = (0, 1, 1/2, −1/2 | 1).
Cj − Zj in Table 3: for S1 = 0 − (2 × (−3/2) + 3 × 1/2) = 3/2. For S2 = 0 − (2 × 1/2 + 3 × (−1/2)) = 1/2. Both are ≥ 0, so the solution is optimal. No artificial variable remains in the basis.
Z = 2 × 3 + 3 × 1 = 9. Both surplus variables are zero, so both minimum requirements are met exactly.

Answer: x1 = 3, x2 = 1. Minimum cost Z = 9 (₹900). Both constraints are binding, with no surplus.

Exam tips

For MCQs, expect questions on which variable is added to which constraint type, the sign of M in the objective, and the entering variable rule. Memorise the table of ≤, ≥ and =.
In written answers, show the initial table and at least the key steps. Marks go for the method as well as the final answer.
Always test the optimum against the graph or by substituting into the constraints when time allows. It catches arithmetic slips.
End the answer with a recommendation in business terms: units to make, resource that is binding, and the value of one more unit of a scarce resource.
If the question gives a partly completed table, find the key column, key row and pivot first. Then complete only the next iteration.

Practice questions from Linear Programming

Simplex Method: frequently asked questions

What is the difference between the simplex method and the Big M method?

The Big M method is a form of the simplex method used when constraints are ≥ or =. It adds artificial variables with a very large penalty M so that they leave the solution. Plain simplex with slack variables only is enough when all constraints are ≤.

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

A slack variable is added to a ≤ constraint and shows unused resource. A surplus variable is subtracted from a ≥ constraint and shows the excess over the requirement. An artificial variable is added to ≥ and = constraints only to start the method, and has no real meaning.

How do I know the simplex solution is optimal?

In a maximisation, all Cj − Zj values must be zero or negative. In a minimisation, all must be zero or positive. You must also check that no artificial variable remains in the basis at a positive value.

Which variable leaves the basis in each iteration?

Divide each solution value by the matching positive entry in the key column. The row with the smallest ratio is the key row, and its basic variable leaves.