QUANTITATIVE TECHNIQUES›UNIT 03›TRANSPORTATION & ASSIGNMENT

Unit 03 — Transportation & Assignment

Recognising the two problem types, checking whether they are balanced, counting variables and constraints, converting the cost matrix into a full LPP — and solving it by NWCR, Least Cost, VAM, MODI and the Hungarian method.

SESSIONS: 4 TEXTBOOK: ANDERSON & SWEENEY — CH. 6, SEC. 6.1 pp. 259–265, SEC. 6.2 pp. 274–278 SCOPE: FORMULATION & BALANCE — SEE SCOPE NOTE Full PPT: Assignment class notes 6 Note 2 — Transportation 23

⚠ Scope note — read this before you revise

The course session plan lists the full Unit 3 as including North-West Corner Rule, Least Cost Method, VAM, the Modified Distribution (MODI) method, degeneracy, maximisation problems and the Hungarian Method Policy p. 7.

Your class notes — the handwritten Assignment Problems set pp. 1–6 and Note 2 pp. 12–18 — stop at formulation, and so do Assignment 6 and every 2025-26 paper question (Q1B, Q5B, Q7). Concepts 1–3 cover that thoroughly.

Concept 4 adds the solving algorithms from the standard textbook method, clearly labelled, so that a "solve by VAM / test by MODI / use the Hungarian method" question cannot catch you out.

◆ What the papers ask from this unit

Q1B (2.5 marks), both papers — a cost matrix, then three fixed sub-questions: Is the problem balanced? Number of constraints (excluding NNC)? Number of variables? Final p. 1 Re-Exam p. 1. This is the most formulaic 2.5 marks on the paper. Solved →
Q5B (5 marks), both papers — flight scheduling: "formulate an assignment problem to minimise aircraft overnight idle time". Solved →
Q7B (5 marks), Final — "formulate in transportation format and identify the number of constraints and variables", with a profit twist. Solved →

1. Telling the Two Problems Apart Core syllabus concept

1Understand the Concept

Both problems arrive as a cost matrix. One sentence separates them Class notes p. 3:

If demand and supply are given, it is a transportation problem. If instead every row must be matched one-to-one with exactly one column, it is an assignment problem.

	Transportation problem	Assignment problem
Rows / columns	Sources (plants, warehouses) × Destinations (markets, regions)	Workers / machines / flights × Tasks / jobs / return flights
Extra data	A supply column and a demand row	None — just the cost matrix
Balanced when	Total supply = total demand	Number of rows (m) = number of columns (n)
Xᵢⱼ means	Quantity shipped from i to j (any non-negative number)	1 if row i is assigned to column j, else 0
Row constraint	Σⱼ Xᵢⱼ ≤ supplyᵢ	Σⱼ Xᵢⱼ = 1 (each worker gets exactly one task)
Column constraint	Σᵢ Xᵢⱼ = demandⱼ	Σᵢ Xᵢⱼ = 1 (each task gets exactly one worker)

2Worked Example — which problem type is each of these?

Question

For each scenario, state whether it is a transportation or an assignment problem, give your reason, and state the number of variables and constraints.

Scenario A

Three factories with monthly capacities of 500, 700 and 400 units supply four warehouses requiring 300, 600, 400 and 300 units. Shipping cost per unit differs by route. Minimise total shipping cost.

Step 1 — Look for the give-away Capacities are given (supply) AND requirements are given (demand) ⟹ TRANSPORTATION problem
Step 2 — Size and balance m = 3 factories , n = 4 warehouses Total supply = 500 + 700 + 400 = 1600 Total demand = 300 + 600 + 400 + 300 = 1600 1600 = 1600 ⟹ BALANCED, no dummy needed
Step 3 — Counting Variables = m × n = 3 × 4 = 12 Constraints = m + n = 3 + 4 = 7 Xᵢⱼ = quantity shipped, so Xᵢⱼ can be ANY non-negative number

Scenario B

Five salespeople must each be given exactly one of five territories. The expected sales for each person in each territory are known. Maximise total expected sales.

Step 1 — Look for the give-away No supply column, no demand row Each person takes exactly ONE territory, and each territory gets exactly ONE person ⟹ ASSIGNMENT problem
Step 2 — Size and balance m = 5 salespeople , n = 5 territories m = n ⟹ BALANCED
Step 3 — Counting, and the variable type Variables = m × n = 5 × 5 = 25 Constraints = m + n = 5 + 5 = 10 Xᵢⱼ = 1 if person i gets territory j, else 0 — BINARY, not a quantity
Step 4 — Note the objective direction
This one maximises sales rather than minimising cost. The structure is identical; only Min becomes Max. Do not assume every assignment problem is a minimisation.

⚠ The one-line test

