Simulation 1 - Kontrollfragen

Ein Modell eines Objektes (des Originals)

• ist ein ähnliches Objekt, mit dessen Hilfe eine Aufgabe gelöst werden kann, deren Lösung am Original nicht möglich oder nicht zweckmäßig ist.
• Ähnlich müssen diejenigen Eigenschaften sein, die bezüglich der Aufgabe wesentlich sind.

• bildet die wesentlichen Objekte und Verhaltensregeln eines realen oder gedanklich konzipierten Systems ab.
• repräsentieren ein reales System durch Werte von Zustandsvariablen

wichtige:

• Stochastisch od. deterministisch
  (zufallsabhängige Ereignisse/ keine)
• Statisch od. dynamisch
  (keine/ zeitabhängige Änderung)
• Kontinuierlich/stetig od. diskret od. kombiniert
  (keine/ sprunghafte Wert-/oder Zustandsänderung)

mit Beispiel:

• geometrisch: Modell eines Bauwerks
• biologisch: Ausgestopftes Tier
• stofflich: Modell einer Fertigungsmaschine (verwendete Materialien müssen gleich der späteren Maschine sein)

Weitere: phsikalisch, strukturell, funktionell, physisch, abstrakt/mathematisch, Computermodell

• dynamische Modelle (i.d.R. durch Programme realisiert)
• mit Simulationsuhr und Zustandsänderungen in zeitlicher Reihenfolge
• Zeit- und Prozessverlauf entspricht dem Originalsystem
• Modellparameter oder Modellvariablen = Merkmale des Originals
• Prozesse werden durch Algorithmen repräsentiert

--> sind beides mathematische Modelle

Analytisches Modell:

• dynamisches Systemverhalten wird durch eine Menge an gekoppelter (Differential-) Gleichungen charakterisiert
• Beschreibung von Zusammenhängen zwischen den Zustandsvariablen, Parametern, Anfangsbedingungen und Eingangsinformationen des Systems (Prozesses) in Form analytischer (funktionaler) Ausdrücke (algebraische, Integral-, Differential- bzw. Differenzengleichungen)

Algorithmisches Modell

• Widerspiegelung des originalen Prozessverlaufs im System in Form struktur- und zeitgerechter Wertveränderung der einzelnen Zustandsvariablen mittels elementarer Operationen und Bedingungen in algorithmischer Verknüpfung

--> Modelle können nach Art der Zustandsübergänge unterschieden werden

Dynamische Modelle lassen sich unterscheiden in:

Modelle mit kontinuierlichen Zustandsübergängen ->Kontinuierliche Simulation

• Darstellung Beziehung zwischen Fluss- und Bestandsgrößen über Differentialgleichungen
• während Modellierung jederzeit Werte für Bestandsgrößen
• Anwendungsgebiet: alle Bereiche der Naturwissenschaft

Modelle mit dirskreten Zustandsübergängen ->Diskrete, ereignisorientierte Simulation

• Darstellung Beziehung zwischen Fluss- und Bestandsgrößen über Differenzengleichungen
• Während Modellierung nur an bestimmten Zeitpunkten Werte für Bestandsgrößen
• Anwendungsgebiet:Produktion, Automatisierung

• Bedienungstheorie = Mathematik der Warteschlangen
• Ein Bedienungssystem besteht immer aus ein oder mehreren Bedienungskanälen (Servern), die von den eintreffenden Forderungen (z.B. Kunden) in Anspruch genommen werden
• zufälligen Ankunfts- und Bedienungszeiten
• zufälligen Wartezeiten für die Kunden
• zufällige Stillstandszeiten der Server
• Bedienungstheorie liefert die theoretische Basis für sehr viele Problemstellungen die mit der diskreten Simulation gelöst werden
• Struktur siehe Bild
• Probleme der Bedienungstheorie durch folgende Merkmale beschrieben:
  • Kundenstrom
    • Zwischenankunftszeiten, (un)geduldige Kunden, Kundentypen
  • Bedienungsanlage
    • Systemkapazität, Serveranzahl, Serveranordnung

• Darstellung der Simulationszeit durch eine Variable:
  • -> Simulationsuhr
• Beziehung zwishcen Real- & Simulationszeit: Lauftempo der Simulationsuhr im Vergleich zur Realzeit ist abhängig von
  • Rechengeschwindigkeit,
  • von der Effektivität des Simulationsprogramms
  • anderen Faktoren
  • -> gewünschtes Verhältnis variabel einstellbar
  • Zeitraffung: simulierte schneller als reale Zeit (Sonst: Zeitlupe)

