Week 9


This is the first of two weeks devoted to Linear Programming. This week, we will cover the first three sections of chapter 5 and the first section of chapter 6.

What is Linear Programming?

A linear programming problem consists of several linear inequalities called constraints, and a linear objective function which is to be maximized or minimized. The objective function is often a profit (to be maximized), or a cost (to be minimized).

For the case of two variables, we can represent the problem graphically. Each constraint corresponds to a half-plane on one side of a straight line. The intersection of all the half-planes forms the feasible region. This region is either empty, or it is a polygon, that is, something bordered by straight line segments.

We want to find the maximum or minimum of the objective function among all the points in the feasible region. The objective function is constant along lines in a certain direction. The maximum and minimum will always occur along a line that just barely touches the region.

For the standard problems that we do, the feasible region is always in the first quadrant, and the slope of the line representing the objective function is negative. This implies that if the region is bounded (that is, it does not extend all the way out to infinity), there is always a minimum and a maximum, and both of them are at corner points of the feasible region. If the region is unbounded, there will be a minimum, but no maximum.

It is possible that the maximum or minimum occurs at two corner points simultaneously. In this case, any point on the boundary between the two corners is also a solution.

Left: Single solution (the usual case).
Right: Multiple solution. Any point between B and C is a solution


Last Updated: Monday, July 13, 2015