Transportation and assignment problems

Why it matters

Shipping castings from three foundries to four assembly plants, or giving five jobs to five machines, are everyday planning decisions where the cheapest plan is far from obvious. Transportation and assignment models solve these special linear programs quickly by hand or in software, and they are a reliable source of short numerical questions.

Key ideas

• Transportation problem. m sources with supplies aᵢ, n destinations with demands bⱼ, and a unit shipping cost cᵢⱼ on each route. Find shipments xᵢⱼ ≥ 0 that meet every supply and demand at minimum total cost. It is an LP with m + n constraints, but only m + n − 1 of them are independent (one is implied by the others when totals balance).
• Balanced vs unbalanced. The methods need Σaᵢ = Σbⱼ. If supply exceeds demand, add a dummy destination that takes the excess; if demand exceeds supply, add a dummy source. Dummy costs are zero (or a penalty for unmet demand if given).
• Basic feasible solution. A non-degenerate solution has exactly m + n − 1 occupied (basic) cells, and they contain no closed loop. Fewer occupied cells means degeneracy; place a tiny allocation ε in a suitable empty independent cell so that u and v can be computed.
• Initial solution methods.
  • North-west corner (NWC) — allocate as much as possible starting from the top-left cell, moving right or down. Fast, ignores cost, so usually far from optimum.
  • Least cost method (LCM) — allocate to the cheapest remaining cell first.
  • Vogel's approximation method (VAM) — for each row and column compute a penalty = second-lowest cost − lowest cost; allocate to the cheapest cell of the row/column with the largest penalty. It usually gives the best start, often the optimum.
• Optimality test (MODI / u–v method). For occupied cells set cᵢⱼ = uᵢ + vⱼ (start with one uᵢ = 0). For each empty cell compute the opportunity cost dᵢⱼ = cᵢⱼ − (uᵢ + vⱼ). If every dᵢⱼ ≥ 0 the solution is optimal (for minimisation); a zero dᵢⱼ means an alternative optimum. If some dᵢⱼ < 0, bring the most negative cell into the solution through a closed loop (+, −, +, − at corners), shifting the smallest quantity at a "−" corner. The stepping-stone method evaluates the same loops directly.
• Assignment problem. n jobs to n machines (one each), cost cᵢⱼ. It is a transportation problem with all supplies and demands equal to 1, so it is highly degenerate; the Hungarian method solves it efficiently.
• Hungarian method. Subtract each row's minimum from that row, then each column's minimum from that column. Cover all zeros with the minimum number of horizontal and vertical lines. If the number of lines equals n, an optimal assignment exists among the zeros. If not, subtract the smallest uncovered element from all uncovered elements, add it to elements at line intersections, and repeat.
• Variants. Unequal jobs and machines → add dummy rows or columns of zeros. Maximisation (profit) → subtract every entry from the largest entry (or negate) and minimise. A prohibited assignment → give that cell a very large cost M.

Formulas

• Transportation objective: Min Z = Σᵢ Σⱼ cᵢⱼ·xᵢⱼ
• Supply constraints: Σⱼ xᵢⱼ = aᵢ for i = 1 … m; demand constraints: Σᵢ xᵢⱼ = bⱼ for j = 1 … n; xᵢⱼ ≥ 0
  • cᵢⱼ = cost per unit from source i to destination j (₹/unit); xᵢⱼ = units shipped; aᵢ = supply at i (units); bⱼ = demand at j (units).
• Balance condition: Σ aᵢ = Σ bⱼ
• Number of basic (occupied) cells in a non-degenerate solution: m + n − 1
• MODI for occupied cells: uᵢ + vⱼ = cᵢⱼ
• Opportunity cost of an empty cell: dᵢⱼ = cᵢⱼ − (uᵢ + vⱼ); optimal for minimisation when all dᵢⱼ ≥ 0.
• Assignment: Min Z = Σᵢ Σⱼ cᵢⱼ·xᵢⱼ, with Σⱼ xᵢⱼ = 1, Σᵢ xᵢⱼ = 1, xᵢⱼ ∈ {0, 1}.

Worked examples

Example 1 (standard): NWC, VAM and MODI test Costs in ₹/unit (rows S1–S3, columns D1–D3): S1: 6, 4, 1; S2: 3, 8, 7; S3: 4, 4, 2. Supplies 50, 40, 60 units; demands 20, 95, 35 units.

