Operations Research Models and Methods / Models /
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.
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
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
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
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
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
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
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
Operations Research Models and Methods
by Paul A. Jensen and Jon Bard, University of Texas, Copyright
by the Authors