Spreadsheet Modeling and
Decision Analysis
DSO 547
Prof Dasgupta
Lecture 4
Linear Programming
1
Agenda
Linear Programming recap of essentials
Excel Modeling tips for Linear Programming
Classwork
Homework Review
Copyright 2013 John
Wiley & Sons, Inc.
LP recap of essentials
We all face decision about how to use
limited resources such as:
Oil in the earth
Land for dumps
Time
Money
Workers
Mathematical Programming...
MP is a field of management science that
finds the optimal, or most efficient, way of
using limited resources to achieve the
objectives of an individual of a business.
a.k.a. Optimization
What is optimization?
Determining
the best values for a set of decisions
subject to a set of constraints
in order to maximize/minimize some objective function
Used to solve problems with:
Competing mechanisms
Resource allocation issues
Implementation/delivery constraints
A furniture company would like to determine
the quantity of chairs/desks/tables to manufacture
subject to production capacities and inventory limits
in order to maximize profit
Applications of Optimization
Determining Product Mix
Manufacturing
Routing and Logistics
Financial Planning
Characteristics of
Optimization Problems
Decisions
Constraints
Objectives
General Form of an Optimization Problem
MAX (or MIN): f0(X1, X2, , Xn)
Subject to: f1(X1, X2, , Xn)<=b1
:
fk(X1, X2, , Xn)>=bk
:
fm(X1, X2, , Xn)=bm
Note: If all the functions in an optimization are linear, the problem is a
Linear Programming (LP) problem
Classes of optimization problems
Optimization
Linear
Non-Linear
Requirements:
Objective formula is linear
All constraints are linear
Requirements:
(none)
We focus on LINEAR optimization problems
Guaranteed Solution
Computationally Efficient
Easy to construct
Model Classification
Linear optimization or linear programming
Objective and all constraints are linear functions of the
decision variables.
Nonlinear optimization or nonlinear programming
Either objective or a constraint (or both) are nonlinear
functions of the decision variables.
Techniques for solving linear models are more
powerful.
Use wherever possible.
Chapter 9
Copyright 2013 John
Wiley & Sons, Inc.
10
10
Linear Programming (LP) Problems
MAX (or MIN):
c1X1 + c2X2 + + cnXn
Subject to:
a11X1 + a12X2 + + a1nXn <= b1
:
ak1X1 + ak2X2 + + aknXn >=bk
:
am1X1 + am2X2 + + amnXn = bm
11
So what is linear?
The function used must fit the format:
f(x) = c1x1 + c2x2 + + cnxn
Distinct variable
Constant value
In math-speak:
1.
Additivity: each variable is a distinct term in the objective formula
2.
Proportionality contribution from each variable proportional to its magnitude
3.
Divisibility a fractional decision is (at least approximately) meaningful
Example: profit = ($100/unit)*(# sold) ($50/unit)(# made) (fixed cost)
12
12
Steps in LP problem formulation
1. Define the decision variables
managerial levers
2. Write the objective formula
optimization problem
as a linear function of these variables
3. Write the constraints
resource limitations
as a linear function of these variables
4. (Determine variable restrictions to be explored later)
Didnt work?
Redefine your decision variables in a clever way and try again!
13
13
An Example LP Problem
Blue Ridge Hot Tubs produces two types of hot tubs: AquaSpas & Hydro-Luxes.
Pumps
Labor
Tubing
Unit Profit
Aqua-Spa
1
9 hours
12 feet
$350
Hydro-Lux
1
6 hours
16 feet
$300
There are 200 pumps, 1566 hours of labor, and 2880
feet of tubing available.
14
5 Steps In Formulating LP Models:
1. Understand the problem.
2. Identify the decision variables.
X1=number of Aqua-Spas to produce
X2=number of Hydro-Luxes to produce
3. State the objective function as a linear
combination of the decision variables.
MAX: 350X1 + 300X2
15
5 Steps In Formulating LP Models
(continued)
4. State the constraints as linear combinations of the decision
variables.
1X1 + 1X2 <= 200 } pumps
9X1 + 6X2 <= 1566 } labor
12X1 + 16X2 <= 2880 } tubing
5. Identify any upper or lower bounds on the decision
variables.
X1 >= 0
X2 >= 0
16
LP Model for
Blue Ridge Hot Tubs
MAX: 350X1 + 300X2
S.T.: 1X1 + 1X2 <= 200
9X1 + 6X2 <= 1566
12X1 + 16X2 <= 2880
X1 >= 0
X2 >= 0
17
Solving LP Problems:
An Intuitive Approach
Idea: Each Aqua-Spa (X1) generates the highest unit profit ($350), so lets
make as many of them as possible!
How many would that be?
Let X2 = 0
1st constraint: 1X1 <= 200
2nd constraint: 9X1 <=1566 or X1 <=174
3rd constraint: 12X1 <= 2880 or X1 <= 240
If X2=0, the maximum value of X1 is 174 and the total profit is $350*174 +
$300*0 = $60,900
This solution is feasible, but is it optimal?
No!
18
Solving LP Problems:
A Graphical Approach
The constraints of an LP problem defines its
feasible region.
The best point in the feasible region is the
optimal solution to the problem.
For LP problems with 2 variables, it is easy to plot
the feasible region and find the optimal solution.
19
X2
Plotting the First Constraint
250
(0, 200)
200
boundary line of pump constraint
X1 + X2 = 200
150
100
50
(200, 0)
0
0
50
100
150
200
250
X1
X2
(0, 261)
Plotting the Second Constraint
250
boundary line of labor constraint
9X1 + 6X2 = 1566
200
150
100
50
(174, 0)
0
50
100
150
200
250
X1
Plotting the Third Constraint
X2
250
(0, 180)
200
150
boundary line of tubing constraint
12X1 + 16X2 = 2880
100
Feasible Region
50
(240, 0)
0
0
50
100
150
200
250
X1
Plotting A Level Curve of the
Objective Function
X2
250
200
(0, 116.67)
objective function
150
350X1 + 300X2 = 35000
100
(100, 0)
50
0
0
50
100
150
200
250
X1
A Second Level Curve of the
Objective Function
X2
250
(0, 175)
200
objective function
350X1 + 300X2 = 35000
objective function
350X1 + 300X2 = 52500
150
100
(150, 0)
50
0
0
50
100
150
200
2014 Cengage Learning. All Rights Reserved. May not be
scanned, copied or duplicated, or posted to a publicly accessible
website, in whole or in part.
250
X1
Using A Level Curve to Locate
the Optimal Solution
X2
250
objective function
350X1 + 300X2 = 35000
200
150
optimal solution
350X1 + 300X2 = 66100
100
objective function
350X1 + 300X2 = 52500
50
0
0
50
100
150
200
250
X1
Calculating the Optimal Solution
The optimal solution occurs where the pumps and labor
constraints intersect.
This occurs where:
X1 + X2 = 200
(1)
and 9X1 + 6X2 = 1566
(2)
From (1) we have, X2 = 200 -X1
(3)
Substituting (3) for X2 in (2) we have,
9X1 + 6 (200 -X1) = 1566
which reduces to X1 = 122
So the optimal solution is,
X1=122, X2=200-X1=78
Total Profit = $350*122 + $300*78 = $66,100
2014 Cengage Learning. All Rights Reserved. May not be
scanned, copied or duplicated, or posted to a publicly accessible
website, in whole or in part.
26
Enumerating The Corner Points
X2
250
obj. value = $54,000
(0, 180)
200
Note: This technique will not work if the
solution is unbounded.
obj. value = $64,000
150
(80, 120)
obj. value = $66,100
(122, 78)
100
50
obj. value = $60,900
(174, 0)
obj. value = $0
(0, 0)
0
0
50
100
150
200
250
X1
Summary of Graphical Solution
to LP Problems
1. Plot the boundary line of each constraint
2. Identify the feasible region
3. Locate the optimal solution by either:
a. Plotting level curves
b. Enumerating the extreme points
28
Sensitivity Analysis:
Understanding How Things Change
See file Blue Ridge Hot Tub
29
Special Conditions in LP Models
A number of anomalies can occur in LP
problems:
Alternate Optimal Solutions
Redundant Constraints
Unbounded Solutions
Infeasibility
30
Example of Alternate Optimal Solutions
X2
250
objective function level curve
450X1 + 300X2 = 78300
200
150
100
alternate optimal solutions
50
0
0
50
100
150
200
250
X1
X2
Example of a Redundant Constraint
250
boundary line of tubing constraint
200
boundary line of pump constraint
150
boundary line of labor constraint
100
Feasible Region
50
0
0
50
100
150
200
250
X1
X2
Example of an Unbounded Solution
1000
objective function
X1 + X2 = 600
800
-X1 + 2X2 = 400
objective function
X1 + X2 = 800
600
400
200
X1 + X2 = 400
0
0
200
400
600
800
1000
X1
Example of Infeasibility
X2
250
200
X1 + X2 = 200
feasible region for
second constraint
150
100
feasible region for
first constraint
50
X1 + X2 = 150
0
0
50
100
150
200
2014 Cengage Learning. All Rights Reserved. May not be
scanned, copied or duplicated, or posted to a publicly accessible
website, in whole or in part.
250
X1
Classwork - Example : Boat Manufacturer
A boat manufacturer facing unlimited demand wants to maximize profit.
They earn $1200 per sailboat sold, and $1000 per motorboat.
Per-unit parts needs and inventory follow this chart
Sailcloth
Glass Fiber
Engines
Sailboat
Unit Reqmt
4
8
0
Motorboat
Unit Reqmt
0
4
1
Inventory Total
400
1000
120
How many of each boat should they make?
35
35
Our solution, graphically
M
Maximize
(65, 120)
(0, 120)
1200S + 1000M
Subject to 4S + 0M 400
8S + 4M 1000
0S + 1M 120
S, M 0
[feasible zone]
(100, 0)
Which of these
constraints are
binding?
36
36
Excel Mini-Lesson: The
SUMPRODUCT Function
The SUMPRODUCT function in Excel takes the
pairwise products of two sets of numbers and
sums the products.
SUMPRODUCT(Array1,Array2)
Array1 references the first set of numbers.
Array2 references the second set of numbers.
The two arrays must have identical layouts and be
the same size.
Chapter 9
Copyright 2013 John
Wiley & Sons, Inc.
37
37
(Cont.)
38
38
Veerman Furniture Company
39
Example : An Allocation Model
Veerman Furniture Company (p. 221)
The company makes chairs, desks, tables.
Each product has estimated average labor inputs of hours per unit in
departments of fabrication, assembly, and shipping.
Total available labor in fabrication, assembly and shipping departments is capped,
based on each departments capacities
Additionally, estimated demand potential shows maximum unit sales, per
product
How do we maximize profit?
40
40
Dahlby Outfitters
41
Dahlby: A Covering Model
What is the business problem about?
We are a packaged goods company. Want to develop a new trail mix
product.
We have available a list of potential ingredients.
For each ingredient we know:
Cost per pound
Nutritional contribution in grams per pound
Finally, we seek to meet minimum overall nutritional requirements, in
order to cater to a particular customer segment.
How large of a package would meet these requirements?
42
42
Diaz Coffee Company
43
Example: A Blending Model
Diaz Coffee Company (p. 230)
We want to make at least 4 million lbs of coffee blend
Target characteristics are:
Minimum aroma rating of 78
Minimum strength rating of 16
The available export grade coffees are:
Bean
Aroma
Rating
Strength
Rating
Cost/lb.
Lbs available
Brazilian
75
15
$0.50
1,500,000
Colombian
60
20
$0.60
1,200,000
Peruvian
85
18
$0.70
2,000,000
44
44
Example: Advertising Mix
A cable television advertising campaign is aimed at three demographic groups:
single adult males, single adult females, and married couples.
The campaign requires 500,000 viewers among the single males, and 200,000
viewers in each of the other two groups.
Five channels are available, each with its own audience demographics. The table
below shows the number of viewers of each type per $1,000 of advertising for
each of the five channels.
Channel
Channel
Channel
Channel
Channel
1
2
3
4
5
Single
Men
Single
Women
Couples
300
100
0
2000
750
850
900
1200
0
500
1200
2000
800
200
500
That is, $2000 spent on channel 2 would reach 200 Single Men,
1800 Single Women, and 4,000 couples, etc.
What is the
optimization
problem?
45
45
Summary
Linear programming represents the most widely used
optimization technique in practice.
The special features of a linear program are a linear
objective function and linear constraints.
Linearity in the optimization model allows us to apply the
simplex method as a solution procedure, which in turn
guarantees finding a global optimum whenever an
optimum of any kind exists.
Therefore, when we have a choice, we are better off with
a linear formulation of a problem than with a nonlinear
formulation.
Chapter 9
Copyright 2013 John
Wiley & Sons, Inc.
46
46
Summary
While optimization is a powerful technique, we should not
assume that a solution that is optimal for a model is also
optimal for the real world.
Often, the realities of the application will force changes in
the optimal solution determined by the model.
One powerful method for making this translation is to look
for the pattern, or the economic priorities, in the optimal
solution.
These economic priorities are often more valuable to
decision makers than the precise solution to a particular
instance of the model.
Chapter 9
Copyright 2013 John
Wiley & Sons, Inc.
47
47
