O ptim aliseren in N etw erken Kees Roos e-mail:
[email protected],
[email protected] URL: http://www.isa.ewi.tudelft.nl/∼roos
HOVO cursus
Wiskunde: zuurstof voor de wereld (deel I) 18 februari, A.D. 2009 Optimization Group
1/44
Onderwerpen ⋆ Inleiding ⋆ Optimaliseren in de geschiedenis ⋆ Kortste paden ⋆ Toewijzingsproblemen ⋆ Maximale stroom probleem ⋆ Handelsreiziger probleem ⋆ “Facility location” probleem ⋆ Minimaliseren van een veelterm ⋆ Portret van M´ axima
Optimization Group
2/44
Navigatiesystemen
Optimization Group
3/44
Optimization Group
4/44
Optimaliseren in de geschiedenis 1
Vraag van 3000 jaar geleden: hoeveel land kan worden ingesloten door de huid van een stier? Meer abstracte formulering: gegeven de lengte van een gesloten kromme, vind het maximale door deze kromme ingesloten oppervlak.
Optimization Group
5/44
Optimaliseren in de geschiedenis 2 gegeven de lengte van een gesloten kromme, vind het maximale door deze kromme ingesloten oppervlak.
Antwoord: het oppervlak is maximaal als de kromme een cirkel is.
Aristoteles
Karl Weierstrass
Hermann Schwarz
384 – 322 B.C.
1815 – 1897
1843 – 1921
Optimization Group
6/44
Optimaliseren in de geschiedenis 4 De natuur optimaliseert ook, bijvoorbeeld bij de voortplanting van het licht: In een niet-homogeen medium plant het licht zich voort, van het ene punt naar het andere punt, langs een weg waarvoor de benodigde tijd minimaal is.
Willebrord Snel van Royen
Pierre Fermat
Christiaan Huygens
alias Snellius: 1580 – 1626
1601 – 1665
1629 – 1695
Optimization Group
7/44
Grondleggers van huidige optimaliseringsmethoden
George Dantzig 1914 - 2005
Leonid Khachyian 1952 - 2005
Optimization Group
Narendra Karmarkar 1957 -
8/44
Definitie van het kortste-pad-probleem
s
3
5
2
4
1
3
5
6
3
2
8
3
2
3
3 1
3
6
7
3
3
4
3
9
3
1
t
Een netwerk, of (gerichte) graaf, bestaat uit een (eindige) verzameling V van knopen, en een verzameling A van (gerichte) takken. Een tak is een geordend paar van knopen. Als a = (v, w) ∈ A dan heet v de beginknoop en w de eindknoop van tak a.
Optimization Group
9/44
Toepassingen
• Vinden van een kortste reisroute van A naar B (reisplanners, navigatiesystemen). • In communicatienetwerken (bijv. internet). • Spraakherkenning: het automatisch omzetten van gesproken in geschreven tekst: voed
De
man
voedt
het
schaap
voet
In veel toepassingen moeten grote aantallen kortste paden worden uitgerekend waardoor het beschikken over een effici¨ent algoritme heel belangrijk is. Het algoritme van Dijkstra is het meest bekende en moderne varianten daarvan zijn de meest gebruikte. Optimization Group
10/44
Definities Zij gegeven een netwerk G = (V, A). Een pad P in het netwerk is een rij van de vorm v1, e1, v2, e2, . . . vk , ek , vk+1
waarbij ei = (vi, vi+1) ∈ A voor i = 1, 2 . . . , k en k ≥ 1. Omdat een tak eenduidig bepaald is door zijn begin- en zijn eindknoop stellen we een pad ook wel kortweg voor als een geordend rijtje van knopen:
P = v1, v2, . . . vk , vk+1 .
De lengte van tak (v, w) noteren we als cvw . We nemen aan dat cvw ≥ 0 voor elke tak. De lengte van het pad P is per definitie de som van de lengten van de takken op P : ℓ(P ) =
X
cvw .
(v,w)∈P
Optimization Group
11/44
Algoritme van Dijkstra
Initialisatie: Q := {s}; πs := 0; πv := ∞, ∀v ∈ V \ {s}; while Q is niet leeg: Kies u ∈ Q zodat πu ≤ πv voor alle v ∈ Q; Verken(u) endwhile
begin doe voor alle a = (u, v) het volgende: begin als πv > πu + cuv dan πv := πu + cuv ; voeg v toe aan Q end; verwijder u uit Q end Procedure Verken(u).
Algoritme van Dijkstra N.B. Gedurende het algoritme stelt πv steeds de lengte voor van een (gevonden) pad van s naar v . Aan het eind is πv gelijk aan de lengte van een kortste pad van s naar v . Dit geldt voor elke knoop v . In het bijzonder dus ook voor knoop t.
Optimization Group
12/44
Toepassing van het algoritme van Dijkstra
s
3 5
2 4
1 3 5
6
3
2 8
3
2 3
1
3
3 4
9
1
2
3
4
5
6
7
8
9
10 11
s
0
0
0
0
0
0
0
0
0
0
0
0
1
∞
3
3
3
3
3
3
3
3
3
3
3
2
∞ ∞ ∞
6
6
6
6
6
6
6
6
6
3
∞ ∞ ∞ ∞ ∞
9
9
9
9
9
9
9
4
∞
2
2
2
2
2
2
2
2
2
2
2
5
∞
5
5
5
5
5
5
5
5
5
5
5
6
∞ ∞ ∞ ∞
6
6
6
6
6
6
6
6
7
∞ ∞ ∞ ∞ ∞ ∞
9
9
9
9
9
9
8
∞ ∞
7
7
7
7
7
7
7
9
∞ ∞ ∞ ∞ ∞ ∞
9
9
9
9
9
9
t
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 12
3 3
6
3
knoop 0
7 3
1
t
8
8
Optimization Group
7
10 10
13/44
Dijkstra met negatieve lengten
1
1
2
1
3
1
4
1
t
6
s 11 −6
5
1
6
1
−14
−12
−10
−8
7
1
8
1
9
• De knopen 1, 2, 3, 4 en t worden elk 6 maal verkend! • Het aantal iteraties is niet meer O(n). • Ook voor het geval dat er negatieve taklengten zijn is er een O(n) algoritme (van Belmann-Ford).
Optimization Group
14/44
Van Zwolle naar Roosendaal met Dijkstra’s algoritme. Kan het sneller?
Optimization Group
15/44
Van Zwolle naar Roosendaal met Dijkstra’s algoritme, parallel
Optimization Group
16/44
Van Zwolle naar Roosendaal met A∗-versie van Dijkstra’s algoritme
Optimization Group
17/44
Van Zwolle naar Roosendaal met A∗-versie van Dijkstra’s algoritme, parallel
Optimization Group
18/44
Het maximale stroom probleem
a
1
b
3
c
5
5 4
s
1
1
4
4
6
d
4
e
2
t
1
1
f
We beschouwen opnieuw een netwerk G = (V, A). Voor elke tak (v, w) is een positief getal cvw gegeven: dit getal stelt nu de capaciteit van tak (v, w) voor. Gegeven zijn verder weer twee speciale knopen, s en t, en gevraagd wordt om een maximale stroom van s naar t te bepalen.
Optimization Group
19/44
Definitie van een stroom op het netwerk
5
s
a 1
4
1
b 4
1
d
4
3
c
t
1
1 6
e
5
2
f
4
Een stroom x is een verzameling van niet-negatieve getallen xvw zodanig dat in elke knoop ongelijk aan s en t behoud van stroom geldt, en op elke tak de stroomwaarde niet groter is dan de capaciteit. Met andere woorden, x moet voldoen aan de balansvergelijkingen X
xuv =
(u,v)∈A
X
xvw ,
v ∈ V \ {s, t}
(v,w)∈A
en aan de capaciteitsbeperkingen 0 ≤ xvw ≤ cvw ,
(v, w) ∈ A.
De waarde van de stroom x is per definitie gelijk aan waarde(x) =
X
(s,v)∈A
xsv −
X
xvs.
(v,s)∈A
Optimization Group
20/44
Het vinden van een stroom
a
5
s
1
1 4
d
b 4
1 4
3
c
t
1
1
e
5
6
4
f
2 xvw = 0, (v, w) ∈ A.
We beginnen met de zogenaamde nulstroom: De waarde is 0. Stromen met een grotere waarde zijn eenvoudig te vinden: neem een willekeurig pad van s naar t in het netwerk, en stuur daarover zoveel mogelijk stroom. Bijvoorbeeld, over het pad (s, a, f, t) kan een stroom ter waarde van 4 worden verzonden. Vervolgens kan over het pad (s, d, e, b, c, t) een extra stroom ter waarde van 3 worden verzonden. Samen leveren deze stromen een stroom ter waarde van 7 op: 4|5
a
0|1
b
3|3
c
3|5
3|4
s
0|1 3|4
d
0|1 0|1 4|6
0|1 3|4
e
0|2
Optimization Group
f
t 4|4
21/44
Het algoritme van Ford-Fulkerson (1956) Ford en Fulkerson vonden een systematische manier om een zogenaamd doorbraakpad te vinden waarover eventueel extra stroom kan worden gestuurd. We gebruiken daarvoor het zogenaamde hulpnetwerk Gx van G behorend bij een gegeven stroom x. Gx heeft dezelfde knopen als G. In Gx nemen we alleen die takken (v, w) ∈ A op waarover extra stroom kan worden gestuurd en de inverse takken van de stroomvoerende takken in G; de capaciteit van deze takken in Gx is gelijk aan de restcapaciteit in G. Met andere woorden, als we de verzameling van de takken in Gx Ax noemen, dan geldt Ax = {(v, w) ∈ A : xvw < cvw } ∪ {(w, v) : (v, w) ∈ A, xvw > 0} .
Als xvw < cvw dan is de restcapaciteit van deze tak in Ax gelijk aan cvw − xvw , en als xvw > 0 dan is restcapaciteit van tak (w, v) in Ax gelijk aan xvw . Hieronder zijn de laatst gevonden stroom en het bijbehorende hulpnetwerk afgebeeld.
4j5
a 0j1
s 3j4
d
0j1
b 3j4
0j1 3j4
3j3 0j1
e
3j5
0j1
4j6 f 0j2
t 4j4
3 b 2 1 4 3 4 3 s 1 1 t 1 1 1 4 1 2 1 3 e 2 f d 3 a
Optimization Group
1
22/44
Het algoritme van Ford-Fulkerson (1956)
3 b 2 1 4 3 4 3 s 1 1 t 1 1 1 4 1 2 1 3 e 2 f d 3 a
1
3j3
4j5 b 4j5 3j4 0j1 s t 0j1 1j1 0j1 4j6 4j4 4j4 d 4j4 e 0j2 f a
0j1
In het hulpnetwerk blijkt via het dik getekende pad een doorbraak mogelijk van s naar t. Bovendien zien we dat over dit pad een extra stroom ter waarde van 1 kan worden gestuurd. Voegen we deze stroom toe aan de oude stroom dan verkrijgen we de stroom in de rechter figuur, met waarde 7 + 1 = 8. Om na te gaan of verder verbetering van de stroomwaarde mogelijk is construeren we het hulpnetwerk voor de nieuwe stroom.
3 b 1 1 4 31 4 4 s 1 1 t 1 4 1 2 4 d 4 e 2 f a
1
Optimization Group
23/44
Het algoritme van Ford-Fulkerson (1956)
3 b 1 1 4 31 4 4 s 1 1 t 1 4 1 2 4 d 4 e 2 f a
1
Op het eerste gezicht is er nu geen doorbraak mogelijk. Om dit systematisch vast te stellen labelen we alle knopen, te beginnen met s, die vanuit s bereikbaar zijn met een ∗. We kunnen dit doen met een aangepaste (vereenvoudigde) versie van het Dijkstra algoritme: In het hulpnetwerk zijn alle vanuit s bereikbare knopen gelabeld, terwijl de ongelabelde knopen niet bereikbaar zijn vanuit s. Het is duidelijk dat er geen doorbraak meer mogelijk is. We zullen nu bewijzen dat hieruit volgt dat de gevonden stroom maximaal is. Optimization Group
24/44
s-t sneden
s
t
+
Æ (S )
S
V nS
We defini¨eren de knoopverzameling S : S = {v ∈ V : v is gelabeld} .
Omdat geen doorbraak mogelijk is geldt s ∈ S , t ∈ / S . De verzameling van de takken die hun beginknoop in S hebben en hun eindknoop buiten S , noteren we als δ +(S). Dus δ +(S) := {(v, w) ∈ A : v ∈ S, w ∈ / S} .
Als we de takken in δ +(S) uit A verwijderen dan is er geen pad meer van s naar t. We noemen δ +(S) daarom een s-t snede, en we defini¨eren de capaciteit c(δ +(S)) van deze snede als volgt: +
c(δ (S)) :=
X
cvw =
(v,w)∈δ + (S)
X
{cvw : v ∈ S, w ∈ / S} .
Optimization Group
25/44
Max-flow min-cut stelling
3 b 1 1 4 31 4 4 s 1 1 t 1 4 1 2 4 d 4 e 2 f a
1
0j1 3j3
4j5 b 4j5 a 4j6 3j4 0j1 s t 0j1 1j1 0j1 4j4 d 4j4 e 0j2 f 4j4
In het onderhavige geval bestaat δ +(S) uit de takken (b, c), (e, c) en (f, t), en er geldt c(δ +(S)) = 3 + 1 + 4 = 8. Dit is precies de waarde van de gevonden stroom x: waarde(x) = c(δ +(S)).
Theorem 1 De waarde van een maximale stroom is gelijk aan n
+
o
min c(δ (U )) : U ⊆ V, s ∈ U, t ∈ /U .
We concluderen dat de gevonden stroom x maximaal is; de snede gevormd door de takken (b, c), (e, c) en (f, t) vormt hiervan het bewijs! Optimization Group
26/44
Toewijzingsproblemen We behandelen ten slotte zogenaamde toewijzingsprobleem. Een speciaal geval is het zogenaamde huwelijksprobleem; een voorbeeld is weergegeven in het netwerk-model links hieronder. j5 m4 j4 m3 j3 m2 j2 m1 j1
J
M
In dit netwerk stellen de knopen links jongens en de knopen rechts meisjes voor. Een tak (j, m), met j ∈ J en m ∈ M , geeft aan dat jongen j en meisje m met elkaar bevriend zijn. De vraag waar het in het huwelijksprobleem (eng. matching problem) om gaat is de volgende: wat is het maximale aantal jongens dat met een vriendin kan trouwen? Er zijn veel andere toepassingen. Bijvoorbeeld als een aantal verschillende taken moet worden uitgevoerd op een aantal verschillende machines, terwijl niet elke machine elke taak kan uitvoeren. Een mogelijke vraag is dan hoeveel taken tegelijkertijd kunnen worden uitgevoerd. Door J te vervangen door de taken en M door de machines, en door middel van takken aan te geven of een machine geschikt is voor een taak kunnen we dit probleem modelleren als een toewijzingsprobleem.
Optimization Group
27/44
Herleiding tot maximale-stroom-probleem Elk toewijzingsprobleem is eenvoudig te herleiden tot een maximale-stroom-probleem. We illustreren dit aan de hand van bovenstaand huwelijksprobleem. Daartoe voegen we twee knopen s en t toe aan het netwerk en voor elke jongen j ∈ J een tak (s, j), en voor elk meisje m ∈ M een tak (m, t). Geef deze takken capaciteit 1, en alle takken in het oorspronkelijke netwerk ook capaciteit 1. Dan is het duidelijk dat het maximale aantal huwelijken gelijk is aan de maximale waarde van een stroom van s naar t in het nieuwe netwerk. j5
1
j4
1 s
1
j3
1
j2
j1
m4
1
1
1 1
1
1
1
m3
1 1
m2
1 1 1
t
1
m1
Optimization Group
28/44
Oplossing van het huwelijksprobleem
1 m2
1j1
t
0j1 1j1 m1
1j
j2
1j1
m3
1
0j
1
j3
m4
0j
0j1
1
1j1
j4
0j1
1j
s
0j1
1
11 j
j5
1j
1j1
Het is eenvoudig om een stroom met waarde 3 te vinden. De stroomwaarden zijn 1 op de blauwe takken en 0 op de overige takken.
0j1
0j1
j1
Om na te gaan of deze stroom optimaal is vormen we het bijbehorende hulpnetwerk. Optimization Group
29/44
Oplossing van het huwelijksprobleem
0j1
0j 1
j2
m4
m3 1j1
0j1 1j1
m2
1j1
t
j4
m3
s
j3
t m2
1j 1
1j1
j5
m4
3
0j 1
1j 1
1j 1 0j1 j4 1j 1j1 1 0j1 j 0j1 j5
1 0j
s
j2
m1
j1
m1
j1
Omdat alle capaciteiten 1 zijn en alle stroomwaarden 0 of 1, hebben de restcapaciteiten op de takken allemaal de waarde 1. Deze zijn daarom niet ingetekend in deze figuur. Door op de standaard manier te labelen vanuit s blijkt dat er geen doorbraak naar t mogelijk is. De gevonden stroom is dus optimaal. Bijgevolg is het maximale aantal huwelijken gelijk aan 3. Optimization Group
30/44
Dualiteitsstelling
j5
j5 m4 j4
m3
s
j3
j4 j3 t
j2
m2 j2
m4 m3 m2 m1
j1
m1
j1
J
M
Let op de nu gelabelde knopen. Dit zijn s, j1, j3, j5 en m3. Elke tak in het oorspronkelijke netwerk is incident met een niet-gelabelde jongen of met een gelabeld meisje. Definition 1 Een verzameling knopen C van knopen in een netwerk heet een knoopoverdekking als elke tak in het netwerk incident is met een knoop uit C . We hebben de volgende dualiteitsstelling voor het huwelijksprobleem. Theorem 2 (Stelling van K˝ onig-Egerv´ ary, 1931) Het maximale aantal huwelijken in een huwelijksprobleem is gelijk aan het minimale aantal knopen in een knoopoverdekking. Optimization Group
31/44
Het handelsreizigerprobleem
Optimization Group
32/44
Mijlpalen in de geschiedenis van het handelsreizigerprobleem
Jaar
Team
Aantal steden
1954
G. Dantzig, R. Fulkerson, and S. Johnson
49
1971
M. Held and R.M. Karp
64
1975
P.M. Camerini, L. Fratta, and F. Maffioli
100
1977
M. Gr¨otschel
120
1980
H. Crowder and M.W. Padberg
318
1987
M. Padberg and G. Rinaldi
532
1987
M. Gr¨otschel and O. Holland
666
1987
M. Padberg and G. Rinaldi
2392
1994
D. Applegate, R. Bixby, V. Chv´atal, and W. Cook
7397
1998
D. Applegate, R. Bixby, V. Chv´atal, and W. Cook
13509
2001
D. Applegate, R. Bixby, V. Chv´atal, and W. Cook
15112
Het record stond in 2001 op een optimale route langs 15.112 steden in Duitsland. De lengte van deze route is 1.573.084 km. De berekening vergde meer dan 18 CPU jaren. Voor de berekening werd een netwerk met 110 werkstations gebruikt, waardoor de oplossing binnen een paar maanden werd gevonden. Sinds 2004 staat het record op naam van een opgeloste TSP met 24.978 steden (alle plaatsen in Zweden). Optimization Group
33/44
Voorbeeld van een “facility location problem” centrum 1
centrum 2
3
3
winkel 1
4
4
4
3
6
winkel 2
4
winkel 3
Er zijn 3 oplossingen: C1
C2
3
3
C1 4
4
6
W1 W2 W3 Alleen C1 open Kosten: 16
4
3
4
W1 W2 W3 Alleen C2 open Kosten: 15 Optimization Group
C2
3
3
4
3
4
W1 W2 W3 C1 en C2 open Kosten: 17 34/44
Een ‘echt’ facility locatie probleem
12 centra:
; 60 winkels:
oplossing met 5 centra
Optimization Group
35/44
Moeilijkheidsgraad van het facility locatie probleem Het moeilijke deel van het probleem is om te bepalen welke centra moeten worden geopend om de laagste totale kosten te krijgen. Als er meerdere centra zijn, zeg k, dan kan dit op 2k − 1 manieren. aantal centra
aantal mogelijkheden
rekentijd
10
1023
0, 34 nsec.
20
1048575
0, 35 msec
30
1073741823
0, 36 sec
40
1099511627775
6, 1 min
50
1125899906842623
60
1152921504606846975
70
1180591620717411303423
4, 3 dagen 12 jaar 12478 jaar
Dit verschijnsel heet combinatorische explosie: als het aantal centra toeneemt, neemt de rekentijd exponentieel toe. Optimization Group
36/44
Heuristieken met kwaliteitsgarantie Stel dat in een optimale oplossing de totale kosten K ∗ zijn. Een (niet-optimale) oplossing, waarvoor de kosten K zijn, heet een α-benaderende oplossing als K ≤ α. ∗ K
Een effic¨ent algoritme dat voor elk facility location probleem een α-benaderende oplossing oplevert, met α vast, heet een α-benaderend algoritme. 1990: er bestaat geen 1-benaderend (dit is een exact!) algoritme. 1998: er bestaat geen 1, 463-benaderend algoritme (tenzij . . . ).
Optimization Group
37/44
Approximatie resultaten
α
Auteur
Methode
1 + log k
Hochbaum (1982)
Greedy
3,16
Shmoys et al. (1997)
LP rounding
2,408
Guha and Kuller (1998)
LP rounding + Greedy
1,736
Chudak (1998)
LP rounding
1,728
Charika and Guha (1999)
LP + Primal-dual + Greedy
1,610
Jain et al. (2001)
Greedy algorithm
1,582
Svridenko (2002)
LP rounding
1,517
Mahdian et al. (2002)
Revised Greedy algorithm
Harde ondergrens voor α: 1, 463. Optimization Group
38/44
Tekenverloop van kwadratische veeltermen Kwadratische veelterm-vergelijking: ax2 + bx + c = 0, abc-formule:
b x=− ± 2a
b2
a>0
4a < 0
b2
x x
s
a 6= 0.
b2 − 4ac . 2 4a
4a = 0
b2
x x
4a > 0
x x
a<0 Zes mogelijkheden voor de grafiek van een kwadratische veelterm. Optimization Group
39/44
Tekenvastheid (d.i. niet-negativiteit voor alle x) b2
4a < 0
a>0
b2
4a = 0
x
b2
4a > 0
x
x x
x
x
a<0
Er geldt dan en slechts dan als
ax2 + bx + c ≥ 0, a ≥ 0,
voor alle x b2 − 4ac ≤ 0.
c ≥ 0,
Dit geldt dan en slechts dan als de matrix
c
X=
b 2
b 2
a
positief semidefiniet is, ofwel als de eigenwaarden van de symmetrische matrix X niet-negatief zijn (notatie: X 0). Dit resultaat kan worden gegeneraliseerd naar willekeurige veeltermen van even graad. Optimization Group
40/44
Minimum bepalen van een veelterm Beschouw een willekeurige veelterm van even graad: p(x) = p0 + p1x + p2x2 + p3x3 + . . . + p2mx2m.
Er geldt p(x) ≥ 0 voor alle x dan en slechts dan als er een positief semidefiniete matrix X bestaat waarvan de overeenkomstige dwarsdiagonaalsommen gelijk zijn aan de co¨efficienten van p(x). We zeggen daarom: tekenvastheid van een veelterm is semidefiniet representeerbaar. Stel nu dat we de minimale waarde z ∗ van p(x) willen weten: z ∗ = min {p(x) : x ∈ R} .
Dan is z ∗ het grootste getal waarvoor de veelterm p(x) − z ∗ tekenvast is. Dus hebben we z ∗ = max {z : p(x) − z is tekenvast} .
De voorwaarde ‘p(x) − z is tekenvast’ is semidefiniet representeerbaar, en dus is dit probleem effici¨ent oplosbaar.
Optimization Group
41/44
Voorbeeld Stel dat we de kleinste waarde z ∗ willen vinden van de veelterm p(x) = 48 − 28x − 56x2 + 35x3 + 7x4 − 7x5 + x6.
Dan zoeken we de grootste waarde voor z zodanig dat p(x) − z = (48 − z) − 28x − 56x2 + 35x3 + 7x4 − 7x5 + x6 ≥ 0,
∀x ∈ R.
Dit komt neer op het oplossen van het volgende semidefiniete optimaliseringsprobleem
max z :
x x x x 11 12 13 14 x 12 x22 x23 x24 0 x x x x 13 23 33 34 x14 x24 x34 z + x11 2x12 2x13 + x22 2x14 + 2x23 2x24 + x33 2x34 x44
x44 = 48 = −28 = −56 = 35 = 7 = −7 = 1
Optimization Group
.
42/44
Oplossing van bovenstaand probleem (met behulp van SeDuMi) p(x) 100 80 60 40 20
x 2
2
20
4
40 60
Grafiek van p(x) = 48 − 28x − 56x2 + 35x3 + 7x4 − 7x5 + x6.
z ∗ = −58, 0214,
X=
48, 0000 − z ∗ −14, 0000 −35, 9129 −14, 0000
15, 8257
−35, 9129
9, 5291
7, 9709
−3, 4074
Optimization Group
7, 9709
9, 5291 −3, 4074
. 13, 8148 −3, 5000
−3, 5000
1, 0000
43/44
Een portret van prinses M´ axima
∗ Thanks
to Robert Bosch Mathematical Department Oberlin College, USA. Optimization Group
44/44
