Unit 2 of 4 · BBA Sem 5

Unit 2: Transportation & assignment problems

Operation Research notes · PTU syllabus (BBA501-18)

3 min read4 topics8 exam questions
On this page
  1. Unit summary
  2. The transportation problem
  3. Initial basic feasible solution
  4. Optimality: the MODI method
  5. The assignment problem
  6. Key terms
  7. Quick revision
  8. Important questions

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
1

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.

2

Topic 2

Initial basic feasible solution

GraphTransportation problem: sources and destinations
S1S2D1D2D3

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

ComparisonMethods for the initial solution
How
Quality

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.

3

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.

ProcessMODI (modified distribution) method
  1. 1

    Find ui and vj with ui + vj = cij for occupied cells

    Set one ui = 0

  2. 2

    Compute opportunity cost for empty cells

    dij = cij − (ui + vj)

  3. 3

    All dij ≥ 0?

    Optimal

  4. 4

    Else enter the most negative cell

  5. 5

    Form a closed loop and reallocate

  6. 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.

4

Topic 4

The assignment problem

Assigns n jobs to n persons (one each) to minimise cost or time.

ProcessHungarian method
  1. 1Row reduction

    Subtract the row minimum

  2. 2Column reduction

    Subtract the column minimum

  3. 3Cover all zeros with minimum lines
  4. 4Lines = n?

    Make the optimal assignment

  5. 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

  1. Q1.What is a balanced transportation problem?
  2. Q2.Name three methods of finding an initial solution.
  3. Q3.What is degeneracy?
  4. Q4.What is the MODI method?
  5. Q5.How is a maximisation assignment problem solved?

Long-answer questions

  1. Q1.Find the initial solution of a transportation problem by NWCR, LCM and VAM and compare costs.
  2. Q2.Test the optimality of a transportation solution using MODI.
  3. 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.

WhatsApp us