Page 386 - A Course in Linear Algebra with Applications

Chapter Ten

LINEAR PROGRAMMING

One of the great successes of linear algebra has been the
construction of algorithms to solve certain optimization prob-
lems in which a linear function has to be maximized or min-
imized subject to a set of linear constraints. Typically the
function is a profit or cost.Such problems are called linear
programming problems.
The need to solve such problems was recognized during
the Second World War, when supplies and labor were limited
by wartime conditions. The pioneering work of George Danzig
led to the creation of the Simplex Algorithm, which for over
half a century has been the standard tool for solving linear
programming problems. Our purpose here is to describe the
linear algebra which underlies the simplex algorithm and then
to show how it can be applied to solve specific problems.

t
10.1 Introduction o Linear Programming
We begin by giving some examples of linear programming
problems.

Example 10.1.1 (A productionproblem)

A food company markets two products F\ and F 2l which are
made from two ingredients I\ and I 2. To produce one unit
of product Fj one requires a^- units of ingredient Jj. The
maximum amounts of I\ and I 2 available are mi and m 2 ,
respectively. The company makes a profit of pi on each unit
of product Fi sold. How many units of F\ and F 2 should
the company produce in order to maximize its profit without
running out of ingredients?

370