
1
Linear Programming
1.1 Introduction
Linear programming (LP) is the problem of optimizing (maximizing or min-
imizing) a linear function subject to linear constraints. A wide variety of
practical problems, from nutrition, transportation, production planning, fi-
nance, and many more areas can be modeled as linear programs. We begin
by introducing one of the earliest examples, the diet problem, and then give
some additional applications in the areas of production management, trans-
portation, finance, and personnel scheduling. Some of these examples are not
initially linear programs, but are amenable to being transformed into LPs and
techniques for conv ...