An outline of linear programming

Linear programming deals with the maximization or minimization of linear functions subject to linear inequality constraints. Definitions and practical examples are given in Section 2. Section 3 gives a geometric interpretation of the simplex algorithm. Section 4 develops the mathematical theory of duality and gives heuristic interpretations in terms of shadow prices. Section 5 studies those linear programs for which integer solutions are normally required and discusses those cases in which integer solutions arise naturally and those in which special techniques must be used.The preparation of this paper was supported in part by the Army Research Office under Contract No. DA-ARO-D-31-124-70-G42.