Probabilistic Analysis of the Capacitated Transportation Problem

We consider the capacitated transportation problem defined by sets of supplies a_i, i ∈ I, demands b_j, j ∈ J, and capacities c_ij, i ∈ I, j ∈ J. Assuming that the capacities are random variables, we prove asymptotic conditions on the supplies and demands which assure that a feasible solution exists almost surely. The proof is constructive and supplies an algorithm whose running time is O(| I| |J|). We then apply the results to the maximum flow problem.