Transportation problem

Transportation problem: modeling, initial feasible solutions (NWC, LCM, VAM), optimality tests (MODI/u–v, stepping-stone), degeneracy, unbalanced cases, special cases (assignment, transshipment), and practical limitations.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Transportation problems decide how much to ship from each source (plant/warehouse) to each destination (market) to meet demand at minimum cost. Good formulations reduce logistics spend, improve service levels, and are a base for more advanced models like supply chain network design.

Key ideas

  • A transportation problem is a special linear program that moves a single homogeneous commodity from m sources to n destinations at minimum total cost.
  • Balanced problem: total supply equals total demand. If not, add a dummy source/destination so totals match. Dummy arcs usually have zero cost; they model surplus/shortage without affecting real shipments.
  • Decision variable xᵢⱼ: quantity shipped from source i to destination j (SI unit: kg or Mg; 1 Mg = 10³ kg). Nonnegative and divisible under the linear model.
  • Cost coefficient cᵢⱼ: cost per unit shipped from i to j (e.g., ₹/Mg). The objective is to minimize Σ cᵢⱼ xᵢⱼ.
  • Supply sᵢ and demand dⱼ: available units at source i and required units at destination j (SI unit: kg or Mg). Constraints enforce Σⱼ xᵢⱼ = sᵢ and Σᵢ xᵢⱼ = dⱼ in the balanced case.
  • Assumptions of the classical model:
    • Linear and separable shipping costs (no fixed charges, no quantity discounts, cost per unit independent of volume on that route).
    • Single commodity, perfectly divisible shipments, deterministic sᵢ, dⱼ, and cᵢⱼ.
    • No capacity limits on individual arcs beyond supplies/demands; no time windows; shipments instantaneous or time ignored.
    • Each unit shipped from i to j incurs the same cᵢⱼ regardless of others.
  • Feasibility and balance: Feasible solutions exist only if every destination is reachable via at least one allowed route from the set of sources, each source has at least one allowed outgoing route (or to a dummy, if added), and if (after adding dummy as needed) Σ sᵢ = Σ dⱼ.
  • Prohibited routes: If shipping i→j is impossible, set cᵢⱼ to a very large number M (big-M) or mark the cell as forbidden so algorithms will not allocate there. Prefer explicit forbidding to avoid numerical issues with big-M.
  • Basic feasible solution (BFS): In a non-degenerate BFS of an m×n transportation problem, the number of positive basic allocations is exactly m + n − 1. Degenerate BFSs have fewer than m + n − 1 positive allocations; we preserve the basis by placing a tiny ε (conceptual zero) in an empty independent cell.
  • Theorem (structure of BFS): Because the m + n constraints have rank m + n − 1 (one is redundant in the balanced case), any BFS has at most m + n − 1 basic variables; a non-degenerate BFS has exactly m + n − 1.
  • Initial BFS methods:
    • Northwest Corner Rule (NWC): ignore costs; fill from top-left, proceed right/down as rows/columns exhaust. Fast but often high cost.
    • Least Cost Method (LCM): repeatedly allocate to the lowest-cost available cell. Usually better than NWC.
    • Vogel’s Approximation Method (VAM): compute row/column penalties (difference between two least costs), pick the largest penalty, and allocate to the least-cost cell in that row/column. Often yields near-optimal starts.
  • Optimality tests and improvement:
    • MODI (u–v) method / Potential method: Assign potentials uᵢ (rows) and vⱼ (columns) so that uᵢ + vⱼ = cᵢⱼ for all basic cells. For a non-basic cell, the reduced cost Δᵢⱼ = cᵢⱼ − uᵢ − vⱼ. If all Δᵢⱼ ≥ 0 (for minimization), the current BFS is optimal. If some Δᵢⱼ < 0, choose the most negative, form a closed loop of alternating +/− cells through basic allocations, and adjust shipments along the loop to reduce total cost. Set the adjustment magnitude θ to the minimum shipment on the “−” positions of the loop; add θ to all “+” cells and subtract θ from all “−” cells. The basic variable that attains this minimum on a “−” cell leaves the basis; if there is a tie, degeneracy occurs—retain feasibility with an ε in one independent cell.
    • Stepping-stone method: Equivalent to MODI but computes net cost change by tracing loops directly from a candidate non-basic cell; if the per-unit net change is negative, adjust by θ as above.
    • Outline derivation of MODI from duality: The primal is min Σ cᵢⱼ xᵢⱼ s.t. Σⱼ xᵢⱼ = sᵢ and Σᵢ xᵢⱼ = dⱼ, xᵢⱼ ≥ 0. The dual is max Σ sᵢ uᵢ + Σ dⱼ vⱼ s.t. uᵢ + vⱼ ≤ cᵢⱼ. Complementary slackness gives: for basic xᵢⱼ > 0, uᵢ + vⱼ = cᵢⱼ; for non-basics, uᵢ + vⱼ ≤ cᵢⱼ, which yields Δᵢⱼ ≥ 0 at optimality.
  • Multiple optima: If some non-basic cells have Δᵢⱼ = 0 at an optimal solution, alternative optima exist along loops containing those cells.
  • Integrality: With integer supplies and demands, the transportation constraints are totally unimodular, so there exists an optimal solution with all xᵢⱼ integral without explicitly enforcing integrality.
  • Sign conventions:
    • Standard formulation is a minimization. For a maximization (e.g., profit per unit), convert to minimization by cᵢⱼ = −profitᵢⱼ or pose the dual appropriately.
    • In network-flow form, treat source node supplies as positive bᵢ and destination node demands as negative bⱼ; flow conservation uses Σ outflow − Σ inflow = bₖ.
  • Standard cases:
    • Balanced vs unbalanced (use dummy to balance).
    • Degenerate BFS (use ε allocations to maintain m + n − 1 basics and allow loops).
    • Prohibited routes (forbid or big-M).
    • Special cases: Assignment problem (sᵢ = dⱼ = 1; make the matrix square by adding a dummy row/column if needed); Transshipment (allow intermediate nodes; convert to expanded transportation network with node balances).
  • Why real systems differ from the ideal: Costs are often nonlinear (fixed vehicle cost plus per-km variable), capacity/time-window constraints matter, multiple modes and commodities exist, lead times and uncertainties (stochastic demands, disruptions) arise, and emissions or service-level penalties can alter objective terms. These require extensions like fixed-charge transportation, multi-commodity flow, time-indexed models, or stochastic programming.

