Besliskunde College 3: Simulatie en Monte Carlo Methoden

Introductie tot Simulatie

• Definitie van Simulatie: Simulatie is het nabootsen van werkelijke processen met behulp van een computer. Dit gebeurt vaak door middel van statistische kansberekeningen (stochastiek).

• Toepassingsgebied: Het wordt vooral ingezet bij grote en complexe systemen waar directe experimenten in de werkelijkheid te duur, gevaarlijk of tijdrovend zouden zijn.

• Status als Tool: Simulatie is een van de meest gebruikte kwantitatieve instrumenten voor systeemanalyse.

• Software: Het is relatief eenvoudig te implementeren met moderne softwarepakketten zoals Excel, ARENA en PowerSim.

• Voordeel t.o.v. Analytische Modellen: Simulatie is vaak veel makkelijker uit te voeren dan een puur wiskundige (analytische) analyse van een complex systeem.

Voorbeelden en Vergelijkingen

• Wiskundig Raadsel (Oppervlakte): In het college wordt de vraag gesteld welke optie de meeste pizza oplevert:

  • Optie 1: Eén pizza met een diameter van $2\,\text{cm}$ en één pizza met een diameter van $18\,\text{cm}$.

  • Optie 2: Twee pizza's met een diameter van $12\,\text{cm}$.

  • Context: Dit illustreert hoe kwantitatieve keuzes soms contra-intuïtief kunnen zijn.

• Praktijkvoorbeelden:

  • Verkeerssimulatie (Traffic Simulation): Het tellen van voertuigen per cyclus om verkeersstromen te optimaliseren.

  • Windtunnels: Het testen van aerodynamica zonder een fysiek voertuig op de weg te hoeven testen.

  • Bedrijfsprocessen: Het simuleren van lopende banden (conveyors) en logistieke systemen.

Voor- en Nadelen van Simulatie

• Voordelen:

  • Biedt een veilige omgeving om oplossingen te testen zonder werkelijke implementatie.

  • Geschikt voor gevoeligheidsanalyse (het effect van veranderende variabelen).

  • Kan zeer grote en complexe systemen aan waarvoor geen simpele formules bestaan.

  • Flexibel; er zijn minder strikte wiskundige aannames nodig.

  • Maakt uitgebreide "What-if"-analyses mogelijk.

• Nadelen:

  • Het bouwen van een accuraat model voor een complex systeem kan moeilijk en kostbaar zijn.

  • Simulatie levert geen "optimale" oplossing (zoals lineair programmeren), maar is een proces van trial-and-error.

  • Elke simulatie is uniek; de resultaten van het ene probleem zijn niet zomaar overdraagbaar naar een ander probleem.

De "Flaw of Averages"

• Concept: Het is een veelgemaakte fout om de verwachte uitkomst te berekenen door simpelweg gemiddelden in een formule in te vullen.

• Voorbeeld Beslisprobleem:

  • Verwachte vraag = $30$.

  • Voorraad = $25$.

  • Prijs = $10\,\text{euro}$.

  • Formule Totale opbrengst = $\min(\text{voorraad}; \text{vraag}) \times \text{prijs}$.

  • Foutieve berekening: $\min(25; 30) \times 10 = 250\,\text{euro}$.

  • Correcte berekening via kansverdeling:

    • Kansen: $0.1$ bij vraag $10$, $0.2$ bij vraag $20$, $0.3$ bij vraag $30$, $0.4$ bij vraag $40$.

    • Opbrengsten: $100$, $200$, $250$, $250$.

    • Verwachte Monetaire Waarde (EMV): $(0.1 \times 100) + (0.2 \times 200) + (0.3 \times 250) + (0.4 \times 250) = 10 + 40 + 75 + 100 = 225\,\text{euro}$.

• Conclusie: De prijs vermenigvuldigd met de gemiddelde vraag is niet gelijk aan de verwachte opbrengst ($225 \neq 250$). Gemiddelden verhullen de impact van variabiliteit.

Het Simulatieproces in 7 Stappen

1. Definieer het probleem: Wat willen we onderzoeken?

2. Introduceer variabelen: Maak onderscheid tussen beïnvloedbare variabelen (beslissingen) en niet-beïnvloedbare variabelen (onzekerheden).

3. Construeer het simulatiemodel: Bepaal de logische samenhang.

4. Specificeer input variabelen: Welke waarden en kansverdelingen gebruiken we?

5. Voer de simulatie uit: Gebruik methoden zoals Monte Carlo.

6. Analyseer resultaten: Bekijk de gemiddelden en de spreiding (risico).

7. Selecteer de beste beslissing: Kies op basis van de analyse de optimale strategie.

Monte Carlo Simulatie

• Kern: Een stochastische variabele wordt gesimuleerd door een willekeurige trekking uit een kansverdeling.

