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
- 1Balance the problem
Add dummy row or column if needed
- 2Initial solution
NWCR, least cost or VAM
- 3Check for degeneracy
Allocations = m + n − 1
- 4Test optimality
MODI method
- 5Improve until optimal
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.
Topic 2
Initial basic feasible solution
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.
Topic 3
Optimality: the MODI method
- 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
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.
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.