• Taktsimulation: Einteilung der Zeit in Abschnitte
• wächst die Simulationszeit bei jedem Sprung um denselben Wert
  • Es werden äquidistante Zeitpunkte betrachtet
  • Nur zu diesen Zeitpunkten wird berechnet, welche Veränderungen von Modelldaten eintreten
• Konstruktionsmethode für Simulationsprogramme:
  • simulierte Zeit wird in Takte gleicher Länge zerlegt
  • Werteberechnung der Modellvariablen zu jedem Taktzeitpunkt
• Anwendung: Finanzbereich (Zins und Zinseszins), Haltestelle

Ereignissimulation Simulation: Zeit wird von einer Zustandsänderung zur nächsten fortbewegt

• die Simulationszeit wird bei jedem Sprung auf den Zeitpunkt des nächstfolgenden Ereignisses eingestellt
• Ereignis = die sprunghafte Änderung des Wertes wenigstens einer Modellvariablen verstanden (Prozesszustandsänderung)
• Ereignis und Zustandsänderung = Synonyme
• Zerlegt nachzubildenden Prozess in eine Folge zeitlich aufeinanderfolgender Ereignisse
  • Ereignisse werden nach wachsenden Ereigniszeitpunkten in eine Ereignisliste einsortiert
• Anwendung: Bankfiliale

-> gegenüber Taktsimulation Trennung besonders bei der Zeit!

• wenn es im Original eine dominierende, prozessbestimmende Taktung gibt
• wenn nichtlineare stetige (kontinuierliche) Prozesse durch einfache Näherungsverfahren zu lösen sind
• Taktzeit wird oft als Zeiteinheit der Systemuhr genutzt
• Bsp. Haltestelle: in gleichen Zeitabständen kommen Straßenbahnen an

• Zustandsänderungen des Modells werden über Ereignisse abgebildet
• Beginn der Simulation: nur Startereignis in der Queue (Initialisierung)
• bei jedem Ereignis, das eintritt, ergeben sich Ereignisse, die in zeitlicher Reihenfolge eingeplant werden (Timing Routinge [Loop])
• Simulationszeit schreitet bis zum nächsten Ereignis fort
• wenn Queue leer, dann Simulation beendet (oder Abbruchbedingung)

• Beschreibung des Flusses einer temporären Entität durch das Modell
• Prozess: Folge von Operationen, die ein Element während seiner Lebensdauer durchläuft
• Sequenz von Ereignissen einschließlich der Verzögerungen zwischen den Ereignissen (wird über Prozessroutinen beschrieben)
• Aktive Entitäten und Ereigniseintrag (bidirektional Verknüpft)
• Logische Bestandteile eines Prozesses (Prozessroutine + Local Event Pointer - verwaltet das aktuell auszuführende Ereignis + lokale Variable)
• Prozesszustände(aktiv - Ereigniseintrag ist in der Ereignisliste oder passiv - kein zugeordnetes Ereignis in der Ereignisliste)
• Zustandsübergänge (activate, Passivate, Suspend)

• Am Beispiel von SLX
  • Modell bestehen aus einer dynamischen Menge an interagierenden aktiven und passiven Objekten
  • Objektklassen und Instanzen in Analogie zur OOP
  • Objekte besitzen Zustand in Form lokaler Daten (Zustandsattribute)
  • aktive Objekte besitzen ein eigenes Verhalten (als Folge von Ereignissen)
    • Verhalten wird über Logiken repräsentiert, die von Nutzern geschrieben werden
  • passive Objekte werden  von aktiven Objekten benutzt bzw. verwendet und haben keine ausführbare Verhaltenslogik
  • Unterscheidung von aktiven und passiven Objekten hängen von der Komplexität des Problems ab

Koroutinen (auch Coroutinen)

• Koroutinen unterbrechen ihren Ablauf und nehmen ihn später wieder auf unter Beibehaltung ihres Status
• vergleichbar mit Threads
  • die wechselseitig ablaufen und nach Abgabe der Kontrolle abwarten, bis sie die Kontrolle zurück erhalten

• Scheduled Delays – geplante zeitliche Verzögerungen
  • Bsp.: Bedienzeit am Bankschalter , Wegezeit
  • SLX-Befehl: „advance x_Zeiteinheiten;“ (auch: wait until time >= absolute_time;)