1. Balance: supply 150 = demand 150 → balanced. Basic cells needed: 3 + 3 − 1 = 5.
2. NWC: S1–D1 20, S1–D2 30, S2–D2 40, S3–D2 25, S3–D3 35. Cost = 20(6) + 30(4) + 40(8) + 25(4) + 35(2) = 120 + 120 + 320 + 100 + 70 = ₹730.
3. VAM, round 1: row penalties S1 = 4 − 1 = 3, S2 = 7 − 3 = 4, S3 = 4 − 2 = 2; column penalties D1 = 4 − 3 = 1, D2 = 4 − 4 = 0, D3 = 2 − 1 = 1. Largest is S2 (4) → cheapest cell S2–D1 (₹3): allocate 20. D1 is satisfied.
4. Round 2 (D2, D3 left): row penalties S1 = 4 − 1 = 3, S2 = 8 − 7 = 1, S3 = 4 − 2 = 2; columns D2 = 0, D3 = 2 − 1 = 1. Largest is S1 → cell S1–D3 (₹1): allocate 35. D3 is satisfied.
5. Only D2 is left: S1–D2 15, S2–D2 20, S3–D2 60.
6. VAM cost = 20(3) + 35(1) + 15(4) + 20(8) + 60(4) = 60 + 35 + 60 + 160 + 240 = ₹555. Occupied cells = 5 = m + n − 1.
7. MODI: set u₁ = 0. S1–D2: v₂ = 4; S1–D3: v₃ = 1; S2–D2: u₂ = 8 − 4 = 4; S2–D1: v₁ = 3 − 4 = −1; S3–D2: u₃ = 4 − 4 = 0.
8. Empty cells: d₁₁ = 6 − (0 − 1) = 7; d₂₃ = 7 − (4 + 1) = 2; d₃₁ = 4 − (0 − 1) = 5; d₃₃ = 2 − (0 + 1) = 1. All positive. Answer: VAM solution is optimal and unique; minimum cost ₹555 (NWC start was ₹730).

Example 2 (GATE level): Hungarian method Four jobs A–D, four machines 1–4, cost in ₹: A: 10, 19, 8, 15; B: 10, 18, 7, 17; C: 13, 16, 9, 14; D: 12, 19, 8, 18.

1. Row minima 8, 7, 9, 8. Row-reduced: A: 2, 11, 0, 7; B: 3, 11, 0, 10; C: 4, 7, 0, 5; D: 4, 11, 0, 10.
2. Column minima 2, 7, 0, 5. Reduced: A: 0, 4, 0, 2; B: 1, 4, 0, 5; C: 2, 0, 0, 0; D: 2, 4, 0, 5.
3. Minimum lines covering all zeros: row A, row C, column 3 → 3 lines < 4.
4. Smallest uncovered element = 1. Subtract from uncovered, add to intersections: A: 0, 4, 1, 2; B: 0, 3, 0, 4; C: 2, 0, 1, 0; D: 1, 3, 0, 4.
5. Lines: column 1, column 3, row C → 3 lines. Smallest uncovered = 2. Result: A: 0, 2, 1, 0; B: 0, 1, 0, 2; C: 4, 0, 3, 0; D: 1, 1, 0, 2.
6. Now 4 lines are needed. Assign: D has a single zero → D–3; then B–1; then A–4; then C–2.
7. Cost = A4 + B1 + C2 + D3 = 15 + 10 + 16 + 8 = 49. Answer: A→4, B→1, C→2, D→3; minimum total cost ₹49.

Common mistakes

• Applying NWC, VAM or MODI to an unbalanced table without first adding a dummy row or column.
• Computing VAM penalties as lowest minus highest, or not recomputing them after a row or column is removed.
• Missing degeneracy: with fewer than m + n − 1 occupied cells the u–v equations cannot all be solved.
• Using the sign rule backwards: for minimisation, a negative dᵢⱼ means improvement is possible.
• In the Hungarian method, covering zeros with more lines than needed, or adding the minimum to uncovered elements instead of intersections.
• Forgetting to convert a profit-maximisation assignment into a regret (opportunity-loss) matrix.

For GATE ME

Expect: initial cost by NWC, LCM or VAM from a small table; the number of basic variables (m + n − 1) and degeneracy; checking optimality with u–v and finding the opportunity cost of a given empty cell; balancing with dummies; and 3×3 or 4×4 assignment problems solved by the Hungarian method, including maximisation and prohibited cells. Practise writing allocations neatly and checking that row and column totals match.

Quick check

1. How many occupied cells does a non-degenerate basic solution of a 4 × 5 transportation problem have?
2. Total supply is 500 units and total demand is 450 units. What do you add?
3. In MODI, what does dᵢⱼ = 0 for an empty cell at the optimum indicate?
4. How do you solve an assignment problem where profits must be maximised?
5. Why is the assignment problem always degenerate when treated as a transportation problem?

Answers: 1. 4 + 5 − 1 = 8. 2. A dummy destination with demand 50 units and zero cost. 3. An alternative optimal solution. 4. Subtract every entry from the largest entry (or negate) and minimise. 5. It has only n positive allocations but needs 2n − 1 basic cells.