Our next step is that we still must find the optimal production policy, a point within the feasible region that gives a maximum profit. There are a lot of points in that region. If you consider points with only whole numbers as values for or , there are many points, but, in fact, either or or both could be some fractional number. There are so many points in this feasible region that to consider the profit at each one of them would require us to calculate profits from now until we grow very old, and still the calculations would not be done. Here is where the genius of the linear-programming technique comes in, with the corner point principle, which we define in terms of our mixture problems.

135

The corner point principle is probably the most important insight into the theory of linear programming. Later in this chapter, we will explain why this principle works. The geometric nature of this principle explains the value of creating a geometric model from the data in a mixture chart.

The corner point principle gives us the following method to solve a linear-programming problem:

Let’s look at the feasible region that we drew in Figure 4.3 on page 133. It is a triangle having three corners; namely, (0, 0), (0, 30), and (12, 0). Now all we need to do is find out which of these three points gives us the highest value for the profit formula, which in this problem is . We display our calculations in Table 4.1. The maximum profit for the toy manufacturer is $16.50, and that happens if the manufacturer makes 0 skateboards and 30 dolls. The point (0, 30) is called the optimal production policy.

General Shape of Feasible Regions

The shape of a feasible region for a linear-programming mixture problem has some important characteristics, without which the corner point principle would not work:

The Role of the Profit Formula: Skateboards and Dolls

In practice, there are often different amounts of resources available in different time periods. The selling price for the products can also change. For example, if competition forces us to cut our selling price, the profit per unit can decrease. To maximize profit, it is usually necessary for a manufacturer to redo the mixture problem calculations whenever any of the numbers change.

Suppose that business conditions change, and now the profits per skateboard and doll are, respectively, $1.05 and $0.40. Let us keep everything else about the skateboards and dolls problem the same. The change in profits would give us a new profit formula of . When we evaluate the new profit formula at the corner points, we get the results shown in Table 4.3. This time, the optimal production policy, the point that gives the maximum value for the profit formula, is the point (12, 0). To get the maximum profit of $12.60, the toy manufacturer should now make 12 skateboards and 0 dolls.

137

We see from this example that the shape of the feasible region, and thus the corner points we test, are determined by the constraint inequalities. The profit formula is used to choose an optimal point from among the corner points, so it is not surprising that different profit formulas might give us different optimal production policies.

We started the exploration of skateboard and doll production with the idea that a toy manufacturer has a product line with either one to two products. But both linear-programming solutions we have found tell the manufacturer that to maximize profit, make just one product. This is probably not an acceptable result for the manufacturer, who might want to produce both products for business reasons other than profit, such as establishing brand loyalty. And it certainly would be very difficult for the manufacturer to be ready to switch back and forth between producing either skateboards or dolls every time the profit formula changed. Linear programming is a flexible enough technique that it can accommodate the desire for there to be both products in the optimal production policy. This is done by specifying that there be nonzero minimum quantities for each period.

Summary of the Pictorial Method Using a Feasible Region

Let’s stop and summarize the steps we are following to find the optimal production policy in a mixture problem:

138

Two Products and Two Resources: Skateboards and Dolls

We return to the toy manufacturer now to consider two limited resources instead of one. The second limited resource will be time, the number of person-minutes available to prepare the products. Suppose that there are 360 person-minutes of labor available and that making one skateboard requires 15 person-minutes and making one doll requires 18 person-minutes. We will continue to use the original values regarding containers of plastic, the first of our two profit formulas, and to keep the problem relatively simple, we use the zero minimum constraints: and . We need a new mixture chart. In general, we will include a column for minimums in a mixture chart only if there are any nonzero minimum constraints. In Figure 4.6, we have the mixture chart for this problem. Using the mixture chart, we can write the two resource constraints:

and

We can also write the profit formula: .

The half-plane corresponding to the plastic resource is shown in Figure 4.7a. We now need to graph the half-plane corresponding to the time constraint. We find where the line intersects the two axes by substituting first and then into that equation.

The line corresponding to the time constraint contains the two points (0, 20) and (24, 0). When we insert the point (0, 0) into the inequality , we get , or , which is true, so (0, 0) is on the side of the line that we shade. Putting all this together, we get the half-plane in Figure 4.7b as the correct half-plane for the time resource constraint.

139

We are not permitted to exceed the supply of even a single resource. Therefore, the feasible region must be made up of points that are shaded twice—both in the half-plane for the plastic resource constraint, shown in Figure 4.7a, and in the half-plane for the time resource constraint in Figure 4.7b. For the procedure with several half-plane constraints, we build our feasible region by finding the intersection, or overlap, of the individual half-planes in the problem. In Figure 4.7c, we show the result of intersecting the half-planes from the two resource constraints. Because this problem has minimums that are zeroes, the shaded region in Figure 4.7c is in fact the feasible region for the problem.

The next step that we need to carry out to use the pictorial method for solving this problem is to find the corner points of the feasible region. This is carried out by doing the algebra necessary to solve two linear equations in two unknowns. This leads to the points (0, 0), (0, 20), (6, 15), and (12, 0). Three of these points have a zero value for one or more of the unknowns, so the calculations are easy.

To find the coordinates of the point (6, 15), it is necessary to solve for the point that satisfies both of the equations and . To solve these two equations simultaneously, you must multiply one or both of the equations by a number to create equivalent equations, so that when added together, one of the variables will cancel out. One way to do this is to multiply the first of these equations by −3, obtaining the equation . When this is added to the second equation, the term “drops out” and we can solve , to get . Now it is an easy matter to substitute this value into either of the original equations to get the value of 6.

We are ready to finish the problem. In Table 4.4 we have evaluated the profit formula at the four corner points of the feasible region. The optimal production policy for the toy manufacturer would be to make 6 skateboards and 15 dolls, for a maximum profit of $14.25.

Here is another mixture problem example of how the pictorial method using a feasible region works from start to finish.