• State-based Delays (auch: conditional delays) – Verzögerung aufgrund einer logischen Bedingung
  • Bsp.: Warten, bis die Ampel grün wird
  • SLX-Befehl: „wait until logischer_Ausdruck“
  • Kombination logischer und zeitlicher Bedingungen möglich (!)

• Inter-Object-Parallelism:
  • Viele Instanzen von aktiven Objekten können zur gleichen Zeit aktiv sein
  • Aktive Objekte konkurrieren typischerweise um Nutzung passiver Obj.
  • Aktive Obj. können sowohl geplante als auch bedingte Verzögerungen erfahren
• Intra-Object-Parallelism:
  • Mehrere gleichzeitige Aktivitäten können innerhalb eines Objektes abgebildet werden
  • fork-Statement, um mehrere Kontrollflüsse zu erzeugen
  • Bsp.: Maschine, die gleichzeitig ein Teil laden, ein anderes Teil bearbeiten und ein drittes Teil entladen kann – ohne Intra-Objekt-Parallelism müsste dies über 3 separate Objekte modelliert werden

• diskrete Zufallsvariable:
  • Anzahl möglicher Werte ist abzählbar
  • Die Wahrscheinlichkeiten der Werte diskreter Zufallsvariablen sind äquivalent beschreibbar mit
    • Kumulativen Verteilungsfunktionen
    • Wahrscheinlichkeitsmassefunktionen
• kontinuierliche (stetige) Zufallsvariable:
  • Anzahl ihrer möglichen Werte ist nicht abzählbar, unendlich
  • Die Wahrscheinlichkeiten der Werte kontinuierliche Zufallsvariablen werden beschrieben mit
    • Kumulativen Verteilungsfunktionen
    • Wahrscheinlichkeitsdichtefunktionen

• Erwartungswert E(X) einer Zufallsvariable X ist jener Wert, der sich bei oftmaligem Wiederholen des zugrundeliegenden Experiments als Mittelwert der Ergebnisse ergibt
• Die Varianz var (X) ist ein Streuungsmaß, d.h. ein Maß für die Abweichung einer Zufallsvariable X von ihrem Erwartungswert

• beschreibung der Wahrscheinlichkeit der Ergebnisse eines Zufallsexperiments
• Darstellung wird auch als kumulative Verteilungsfunktion bezeichnet

• Simulator nutzt einen deterministischen (!) Algorithmus zur Erzeugung der Zufallszahlen, daher generiert er Pseudozufallszahlen
  • Das ist so beabsichtigt (Wiederholbarkeit der Simulation)
  • Zufallszahlengeneratoren können jedoch typischerweise mit einem zufälligen Startwert initialisiert werden
• Erzeugung von Zufallsvariablen mit beliebigen Verteilungen
  • Gegeben:
    • Ein Zufallszahlengenerator, der gleichverteilte Zufallszahlen im Intervall (0,1) erzeugt: U (0,1)
    • Eine kumulative Verteilungsfunktion F(X), die die gewünschte Verteilung beschreibt
  • Vorgehen: Siehe Bild
    • Generiere eine Zufallszahl y ~ U(0,1)
    • Berechne x = F^-1(y)

1. Daten sammeln (messen o. schätzen) - wichtig für belastbare Resultate der Simulation

2. Schätzen des Typs der Verteilungsfunktion der Daten

2.1 Zeichnen eines Histogramms der Daten

2.2 Generierung eines Quantile-Quantile-Plots

3. Bestimmung der spezifischen Parameter der Verteilungsfunktion

4. Überprüfung der erreichten Qualität der Verteilungsfunktion

Beobachtungsdaten (Zähldaten)

• Sequenz von ungewichteten Beobachtungen

Zeitgewichtete Daten

• Sequenz von Beobachtungen, deren Werte sich über eine bestimmte Simulationszeitspanne nicht verändern
• Zeitspanne mit konstantem Wert = Wichtungsfaktor 

Eingangsdaten (zufällig) --> resultierenden Daten (auch zufällig)

Durchführung einer Simulation = 1 Zufallsexperiment

potentielle Lösungsansätze:

• mehrere Replikationen desselben Simulationsmodells durchführen
  • Unterschiedliche Startwerte für Zufallszahlengenerator
  • Bestimmung von Mittelwert, Varianz und Konfidenzintervallen für gesuchte Größen 
• Einen sehr langen Lauf durchführen und in Abschnitte unterteilen (Werte meist autokorreliert - nicht unabhängig voneinander)
  • Statistik nach jedem Abschnitt zurücksetzen und neu starten
  • Nach Simulationsende: Mittelwerte und Konfidenzintervall über Ergebnisse der einzelnen Abschnitte bestimmen

