Equalities in transportation problems and characterizations of optimal solutions

This paper considers the classical finite linear transportation Problem (I) and two relaxations, (II) and (III), of it based on papers by Kantorovich and Rubinstein, and Kretschmer. Pseudo-metric type conditions on the cost matrix are given under which Problems (I) and (II) have common optimal value, and a proper subset of these conditions is sufficient for Problems (II) and (III) to have common optimal value. The relationships between the three problems provide a proof of Kantorovich's original characterization of optimal solutions to the standard transportation problem having as many origins as destinations. The result are extended to problems having cost matrices which are nonnegative row-column equivalent.