The input to the transportation problem consists of a complete weighted bipartite graph G = (V ₁,V ₂,w), integer supplies a _i ≥ 0, i ∈ V ₁, and integer demands b _j ≥ 0, j ∈ V ₂, where w.l.o.g. . The problem is to compute flows x _ij i ∈ V ₁, j ∈ V ₂ such that for every i ∈ V ₁, for every j ∈ V ₂, and is maximized (or minimized). The transportation problem is polynomially solvable even when the flows are required to be integers.