(mehrere) Simulationsdurchläufe mit demselben Modell und identischen Parametern

Terminierende Simulationen

• Simulation läuft für eine bestimmte Zeit TE, wobei E ein spezifisches Endeereignis ist
• Simuliertes System startet zum Zeitpunkt 0 unter definierten (und wichtigen) Initialbedingungen und endet zum Zeit TE
• Bsp.: Bank mit Öffnungszeiten von 8-16 Uhr

Nicht-terminierende Simulationen

• Simulation welche System abbildet, das ständig weiterläuft (oder zumindest über sehr lange Zeit)
• Simulation startet zum Zeitpunkt 0 unter definierten Initialbedingungen und endet zu einem vom Simulationsexperten spezifizierten Endezeitpunkt TE
• Zielstellung ist das Studieren des „steady-state“-Verhaltens, d.h. des Verhaltens des stationären bzw. eingeschwungenen Systems
• Ergebnisse sollen nicht durch Initialisierungsbedingungen beeinflusst werden.
• Bsp.: Produktion im Schichtbetrieb, wo die Maschinen dauerhaft laufen

Ergebnisanalyse – Terminating-Simulations

• Simuliert wird über das Zeitintervall von [0, TE]
• Beobachtungswerte Y1, Y2, … , Yn werden gespeichert
• Anzahl der Beobachtungswerte n ist fest (Verweilzeit von 100 Kunden)
• Ziel der Simulation: Schätzung des Mittelwertes (Punktschätzung)
• Die berechneten Daten der einzelnen Replikationen sind
  • Unabhängig (basieren auf unterschiedlichen Zufallszahlenströmen)
  • Identisch verteilt (das identische Modell wird in jedem Lauf verwendet)
  • Tendieren auf eine Normalverteilung (da sie auf vielen Werten eines Laufes basieren)

Ergebnisanalyse – Steady-State-Simulations

• Beobachtungen aus einem einzelnen Lauf Y1 ,Y2 , ..., Yn
• θ ist der long-run Mittelwert für die Durchlaufzeit
• Mittelwert ist als „lim“ definiert d. h. er ist unabhängig von den Initialisierungsbedingungen zum Zeitpunkt 0
• Systematischer Fehler (Bias)
  • Initialisierungsbedingungen beeinflussen den Fehler bei der Punktschätzung in Steady-State-Simulationen
  • Bei der Simulation von komplexen Systemen ist nicht von einem „empty and idle“ Zustand auszugehen
  • Umsetzung durch zwei unterschiedliche Herangehensweisen:
    • Verwendung von Initialisierungsbedingungen, die einen entsprechenden Zustand des Systems aufzeigen
    • Start mit „empty and idle” und das Nichtberücksichtigen (Wegwerfen) von Daten aus der Einschwingphase
• Replikationsmethode: (besser: T0 erhöhen)
  • Beachte: größere Anzahl Läufen verkleinert Varianz des Schätzers, aber das resultierende Konfidenzintervall kann falsch sein
  • Ursache: Einfluss des Bias nicht durch Anzahl der Läufe R bedingt, sondern nur durch Streichung von Daten aus der transienten Phase
  • ->  D.h. Erhöhung der Anzahl der Läufe führt dann zwar zu einer Reduzierung des Konfidenzintervalls, jedoch um einen falschen Punkt θ + b und nicht um den Punkt θ

Vorbereitung, Durchführung und Auswertung

Vorbereitung

• Entscheidung: Simulationswürdig?
• Aufgabe und Ziel formulieren
• Aufwand abschätzen (System- & Datenanlyse)
• Daten: ermitteln, aufbereiten, abstimmen (aus den Maschinen)
• Analytische Grobabschätzung
• Simulationsmodell erstellen und verifizieren

Durchführung

• Simulationsexperimente planen
• Simulationsexperimente durchführen
• Simulationsexperimente validieren

Auswertung

• Ergebnisaufbereitung
• Ergebnisinterpretation
• Dokumentation

Vorgehensweise:

1. Entscheidung über die Vorzugsvariante
2. Berechnung der Punktschätzung für die Differenz θ₁ - θ₂
3. Berechnung des Konfidenzintervalls für diese Differenz 
4. Beantwortung der folgenden Fragen:
   1. Wie groß ist der Mittelwert für diese Differenz & wie genau ist die Schätzung für diesen Mittelwert? (Punktschätzung & Konfidenzintervall) 
   2. Gibt es einen signifikanten Unterschied zwischen den beiden Systemen? (Mögliche „Lagen“ des Konfidenzintervalls) 

