Enkele basismodellen uit operationeel onderzoek Roel Leus
[email protected]
Studiedag Wiskunde 3e graad ASO 6 mei 2010
Inleiding •
Operationeel onderzoek (O.O.) = het gebruik van wiskundige technieken voor optimalisatie en voor analyse van “operaties” (< W.O. II)
•
Operaties = het gebruik van hulpmiddelen (kapitaal, materialen, technologie, menselijke vaardigheden/kennis, ...) bij de productie en distributie van goederen en diensten
•
Vbn.: routebepaling (GPS, “handelsreizigersprobleem”); productieplanning onder einde capaciteit; wachtlijntheorie; optimale strategieën bij kansspelen; …
•
Vandaag: Capita selecta uit cursussen 2e bach TEW en 2e/3e bach HIR Deterministische problemen 2
Agenda 1. Lineaire programmering
2. Geheeltallige programmering 3. Oefening
3
Productmix •
Productmix bij computerproducent: draagbare computers (notebooks) en desktop computers.
•
Onder de huidige marktomstandigheden, materiaalkost, en het bestaande productiesysteem, genereert elke draagbare computer 750 EUR winst en elke desktop 1000 EUR winst.
Hoeveel van elk product te produceren volgend kwartaal zodanig dat de winst wordt gemaximaliseerd? … mits beperkingen: 1. Elke computer (notebook & desktop) heeft een processorchip nodig. Vanwege beperkte capaciteit van onze leverancier beschikken we slechts over 10.000 van zulke chips. 2. Elke computer heeft intern geheugen nodig. Dit wordt geleverd in 512MB chips. Een draagbare computer heeft 512MB nodig (= 1 chip), een desktop vereist 1GB (= 2 chips). We beschikken over 15.000 geheugenchips voor het volgende kwartaal. 3. Elke computer wordt geassembleerd. Draagbare computer: gemiddeld 4 minuten assemblagetijd, desktop 3 minuten. In het volgende kwartaal zijn er 25.000 minuten assemblagetijd beschikbaar.
4
Formuleren van een LP-model (“lineair programma”) 1. Beslissingsvariabelen: x1 = aantal notebooks (in 1000'en) x2 = aantal desktops (in 1000'en) 2. Doelfunctie:
maximaliseer
750x1 + 1000x2
3. Beperkingen: x1 x1 4x1 x1
+ x2 + 2x2 + 3x2 x2
• •
10 15 25 0 0
Conclusie: formuleren van een lineair programma = definiëren van de beslissingsvariabelen, de lineaire doelfunctie en lineaire beperkingen Oplossen? Grafisch: indien slechts 2 variabelen… Algoritmisch: o.a. “simplex” – handmatig / via software 5
Grafische oplossingsmethode x2
10
1 7
8
1 x1+ x2 10
6 4
2 x + 2x 1
3
2
2
z = 750x1+ 1000x2
4x1+ 3x2 25
x1
0 0 • • •
2
4
15
6
8
10
Optimale oplossing: x1 = 1 en x2 = 7; of dus 1.000 notebooks produceren en 7.000 desktops, wat een winst van 7.750.000 EUR oplevert Belang “hoekpunt” (definitie “extreem punt” van een convexe verzameling) Stelling: als een LP-probleem een optimale oplossing heeft, dan is er ook een hoekpunt dat optimaal is 6
Software… o.a. Excel Solver add-in
7
LP in “standaardvorm” • Alle var. ≥ 0 • Op de tekenbeperkingen na enkel gelijkheden • Alle rechterleden ≥ 0 odb
x1 max z 750 1000 x2
x1 1 1 1 0 0 x 2 10 1 2 0 1 0 s1 15 4 3 0 0 1 s 25 2 s3
en
x1 0 x2 0 s 0 1 s2 0 s3 0 8
Stelsels van lineaire gelijkheden •
•
x1 1 1 1 0 0 x 2 10 1 2 0 1 0 s1 15 4 3 0 0 1 s 25 2 s3 0 1 1 1 0 1 2 0 1 0 0 5 0 4 1
5 of 15 35
of
s1 10 1 1 s2 15 1 x1 2 x2 s 25 4 3 3 BV = { s1,s2,s3 }
s1 5 1 1 x1 15 2 x2 1 s2 s 35 5 4 3 BV = { x1,s1,s3 }
• Stel niet-BV :=0 “basis-oplossing” (bo) indien oplossing uniek is; “toelaatbare basis-oplossing” (tbo) indien alle var. ≥ 0
9
Algebraïsche karakterisatie van extreme punten x2
= tbo
1
xi = 0 op de (andere) as
= ontoelaatb. bo
3
si = 0 oorspronkelijke -beperking bindend
2 x1
alle xi en si 0 in gebied
• Stelling: voor een LP-probleem komt de verzameling extreme punten overeen met de verz. tbo’s
10
Op zoek naar een optimale oplossing • We kunnen dus in principe elk LP-probleem met begrensde oplossing oplossen door alle extreme punten op te sommen… Probleem: aantal tbo’s is maximaal n m (met n = aantal var., m = aantal bep.) • In plaats van zo’n “brute-force” oplossingsmethode kunnen we beter: het “simplex-algoritme” empirisch: rekentijd gemiddeld genomen zowat lineair in n en m
11
Simplex-algoritme x2
10
1
8 6 4
2 3
2
x1
0 0
2
4
6
8
10
12
14
16
– Hoe ga ik van 1 tbo naar een andere? (pivots) – Kunnen we zorgen dat hierbij telkens de doelfunctie verbetert? – Wat met details zoals initializatie, convergentie, onbegrensde oplossingen, … ?
12
Assumpties LP 1. Proportionaliteit 2. Additiviteit Niet-lineaire programmering 3. Deelbaarheid Geheeltallige programmering (waarom dan toch LP gebruiken…?)
4. Zekerheid … 13
Agenda 1. Lineaire programmering
2. Geheeltallige programmering 3. Oefening
14
Opnieuw productieplanning… • productie tafels & stoelen arbeid (u) hout (m2) winst ($) tafels
1
9
8
stoelen
1
5
5
beschikbaar 6
•
45
max 8 x1 + 5 x2 odb
x1 + x2 9 x1 + 5 x2 x1 , x2 x1 , x2
≤ ≤ ≥
6 45 0 { 0, 1, 2, … }
• Hoe dit op te lossen? 15
LP-relaxatie Laat (voorlopig) de geheeltalligheids-eis vallen x2 hout
6 arbeid
5
doelfunctie
4 3 LP-optimum x1=3.75 x2=2.25
2 1
0
1
2
3
4
5
6
x1
16
Oplossingsruimte I(L)P (integer (linear) program) x2
• Oplossing LP-relaxatie: (3.75 , 2.25)
hout
6
• Wat als deze oplossing geheeltallig was geweest?
arbeid
5
doelfunctie
4
• Zal de geheeltallige doelfunctie-waarde >/
3 LP-optimum x1=3.75 x2=2.25
2 1
IP-optimum
0
1
x1 3
2
3
4
5
6
x1
x1 4
• Kunnen we LP gebruiken om IP op te lossen? Afronden lukt alleszins niet (altijd) • “Branching”, bvb. op x1 17
Branching • Vertakken: partitioneren van de zoekruimte x2 hout
6
arbeid
5
doelfunctie
4 3
2 1
0
1
2
3
4
5
6
x1
• Twee nieuwe LP-instanties. Herhaal… 18
“branch-and-bound” zoekboom 1 x = 15/4 1 x2 = 9/4
2
GUB 165/4 = 41
x1 4
x1 3
3
LUB 41 x1 = 4
LUB 39
x2 = 1.8 FATHOMED
4
x2 2
x2 1
5
x1 = 4.44 x2 = 1
LUB 40.55 = 40
INFEASIBLE
6
x1 5
GLB 40 x1 = 5 x2 = 0
INTEGER
7
x1 4
x1 = 4 x2 = 1 INTEGER
GLB 37 19
Geheeltallige variabelen • Toleranties… • Kunnen we LP gebruiken om IP op te lossen?
Afronden lukt niet altijd Branch-and-bound Cutting planes Branch-and-cut
• Voordelen van geheeltalligheids-eis Realistischer Flexibeler
• Nadeel: kan veel moeilijker zijn om op te lossen (rekentijd!) • Excel-solver (en andere software) 20
Cutting-plane algoritme x2
snede hout
6 arbeid
5 4 3 LP-optimum X1=3.75 X2=2.25
2 1
IP-optimum
0
1
2
3
4
5
6
x1 21
Agenda 1. Lineaire programmering
2. Geheeltallige programmering 3. Oefening
22
Oefening (< EX 2e bach TEW jan. ’07) Drie personen moeten samen zeven taken uitvoeren. Elke persoon neemt een aantal taken voor zijn rekening. Een taak kan niet gesplitst worden over meerdere personen. Elke taak heeft een vaste duurtijd:
taak 1: 4 minuten taak 2: 8 minuten taak 3: 2 minuten taak 4: 5 minuten taak 5: 9 minuten taak 6: 7 minuten taak 7: 5 minuten
1
Persoon 1:
Persoon 2: Persoon 3:
3
2
7
4 5
6 tijd Lengte werkplan
De taken moeten worden verdeeld over de drie personen. Geef een lineaire formulering (eventueel geheeltallig) die toelaat een toewijzing van taken te vinden zodat de lengte van het volledige werkplan wordt geminimalizeerd.
23
Oplossing (formulering) • Beslissingsvariabelen ? X11 = 1 indien persoon 1 taak 1 uitvoert = 0 in het andere geval Xpt = 1 indien persoon p taak t uitvoert = 0 anders (p=1,2,3, t=1,…,7)
• Beperkingen ? X11 + X21 + X31 = 1 X1t + X2t + X3t = 1
voor t = 1,…,7
24
Doelfunctie ? • minimalizeer
MAX{einde1,einde2,einde3}
met einde1 = 4X11 + 8X12 + 2X13 + … einde2 = 4X21 + 8X22 + 2X23 + … … • z z z
min z ≥ 4X11 + 8X12 + 2X13 + … ≥ 4X21 + 8X22 + 2X23 + … ≥ 4X31 + 8X32 + … 25
Excel Solver
26
Extra: combinatorische restricties • de persoon die taak 2 doet, mag taak 5 niet uitvoeren • de persoon die taak 2 doet, moet ook taak 5 uitvoeren • als persoon 1 taak 1 en taak 2 uitvoert, dan moet hij / zij ook taak 3 uitvoeren
27
Extra (2): symmetrie (research topic) symmetrie: X11 = X13 = X17 = X22 = X24 = X35 = X36 = 1 is equivalent met X21 = X23 = X27 = X12 = X14 = X35 = X36 = 1 1
Persoon 1:
Persoon 2: Persoon 3:
2
3
7
4 5
6 tijd Lengte werkplan 28
Vragen ?
29
