Samenvatting
Samenvatting linear optimisation 2023
- Instelling
- Katholieke Universiteit Leuven (KU Leuven)
Volledige samenvatting. - part 1 - part 2.1 - part 2.2 - lecture 6 - lecture 7 - lecture 8
[Meer zien]Voorbeeld 4 van de 42 pagina's
Voorbeeld 4 van de 42 pagina's
In winkelwagenVerkoper
Volgen
Voorbeeld van de inhoud
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.
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
√ Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, Bancontact of creditcard voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper mariep1. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €10,48. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 78252 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen