Optimisation

Part 2
Recapping linear programming
Solving integer programs

Record
!
Optimisation
Part 2
Recapping linear programming
Solving integer programs
Reminder:
Before the Easter break
 We talked about what  We saw how to model a
optimisation is. problem from a worded
 description (making skis, and
We talked about the different
distributing umbrellas)
types of optimisation, and the
two we will focus on (LP’s and  We saw how to set this up in
IP’s) excel to solve it
 We laid out the three parts of
an optimisation model  We looked at the graphical
 Decision variables simplex method to understand
 Objective function and value what’s happening behind-the-
scenes.
 Set of constraints
Reminder: The two types of
optimisation on this module
Linear (LP) Last Integer (IP)
time Today
 Linear programming is the  Integer programming is much
‘easiest’ type of optimisation ‘harder’ than linear
 It relies on the fact that  It has a similar setup to an LP
variables can take any value,  But with the added constraint
so long as the constraints are
that every variable can only
satisfied
take integer values
 There are many methods but  This complicates the problem
the most common is the
more than you might expect
Simplex method.
 The most common method for
 We will not cover the full
IP’s is Branch & Bound
simplex method, but will see
examples of graphical simplex!
Reminder: Read the whole problem
 Sklenka Ski Company (SSC) is a small manufacturer of two types of
popular all-terrain snow skis, the Jordanelle and the Deercrest models.
 The manufacturing process consists of two principal departments:
fabrication and finishing. The fabrication department has 12 skilled
workers, each of whom works seven hours per day. The finishing
department has three workers, who also work a seven-hour shift. Each pair
of Jordanelle skis requires 3.5 labor-hours in the fabricating department
and 1 labor-hour in finishing. The Deercrest model requires 4 labor-hours in
fabricating and 1.5 labor-hours in finishing. The company operates five
days per week.
 SSC makes a net profit of £50 on the Jordanelle model and £65 on the
Deercrest model.
 In anticipation of the next ski-sale season, SSC must plan its production of
these two models. Because of the popularity of its products and limited
production capacity, its products are in high demand, and SSC can sell all it
can produce each season.
 The company anticipates selling at least twice as many Deercrest models
as Jordanelle models. The company wants to determine how many of each
model should be produced on a daily basis to maximize net profit.
Reminder: pick out the key details

 Two types of skis: Jordanelle and Deercrest.

 Manufacturing consists of two departments: fabrication and finishing.
 Fabrication has 12 workers, finishing has 3. All work seven hours per
day.
 Jordanelles require 3.5 hours of fabricating and 1 hour of finishing.
 Deercrests require 4 hours of fabricating and 1.5 hours of finishing.
 The company operates five days per week.
 £50 profit on Jordanelle, £65 profit on Deercrest.
 SSC can sell all it can produce.
 Sell at least twice as many Deercrests as Jordanelles.
 Determine how many of each model should be produced on a daily
basis to maximize net profit.
 I recommend you keep this definition slide open for the next steps.
Reminder: identify variables,
objective, and constraints
 Two types of skis: Jordanelle and Deercrest.
 Manufacturing consists of two departments: fabrication and finishing.
 Fabrication has 12 workers, finishing has 3. All work seven
hours per day.
 Jordanelles require 3.5 hours of fabricating and 1 hour of
finishing.
 Deercrests require 4 hours of fabricating and 1.5 hours of
finishing.
 The company operates five days per week.
 £50 profit on Jordanelle, £65 profit on Deercrest.
 SSC can sell all it can produce.
 Sell at least twice as many Deercrests as Jordanelles.
 Determine how many of each model should be produced on a
daily basis to maximize net profit.
Reminder: Put it all together as a
model
 Variables:
 J = the number of Jordanelles produced per day
 D = the number of Deercrests produced per day
 Objective:
 Maximise P = 50J + 65D
 Constraints:
 3.5J + 4D ≤ 84
 1J + 1.5D ≤ 21
 2J – D ≤ 0
 One final constraint sets the domains of the variables:
 J≥0
 D≥0
Reminder: Excel solver

 Our model:
 Maximise P = 50J +
65D
 3.5J + 4D ≤ 84
 1J + 1.5D ≤ 21
 2J – D ≤ 0
 J ≥ 0, D ≥ 0
 J = number
Jordanelles produced
per day
 D = number
Deercrests produced
per day
 Reminder: Graphical simplex
 First thing we do is plot the constraints

 Our model:
 Maximise P = 50J +
65D
 3.5J + 4D ≤ 84
 1J + 1.5D ≤ 21
 2J – D ≤ 0
 J ≥ 0, D ≥ 0
 J = number
