Opgave 1.3 uit het boek Koop voor € 1.000.000 aandelen Vilyps, Dikstaal en Multilever. fonds Vilyps Dikstaal Multilever
prijs/aandeel € 50 € 20 € 75
dividend/aandeel €7 €6 €9
Minimaal 30% is in Vilyps belegd. Minstens driemaal zoveel geld is in Multilever belegd als in Dikstaal. Maximaliseer de verwachte opbrengst. Formuleer eerst het LP model: Max z.d.d.
Z = 7v + 6d + 9m 50v + 20d + 75m = 1.000.000 50v ≥ 300000 75m ≥ 60d v, d, m ≥ 0
Vereenvoudig de getallen wat: Max z.d.d.
Z = 7v + 6d + 9m 10v + 4d + 15m = 200000 v ≥ 6000 5m – 4d ≥ 0 v, d, m ≥ 0
Max z.d.d.
Z = 7v + 6d + 9m 10v + 4d + 15m = 200000 v ≥ 6000 5m – 4d ≥ 0 v, d, m ≥ 0
v ≥ 6000: Vervang v’ = v – 6000, ofwel v = v’ + 6000: Max z.d.d.
Z = 7v’ + 6d + 9m + 42000 10v’ + 4d + 15m = 140000 5m – 4d ≥ 0 v’, d, m ≥ 0 (v ≥ 6000 wordt nu v’ ≥ 0)
Max z.d.d.
Z = 7v’ + 6d + 9m + 42000 10v’ + 4d + 15m = 140000 4d – 5m ≤ 0 (zet in de standaard vorm ≤) v’, d, m ≥ 0
Voer een slack variabele s in: Max z.d.d.
Z = 7v’ + 6d + 9m + 42000 10v’ + 4d + 15m = 140000 4d – 5m + s = 0 v’, d, m ≥ 0
Probleem: Oorsprong v’ = d = m = 0 is geen oplossing !!
Voer een hulpvariabele p in (mag eigenlijk niet !): Max z.d.d.
Z = 7v’ + 6d + 9m – Mp + 42000 10v’ + 4d + 15m + p = 140000 4d – 5m + s = 0 v’, d, m ≥ 0
De extra term – Mp in de doelfunctie zorgt dat (uiteindelijk) p = 0 wordt. (M is een heel groot getal). Basisvariabelen s en p mogen niet in Z voorkomen: Z – 7v’ – 6d – 9m + Mp = 42000 10v’ + 4d + 15m + p = 140000 4d – 5m +s =0 Vegen: Z – (10M+7)v’ – (4M+6)d – (15M+9)m 10v’ + 4d + 15m + p 4d – 5m
= 42000-140000M = 140000 +s=0
Simplexiteratie: Z – (7+10M)v’ – (6+4M)d – (9+15M)m 10v’ + 4d + 15m + p 4d – 5m
= 42000-140000M = 140000 +s=0
Z – v’ – 18/5d +(M+3/5)p 2/3v’ + 4/15d + m + 1/15p 10/3v’ + 16/3d + 1/3p + s
= 126000 = 28000/3 = 14000/3
Simplex iteratie : Z – v’ – 18/5d +(M+3/5)p 2/3v’ + 4/15d + m + 1/15p 10/3v’ + 16/3d + 1/3p + s
= 126000 = 28000/3 = 14000/3
Vegen levert: Z +5/4v’ +(M+33/40)p + 27/10s 1/2v’ + m + 1/20p - 1/20s 5/8v’ + d + 1/16p + 3/16s
= 157500 = 7000 = 8750
Alle coëfficiënten in de Z vergelijking zijn positief, dus: Optimale oplossing is bereikt: v = 6000 (v’ = 0), m = 7000,
d = 8750,
Z = 157500
Koop 6000 aandelen Vilyps, 8750 aandelen Dickstaal en 7000 aandelen Multilever en gij zult € 157500 dividend opstrijken.
Tie breaking in de simplex methode Tijdens de Simplexmethode kan op een aantal momenten onduidelijk zijn wat je moet doen: 1. Variabele die de basis in gaat: Zoek de grootste coëfficiënt in de doelfunctie. Wat als er twee grootste zijn? Voorbeeld: Z = 3x1 + 3x2 +x4. Antwoord: Kies er maar een (Bv. de eerste) 2. Variabele die uit de basis gaat: Kijk hoe groot de variabele kan worden (quotiëntregel). Wat doe je als er coëfficiënten negatief zijn? Voorbeeld: 2a. 2x1 + x3 = 4, dan x1 ≤ 4/2 = 2 (want x3 ≥ 0) Normale situatie. 2b. -2x1 + x3 = 4, dan x1 ≥ -4/2 = -2. Dit is altijd waar, dus niets te controleren. 2c. 2x1 + x3 = -4, dan x1 ≤ -4/2 = -2. Niet feasible. Kan niet! Rekenfout! 2d. -2x1 + x3 = -4, dan x1 ≥ 4/2 = 2. Kan niet, want x1 = 0 was feasible. Rekenfout! Gevolg: Quotiëntregel alleen als pivotelement positief en rechterlid niet-negatief.
3. Twee quotiënten zijn gelijk. Je loopt tegen twee constraints tegelijk op. Dit kan leiden tot oneindige loop (cycling), waarbij stappen ter lengte 0 worden gemaakt, totdat een oud tableau weer terugkomt. Hiervoor zijn oplossingen bekend (kies een andere richting).
4. Er is geen uittredende variabele, omdat alle coëfficiënten in pivotkolom ≤ 0 zijn. Het probleem is dan onbegrensd (Meestal fout in de modellering).
5. Er zijn meer optimale oplossingen met dezelfde doelwaarde. De Simplexmethode vindt alleen de eerste. Simplexalgoritme kan verder itereren in een richting waarin de doelfunctie niet verbetert (niet-basis variabele met cöefficiënt 0). Zo kun je ook andere optima vinden.
Twee fasen methode. De Big-M methode geeft bij implementatie numerieke problemen (cancellation, aftrekken van grote getallen is onbetrouwbaar). In de twee fasen aanpak wordt eerst het deel met de M opgelost (resulteert in feasible punt). Vervolgens wordt het beste punt gevonden.
Originele probleem: Min Z = 0.4 x1 + 0.5 x2 z.d.d. 0.3x1 + 0.1x2 ≤ 2.7 0.5x1 + 0.5x2 = 6 0.6x1 + 0.4x2 ≥ 6 en x1, x2 ≥ 0 Simplex vorm: Min Z = 0.4 x1 + 0.5 x2 + Mx4 + Mx6 z.d.d. 0.3x1 + 0.1x2 + x3 = 2.7 0.5x1 + 0.5x2 + x4 = 6 0.6x1 + 0.4x2 –x5 + x6 = 6 en x1, x2, x3, x4, x5, x6 ≥ 0 Fase 1 (alleen het Big-M deel van de doelfunctie): Min Z = x4 + x6 z.d.d. 0.3x1 + 0.1x2 + x3 = 2.7 0.5x1 + 0.5x2 + x4 = 6 0.6x1 + 0.4x2 –x5 + x6 = 6 en x1, x2, x3, x4, x5, x6 ≥ 0 Deze fase moet eindigen in Z = 0: x4 = x6 = 0, anders is er geen toegelaten oplossing. Je vindt hiermee een toegelaten oplossing voor het originele probleem.
Fase 2 (nu is x4 = x6 = 0, de andere variabelen zoals gevonden in de vorige fase): Min Z = 0.4 x1 + 0.5 x2 z.d.d. 0.3x1 + 0.1x2 + x3 = 2.7 0.5x1 + 0.5x2 = 6 0.6x1 + 0.4x2 –x5 = 6 en x1, x2, x3, x5 ≥ 0 Hiermee vind je vervolgens de beste toegelaten oplossing.
Big-M krijg je als de nuloplossing in het originele probleem niet toelaatbaar is. De eerste fase levert een toelaatbare oplossing. De tweede fase levert een optimale toelaatbare oplossing
De simplexmethode is niet eindig (cycling, zie practicum) maar in de praktijk wel. De simplexmethode is niet polynomiaal (Klee, Minty, zie practicum) maar in de praktijk wel: ca. 1.5m iteraties, maximaal 3m (m = #constraints) Rekentijd ∼ m3.
Inwendige puntmethoden zijn bewijsbaar polynomiaal. In de praktijk is het aantal iteraties daarvan constant, ca 20 – 80.
