An Algorithm for Assigning Uses to Sources in a Special Class of Transportation Problems

Abstract

This paper considers a special class of transportation problems in which the needs of each user are to be supplied entirely by one of the available sources. We first show that an optimum solution to this special transportation problem is a basic feasible solution to a slightly different standard transportation problem. A branch-and-bound solution procedure for finding the desired solution to the latter is then presented and illustrated with an example. We then consider an extension of this problem by allowing the possibility of increasing (at a cost) the source capacities. The problem formulation is shown to provide a generalization to the well known assignment problem. The solution procedure appears to be relatively more efficient when the number of uses greatly exceeds the number of sources.