Jordanelles produced
per day
 D = number
Deercrests produced
per day
 Reminder: Graphical simplex
 Then identify the feasible region

 Our model:
 Maximise P = 50J +
65D
 3.5J + 4D ≤ 84
 1J + 1.5D ≤ 21
 2J – D ≤ 0
 J ≥ 0, D ≥ 0
 J = number
Jordanelles produced
per day
 D = number
Deercrests produced
per day
 Example: Graphical simplex
 Check the direction of the objective function to see which corner is
best

 Our model:
 Maximise P = 50J +
65D
 3.5J + 4D ≤ 84 P=100
 1J + 1.5D ≤ 21 0
 2J – D ≤ 0 P=60

0
J ≥ 0, D ≥ 0
 J = number P=30
Jordanelles produced 0
per day
 D = number
Deercrests produced
per day P=0
 Reminder: Graphical simplex
 Finally, identify the optimal solution

 Our model:
 Maximise P = 50J +
65D
 3.5J + 4D ≤ 84
 1J + 1.5D ≤ 21
 2J – D ≤ 0
 J ≥ 0, D ≥ 0
 J = number
Jordanelles produced
per day
 D = number
Deercrests produced
per day
Reminder: The two types of
optimisation on this module
Linear (LP) Last Integer (IP)
time Today
 Linear programming is the  Integer programming is much
‘easiest’ type of optimisation ‘harder’ than linear
 It relies on the fact that  It has a similar setup to an LP
variables can take any value,  But with the added constraint
so long as the constraints are
that every variable can only
satisfied
take integer values
 There are many methods but  This complicates the problem
the most common is the
more than you might expect
Simplex method.
 The most common method for
 We will not cover the full
IP’s is Branch & Bound
simplex method, but will see
examples of graphical simplex!
Integer Programming
Why is it so hard?
 The modelling stage is the  Behind the scenes:
same, apart from the domains.  To solve an integer program we
Change:
solve lots of slightly different
 J ≥ 0, D ≥ 0 to be linear programs
 J, D ∈ ℤ or J, D are integer  That’s why it’s “harder”, it
 The difficulty comes in solving. takes much more
computational power
 For Excel solver we won’t see
the difference
 At large scale it makes a
massive difference!
Integer Programming
Why is it so hard?
 The feasible region of an IP
looks quite different.
 The bounds are the same as
the equivalent LP, but now the
corners are not solutions!
 We can’t just find the best
corner and round it. This would
give a feasible solution, but not
necessarily the optimal
solution.
 The methods are much more
complex.
Solving Integer Programs:
The Branch & Bound method
 Starts by completely ignoring  An example model:
the need to make our variables  Maximise:
integer.

4x + 5y
This is called the linear
relaxation of the problem.  Constraints:
 It is solved the same way we x + 4y ≤ 10
solve any LP. 3x – 4y ≤ 6
 Then new constraints are x, y ≥ 0
added to make any non-integer
variables be integers! x, y integer
Solving Integer Programs:
The Branch & Bound method
 An example model:
 Maximise:
4x + 5y
 Constraints:
x + 4y ≤ 10
3x – 4y ≤ 6
x, y ≥ 0
x, y integer
 Plot the feasible region:
Solving Integer Programs:
The Branch & Bound method
 An example model:  Solving this as an LP gives the
 solution:
Maximise:
 x = 4, y = 1.5
z = 4x + 5y
 Valid LP solution, invalid IP
 Constraints:
solution.
x + 4y ≤ 10  Branch the problem with new
3x – 4y ≤ 6 constraints:
x, y ≥ 0  y ≥ 2 and y ≤1

 Ignore integer constraint, solve

LP
Branch and Bound: the overview
 An example model:
 Maximise:
z = 4x +
5y
 Constraints:
x + 4y ≤
10
3x – 4y ≤ 6
x, y ≥ 0
x, y are
integers
 In every box we solve
an IP
 Some boxes will be
pruned, reducing the
Branch and Bound: pruning
 Pruning ends a branch
 This means we don’t have to
fully enumerate the whole
problem space.
 Three types of pruning:
 Integrality:
 All variables are integer from
the LP solve, no new
constraints need to be
added.
 Infeasibility:
 The LP has no feasible
solution.
 Bounded:
 The solution offered by the
LP is worse than the best
Do you need to be able to do branch
and bound?
 No!  The key thing you need to
 understand is the modelling
This is the same as when I
process.
showed you graphical simplex
last time.  Also, how to pass a model into
 Excel solver.