Formulas

Z = Σᵢ Σⱼ cᵢⱼ · xᵢⱼ Z is total cost (₹). cᵢⱼ is cost per unit from i to j (₹/Mg). xᵢⱼ is shipped quantity (Mg). Applies to classical linear transportation objective.

Σⱼ xᵢⱼ = sᵢ for all i = 1…m Row (supply) constraints. xᵢⱼ (Mg), sᵢ (Mg). Applies in balanced/unbalanced problems with dummy added as needed.

Σᵢ xᵢⱼ = dⱼ for all j = 1…n Column (demand) constraints. xᵢⱼ (Mg), dⱼ (Mg). Applies in balanced/unbalanced problems with dummy added as needed.

Σᵢ sᵢ = Σⱼ dⱼ Balance condition (Mg). If not satisfied, add a dummy source/destination to enforce it.

xᵢⱼ ≥ 0 Non-negativity. xᵢⱼ is shipment (Mg). Applies always in classical model.

Number of basic variables in a non-degenerate BFS = m + n − 1 Count property of transportation BFSs. Applies to connected, balanced problems; fewer basics implies degeneracy.

uᵢ + vⱼ = cᵢⱼ for all basic cells (i, j) MODI potentials. uᵢ, vⱼ are dual potentials (₹/Mg). Applies when computing Δᵢⱼ.

Δᵢⱼ = cᵢⱼ − uᵢ − vⱼ Reduced cost (₹/Mg) of non-basic cell (i, j). If all Δᵢⱼ ≥ 0 (minimization), the solution is optimal.

Net cost change around a closed loop = Σ(“+” cells cᵢⱼ) − Σ(“−” cells cᵢⱼ) Stepping-stone loop evaluation (₹/Mg). Applies for candidate entering cells; improve if negative.

θ = min{ current allocations on all “−” cells in the chosen improvement loop } Step size for MODI/stepping-stone adjustment (Mg). Add θ to “+” cells and subtract θ from “−” cells; the “−” cell attaining θ leaves the basis (ties → degeneracy; handle with ε).

Worked examples

Example 1 — Balanced TP; VAM start and MODI optimality Given:

  • Sources S1=20 Mg, S2=30 Mg, S3=25 Mg; Destinations D1=10 Mg, D2=35 Mg, D3=30 Mg (balanced: 75 Mg each).
  • Costs cᵢⱼ (₹/Mg):
    • S1→[D1=8, D2=6, D3=10]
    • S2→[D1=9, D2=12, D3=13]
    • S3→[D1=14, D2=9, D3=16] Task: Find a good initial solution using VAM, then test optimality by MODI.

