chapter  4
40 Pages

Linear programming

Linear programming is an optimization technique for finding optimal solutions to

problems where the objective and constraints are linear. In what follows, the gen-

eral 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 struc-

ture 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 un-

derstanding 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 sec-

ond program (the dual). Before developing the discussion, a simple example will

illustrate how these programs arise.