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

作者：George B. Dantzig, Alex Orden, Philip Wolfe · 发表于：Pacific Journal of Mathematics · 年份：1955 · DOI：10.2140/pjm.1955.5.183 · 被引用次数：584 · 研究领域：Advanced Optimization Algorithms Research

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 demonstrate...