Wiskunde D assignment problem Hier stonden ooit namen
Inhoud
Wat?
Pagina
Het probleem
2
Probleem analyse
34
Oplossing adjacency assignment
56
Oplossing gerneral assignment via hungarian algorithm
712
Oplossing adjacency assignment via cover
1325
Soorten wiskunde
2627
Voorbeeld
28
Beoordelingsblad
29
1
Het probleem De hele dag en overal om je heen wordt er gecombineerd. Denk bijvoorbeeld aan het schoolrooster, deze moet voor docenten en leerlingen zo optimaal mogelijk zijn. Of denkt bijvoorbeeld aan de postbezorger die iedere dag langskomt. Die heeft zijn route op een bepaalde manier gecombineerd, waardoor hij zijn route het snelst aflegt. De optimale combinatie dus. Ook maak je zelf de hele dag door, zonder dat je het vaak doorhebt, optimale combinaties. Als je bijvoorbeeld naar school fietst, fiets je altijd de snelste, en dus de meest optimale route. Of als je boodschappen gaat doen, zal je niet kris kras, als een kip zonder kop door de winkel lopen. Je volgt meestal een enigszins samengestelde route, die je in de kortste tijd, langs al de benodigde producten leidt. De optimale route wordt ook wel het handelsreizigersprobleem genoemd. Het handelsreizigersprobleem werd al in 18321 beschreven. Handelaren moesten vroeger namelijk lange afstanden afleggen tussen de verschillende steden waar ze handel mee dreven. Het reizen ging in die tijd ook lang niet zo snel als nu, waardoor het voor de handelaren belangrijk was om de meest optimale route te bepalen. Kleine problemen zijn door deze te analyseren en er een beetje mee te puzzelen nog wel op te lossen. Echter zijn er ook problemen waar miljoenen al dan geen miljarden mogelijkheden voor zijn. Als je van deze problemen alle mogelijkheden zelf wilt na gaan ben je miljoenen jaren bezig, waardoor dit onmogelijk is. Echter door de komst van de computer en de ‘’Computatonal Sciences’’ zijn problemen veel sneller op te lossen. Maar over een probleem met miljarden oplossingen zou een computer nog steeds veel en veel te lang doen. Kortom, er moest een andere methoden gevonden worden. In dit verslag gaan we daar verder op in. Zo worden in dit verslag verschillende strategieën (algoritmes) uitgelegd. Door deze algoritmes zijn we in staat ook heel grote problemen relatief snel op te lossen.
1
bit.ly/1Iq41Dq bron
2
Probleem analyse Het toewijzingsprobleem Er is een aantal personen en een aantal banen. Elk persoon kan toegewezen worden aan elke baan. De banen hebben een bepaalde waarde. Elk persoon moet worden toegewezen aan een baan en precies één baan moet worden toegewezen per persoon zodat de uiteindelijke waarde zo hoog of zo groot mogelijk is. Het general assignment problem is het probleem in het geheel van het toewijzen van waardes aan personen zodat de uitkomst ervan zo hoog mogelijk is zonder dat een baan twee keer wordt gekozen door een persoon of eenvoudiger gezegd het kiezen van waardes uit een adjacency matrix op zo'n manier dat je de hoogste waarde haalt. Het simple assignment problem is het opsplitsen van het general assignment problem in deelproblemen om zo uiteindelijk een adjacency matrix zodanig te vereenvoudigen totdat het general assignment problem eenvoudig op te lossen is. Dit vereenvoudigen wordt gedaan door de waardes die de banen hebben om te zetten in énen en nullen of door de adjacency matrix een cover te geven waardoor je kan bepalen waar de énen moeten komen te staan en je kan er mee uitrekenen wat de maximale waarden zijn zodat je een heel klein beetje een richtlijn hebt in welke buurt je antwoord moet uitkomen als je het goed wil hebben. 3
Voorbeeld Al zijn er drie personen en drie banen. En persoon één is geschikt voor baan 1,2 en 3, persoon twee is geschikt voor baan 3 en persoon drie is geschikt voor baan 1 en 2. Wat zijn dan de mogelijkheden? Eerst kijk je hoe de matrix eruit gaat zien. Een 1 staat voor geschikt voor een baan en een 0 staat voor ongeschikt voor een baan: { 1 1 1 } { 0 0 1 } { 1 1 0 } Nu kijk je welke oplossingen er zijn dat alle banen één keer bezet zijn. { 1*1 1 } { 1 1*1 } { 0 0 1*} En { 0 0 1*} { 1 1*0 } { 1*1 0 } In dit geval zijn er twee oplossingen die de hoogste uitkomst hebben.
4
Oplossing adjacency assignment problem Persoon\baan A
B
C
D
Jesse
0
1
1
0
Tim
1
0
0
0
Niels
1
1
1
0
Patricia
0
0
0
1
Stap 1 : Streep een 1tje aan die alleen in de rij en kolom staan Persoon\baan A
B
C
D
Jesse
0
1
1
0
Tim
0
0
1
0
Niels
1
1
1
0
Patricia
0
0
0
1
Herhaal dit totdat er geen 1tjes meer zijn die alleen in de rij en kolom staan. Stap 2 : Streep een 1tje aan die alleen in de kolom of rij staan. Persoon\baan A
B
C
D
Jesse
0
1
1
0
Tim
0
0
1
0
Niels
1
1
1
0
Patricia
0
0
0
1
Herhaal totdat er geen 1tjes meer alleen in de kolom of rij staan. Vergeet niet stap 1 te herhalen voordat je stap 2 nog een keer herhaald.
5
Stap 1 herhaling 1 : Streep een 1tje aan die alleen in de rij en kolom staan Persoon\baan A
B
C
D
Jesse
0
1
1
0
Tim
0
0
1
0
Niels
1
1
1
0
Patricia
0
0
0
1
Herhaal dit totdat er geen 1tjes meer zijn die alleen in de rij en kolom staan. Stap 2 herhaling 1 : Streep een 1tje aan die alleen in de kolom of rij staan. Persoon\baan A
B
C
D
Jesse
0
1
1
0
Tim
0
0
1
0
Niels
1
1
1
0
Patricia
0
0
0
1
Herhaal todat er geen 1tjes meer alleen in de kolom of rij staan. Vergeet niet stap 1 te herhalen voordat je stap 2 nog een keer herhaald. Stap 1 herhaling 2 : Streep een 1tje aan die alleen in de rij en kolom staan Persoon\baan A
B
C
D
Jesse
0
1
1
0
Tim
0
0
1
0
Niels
1
1
1
0
Patricia
0
0
0
1
Herhaal dit totdat er geen 1tjes meer zijn die alleen in de rij en kolom staan. Stel nou je hebt na stap 2 nog steeds je matrix niet ingevuld ga dan naar stap 3 Stap 3 : Kies gewoon een 1tje. En ga dan weer naar stap 1
6
Oplossing general assignment problem via hungarian algorithm2 Persoon\Baan A
B
C
D
Jesse
20
60
50
54
Tim
60
30
80
75
Niels
70
90
80
70
Patricia
65
80
75
70
Stap 1 : Maak er een minimizing matrix van: Persoon\Baan A
B
C
D
Jesse
80
40
50
46
Tim
40
70
20
25
Niels
30
10
20
30
Patricia
35
20
25
30
Wij hebben zojuist van de maximizing matrix (alle assingnments die je maakt moeten bij elkaar zo hoog mogelijk zijn) een minimizing matrix (alle assingnments die je maakt moeten bij elkaar zo laag mogelijk zijn) gemaakt. Dit doe je door 100X te doen voor ieder vak in de tabel (uitgaande van dat het maximum dat je kan halen 100 is). Stap 2 : Krijg minimaal 1 nul in ieder rij. Persoon\Baan A
B
C
D
Jesse
8040=40
4040=0
5040=10
4640=6
Tim
4020=20
7020=50
2020=0
2520=5
Niels
3010=20
1010=0
2010=10
3010=20
Patricia
3520=15
2020=0
2520=5
3020=10
Om in iedere rij een 0 te krijgen nemen we het laagste getal van iedere kolom en trekken we die af van alle getallen in die rij. Alle nullen zijn optimale oplossingen al
2
bit.ly/1ImNArz en bit.ly/1ImOKTO bron oplossing
7
zouden we geen rekening hoeven te houden met het feit dat iedere baan maximaal en minimaal 1 persoon nodig heeft. Maar dat moeten we helaas wel dus. Stap 3 : Krijg minimaal 1 nul in iedere kolom Persoon\Baan A
B
C
D
Jesse
4015=25
00=0
100=10
65=1
Tim
2015=5
500=50
00=0
55=0
Niels
2015=5
00=0
100=10
205=15
Patricia
1515=0
00=0
50=5
105=5
We doen nu precies hetzelfde als bij stap 2 alleen dan bij de kolom. Je zoekt het laagste getal in de kolom en trekt die van de rest van de getallen in die kolom af. De nullen die we nu hebben zijn optimaal uitgaande dat iedere persoon/baan 1 of meer baan/persoon aankan. Maar dat kan niet dus. Stap 4 : Bedek alle nullen met zo min mogelijk verticalen en horizontale lijnen. Persoon\Baan A
B
C
D
Jesse
25
0
10
1
Tim
5
50
0
0
Niels
5
0
10
15
Patricia
0
0
5
5
Dit doe je door een paar kleineren stappen: 1 Vindt de kolom/rij met de meeste nullen en kras die kolom/rij door. 2 Zijn alle nullen bedekt? Zo nee ga weer naar stap 1. Is het aantal doorgekraste rijen en kolommen gelijk aan de hoeveelheid banen/personen? Zo ja ga naar stap 7. Zo nee ga naar de volgende stap. Helaas hebben wij er 3 en dat is minder dan 4 dus wij gaan naar stap 5 Stap 5 : Zoek het laagste niet doorgekraste getal en trek die van alle niet doorgekraste af. En tel die op bij allen dubbel doorgekraste. Persoon\Baan A
B
C
D
Jesse
251=24
0
101=9
11=0
Tim
5
50+1=51
0
0
Niels
51=4
0
101=9
151=14
Patricia
0
0+1=1
5
5
8
Stap 6 : Haal al het gekras weg en ga weer naar stap 4 Persoon\Baan A
B
C
D
Jesse
24
0
9
0
Tim
5
51
0
0
Niels
4
0
9
14
Patricia
0
1
5
5
Stap 4 herhaling 1 : Bedek alle nullen met zo min mogelijk verticalen en horizontale lijnen Persoon\Baan A
B
C
D
Jesse
24
0
9
0
Tim
5
51
0
0
Niels
4
0
9
14
Patricia
0
1
5
5
Dit doe je door een paar kleineren stappen : 1 Vindt de kolom/rij met de meeste nullen en kras die kolom/rij door. 2 Zijn alle nullen bedekt? Zo nee, ga weer naar stap 1. Is het aantal doorgekraste rijen en kolommen gelijk aan de hoeveelheid banen/personen? Zo ja, ga naar stap 7. Zo nee, ga naar stap 5. Wij hebben er 4 en gelukkig is 4 gelijk aan 4. Stap 7 : Wijs de banen toe Persoon\Baan A
B
C
D
Jesse
24
0
9
0
Tim
5
51
0
0
Niels
4
0
9
14
Patricia
0
1
5
5
Dit doe je in een paar kleinere stappen. 9
Stap 7.1 : Zoek een nul die alleen staat in de rij en kolom wijs die toe en kras de rest van de kolom en rij door. Persoon\Baan A
B
C
D
Jesse
24
0
9
0
Tim
5
51
0
0
Niels
4
0
9
14
Patricia
0
1
5
5
Herhaal deze stap totdat er geen nullen alleen in de rij en kolom staan. Stap 7.2 : Zoek een nul die alleen in de rij of kolom staat (niet beide) Persoon\Baan A
B
C
D
Jesse
24
0
9
0
Tim
5
51
0
0
Niels
4
0
9
14
Patricia
0
1
5
5
We kunnen hier kiezen tussen Tim C en Niels B. We kozen niels B omdat we werken van links naar rechts want we vinden dat prettiger. Ga terug naar stap 7.1 voordat je herhaalt. Stap 7.1 herhaling 1 : Zoek een nul die alleen staat in de rij en kolom wijs die toe en kras de rest van de kolom en rij door Persoon\Baan A
B
C
D
Jesse
24
0
9
0
Tim
5
51
0
0
Niels
4
0
9
14
Patricia
0
1
5
5
Dat gaat in dit geval niet dus we gaan weer naar stap 7.2
10
Stap 7.2 herhaling 2 : Zoek een nul die alleen in de rij of kolom staat (niet beide) Persoon\Baan A
B
C
D
Jesse
24
0
9
0
Tim
5
51
0
0
Niels
4
0
9
14
Patricia
0
1
5
5
We kunnen hier uit 2 opties kiezen. We kunnen Tim C doen en Jesse D. We kiezen voor Tim C omdat we het prettiger vinden om van links naar rechts te werken. en nu gaan we weer naar 7.1 Stap 7.1 Herhaling 2 : Zoek een nul die alleen staat in de rij en kolom wijs die toe en kras de rest van de kolom en rij door Persoon\Baan A
B
C
D
Jesse
24
0
9
0
Tim
5
51
0
0
Niels
4
0
9
14
Patricia
0
1
5
5
Nu dat de matrix volledig is toe gewezen gaan we naar stap 8. Stap 8 : maak een tabel met alle personen en toegewezen banen
Persoon
Baan
Jesse
D
Tim
C
Niels
B
Patricia
A
11
Stap 9 : Vul de toegewezen banen in op de originele matrix Persoon\Baan A
B
C
D
Jesse
20
60
50
54
Tim
60
30
80
75
Niels
70
90
80
70
Patricia
65
80
75
70
Tada!!! We hebben deze matrix opgelost en er is gebleken dat het maximum aantal punten dat we kunnen halen 289 (alle groene vakken bij elkaar opgeteld) is. Kijk Tip dat kan u niet maar of u hoger kan krijgen .
12
Oplossing general assignment problem via cover Persoon\Baan A
B
C
D
Jesse
20
60
50
54
Tim
60
30
80
75
Niels
70
90
80
70
Patricia
65
80
75
70
Stap 1 : maak een cover Cover\cover 0
0
0
0
0
310
Persoon\ Baan
A
B
C
D
60
Jesse
20
60
50
54
80
Tim
60
30
80
75
90
Niels
70
90
80
70
80
Patricia
65
80
75
70
Je neemt het hoogste cijfer uit iedere rij en schrijft het ernaast op. Al wil je kan je het ook bij elkaar optellen en dan weet je in ieder geval dat je uiteindelijke uitkomst bij elkaar minder moet zijn dan dat getal (in dit geval 310). Vervolgens schrijf je in de bovenste rij allemaal nullen. Al tel je deze getallen boven aan op dan weet je dat het in ieder geval hoger dan dat getal zal worden (later zal het nog hoger worden dan nul).
13
Stap 2 : Maak er een adjacency matrix van Persoon\Baan A
B
C
D
Jesse
0
1
0
0
Tim
0
0
1
0
Niels
0
1
0
0
Patricia
0
1
0
0
Je maakt van alle gecoverde cijfers (cijfers waarbij geld Rij+Kolom=Cijfer) een 1. En alle niet gecoverde (cijfers waarbij geld Rij+Kolom=!Cijfer) cijfers een 0. Stap 3 : Probeer de matrix op te lossen Persoon\Baan A
B
C
D
Jesse
0
1
0
0
Tim
0
0
1
0
Niels
0
1
0
0
Patricia
0
1
0
0
Om de matrix op te lossen moet je de volgende stappen zetten. Opgelost? Ga naar stap 6. Niet opgelost ga naar stap 4. stap 3.1 : Kies een 1tje die alleen staat in de rij en kolom Persoon\Baan A
B
C
D
Jesse
0
1
0
0
Tim
0
0
1
0
Niels
0
1
0
0
Patricia
0
1
0
0
Herhaal deze stap totdat er geen 1tjes meer zijn die alleen in de rij en kolom staan.
14
Stap 3.2 : Kies er een die alleen in de kolom of rij staat Persoon\Baan A
B
C
D
Jesse
0
1
0
0
Tim
0
0
1
0
Niels
0
1
0
0
Patricia
0
1
0
0
Doe dit totdat je 1tjes alleen in de rij of kolom staat. (Vergeet niet iedere keer stap 3.1 te herhalen) Stap 4 : Benoem essentiële rijen en kolommen Persoon\Baan A
B
C
D
Jesse
0
1
0
0
Tim
0
0
1
0
Niels
0
1
0
0
Patricia
0
1
0
0
Een rij is essentieel al is het ook mogelijk een andere 1 te nemen. Ook is Een rij essentieel al is er een toegewezen 1 die ook een andere 1 had kunnen zijn in diezelfde rij. Al is dit niet mogelijk dan is de kolom essenteel. Stap 5 : Pas de cover aan Cover\cover 10
0
0+5=5
0+5=5
0
290
Persoon\ Baan
A
B
C
D
605=55
Jesse
20
60
50
54
805=75
Tim
60
30
80
75
905=85
Niels
70
90
80
70
805=75
Patricia
65
80
75
70
Kijk wat het kleinste verschil in de cover is en trek die van alle niet essentiële rijen af en bij de essentiële kolommen op. Ga daarna terug naar stap 2.
15
Stap 2 herhaling 1 : Maak er een simpel matrix van Persoon\Baan A
B
C
D
Jesse
0
1
0
0
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Je maakt van alle gecoverde cijfers (cijfers waarbij geld Rij+Kolom=Cijfer) een 1. En alle niet gecoverde (cijfers waarbij geld Rij+Kolom=!Cijfer) cijfers een 0. Stap 3 herhaling 1 : Probeer de matrix op te lossen Persoon\Baan A
B
C
D
Jesse
0
1
0
0
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Om de matrix op te lossen moet je de volgende stappen zetten. Opgelost? Ga naar stap 6. Niet opgelost ga naar stap 4. Stap 3.1 herhaling 1 : Kies een 1tje die alleen staat in de rij en kolom Persoon\Baan A
B
C
D
Jesse
0
1
0
0
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Herhaal deze stap todat er geen 1tjes meer zijn die alleen in de rij en kolom staan.
16
Stap 3.2 herhaling 1 : Kies 1tje die alleen in de kolom of rij staat Persoon\Baan A
B
C
D
Jesse
0
1
0
0
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Doe dit totdat je 1tjes alleen in de rij of kolom staat. (Vergeet niet iedere keer stap 3.1 te herhalen) Stap 3.1 herhaling 2 : Kies een 1tje die alleen staat in de rij en kolom Persoon\Baan A
B
C
D
Jesse
0
1
0
0
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Herhaal deze stap totdat er geen 1tjes meer zijn die alleen in de rij en kolom staan. Stap 4 herhaling 1 : Benoem essentiële rijen en kolommen Persoon\Baan A
B
C
D
Jesse
0
1
0
0
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Een rij is essentieel al is het mogelijk een andere 1 te nemen. Ook is een rij is essentieel al is er een toegewezen 1 die ook een andere 1 had kunnen zijn in diezelfde rij. Al is dit niet mogelijk dan is de kolom essentieel.
17
Stap 5 herhaling 1 : Pas de cover aan Cover\cover 11
0
5+1=6
5
0
287
Persoon\ Baan
A
B
C
D
551=54
Jesse
20
60
50
54
75
Tim
60
30
80
75
851=84
Niels
70
90
80
70
751=74
Patricia
65
80
75
70
Kijk wat het kleinste verschil in de cover is en trek die van alle niet essentiële rijen af en bij de essentiële kolommen op. Ga daarna terug naar stap 2. Stap 2 herhaling 2 : Maak er een adjacency matrix van Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Je maakt van alle gecoverde cijfers (cijfers waarbij geld Rij+Kolom=Cijfer) een 1. En alle niet gecoverde (cijfers waarbij geld Rij+Kolom=!Cijfer) cijfers een 0. Stap 3 herhaling 2 : Probeer de matrix op te lossen Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Om de matrix op te lossen moet je de volgende stappen zetten. Opgelost? Ga naar stap 6. Niet opgelost ga naar stap 4.
18
stap 3.1 herhaling 3 : Kies een 1tje die alleen staat in de rij en kolom Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Herhaal deze stap totdat er geen 1tjes meer zijn die alleen in de rij en kolom staan. stap 3.2 herhaling 2 : Kies 1tje die alleen in de kolom of rij staat Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Doe dit totdat je 1tjes alleen in de rij of kolom staat. (Vergeet niet iedere keer stap 3.1 te herhalen) stap 3.1 herhaling 4 : Kies 1tje die alleen staat in de rij en kolom Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Herhaal deze stap totdat er geen 1tjes meer zijn die alleen in de rij en kolom staan.
19
stap 3.2 herhaling 3 : Kies een 1tje die alleen in de kolom of rij staat Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Doe dit totdat je 1tjes alleen in de rij of kolom staat. (Vergeet niet iedere keer stap 3.1 te herhalen) stap 3.1 herhaling 4 : Kies 1tje die alleen staat in de rij en kolom Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Herhaal deze stap totdat er geen 1tjes meer zijn die alleen in de rij en kolom staan. stap 3.2 herhaling 4 : Kies 1tje die alleen staat in de rij en kolom Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Doe dit totdat je 1tjes alleen in de rij of kolom staat. (Vergeet niet iedere keer stap 3.1 te herhalen)
20
Stap 4 herhaling 2 : Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
0
0
Patricia
0
1
0
0
Een rij is essentieel al is het mogelijk een anderen 1 te nemen. Ook is een rij essentieel al is er een toegewezen 1 die ook een andere 1 had kunnen zijn in diezelfde rij. Al is dit niet mogelijk dan is de kolom essentieel. stap 5 herhaling 2 : Pas de cover aan Cover\cover 20
0
6+9=15
5
0
269
Persoon\ Baan
A
B
C
D
54
Jesse
20
60
50
54
75
Tim
60
30
80
75
849=75
Niels
70
90
80
70
749=65
Patricia
65
80
75
70
Kijk wat het kleinste verschil in de cover is en trek die van alle niet essentiële rijen af en bij de essentiële kolommen op. Ga daarna terug naar stap 2. Stap 2 herhaling 2 : Maak er een adjacency matrix van Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
1
0
Patricia
1
1
0
0
Je maakt van alle gecoverde cijfers (cijfers waarbij geld Rij+Kolom=Cijfer) een 1. En alle niet gecoverde (cijfers waarbij geld Rij+Kolom=!Cijfer) cijfers een 0. 21
Stap 3 herhaling 3 : Probeer de matrix op te lossen Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
1
0
Patricia
1
1
0
0
Stap 3.1 herhaling 5 : Kies een 1tje die alleen staat in de rij en kolom Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
1
0
Patricia
1
1
0
0
Herhaal deze stap totdat er geen 1tjes meer zijn die alleen in de rij en kolom staan. Stap 3.2 herhaling 5 : Kies een 1tje die alleen in de kolom of rij staat Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
1
0
Patricia
1
1
0
0
Doe dit totdat je 1tjes alleen in de rij of kolom staat. (Vergeet niet iedere keer stap 3.1 te herhalen) Stap 3.1 herhaling 6 : Kies een 1tje die alleen staat in de rij en kolom Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
1
0
Patricia
1
1
0
0
Herhaal deze stap totdat er geen 1tjes meer zijn die alleen in de rij en kolom staan. 22
Stap 3.2 herhaling 6 : Kies een 1tje die alleen in de kolom of rij staat Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
1
0
Patricia
1
1
0
0
Stap 3.1 herhaling 7 : Kies een 1tje die alleen staat in de rij en kolom Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
1
0
Patricia
1
1
0
0
Herhaal deze stap totdat er geen 1tjes meer zijn die alleen in de rij en kolom staan. Stap 3.2 herhaling 7 : Kies een 1tje die alleen staat in de rij en kolom Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
1
0
Patricia
1
1
0
0
Doe dit totdat je 1tjes alleen in de rij of kolom staat. (Vergeet niet iedere keer stap 3.1 te herhalen) Stap 3.1 herhaling 8 : Kies een 1tje die alleen staat in de rij en kolom Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
1
0
Patricia
1
1
0
0
23
Herhaal deze stap totdat er geen 1tjes meer zijn die alleen in de rij en kolom staan. Stap 3.2 herhaling 8 : Kies een 1tje die alleen in de kolom of rij staat Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
1
0
Patricia
1
1
0
0
Doe dit totdat je 1tjes alleen in de rij of kolom staat. (Vergeet niet iedere keer stap 3.1 te herhalen) Stap 3.1 herhaling 9 : Kies een 1tje die alleen staat in de rij en kolom Persoon\Baan A
B
C
D
Jesse
0
1
0
1
Tim
0
0
1
1
Niels
0
1
1
0
Patricia
1
1
0
0
Herhaal deze stap totdat er geen 1tjes meer zijn die alleen in de rij en kolom staan.
24
Stap 6 : Maak een tabel met alle personen en toegewezen banen Persoon
Baan
Jesse
D
Tim
C
Niels
B
Patricia
A
Stap 7 : Vul de toegewezen banen in op de originele matrix
Persoon\Baan A
B
C
D
Jesse
20
60
50
54
Tim
60
30
80
75
Niels
70
90
80
70
Patricia
65
80
75
70
25
Soorten wiskunde Op de middelbare school heb je te maken met verschillende soorten wiskunde. Hierbij moet je denken aan: Algebra Meetkunde Kansrekening en statistiek Natuurwetenschappen Analyse Algebra: Algebra is hetgeen waar je het meest mee te maken krijgt met een natuur en/of technisch profiel. Algebra komt van het Arabische woord ALGibr3 , dat hereniging, verbinding of vervollediging betekent. Algebra is wiskunde die zich bezighoudt met rekenen met letters en tekens. Getallen worden voorgesteld door letters en allerlei regels geven aan hoe je met de letters moet rekenen. Meetkunde: Meetkunde is ook een onderdeel van de wiskunde. De meetkunde houd zich bezig met het bepalen van afmetingen en vormen. Ook het bepalen van de positie van figuren in de ruimte en de eigenschappen daarvan, vallen onder de term meetkunde. Meetkunde is ook nog eens een van de oudste wetenschappen ter wereld. Al in de e 3 eeuw v.Chr.4 kregen mensen kennis over lengtes, volumes en oppervlakten. Kansrekening en statistiek: Kansberekening en statistiek is een onderdeel van de wiskunde dat zich bezighoud met de kans dat X gebeurt. Deze vorm van wiskunde wordt gebruikt in onderzoeken, maar je krijgt er zelf vaak ook mee te maken. Als je jezelf bijvoorbeeld afvraagt hoe groot de kans is dat jij met jouw lot een prijs wint, ben je al met kansberekening bezig. Het is dus een onderdeel van de wiskunde dat zich bezighoud met situaties waarin toeval een rol speelt. De kans wordt aangegeven met de letter P, wat probability (waarschijnlijkheid) betekent. Statistiek is een onderdeel van de wiskunde dat zich vooral bezighoud met het verzamelen, organiseren en interpreteren van gegevens of data. Beroepen zoals econoom5 , arts en politicus, maken veel gebruik van statistiek. 3
bit.ly/1eYn4eq bron bit.ly/1eYn9Pk bron 5 bit.ly/1eYnd1i bron 4
26
Natuurwetenschappen: Natuurwetenschappen komen voornamelijk aan bod in vakken zoals Natuurkunde en Scheikunde. De natuurwetenschap houd zich bezig met het zoeken naar natuurwetten die verklaringen kunnen bieden voor natuurverschijnselen. Een steen 2 valt bijvoorbeeld met 9,81 m/s naar de grond. Dankzij de natuurkundige formule F = z m*g weten we waarom dit daadwerkelijk gebeurd. Analyse: Analyse is een onderdeel van de wiskunde dat zich bezighoud met het bestuderen van functies van reële en complexe getallen. De analyse is ontwikkeld uit de rekenkunde en de meetkunde. De analyse bestudeert niet alle functies, het gaat vooral om verandering binnen functies. Dit zijn bijvoorbeeld functies met de formule, y=ax2, y=a/x, y=a/(x2) of y=a√x. kortom, functies waar een helling of kromming in zit. We behandelen op de middelbare school echter niet alle onderdelen van de wiskunde. Wiskundige gebieden die we niet uitvoerig behandelen zijn bijvoorbeeld: Foundations (grondslagen) Computational Sciences (computerwetenschappen) Foundations (grondslagen): Grondslagen van de wiskunde is een wiskundegebied dat zich bezighoud met de logische en filosofische basis van de wiskunde. Het maakt onderscheid tussen de grondslagen van wiskunde en de filosofische theorieën6 over de aard van de wiskunde. Computational Sciences (computerwetenschappen): Computational Sciences, oftewel computerwetenschappen, is een tak van de wiskunde die zich bezighoud met de toepassing van wiskunde in computersystemen. Hierdoor zijn we in staat om computermodellen te maken. Door deze modellen kunnen we voorspellingen doen over heel erg veel verschillende problemen. Enkele voorbeelden hiervan zijn de doorstroming van het verkeer of de verspreiding van een epidemie. Twee heel verschillende dingen dus, en door hier computermodellen van te maken zijn we in staat een beter overzicht van de problemen te krijgen, om deze vervolgens te proberen om op te lossen. De voorspellingen over problemen worden gedaan volgens algoritmische procedures, ook wordt er gebruikt gemaakt van bijvoorbeeld logica7.
6 7
bit.ly/1eYmT2P bron bit.ly/1eYn1zj bron
27
