Appendix Linear Programming

In this chapter’s Power Recreation example (see Product-Mix Decisions With Capacity Constraints), suppose both the snowmobile and boat engines must be tested on a very expensive machine before they are shipped to customers. The available machine-hours for testing are limited. Production data are as follows:

Exhibit 12-13 summarizes these and other relevant data. In addition, as a result of material shortages for boat engines, Power Recreation cannot produce more than 110 boat engines per day. How many engines of each type should Power Recreation’s managers produce and sell daily to maximize operating income?

Because there are multiple constraints, managers can use a technique called linear programming (LP) to determine the number of each type of engine to produce. LP models typically assume that all costs are either variable or fixed for a single cost driver (units of output). We will see that LP models also require certain other linear assumptions to hold. When these assumptions fail, managers should consider other decision models.^*

Steps in Solving an LP Problem

We use the data in Exhibit 12-13 to illustrate the three steps in solving an LP problem. Throughout this discussion, S equals the number of snowmobile engines produced and sold, and B equals the number of boat engines produced and sold.

Step 1: DETERMINE THE OBJECTIVE FUNCTION. The objective function of a linear program expresses the objective or goal to be maximized (say, operating income) or minimized (say, operating costs). In our example, the objective is to find the combination of snowmobile engines and boat engines that maximizes total contribution margin. Fixed costs remain the same regardless of the product-mix decision and are irrelevant. The linear function expressing the objective for the total contribution margin (TCM) is

1. Step 2: SPECIFY THE CONSTRAINTS. A constraint is a mathematical inequality or equality that must be satisfied by the variables in a mathematical model. The following linear inequalities express the relationships in our example:

1. The three solid lines on the graph in Exhibit 12-14 show the existing constraints for assembly and testing and the materials-shortage constraint.^* The feasible or technically possible alternatives are those combinations of quantities of snowmobile engines and boat engines that satisfy all the constraining resources or factors. The shaded “area of feasible solutions” in Exhibit 12-14 shows the boundaries of those product combinations that are feasible.

1. Step 3: COMPUTE THE OPTIMAL SOLUTION. Linear programming (LP) is an optimization technique used to maximize the objective function when there are multiple constraints. We present two approaches for finding the optimal solution using LP: trial-and-error approach and graphic approach. These approaches are easy to use in our example because there are only two variables in the objective function and a small number of constraints. Understanding these approaches provides insight into LP. In most real-world LP applications, managers use computer software packages to calculate the optimal solution.^*

Trial-and-Error Approach

Managers can find the optimal solution by trial and error, by working with coordinates of the corners of the area of feasible solutions. As we will see, the optimal solution always lies at an extreme point of the feasible region.

First, select any set of corner points and compute the total contribution margin. Five corner points appear in Exhibit 12-14. It is helpful to use simultaneous equations to obtain the exact coordinates in the graph. To illustrate, the corner point $(S=75, B=90)$ can be derived by solving the two pertinent constraint inequalities as simultaneous equations:

Given $S = 75$ snowmobile engines and $B = 90$ boat engines, $TCM=(\mathrm{\$}240\text{per snowmobile engine}\times 75\text{snowmobile engines}) +$ $(\mathrm{\$}375\text{per boat engine} \times$ $90\text{boat engines})=\mathrm{\$}\text{51,750}$.

Second, move from corner point to corner point and compute the total contribution margin at each corner point.

The optimal product mix is the mix that yields the highest total contribution: 75 snowmobile engines and 90 boat engines. To understand the solution, consider what happens when moving from the point (25, 110) to (75, 90). Power Recreation gives up $\mathrm{\$}\text{7,500}\mathrm{\hspace{0.17em}}[\mathrm{\$}375\times (110-90)]$ in contribution margin from boat engines while gaining $\mathrm{\$}\text{12,000}\mathrm{\hspace{0.17em}}[\mathrm{\$}240\times (75-25)]$ in contribution margin from snowmobile engines. This results in a net increase in contribution margin of $4,500 $(\mathrm{\$}\text{12,000}-\mathrm{\$}\text{7,500})\mathrm{,}$ from $47,250 to $51,750.

Graphic Approach

Consider all possible combinations that will produce the same total contribution margin of, say, $12,000. That is,

This set of $12,000 contribution margins is a straight dashed line through $[S=50\mathrm{\hspace{0.17em}}(\mathrm{\$}\text{12,000}÷\mathrm{\$}240);B=0]$ and $[S=0;B=32\mathrm{\hspace{0.17em}}(\mathrm{\$}\text{12,000}÷\mathrm{\$}375)]$ in Exhibit 12-14. Other equal total contribution margins can be represented by lines parallel to this one. In Exhibit 12-14, we show three dashed lines. Lines drawn farther from the origin represent more sales of both products and higher amounts of equal contribution margins.

The optimal line is the one farthest from the origin but still passing through a point in the area of feasible solutions. This line represents the highest total contribution margin. The optimal solution—the number of snowmobile engines and boat engines that will maximize the objective function, total contribution margin—is the corner point $(S=75\mathrm{,} B=90)\mathrm{.}$ This solution will become apparent if you put a straight-edge ruler on the graph and move it outward from the origin and parallel with the $12,000 contribution margin line. Move the ruler as far away from the origin as possible—that is, increase the total contribution margin—without leaving the area of feasible solutions. In general, the optimal solution in a maximization problem lies at the corner where the dashed line intersects an extreme point of the area of feasible solutions. Moving the ruler out any farther puts it outside the area of feasible solutions.

Sensitivity Analysis

What are the implications of uncertainty about the accounting or technical coefficients used in the objective function (such as the contribution margin per unit of snowmobile engines or boat engines) or the constraints (such as the number of machine-hours it takes to make a snowmobile engine or a boat engine)? Consider how a change in the contribution margin of snowmobile engines from $240 per unit to $300 per unit would affect the optimal solution. Assume the contribution margin for boat engines remains unchanged at $375 per unit. The revised objective function will be

Using the trial-and-error approach to calculate the total contribution margin for each of the five corner points described in the previous table, the optimal solution is still $(S=75\mathrm{,}\hspace{0.17em}B=90)\mathrm{.}$ What if the contribution margin of snowmobile engines falls to $160 per unit? The optimal solution remains the same $(S=75\mathrm{,}\hspace{0.17em}B=90)\mathrm{.}$ Thus, big changes in the contribution margin per unit of snowmobile engines have no effect on the optimal solution in this case. That’s because, although the slopes of the equal contribution margin lines in Exhibit 12-14 change as the contribution margin of snowmobile engines changes from $240 to $300 to $160 per unit, the farthest point at which the equal contribution margin lines intersect the area of feasible solutions is still $(S=75,\hspace{0.17em}B=90)\mathrm{.}$