Transportation problem

The transportation problem minimizes linear shipping cost while matching prescribed row supplies and column demands.

The assignment problem chooses a one-to-one pairing of jobs and agents minimizing their total cost. Its minimum-cost flow formulation puts unit supplies on job vertices and unit demands on agent vertices of a bipartite graph. Integral feasible flows are perfect matchings.

The Hungarian algorithm maintains feasible assignment dual potentials and a matching of equality edges. If the alternating search cannot augment, adjust reachable job and agent potentials by the smallest reduced cost leaving the search set. This preserves feasibility and existing matching equalities while exposing a new equality edge. A resulting perfect matching attains the dual lower bound.

These feasible potentials give the lower bound ${\sum }_i{\lambda }_i-{\sum }_j{\mu }_j$ on every assignment cost. An assignment using only equality edges attains this bound and is optimal by weak duality and complementary slackness.

The transportation polytope is the set of nonnegative matrices with fixed row and column sums.

The positive cells of a nondegenerate transportation basis form a spanning tree in the bipartite graph of supply and demand vertices.

The transportation simplex computes row and column potentials, enters a negative-reduced-cost cell, and pivots around its induced alternating cycle.

The northwest-corner method repeatedly allocates the smaller remaining supply and demand in the current top-left cell to construct an initial transportation basis.

For transportation potentials, the reduced cost is ${\bar{c}}_{ij}=c_{ij}-u_i-v_j$; a negative value identifies an improving entering cell.

Adding a nonbasic edge to a transportation tree creates one cycle; alternating equal additions and subtractions around it preserves every row and column sum.

Integer supplies and demands admit an integer optimum because an integer initial basis and every cycle pivot remain integer.

A matrix is totally unimodular when every square subdeterminant is $0$, $1$, or $-1$; linear programs with such a constraint matrix and integer right side have integral vertices.