Solving generalized transportation problems via pure transportation problems

This paper investigates certain issues of coefficient sensitivity in generalized network problems when such problems have small gains or losses. In these instances, it might be computationally advantageous to temporarily ignore these gains or losses and solve the resultant “pure” network problem. Subsequently, the optimal solution to the pure problem could be used to derive the optimal solution to the original generalized network problem. In this paper we focus on generalized transportation problems and consider the following question: Given an optimal solution to the pure transportation problem, under what conditions will the optimal solution to the original generalized transportation problem have the same basic variables? We study special cases of the generalized transportation problem in terms of convexity with respect to a basis. For the special case when all gains or losses are identical, we show that convexity holds. We use this result to determine conditions on the magnitude of the gains or losses such that the optimal solutions to both the generalized transportation problem and the associated pure transportation problem have the same basic variables. For more general cases, we establish sufficient conditions for convexity and feasibility. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 666–685, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10034