I want you to understand the
methods you’re using.  So let’s see that again now!
 In practice (and the exam) this
is all covered by software.  Reminder: the modelling
 If you go onto more advanced process is the same for LP’s
optimisation, the software will and IP’s
change, but you still won’t
have to implement the
methods.
Example 1
Choosing fertiliser blends
Example: Choosing fertiliser blends

 A farmer has two brands of fertiliser available to him, with different

chemical compositions.
 He has evaluated the performance of different chemicals on his crops
and wants to ensure that the field he is covering is fed with at least
16 kilograms of Nitrogen and 24 kilograms of Phosphate.
 Fertiliser blend 1 is named Super-Gro. Each bag of Super-Gro contains
2kg of Nitrogen and 4kg of Phosphate.
 Fertiliser blend 2 is named Crop-Quick. Each bag contains 4kg of
Nitrogen and 3kg of phosphate.
 A bag of Super-Gro costs £6, and a bag of Crop-Quick costs £3.
 The farmer wants to know how many bags of each blend to buy to
satisfy his requirements while minimising the total cost.
Step 1: Define variables
What can we change?
 A farmer has two brands of fertiliser available to him, with different
chemical compositions.
 He has evaluated the performance of different chemicals on his crops
and wants to ensure that the field he is covering is fed with at least
16 kilograms of Nitrogen and 24 kilograms of Phosphate.
 Fertiliser blend 1 is named Super-Gro. Each bag of Super-Gro contains
2kg of Nitrogen and 4kg of Phosphate.
 Fertiliser blend 2 is named Crop-Quick. Each bag contains 4kg of
Nitrogen and 3kg of phosphate.
 A bag of Super-Gro costs £6, and a bag of Crop-Quick costs £3.
 The farmer wants to know how many bags of each blend to buy
to satisfy his requirements while minimising the total cost.
Step 1: Define variables
What can we change?
 We will have two variables.
 The variables will be the number of bags of each blend we buy.
 Let’s name them:
 A = number of bags of super-gro purchased
 B = number of bags of crop-quick purchased
Step 2: Define objective, and
function
What
 A farmeris
has the goal,
two brands and
of fertiliser how
available is with
to him, it different
chemical compositions.
counted?
 He has evaluated the performance of different chemicals on his crops
and wants to ensure that the field he is covering is fed with at least
16 kilograms of Nitrogen and 24 kilograms of Phosphate.
 Fertiliser blend 1 is named Super-Gro. Each bag of Super-Gro contains
2kg of Nitrogen and 4kg of Phosphate.
 Fertiliser blend 2 is named Crop-Quick. Each bag contains 4kg of
Nitrogen and 3kg of phosphate.
 A bag of Super-Gro costs £6, and a bag of Crop-Quick costs
£3.
 The farmer wants to know how many bags of each blend to buy to
satisfy his requirements while minimising the total cost.
Step 2: Define objective, and
function
What
 A bag of is thecosts
Super-Gro goal,£6, andand
a bag ofhow is costs
Crop-Quick it £3.
counted?
 Minimising the total cost.

 The total cost will be:

 6A + 3B

 And we want to minimise this.

Step 3: Set the constraints
What is limiting the objective?
 A farmer has two brands of fertiliser available to him, with different
chemical compositions.
 He has evaluated the performance of different chemicals on his crops
and wants to ensure that the field he is covering is fed with at least
16 kilograms of Nitrogen and 24 kilograms of Phosphate.
 Fertiliser blend 1 is named Super-Gro. Each bag of Super-Gro
contains 2kg of Nitrogen and 4kg of Phosphate.
 Fertiliser blend 2 is named Crop-Quick. Each bag contains 4kg of
Nitrogen and 3kg of phosphate.
 A bag of Super-Gro costs £6, and a bag of Crop-Quick costs £3.
 The farmer wants to know how many bags of each blend to buy to
satisfy his requirements while minimising the total cost.
Step 3: Set the constraints
What is limiting the objective?
 Need: 16kg Nitrogen and 24kg Phosphate.
 Super-Gro: 2kg Nitrogen and 4kg Phosphate.
 Crop-Quick: 4kg Nitrogen and 3kg Phosphate.
 We’ll need one constraint for each chemical quantity:

 Nitrogen: 2A + 4B ≥ 16
 Phosphate: 4A + 3B ≥ 24

 And the domain constraints:

A, B ≥ 0 A, B ∈ ℤ
Step 4: Put it all together

 Variables:  Now we’re ready to put this

Set A, B in Excel Solver!

to
 Objective: minimise
6A + 3B

subject to
 Constraints: 2A + 4B ≥
16

