Skip to content

Lesson 2: Introduction to Linear Programming and Formulation

2.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. State the four assumptions of linear programming and recognise when they fail.
  2. Write an LP in general, canonical and standard form and convert between them.
  3. Convert inequalities to equations using slack, surplus and artificial variables.
  4. Handle unrestricted variables and \(\ge\) constraints correctly.
  5. Formulate a range of applied problems as LPs.

2.2 What Makes a Programme Linear?

Definition. A linear programming problem is one in which a linear objective function is optimised subject to linear equality and inequality constraints, with variables restricted to non-negative values (in the standard treatment).

Definition (linear function). \(f(x_1,\ldots,x_n) = c_1x_1 + c_2x_2 + \cdots + c_nx_n\) — each variable appears to the first power, multiplied by a constant, with no products of variables and no transcendental functions.

Not linear: \(x_1x_2\), \(x_1^2\), \(\sqrt{x_1}\), \(\log x_1\), \(\max(x_1,x_2)\), \(|x_1|\).

2.3 The Four Assumptions

Assumption Meaning Fails when…
1. Proportionality the contribution of each variable is proportional to its value there are economies of scale, setup costs, or quantity discounts
2. Additivity total contribution = sum of individual contributions activities interact (e.g. two products share a joint setup)
3. Divisibility variables may take fractional values items are indivisible (aircraft, people) ⟹ use integer programming (L16–L18)
4. Certainty all coefficients are known constants parameters are random ⟹ use stochastic programming

Why these matter in practice

Proportionality fails most often through fixed setup costs. "Producing any quantity of product A incurs a ₹5000 setup" is not linear — the cost function jumps at zero. The standard fix is a binary variable \(y \in \{0,1\}\) with the big-M linking constraint

\[ x \le M y \]

so that \(x > 0\) forces \(y = 1\) and incurs the fixed cost — converting the model to a mixed-integer programme.

Divisibility fails whenever the answer must be a whole number. If the LP optimum is \(x_1 = 12.857\) aircraft, rounding is not safe: the rounded point may be infeasible, or feasible but far from the integer optimum. L16–L18 handle this properly.

The engineering judgement. If the LP optimum is \(x_1 = 12{,}857.3\) bottles, round it — the error is negligible. If it is \(12.857\) aircraft, do not.

2.4 The Three Standard Forms

General form

\[ \begin{aligned} \text{Optimise } & Z = \sum_{j=1}^{n} c_jx_j\\ \text{s.t. } & \sum_{j=1}^{n} a_{ij}x_j\ \{\le, =, \ge\}\ b_i, \quad i = 1,\ldots,m\\ & x_j \ge 0 \end{aligned} \]

Canonical form

Used for duality theory (L07).

\[ \begin{aligned} \max\ & Z = \vec c^{T}\vec x\\ \text{s.t. } & A\vec x \le \vec b\\ & \vec x \ge \vec 0 \end{aligned} \]

All constraints \(\le\), objective maximised, all variables non-negative.

Standard form

Used for the simplex method (L04–L05).

\[ \begin{aligned} \max\ & Z = \vec c^{T}\vec x\\ \text{s.t. } & A\vec x = \vec b, \quad \vec b \ge \vec 0\\ & \vec x \ge \vec 0 \end{aligned} \]

All constraints are equations, and all right-hand sides are non-negative.

2.5 Conversion Rules

Memorise these; every simplex problem begins with them.

Minimisation to maximisation

