Transportation problem

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

This is the finite discrete optimal transport problem with prescribed supply and demand marginals.

When factory $i$ incurs unit production cost $p_i$ only on goods actually shipped, add that cost to every real shipping destination in its row. Unused capacity incurs no production cost; a dummy unused-capacity column therefore keeps zero cost rather than receiving $p_i$. This changes the optimal factory utilization when capacity exceeds total demand. Transportation dual certificate with capacity inequalities proves optimality without assuming every factory must produce at full capacity.

Row and column potentials satisfying the displayed inequalities give a lower bound on the cost of every feasible shipment matrix: ${\sum }_{ij}{c}_{ij}{x}_{ij}\ge {\sum }_i{u}_i{s}_i+{\sum }_j{v}_j{d}_j$, since row sums are supplies $s_i$ and column sums are demands $d_j$. The reduced costs are $c_{ij}-u_i-v_j$. A feasible matrix using only zero-reduced-cost cells attains the lower bound, proving optimality by weak duality. The transportation simplex algorithm sets these potentials by equality on a transportation spanning tree, and enters a negative-reduced-cost cell if one exists.

For shipments $x_{ij}\ge 0$ with factory row sums at most capacities $s_i$ and shop column sums exactly demands $d_j$, the displayed dual potentials give $\sum c_{ij}{x}_{ij}\ge {\sum }_i{u}_i{s}_i+{\sum }_j{v}_j{d}_j$. The sign $u_i\le 0$ ensures $u_i{\sum }_j{x}_{ij}\ge u_i{s}_i$. Equality proves optimality. It occurs when every used cell is tight and every row with spare capacity has $u_i=0$, the relevant complementary slackness conditions. A dummy demand column with zero costs converts unused capacity into a balanced transportation problem.

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.

For a partial assignment problem, add its fixed cost to the sum, over remaining tasks, of each task's cheapest available machine cost. This is a lower bound because it relaxes the requirement that different tasks use distinct machines. It is an admissible bound for branch and bound, even though the minimizing choices may assign the same machine repeatedly.

// Target: mathematical-optimization.bigb

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 of nonnegative rational numbers with integer row and column sums can be rounded entrywise up or down while preserving all those sums. Let $p_{ij}=\lfloor a_{ij}\rfloor$ and $f_{ij}=a_{ij}-p_{ij}$ be its floor and fractional part. The residual row and column sums $r_i={\sum }_j{f}_{ij}$ and $c_j={\sum }_i{f}_{ij}$ are nonnegative integers. Build a flow network with source-to-row flow network edge capacities $r_i$, row-to-column flow network edge capacities one where $f_{ij}>0$, and column-to-sink flow network edge capacities $c_j$. The fractional parts supply a feasible flow saturating all source arcs. The integral max-flow theorem supplies an integral one of the same total value. If its middle-arc flows are $h_{ij}\in \{0,1\}$, with $h_{ij}=0$ where $f_{ij}=0$, then $b_{ij}=p_{ij}+h_{ij}$ is the required matrix. This is a constructive polynomial-time algorithm; no multiplication by a common denominator is required.

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.

A matrix with entries in $\{0,1,-1\}$ is a totally unimodular matrix if every column has at most two nonzero entries, with opposite signs when both occur. To prove this, induct on the size of a square submatrix. A zero column gives determinant zero, a one-entry column reduces by cofactor expansion, and if every column has two entries then all column sums vanish, giving dependent rows. The total unimodularity of directed incidence matrices is a central instance.

The directed vertex-edge incidence matrix has one $+1$ and one $-1$ per nonloop column and a zero column for a loop. Every square subdeterminant belongs to $\{0,1,-1\}$. Induct on its size: a column with no nonzero entries makes the determinant zero; a column with one nonzero entry permits a cofactor expansion to a smaller determinant; and if every column has two nonzero entries, their opposite signs make the column sums zero, giving linearly dependent rows. Negating rows preserves absolute subdeterminants. Consequently the unsigned vertex-edge incidence matrix of a bipartite graph is totally unimodular: negate all rows in one part. The assignment problem is an instance, with row vertices and column vertices forming the two parts.