Unit 2: Transportation & assignment problems
Operation Research notes · PTU syllabus (BBA501-18)
On this page
Unit summary
Two special LP problems arise constantly: shipping goods at minimum cost (transportation) and assigning jobs to people at minimum cost (assignment). This unit covers both, including initial solutions, degeneracy, optimality and variations.
After this unit you can
- Formulate a transportation problem
- Find initial solutions by NWCR, least cost and VAM
- Test optimality with the MODI method and handle degeneracy
- Solve assignment problems with the Hungarian method, including variations
PTU syllabus topics
- General structure of the transportation problem
- methods of initial allocation
- degeneracy
- optimal solution
- the assignment problem
- structural variations in assignment problems
Topic 1
The transportation problem
It finds how much to ship from each source (factory) to each destination (warehouse) to minimise total cost, given supplies and demands.
- Balanced: total supply = total demand; otherwise add a dummy row or column with zero cost.
Example
North-West Corner Rule, step by step: supplies S1 = 20, S2 = 30, S3 = 50; demands D1 = 30, D2 = 40, D3 = 30 (total 100 = 100, balanced). Costs (₹ per unit): S1 — 2, 3, 5; S2 — 4, 1, 6; S3 — 3, 4, 2. Allocate (S1, D1) = 20 → S1 done; (S2, D1) = 10 → D1 done; (S2, D2) = 20 → S2 done; (S3, D2) = 20 → D2 done; (S3, D3) = 30. That is 5 allocations = m + n − 1 = 3 + 3 − 1, so the solution is non-degenerate. Cost = 20×2 + 10×4 + 20×1 + 20×4 + 30×2 = 40 + 40 + 20 + 80 + 60 = ₹240 — then test it for optimality with MODI.
Topic 2
Initial basic feasible solution
Each route has a unit cost; the aim is to meet demand from supply at least total cost. Methods: north-west corner, least cost, Vogel's approximation; then test with MODI
North-West Corner Rule
Allocate from the top-left cell, moving right or down
Quick but ignores cost
Least Cost Method
Allocate to the cheapest cell first
Better
Vogel's Approximation Method
Use penalties (difference between two lowest costs) to choose rows/columns
Usually closest to optimal
A basic feasible solution has m + n − 1 allocations (m sources, n destinations). Fewer means degeneracy — resolved by placing a tiny quantity ε in an independent empty cell.
Example
North-west corner and least cost: supplies are 20 and 30; demands are 10, 25 and 15. Costs are 2, 3, 1 in row 1 and 5, 4, 8 in row 2. NWCR: x₁₁ = 10, x₁₂ = 10, x₂₂ = 15, x₂₃ = 15; cost = 20 + 30 + 60 + 120 = ₹230. Least cost: x₁₃ = 15, x₁₁ = 5, x₂₂ = 25, x₂₁ = 5; cost = 15 + 10 + 100 + 25 = ₹150. Both have 4 allocations = m + n − 1.
Exam tip
VAM usually gives the best starting solution, least cost the next, and NWCR the poorest.
Topic 3
Optimality: the MODI method
The initial solution of a transportation problem (by NWCR, least cost or VAM) may not be the cheapest. The MODI (modified distribution) method tests it. It computes an opportunity cost for every empty cell; if none is negative, the solution is optimal. Otherwise the solution is improved by shifting units around a closed loop.
- 1
Find ui and vj with ui + vj = cij for occupied cells
Set one ui = 0
- 2
Compute opportunity cost for empty cells
dij = cij − (ui + vj)
- 3
All dij ≥ 0?
Optimal
- 4
Else enter the most negative cell
- 5
Form a closed loop and reallocate
- 6
Repeat
Example
The test on one empty cell: suppose for occupied cells we find u₁ = 0, v₁ = 4, v₂ = 6 and u₂ = 2. For the empty cell (2,1) with cost c₂₁ = 5, the opportunity cost is d₂₁ = c₂₁ − (u₂ + v₁) = 5 − (2 + 4) = −1. A negative value means that using this cell would reduce total cost by ₹1 per unit, so the solution is not yet optimal.
Exam tip
Before MODI, check that the number of occupied cells equals m + n − 1. If it is less, the solution is degenerate and a very small quantity ε must be added to an empty cell.
Topic 4
The assignment problem
Assigns n jobs to n persons (one each) to minimise cost or time.
- 1Row reduction
Subtract the row minimum
- 2Column reduction
Subtract the column minimum
- 3Cover all zeros with minimum lines
- 4Lines = n?
Make the optimal assignment
- 5Else adjust
Subtract the smallest uncovered value; add it at intersections; repeat
Variations: unbalanced problems (add dummy rows/columns), maximisation (subtract every element from the largest first), restricted assignments (put a very large cost M), and multiple optimal solutions.
Example
Hungarian method on a 3 × 3 problem: costs — Worker A: 10, 4, 8; B: 6, 7, 3; C: 5, 9, 6 (for jobs 1, 2, 3). Row reduction (subtract 4, 3 and 5): A — 6, 0, 4; B — 3, 4, 0; C — 0, 4, 1. Every column already has a zero, so column reduction changes nothing. The zeros at A–2, B–3 and C–1 lie in different rows and columns, so the assignment is optimal: A → job 2, B → job 3, C → job 1, total cost 4 + 3 + 5 = ₹12.
Exam tip
For a maximisation assignment (profits instead of costs), first subtract every number from the largest number in the table, then apply the Hungarian method as usual. For an unbalanced table, add a dummy row or column of zeros.
Key terms
- Transportation problem
- Minimising the cost of shipping from sources to destinations
- Dummy
- An extra row or column to balance a problem
- Degeneracy
- Fewer than m + n − 1 allocations
- MODI method
- A test of optimality using ui and vj
- Hungarian method
- An algorithm for assignment problems
Quick revision
- Balance first with a dummy.
- NWCR, LCM, VAM; VAM is usually best.
- Allocations must equal m + n − 1.
- Hungarian: reduce rows, reduce columns, cover zeros, adjust.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.What is a balanced transportation problem?
- Q2.Name three methods of finding an initial solution.
- Q3.What is degeneracy?
- Q4.What is the MODI method?
- Q5.How is a maximisation assignment problem solved?
Long-answer questions
- Q1.Find the initial solution of a transportation problem by NWCR, LCM and VAM and compare costs.
- Q2.Test the optimality of a transportation solution using MODI.
- Q3.Solve an assignment problem using the Hungarian method.
Stuck on this unit?
Message SBS on WhatsApp for help with Operation Research, or to ask about studying BBA at Synetic.