\[ \min\ Z = \sum c_jx_j \qquad\Longleftrightarrow\qquad \max\ Z' = -Z = \sum (-c_j)x_j \]

with \(Z_{\min} = -Z'_{\max}\).

Inequality to equality

A \(\le\) constraint — add a slack variable.

\[ \sum_j a_{ij}x_j \le b_i \qquad\Longrightarrow\qquad \sum_j a_{ij}x_j + s_i = b_i,\quad s_i \ge 0 \]

\(s_i\) = unused resource.

A \(\ge\) constraint — subtract a surplus variable.

\[ \sum_j a_{ij}x_j \ge b_i \qquad\Longrightarrow\qquad \sum_j a_{ij}x_j - s_i = b_i,\quad s_i \ge 0 \]

\(s_i\) = excess over the requirement.

The trap. For a \(\ge\) constraint the surplus variable enters with coefficient \(-1\), so it cannot serve as a basic variable with a non-negative value at the origin. This is exactly why artificial variables are needed (§4.4) and why the Big-M and two-phase methods exist (L06).

Negative right-hand side

If \(b_i < 0\), multiply the whole constraint by \(-1\) and reverse the inequality:

\[ 3x_1 - 2x_2 \ge -6 \qquad\Longrightarrow\qquad -3x_1 + 2x_2 \le 6 \]

Artificial variables

For a \(\ge\) or \(=\) constraint, add an artificial variable \(A_i \ge 0\) purely to provide an initial basic feasible solution:

\[ \sum_j a_{ij}x_j - s_i + A_i = b_i \]

Artificial variables have no physical meaning and must be driven to zero. Two methods do this:

  • Big-M: penalise them in the objective with a coefficient \(-M\) (for maximisation), \(M\) very large.
  • Two-phase: first minimise \(\sum A_i\); then, if the minimum is 0, proceed with the real objective.

If any artificial variable remains positive at optimality, the original problem is infeasible.

Unrestricted (free) variables

If \(x_j\) may be negative, substitute

\[ x_j = x_j' - x_j'', \qquad x_j', x_j'' \ge 0 \]

Then \(x_j > 0\) when \(x_j' > x_j''\), and \(x_j < 0\) when \(x_j'' > x_j'\). One free variable becomes two non-negative ones.

(Alternative: substitute \(x_j = x_j' - k\) for a lower bound \(k\), if one is known.)

2.6 Worked Conversion

Convert to standard form:

\[ \begin{aligned} \min\ & Z = 3x_1 - 2x_2 + 4x_3\\ \text{s.t. } & 2x_1 + x_2 - x_3 \le 10\\ & x_1 - 3x_2 + 2x_3 \ge 4\\ & x_1 + x_2 + x_3 = 8\\ & x_1, x_2 \ge 0, \quad x_3 \text{ unrestricted} \end{aligned} \]

Step 1 — objective to maximisation.

\[ \max\ Z' = -3x_1 + 2x_2 - 4x_3 \]

Step 2 — free variable. Put \(x_3 = x_3' - x_3''\) with \(x_3', x_3'' \ge 0\).

Step 3 — constraints.

\[ \begin{aligned} 2x_1 + x_2 - x_3' + x_3'' + s_1 &= 10 && \text{(slack)}\\ x_1 - 3x_2 + 2x_3' - 2x_3'' - s_2 + A_1 &= 4 && \text{(surplus + artificial)}\\ x_1 + x_2 + x_3' - x_3'' + A_2 &= 8 && \text{(artificial)} \end{aligned} \]

Step 4 — the Big-M objective.

\[ \max\ Z' = -3x_1 + 2x_2 - 4x_3' + 4x_3'' + 0s_1 + 0s_2 - MA_1 - MA_2 \]

Final tally: 7 variables (\(x_1, x_2, x_3', x_3'', s_1, s_2\) plus 2 artificials = 8), 3 equations. The original 3 variables became 8 — this expansion is normal and is the price of a uniform algorithm.

2.7 Solved Problems

Problem 1 — Complete conversion to standard form

Convert to standard form:

\[ \begin{aligned} \min\ & Z = 5x_1 + 8x_2\\ \text{s.t. } & 3x_1 + 2x_2 \ge 12\\ & x_1 + 4x_2 \le 20\\ & x_1 - x_2 = 2\\ & x_1, x_2 \ge 0 \end{aligned} \]

Solution.

Objective. \(\max\ Z' = -5x_1 - 8x_2\), with \(Z_{\min} = -Z'_{\max}\).

Constraint 1 (\(\ge\)): subtract surplus \(s_1\), add artificial \(A_1\):

\[ 3x_1 + 2x_2 - s_1 + A_1 = 12 \]

Constraint 2 (\(\le\)): add slack \(s_2\):

\[ x_1 + 4x_2 + s_2 = 20 \]

Constraint 3 (\(=\)): add artificial \(A_2\):

\[ x_1 - x_2 + A_2 = 2 \]

The complete standard form.

\[ \begin{aligned} \max\ & Z' = -5x_1 - 8x_2 + 0s_1 + 0s_2 - MA_1 - MA_2\\ \text{s.t. } & 3x_1 + 2x_2 - s_1 + A_1 = 12\\ & x_1 + 4x_2 + s_2 = 20\\ & x_1 - x_2 + A_2 = 2\\ & x_1, x_2, s_1, s_2, A_1, A_2 \ge 0 \end{aligned} \]

Initial basic feasible solution. Set the non-basic variables \(x_1 = x_2 = s_1 = 0\); the basis is \(\{A_1, s_2, A_2\}\) with

\[ A_1 = 12, \quad s_2 = 20, \quad A_2 = 2, \qquad Z' = -M(12) - M(2) = -14M \]

The hugely negative objective is exactly what drives the artificials out of the basis.

(For reference, this LP's optimum is \(x_1 = 3.2\), \(x_2 = 1.2\), \(Z_{\min} = 25.6\): check \(3(3.2)+2(1.2)=12\ge12\) ✓ (binding), \(3.2+4.8=8\le20\) ✓, \(3.2-1.2=2\) ✓.)

Problem 2 — Transportation formulation as an LP

A company has warehouses in Delhi (200 units) and Mumbai (300 units), supplying Kolkata (150), Chennai (200) and Bengaluru (150). Unit shipping costs (₹) are:

From \ To Kolkata Chennai Bengaluru
Delhi 16 22 18
Mumbai 14 12 20

Formulate as an LP.

Solution.

Decision variables.

\[ x_{ij} = \text{units shipped from warehouse } i \text{ to city } j \]

with \(i \in \{D, M\}\) and \(j \in \{K, C, B\}\) — 6 variables.

Objective.

\[ \min\ Z = 16x_{DK} + 22x_{DC} + 18x_{DB} + 14x_{MK} + 12x_{MC} + 20x_{MB} \]

Supply constraints (cannot ship more than you have):

\[ x_{DK} + x_{DC} + x_{DB} \le 200 \]
\[ x_{MK} + x_{MC} + x_{MB} \le 300 \]

Demand constraints (each city must be satisfied):

\[ x_{DK} + x_{MK} \ge 150 \]
\[ x_{DC} + x_{MC} \ge 200 \]
\[ x_{DB} + x_{MB} \ge 150 \]

Non-negativity. \(x_{ij}\ge0\).

Checking balance.

\[ \text{total supply} = 200 + 300 = 500, \qquad \text{total demand} = 150+200+150 = 500 \]

Balanced. When supply equals demand, every constraint must hold with equality at any feasible solution (you cannot leave supply unshipped if all of it is demanded), so the \(\le\) and \(\ge\) may be replaced by \(=\).

Why we still study a special algorithm. This is a perfectly ordinary LP with 6 variables and 5 equations. But the constraint matrix has a highly special structure — each variable appears in exactly two constraints, with coefficient \(+1\) — which makes it totally unimodular. Consequences:

  1. The optimal solution is automatically integral whenever supplies and demands are integers — no integer programming needed.
  2. A specialised algorithm (MODI, L09) solves it far faster than simplex, using a tableau rather than a full basis inverse.

(The optimum here is \(Z = ₹7{,}300\), found in L09.)

Problem 3 — A goal-programming style formulation with a free variable

A firm wants production of \(x_1\) and \(x_2\) to hit a target revenue of ₹50 000, where unit revenues are ₹200 and ₹350. Deviations in either direction are penalised: ₹5 per rupee of shortfall and ₹2 per rupee of excess. Machine hours available: \(4x_1 + 6x_2 \le 900\). Formulate.

Solution.

The difficulty. "Deviation in either direction" is \(|200x_1 + 350x_2 - 50000|\) — not linear.

The standard technique: split the deviation into two non-negative parts.

\[ d^{-} = \text{shortfall below target} \ge 0, \qquad d^{+} = \text{excess above target} \ge 0 \]

Goal constraint.

\[ 200x_1 + 350x_2 + d^{-} - d^{+} = 50{,}000 \]

(If revenue is below target, \(d^{-}>0\) makes up the difference; if above, \(d^{+}>0\) absorbs it.)

Objective.

\[ \min\ Z = 5d^{-} + 2d^{+} \]

Resource constraint.

\[ 4x_1 + 6x_2 \le 900 \]

Complete model.

\[ \begin{aligned} \min\ & Z = 5d^{-} + 2d^{+}\\ \text{s.t. } & 200x_1 + 350x_2 + d^{-} - d^{+} = 50{,}000\\ & 4x_1 + 6x_2 \le 900\\ & x_1, x_2, d^{-}, d^{+} \ge 0 \end{aligned} \]

Why \(d^{-}\) and \(d^{+}\) are never both positive at an optimum. Suppose both were positive, say \(d^{-} = a > 0\) and \(d^{+} = b > 0\). Reducing both by \(\min(a,b)\) keeps the goal constraint satisfied (they appear with opposite signs) and strictly reduces the objective, since both cost coefficients are positive. So at least one is zero at any optimum ✓.

\[ \boxed{\ \textbf{This is the standard trick for absolute values and goal programming.}\ } \]

A quick feasibility observation. The maximum achievable revenue is found by maximising \(200x_1+350x_2\) subject to \(4x_1+6x_2\le900\). Per machine-hour, product 1 yields \(200/4 = ₹50\) and product 2 yields \(350/6 = ₹58.3\). So devote all hours to product 2: \(x_2 = 150\), revenue \(= ₹52{,}500\). Since \(52{,}500 > 50{,}000\), the target is attainable, and the optimum will have \(d^- = 0\) with a small \(d^+\) — or exactly zero deviation if a combination hits ₹50 000 exactly.

Problem 4 — Recognising and repairing non-linearities

Which of the following are linear? Repair those that can be linearised.

(a) \(\max\ 3x_1 + 5x_2\) s.t. \(x_1x_2 \le 10\) (b) \(\min\ \sqrt{x_1} + x_2\) (c) \(\max\ 4x_1 + 7x_2\) s.t. \(\dfrac{x_1}{x_1+x_2} \ge 0.4\) (d) \(\min\ |x_1 - 5| + x_2\) (e) \(\max\ 2x_1\) s.t. \(x_1 \le 100\) if \(y = 1\), \(x_1 = 0\) if \(y = 0\), \(y\) binary

Solution.

(a) Non-linear — and NOT repairable within LP. The product \(x_1x_2\) makes the feasible region non-convex. This needs non-linear programming (Unit IV) or a piecewise-linear approximation.

(b) Non-linear objective — not repairable exactly. \(\sqrt{x_1}\) is concave. For a minimisation of a concave function the problem is genuinely hard. (Had it been maximisation of a concave function it would be a convex programme — see L36.) A piecewise-linear approximation is the practical route.

(c) Non-linear as written — REPAIRABLE. Cross-multiply (valid since \(x_1+x_2>0\)):

\[ x_1 \ge 0.4(x_1+x_2) \ \Longrightarrow\ 0.6x_1 - 0.4x_2 \ge 0 \ \Longrightarrow\ \boxed{3x_1 \ge 2x_2} \]

Now linear ✓ (the technique of L01, Problem 3).

(d) Non-linear as written — REPAIRABLE. Introduce \(d^{+}, d^{-}\ge0\) with

\[ x_1 - 5 = d^{+} - d^{-}, \qquad \min\ d^{+} + d^{-} + x_2 \]

Now linear ✓. As shown in Problem 3, at an optimum at most one of \(d^\pm\) is positive, so \(d^{+}+d^{-} = |x_1 - 5|\) exactly.

(This works because we are minimising the absolute value. Maximising \(|x_1-5|\) is not linearisable — it maximises a convex function, which is NP-hard in general.)

(e) Conditional — REPAIRABLE as a mixed-integer programme. The "big-M" linking constraint:

\[ x_1 \le 100y, \qquad y\in\{0,1\} \]

If \(y=0\) then \(x_1\le0\), forcing \(x_1 = 0\) ✓. If \(y=1\) then \(x_1\le100\) ✓. Linear constraints, but with an integer variable — so this is an MILP, not an LP (L16–L18).

Summary table.

Type Repairable? Method
(a) bilinear ✗ NLP
(b) concave objective (min) ✗ NLP / piecewise
(c) ratio ✓ cross-multiply
(d) absolute value (min) ✓ split into \(d^{+}, d^{-}\)
(e) logical condition ✓ big-M with a binary variable

Problem 5 — A staffing problem with cyclic constraints

A hospital needs nurses on six 4-hour shifts per day, with minimum requirements 7, 15, 12, 16, 9, 5. Each nurse works two consecutive shifts. Formulate an LP minimising the number of nurses.

Solution.

Decision variables. Let

\[ x_j = \text{nurses starting at the beginning of shift } j, \qquad j = 1,\ldots,6 \]

Each such nurse covers shifts \(j\) and \(j+1\) (with shift 7 wrapping to shift 1).

Objective.

\[ \min\ Z = x_1 + x_2 + x_3 + x_4 + x_5 + x_6 \]

Coverage constraints. Shift \(j\) is staffed by nurses who started at shift \(j\) and those who started at shift \(j-1\):

\[ \begin{aligned} \text{Shift 1:}\quad & x_6 + x_1 \ge 7\\ \text{Shift 2:}\quad & x_1 + x_2 \ge 15\\ \text{Shift 3:}\quad & x_2 + x_3 \ge 12\\ \text{Shift 4:}\quad & x_3 + x_4 \ge 16\\ \text{Shift 5:}\quad & x_4 + x_5 \ge 9\\ \text{Shift 6:}\quad & x_5 + x_6 \ge 5 \end{aligned} \]

Non-negativity (and, strictly, integrality — nurses are indivisible).

Two structural observations worth teaching.

  1. The cyclic wrap-around. Shift 1's constraint involves \(x_6\), closing the cycle. Forgetting this is the most common error, and it produces a solution that under-staffs the night shift.

  2. A lower bound by inspection. Every nurse covers exactly 2 shifts, so

    \[ 2Z \ge \sum_j(\text{requirement}_j) = 7+15+12+16+9+5 = 64 \ \Longrightarrow\ Z \ge 32 . \]

    This bound is usually not attained, because requirements are uneven — a nurse hired to cover a busy shift may be idle in the adjacent quiet one.

A first attempt. Take \(x_1 = 15\), \(x_3 = 16\), \(x_5 = 5\), others 0:

Shift Coverage Required Status
1 \(x_6+x_1 = 0+15 = 15\) 7 ✓
2 \(x_1+x_2 = 15+0 = 15\) 15 ✓ binding
3 \(x_2+x_3 = 0+16 = 16\) 12 ✓
4 \(x_3+x_4 = 16+0 = 16\) 16 ✓ binding
5 \(x_4+x_5 = 0+5 = 5\) 9 ✗ short by 4

Infeasible. Raising \(x_5\) to 9 repairs it and gives \(Z = 15+16+9 = 40\) — feasible, but not optimal.

The true optimum. Exhaustive search gives \(\vec x = (2, 13, 0, 16, 0, 5)\):

Shift Coverage Required Status
1 \(5+2 = 7\) 7 ✓ binding
2 \(2+13 = 15\) 15 ✓ binding
3 \(13+0 = 13\) 12 ✓
4 \(0+16 = 16\) 16 ✓ binding
5 \(16+0 = 16\) 9 ✓
6 \(0+5 = 5\) 5 ✓ binding
\[ Z = 2+13+0+16+0+5 = \mathbf{36\ \text{nurses}} \]

Compared with the lower bound of 32, the excess of 4 is the unavoidable cost of uneven demand. Note that the naive plan needed 40 — 11 % more staff than necessary, which at nursing salaries is a substantial annual sum. That gap is precisely the value LP delivers here.

Why this model matters. Set-covering formulations of exactly this shape schedule airline crews, call-centre agents, bus drivers and police patrols — among the most economically significant applications of LP in existence.

2.8 Practice Problems

  1. Convert to standard form: \(\max\ 2x_1+3x_2\) s.t. \(x_1+x_2\ge5\), \(2x_1-x_2\le8\), \(x_1\ge0\), \(x_2\) free.
  2. How many variables after conversion in Problem 1? [Ans: \(x_1, x_2', x_2'', s_1, s_2, A_1\) = 6]
  3. Linearise \(\dfrac{2x_1+3x_2}{x_1+x_2}\le 2.5\). [Ans: \(0.5x_2 \le 0.5x_1\), i.e. \(x_2\le x_1\)]
  4. Which LP assumption fails for quantity discounts? [Ans: proportionality]
  5. Formulate a 7-day staffing problem where each worker works 5 consecutive days.
  6. Convert \(\min\ Z\) with \(b_2 = -15\) on a \(\ge\) constraint into standard form.
  7. Explain why an artificial variable positive at optimality signals infeasibility.

2.9 Summary

  • LP optimises a linear objective over linear constraints; the four assumptions are proportionality, additivity, divisibility and certainty.
  • Canonical form (all \(\le\), max) is used for duality; standard form (all \(=\), \(\vec b\ge0\)) is used for simplex.
  • Conversions: \(\min \to \max\) by negation; \(\le\) ⟶ + slack; \(\ge\) ⟶ − surplus + artificial; \(b_i<0\) ⟶ multiply by \(-1\); free variable ⟶ \(x = x' - x''\).
  • Artificial variables have no meaning and must reach zero; if any is positive at optimality, the problem is infeasible.
  • Repairable non-linearities: ratios (cross-multiply), minimised absolute values (split into \(d^{+}, d^{-}\)), logical conditions (big-M with a binary). Not repairable within LP: products of variables, concave minimisation.
  • Transportation problems are LPs with totally unimodular structure, so their optima are automatically integral.
  • Set-covering / cyclic staffing models are among LP's most valuable real applications; remember the wrap-around constraint.

Next lesson: L03 — The graphical method.

Practise now: unit1-lp-lab.html → Standard Form Converter: type any LP and watch the slack, surplus and artificial variables be introduced step by step.