Operations Research Models and Methods / Models / Linear Programming

Product Mix Problem


Click for Details

The figure represents a manufacturing system producing two products labeled P and Q. The rounded rectangles at the top of the figure indicate the revenue per unit and the maximum sales per week. For instance we can sell as many as 100 units of P for $90 per unit. The circles show the raw materials used, and the rectangles indicate the operations that the products must pass through in the manufacturing process. Each rectangle designates a machine used for the operation and the time required.

For example product P consists of two subassemblies. To manufacture the first subassembly, one unit of RM1 passes through machine A for 15 minutes. The output of machine A is moved to machine C where it is processed for 10 minutes. The second subassembly starts with RM2 processed in machine B for 15 minutes. The output is taken to machine C for 5 minutes of processing. The two subassemblies are joined with a purchased part in machine D. The result is a finished unit of P. Product Q is manufactured by a similar process as indicated in the figure.

The rectangle at the upper left indicates that one machine of each type is available. Each machine operates for 2400 minutes per week. OE stands for operating expenses. For this case the operating expenses, not including the raw material cost is $6000.

Our problems include the following: Find the product mix that maximizes profit. Identify the bottlenecks. For each product, find the range over which the unit profit can change without affecting the product mix. For each machine, identify the marginal benefit of adding one more minute of machine time. For each machine, find the range over which the time availability can change without affecting the identity of the bottleneck.


Linear Programming Model

There are many problems that might be posed using the figure above, but we choose the problem of allocating the times available on the machines to the manufacture of the two products. The decisions involve the amounts of the two products.

The objective is to maximize profit. From the figure we see that the profit per unit of product is its unit revenue less the raw material cost per unit. For P the unit profit is $45 and for Q it is $60. The objective is a linear expression of the amounts produced.

The constraints specify that the amounts of time required of each machine must not exceed the amount available. The amount of time required of a machine is a linear function of the production amounts.

Machine Time Constraints

Finally, we require that the amounts manufactured not exceed the demand determined by the markets for the products. We include the nonnegativity requirement with the market constraints.

Market Constraints

The linear model is complete. This simple case illustrates the required parts of the model. First we provide a word definition of each of the variables of the problem. Next we show the objective criterion with which alternatives are to be compared. Then we list the constraints that must be satisfed by a feasible solution. Each set of constraints should be named to describe the purpose of the constraint.

Solving the Model with the Excel Solver

Find the optimum product mix

The problem is to find values of P and Q that maximize the objective of the problem. We use the Mathematical Programming add-in to generate the model in Excel. The model is then solved with the Excel Solver. The worksheet with the model is shown below. Notice that the model has four constraints representing the machine times. The market constraints on production are represented as simple upper bounds. These could have been included in the constraint set, but expressing the simple upper bound approach is easier.

The solution is shown under P and Q in row 8. The optimum solution is to produce 100 units of P and 30 units of Q.

The net profit of this solution is $300. That is the $6300 shown in cell H5 on the worksheet, less the $6000 operating expense. The latter was not included in the model, because it does not affect the optimum decisions. Constant values are never included in the objective function.


Find the bottlenecks

From the value column, we see the amounts of time required by the optimum production quantities. Clearly, the time on machine B is a bottleneck for this situation. The market for P is also a bottleneck because the optimum value is at its upper bound. If either the time on machine B or the market for product P are increased, the profit will increase.

Find the range over which the unit profit may change

This result is determined from the sensitivity analysis. We show below the sensitivity analysis created by the Excel Solver. The two rows at the top provide information concerning the objective function. We see that the allowable increase in the objective coefficient for P is essentially infinity and the allowable decrease is 15. This means that the unit profit (objective coefficient) can range between 30 and infinity while the current solution ( P=100 and Q = 30) remains optimal. The unit profit of Q can range between 0 and 90 with the current solution remaining optimal. It should be emphasized that these ranges are correct only if one coefficient is changed at a time.


Find the marginal benefit of increasing the time availability

The bottom part of the sensitivity analysis, gives information concerning changes in the constraint coefficients. The top four rows of the table describe the upper bounds on the machine time constraints. The bottom four rows describe the lower bounds on the machine time constraints.The Mathmatical Programming add-in always provides both upper and lower bounds. Since the lower limits are large negative numbers in this case,, the bottom four rows provide no information.

In this table the column labeled Shadow Price gives the marginal benefits of increasing the time availability. For machines A, C and D the marginal benefit is zero. Since these machines are underutilized, there is obviously no benefit for providing additional minutes.

The shadow price for machine B is 2. This means that an extra minute of machine time yields an increase in profit of $2. This number is valid throughout the range indicated by the last two columns. That is, for product B, the shadow price of 2 is valid for any availability between 1500 and 3000 minutes.

Find the range over which the time availability may change

The allowable increase and decrease columns give the change in the constraint limit within which the current basis remains optimal. This means the bottlenecks remain the same in this range.

We learn from the row for A that the machine availability can go as low as 1800 and as high as infinity. Of course this is reasonable because this constraint is loose with 600 unused minutes for machine. Simlar comments can be made about machines C and D.

The range for machine B is from 1500 to 3000 minutes. Since this constraint is tight for the optimum solution, certainly as the time available for B changes, the amounts of products P and Q must change. The interesting result is that the time on machine B and the market for P remain the bottlenecks within the range.

Solving the Model with the Jensen LP Solver

Linear Programming Models may be solved with either the Excel Solver or the Jensen LP Solver. The latter is available if the LP Solver add-in has been installed. The figure below shows the results when the Jensen LP Solver is used. The only difference betwen the two forms is the absence of the yellow range from rows 2 to 8 in the first column. That region holds the model for the Excel Solver which is not necessary for the Jensen Solver.

The Jensen Solver yields a more convenient sensitivity analysis format adapted particularly to the format of the LP model. The lower and upper limits for each constraint are combined on a single line. The information shown is the same as that shown by the Excel Solver sensitivity analysis.

Operations Research Models and Methods
by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors