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.
Write the top row as . The bottom row is then , and nonnegativity becomes
The feasible set is a hexagon in this plane. Its six vertices, hence all basic feasible solutions of this transportation problem, are
There are four independent constraints; each displayed support consists of four cells forming a transportation spanning tree, so each is a nondegenerate basic solution. Conversely, a basic feasible solution is a vertex, so the hexagon enumeration is exhaustive.
For any feasible , the proposed dual inequalities give
If equality holds on every cell with , this last quantity equals . Hence for every feasible . This is weak duality with complementary slackness.
The Northwest corner method first allocates three units to , then two to , one to and four to :
Choose , , . Equality holds on its four occupied cells. The other inequalities are and . Thus implies that minimizes .
The last printed clause changes from minimization to maximization. To answer that wording, use the transportation simplex algorithm for maximization, equivalently minimize the negative costs. There are only two possible entering cells at :
  • Entering increases and by , and decreases and by . The maximal feasible step is , reaching and increasing by .
  • Entering increases and , and decreases and . Here , reaching and changing by .
Put . On the feasible hexagon,
If , this expression is maximized by taking , so is a global maximizer. If , the feasible vertex has objective larger than , so is not a maximizer. Nor can ever be one: comparison with requires , while comparison with the vertex requires . Therefore one pivot to a maximizer is possible exactly when , by entering . Its reduced cost for maximization is ; the other reduced cost is , so the improving pivot is unambiguous.
If “transportation algorithm” is required to retain the preceding minimization objective, no such step can reach a maximizer: every minimizing step is nonincreasing, whereas the feasible point always has . If the final word was intended to be “minimizes”, the corresponding genuinely improving one-pivot condition would instead be ; at , is already optimal and a zero-cost pivot is possible. These distinctions preserve the printed maximization request without silently altering it.