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.
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 and be its floor and fractional part. The residual row and column sums and are nonnegative integers. Build a flow network with source-to-row flow network edge capacities , row-to-column flow network edge capacities one where , and column-to-sink flow network edge capacities . 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 , with where , then 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 , , or ; linear programs with such a constraint matrix and integer right side have integral vertices.
A matrix with entries in 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 and one per nonloop column and a zero column for a loop. Every square subdeterminant belongs to . 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.
Articles by others on the same topic
There are currently no matching articles.