An Algorithm for a Special Class of Generalized Transportation-Type Problems

摘要

The algorithm described in this paper is used to solve a special class of linear programming problems characterized by constraint coefficient matrices having generalized transportation structure. Specifically, n available resources are allocated to m capacity-limited operations (where the operational capability of assigning the jth resource to the ith operation is known) such as to maximize the total profit for the system. The row-and-column structure of such problems permits an algorithm more efficient than the general simplex algorithm to be used to solve moderate-sized problems (problems where loop-tracing techniques or equivalent schemes are not required). It is not required in the problem statement that all the resources be allocated or that all operations be performed to capacity limits. It is characteristic of such problems, however, that the optimizing solution usually requires that at least one of the two conditions holds, i.e., either supply or demand is exhausted. The paper contains a description of the algorithm, a computer program, an example illustrating its application, and some comparisons with the general simplex algorithm in solving the same problem. (Author)