Samenvatting
Summary D0H45A_Linear Optimisation: Part 2: Models
- Instelling
- Katholieke Universiteit Leuven (KU Leuven)
- Boek
- Operations Research
Uitbreiding van grafiek en simplex method om LP problemen op te lossen
[Meer zien]Voorbeeld 2 van de 10 pagina's
Voorbeeld 2 van de 10 pagina's
In winkelwagenGekoppeld boek
Titel boek:
Auteur(s):
- Uitgave:
- ISBN:
- Druk:
Verkoper
Volgen
Voorbeeld van de inhoud
Part 2: MethodsGraphical solution of LP problems with two variables
General form
Max cx
s.t. Ax ≤ b
x≥0
To graphically determine the
solution of an LP problem we will
represent the information we have
in a graph by drawing the lines of
all the constraints and determine
on basis if that the feasible region.
In order to find the optimal
solution of the feasible set we will
draw the objective function and
make it move in the direction c.
C is the improving direction and is the vector made with the coefficients of the objective
function.
Isoprofit line: line on which all points have the same z-value (𝑧 = 𝑎𝑥$ + 𝑏𝑥?) for
maximization problems
Isocost line: line on which all points have the same z-value (𝑧 = 𝑎𝑥$ + 𝑏𝑥? ) for minimization
problems
As we move the isoprofit lines in the direction of c, the total profit will increase. To solve an
LP problem in 2 variables, we should try tp push isoprofit (or isocost) lines in the improving
direction as much as possible while still staying in the feasible region.
!! for a maximization problem we use c as improving direction. For minimization problems
we will have to use ( -c) because otherwise we are improving.
The feasible region is defined by the constraints so if we modify the objective function while
keeping the constraints the same, this one won’t change.
What will change in this case is the improving direction => is defined by the objective
function.
Convex set
Set S is convex if the line joining any pair of points in S is completely contained in S.
, Convex if for two points 𝑥 ∈ 𝑆 and 𝑦 ∈ 𝑆, their convex combination 𝜆𝑥 + (1 − 𝜆)𝑦 ∈ 𝑆 for
all 𝜆 ∈ [0,1].
ð Feasible set of an LP must be a convex set
Strict convex combination
X is a strict convex combination of 𝑥$ and 𝑥? if 𝑥 = 𝜆𝑥$ + (1 − 𝜆)𝑥? for some 𝜆 ∈ ]0,1[.
Extreme point (corner point)
P is an extreme point of it cannot be represented as a strict convex combination of distinct
points of S. If to represent the point as a convex combination of 2 other points then if one
point is in the set then the other one will necessarily have to be outside of the set S.
In the case that the isoprofit or isocost line on a constraint line arrives when optimization its
direction, we will have as optimal solution every feasible solution on the segment of the
constraint line that belongs to the feasible region.
ð LP has multiple or alternate optimal solutions
Unbounded LP Problems:
Arises when we the objective function can be moved infinitely while keeping optimizing the
problem and staying in the feasible region.
For such a LP problem there is no optimal solution because we can always find beter and
the optimal value is defined to be +∞ (−∞)
Infeasible LP Problems:
Happens when we can’t find a feasible solution.
Fundamental Theorem of Linear Programming
“If the feasible set is not empty, if there is a feasible solution, then there is at least an
extreme point.”
“If an LP with feasible set has an optimal solution, then there is an extreme point of the
feasible region that is an optimal solution to the LP.”
ð ! not every optimal solution needs to be an extreme point!
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 chlodewandeleer. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €4,49. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 56326 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen