PART 1: LINEAR PROGRAMMING MODELS
Operations research =
- a decision making tool based on mathematical modelling and analysis to aid in
determining how best to design and operate a system usually under the conditions
requiring allocation of scarce resources.
- defined as the scientific process of transforming data into insights into making
better decisions.
- called the science of better
BRIEF HISTORY OF OR
- origin:
- during WWI in Britain I, the military management in England invited a team
of scientists to study the strategic and tactical problems related to air and
land defense of the country
- problem: resources were limited
- ‘operations’ = the problems of militar
- objective: win the war with these limited resources
- ‘research’ = inventing new methods
- After WWI: discovered that OR techniques could also be applicable in various
different settings.
SOLVE AN OPTIMIZATION PROBLEM
- Stap 1 : build a mathematical model of the problem
- Model: structure which has been built purposely to exhibit features and
characteristics of some other object
- Mathematical model: involves a set of mathematical relationships (such as
equations, inequalities, logical dependencies, etc.), which correspond to the
characterization of the relationships in the real world.
- Why mathematic modelling?
1. have a greater understanding of the object being modelled.
2. simplify the inner workings of a complex system and to use the
universally understandable language of algebra and math.
3. analyze it mathematically to help suggest courses that are not
apparent otherwise.
4. Experiment
- Stap 2: decision making
- Decision alternatives?
- Restrictions?
- What objective criterion to evaluate the
alternatives?
A MILK PRODUCTION PROBLEM
= mathematical programming problem
gegevens
- two machines needed to process milk to produce low-fat and regular milk
- the processing times are:
- Machine 1 can be used for 12 hours in one day
- Machine 2 can be used for 6 hours
- Sales price: $2.5 for low-fat milt and $1.5 for regular milk
te berekenen:
- Hoeveel produceren van elk in een dag zodat de winst maximaal is?
,Oplossing:
Decision variables:
- x1 : amount in liters of low-fat milk produced in a day
- x2 : amount in liters of regular milk produced in a day
parameters:
- Available machine hours
- Required machine hours/product
- Revenue per unit of each product
Constraints:
- Total production time on each machine cannot exceed the available machine hours
- Production amounts should be nonnegative.
Objective function:
- Total revenue
Maak nu een mathematical model!
= voorbeeld van een linear programming model (LP) (zie verder)
algemeen Ingevuld
maximize (max) total revenue ( = objective function)
subject to (s.t.)
Total production time on
constraint Machine 1 ≤ 12 hours
s Total production time on
Machine 2 ≤ 6 hours
Production amounts ≥ 0
WHAT IS MATHEMATICAL PROGRAMMING?
In a mathematical programming problem, one seeks to minimize or maximize a real
function of real or integer variables, subject to constraints on the variables
- Algemene vorm:
- Linear problem?
- If f and g are linear for -> problem = linear
- If ONE is not linear -> problem = nonlinear
Linear is easier than nonlinear
- Continuous problem?
- if all variables are continuous -> problem = continuous
- otherwise -> problem = discrete
continuous is easier than discrete
ASSUMPTIONS OF LINEAR PROGRAMMING
1) Proportionality & Additivity:
The contribution of each decision variable to the objective function or to each
constraint is proportional to the value of that variable.
The contributions from decision variables are independent from one another and the
total contribution is the sum of the individual contributions
→ Linear problem
, 2) Divisibility:
Each decision variable is allowed to take fractional values → continuous problem
3) Certainty:
All input parameters (coefficients of the objective function and of the constraints)
are known with certainty.
→ Deterministic problem (as opposed to stochastic)
A LINEAR PROGRAMMING PROBLEM
An LP problem is a an optimization problem in which:
- the decision variables x1, . . . , xn are continuous
- the objective function is a linear function of the decision variables:
met c1, . . . , cn: the objective function coefficients
- the constraints are linear inequalities or linear equations ( i.e., each constraint i has
the following form: )
met:
- ai1, . . . , ain are the technical coefficients
- bi is the right hand side of constraint = 1, . . . , m.
general form:
- x1, . . . , xn → decision
variables.
- cj ’s, aij ’s, bj ’s
→ given
→ parameters
Feasible solution:
Any vector (x1, x2,..) that satisfies all constraints simultaneously
Feasible set/feasible region:
The set of all feasible solutions
Optimal solution:
A feasible solution that yields the best objective function value
Optimal value:
The best objective function value (or the objective function value evaluated at an optimal
solution)
How to solve a LP problem?
- LINDO/LINGO (input = algebraic model)
- Excel solver (input = spreadsheet)
- Other commercial solvers
VOORBEELD: A MULTI-PLANT MODEL FOR WILLIAMS (2013)
, - A company operates two factories, A and B. Each factory makes two products,
standard and deluxe using two processes, grinding and polishing. The grinding and
polishing times in hours are as follows:
- Factory A - Factory B
- Grinding capacity = 80 - Grinding capacity = 60
hours/week hours/week
- Policing capacity = 60 - Policing capacity = 75
hours/week hours/week
- Unit profit for:
- Standards = $10
- Deluxe = $15
- Each product: 4 kg of raw materials
- Factory heeft 120 kg of raw materials/week
- A krijgt 75 kg/week
- B krijgt 45 kg/week
Te berekenen: maximize profit
Oplossing:
Eerst kijken we naar het model van Factory A
Decision variables:
- x1 : the quantity of standard to be produced in A
- x2 : the quantity of deluxe to be produced in A
model:
Optimal value zA = 225.
Optimal solution:
= 11.25 and = 7.5
with 20 hours surplus of
grinding capacity
nu kijken we naar het model van Factory B
Decision variables:
- x3 : the quantity of standard to be produced in B
- x4 : the quantity of deluxe to be produced in B
model:
optimal value zB = 168.75
Optimal solution:
= 0 and = 11.25
with 26.25 hours surplus of
grinding and 7.5 hours surplus
polishing capacity
wat nu als we TOTALE profit willen maximaliseren?
- There will be a single raw material constraint limiting the company to 120 kilograms
per week. No longer allocate 75 kilograms of raw material to A and 45 kilograms to
B.
Operations research =
- a decision making tool based on mathematical modelling and analysis to aid in
determining how best to design and operate a system usually under the conditions
requiring allocation of scarce resources.
- defined as the scientific process of transforming data into insights into making
better decisions.
- called the science of better
BRIEF HISTORY OF OR
- origin:
- during WWI in Britain I, the military management in England invited a team
of scientists to study the strategic and tactical problems related to air and
land defense of the country
- problem: resources were limited
- ‘operations’ = the problems of militar
- objective: win the war with these limited resources
- ‘research’ = inventing new methods
- After WWI: discovered that OR techniques could also be applicable in various
different settings.
SOLVE AN OPTIMIZATION PROBLEM
- Stap 1 : build a mathematical model of the problem
- Model: structure which has been built purposely to exhibit features and
characteristics of some other object
- Mathematical model: involves a set of mathematical relationships (such as
equations, inequalities, logical dependencies, etc.), which correspond to the
characterization of the relationships in the real world.
- Why mathematic modelling?
1. have a greater understanding of the object being modelled.
2. simplify the inner workings of a complex system and to use the
universally understandable language of algebra and math.
3. analyze it mathematically to help suggest courses that are not
apparent otherwise.
4. Experiment
- Stap 2: decision making
- Decision alternatives?
- Restrictions?
- What objective criterion to evaluate the
alternatives?
A MILK PRODUCTION PROBLEM
= mathematical programming problem
gegevens
- two machines needed to process milk to produce low-fat and regular milk
- the processing times are:
- Machine 1 can be used for 12 hours in one day
- Machine 2 can be used for 6 hours
- Sales price: $2.5 for low-fat milt and $1.5 for regular milk
te berekenen:
- Hoeveel produceren van elk in een dag zodat de winst maximaal is?
,Oplossing:
Decision variables:
- x1 : amount in liters of low-fat milk produced in a day
- x2 : amount in liters of regular milk produced in a day
parameters:
- Available machine hours
- Required machine hours/product
- Revenue per unit of each product
Constraints:
- Total production time on each machine cannot exceed the available machine hours
- Production amounts should be nonnegative.
Objective function:
- Total revenue
Maak nu een mathematical model!
= voorbeeld van een linear programming model (LP) (zie verder)
algemeen Ingevuld
maximize (max) total revenue ( = objective function)
subject to (s.t.)
Total production time on
constraint Machine 1 ≤ 12 hours
s Total production time on
Machine 2 ≤ 6 hours
Production amounts ≥ 0
WHAT IS MATHEMATICAL PROGRAMMING?
In a mathematical programming problem, one seeks to minimize or maximize a real
function of real or integer variables, subject to constraints on the variables
- Algemene vorm:
- Linear problem?
- If f and g are linear for -> problem = linear
- If ONE is not linear -> problem = nonlinear
Linear is easier than nonlinear
- Continuous problem?
- if all variables are continuous -> problem = continuous
- otherwise -> problem = discrete
continuous is easier than discrete
ASSUMPTIONS OF LINEAR PROGRAMMING
1) Proportionality & Additivity:
The contribution of each decision variable to the objective function or to each
constraint is proportional to the value of that variable.
The contributions from decision variables are independent from one another and the
total contribution is the sum of the individual contributions
→ Linear problem
, 2) Divisibility:
Each decision variable is allowed to take fractional values → continuous problem
3) Certainty:
All input parameters (coefficients of the objective function and of the constraints)
are known with certainty.
→ Deterministic problem (as opposed to stochastic)
A LINEAR PROGRAMMING PROBLEM
An LP problem is a an optimization problem in which:
- the decision variables x1, . . . , xn are continuous
- the objective function is a linear function of the decision variables:
met c1, . . . , cn: the objective function coefficients
- the constraints are linear inequalities or linear equations ( i.e., each constraint i has
the following form: )
met:
- ai1, . . . , ain are the technical coefficients
- bi is the right hand side of constraint = 1, . . . , m.
general form:
- x1, . . . , xn → decision
variables.
- cj ’s, aij ’s, bj ’s
→ given
→ parameters
Feasible solution:
Any vector (x1, x2,..) that satisfies all constraints simultaneously
Feasible set/feasible region:
The set of all feasible solutions
Optimal solution:
A feasible solution that yields the best objective function value
Optimal value:
The best objective function value (or the objective function value evaluated at an optimal
solution)
How to solve a LP problem?
- LINDO/LINGO (input = algebraic model)
- Excel solver (input = spreadsheet)
- Other commercial solvers
VOORBEELD: A MULTI-PLANT MODEL FOR WILLIAMS (2013)
, - A company operates two factories, A and B. Each factory makes two products,
standard and deluxe using two processes, grinding and polishing. The grinding and
polishing times in hours are as follows:
- Factory A - Factory B
- Grinding capacity = 80 - Grinding capacity = 60
hours/week hours/week
- Policing capacity = 60 - Policing capacity = 75
hours/week hours/week
- Unit profit for:
- Standards = $10
- Deluxe = $15
- Each product: 4 kg of raw materials
- Factory heeft 120 kg of raw materials/week
- A krijgt 75 kg/week
- B krijgt 45 kg/week
Te berekenen: maximize profit
Oplossing:
Eerst kijken we naar het model van Factory A
Decision variables:
- x1 : the quantity of standard to be produced in A
- x2 : the quantity of deluxe to be produced in A
model:
Optimal value zA = 225.
Optimal solution:
= 11.25 and = 7.5
with 20 hours surplus of
grinding capacity
nu kijken we naar het model van Factory B
Decision variables:
- x3 : the quantity of standard to be produced in B
- x4 : the quantity of deluxe to be produced in B
model:
optimal value zB = 168.75
Optimal solution:
= 0 and = 11.25
with 26.25 hours surplus of
grinding and 7.5 hours surplus
polishing capacity
wat nu als we TOTALE profit willen maximaliseren?
- There will be a single raw material constraint limiting the company to 120 kilograms
per week. No longer allocate 75 kilograms of raw material to A and 45 kilograms to
B.
