Page 71 - 35Linear Algebra

3

The Simplex Method

In Chapter 2, you learned how to handle systems of linear equations. However
there are many situations in which inequalities appear instead of equalities.
In such cases we are often interested in an optimal solution extremizing a
particular quantity of interest. Questions like this are a focus of fields such as
mathematical optimization and operations research. For the case where the
functions involved are linear, these problems go under the title linear pro-
gramming. Originally these ideas were driven by military applications, but
by now are ubiquitous in science and industry. Gigantic computers are dedi-
cated to implementing linear programming methods such as George Dantzig’s
simplex algorithm–the topic of this chapter.

3.1 Pablo’s Problem

Let us begin with an example. Consider again Pablo the nutritionist of
problem 5, chapter 1. The Conundrum City school board has employed
Pablo to design their school lunch program. Unfortunately for Pablo, their
requirements are rather tricky:

Example 34 (Pablo’s problem)
The Conundrum City school board is heavily influenced by the local fruit grower’s
association. They have stipulated that children eat at least 7 oranges and 5 apples
per week. Parents and teachers have agreed that eating at least 15 pieces of fruit per
week is a good thing, but school janitors argue that too much fruit makes a terrible
mess, so that children should eat no more than 25 pieces of fruit per week.

71