Ask: "Is a row allowed to be split across several columns?" If yes — a factory can ship to several warehouses — it is transportation and Xᵢⱼ is a quantity. If no — one person, one territory — it is assignment and Xᵢⱼ is 0 or 1.

Sources

Class Assignment vs transportation, cost matrix pp. 1–4 · Note 2 pp. 12–14

2. Balance, Variables and Constraints Core syllabus concept

1The three counting rules

Q1B in both papers is exactly these three rules applied to an m × n matrix. Memorise them as a block:

Number of VARIABLES = m × n (one Xᵢⱼ per cell of the matrix) Number of CONSTRAINTS = m + n (one per row + one per column, excluding NNC) BALANCED? Assignment → m = n Transportation → Σ supply = Σ demand

2How to balance an unbalanced problem

Whichever side is less, add a corresponding DUMMY row or column, and set every cost in the dummy to zero Class notes p. 1.

Assignment: if rows ≠ columns, add a dummy row (or column) of zeros so the matrix becomes square.
Transportation: if Σ supply ≠ Σ demand, add a dummy source (if supply is short) or dummy destination (if demand is short), with zero costs and the missing quantity as its supply/demand p. 3.

Why zero costs: a dummy represents goods that are never actually shipped, or a task never actually performed. Charging it nothing keeps the objective value honest.

3Worked — the exact Q1B pattern, both versions

Final Exam Q1B — assignment, 3 workers × 3 tasks QP p. 1

	T1	T2	T3
W1	9	2	7
W2	6	4	3
W3	5	8	1

Answer: (1) Yes, balanced — number of rows = number of columns = 3. (2) Constraints m + n = 3 + 3 = 6. (3) Variables m × n = 3 × 3 = 9. Matches the synoptic key exactly Key p. 1.

Re-Exam Q1B — transportation, and this one is not balanced QP p. 1

	P1	P2	P3	Supply
W1	9	2	7	30
W2	6	4	3	25
W3	5	8	1	20
Demand	20	30	35

Answer: Σ supply = 30 + 25 + 20 = 75; Σ demand = 20 + 30 + 35 = 85. (1) No, not balanced — demand exceeds supply by 10, so add a dummy row (source) with supply 10 and zero costs. (2) Constraints m + n = 3 + 3 = 6. (3) Variables m × n = 3 × 3 = 9. Matches the key Key p. 1.

⚠ The counting subtlety

The synoptic key counts m + n and m × n on the original matrix, not on the balanced one. Answer the counting parts from the matrix as given, and mention the dummy separately when asked how to balance it. Also note the phrase "excluding NNC" in the question — the non-negativity restriction is not counted as a constraint.

ENBalanced & Unbalanced theory College Tutor HIUnbalanced → balanced (Hindi) Start Practicing

Practice H1–H2 — one unbalanced assignment, one unbalanced transportation →

Sources

Class Balance rule, dummy rows, counting pp. 1, 3 · Note 2 pp. 12–13

Exam Final Q1B p. 1 + key p. 1 · Re-Exam Q1B p. 1 + key p. 1

3. Converting the Matrix into an LPP Core syllabus concept

1The template — assignment problem

4 employees × 4 tasks, the class example Class notes pp. 1–2

Employees	Task 1	Task 2	Task 3	Task 4
A	10	12	8	15
B	8	10	12	11
C	12	15	9	13
D	11	9	14	10

Solution

Step 1 — Housekeeping (write these four lines first, they carry marks) Balanced problem : Yes (m = n = 4) No. of variables : m × n = 4 × 4 = 16 No. of constraints: m + n = 4 + 4 = 8 Decision variable : Xᵢⱼ , i → employee A to D , j → task 1 to 4 Xᵢⱼ = 1 if employee i is assigned task j, else 0
Step 2 — Objective function, read row by row off the matrix Min Z = 10X₁₁ + 12X₁₂ + 8X₁₃ + 15X₁₄ + 8X₂₁ + 10X₂₂ + 12X₂₃ + 11X₂₄ + 12X₃₁ + 15X₃₂ + 9X₃₃ + 13X₃₄ + 11X₄₁ + 9X₄₂ + 14X₄₃ + 10X₄₄
Step 3 — Row constraints: each employee gets exactly one task X₁₁ + X₁₂ + X₁₃ + X₁₄ = 1 X₂₁ + X₂₂ + X₂₃ + X₂₄ = 1 X₃₁ + X₃₂ + X₃₃ + X₃₄ = 1 X₄₁ + X₄₂ + X₄₃ + X₄₄ = 1
Step 4 — Column constraints: each task goes to exactly one employee X₁₁ + X₂₁ + X₃₁ + X₄₁ = 1 X₁₂ + X₂₂ + X₃₂ + X₄₂ = 1 X₁₃ + X₂₃ + X₃₃ + X₄₃ = 1 X₁₄ + X₂₄ + X₃₄ + X₄₄ = 1
Step 5 — Non-negativity, and the internal check Xᵢⱼ ≥ 0 (and binary, 0 or 1) 4 row + 4 column = 8 constraints ✓ matches the m + n counted in Step 1