4A + 3B ≥ 24

A, B ≥ 0
Example 2
Chemical production plant
Example: Chemical production

 A chemical plant produces two liquid products.

 To produce one litre of Product A, 2 hours of machine time is
required. One litre of Product B requires 1 hour of machine time.
 The total number of available machine hours per day is 40.
 In addition, 4 labour hours are needed to produce one litre of Product
A and 1 labour hour is needed to produce one litre of Product B.
 The total number of available labour hours per day is 60.
 Profit contribution is £60/litre for product A and £40/litre for product
B.
 At least 5 litres of A should be produced per day due to prior
commitments.
 What should be the daily production mix?
Identify:
variables, objective, constraints
 A chemical plant produces two liquid products.
 To produce one litre of Product A, 2 hours of machine time is
required. One litre of Product B requires 1 hour of machine time.
 The total number of available machine hours per day is 40.
 In addition, 4 labour hours are needed to produce one litre of
Product A and 1 labour hour is needed to produce one litre of
Product B.
 The total number of available labour hours per day is 60.
 Profit contribution is £60/litre for product A and £40/litre for
product B.
 At least 5 litres of A should be produced per day due to prior
commitments.
 What should be the daily production mix?
Identify:
variables, objective, constraints
 Set quantity of the two liquid products.
 a = litres of Product A produced per day
 b = litres of product B produced per day

 Maximise Profit: P = 60a + 40b

 Machine time: 2a + 1b <= 40

 Labour hours: 4a + 1b <= 60
 Prior Product A commitment: a >= 5

 b >= 0; a, b are integers

Example 3
Building tables
Example: Building tables
 Wood Walker is a self-employed furniture
maker.
 He makes three different styles of tables: A,
B, and C.

Time per Table (hours)
Each model of table requires a certain
Assembl
amount of time for the cutting of Model Cutting Painting Profit
y
component parts, for assembling, and for A 1 2 4 $35
painting. B 2 4 4 $40
 Wood can sell all the units he makes. B (unpainted) 2 4 0 $20
 C 3 7 5 $50
Model B may be sold without painting.
 Capacity
Use the data below to formulate a (hours/month 200 300 150
spreadsheet model that will help Wood )
determine the product mix that will
maximize his profit.

 Let’s do the modelling of this one by

hand!
 Time per Table (hours)
Model Cutting Assembly Painting Profit

Model the problem: A

B
1
2
2
4
4
4
$35
$40
B (unpainted) 2 4 0 $20
C 3 7 5 $50

Capacity
200 300 150
(hours/month)
Example 4
Manufacturing slip-rings
Where some can be manufactured in-house, and some must be
purchased
Example 4: Slip rings
The setup
 The Electro-Poly Corporation is the world’s leading manufacturer of slip
rings.
 A slip ring is an electrical coupling device that allows current to pass
through a spinning or rotating connection. The company recently received
a $750,000 order for various quantities of three types of slip rings. Each
slip ring requires a certain amount of time to wire and harness. The first
table summarizes the requirements for the three models of slip rings.
 Unfortunately, Electro-Poly doesn’t have enough wiring and harnessing
capacity to fill the order by its due date.
 The company has only 10,000 hours or wiring capacity and 5,000 hours of
harnessing capacity available to devote to this order. However, the
company can subcontract any portion of the order. The unit costs of
producing each model in-house and buying the finished products from a
subcontractor are summarized in the second table.
 Determine the number of slip rings to make and the number to buy in
order to fill the customer order at the least possible cost.
Example 4: Slip rings
The data
Model 1 Model 2 Model 3

Number Ordered 3000 2000 900

Wiring/unit (hours) 2 1.5 3

Harnessing/unit
1 2 1
(hours)

Model
Model 1 Model 2
3
Cost to
$50 $83 $130
make

Cost to buy $60 $97 $145

 Model 1 Model 2 Model 3

Example 4: Slip rings Number Ordered 3000 2000 900

The modelling Wiring/unit (hours)

Harnessing/unit
2 1.5 3

1 2 1
(hours)
Model
Model 1 Model 2
3
Cost to
$50 $83 $130
make

Cost to buy $60 $97 $145

That’s all the content for my part!

 Reminders:
 No seminars this week, they will be next week
 Next weeks lecture is me and Meng and will cover everything you need to
know about the exam, as well as revision and recap.

 If there’s still more time today we have some options:

1. Start going through seminar exercises
2. Show you some of the research I’ve done that uses LP’s or IP’s for
industrial problems
3. Finish early and not worry about it

 But maybe Ollie planned this perfectly for time? Seems unlikely!