Chapter 2 Introduction to Optimisation.ppt

This shows how optimisation can be used to make the most efficient use of limited resources in businesses to make the optimal decision in terms of maximising profits or minimising costs. It is well explained and very detailed. Might even include some linear programming.

1. 1
Spreadsheet Modeling &
Decision Analysis
A Practical Introduction to
Management Science
4
th
edition
Cliff T. Ragsdale

2. 2
Introduction to Optimization
and Linear Programming
Chapter 2

3. 3
Introduction
•We all face decision about how to use
limited resources such as:
–Oil in the earth
–Land for dumps
–Time
–Money
–Workers

4. 4
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

5. 5
Applications of Optimization
•Determining Product Mix
•Manufacturing
•Routing and Logistics
•Financial Planning

6. 6
Characteristics of Optimization
Problems
•Decisions
•Constraints
•Objectives

7. 7
General Form of an Optimization Problem
MAX (or MIN): f
0(X
1, X
2, …, X
n)
Subject to:f
1(X
1, X
2, …, X
n)<=b
1
:
f
k(X
1, X
2, …, X
n)>=b
k
:
f
m
(X
1
, X
2
, …, X
n
)=b
m
Note: If all the functions in an optimization are linear,
the problem is a Linear Programming (LP) problem

8. 8
Linear Programming (LP) Problems
MAX (or MIN):c
1
X
1
+ c
2
X
2
+ … + c
n
X
n
Subject to: a
11X
1 + a
12X
2 + … + a
1nX
n <= b
1
:
a
k1X
1 + a
k2X
2 + … + a
knX
n >=b
k
:
a
m1X
1 + a
m2X
2 + … + a
mnX
n = b
m

9. 9
An Example LP Problem
Blue Ridge Hot Tubs produces two types of hot
tubs: Aqua-Spas & Hydro-Luxes.
There are 200 pumps, 1566 hours of labor,
and 2880 feet of tubing available.
Aqua-Spa Hydro-Lux
Pumps 1 1
Labor 9 hours 6 hours
Tubing 12 feet 16 feet
Unit Profit$350 $300

10. 10
5 Steps In Formulating LP Models:
1. Understand the problem.
2. Identify the decision variables.
X
1=number of Aqua-Spas to produce
X
2=number of Hydro-Luxes to produce
3.State the objective function as a linear
combination of the decision variables.
MAX: 350X
1 + 300X
2

11. 11
5 Steps In Formulating LP Models
(continued)
4. State the constraints as linear combinations
of the decision variables.
1X
1
+ 1X
2
<= 200} pumps
9X
1 + 6X
2 <= 1566 } labor
12X
1 + 16X
2 <= 2880} tubing
5. Identify any upper or lower bounds on the
decision variables.
X
1 >= 0
X
2
>= 0

12. 12
LP Model for Blue Ridge Hot Tubs
MAX: 350X
1 + 300X
2
S.T.:1X
1 + 1X
2 <= 200
9X
1
+ 6X
2
<= 1566
12X
1
+ 16X
2
<= 2880
X
1 >= 0
X
2 >= 0

13. 13
Solving LP Problems:
An Intuitive Approach
•Idea: Each Aqua-Spa (X
1
) generates the highest unit
profit ($350), so let’s make as many of them as possible!
•How many would that be?
–Let X
2
= 0
•1st constraint:1X
1
<= 200
•2nd constraint:9X
1
<=1566 or X
1
<=174
•3rd constraint:12X
1
<= 2880 or X
1
<= 240
•If X
2
=0, the maximum value of X
1
is 174 and the total
profit is $350*174 + $300*0 = $60,900
•This solution is feasible, but is it optimal?
•No!

14. 14
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.

15. 15
X
2
X
1
250
200
150
100
50
0
0 50 100 150 200 250
(0, 200)
(200, 0)
boundary line of pump constraint
X
1 + X
2 = 200
Plotting the First Constraint

16. 16
X
2
X
1
250
200
150
100
50
0
0 50 100 150 200 250
(0, 261)
(174, 0)
boundary line of labor constraint
9X
1 + 6X
2 = 1566
Plotting the Second Constraint

17. 17
X
2
X
1
250
200
150
100
50
0
0 50 100 150 200 250
(0, 180)
(240, 0)
boundary line of tubing constraint
12X
1 + 16X
2 = 2880
Feasible Region
Plotting the Third Constraint

18. 18
X
2
Plotting A Level Curve of the
Objective Function
X
1
250
200
150
100
50
0
0 50 100 150 200 250
(0, 116.67)
(100, 0)
objective function
350X
1
+ 300X
2
= 35000

19. 19
A Second Level Curve of the Objective
FunctionX
2
X
1
250
200
150
100
50
0
0 50 100 150 200 250
(0, 175)
(150, 0)
objective function
350X
1 + 300X
2 = 35000
objective function
350X
1 + 300X
2 = 52500

20. 20
Using A Level Curve to Locate
the Optimal Solution
X
2
X
1
250
200
150
100
50
0
0 50 100 150 200 250
objective function
350X
1 + 300X
2 = 35000
objective function
350X
1 + 300X
2 = 52500
optimal solution

21. 21
Calculating the Optimal Solution
•The optimal solution occurs where the “pumps” and “labor”
constraints intersect.
•This occurs where:
X
1 + X
2 = 200 (1)
and 9X
1 + 6X
2 = 1566(2)
•From (1) we have, X
2 = 200 -X
1(3)
•Substituting (3) for X
2 in (2) we have,
9X
1
+ 6 (200 -X
1
) = 1566
which reduces to X
1 = 122
•So the optimal solution is,
X
1
=122, X
2
=200-X
1
=78
Total Profit = $350*122 + $300*78 = $66,100

22. 22
Enumerating The Corner Points
X
2
X
1
250
200
150
100
50
0
0 50 100 150 200 250
(0, 180)
(174, 0)
(122, 78)
(80, 120)
(0, 0)
obj. value = $54,000
obj. value = $64,000
obj. value = $66,100
obj. value = $60,900obj. value = $0
Note: This technique will not work if
the solution is unbounded.

23. 23
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

24. 24
Special Conditions in LP Models
•A number of anomalies can occur in
LP problems:
–Alternate Optimal Solutions
–Redundant Constraints
–Unbounded Solutions
–Infeasibility

25. 25
Example of Alternate Optimal
SolutionsX
2
X
1
250
200
150
100
50
0
0 50 100 150 200 250
450X
1
+ 300X
2
= 78300
objective function level curve
alternate optimal solutions

26. 26
Example of a Redundant Constraint
X
2
X
1
250
200
150
100
50
0
0 50 100 150 200 250
boundary line of tubing constraint
Feasible Region
boundary line of pump constraint
boundary line of labor constraint

27. 27
Example of an Unbounded
Solution
X
2
X
1
1000
800
600
400
200
0
0 200 400 600 800 1000
X
1
+ X
2
= 400
X
1 + X
2 = 600
objective function
X
1
+ X
2
= 800
objective function
-X
1
+ 2X
2
= 400

28. 28
Example of Infeasibility
X
2
X
1
250
200
150
100
50
0
0 50 100 150 200 250
X
1 + X
2 = 200
X
1
+ X
2
= 150
feasible region for
second constraint
feasible region
for first constraint

29. 29
End of Chapter 2