Chapter 16: Linear Programming

Contents Previous Chapter First Topic No Next Chapter

In Topic 11, we saw unconstrained optimization. We were looking for a local extreme point (minimum or maximum) of nonlinear functions. In this topic, we will look at finding global extreme points of linear functions subject to linear constraints. For example, what is the maximum value of f(x, y) = 3x + 4y when subject to the constraints

x ≥ 0
y ≥ 0
2x + 3y ≤ 7
2x + 2y ≤ 5
4x + y ≤ 9

These constrains define the region shown in Figure 1.

Figure 1. The constrained region

We will define such a problem more exactly, and then look at two techniques for solving such problems: the simplex method and the interior point method. The first starts from the outside and walks along the edges of the region while the second starts in the interior and works its way towards a solution.

Copyright ©2005 by Douglas Wilhelm Harder. All rights reserved.