2The template — transportation problem

3 origins × 4 destinations, the class example Class notes pp. 3–4

	D1	D2	D3	D4	Supply
O₁	6	4	1	5	14
O₂	8	9	2	7	16
O₃	4	3	6	2	5
Demand	6	10	15	4	35 / 35

Solution

Step 1 — Housekeeping, starting with the balance test Total supply = 14 + 16 + 5 = 35 Total demand = 6 + 10 + 15 + 4 = 35 35 = 35 ⟹ BALANCED, no dummy needed Decision variable : Xᵢⱼ = quantity shipped from origin i (1–3) to destination j (1–4) No. of variables : m × n = 3 × 4 = 12 No. of constraints: m + n = 3 + 4 = 7
Step 2 — Objective function, read row by row Min Z = 6X₁₁ + 4X₁₂ + 1X₁₃ + 5X₁₄ + 8X₂₁ + 9X₂₂ + 2X₂₃ + 7X₂₄ + 4X₃₁ + 3X₃₂ + 6X₃₃ + 2X₃₄
Step 3 — Supply constraints, one per ROW — note the ≤ X₁₁ + X₁₂ + X₁₃ + X₁₄ ≤ 14 X₂₁ + X₂₂ + X₂₃ + X₂₄ ≤ 16 X₃₁ + X₃₂ + X₃₃ + X₃₄ ≤ 5
Step 4 — Demand constraints, one per COLUMN — note the = X₁₁ + X₂₁ + X₃₁ = 6 X₁₂ + X₂₂ + X₃₂ = 10 X₁₃ + X₂₃ + X₃₃ = 15 X₁₄ + X₂₄ + X₃₄ = 4
Step 5 — Non-negativity, and the internal check Xᵢⱼ ≥ 0 3 supply + 4 demand = 7 constraints ✓ matches m + n from Step 1
The asymmetry is deliberate: supply is a ceiling (≤) but demand must be met exactly (=). When the problem is perfectly balanced you may write the supply constraints as = too; the class notes use ≤, which is the safer general form.

⚠ Unit 3 — where marks are lost

Writing Xᵢⱼ without saying what i and j range over. "i → row 1 to 3, j → column 1 to 4" is a marked line.
Mixing up the row and column constraint directions. Supply ≤, demand =. For assignment, both are = 1.
Transposing the cost matrix in the objective. X₁₃ is row 1, column 3 — read row-wise and it is impossible to slip.
Answering "how many constraints" with m × n. Variables are m × n; constraints are m + n. They are swapped surprisingly often under time pressure.

ENTransportation — LP formulation Joshua Emmanuel ENAssignment — dummy nodes Joshua Emmanuel

Practice H3–H5 — full LPP conversion, profit variant, forbidden pairing →

Sources

Class Full LPP conversion for both problem types pp. 1–4 · Note 2 pp. 12–18

Course Session plan for Unit 3 Policy p. 7

Exam Final Q5B, Q7B pp. 4, 6 · Re-Exam Q5B p. 3

4. Solving the Problems — NWCR, Least Cost, VAM, MODI and the Hungarian Method Supporting concept

Why this section exists

The session plan lists these algorithms for Unit 3 Policy p. 7, but your class notes, Assignment 6 and both 2025-26 papers only ever ask for formulation. They are added here for completeness, using the standard textbook method, so that a "find the initial solution by VAM" question cannot catch you out.

1The three ways to get an initial feasible solution

Method	Rule	Quality
North-West Corner (NWCR)	Start top-left; allocate as much as possible; move right when a column is filled, down when a row is used up.	Fast, ignores cost — usually poor
Least Cost (LCM)	Allocate as much as possible to the cheapest cell left; strike out the exhausted row/column; repeat.	Better
Vogel's Approximation (VAM)	For every row and column, penalty = difference between its two lowest costs. Pick the largest penalty; allocate to the cheapest cell in that row/column; strike out; recompute.	Best — often optimal or close

Count check: a basic feasible solution has exactly m + n − 1 occupied cells (3 + 4 − 1 = 6 here). Fewer ⟹ degenerate: put a tiny ε in an empty independent cell so the MODI test can run.

2Worked Example — one problem, three starting solutions

Question

Cost	D1	D2	D3	D4	Supply
S1	19	30	50	10	7
S2	70	30	40	60	9
S3	40	8	70	20	18
Demand	5	8	7	14	34

Find an initial solution by NWCR, LCM and VAM, then test the VAM solution for optimality.

Solution

NWCR

NWCR D1 D2 D3 D4 Supply

S1 5 @19 2 @30 50 10 7

S2 70 6 @30 3 @40 60 9

S3 40 8 4 @70 14 @20 18

Demand 5 8 7 14 34

Cost = 5(19) + 2(30) + 6(30) + 3(40) + 4(70) + 14(20) = ₹1,015
Least Cost

LCM D1 D2 D3 D4 Supply

S1 19 30 50 7 @10 7

S2 2 @70 30 7 @40 60 9

S3 3 @40 8 @8 70 7 @20 18

Demand 5 8 7 14 34

Cheapest cell first: S3D2 (8) ← 8, then S1D4 (10) ← 7, S3D4 (20) ← 7, S2D3 (40) ← 7, S3D1 (40) ← 3, S2D1 (70) ← 2.
Cost = ₹814

NWCR	D1	D2	D3	D4	Supply
S1	5 @19	2 @30	50	10	7
S2	70	6 @30	3 @40	60	9
S3	40	8	4 @70	14 @20	18
Demand	5	8	7	14	34

LCM	D1	D2	D3	D4	Supply
S1	19	30	50	7 @10	7
S2	2 @70	30	7 @40	60	9
S3	3 @40	8 @8	70	7 @20	18
Demand	5	8	7	14	34

VAM — penalties at each step

Step	Largest penalty	Allocate
1	Column D2: 30 − 8 = 22	S3D2 ← 8
2	Column D1: 40 − 19 = 21	S1D1 ← 5
3	Row S3: 70 − 20 = 50	S3D4 ← 10
4	Column D4: 60 − 10 = 50	S1D4 ← 2
5	Only S2 is left	S2D3 ← 7, S2D4 ← 2

VAM	D1	D2	D3	D4	Supply
S1	5 @19	30	50	2 @10	7
S2	70	30	7 @40	2 @60	9
S3	40	8 @8	70	10 @20	18
Demand	5	8	7	14	34

Cost = 5(19) + 2(10) + 7(40) + 2(60) + 8(8) + 10(20) = ₹779 — 6 occupied cells = m + n − 1 ✓

MODI test on the VAM solution For every occupied cell, uᵢ + vⱼ = cᵢⱼ; set u₁ = 0 u₁ = 0, u₂ = 50, u₃ = 10; v₁ = 19, v₂ = −2, v₃ = −10, v₄ = 10 For every empty cell, dᵢⱼ = cᵢⱼ − (uᵢ + vⱼ): S1D2 = 32, S1D3 = 60, S2D1 = 1, S2D2 = 30 − 48 = −18, S3D1 = 11, S3D3 = 70 A negative dᵢⱼ (S2D2) ⟹ NOT optimal
One improvement — the closed loop Loop: S2D2 (+) → S3D2 (−) → S3D4 (+) → S2D4 (−) θ = smallest (−) allocation = min(8, 2) = 2 New: S2D2 = 2, S3D2 = 6, S3D4 = 12, S2D4 = 0 (leaves) Cost falls by 18 × 2 = 36 ⟹ ₹743

Optimal D1 D2 D3 D4 Supply

S1 5 @19 30 50 2 @10 7

S2 70 2 @30 7 @40 60 9

S3 40 6 @8 70 12 @20 18

Demand 5 8 7 14 34

Re-running MODI gives no negative dᵢⱼ, so ₹743 is optimal — confirmed independently by solving the LPP.

3Two variations

Variation	What to do
Maximisation (profit matrix)	Convert to a loss matrix — subtract every profit from the largest profit (or multiply by −1) — then minimise as usual.
Unbalanced	Add a dummy row or column with zero cost first (concept 2).
Degeneracy	Occupied cells < m + n − 1: place ε (a very small quantity) in an empty cell that does not form a loop, and continue.

4The Hungarian method for assignment problems

Row reduction — subtract each row's minimum from every entry in that row.
Column reduction — subtract each column's minimum from every entry in that column.
Cover all zeros with the minimum number of horizontal/vertical lines.
If the number of lines = n, an optimal assignment exists among the zeros — pick one zero in each row and column.
Otherwise subtract the smallest uncovered number from every uncovered cell, add it to cells covered twice, and return to step 3.

Fully worked on a flight-pairing problem — with two optimal answers — in Assignment 6, Q1. For a maximisation assignment, first subtract every entry from the largest; for a forbidden pairing, put a very large cost (M) in that cell.

Sources

Course Session plan, Unit 3: NWCR, Least Cost, VAM, unbalanced problems, MODI, degeneracy, maximisation, Hungarian method Policy p. 7

Textbook Anderson & Sweeney Ch. 6 sec. 6.1–6.2 (named by the session plan; not supplied as a file). The worked example is a standard textbook problem, checked by solving its LPP.