Vorteile:

• Modellerstellung zügig möglich (schnelle 80% Lösung) per Drag & Drop [SLX: alles Programmieren]
• schnell eine einfache grafische Darstellung möglich
• vordefinierte Elemente, die im Programm verwendet werden können [SLX: extra Programm (Proof Animation)]
• Auftragsgetriebene Sicht: bewegliche Elemente konkurrieren typischerweise um die Nutzung von Ressourcen (Bedieneinrichtung, Maschine, Kellner, …) -> Teil ist aktiv

[SLX: ressourcengetriebene Sicht: Ressourcen arbeiten Aufträge ab à sind aktive Elemente]

Nachteile:

• kann nicht bestimmt werden, welches Element aktiv/passiv ist
• wenig Flexibilität
• Simulations- und Statistikkenntnisse notwendig, und ggf. auch Programmierkenntnisse, wenn vordefinierte Bausteine nicht die benötigte Funktionalität haben

• Verifikation:
  • „formaler Nachweis der Korrektheit des Simulationsmodells“
  • Vergleich des konzeptionellen Modells mit seiner Implementierung
    • Überprüfung der korrekten Überführung des konzeptionellen Modells in das Simulationsprogramm
    • Ist das Modell richtig?
    • Untersuchung, ob es so arbeitet, wie es im Modell beabsichtigt war.
• Validierung:
  • „Überprüfung der hinreichenden Übereinstimmung von Modell und Originalsystem“
  • Sicherstellung dass das Modell das Verhalten des realen Systems genau und fehlerfrei widerspiegelt
  • Ist es das richtige Modell für die Aufgabenstellung?

• Nutzung historischer Eingabedaten:
  • Vorgehensweise
    • Das Modell wird mit historischen Eingabedaten gespeist (d.h. wirklich aufgetretene Ankunftszeiten, keine angenäherten Verteilungsfunktionen)
  • Voraussetzung
    • Vollständig historischer Datensatz muss verfügbar sein, auch bzgl. real gemessener Ausgabeparameter
    • Simulator muss in der Lage sein, Rohdaten zu verarbeiten

• Festwerttest:
  • Ausschließliche Verwendung von konstanten Werten im Modell
  • Bsp. manuelle Montagelinie:
    • Werden die Verteilungszeiten für Bearbeitungszeiten durch feste Werte ersetzt, so bestimmt die Station mit der höchsten Bearbeitungszeit den Durchsatz der Linie
    • Durchsatz der Linie kann so leicht ohne Simulation berechnet werden
  • Sinnvolles Vorgehen: Definition von Hypothesen, wie sich das deterministische Modell verhalten wird
  • Ggf. in Kombination mit anderen Verfahren, z.B. Vergleich mit anderen Modellen (Tabellenkalkulation als Vergleichsmodell)
• Grenzwerttest:
  • Test des Modells mit Kombinationen aus Extremwerten für Eingabedaten und Parameter
  • Ziel: Bessere Vorhersagbarkeit, wie sich Modell verhalten sollte
    • Bsp.: Alle Losgrößen auf kleinsten Wert – lässt Verhältnis Rüstzeiten zu Bearbeitungszeiten an Maschinen besser abschätzen
    • Bsp.: Nur ein einziger Auftrag wird eingelastet
    • Bsp.: Wahrscheinlichkeit für Nacharbeit auf Null setzen
  • Verwandtschaft mit Festwerttest

• Sensitivitätsanalyse misst
  • die Abhängigkeit von Ergebnisgrößen von Eingabeparametern
  • Geg.:
    • Ausgabegröße O
    • Eingabeparameter I
  • Sensitivität S = dO / dI
  • Beispiel: Einfache Warteschlange mit fester Ankunftsrate
  • I: Bedienrate
  • O: Durchschnittliche Warteschlangenlänge
• Anwendung z.B. durch Befragung des Managements, ob sich bei Veränderungen von Eingabedaten das Modell so verhält, wie es im realen System erwartet wird
  • Erhöhung der Ankunftsrate auf die Auslastung von Servern
  • Management besitzt Vorstellungen über die Richtung der Veränderungen von Systemparametern
• Sensitivitätstest bei large-scale Models
  • Viele mögliche Eingabeparameter und somit viele Möglichkeiten
• Versuche die kritischen Parameter zu identifizieren
• Beispiel:
  • Befragung von Experten