Integrality of the transportation problem Created 2026-09-24 Updated 2026-11-05
For nonnegative integer supplies and demands 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 or . 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.
Use the transportation simplex algorithm, with transportation dual potentials and reduced costs . On a basic cell choose . The initial shipment matrix, read from the circled entries in the PDF, is
Its six positive cells form a transportation spanning tree. Setting gives
Enter cell , whose reduced cost is . The cycle pivot has signs
The maximum feasible increment is , so cell leaves the basis. The result is
For the new transportation spanning tree,
Enter cell with reduced cost . Its cycle pivot is
Now , and cell leaves. We obtain
Its row sums are and its column sums , as required. The final transportation dual potentials are
All reduced costs are nonnegative, proving optimality. More explicitly, for any feasible shipment matrix ,
Our shipments use only zero-reduced-cost cells and attain this lower bound. This supplies an independent weak duality certificate for the transportation optimum.