Samenvatting
Summary D0H45A_Linear Optimisation: Part 3: Duality Theory
- Instelling
- Katholieke Universiteit Leuven (KU Leuven)
- Boek
- Operations Research
Uitbreiding duality theorema toegepast op simplex
[Meer zien]Voorbeeld 2 van de 8 pagina's
Voorbeeld 2 van de 8 pagina's
In winkelwagenGekoppeld boek
Titel boek:
Auteur(s):
- Uitgave:
- ISBN:
- Druk:
Verkoper
Volgen
Voorbeeld van de inhoud
Part 3: Duality TheoryDual: Associated with any LP there is another LP called the dual
Primal: When taking the dual of an LP, the give LP is called the primal.
We speak of primal-dual pairs. This theory will give us insights in how changes in an LP’s
parameter the LP’s optimal solution affects.
The primal and dual Problems in Canonical Form
Maximization LP
Primal Dual
Max cx min wb
s.t. Ax ≤ b s.t. wA ≥ c
x≥0 w≥0
Minimization LP
Primal Dual
Min cx max wb
s.t. Ax ≥ b s.t. wA ≤ c
x≥0 w≥0
If the primal is in canonical form, the dual is also in canonical form.
Constraint i from primal will be associated to 𝑤) in dual.
Theorem
“Dual of the Dual is the primal”
, Primal-Dual pairs
A constraint in Primal ⟺ Variable in Dual
A variable in Primal ⟺ a constraint in Dual
Min in Primal ⟺ max in Dual (and vice versa)
What happens when we have equality constraints Ax = b in the primal?
Equality constraint in Primal ⟺ corresponding variable free in Dual
Primal Dual
Min cx max wb
s.t. Ax = b s.t. wA ≤ c
x≥0 w free
What happens when we have free variables in the primal?
Free variable in Primal ⟺ Corresponding constraint is equality in Dual
Primal Dual
Max cx min wb
s.t. Ax ≤ b s.t. wA = c
x free w≥0
What happens when we have non-positive variables in the primal?
ð Will define a new variable y = -x
Primal Dual
Max cx max - cy min wb min wb
s.t. Ax ≤ b ⟹ s.t. - Ay ≤ b s.t. -wA ≥ - c ⟹ s.t. wA ≤ c
x≤0 y≥0 w≥0 w≥0
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