Transportation Problem Calculator (Northwest, Min-Cost & MODI)

Calculate Initial Basic Feasible Solutions using Northwest Corner or Minimum Cost methods, and optimize distribution networks with the MODI potential algorithm.

3
3
D1D2D3Supply
S1
S2
S3
Demand
Supply Chain & Network Flow Optimization

The Transportation Problem: Northwest Corner, Minimum Cost & MODI Methods

A comprehensive academic guide to modeling distribution networks, finding initial basic feasible solutions, and optimizing to global minima with the MODI (u-v) algorithm.

1. What Problem Does the Transportation Model Solve?

The Transportation Problem is a specialized branch of Linear Programming formulated to determine the most cost-effective shipping schedule between m supply origins (factories, warehouses) with known capacities, and n demand destinations (markets, retail stores) with required quantities. When total supply equals total demand (∑ sᵢ = ∑ dⱼ), the model is balanced. The mathematical objective is to minimize total distribution cost Z = ∑∑ cᵢⱼ xᵢⱼ subject to supply and demand conservation constraints.

2. Solution Methodology: From Initial Feasibility to Optimality

Initial Basic Feasible Solution (IBFS)
Northwest Corner Method (NWC)

A geometric allocation starting at top-left cell (1, 1). It allocates min(s₁, d₁), exhausts a row or column, and steps systematically right or down. It ignores unit transport costs, producing an initial feasible baseline quickly but rarely an optimal one.

Initial Basic Feasible Solution (IBFS)
Minimum Cost Method (Least Cost)

A greedy heuristic that prioritizes allocating the maximum possible quantity to the unused route with the lowest unit shipping cost cᵢⱼ. By focusing on economical routes first, it frequently yields an initial cost significantly closer to the true optimum.

Exact Optimality Algorithm
MODI Method (Modified Distribution / u-v)

The dual simplex counterpart for network graphs. Using the condition uᵢ + vⱼ = cᵢⱼ for all basic (allocated) cells, it computes shadow prices uᵢ and vⱼ. It then calculates the opportunity cost (evaluation index) Δᵢⱼ = cᵢⱼ - (uᵢ + vⱼ) for every empty cell. If all Δᵢⱼ ≥ 0, the solution is proven globally optimal. If any Δᵢⱼ < 0, a closed stepping-stone loop reallocates units along an alternating +/- cycle.

3. Solved Academic Example: 3 Origins × 3 Destinations

Compare initial methods and observe exact optimality verification matching our engine.

Supply: Origins S₁, S₂, S₃ have capacities of 100, 300, and 300 units.
Demand: Destinations D₁, D₂, D₃ require 300, 200, and 200 units.
Total Supply = 700 units | Total Demand = 700 units (Perfectly Balanced).
Origin / DestinationDestination 1 (D₁)Destination 2 (D₂)Destination 3 (D₃)Supply Capacity
Origin 1 (S₁)$8$4$12100
Origin 2 (S₂)$10$5$6300
Origin 3 (S₃)$7$8$15300
Demand Requirement300200200700

A. Northwest Corner Method Walkthrough

Start at (S₁, D₁): allocate min(100, 300) = 100. S₁ is empty. Move down to (S₂, D₁): allocate min(300, 200) = 200. D₁ is satisfied. Move right to (S₂, D₂): allocate min(100, 200) = 100. S₂ is empty. Move down to (S₃, D₂): allocate min(300, 100) = 100. D₂ is satisfied. Move right to (S₃, D₃): allocate remaining min(200, 200) = 200.

Total NWC Cost = (100 × $8) + (200 × $10) + (100 × $5) + (100 × $8) + (200 × $15) = $800 + $2,000 + $500 + $800 + $3,000 = $7,100.

B. Minimum Cost Method Walkthrough

1. Global lowest cost is cell (S₁, D₂) with cost $4: allocate min(100, 200) = 100. S₁ is exhausted. 2. Next lowest available cost is cell (S₂, D₂) with cost $5: allocate min(300, 100 remaining) = 100. D₂ is satisfied. 3. Next is cell (S₂, D₃) with cost $6: allocate min(200 remaining, 200) = 200. S₂ and D₃ are satisfied. 4. Finally, cell (S₃, D₁) with cost $7: allocate min(300, 300) = 300. S₃ and D₁ are satisfied.

Total Minimum Cost = (100 × $4) + (100 × $5) + (200 × $6) + (300 × $7) = $400 + $500 + $1,200 + $2,100 = $4,200.

C. MODI Optimality Verification

For the basic cells (S₁, D₂), (S₂, D₂), (S₂, D₃), and (S₃, D₁), setting u₂ = 0 gives v₂ = 5, v₃ = 6, u₁ = -1, and solving dual equations yields all opportunity costs Δᵢⱼ = cᵢⱼ - (uᵢ + vⱼ) ≥ 0. No negative evaluation index exists; therefore, the Minimum Cost allocation is already the exact global optimum.

Global Optimal Minimum Cost = $4,200 (Identical to calculator engine output).

Efficiency Analysis: $2,900 in Savings

By choosing the cost-conscious Minimum Cost heuristic over the naive Northwest Corner rule, shipping costs drop immediately from $7,100 to $4,200—saving $2,900 (a 40.8% reduction) before even requiring stepping-stone iterations.

4. Common Student & Academic Pitfalls

⚠

Overlooking Network Imbalance

If total supply exceeds demand, a dummy destination with zero transportation cost must be added to absorb excess supply. Conversely, if demand exceeds supply, create a dummy source.

⚠

Degeneracy in Basis (Fewer than m + n - 1 Allocations)

A basic solution requires exactly m + n - 1 occupied cells (here, 3 + 3 - 1 = 5). If simultaneous row and column exhaustion leaves fewer basic cells, an infinitesimal ε must be assigned to an independent cell to permit computing uᵢ and vⱼ dual multipliers.

⚠

Constructing Invalid Closed Loops in MODI

The closed stepping-stone loop must only turn at basic (allocated) cells at 90-degree right angles. Turning at empty cells will invalidate the simplex pivot.