Suchergebnisse

AbstractA recent result of Gomory (Princeton) solved an outstanding problem, namely that of solving linear programs in integers. Gomory showed how to add linear inequality constraints to a linear programming problem automatically in such a way that the extreme points of the resulting convex contain only integral solutions in the neighborhood of the minimum. In this paper an alternative method is given for generating these additional constraints in a way easy to justify and to apply. However it is not known whether these conditions will lead to a solution in a finite number of iterations of the simplex method as is true for the stronger Gomory conditions. Thus anyone considering their practical use should weigh the ease of generation against the extra number of iterations that will undoubtedly be required for convergence.

AbstractA simple computational method, based on the simplex algorithm of linear programming, is proposed for the following problem:"Consider a network (e.g., rail, road, communication network) connecting two given points by way of a number of intermediate points, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given point to the other."