Learning outcomes
- State the four assumptions of linear programming and recognise when each fails.
- Write an LP in general, canonical and standard form and convert between them.
- Convert inequalities to equations using slack, surplus and artificial variables.
- Handle unrestricted variables and ≥ constraints correctly.
- Formulate applied problems — transportation, goal programming, cyclic staffing — as LPs.
Start here
You have a fixed number of machine hours, a fixed payroll and a fixed amount of cash. Linear programming is the arithmetic of squeezing the most out of exactly what you have. It insists on two ordinary habits: doubling the work doubles the cost, and separate jobs simply add up. Those sound too obvious to name, but they are what let an algorithm search millions of plans in a fraction of a second.
The page does two things. First, writing a business situation down in that arithmetic correctly — almost every real modelling failure happens here, not in the algebra later. Second, rewriting it into one fixed shape, so that a single algorithm can solve every problem you will ever write. That second half is purely mechanical: six rules, learned once, applied in a fixed order.
Why does the shape matter at all? The solving method you meet next (the simplex method) works only on equations whose right-hand sides are non-negative, and it wants to start from a solution it can read straight off the page. Real problems arrive as a jumble of ≤, = and ≥ rows, negative numbers on the right, and variables that may go negative. The six rules are the translation service between the two.
1. What makes a programme linear
A linear objective function optimised subject to linear equality and inequality constraints, with the variables restricted to non-negative values in the standard treatment.
f(x₁, …, xₙ) = c₁x₁ + ⋯ + cₙxₙ — every variable to the first power, times a constant, with no products of variables and no transcendental functions.
The narrowness is the point, and it buys one enormous prize. Each linear constraint cuts space with a flat wall (in two variables a straight line, in three a plane, in n a hyperplane), and each ≤ or ≥ keeps everything on one side of that wall. Intersecting flat-sided pieces gives a flat-sided region with no dents in it — a convex polyhedron. A linear objective is a straight ruler laid across that region, so improving the objective always means walking in one fixed direction; you can keep walking until a wall stops you. The best value is therefore never strictly inside the region: it sits on the boundary, and in fact at a corner, a point where enough walls meet to pin it down.
That single fact turns an infinite search (every point of a continuous region) into a finite one (a list of corners) — the machinery of L03 and L04. Two honest exceptions: if the region is unbounded in the improving direction there is no best value at all, and if the ruler happens to lie parallel to a wall then a whole edge ties for best — but the two corners at its ends are among the winners, so searching corners still finds an optimum.
Learn the illegal expressions by sight, since they hide inside innocuous business language: whichever is larger
is a max, a share of the total
is a ratio, however far we miss the target
is an absolute value. Not linear: x₁x₂, x₁², √x₁, log x₁, max(x₁, x₂), |x₁|. Some of these can be repaired into linear form and some cannot; Problem 4 sorts them.
2. The four assumptions, and how each fails
| Assumption | Meaning | Fails when… |
|---|---|---|
| 1. Proportionality | each contribution is proportional to its variable | economies of scale, setup costs, quantity discounts |
| 2. Additivity | total contribution = sum of contributions | activities interact — a shared joint setup |
| 3. Divisibility | variables may be fractional | indivisible items (aircraft, people) ⟹ integer programming (L16–L18) |
| 4. Certainty | coefficients are known constants | random parameters ⟹ stochastic programming |
Proportionality fails most often through fixed setup costs. Any quantity of product A incurs a ₹5000 setup
is not linear: the cost is 0 at x = 0 and 5000 the instant x moves off zero, and no straight line through the origin can imitate that jump. The repair is to add a yes/no variable y ∈ {0, 1} — 1 if we produce at all, 0 if not — charge the ₹5000 as 5000y in the objective, and link y to x by choosing a constant M larger than any x the constraints allow.
Read the link both ways. If y = 0 the row says x ≤ 0, so nothing is produced. If y = 1 the row says x ≤ M, which is no restriction at all, and the objective has been charged the setup. Every row here is still linear — but y is forced to be a whole number, so the model has left LP and become a mixed-integer programme. Quantity discounts break proportionality more gently: the cost per unit falls as the order grows, so total cost bends instead of jumping, and no single cost coefficient describes it.
Additivity fails when activities interact: two products sharing one setup cost less together than apart, so the total is not the sum of the parts. Certainty fails whenever a coefficient is really a forecast — next quarter's demand, next month's price. Divisibility fails when the answer must be a whole number, and here the tempting shortcut is genuinely wrong: if the optimum is x₁ = 12.857 aircraft, rounding is not safe. Rounding up can push the point outside the constraints entirely (an infeasible plan), and rounding down can land far from the best whole-number plan, which need not be anywhere near the fractional one. Finding the true integer optimum needs branch and bound (L16–L18), not arithmetic on the LP answer.
3. The three standard forms
The same problem can be written three ways. Nothing about the situation changes; only the shape of the writing does. In all three, m is the number of constraints and n the number of variables, cⱼ is the objective coefficient of variable xⱼ, aᵢⱼ is the coefficient of xⱼ in constraint i, and bᵢ is the number on the right of constraint i. In matrix shorthand A holds the aᵢⱼ, and c, x and b are columns.
General form is how a problem arrives from the world: optimise Z = ∑ⱼ cⱼxⱼ subject to ∑ⱼ aᵢⱼxⱼ {≤, =, ≥} bᵢ for i = 1, …, m, with xⱼ ≥ 0. Either direction of optimisation, any mixture of the three relations, either sign of bᵢ. It is faithful to the story and useless to an algorithm.
Canonical form is the symmetric one: all rows point the same way, so the companion problem called the dual — a second LP built by transposing the coefficients, which prices the resources instead of choosing the activities — can be written down mechanically, with no sign traps. That is L07's business; here it is enough to know which shape it wants.
Standard form is the computational one, and the reason is worth spelling out. Once every row is an equation, m equations in n unknowns with n larger than m, you can pick m variables to solve for and set the other n − m to zero; the m you keep are called the basis, and the resulting point is a basic solution (basic feasible if it also obeys x ≥ 0). Solving normally means inverting a matrix — unless some variable appears with coefficient 1 in exactly one row and 0 in every other row. Such a column is a column of the identity matrix, and it hands you that variable's value for free: it simply equals that row's bᵢ. Standard form is engineered so that every row contains one such variable, which is why the slack and artificial variables of the next section exist at all. Requiring b ≥ 0 then makes that free starting solution non-negative, hence feasible.
4. The conversion rules
Six rules take any linear programme to standard form. They are listed here in the order you must apply them, and the order is not decorative: rules 1 to 3 rewrite what is already there, and only then do rules 4 to 6 add new variables. Add a slack first and then discover a negative right-hand side, and multiplying that row by −1 turns your + sᵢ into − sᵢ; the row has to be started again.
Rule 1 — make the objective a maximisation. Standard form is defined for maximisation, so a minimisation must be flipped. Negate every objective coefficient and maximise the result. Nothing about the constraints changes, so the feasible region is untouched and the winning x is exactly the same point; the smallest Z is the largest −Z. Only the reported number flips sign, and forgetting to flip it back is the single most common slip in this whole chapter.
Rule 2 — make every right-hand side non-negative. If bᵢ < 0, multiply that whole row by −1. Multiplying an inequality by a negative number reverses its direction, so a ≥ becomes a ≤ and vice versa (an = stays an =); every coefficient in the row changes sign too, including the right-hand side, which is the point of the exercise.
Do this before rules 4 to 6. A row's type decides which new variable it receives, and rule 2 can change that type — the row above arrives as a ≥ (which would take a surplus and an artificial) and leaves as a ≤ (which takes only a slack).
Rule 3 — remove unrestricted (free) variables. Standard form insists every variable be ≥ 0, so a variable allowed to go negative must be rewritten. Substitute the difference of two non-negative ones, everywhere it appears — in the objective and in every single constraint.
Any real number is the difference of two non-negative numbers, so nothing is lost: one free variable simply becomes two columns. A coefficient a on xⱼ becomes +a on xⱼʹ and −a on xⱼʺ. There is a cheaper route when a lower bound is known. If the problem says xⱼ ≥ −20, then xⱼ + 20 is already non-negative, so put xⱼ = xⱼʹ − 20 with xⱼʹ ≥ 0 and substitute as before: one variable in, one variable out, no extra column. Use the two-part split only when xⱼ has no lower bound at all.
Rule 4 — a ≤ row takes a slack variable. The row says the left side falls short of bᵢ by some non-negative amount; give that amount a name, sᵢ, and the inequality becomes an equation. The slack is real and readable: it is the resource left unused.
Notice the free gift: sᵢ appears in this row with coefficient +1 and in no other row, so it is exactly the identity column of the previous section. Setting all the original variables to zero gives sᵢ = bᵢ ≥ 0 immediately — a starting basic feasible solution at no cost.
Rule 5 — a ≥ row takes a surplus variable, and then an artificial. Here the left side exceeds bᵢ by a non-negative amount, so that amount is subtracted to reach equality.
So a ≥ row is repaired twice. After subtracting the surplus, add an artificial variable Aᵢ ≥ 0 with coefficient +1 to supply the missing identity column.
Rule 6 — an = row takes an artificial only. An equation is already an equation, so it needs neither slack nor surplus; but it still has no +1 column of its own, so it too gets Aᵢ ≥ 0.
Artificial variables are a scaffold, not part of the building. Adding Aᵢ genuinely enlarges the feasible set — any row can be satisfied by making its artificial large enough — so a solution is only a solution of the original problem when every artificial has reached zero. Two methods force that, and both are L06's subject: Big-M gives each artificial a coefficient of −M in the maximised objective, where M stands for a number larger than any coefficient in the problem, so keeping an artificial positive is ruinously expensive; two-phase ignores the real objective at first and minimises A₁ + A₂ + ⋯ on its own, then, if that minimum is zero, restarts from the basis it reached and optimises the real objective.
5. A worked conversion
One problem, all six rules, nothing skipped. Here is the programme as it arrives.
x₁ − 3x₂ + 2x₃ ≥ 4
x₁ + x₂ + x₃ = 8
x₁, x₂ ≥ 0, x₃ unrestricted
Rule 1 — flip the objective. It is a minimisation, so negate all three coefficients and maximise instead. The 3 becomes −3, the −2 becomes +2, the 4 becomes −4.
Rule 2 — check the right-hand sides. They are 10, 4 and 8, all non-negative, so no row needs multiplying by −1. Check this every time even when there is nothing to do; the rule is silent here, not absent.
Rule 3 — remove the free variable. Only x₃ is unrestricted. Put x₃ = x₃ʹ − x₃ʺ with both parts ≥ 0, and substitute in all four lines. Each coefficient of x₃ splits into a pair with opposite signs: −4x₃ becomes −4x₃ʹ + 4x₃ʺ in the objective, −x₃ becomes −x₃ʹ + x₃ʺ in row 1, +2x₃ becomes +2x₃ʹ − 2x₃ʺ in row 2, and +x₃ becomes +x₃ʹ − x₃ʺ in row 3.
Rules 4 to 6 — one branch per row. Row 1 is a ≤, so it takes a slack s₁. Row 2 is a ≥, so it loses a surplus s₂ and gains an artificial A₁ — the surplus alone would leave the row without a usable starting variable. Row 3 is already an equation, so it takes an artificial A₂ and nothing else.
Last, write the objective over the full variable list. Slack and surplus variables cost nothing, so they enter with coefficient 0; the artificials are penalised with −M so the method is pushed to drive them out.
Final tally. Six ordinary variables — x₁, x₂, x₃ʹ, x₃ʺ, s₁, s₂ — plus the two artificials make eight variables in three equations. Three originals became eight, and that expansion is normal rather than a mistake: it is the price of uniformity, because the simplex method now sees three rows of exactly one kind instead of a ≤, a ≥ and an =. Sanity check before moving on — each of s₁, A₁ and A₂ appears with coefficient +1 in exactly one row and nowhere else, so the starting solution can be read straight off: s₁ = 10, A₁ = 4, A₂ = 8.
6. Solved problems
max Zʹ = −5x₁ − 8x₂. Whatever value the method returns, the answer to the original question is Zmin = −Zʹmax.
The right-hand sides are 12, 20 and 2, all non-negative, so no row is multiplied by −1. Both variables are already declared ≥ 0, so there is no free variable to split. Say so explicitly rather than skipping: a rule that does not fire still has to be checked.
Three equations in six unknowns means three variables are solved for and the other three are set to zero. Choose as the three to keep exactly those with a +1 column of their own: A₁ from row 1, s₂ from row 2, A₂ from row 3. That forces the other three, x₁, x₂ and s₁, to zero, and each kept variable then simply equals its row's right-hand side: A₁ = 12, s₂ = 20, A₂ = 2. All are non-negative, so this starting point is feasible for the enlarged problem.
Now evaluate the objective there. With x₁ = x₂ = 0 the −5x₁ − 8x₂ part contributes nothing, s₂ carries coefficient 0, and the two artificials contribute −M(12) and −M(2):
That hugely negative number is the whole mechanism, not an accident. Because M stands for something enormous, any pivot that shrinks an artificial improves Zʹ far more than any trade among the real variables, so the method spends its first moves throwing the scaffold away.
The decision is not how much does Delhi send
but how much travels along each route
, so there is one variable per warehouse–city pair. Let xij be units shipped from i ∈ {D, M} to j ∈ {K, C, B} — two warehouses times three cities gives six variables. Each unit shipped on a route costs that route's rate, so total cost is the sum of rate times quantity over all six.
Group the six variables two ways. Summing a warehouse's row cannot exceed what it holds; summing a city's column must at least meet what it needs. That gives two supply rows and three demand rows.
Add up both sides. Total supply is 200 + 300 = 500 and total demand is 150 + 200 + 150 = 500, so the problem is balanced. That has a consequence worth deriving rather than asserting: the total shipped can be counted either by warehouse or by city, and it is at most 500 by the supply rows and at least 500 by the demand rows. Squeezed between the two, it is exactly 500 — which leaves no slack anywhere, so every ≤ and every ≥ holds with equality and may be rewritten as =. If supply had exceeded demand the ≤ rows would keep genuine slack, and the standard repair is to invent a dummy city that absorbs the surplus at zero cost.
This is now an ordinary LP with six variables and five equations, and the earlier rules would convert it. But look at the coefficient pattern: every variable appears in exactly two rows, once in its warehouse row and once in its city row, always with coefficient +1. A matrix of that shape is totally unimodular, meaning every square piece of it has determinant 0, +1 or −1. Two consequences follow. Because solving for the basis divides by such a determinant, the optimal values come out whole whenever the supplies and demands are whole — so integrality is free here, with no integer programming needed. And the pattern is regular enough that a specialised method, MODI (L09), exploits it with a small tableau instead of a full basis inverse.
In an ordinary LP you push one quantity as far as it will go. In goal programming you instead name a target and pay a penalty for missing it, possibly at different rates for missing high and missing low. The objective becomes deviate as little as possible
rather than maximise profit
, which is much closer to how targets are set in practice.
Revenue is 200x₁ + 350x₂, so the miss in either direction is |200x₁ + 350x₂ − 50000|. An absolute value bends at its zero — a V, not a straight line — so it is not linear and cannot go into an LP as written.
Instead of one signed miss, use two variables that are each never negative: let d⁻ ≥ 0 be the shortfall below target and d⁺ ≥ 0 the excess above it. Adding d⁻ and subtracting d⁺ lets revenue reach the target from whichever side it is on — if revenue is short, d⁻ makes up the difference; if it overshoots, d⁺ absorbs it.
The penalties are ₹5 per rupee short and ₹2 per rupee over, so the objective charges each deviation at its own rate and the machine-hour limit rides along unchanged.
The split would be a cheat if the model could raise both halves at once. It cannot. Suppose an optimal solution had d⁻ = a > 0 and d⁺ = b > 0, and reduce both by min(a, b). Because they enter the goal constraint with opposite signs, subtracting the same amount from each leaves the equation exactly as true as before, and both stay ≥ 0. But the objective 5d⁻ + 2d⁺ has two strictly positive costs, so it strictly falls — contradicting optimality. Hence at least one of them is zero at any optimum, and whichever survives is precisely the size of the miss. That is why d⁻ + d⁺ can stand in for an absolute value, and it is the standard trick behind all of goal programming.
Worth asking before trusting the model: if ₹50,000 were out of reach, the answer would be a large forced d⁻. The only limit is 4x₁ + 6x₂ ≤ 900, so compare revenue earned per machine-hour. Product 1 gives 200/4 = ₹50 per hour, product 2 gives 350/6 = ₹58.3 per hour, so every hour is worth more in product 2. Spending all 900 hours there gives x₂ = 900/6 = 150 units and revenue 350 × 150 = ₹52,500, which is the most this firm can possibly earn.
In (a) the constraint x₁x₂ ≤ 10 multiplies two decision variables together. The region it allows is curved inwards rather than flat-sided, so the corner argument that LP depends on simply does not apply; this needs non-linear programming, or a piecewise-linear approximation that replaces the curve by several straight pieces. In (b) the objective contains √x₁, which is concave — it rises ever more slowly. Minimising a concave function pushes the answer towards the extremes rather than to a single well-behaved point, and that is genuinely hard. Had the problem maximised the same concave function it would be a convex programme, which is tractable (L36) though still not an LP.
x₁/(x₁ + x₂) ≥ 0.4 is not linear because a variable sits in the denominator. Multiply both sides by x₁ + x₂, which is legitimate here precisely because that quantity is positive — multiplying an inequality by a positive number preserves its direction. Then collect terms:
Now linear. The one thing to guard is the sign of the denominator: if x₁ + x₂ could be negative, cross-multiplying would have flipped the inequality.
Reuse the device of Problem 3. Introduce d⁺, d⁻ ≥ 0, set x₁ − 5 = d⁺ − d⁻, and minimise d⁺ + d⁻ + x₂. The argument of Problem 3 applies word for word — both deviations enter the equation with opposite signs and both cost something — so at most one is positive at an optimum, and therefore d⁺ + d⁻ equals |x₁ − 5| exactly rather than merely bounding it. The trick works only because we are minimising the absolute value: maximising it would mean maximising a convex function, which is NP-hard in general.
The two written conditions are an if-then, not an algebraic relation. One row captures both: x₁ ≤ 100y with y ∈ {0, 1}. Substituting y = 0 gives x₁ ≤ 0, which with x₁ ≥ 0 forces x₁ = 0; substituting y = 1 gives back x₁ ≤ 100. Here 100 plays the part of M, chosen because it is already the largest x₁ can be. The constraints are linear, but y must be a whole number, so the model is a mixed-integer programme rather than an LP (L16–L18).
| Type | Repairable? | Method | |
|---|---|---|---|
| (a) | bilinear | ✗ | NLP |
| (b) | concave objective, minimised | ✗ | NLP or piecewise-linear |
| (c) | ratio | ✓ | cross-multiply |
| (d) | absolute value, minimised | ✓ | split into d⁺, d⁻ |
| (e) | logical condition | ✓ | big-M with a binary variable |
The tempting choice, nurses on duty during shift j
, does not work: those counts are not independent, because a nurse on duty in shift 4 may also be on duty in shift 5, and no set of constraints on the counts alone says which. Take the start time instead. Let xⱼ be the number of nurses who begin at shift j; each of them covers shifts j and j+1, with shift 7 wrapping round to shift 1. Every nurse is then counted exactly once, so the total hired is simply the sum.
Shift j is staffed by two groups: those starting at j, and those who started at j−1 and are still on. Each shift's requirement therefore constrains one adjacent pair.
x₃ + x₄ ≥ 16, x₄ + x₅ ≥ 9, x₅ + x₆ ≥ 5all xⱼ ≥ 0 and, strictly, whole numbers — nurses are indivisible
Look at the first row: shift 1 is covered by x₁ and by x₆, the nurses who started on the last shift of the day and are still working as the day rolls over. That wrap-around closes the cycle, and dropping it is the classic error — the model would then under-staff the night shift while looking perfectly healthy.
Add all six coverage rows together. Each xⱼ appears in exactly two of them, so the left-hand sides sum to 2(x₁ + ⋯ + x₆) = 2Z, while the right-hand sides sum to 7 + 15 + 12 + 16 + 9 + 5 = 64. Hence 2Z ≥ 64, that is Z ≥ 32. No schedule can beat 32 nurses. The bound is usually not reached, because it would need every nurse's two shifts to be fully needed, and uneven requirements make that impossible — a nurse hired for a busy shift is partly idle in the quiet one next to it.
Try covering the three busiest shifts head-on: x₁ = 15, x₃ = 16, x₅ = 5, the rest zero. Shift 2 gets x₁ + x₂ = 15, exactly its requirement, and shift 4 gets x₃ + x₄ = 16, exactly its requirement. But shift 5 is covered by x₄ + x₅ = 0 + 5 = 5 against a requirement of 9 — short by 4, so the plan is infeasible, not merely expensive. Raising x₅ to 9 repairs it and gives Z = 15 + 16 + 9 = 40. Feasible now, but as the next step shows, four nurses too many.
Exhaustive search over the whole nurse rostering problem gives x = (2, 13, 0, 16, 0, 5). Check every shift against its requirement by adding the adjacent pair: shift 1 gets x₆ + x₁ = 5 + 2 = 7 against 7; shift 2 gets 2 + 13 = 15 against 15; shift 3 gets 13 + 0 = 13 against 12; shift 4 gets 0 + 16 = 16 against 16; shift 5 gets 16 + 0 = 16 against 9; shift 6 gets 0 + 5 = 5 against 5. All six hold, and shifts 1, 2, 4 and 6 hold with equality, so those four are binding. The total is Z = 2 + 13 + 0 + 16 + 0 + 5 = 36 nurses.
7. Where these formulations are used
Airline crew scheduling
Problem 5 at scale: each variable a legal rotation, each constraint a flight leg to cover.
Freight distribution
Problem 2 with hundreds of depots; unimodularity delivers whole pallets with no integer machinery.
Refinery blending
Crude streams blended to octane and sulphur targets, where proportionality holds almost exactly.
Financial goal setting
The d⁺ / d⁻ split of Problem 3 states several budget targets at once and penalises missing each at its own rate.
Call-centre rostering
The same adjacent-pair structure as Problem 5 schedules agents, bus drivers and police patrols against a demand curve.
Diet and feed formulation
Minimise cost subject to nutrient minima. Every row is a ≥, so by rule 5 every row needs a surplus and an artificial.
8. Common mistakes
- Adding a slack to a ≥ row. A ≥ row loses a surplus and gains an artificial. Writing + sᵢ instead of − sᵢ silently states the opposite requirement, and the answer will be feasible for a problem nobody asked about.
- Stopping at the surplus. Subtracting sᵢ makes the row an equation but leaves it with no +1 column, so there is no starting solution. The artificial is not optional.
- Forgetting to flip the objective back. After maximising Zʹ = −Z, the answer to report is Zmin = −Zʹmax, not Zʹmax.
- Adding variables before fixing a negative right-hand side. Rule 2 comes first, because multiplying by −1 can turn a ≥ row into a ≤ row and change which variables it needs.
- Treating an artificial as meaningful. One left positive at optimality is a verdict of infeasibility, not a quantity of anything.
- Substituting a free variable in the objective only. The substitution xⱼ = xⱼʹ − xⱼʺ must be made in every constraint as well, or the rows no longer describe the same problem.
- Rounding a fractional answer to get an integer one. Rounding 12.857 aircraft can land outside the feasible region altogether; use branch and bound (L16–L18).
- Dropping the cyclic wrap-around in a rostering model, which quietly under-staffs the shift where the day rolls over.
9. Practice problems
- Convert to standard form: max 2x₁ + 3x₂ s.t. x₁ + x₂ ≥ 5, 2x₁ − x₂ ≤ 8, x₁ ≥ 0, x₂ free.
- How many variables after conversion in question 1? [Ans: x₁, x₂ʹ, x₂ʺ, s₁, s₂, A₁ = 6]
- Linearise (2x₁ + 3x₂)/(x₁ + x₂) ≤ 2.5. [Ans: 0.5x₂ ≤ 0.5x₁, that is x₂ ≤ x₁]
- Which LP assumption fails for quantity discounts? [Ans: proportionality]
- Formulate a seven-day staffing problem where each worker works five consecutive days. Follow Problem 5: one variable per starting day, and each day covered by five consecutive start variables, wrapping round the week.
- A minimisation has a ≥ constraint whose right-hand side is b₂ = −15. Convert the problem to standard form. Which rule applies to that row first, and what does the row look like once it has? Does it still need an artificial?
- Explain why an artificial variable left positive at optimality signals infeasibility. Argue from what adding the artificial did to the feasible set.
10. Summary
You can now do the following, without looking anything up.
- Decide whether a model is an LP at all. Every term a constant times a single variable to the first power: no products of variables, no powers, no functions. If it fails, name which of the four assumptions — proportionality, additivity, divisibility, certainty — broke, and say what the model becomes instead (mixed-integer, non-linear, stochastic).
- Choose the right form for the job. Canonical (all ≤, maximised) when you are about to write a dual; standard (all =, b ≥ 0, all variables ≥ 0) when you are about to run the simplex method. Converting between them changes the writing, never the optimal x.
- Convert any linear programme to standard form, in this order: (1) minimise ⟶ maximise by negating the objective; (2) any bᵢ < 0 ⟶ multiply that row by −1 and reverse its relation; (3) any free variable ⟶ xⱼ = xⱼʹ − xⱼʺ everywhere it appears; then, row by row, (4) ≤ ⟶ + slack; (5) ≥ ⟶ − surplus, + artificial; (6) = ⟶ + artificial. Rules 1 to 3 before 4 to 6, always.
- Explain why each rule exists, not just what it says: the slack's +1 column is a free starting solution, the surplus's −1 column is not, and the artificial is the scaffold that puts a +1 back.
- Read an artificial variable correctly. It has no physical meaning and must reach zero; one still positive at optimality means the original problem is infeasible.
- Repair the repairable non-linearities: ratios by cross-multiplying, minimised absolute values by splitting into d⁺ and d⁻, logical conditions by a big-M constraint with a binary. And recognise the ones you cannot repair inside LP: products of variables, minimisation of a concave function.
- Formulate the three standard applied shapes — a transportation problem (six route variables, supply and demand rows; balanced, totally unimodular, optimum ₹7,300 when solved in L09), a goal programme (target as an equation, deviations penalised), and a cyclic staffing problem (variables are start times, and the wrap-around row is not optional; 36 nurses against a bound of 32 and a naive plan of 40).