Transcript My Presentation Title

Optimisation using Linear
Programming
Geraint Palmer
Taxonomy of OR methods
OR Methods
Methods to calculate
an attribute of a
system
“Soft” methods
Methods to help
structure illstructured problem
situations
Methods for more
structured problems
-parameters difficult
to quantify
Deterministic
methods
Methods to replicate
or forecast system
behaviour
Optimization
methods
Deterministic
replication methods
Optimization of
deterministic
systems
Statistical methods
Stochastic replication
methods
Optimization of
stochastic systems
Static Monte Carlo
simulation methods
Complexity
understanding
methods
Stochastic methods
Probabilistic methods
Williams, T (2008) Management Science in Practice, Wiley. p.101
Logic methods
Problem
Given a restricted budget, how much of drug A and
drug B should a hospital purchase in order to
maximise number of QALYs saved?
A hospital can save 50 QALYs per tonne of drug A, and
60 QALYs per tonne of drug B.
A tonne of A requires 4 tonnes of X and 5 tonnes of Y.
A tonne of B requires 6 tonnes of X and 4 tonnes of Y.
We can only afford 24 tonnes of X, and 20 tonnes of Y.
Formulation
Given a restricted budget, how much of drug A and drug B should a
hospital purchase in order to maximise number of QALYs saved?
A hospital can save 50 QALYs per tonne of drug A, and 60 QALYs
per tonne of drug B.
A tonne of A requires 4 tonnes of X and 5 tonnes of Y.
A tonne of B requires 6 tonnes of X and 4 tonnes of Y.
We can only afford 24 tonnes of X, and 20 tonnes of Y.
Maximise: 50 A + 60 B
Constraints:
Resource X: 4 A + 6 B ≤ 24
Resource Y: 5 A + 4 B ≤ 20
Solution
4 A + 6 B ≤ 24
5 A + 4 B ≤ 20
Solution
4 A + 6 B ≤ 24
5 A + 4 B ≤ 20
50 A + 60 B
Solution
4 A + 6 B ≤ 24
12
20
≈ 1.714 tonnes A
7 ≈ 2.857 tonnes B
7
5 A + 4 B ≤ 20
50 A + 60 B
Features
• Objectives and constraints must be linear
• Multi-Dimensional – More variables!
• Lots of Constraints
• Computer does all the solving
• Mixed Integer Linear Programming – when solutions
must be integers
• Sensitivity Analysis
Potential Uses
• Resource Allocation
• Operating Room Scheduling
• Nurse Rostering
• Workforce Planning
• Public Health Campaigns