Transportation and assignment problems

Why it matters

An automobile group ships engines from several powertrain plants to several assembly plants, and parts from many suppliers to many warehouses; the cheapest shipping plan is a transportation problem. Assigning jobs to machines, operators to stations or service bays to vehicles one-to-one is an assignment problem. Both are special linear programmes with fast hand methods, and both appear regularly in GATE as short numericals.

Key ideas

Transportation problem. m sources with supplies a_i, n destinations with demands b_j, unit shipping cost c_ij. Find shipments x_ij ≥ 0 that meet every demand without exceeding any supply at minimum total cost.

• Balanced if Σa_i = Σb_j. If not, add a dummy source or destination carrying the difference, with zero cost (or a penalty cost for unmet demand, if one is given). Then every constraint is an equation.
• A basic feasible solution has at most m + n − 1 positive allocations (one equation is redundant). If it has fewer, it is degenerate: put a tiny allocation ε in a suitable empty cell (one that does not form a closed loop with the others) so that MODI can run.

Finding an initial solution.

• North-west corner rule — start at the top-left cell, allocate as much as possible, move right if the row's supply is left over, or down if the column's demand is met. Ignores cost, so it is quick but usually far from optimal.
• Least-cost method — allocate to the cheapest remaining cell each time.
• Vogel's approximation method (VAM) — for every row and column find the penalty = difference between its two smallest costs; choose the row or column with the largest penalty and allocate to its cheapest cell; cross out the exhausted row or column and recompute penalties. VAM is usually optimal or very close.

Optimality test — MODI (u–v) method.

1. For each occupied cell, u_i + v_j = c_ij; set one u (say u₁) = 0 and solve for the rest.
2. For each empty cell, compute the opportunity cost Δ_ij = c_ij − (u_i + v_j).
3. If all Δ_ij ≥ 0, the solution is optimal (a zero Δ means an alternative optimum). If some Δ_ij < 0, bring in the most negative cell: form a closed loop of occupied cells with alternate + and − signs, shift the smallest quantity in a "−" cell around the loop, and repeat. The stepping-stone method evaluates the same loops directly.

Assignment problem. n jobs, n machines, cost c_ij of doing job i on machine j; each job to exactly one machine and each machine one job. It is a transportation problem with all supplies and demands equal to 1, so it is highly degenerate; the Hungarian method solves it directly.

1. Subtract each row's minimum from that row.
2. Subtract each column's minimum from that column.
3. Cover all zeros with the minimum number of horizontal and vertical lines.
4. If lines = n, make the assignment on zeros (start with rows or columns having a single zero). If lines < n, subtract the smallest uncovered number from all uncovered cells, add it at line intersections, and return to step 3.

• Unbalanced (more jobs than machines or the reverse): add dummy rows or columns of zeros.
• Maximisation (profit): subtract every element from the largest element, then minimise.
• Prohibited assignments: put a very large cost (M) in that cell. The travelling-salesman problem looks similar but adds the condition that the route must be a single tour, so plain Hungarian is not enough.

Formulas

Min Z = Σ_i Σ_j c_ij · x_ij

• Z = total cost (₹); c_ij = unit cost from source i to destination j (₹/unit); x_ij = quantity shipped (units).

Σ_j x_ij = a_i, Σ_i x_ij = b_j, x_ij ≥ 0

• Supply and demand constraints for a balanced problem.

Number of basic cells = m + n − 1

• m sources, n destinations; fewer positive cells → degenerate.

u_i + v_j = c_ij (occupied cells), Δ_ij = c_ij − u_i − v_j (empty cells)

• MODI dual variables and opportunity costs; optimal when all Δ_ij ≥ 0 for minimisation.

x_ij ∈ {0, 1}, Σ_j x_ij = 1, Σ_i x_ij = 1

• Assignment constraints.

Worked examples

Example 1 (standard → GATE level) — VAM and MODI. Three engine plants S1, S2, S3 supply 25, 35 and 40 engines; three assembly plants C1, C2, C3 need 30, 40 and 30. Unit costs (₹ hundred):

	C1	C2	C3	Supply
S1	8	6	10	25
S2	9	7	4	35
S3	3	4	2	40
Demand	30	40	30	100
Balanced (100 = 100). m + n − 1 = 5.

