Integrality of the transportation problem (source code)

= Integrality of the transportation problem

For nonnegative integer supplies $s_i$ and demands $d_j$ with equal totals, the complete <transportation problem> has an integral optimal shipment matrix for every finite real cost array. A feasible matrix exists, and its nonnegative entries are bounded by their row supplies, so the <transportation polytope> is compact and a linear objective attains its minimum.

Its constraints are the vertex-edge incidence equations of a <bipartite graph>. Negating the demand rows gives a directed <incidence matrix>, which is a <totally unimodular matrix>. After deleting one redundant equality, any independent square basis has determinant $+1$ or $-1$. An integer right side therefore gives integer basic coordinates by <Cramer's rule>. The <Fundamental theorem of linear programming> supplies an optimal <basic feasible solution>, proving integrality.

There is also an algorithmic view. The <northwest corner method> starts with integer shipments; a <cycle pivot> adds and subtracts an integer minimum along its alternating cycle, preserving integrality. Zero allocations may be needed to complete a degenerate basis. With forbidden routes, equality of total supply and demand is no longer enough for feasibility, though an existing transportation feasible polytope retains the same incidence-matrix integrality property.