The generalized simplex method for minimizing a linear form under linear inequality restraints

Abstract

Background and summary.The determination of "optimum" solutions of systems of linear inequalities is assuming increasing importance as a tool for mathematical analysis of certain problems in economics, logistics, and the theory of games [l;5] The solution of large systems is becoming more feasible with the advent of high-speed digital computers; however, as in the related problem of inversion of large matrices, there are difficulties which remain to be resolved connected with rank.This paper develops a theory for avoiding assumptions regarding rank of underlying matrices which has import in applications where little or nothing is known about the rank of the linear inequality system under consideration.The simplex procedure is a finite iterative method which deals with problems involving linear inequalities in a manner closely analogous to the solution of linear equations or matrix inversion by Gaussian elimination.Like the latter it is useful in proving fundamental theorems on linear algebraic systems.For example, one form of the fundamental duality theorem associated with linear inequalities is easily shown as a direct consequence of solving the main problem.Other forms can be obtained by trivial manipulations (for a fuller discussion of these interrelations, see [13]); in particular, the duality theorem [8; 10; 11; 12] leads directly to the Minmax theorem for zero-sum two-person games [id] and to a computational method (pointed out informally by Herman Rubin and demonstrated by Robert Dorfman [la]) which simultaneously yields optimal strategies for both players and also the value of the game.The term "simplex" evolved from an early geometrical version in which (like in game theory) the variables were nonnegative and summed to unity.In that formulation a class of "solutions" was considered which lay in a simplex.The generalized method given here was outlined earlier by the first of the authors (Dantzig) in a short footnote [lb] and then discussed somewhat more fully at the Symposium of Linear Inequalities in 1951.Its purpose, as we have