1. North-west corner for comparison: S1–C1 25, S2–C1 5, S2–C2 30, S3–C2 10, S3–C3 30. Cost = 200 + 45 + 210 + 40 + 60 = 555.
2. VAM, step 1: row penalties 2, 3, 1; column penalties C1 = 8 − 3 = 5, C2 = 2, C3 = 2. Largest is C1 → cheapest cell S3–C1 (3): allocate 30. C1 done; S3 has 10 left.
3. Step 2: row penalties S1 = 10 − 6 = 4, S2 = 3, S3 = 2; columns C2 = 2, C3 = 2. Largest S1 → S1–C2 (6): allocate 25. S1 done; C2 needs 15.
4. Step 3: S2 = 3, S3 = 2, C2 = 7 − 4 = 3, C3 = 2. Tie at 3; take S2 → S2–C3 (4): allocate 30. C3 done; S2 has 5 left.
5. Step 4: only C2 is left: S2–C2 = 5, S3–C2 = 10.
6. VAM cost = 25×6 + 5×7 + 30×4 + 30×3 + 10×4 = 150 + 35 + 120 + 90 + 40 = 435, with 5 allocations (not degenerate).
7. MODI: u₁ = 0 → v₂ = 6 (S1–C2); u₂ = 7 − 6 = 1 (S2–C2); v₃ = 4 − 1 = 3 (S2–C3); u₃ = 4 − 6 = −2 (S3–C2); v₁ = 3 − (−2) = 5 (S3–C1).
8. Empty cells: Δ₁₁ = 8 − 0 − 5 = 3; Δ₁₃ = 10 − 0 − 3 = 7; Δ₂₁ = 9 − 1 − 5 = 3; Δ₃₃ = 2 − (−2) − 3 = 1. All positive.

Answer: the VAM solution is optimal and unique; minimum cost = 435 (₹43,500), 120 less than the north-west-corner start.

Example 2 (GATE level) — Hungarian method. Four jobs on four machines, times in hours:

	M1	M2	M3	M4
J1	10	12	19	11
J2	5	10	7	8
J3	12	14	13	11
J4	8	15	11	9

1. Row minima 10, 5, 11, 8 → rows become J1 (0, 2, 9, 1), J2 (0, 5, 2, 3), J3 (1, 3, 2, 0), J4 (0, 7, 3, 1).
2. Column minima 0, 2, 2, 0 → J1 (0, 0, 7, 1), J2 (0, 3, 0, 3), J3 (1, 1, 0, 0), J4 (0, 5, 1, 1).
3. Zeros can be covered by no fewer than 4 lines (e.g. column M1, column M3, row J1, row J3) = n, so an optimal assignment exists.
4. J4 has a single zero (M1) → J4–M1. Then J2's remaining zero is M3 → J2–M3. J1 → M2. J3 → M4.
5. Total = 12 + 7 + 11 + 8 = 38 h.

Answer: J1–M2, J2–M3, J3–M4, J4–M1; minimum total time 38 h.

Common mistakes

• Forgetting to balance the problem before starting.
• Counting allocations wrongly: m + n − 1 basic cells are needed; fewer means degeneracy and MODI cannot be completed without ε.
• Computing VAM penalties as largest minus smallest instead of the difference between the two smallest costs.
• Sign errors in Δ_ij: it is c_ij − (u_i + v_j); for minimisation a negative value means improvement is possible.
• In the Hungarian method, stopping after row reduction without column reduction, or drawing more lines than needed.
• Applying Hungarian to a maximisation matrix directly.

For GATE ME

Expect north-west-corner, least-cost or VAM initial costs, the number of basic variables and degeneracy, MODI opportunity costs, and Hungarian-method minimum cost for 3×3 or 4×4 matrices, including unbalanced and maximisation versions. Practise doing the arithmetic in a neat grid; most errors are bookkeeping, not concept.

Quick check

1. A transportation problem has 4 sources and 5 destinations. How many basic variables does a non-degenerate solution have?
2. Supply 120, demand 100. What do you add?
3. Row costs 6, 9, 4, 7. What is that row's VAM penalty?
4. For an empty cell c = 5, u = 2, v = 4. Is the solution improvable through this cell?
5. How is a profit-maximising assignment problem converted for the Hungarian method?

Answers: 1. 8. 2. A dummy destination with demand 20 and zero cost. 3. 6 − 4 = 2. 4. Yes, Δ = 5 − 6 = −1 < 0. 5. Subtract every entry from the largest entry and minimise.