• Toepassingen:

  • Aantal studenten in een collegezaal.

  • Servicetijd van monteurs.

  • Tussenkomsttijd tussen twee klantbezoeken.

  • Aantal zieke of afwezige werknemers.

• Willekeurige Getallen: Willekeurig betekent dat er geen voorspelbaar patroon is.

• Pseudo-willekeurige getallen: Volgens John von Neumann (1951) is het gebruik van rekenkundige methoden voor willekeur "zondig". Pseudo-random getallen worden gegenereerd via formules. Ze zijn herhaalbaar (periodiek), wat handig is voor "What-if"-analyses omdat je dezelfde scenario's met verschillende beslissingen kunt testen.

Monte Carlo Simulatie: Het 4-stappenplan

1. Bepaal de kansverdeling: Identificeer hoe vaak elke uitkomst voorkomt.

2. Bouw de cumulatieve kansverdeling: Tel de individuele kansen bij elkaar op.

3. Kies intervallen: Koppel specifieke reeksen willekeurige getallen aan de uitkomsten.

4. Genereer getallen: Voer de simulatie uit aan de hand van de gekozen intervallen.

Oefenopgave: Nederlandse Spoorwegen (NS)

• Casus: Bepaal het verwachte aantal reizigers zonder zitplaats op een traject waar een trein met $130$ zitplaatsen rijdt.

• Gegevens:

  • Reizigers $50$ (Kans $0.1$), $100$ (Kans $0.4$), $150$ (Kans $0.2$), $200$ (Kans $0.3$).

  • Trekkingen: $66$, $37$, $12$, $05$, $88$.

• Intervallen (01-00):

  • $50$ reizigers: $01-10$

  • $100$ reizigers: $11-50$

  • $150$ reizigers: $51-70$

  • $200$ reizigers: $71-00$

• Resultaten:

  • $66 \rightarrow 150$ reizigers (tekort $20$)

  • $37 \rightarrow 100$ reizigers (tekort $0$)

  • $12 \rightarrow 100$ reizigers (tekort $0$)

  • $05 \rightarrow 50$ reizigers (tekort $0$)

  • $88 \rightarrow 200$ reizigers (tekort $70$)

• Gemiddelden over 5 simulaties:

  • Verwacht aantal reizigers: $\frac{150+100+100+50+200}{5} = 120$

  • Verwacht tekort: $\frac{20+0+0+0+70}{5} = 18$

Casus: Voorraadanalyse

• Variabelen:

  • Onzeker (niet-beïnvloedbaar): Vraag per dag, Lead time (levertijd).

  • Beslissingen (beïnvloedbaar): Bestelgrootte ($Q$), Bestelmoment ($R$).

• Doelstelling: Minimaliseren van de totale kosten (bestelkosten + voorraadkosten + nee-verkoopkosten).

• Modeldetails:

  • Kosten eindvoorraad: $0.03\,\text{euro}$ per eenheid per dag.

  • Boete nee-verkoop: $8\,\text{euro}$ per eenheid.

  • Leveringskosten: $10\,\text{euro}$ per order.

• Input kansverdelingen (Vraag):

  • $0$ (kans $0.05$), $1$ ($0.1$), $2$ ($0.2$), $3$ ($0.4$), $4$ ($0.15$), $5$ ($0.1$).

• Input kansverdelingen (Lead time):

  • $1$ dag (kans $0.2$), $2$ dagen ($0.5$), $3$ dagen ($0.3$).

• Analyse van 10 Dagen Simulatie:

  • Gemiddelde eindvoorraad: $4.1$ per dag.

  • Gemiddelde nee-verkoop: $0.2$ per dag.

  • Gemiddeld aantal orders: $0.3$ per dag.

  • Totale gemiddelde kosten per dag: $(4.1 \times 0.03) + (0.2 \times 8) + (0.3 \times 10) = 4.72\,\text{euro}$.

Verificatie versus Validatie

• Verificatie: Gaat over de technische correctheid van het model. Is het model correct geïmplementeerd volgens de specificaties? "Did we build the model right?"

• Validatie: Gaat over de aansluiting bij de werkelijkheid. Komt de output van het model overeen met wat we in de echte wereld zien? "Did we build the right model?"

• Methode: Vergelijk de resultaten van het model met historische data waarbij de inputs hetzelfde waren.

Opmerkingen over computer-simulaties

• Een simulatie van 10 dagen is veel te kort voor een betrouwbaar beeld.

• In Excel kunnen met functies als =RAND() (of =ASELECT()) eenvoudig duizenden dagen worden gesimuleerd om een stabiel gemiddelde en een risicoprofiel te krijgen.

• Verschillende bestelgrootten en bestelmomenten kunnen worden getest om de kosten te optimaliseren via een trial-and-error methode.