Summary
Samenvatting linear optimisation 2023
- Course
- Institution
Volledige samenvatting. - part 1 - part 2.1 - part 2.2 - lecture 6 - lecture 7 - lecture 8
[Show more]
Seller
Follow
mariep1
Content preview
PART 1: LINEAR PROGRAMMING MODELSOperations 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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller mariep1. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $11.37. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
78252 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now