Optimalisering Hoorcollege 4
Leo van Iersel Technische Universiteit Delft
23 september 2015
Leo van Iersel (TUD)
Optimalisering
23 september 2015
1 / 19
Mededelingen
Maandag 28 september: deadline huiswerk 1. Volgende hoorcollege: woensdag 7 oktober, Gorlaeus zaal C2.
Leo van Iersel (TUD)
Optimalisering
23 september 2015
2 / 19
Dualiteit
Dualiteit: Elk LP probleem heeft een bijbehorend duaal probleem. Primaal (oorspronkelijk) probleem min max n variabelen m restricties
Duaal probleem max min n restricties m variabelen
Dualiteit wordt gebruikt om ondergrenzen op de optimale doelfunctiewaarde te berekenen (voor minimaliseringsproblemen) en optimaliteit te verifi¨eren.
Leo van Iersel (TUD)
Optimalisering
23 september 2015
3 / 19
Dieet probleem Een aantal soorten voedsel bevatten elk een bepaalde hoeveelheid van verschillende voedingsstoffen. We willen van elke voedingsstof genoeg binnenkrijgen. Voor zo min mogelijk geld. Hoeveel kun je het beste eten van elke soort voedsel?
Voorbeeld kosten koolhydraten eiwitten vetten
chips 3 2 0 4
Leo van Iersel (TUD)
muesli 3 1 1 0
bitterballen 4 0 4 8
Optimalisering
benodigd (ADH) 3 2 9
23 september 2015
4 / 19
Dieet probleem Een aantal soorten voedsel bevatten elk een bepaalde hoeveelheid van verschillende voedingsstoffen. We willen van elke voedingsstof genoeg binnenkrijgen. Voor zo min mogelijk geld. Hoeveel kun je het beste eten van elke soort voedsel?
Voorbeeld min 3 x1 +3 x2 +4 x3 o.d.v . 2 x1 + x2 ≥3 x2 +4 x3 ≥ 2 4 x1 +8 x3 ≥ 9 x1 , x2 , x3 ≥ 0
(1) (2) (3)
Kunnen we ondergrenzen bepalen op hoeveel we minimaal kwijt zijn aan ons dieet? Leo van Iersel (TUD)
Optimalisering
23 september 2015
5 / 19
Voorbeeld min 3 x1 +3 x2 +4 x3 o.d.v . 2 x1 + x2 ≥3 x2 +4 x3 ≥ 2 4 x1 +8 x3 ≥ 9 x1 , x2 , x3 ≥ 0
(1) (2) (3)
⇒
2 x1 +2 x2 +4 x3 ≥ 5
(1) + (2)
⇒
3 x1 +3 x2 +4 x3 ≥ 5
Dus de kosten van een optimaal dieet zijn minstens 5. Kun je een betere ondergrens vinden?
Leo van Iersel (TUD)
Optimalisering
23 september 2015
6 / 19
Voorbeeld min 3 x1 + 3 x2 + 4 x3 o.d.v . 2 x1 + x2 ≥3 x2 + 4 x3 ≥ 2 4 x1 + 8 x3 ≥ 9 x1 , x2 , x3 ≥ 0 ⇒
3 x1 + 2 21 x2 + 4 x3 ≥ 6 12
⇒
3 x1 + 3 x2 + 4 x3 ≥ 6 12
(1) (2) (3)
1 21 × (1) + (2)
Dus de kosten van een optimaal dieet zijn minstens 6 12 . Kunnen we nog betere ondergrenzen vinden?
Leo van Iersel (TUD)
Optimalisering
23 september 2015
7 / 19
Voorbeeld min 3 x1 +3 x2 +4 x3 o.d.v . 2 x1 + x2 ≥3 x2 +4 x3 ≥ 2 4 x1 +8 x3 ≥ 9 x1 , x2 , x3 ≥ 0
(1) (2) (3)
Voor elke π1 , π2 , π3 ≥ 0 geldt: π1 (2 x1 + x2 ) + π2 ( x2 +4 x3 ) + π3 (4 x1 +8 x3 ) ≥ 3π1 + 2π2 + 9π3
π1 × (1) π2 × (2) π3 × (3)
Dus 3π1 + 2π2 + 9π3 is een ondergrens op de optimale waarde wanneer π1 (2 x1 + x2 ) + π2 ( x2 +4 x3 ) + π3 (4 x1 +8 x3 ) ≤ 3 x1 +3 x2 +4 x3 Leo van Iersel (TUD)
Optimalisering
π1 × (1) π2 × (2) π3 × (3)
23 september 2015
8 / 19
Voorbeeld min 3 x1 +3 x2 +4 x3 o.d.v . 2 x1 + x2 ≥3 x2 +4 x3 ≥ 2 4 x1 +8 x3 ≥ 9 x1 , x2 , x3 ≥ 0
(1) (2) (3)
Dus 3π1 + 2π2 + 9π3 is een ondergrens op de optimale waarde voor alle π1 , π2 , π3 ≥ 0 met π1 (2 x1 + x2 ) + π2 ( x2 +4 x3 ) + π3 (4 x1 +8 x3 ) ≤ 3 x1 +3 x2 +4 x3
π1 × (1) π2 × (2) π3 × (3)
De beste ondergrens vinden we door 3π1 + 2π2 + 9π3 te maximaliseren.
Leo van Iersel (TUD)
Optimalisering
23 september 2015
9 / 19
Voorbeeld Het primale probleem: min 3 x1 +3 x2 +4 x3 o.d.v . 2 x1 + x2 ≥3 x2 +4 x3 ≥ 2 4 x1 +8 x3 ≥ 9 x1 , x2 , x3 ≥ 0
(1) (2) (3)
Het duale probleem (vinden van de beste ondergrens): max o.d.v .
3 π1 + 2 π2 +9 π3 2 π1 +4 π3 ≤ 3 π1 + π2 ≤3 4 π2 +8 π3 ≤ 4 π1 , π2 , π3 ≥ 0
(D1) (D2) (D3)
Wat is de interpretatie van de duale voor het dieet probleem? Leo van Iersel (TUD)
Optimalisering
23 september 2015
10 / 19
Duale van het dieet probleem Een pilmaker produceert pillen voor elke voedingsstof. Voor elk soort voedsel moet het goedkoper zijn om de voedingsstoffen d.m.v. pillen binnen te krijgen dan d.m.v. het voedsel. De prijs om van elke voedingsstof genoeg binnen te krijgen wil de pilmaker zo hoog mogelijk maken. Wat zijn de optimale prijzen (π1 , π2 , π3 ) voor de pillen?
Voorbeeld max o.d.v .
Leo van Iersel (TUD)
3 π1 + 2 π2 +9 π3 2 π1 +4 π3 ≤ 3 π1 + π2 ≤3 4 π2 +8 π3 ≤ 4 π1 , π2 , π3 ≥ 0
Optimalisering
(D1) (D2) (D3)
23 september 2015
11 / 19
Voorbeeld Het primale probleem:
Het duale probleem:
min 3 x1 +3 x2 +4 x3 o.d.v . 2 x1 + x2 ≥3 x2 +4 x3 ≥ 2 4 x1 +8 x3 ≥ 9 x1 , x2 , x3 ≥ 0
max o.d.v .
3 π1 + 2 π2 +9 π3 2 π1 +4 π3 ≤ 3 π1 + π2 ≤3 4 π2 +8 π3 ≤ 4 π1 , π2 , π3 ≥ 0
Oplossing (π1 , π2 , π3 ) = (1 12 , 1, 0) voor het duale probleem geeft een ondergrens van 6.5 op de optimale waarde van het primale probleem. Is er een nog betere ondergrens? Nee! Want (x1 , x2 , x3 ) = (1 21 , 0, 21 ) is een oplossing van het primale probleem met waarde 6.5. Dus zijn beide oplossingen optimaal!
Leo van Iersel (TUD)
Optimalisering
23 september 2015
12 / 19
Dualiteit voor algemene LP problemen
Het primale probleem (P): min cT x o.d.v . ai x = bi ai x ≥ bi xj ≥ 0 xj ∈ R
i i j j
∈M ¯ ∈M ∈N ∈ N¯
Het duale probleem (D): max o.d.v .
bT π πi ∈ R πi ≥ 0 π T Aj ≤ cj π T Aj = cj
i i j j
∈M ¯ ∈M ∈N ∈ N¯
Stelling (3.2) De duale van het duale probleem is het primale probleem.
Leo van Iersel (TUD)
Optimalisering
23 september 2015
13 / 19
Zwakke dualiteitsstelling Het primale probleem (P): min z = c T x o.d.v . ai x = bi ai x ≥ bi xj ≥ 0 xj ∈ R
i i j j
∈M ¯ ∈M ∈N ∈ N¯
Het duale probleem (D): max w = b T π o.d.v . πi πi π T Aj π T Aj
∈R ≥0 ≤ cj = cj
i i j j
∈M ¯ ∈M ∈N ∈ N¯
Stelling (3.1a: zwakke dualiteitsstelling) Als x een toegelaten oplossing is van (P) en π een toegelaten oplossing van (D), dan is z(x) ≥ w (π). (Elke toegelaten oplossing van het duale probleem geeft een ondergrens op de optimale waarde van het primale probleem.) Leo van Iersel (TUD)
Optimalisering
23 september 2015
14 / 19
Sterke dualiteitsstelling Het primale probleem (P): min z = c T x o.d.v . ai x = bi ai x ≥ bi xj ≥ 0 xj ∈ R
i i j j
∈M ¯ ∈M ∈N ∈ N¯
Het duale probleem (D): max w = b T π o.d.v . πi πi π T Aj π T Aj
∈R ≥0 ≤ cj = cj
i i j j
∈M ¯ ∈M ∈N ∈ N¯
Stelling (3.1b: sterke dualiteitsstelling) Als (P) en (D) beide toegelaten zijn en (P) een optimale oplossing x ∗ heeft, dan heeft (D) een optimale oplossing π ∗ en geldt z(x ∗ ) = w (π ∗ ). (Het primale en duale probleem hebben hetzelfde optimum.)
Leo van Iersel (TUD)
Optimalisering
23 september 2015
15 / 19
Mogelijke primale-duale combinaties
Primale
Begrensd optimum Onbegrensd Niet toegelaten
Begrensd optimum (1) x x
Duale Onbegrensd x x (2)
Niet toegelaten x (2) (3)
Combinaties met een x zijn niet mogelijk!
Leo van Iersel (TUD)
Optimalisering
23 september 2015
16 / 19
Duale oplossing vinden in het Simplextableaux Laat xB de basisvariabelen in een optimale oplossing zijn en xN de niet-basisvariabelen. Neem voor gemak aan A = [B N] c en c = B cN LP probleem: In standaard vorm: min z = c T x o.d.v . Ax+Is =b x, s ≥ 0
min z = c T x o.d.v . Ax ≤ b x ≥0 Starttableaux:
Leo van Iersel (TUD)
basis
b¯
xB
xN
s
s
b
B
N
I
−z
0
cBT
cNT
0
Optimalisering
23 september 2015
17 / 19
Starttableaux: basis
b¯
xB
xN
s
s
b
B
N
I
B −1 ·
−z
0
cBT
cNT
0
−cBT B −1 (rij 1)
Eindtableaux: basis
b¯
xB
xN
s
xB
B −1 b
I
B −1 N
B −1
−z
−cBT B −1 b
0
cNT −cBT B −1 N
−cBT B −1
Leo van Iersel (TUD)
Optimalisering
23 september 2015
18 / 19
Eindtableaux: basis b¯
xB
xN
s
xB
B −1 b
I
B −1 N
B −1
−z
−cBT B −1 b
0
cNT − cBT B −1 N
−cBT B −1
Hieruit kunnen we aflezen:
−1 xB B b . Een optimale oplossing: x ∗ = = xN 0 De optimale waarde: z ∗ = cBT xB = cBT B −1 b. c¯NT = cNT − cBT B −1 N ≥ 0 (want optimaal min-probleem). Een optimale oplossing van het duale probleem: π ∗ = cBT B −1 (af te lezen in de kolommen van de slackvariabelen).
Leo van Iersel (TUD)
Optimalisering
23 september 2015
19 / 19
