Optimalisering WI 2608 Docent: Hans Melissen, EWI kamer 7.080 e-mail:
[email protected] tel: 015-2782547 Studiemateriaal op : http://www.isa.ewi.tudelft.nl/~melissen (kijk bij onderwijs → WI 2608) college:
Maandag 3+4 zaal F Vrijdag 3+4 zaal E
Boek: F.S. Hillier and G.J. Lieberman: Introduction to Operations Research, 8th Ed., McGraw-Hill, 2005 + CD-ROM. ISBN 007-123828-X
Operations Research (OR, besliskunde) Management Science (MS) OR: - deterministisch: Optimalisering (H 1-12) - stochastisch:
Wachttijdtheorie (H 16) Risicoanalyse Speltheorie (H14) Voorraadbeheer (H 18) Simulatie (H 20)
Optimalisering (Mathematical Programming): Lineair (LP)
- Continu, simplexmethode (H 1-7) - Geheeltallig (+ binair) (H 11) - Mixed integer
Niet-lineair (NLP) (H12)
Lineaire programmering. Toepassingen: productieplanning mengproblemen locatieproblemen transportproblemen routering projectplanning aandelenportefeuilles
Geschiedenis: 1947 George B. Dantzig: Simplexmethode voor LP Uitvoerbaar door opkomst van de computer 1984 Karmarkar: polynomiaal algoritme voor LP Voorpaginanieuws in de New York Times
Een dieet voor een jongen van 19 moet dagelijks 3000 kcal, 81 gram eiwit, 100 gram vet en 410 gram koolhydraten bevatten. kaas bruine boterham boter (5g) aardappel (lepel) bruine bonen (lepel) braadworst (125 g) Mars
kcal 75 85 20 40 55
eiwit 5 3 0 1 4
vet 6 1 2 0 0
koolhydr 0 16 0 8 8
Prijs 0,20 0,12 0,04 0,05 0,05
230
17
18
1
0,75
240
3
11
32
0,90
Maak een zo goedkoop mogelijk dieet met deze ingrediënten: Min z.d.d.
20x1 + 12x2 + 4x3 + 5x4 + 5x5 + 75x6 + 90x7 75x1 + 85x2 + 20x3 + 40x4 + 55x5 + 230x6 + 240x7 ≥ 3000 5x1 + 3x2 + 0x3 + 1x4 + 4x5 + 17x6 + 3x7 ≥ 81 6x1 + 1x2 + 2x3 + 0x4 + 0x5 + 18x6 + 11x7 ≥ 100 0x1 + 16x2 + 0x3 + 8x4 + 8x5 + 1x6 + 32x7 ≥ 410 kaas brood boter aardap bonen worst Mars Prijs ? ? ? ? ? ? ? ?
alle xi ≥ 0
50
51,3
4,56
3,3
4,56
boon ≤ aardappel boter ≤ brood
3,8
brood ≤ 8
12,7
8
8
35,3
aardappels ≤ 6
1,9
8
8
6
6
0,04
5,8
7,51
19,9
40
8,2
25,6 25,6
0,02
4,87 5,57
Mars ≤ 1
8
6
6
154
1
117,96
Mars ≤ 5
8
6
6
26
5
25,56
-
-
-
-
-
Worst ≤ 20
-
-
-
Conclusie: Jongens minstens 5,8 Marsen per dag, meisjes 3,6!
Voorbeeld: productieplanning Bedrijf fabriceert producten A, B, C, D Productiefasen: assemblage, afronding, verpakking Productietijden (uren) per eenheid:
Assemblage Afronding Verpakking
A 0,70 0,55 0,24
grondstoffen Winst
1,9 €4,80
productietijden (uren) B C 0,75 0,55 0,82 0,80 0,32 0,45 2,5 €12,00
1,8 €6,00
D 0,34 0,55 0,27
Beschikbaar 400 uur 480 uur 220 uur
2 €7,20
Aanwezige grondstoffen: 1500 eenheden Order voor volgende week: 100 eenheden A Al het geproduceerde wordt afgenomen Vraag: Hoeveel moet je produceren voor maximale winst? Formulering: Beslissingsvariabelen: xA = aantal eenheden A xB = aantal eenheden B xC = aantal eenheden C xD = aantal eenheden D B
Model: Maximaliseer
Z = 4,8xA + 12xB + 6xC + 7,2xD
z.d.d.
en
0,70xA + 0,75xB + 0,55xC + 0,34xD ≤ 400 0,55xA + 0,82xB + 0,80xC + 0,55xD ≤ 480 0,24xA + 0,32xB + 0,45xC + 0,27xD ≤ 220 1,9xA + 2,5xB + 1,8xC + 2xD ≤ 1500 xA ≥ 100 xA, xB, xC, xD ≥ 0
Oplossing:
xA = 100,0 xB = 330,15 xC = 0 xD = 242,31 Z = 6186,46
B
B
B
B
B
(assemblage) (afronding) (verpakking) (grondstoffen) (order)
B
B
Algemene aannamen voor dergelijke problemen: Proportionaliteit:
Productie van 7 eenheden kost 7 keer zoveel, vergt 7 keer zoveel grondstoffen
Additiviteit:
De winst van twee producten is de som van de afzonderlijke winsten
Deelbaarheid:
Beslissingsvariabelen kunnen willekeurige reële waarden aannemen (niet alleen geheeltallig)
Lineair Programmeren (LP) = Lineair Optimaliseren (LO) Programmeren = plannen Lineair = alle functies zijn lineair: Additief:
f(x+y) = f(x) + f(y) voor alle x, y
Multiplicatief:
f(λx) = λf(x)
Continue reële variabelen
voor alle λ, x
Lineaire functies: x → 3x (x1, x2) → 5x1 – 7x2 x → 6x – 17
niet lineair
x → ax (a, x) → ax niet-lineair 3x12 + 5log x2
niet-lineair
substitueer x1 = √y1, x2 = exp(y2) levert 3y1 + 5y2
na substitutie lineair.
Niet-lineaire functies kunnen soms bij benadering gelineariseerd worden
Opgave Een kolencentrale verwerkt steenkoolsoorten A en B om energie op te wekken. De steenkool wordt eerst verpulverd en daarna verbrand om stoom te maken voor het aandrijven van stoomturbines. De vraag is in welke verhouding de steenkoolsoorten verwerkt moeten worden voor de maximale productie van energie, gegeven een aantal beperkende voorwaarden. Zo zijn milieueisen opgelegd voor de gas- en roetuitstoot. De roetuitstoot mag hooguit 12 kg per uur zijn, en het aantal deeltjes zwavel per miljoen gasdeeltjes mag niet meer dan 3000 zijn. De verbranding van 1 ton kolensoort A geeft een roetuitstoot van 0,5 kg per uur en 1 ton kolensoort B geeft een roetuitstoot van 1 kg per uur. De kolensoort A heeft de eigenschap dat op elke miljoen deeltjes die na verbranding van deze kolensoort vrijkomen er 1800 zwaveldeeltjes zijn, terwijl voor kolensoort B het aantal zwaveldeeltjes 3800 is op elke miljoen vrijgekomen gasdeeltjes. De kolensoorten A en B stoten per verbrande ton evenveel deeltjes uit. De kolensoorten worden per trein aangevoerd en de aanvoer is beperkt tot 20 ton per uur. De capaciteit van de verpulverinstallatie is ook beperkt: 16 ton kolensoort A per uur als A de enige zou zijn en 24 ton kolensoort B per uur als B de enige zou zijn. Ten slotte geeft 1 ton kolensoort A na verbranding 24 000 pond stoomenergie en 1 ton kolensoort B geeft 20 000 pond stoomenergie. Formuleer het probleem als een LP probleem. Los het (grafisch) op.
Grafische oplosmethode (2 variabelen) Max Z = 24x1 + 20x2 z.d.d. x1 + x2 ≤ 20 0,5x1 + x2 ≤ 12 1 1 x + x2 ≤ 1 1 16 24 12x1 - 8x2 ≥ 0 x1, x2 ≥ 0
(transportbeperking) (roetuitstoot) (verpulvercapaciteit) (zwaveluitstoot) (hoeveelheden)
Hint: arceer telkens de niet-toegelaten gebieden!
Opgave: Los op met de grafische methode: max Z = 5x + 23y z.d.d. 2x + 9y ≤ 24 2x – 5y ≤ 3 x, y ≥ 0 Teken de lijn 2x + 9y = 24: 8 3
x=0
→
y=
y=0
→
x = 12 8
Lijn door (0, 3 ) en (12,0). Probeer (0,0): 2·0 + 9·0 = 0 ≤ 24, dus (0,0) ligt aan de goede kant. Oplossing: Hoekpunten van het toelaatbare gebied zijn: (0,0) 3 ( 2 ,0)
Z=0 15 Z = 2 = 7,5
21 3 , ) 4 2 8 (0, 3 )
Z=
(
Z=
237 4 184 3
= 59,25 = 61,3333
Algemene formulering LP probleem Probleem: n producten j = 1, …, n m grondstoffen i = 1, …, m Van grondstof j is bi aanwezig Op product j wordt cj winst gemaakt per eenheid Voor product j is aij eenheden grondstof i nodig Vraag: hoeveel maken zodat de winst maximaal is?
LP Model: Maak xj eenheden van product j (beslisvariabelen). Max Z = c1x1 + c2x2 + … + cnxn z.d.d. a11x1 + a12x2 + … + a1nxn ≤ b1 a21x1 + a22x2 + … + a2nxn ≤ b2 …
en
…
…
…
…
…
…
…
am1x1 + am2x2 + … + amnxn ≤ bm x1, x2 …, xn ≥ 0
n
Max
Z = ∑cjxj j =1
n
z.d.d.
∑a x
en
xj ≥ 0
j =1
ij
j
≤ bi
voor i = 1, 2, …, m voor j = 1, 2, …, n
Standaardvorm voor een LP probleem: Max
Z = c1x1 + c2x2 + … + cnxn
z.d.d. a11x1 + a12x2 + … + a1nxn ≤ b1 a21x1 + a22x2 + … + a2nxn ≤ b2 …
…
…
…
…
…
…
…
am1x1 + am2x2 + … + amnxn ≤ bm en
x1, x2 …, xn ≥ 0
Terminologie: Beslisvariabelen (decision variables): xj Parameters: cj, aij Doelfunctie, objectfunctie (objective function): Z Begrenzingen (constraints)
Terminologie Oplossing: Willekeurige keuze van de beslisvariabelen
Toelaatbare oplossing (feasible solution): Oplossing die aan alle beperkingen voldoet
Toelaatbaar gebied (feasible region): Verzameling van alle toelaatbare oplossingen
Niet-toelaatbare oplossing: Oplossing die aan minstens één beperking niet voldoet
Optimale oplossing: Toelaatbare oplossing met optimale doelwaarde.
Een toelaatbaar gebied is meestal begrensd en niet leeg, maar dat hoeft niet
Onbegrensd toelaatbaar gebied
Leeg toelaatbaar gebied
Optimale oplossingen hoeven niet uniek te zijn:
Nog extremer: Als de doelfunctie Z = 0 is, zijn alle toegelaten waarden optimaal!
Een begrensd toelaatbaar gebied in R2 wordt gedefinieerd door n lineaire ongelijkheden. Hoeveel hoekpunten (h) kan dit gebied hebben? Voorbeeld:
N=3→h=3
N=5→h=5
h → h-1+2 = h+1
Oplossing:
h = n.
n = 5, h = 3 ??? Betere oplossing:
h≤n
Nog betere oplossing:
3≤h≤n
Kan elke h met 3 ≤ h ≤ n? Kan h = 0? x≤0 ∧x≥1
(kan dus als n ≥ 2)
Kan h = 1? x ≥ 0 ∧ y ≥ 0 ∧ x+y ≤ 0
(mogelijk als n ≥ 3)
Kan h = 2? x≤0 ∧x≥0∧y≤1 ∧y≥0
(mogelijk als n ≥ 4)
De echte oplossing is dus: n = 2:
h=0
n = 3:
h = 0, 1, 3
n ≥ 4:
0≤h≤n
Zonder de eis begrensd toelaatbaar gebied is het antwoord: n = 0:
h=0
n = 1:
h=0
n = 2:
h = 0, 1
n ≥ 3:
0≤h≤n
Het toegelaten gebied is een gebied in Rn dat wordt bepaald door lineaire ongelijkheden en is dus de doorsnijding van halfruimten. Dit definieert een “polytoop” met hoekpunten, ribben, zijvlakken, etc. Wat is een hoekpunt? n lineaire ongelijkheden bepalen in n dimensies normaal gesproken een punt. Bij n van de lineaire ongelijkheden hoort dus een punt: hoekpunt. Als dit hoekpunt toelaatbaar is heet het een toelaatbaar hoekpunt (Corner Point Feasible (CPF) solution) Hoeveel hoekpunten zijn er bij n variabelen en m ongelijkheden?
⎛ m⎞ ⎜⎜ ⎟⎟ ⎝n⎠ Voorbeeld: 50 variabelen, 150 constraints, aantal hoekpunten is: 20128660909731932294240234380929315748140 ≈ 2·1040 Als je 1 miljard hoekpunten per seconde controleert ben je na 6·1020 jaar klaar!
