LINEAR PROGRAMMING

What is linear programming? It's the way we solve problems like the one we encountered in the last section, when all the constraints are linear (in other words, you don't have anything squared or cubed, no logarithms or trigonometric functions; everything is simple). And no, linear programming doesn't mean you have to know how to program a computer (or even a calculator, for that matter), though computer programs do greatly simplify the process. If you know the C programming language, be sure to look at our free source code for two-dimensional linear programming problems.

The basic idea behind linear programming is that you only need to consider points in what's called the feasible region: the set of points that could possibly satisfy your constraints. When you graph this region, you will obtain a polygon-shaped area, with multiple corners. Because of the linear nature of your problem, the solution will only be found at a corner point. All you have to do is check the value of your objective function at each corner. For simple, two-dimensional problems without many constraints, this is simple. For more complex problems with many variables, we need a better way than checking every corner, and we use the simplex method. We'll get to that later. For now, we'll just try it the other way. In the last section we developed this problem:

Maximize a + 2b given the constraints a ³ 0, b ³ 0, 5a + 10b £ 50, and
18a + 4b £ 50.

Let's graph the feasible region determined by the constraints. It looks like this: