Multiparametric demand transportation problem

In some applications a minimum cost transportation model arises where supplies are fixed while demands may simultaneously vary. In this paper we analyse the structure of such a model and propose several techniques to describe its behaviour. Our approach is founded on the concept of optimal region, i.e., the subset of demand vectors where a given basic tree is optimal. The proposed algorithm consists in different pivoting strategies designed to: (1) build up a minimal list of basic trees such that the associated optimal regions cover the set of feasible demand vectors; (2) analyse the effects of either opening a new supplier or closing an existing one; (3) suitably treat the dual degenerate case by building up a minimal representation of every maximal region where the optimal value is linear in the demand vector. Computational complexity is discussed and numerical examples are given.