How do you solve a linear programming problem with a graph?
Now that we have several linear programming problems, let’s look at how we can solve them using the graph of the system of inequalities. The linear programming problem for the craft brewery was found to be
Figure 2 – The feasible region for the craft brewery problem.
The shaded region corresponds to all of the possible combinations of pale ale and porter that satisfy the constraints. Since the solution to the maximization of profit must come from this region, it is called the feasible region. This means that the ordered pairs in the shaded region are feasible solutions for the linear programming problem.
To solve the linear programming problem, we need to find which combination of x1 and x2 lead to the greatest profit. We could pick possible combination from the graph and calculate the profit at each location on the graph, but this would be extremely time consuming. Instead we’ll pick a value for the profit and find all of the ordered pairs on the graph that match that profit.
Suppose we start with a profit of $3,000,000. Substitute this value into the objective function to yield the equation
3,000,000 = 100x1 + 80x2
If we graph this line on the same graph as the system of inequalities, we get the dashed line labeled P = 3,000,000. A line on which the profit is constant is called an isoprofit line. The prefix iso- means same so that an isoprofit line has the same profit along it. Along the isoprofit line P = 3,000,000, every combination of pale ale and porter leads to a profit of $3,000,000.
Figure 3 – Several levels of profit at $3,000,000, $4,000,000 and $5,000,000.
The isoprofit lines P = 4,000,000 and P = 5,000,000 can be graphed in the same manner and are pictured in Figure 3.
As profit increases, the isoprofit lines move farther to the right. Higher profit levels lead to similar lines that are farther and farther from the origin. Eventually the isoprofit line is outside of the feasible region. For equally spaced profit levels we get equally spaced parallel lines on the graph. Notice that P = 5,000,000 is completely outside the shaded region. This means that no combination of pale ale and porter will satisfy the inequalities and earn a profit of $5,000,000. There is an isoprofit line, P ≈ 4,706,564, that will just graze the feasible region. This isoprofit line will touch where the border for the capacity constraint and the border of the hops constraint intersect. Points where the borders for the constraints cross are called corner points of the feasible region.
Figure 4 -The optimal production level for the craft brewery rounded to one decimal place. The isoprofit for this level is also graphed.
If the profit is any higher than this level, the isoprofit line no longer contains any ordered pairs from the feasible region. This means that this profit level is the maximum profit and it occurs at the corner point where 35,328.2 barrels of pale ale and 14,671.8 barrels of porter are produced.
Two of the constraint borders intersect at the corner point corresponding to the optimal solution. These constraints, the constraints for capacity and hops, are said to be binding constraints. The malt constraint does not intersect the corner point that maximizes profit so it is a nonbinding constraint.
For resources corresponding to binding constraints, all of the resources are used. In this case, all of the capacity and hops are used to produce the optimal amounts of beer. However, all of the malt is not used which is why the malt constraint is not binding at the optimal solution.
The fact that the optimal solution occurs at a corner point of the feasible region suggests the following insight.
The optimal solution to a linear programming occurs at a corner point to the feasible region or along a line connecting two adjacent corner points of the feasible region.
If a feasible region is bounded, there will always be an optimal solution. Unbounded feasible regions may or may not have an optimal solution.
We can use this insight to develop the following strategy for solving linear programming problems with two decision variables.
1. Graph the feasible region using the system of inequalities in the linear programming problem.
2. Find the corner points of the feasible region.
3. At each corner point, find the value of the objective function.
By examining the value of the objective function, we can find the maximum or minimum values. If the feasible region is bounded, the maximum and minimum values of the objective function will occur at one or more of the corner points. If two adjacent corner points lead to same maximum (or minimum) value, then the maximum (or minimum) value also occurs at all points on the line connecting the adjacent corner points.
Unbounded feasible regions may or may not have optimal values. However, if the feasible region is in the first quadrant and the coefficients of the objective function are positive, then there is a minimum value at one or more of the corner points. There is no maximum value in this situation. Like a bounded region, if the minimum occurs at two adjacent corner points, it also occurs on the line connecting the adjacent corner points.
Figure 5 – The feasible region in Graph (a) can be enclosed in a circle so it is a bounded feasible region. The feasible region in Graph (b) extends infinitely far to the upper right so it cannot be enclosed in a circle. This feasible region is unbounded.
Example 2 Solve the Linear Programming Problem Graphically
Solve the linear programming problem graphically:
Solution The feasible region is in the first quadrant since the non-negativity constraints and are included in the system of inequalities.
The other two inequalities are converted to equations and graphed using the horizontal and vertical intercepts.
We can graph these intercepts in the first quadrant and connect them with solid lines to yield the following graph.
Figure 6 – The borders for the feasible region in Example 2. Since the inequalities are not strict inequalities, the borders are drawn with solid lines.
To determine what portion of this graph corresponds to the feasible region, we need to test the original inequalities with a point from the graph. Although we could choose any ordered pair that is not on one of the lines, in this example we’ll test with (1, 1).
The test point is in the solution set of each inequality. Sketch arrows on each line pointing in the direction of the test point.
Figure 7 – Since both inequalities are true, the arrows on each line should point in the direction of the test point.
The solution sets for the inequalities overlap in the lower left hand corner of the graph.
Figure 8 – The feasible region for the linear programming problem in Example 2.
The optimal solution for the linear programming problem must come from this region. Since this is a bounded feasible region, the maximum will occur at one of the corner points. From the graph and the intercepts of the borders, we can see easily identify three corner points: (0, 0), (2, 0), and (0, 2). One more corner point is located at the intersection of the line 2x + y = 4 and x + 2y = 4. We could find this corner point by the Substitution Method, Elimination Method or with matrices, In this example we’ll use the Substitution Method since it is easy to solve for a variable in one of the equations.
To apply the Substitution Method to the system of equations
solve the first equation for y. If we subtract 2x form both sides of the first equation we get y = -2x + 4.
Replace y with -2x + 4 in the second equation and solve for x,
To find y, substitute the value for x into y = -2x + 4 to yield
The solution to the system is x = 4/3 and y = 4/3.
Let’s label the corner points on the graph and calculate the value of the objective function at each of them.
Figure 9 – The feasible region with the corner points labeled.
Since 44/3 is approximately 14.67, the corner point at (4/3, 4/3) yields the maximum value of the objective function.
Example 3 Solve the Linear Programming Problem Graphically
Solve the linear programming problem graphically:
Solution To graph the system of inequalities, we need to pick an independent variable to graph on the horizontal axis. Although the choice is arbitrary, in this example we’ll graph y1 on the horizontal axis and y2 on the vertical axis.
This linear programming problem includes non-negativity constraints, y1 ≥ 0 and y2 ≥ 0. In the graph, we’ll account for these constraints by graphing the system of inequalities in the first quadrant only.
The borders for the other two constraints are graphed by utilizing the slope-intercept form of a line and intercepts.
Figure 10 – The borders of the first two constraints in the linear programming problem in Example 3. The graph is shown in the first quadrant due to non-negativity constraints.
Notice that the borders are drawn with solid lines since the inequalities are not strict inequalities. To shade the solution on the graph, substitute the test point (0, 0) into each inequality.
Since each inequality is false, draw arrows on each line pointing away from the test point.
Figure 11 – Since each inequality is false at (0, 0), the side opposite each test point must be shaded.
The shading for each inequality coincides in the upper right portion of the graph.
Figure 12 – The feasible region for the system of inequalities for Example 3.
The feasible region extend infinitely far towards the upper right. This feasible region is unbounded since it cannot be enclosed in a circle. A minimum value may or may not exist.
Three corner points are evident in the feasible region. Two of the corner points, (0, 8) and (8, 0), are on the lines drawn earlier. The third corner point occurs where the line y2 = –1/4 y1 + 2 and the line 7y1 + 4y2 = 32 cross.
Figure 13 – The corner points for the feasible region.
Since the first equation, y2 = –1/4 y1 + 2, is solved for y2, it is easiest to use the Substitution Method to solve for the intersection point.
Substitute y2 = –1/4 y1 + 2 into to 7y1 + 4y2 = 32 yield
Solve this equation by isolating y1:
Put this value into the first equation to give y2 = –1/4 (4) + 2 = 1. So the third corner point is located at (y1, y2) = (4, 1).
To find the minimum value of the objective function w = 4y1 + y2, substitute the corner points.
Figure 14 – The feasible region with the corner points labeled.
It appears that the minimum is at the ordered pair (y1, y2) = (0, 8).
To confirm that the minimum is located at (0, 8), look at three isolevels of w = 4, w = 8, and w = 12. The level should pass through the corner point, but where do the other levels lie?
If we set w equal to each of these levels in the objective function and add these to the graphs, we see how the isolevels behave near the feasible region.
As anticipated, the w = 8 level passes through the corner point at (0, 8). Higher w levels, like w = 12, pass through the feasible region. As w increases, the isolevel lines move farther and farther into the feasible region meaning the feasible region has no maximum value.
We are interested in a minimum value for the objective function. The lowest value of w that includes any points in the feasible region is w = 8. Any levels lower than w = 8, like w = 4, lie completely outside of the feasible region. The level w = 8 passes through the corner point (0, 8) and is the optimal value for the linear programming problem.
In each of the previous examples, there was one optimal solution. In the next example, there are many possible solutions to the linear programming problem. Each solution yields the same value of the objective function.
Example 4 Solve the Linear Programming Problem Graphically
Solve the linear programming problem graphically:
Solution As with the earlier examples, the non-negativity constraints allow us to graph the system of inequalities in the first quadrant only. To graph the borders of the other three constraints, convert each of the inequalities to equations,
The line x = 8 is a vertical line passing through the horizontal axis at (8, 0). We can place these three lines on a graph as shown in Figure 15.
Figure 15 – A graph of the border of each inequality in Example 4.
To shade the solution on the graph, substitute the test point into each inequality.
Figure 16 – Since each inequality is true, shade the half plane formed by each inequality where the test point lies.
The individual solution sets all overlap in the feasible region shown below.
Figure 17 – The feasible region for the system of inequalities in Example 4.
Since this feasible region is bounded, the maximum value of the objective function is located at one of the corner points or along a line connecting adjacent corner points.Several of the corner points are easily identified from the intercepts. However, the two corner points in the upper-right corner of the feasible region are not so obvious.
The red border, given by the line x + 3y = 24, and the green line, given by x = 8, intersect at one of these corner points.
If we substitute x = 8 into x + 3y = 24, we can solve for y to get the first corner point:
The corner point is at (8, 16/3).
Figure 18 – The feasible region with a corner point shown.
Another corner point is where red line, x + 3y = 24, intersects the blue line, –x + 6y = 30. Using the Substitution Method, we can solve for x in the first equation to yield x = -3y + 24. Substitute the expression -3y + 24 for x in the second equation and solve for y:
If we set y = 6 in x = -3y + 24, we get the corresponding x value, x = 6.
Figure 19 – The feasible region with a corner points at (6, 6) and shown (8, 16/3).
Now that we have the corner points, we can substitute the coordinates into the objective function to find the maximum value.
Figure 20 – The corner points and the corresponding values of the objective function.
Two adjacent corner points yield the same value, z = 120. This means that the objective function is maximized at any point of a line connecting (6, 6) and (8, 16/3).
Figure 21 – The isolevel z = 120 passes through two adjacent corner points indicating that the objective function is optimized anywhere on the line connecting the points.
If we graph the isolevel 5x + 15y = 120 on the feasible region, we see that it passes through these points.
For any higher isolevel, the line would be outside of the feasible region. Therefore, this level is the maximum value of the objective function.