Step 1: Initial BFS by VAM (sketch of allocations; penalties computed as differences of two least costs per row/column).

  • Allocation sequence (after computing penalties and choosing largest): x₃₂=25 Mg, x₁₂=10 Mg, x₂₁=10 Mg, x₁₃=10 Mg, x₂₃=20 Mg. This yields m + n − 1 = 5 basic allocations (non-degenerate).

Step 2: Compute total cost Z.

  • Formula: Z = Σ cᵢⱼ · xᵢⱼ.
  • Numbers with units:
    • S3→D2: 9 ₹/Mg × 25 Mg = 225 ₹
    • S1→D2: 6 ₹/Mg × 10 Mg = 60 ₹
    • S2→D1: 9 ₹/Mg × 10 Mg = 90 ₹
    • S1→D3: 10 ₹/Mg × 10 Mg = 100 ₹
    • S2→D3: 13 ₹/Mg × 20 Mg = 260 ₹
  • Sum: 225 + 60 + 90 + 100 + 260 = 735 ₹.

Step 3: MODI optimality test.

  • Set u₁ = 0 (arbitrary). For basics, uᵢ + vⱼ = cᵢⱼ:
    • (1,2): 0 + v₂ = 6 ⇒ v₂ = 6
    • (1,3): 0 + v₃ = 10 ⇒ v₃ = 10
    • (2,1): u₂ + v₁ = 9 (hold)
    • (2,3): u₂ + 10 = 13 ⇒ u₂ = 3 ⇒ v₁ = 9 − u₂ = 6
    • (3,2): u₃ + 6 = 9 ⇒ u₃ = 3
  • Reduced costs Δᵢⱼ = cᵢⱼ − uᵢ − vⱼ for non-basics:
    • (1,1): 8 − 0 − 6 = +2 ≥ 0
    • (2,2): 12 − 3 − 6 = +3 ≥ 0
    • (3,1): 14 − 3 − 6 = +5 ≥ 0
    • (3,3): 16 − 3 − 10 = +3 ≥ 0
  • All Δᵢⱼ ≥ 0 ⇒ current plan is optimal.

Answer: Optimal shipping cost is 735 ₹.

Example 2 — Unbalanced, prohibited route, dummy destination; VAM/LCM to BFS; MODI optimality Given:

  • Sources: S1=30 Mg, S2=25 Mg, S3=35 Mg (total 90 Mg).
  • Destinations: D1=40 Mg, D2=20 Mg (total 60 Mg). Add dummy D3=30 Mg to balance supply.
  • Costs cᵢⱼ (₹/Mg):
    • S1→[D1=4, D2=6, D3=0]
    • S2→[D1=prohibited, D2=3, D3=0]
    • S3→[D1=5, D2=4, D3=0] Task: Find an optimal plan. Treat prohibited S2→D1 as forbidden (do not allocate there).

Step 1: Construct a feasible BFS (guided by costs and feasibility).

  • Prefer cheap feasible allocations while keeping D1 reachable (since S2→D1 is forbidden):
    1. Allocate S2→D2: min(25 Mg, 20 Mg) = 20 Mg ⇒ x₂₂ = 20 Mg; S2 left 5 Mg; D2 satisfied.
    2. Allocate S2→D3: min(5 Mg, 30 Mg) = 5 Mg ⇒ x₂₃ = 5 Mg; S2 satisfied; D3 left 25 Mg.
    3. Allocate S1→D1: min(30 Mg, 40 Mg) = 30 Mg ⇒ x₁₁ = 30 Mg; S1 satisfied; D1 left 10 Mg.
    4. Allocate S3→D1: min(35 Mg, 10 Mg) = 10 Mg ⇒ x₃₁ = 10 Mg; S3 left 25 Mg; D1 satisfied.
    5. Allocate S3→D3: remaining 25 Mg ⇒ x₃₃ = 25 Mg; S3 satisfied; D3 satisfied.
  • Basics: x₂₂, x₂₃, x₁₁, x₃₁, x₃₃ (5 basics = m + n − 1 for 3×3).

Step 2: Compute total cost Z.

  • Formula: Z = Σ cᵢⱼ · xᵢⱼ.
  • Numbers with units:
    • S2→D2: 3 ₹/Mg × 20 Mg = 60 ₹
    • S2→D3: 0 ₹/Mg × 5 Mg = 0 ₹
    • S1→D1: 4 ₹/Mg × 30 Mg = 120 ₹
    • S3→D1: 5 ₹/Mg × 10 Mg = 50 ₹
    • S3→D3: 0 ₹/Mg × 25 Mg = 0 ₹
  • Sum: 60 + 0 + 120 + 50 + 0 = 230 ₹.

Step 3: MODI optimality test.

  • Set u₁ = 0. For basics, uᵢ + vⱼ = cᵢⱼ:
    • (1,1): 0 + v₁ = 4 ⇒ v₁ = 4
    • (2,2): u₂ + v₂ = 3 (hold)
    • (2,3): u₂ + v₃ = 0 (hold)
    • (3,1): u₃ + 4 = 5 ⇒ u₃ = 1
    • (3,3): 1 + v₃ = 0 ⇒ v₃ = −1 ⇒ from (2,3): u₂ = 1 ⇒ from (2,2): v₂ = 2
  • Reduced costs for non-basics:
    • (1,2): 6 − 0 − 2 = +4 ≥ 0
    • (1,3): 0 − 0 − (−1) = +1 ≥ 0
    • (3,2): 4 − 1 − 2 = +1 ≥ 0
    • (2,1): forbidden (ignored in optimality scan)
  • All Δᵢⱼ ≥ 0 ⇒ optimal.

Answer: Optimal shipping cost is 230 ₹.

Notes on degeneracy handling (general): If after constructing a BFS you have fewer than m + n − 1 basic allocations (e.g., because an allocation exhausts a row and a column simultaneously), place a zero (ε) allocation in one independent empty cell to restore the count and allow loop formation. ε is conceptual; it carries no shipment or cost.

Common mistakes

  • Forgetting to balance the problem with a dummy row/column when Σ sᵢ ≠ Σ dⱼ, leading to infeasible constraints in the tableau.
  • Using big-M for prohibited routes and then accidentally allocating to those cells because M wasn’t large enough; safer to mark the cell forbidden.
  • Losing the count of basics: having more or fewer than m + n − 1 in a supposed non-degenerate BFS; not adding an ε in a degenerate case, which prevents forming a valid loop.
  • In MODI, assigning uᵢ, vⱼ inconsistently (e.g., using a non-basic equality), or computing Δᵢⱼ with the wrong sign convention (for minimization, need Δᵢⱼ ≥ 0 at optimum).
  • Loop construction errors: not alternating +/− signs correctly or not forming a closed orthogonal loop through basic cells.
  • Ignoring units: mixing kg and Mg, or forgetting that cᵢⱼ is per unit, so total cost is cᵢⱼ × xᵢⱼ.
  • Treating assignment problems as general TPs without noting that sᵢ = dⱼ = 1 (leading to overcomplication).

For GATE ME

  • Quick initial solution by NWC/LCM/VAM and one iteration of MODI to check optimality or to improve cost.
  • Spotting balanced vs unbalanced; adding an appropriate dummy and interpreting dummy shipments.
  • Degeneracy: recognizing when it occurs and inserting ε at the correct independent cell; then proceeding with MODI.
  • Identifying multiple optimal solutions via zero reduced costs.
  • Handling prohibited routes and verifying feasibility (e.g., ensuring each demand has at least one allowed incoming route and each source has at least one allowed outgoing route or dummy).
  • Small numerical examples with 3×3 or 3×4 tables, computing u–v potentials and Δᵢⱼ efficiently.
  • Conceptual questions on the dual, complementary slackness, and why integer inputs yield integer solutions.

Practise:

  • Derive MODI potentials fast: pick u₁ = 0, propagate uᵢ, vⱼ across basics, then compute all Δᵢⱼ in a table.
  • Construct closed loops systematically: from entering cell, move horizontally/vertically to a basic, alternate directions, ensure closure; choose θ as the minimum on the “−” cells and update.
  • Try a few VAM starts and compare with LCM to build intuition about near-optimal starts.

Quick check

  1. In a 4×3 balanced transportation problem, how many basic variables must a non-degenerate BFS have?
  2. In MODI for minimization, what condition on Δᵢⱼ guarantees optimality?
  3. When total supply exceeds total demand by Q, what do you add and with what cost entries?

Answers: 1) 6 (since m + n − 1 = 4 + 3 − 1), 2) All Δᵢⱼ ≥ 0 for non-basic cells, 3) Add a dummy destination with demand Q and usually zero costs from all sources.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?