Transportation Problem

The Transportation Problem — also called the Hitchcock Problem or Hitchcock-Koopmans Problem — is the classical linear programming (LP) problem of allocating weekly shipments between m sources (plants, warehouses) and n destinations (customers, distribution points). Each source has fixed capacity (s_i), each destination has fixed demand (d_j), and each source-destination pair has a per-unit transport cost (c_ij); the decision variable x_ij ≥ 0 (quantity from source i to destination j) minimises total freight cost. Balanced when total supply equals total demand; unbalanced cases are resolved by adding a dummy source or destination. Founded by Hitchcock (1941) and Koopmans (1947); Dantzig (1951) developed the Simplex method on this very problem. The Assignment Problem is a special case (equal source-destination count, capacity = demand = 1). Modern LP solvers handle thousands of source-destination pairs in seconds; dual variables (shadow prices) are direct input for marginal capacity decisions.