A linear programming problem is one in which we are to maximize (or minimize) a linear objective function subject to constraints in the form of linear inequalities or equations. Among these constraints is the requirement that the values of the variables are non-negative. The feasible region is the set of points that simultaneously satisfy all of these constraints. The optimal solution is any point in the feasible region for which the objective function has its maximum (or minimum) value.
A manufacturer of lightweight mountain tents makes a standard model and an expedition model for national distribution. Each standard tent requires 1 labor-hour from the cutting department and 3 labor-hours from the assembly department. Each expedition tent requires 2 labor-hours from the cutting department and 4 labor-hours from the assembly department. The maximum labor-hours available per day in the cutting department and the assembly department are 32 and 84 respectively. If the company makes a profit of $50 on each standard tent and $80 on each expedition tent, how many tents of each type should be manufactured each day to maximize the total daily profit (assuming that all tents can be sold)?
Here is the mathematical model for this problem:
The objective function is the profit function and our goal is to find the maximum profit subject to the cutting and assembly labor-hours constraints (and the constraints that x1 ≥ 0 and x2 ≥ 0). The feasible region is the shaded region in the graph below where the red line corresponds to the cutting constraint and the green line corresponds to the assembly constraint:
The profit function is given by P = 50x1 + 80x2. Solve this function for x2:
This final equation is in the form x2 = mx1 + b where m is the slope of the line and b is the value of the y-intercept. The slope of the profit equation is -5/8 and the y-intercept is P/80 (i.e., the profit divided by 80). Notice, in particular that the slope of this line is independent of the profit so all of the profit lines are parallel to each other. Furthermore, as the profit increases, the y-intercept also increases and the profit line gets farther from the origin.
A profit of zero is earned if no tents of either type are made (i.e., at the origin). As we saw in the previous section, the higher the profit, the farther the profit line is from the origin. Geometrically, then, the maximum profit corresponds to the profit line that is farthest from the origin but which still intersects the feasible region. The goal of linear programming is to find that optimal profit line. The animated image below illustrates this basic concept. You can watch as the profit line moves from the origin out as far as possible.
Notice that for a profit line with a slope of -5/8, the line farthest from the origin passes through the point (20, 6). Consequently, the maximum daily profit occurs when the company makes 20 standard tents and 6 expedition tents per day. The profit line through this point corresponds to a profit of $1,480 per day.
Since the constraints of a linear programming problem are linear, the feasible region is bounded by straight lines. The intersections of these sides are the vertices of the feasible region. In the example above, the feasible region has four sides and four vertices. For a maximization problem, the line representing the objective function is moved as far as possible from the origin (while still intersecting the feasible region). For a minimization problem, the line representing the objective function is moved as close to the origin as possible (while still intersecting the feasible region).
In either case, the optimal solution will normally intersect the feasible region at one of its vertices. If the slope of the objective function is the same as the slope of one of the sides of the feasible region, the line representing the objective function may be coincident with this side leading to multiple solutions. This is summed up in the fundamental theorem of linear programming: If a linear programming problem has an optimal solution, it will occur at one or more of the vertices of the feasible region.
Given all of the constraints of our tent manufacturing example, let's investigate several different profit functions.
Example 1. Suppose the manufacturer makes $32 on each standard tent and $76 dollars on each expedition tent. The profit equation is given by P = 32x1 + 76x2. The optimal solution is at the vertex (0, 16) as shown in the graph below. The profit line cannot be moved any further from the origin and still intersect the feasible region. The maximum profit is earned when the company makes 16 expedition tents per day but no standard tents at all. The maximum daily profit is $1,216.
Example 2. Suppose the manufacturer makes $48 on each standard tent and $96 on each expedition tent. The profit equation is given by P = 48x1 + 96x2. The optimal solution is at the vertex (0, 16) and at the vertex (20, 6) as shown in the graph below. The profit line can not be moved any further from the origin and still intersect the feasible region. Notice that the profit line coincides with one side of the feasible region. The maximum daily profit is $1,536.
Actually, there are a lot more optimal solutions. All of the points with integer values on the edge of the feasible region from (0, 16) to (20, 6) are optimal solutions and all yield a daily profit of $1,536. The following points are all additional solutions: (2, 15), (4, 14), (6, 13), (8, 12), (10, 11), (12, 10), (14, 9), (16, 8), and (18, 7).
Example 3. Suppose the manufacturer makes $60 on each standard tent and $70 on each expedition tent. The profit equation is given by P = 60x1 + 70x2. The optimal solution is at the vertex (28, 0) as shown in the graph below. The profit line cannot be moved any further from the origin and still intersect the feasible region. The company should make 28 standard tents and no expedition tents. The maximum daily profit is $1,680.