Linear Programming
Linear
programming (LP) is a specific type of optimization that help users determine
the optimal allocation of scarce resources in order to maximize profits,
minimize costs, obtain the best possible quality etc. It is applicable in a wide
variety of business areas for solving allocation problems. Some of the most
typical ones are production planning, workforce scheduling, financial portfolio
optimization and capital budgeting.
A linear programming problem contains
an objective function and a set of constraints, all of which are linear. The
problem is finding the best combination of activity levels, without using more
resources than are actually available.
Among many software packages that are
dedicated to solving linear programs, Microsoft Excel spreadsheet with its
Solver add-in is the one that we are focusing on. For illustrating formulation
of problems as LP models, solving them and interpreting the results, a product
mix problem (Example 3.1) would be pretty helpful.
The Monet Company produces four types of picture frames. Each type requires different amounts of skilled labor, metal and glass; and is sold for a different price. Given the limited amounts of these inputs, Monet wants to create a production plan that will maximize weekly profits, while only producing enough number of frames that can actually be sold. LP model will come up with the exact number of the four types of frames to be produced each week that will maximize weekly profits and that will meet the constraints at the same time.
Formulating
the Model:
A linear programming problem consists
of three parts, which are decision variables, the objective function and a set
of constraints.
-
Decision Variables
The first step of formulating a model is
identifying the decision variables. They are the controllable inputs of the
model describing the quantities that the decision makers want to find. Thus,
their values determine the solution of the model. In other words, they are the
unknowns of the model.
The decision variables are the number
of frames of type 1,2,3 and 4 to be produced, which are labeled x1,
x2, x3, and x4 respectively.
Decision Variables |
Label |
Number of type 1 frames to be produced |
X1 |
Number of type 2 frames to be produced |
X2 |
Number of type 3 frames to be produced |
X3 |
Number of type 4 frames to be produced |
X4 |
-
Objective Function
The next
step in formulating an LP model is defining the objective function, which must
be either maximization or minimization of a linear function. The objective
function depends on the decision variables and represents the goal of the
decision maker. For the Monet Company, the objective function is:
Maximizing 6 x1 + 2 x2 +
4 x3 + 3 x4
This means that Monet wants to find the number of
each type of frames to be produced, which gives the maximum value for weekly
profits. The coefficient of each decision variable in the objective function
represents the amount that each frame type contributes to profit, and it is
calculated as the unit selling price minus the cost of the inputs for a single
frame of each type. The total profit is obtained by adding up the profits from
the four products.
-Constraints
These are the real world limitations on
the decisions that come from the decision makers’ environment such as limited
resources, physical laws and contractual obligations. A constraint is an
equality or inequality that restricts the possible values a variable can take. Constraints
must be linear with the forms of ≤, ≥ or =. Strict inequalities
(< or >) are not permitted in an LP model.
The following inequalities restrict the
total number of labor hours that can be purchased to 4,000, the total ounces of
metal to 6,000 and the total ounces of glass to 10,000.
2 x1 + x2 +
3 x3 + 2 x4 ≤ 4,000 (labor constraint)
4 x1 + 2 x2 +
x3 + 2 x4 ≤ 6,000 (metal constraint)
6 x1 + 2 x2 + x3 +
2 x4 ≤ 10,000
(glass constraint)
The following market constraints
specify that it is impossible to sell more than 1,000 type 1 frames, 2,000 type
2 frames, 500 type 3 frames and 1,000 type 4 frames.
x1 ≤ 1,000 (frame 1 sales
constraint)
x2 ≤ 2,000 (frame 2 sales
constraint)
x3 ≤ 500 (frame 3 sales constraint)
x4 ≤ 1,000 (frame 4 sales
constraint)
Since producing a negative number of
products would make no sense, nonnegativity constraints should be added to the
LP model formula. The maximum sales constraints above and the nonnegativity
constraints below place upper and lower limits on the numbers of frames that
can be produced.
x1, x2,
x3, x4 ≥ 0
(nonnegativity constraints)
The resulting mathematical formulation of the linear
programming problem is:
maximize 6 x1 + 2
x2 + 4 x3 + 3 x4 subject to 2
x1 + x2
+ 3 x3
+ 2 x4 ≤ 4,000 4 x1 + 2 x2 + x3 + 2 x4 ≤ 6,000 6 x1 + 2 x2 + x3 + 2 x4 ≤ 10,000 x1 ≤ 1,000 x2 ≤ 2,000 x3 ≤ 500 x4 ≤ 1,000 x1, x2,
x3, x4 ≥
0
Having formulated the problem, it is
time to enter them into Excel. The spreadsheet includes four sections that are
the inputs, production plan, constraints on inputs & revenue, and cost
summary.
- Input data
We start
with entering the input parameters into the cells, which are enclosed in a blue
border. These are the uncontrollable inputs of the model that are usually given
constant quantitative values. Therefore, only numbers, not formulas are entered
into input cells. In this problem, the uncontrollable inputs are the unit
costs, which are $8.00 per labor hour, $0.50 per ounce of metal and $0.75 per
ounce of glass. Other inputs are the certain amounts of skilled labor, metal
and glass required for each type of frames and their unit selling prices.
- Production plan
In this section, we enter any values
for each frame type. Although we can use any trial values, Solver will find the
optimal values that satisfy all constraints. These are the cells that include
the decision variables. The range is named “Produced”, and bordered by red.
In this section, we can also reflect
the sales constraints by entering the maximum units of frames that can be sold
and call this range “MaxSales”.
- Constraints on inputs
In this
section, we enter SUMPRODUCT function to calculate the units of labor, metal
and glass used by the current product mix, and name the range as “Used”. To the
right of the “Used” range, the maximum available limits of these resources are
entered and the region is labeled as “Available”.
- Revenue, cost summary
At the
bottom of the spreadsheet model, the revenues and costs associated with each
product is calculated to get the final outcome, total profit.
The following snapshot of the model
includes the results for trail production values of 1000 for frame 1, 0 for
frame 2, 500 for frame 3, and 250 for frame 4.
Obtaining Results using Solver:
Once the
model has been created, the next step is invoking Solver to specify the
changing cells for decision variables, the target cell and the constraints in
order to ask Solver to find the optimal quantity of each frame type to maximize
the weekly profit.
To let Solver know the cells on the
spreadsheet that represent the decision variables, objective function and
constraints, we open the Solver dialog box. The sections that must be filled in
are:
- Target cell: It contains the value of the
objective function that we want to maximize. Therefore, we enter the Total
Profit (TotProfit) cell as the target cell, and click on the “Maximize” button.
- Changing cells: These are the cells that contain the decision variables. Solver changes the values in these cells to optimize the objective
function. Therefore, we enter the “Produced” range, which includes the numbers
of frames to produce, as the changing cells.
- Constraints: To indicate that no more
of each resource can be used than is available, we add the constraint “Used
<= Available”. To specify that its maximum sales level is the upper limit on
the quantity of each frame type to be produced, we add the constraint “Produced <= MaxSales”.
When the parameters have been entered,
the Solver Parameters dialog box looks like:
As the last step before clicking on
Solve button, we must specify that the changing cells must be kept nonnegative
by checking the “Assume Non-Negative” box in the Solver Options dialog box as
shown below. We also check the “Assume Linear Model” box to instruct Excel to
use the Simplex Method, which is the most efficient one for solving linear
models.
When we click on the “Solve” button in
the Solver Parameters dialog box, Solver finds the optimal solution by changing
the values for the decision variables, which are the number of each type of
frames to be produced. As shown in the following snapshot of the model, the
optimal production plan that maximizes weekly profit while satisfying the
constraints is to produce 1000 type 1 frames, 800 type 2 frames, 4000 type 3
frames and no type 4 frames.
Monet utilizes all of the available
labor hours and metal but only 8,000 of the10,000 ounces of glass available and
earns $9,200 profit. Although it can still produce more type 2, 3 and 4 frames
to meet their maximum sales constraints, it does not have enough labor and
metal for production. Therefore, the labor hours and metal availability
constraint, since they are met exactly, are the bottlenecks for this situation and
are called binding constraints. This means if either the labor hours or metal
availability are increased, the profit would increase. The glass availability
constraint, since it has 2,000 units of slack, is the nonbinding constraint of
production.
The details of the optimum solution are
given in the Solver’s Answer Report below. The original trial values and the
final values of the objective function and the decision variables, as well as
the status of each constraint are provided.
|
|
|
|
|
|
|
|
|
|
|
|
Microsoft
Excel 9.0 Answer Report |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
Target
Cell (Max) |
|
|
|
|
|
||
|
|
|
Cell |
Name |
Original Value |
Final Value |
|
|
|
|
|
|
$F$32 |
TotProfit |
$8,750 |
$9,200 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adjustable
Cells |
|
|
|
|
|
||
|
|
|
Cell |
Name |
Original Value |
Final Value |
|
|
|
|
|
|
$B$16 |
Type 1 frames produced |
1000 |
1000 |
|
|
|
|
|
|
$C$16 |
Type 2 frames produced |
0 |
800 |
|
|
|
|
|
|
$D$16 |
Type 3 frames produced |
500 |
400 |
|
|
|
|
|
|
$E$16 |
Type 4 frames produced |
250 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Constraints |
|
|
|
|
|
||
|
|
|
Cell |
Name |
Cell Value |
Formula |
Status |
Slack |
|
|
|
|
$B$21 |
Labor hours Used |
4000 |
$B$21<=$D$21 |
Binding |
0 |
|
|
|
|
$B$22 |
Metal (oz.) Used |
6000 |
$B$22<=$D$22 |
Binding |
0 |
|
|
|
|
$B$23 |
Glass (oz.) Used |
8000 |
$B$23<=$D$23 |
Not Binding |
2000 |
|
|
|
|
$B$16 |
Type 1 frames produced |
1000 |
$B$16<=$B$18 |
Binding |
0 |
|
|
|
|
$C$16 |
Type 2 frames produced |
800 |
$C$16<=$C$18 |
Not Binding |
1200 |
|
|
|
|
$D$16 |
Type 3 frames produced |
400 |
$D$16<=$D$18 |
Not Binding |
100 |
|
|
|
|
$E$16 |
Type 4 frames produced |
0 |
$E$16<=$E$18 |
Not Binding |
1000 |
|
|
|
|
|
|
|
|
|
|
|
Performing Sensitivity Analysis:
Sensitivity analysis can be performed
by clicking on “Sensitivity” in the dialog box that appears when Solver finds
the optimal solution to the problem:
The resulting Sensitivity Report
provides information on reduced costs, shadow prices, the upper and lower
allowable limits for decision variables and constraints.
|
|
|
|
|
|
|
|
|
|
|
|
|
Microsoft
Excel 9.0 Sensitivity Report |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Adjustable
Cells |
|
|
|
|
|
|
||
|
|
|
|
|
Final |
Reduced |
Objective |
Allowable |
Allowable |
|
|
|
|
Cell |
Name |
Value |
Cost |
Coefficient |
Increase |
Decrease |
|
|
|
|
$B$16 |
Type 1 frames produced |
1000 |
2 |
6 |
1E+30 |
2 |
|
|
|
|
$C$16 |
Type 2 frames produced |
800 |
0 |
2 |
1 |
0.25 |
|
|
|
|
$D$16 |
Type 3 frames produced |
400 |
0 |
4 |
2 |
0.5 |
|
|
|
|
$E$16 |
Type 4 frames produced |
0 |
0 |
3 |
0.2 |
1E+30 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Constraints |
|
|
|
|
|
|
||
|
|
|
|
|
Final |
Shadow |
Constraint |
Allowable |
Allowable |
|
|
|
|
Cell |
Name |
Value |
Price |
R.H. Side |
Increase |
Decrease |
|
|
|
|
$B$21 |
Labor hours Used |
4000 |
1.20 |
4000 |
250 |
1000 |
|
|
|
|
$B$22 |
Metal (oz.) Used |
6000 |
0.40 |
6000 |
2000 |
500 |
|
|
|
|
$B$23 |
Glass (oz.) Used |
8000 |
0.00 |
10000 |
1E+30 |
2000 |
|
|
|
|
|
|
|
|
|
|
|
|
The first part of the report gives
information concerning the objective function. The allowable increase/decrease
represents the range in which the current solution remains optimal. We see that
the unit profit (the objective function coefficient) of type 1 frames would
have to decrease by $2.00 for the current product mix to change. The unit profit for type 2 frames can
range between $1.75 and $3.00, whereas that of type 3 can be between $3.50 and
$6.00 with the current product mix remaining optimal. But, the unit profit for
type 4 frames would have to increase by $0.20 before they can start to be
produced. It should also be noted that the ranges above are valid only if one
coefficient is altered at a time.
Reduced cost refers to the increase in profit by producing one more unit
of a product. Therefore, Monet’s profit can increase by $2 if it produces an
extra unit of Type 1 frames, whereas producing additional amounts of other
frame types would lead to no extra gains.
The second part of the sensitivity
report gives information about the constraints. The shadow price refers to the
marginal increase in profit by obtaining an extra unit of a resource. Therefore,
it is the maximum amount that the company is willing to pay for an extra unit.
We conclude that Monet is willing to pay $1.20 for each additional labor hour
between 3,000 and 4,250 hours, $0.4 for each extra ounce of metal between 5,500
and 8,000 ounces. Since glass is underutilized by 2,000 ounces, there is no
need for purchasing any additional units. Thus, its shadow price is $0.
To see the impact of changes in one or
more constraints on the optimal profit and the optimal product mix, we also
perform a sensitivity analysis by using the SolverTable add-in. To measure the
effect of a change in a single input on any number of outputs, a “one-way”
table is used. The impact of simultaneous changes in two inputs on one output
is determined by a “two-way” table.
To illustrate the use of SolverTable
for one-way sensitivity analysis, we can measure the sensitivity of outputs to
variations in the number of labor hours available. We start by selecting a
one-way table in the Data/SolverTable dialog box, and fill in the next dialog
box as shown below:
The cell including the number of labor hours available is
selected as the input cell. Then, the desired minimum and maximum values of
inputs are entered. At the bottom of the dialog box, we specify the number of
each type of frame to be produced and the total profit as the outputs.
SolverTable returns the following output table:
|
|
|
|
|
|
|
|
|
|
|
|
Sensitivity of optimal solution to number of labor hours |
|
|
|
||||
|
|
|
Frames produced
|
|
|
|
|||
|
|
Labor hours
|
1 |
2 |
3 |
4 |
Total profit |
|
|
|
|
|
$B$16 |
$C$16 |
$D$16 |
$E$16 |
$F$32 |
Increase |
|
|
|
2500 |
1000 |
500 |
0 |
0 |
$7,000 |
|
|
|
|
2750 |
1000 |
750 |
0 |
0 |
$7,500 |
$500 |
|
|
|
3000 |
1000 |
1000 |
0 |
0 |
$8,000 |
$500 |
|
|
|
3250 |
1000 |
950 |
100 |
0 |
$8,300 |
$300 |
|
|
|
3500 |
1000 |
900 |
200 |
0 |
$8,600 |
$300 |
|
|
|
3750 |
1000 |
850 |
300 |
0 |
$8,900 |
$300 |
|
|
|
4000 |
1000 |
800 |
400 |
0 |
$9,200 |
$300 |
|
|
|
4250 |
1000 |
750 |
500 |
0 |
$9,500 |
$300 |
|
|
|
4500 |
1000 |
500 |
500 |
250 |
$9,750 |
$250 |
|
|
|
4750 |
1000 |
250 |
500 |
500 |
$10,000 |
$250 |
|
|
|
5000 |
1000 |
0 |
500 |
750 |
$10,250 |
$250 |
|
|
|
|
|
|
|
|
|
|
|
We
can see that for any available labor hour values between 2,500 and 5,000, the quantity of type 1 frames to be
produced does not change. But, type 2
frames would be discontinued
if 5,000 labor hours were available. The production of type 3 frames would start at 3,250 labor hours and frames of type 4
would finally be produced when 4,500
labor hours are available.
In the last column of the table above, we can track how
labor hours increase the total profit. Although this is not automatically
produced by SolverTable add-in, we can easily compute it on the spreadsheet. It
is clear that having extra labor hours adds to profit. But the increase in
profit per extra hour, called the shadow price of labor hours, decreases as
more hours are obtained. We can graph the optimal profit values versus the
available labor hours to display how shadow price, which is the slope of the
line, decreases as more labor hours are purchased.