ABSTRACT
Linear programming is an optimization technique for finding optimal solutions to problems where the objective and constraints are linear. In what follows, the general linear programming problem and methods of solution are described, along with various features of this class of problem. A linear program is characterized by a linear objective, linear constraints and restrictions on the signs of choice variables. Linearity of the constraint set leads to a particular geometric structure on the set possible choice variables. For low-dimensional programs this permits a graphical treatment of the problem and, more generally, the geometric structure leads naturally to an algorithmic method for finding solutions. Section 4.1 develops the basic features of a linear program. This consists of formulation of the programming problem, description of key issues in solving these programs and the valuation of resource constraints through the dual prices. A broader understanding of linear programming requires knowledge of basic solutions, which are discussed in Section 4.2. Here the geometric view described in Section 4.1 is reinterpreted in terms of equation systems. Section 4.3 describes classic results in linear programming where the original program (the primal) is related to a second program (the dual). Before developing the discussion, a simple example will illustrate how these programs arise.
