An Introduction to Linear Programming

Is linear programming useful in real life?

In real life, linear programming is part of a very important area of mathematics called "optimization techniques".

This field of study (or at least the applied results of it) are used every day in the organization and allocation of resources. These real life systems can have dozens of variables, or hundreds, or more. (For the curious, a history of linear programming: PDF)

In algebra, though, you'll only work with the simple (and graphable) two-variable linear case.

How do you solve a linear programming problem?

The general process for solving linear-programming exercises is as follows:

1. Graph the system of linear inequalities. The area walled off by the various inequalities is called the "feasibility region".
2. Taking the "equals" versions of the inequalities, solve pairs of lines to find the corner points (or "vertices") of the feasibility region.
3. Plug the coordinates of each of the vertices into the model for the situation at hand (that is, into the optimization equation).
4. If you're maximizing, take the corner that gives you the highest value; otherwise, take the one with the lowest value.
5. For word problems, interpret the result within the context given (for example, say "eight meters wide and three meters tall" rather than just "(8, 3)").

Why do you test only the corners?

Somebody figured out that, given a system of linear inequalities and an equation to be optimized (that is, to be maximized or minimized), the system's optimal solution will always be on a corner.

There are complicated explanations for this, but also intuitive ones (for the simple two-variable case that we'll be working with). Either way, the corners are where it's at.

---

• Find the maximal and minimal value of z = 3x + 4y subject to the following constraints:
  

---

As you can see, solving a linear-programming exercise can be a lengthly process, but each individual step is fairly straightforward. Just take your time, label clearly, and work neatly, and you'll get it!