Please enable JavaScript.
Coggle requires JavaScript to display documents.
Modellbildung und Simulation - Coggle Diagram
Modellbildung und Simulation
KE1
Einleitung (1.)
Einführung
Simulationspipeline
Berechnung/ Simulation
Implementierung
Validierung
Modellierung
Einbettung
Einführung in die Modellierung
Allgemeines
Prosa -> Modell der Anwendungswissenschaft => Mathematisches Modell
Herleitung von Modellen
Was genau soll modelliert & simuliert werden?
Welche Größen qualitativ & qualitativ
Instrumentarium
algebraische Gleichungen
algebraische Strukturen
Sprachkonzepte (UML)
Systeme gewöhnlicher Differentialgleichungen
Systeme paralleler Differentialgleichungen
regelbasierte Systeme
Wahrscheinlichkeitsverteilung
Automaten & Zustandsübergangsdiagramme
Graphen
Neuronale Netze
Fragen (Notes)
Skalen (Notes)
Klassifikation von Modellen
diskrete Modelle
stochastische Modelle
vs
diskrete bzw. kombinatorische Beschreibung
je nach Aufgabenstellung können Systeme diskret &/oder kontinuierlich modelliert werden.
kontinuierliche Modelle
deterministische Modelle
reelwertige bzw. kontinuierliche Beschreibungen (reelle Zahlen, physikalische Größen, algebraische Gleichungen)
Einführung zur Simulation
Allgemeine Bemerkungen (Notes)
verschiedene Ansätze
analytische Lösung
heuristische Lösung
direkt-numerischer Ansatz
approximativ numerischer Ansatz
Bewertung
Validierung
Verifikation (Notes)
Vorgehensweisen
Abgleich mit experimentellen Untersuchungen
A-posteriori Beobachtungen
Realitätstests
Zufriedenheitstests
Plausibilitätstests
Modellvergleich
Kostenfrage
Genauigkeit
immer abwägen
Spieletheorie (2.)
Beispiele
Kampf der Geschlechter
Gefängnisdilemma
Ausblick
Was bringt uns die modellierung?
wie zuverlässig sind die erzielten Ergebnisse
Spiele in strategischer Normalform
Definition strategische Normalform (N)
Spieler (N)
Strategien (N)
Auszahlungsfunktion
Nutzenmatrix/ Auszahlungsmatrix
Beispiel:
Spiele ohne Annahmen über den Gegner
Spiel bei Gewissheit (N)
Spiel bei Risiko (N)
Mentalität des Spielers ist hier sehr entscheidend
Reaktionsabbildung
Was müssen wir tun, wenn Gegner y wählt?
Dominante Strategien (N)
Spieler kennen nicht die Strategie des anderen, aber die Auszahlungsfunktion
Gemischte Strategien (N)
Nash-Gleichgewicht (N)
Gleichgewichtspunkt heißt in dem Fall auch Sattelpunkt
Zeitpläne (3.)
Ziel: Modellierung von Aufgaben (N)
Prozess-Scheduling (deterministisch)
Prozess-Scheduling (stochastisch)
Beispiele:
Wichtigste 3 Beispiele für Verteilung
Fall fester Bearbeitungszeit (Abb. 5.4 links)
Bearbeitung des Auftrags endlich viele Fälle & deren Wahrscheinlichkeit bekannt (Abb. 5.4 mitte)
Bearbeitungszeit ist kontinuierliche Zufallsvariable (Abb. 5.4 rechts)
Zwei Konfigurationen
strikt serielle Bearbeitung:
strikt parallele Bearbeitung:
Job Shop Problem
Hier wird gelöst, welche mögliche Kombination unter bestimmten Ressourcen (100 Teile, 3 Maschinen, usw.) am besten das Problem löst.
KE2
Makroskopische Simulation von Straßenverkehr (1.)
Modellansatz
Störungen im Verkehrsfluss breiten sich Wellenartig aus
Verkehrsmodell
Verkehrs- oder Strömungsgeschwindigkeit v(x, t)
Fahrzeugdichte p(x, t)
Verkehrsfluss f(x, t)
Modellannahmen
\( 0 \leq \rho(x,t) \leq \rho_{max} \) (N)
\( 0 \leq v(x,t) \leq v_{max} \) (N)
Homogene Verkehrsströmung (N)
Ein erstes Ergebnis
Zustand hängt nur von Dichte ab (N)
Zustandgleichung \( \bar{f} = \bar{ \rho} \bar{v} \) (N)
Geschwindigkeit, Fluss und Dichte
Modellierung der Geschwindigkeit in Abhängigkeit der Dichte
3 Bedingungen
1) Freie Fahrbahn? Alle Fahrer \( v_{max} \)
\( \rho \rightarrow 0 => v \rightarrow v_{max} \)
2) Volle Fahrbahn? Stau. \( \rho \rightarrow \rho_{max} => v \rightarrow 0 \)
3) Steigt Dichte an? v wird nicht erhöht. \( v(\rho) := v_{max} (1 - \frac{\rho}{\rho_{max}}) \)
Modellierung des Flusses
\( f(\rho) = \gamma(\rho) \rho \)
\( f \rightarrow 0 \) für, \( \rho \rightarrow 0 \) & \( \rho \rightarrow \rho_{max} \) (N)
Fundamentaldiagramm (N)
(N)
Modellverfeinerung
Verfeinerung durch hinzufügen von Freiheitsgraden
\( v(\rho) := v_{max} (1- \alpha \rho + \beta \rho^2 ) \)
Bedingung erfüllt, 2 Bedingung \( v(\rho_{max}) = 0 => 0 = v_{max}(1- \alpha \rho_{max} + \beta \rho^2_{max}) \)
\( f(\rho) := v_{max} (1- \alpha \rho + \beta \rho^2)\rho \)
\( \frac{d}{d \rho} f(\rho_{opt}) = 0 \)
\( 0 = v_{max} (1-2 \alpha \rho_{opt} + 3 \beta \rho^2_{opt}) \)
Alternativ
\( f_{max} = v_{max}(1- \alpha \rho_{opt} + \beta \rho^2_{opt}) \rho_{opt} \)
Autofahrer über reagieren beim Bremsen & fahren egoistisch
\( v(\rho) := v_{max}(1-(\frac{\rho}{\rho_{max}})^{\alpha})^{\beta} \)
Empirisch gewonnene Daten werden mittels Methode der kleinsten Quadranten für die Bestimmung der Parameter verwendet.
Inhomogene Verkehrsströmung
Kontinuitätsgleichung (N)
Visualisierung der Berechnungen:
Simulation einer einfachen Ringstraße (N)
Partielle Differentialgleichung diskretisieren
Anfangs- & Randbedingungen festlegen
Berechnen von Dichte und dadurch Fluss & Geschwindigkeit (numerisch)
Ein erster Versuch
Begriffe & Formeln
Reelwertige Position \( x \epsilon [a, b] \) (N)
Diskrete Punkte \( n+1, x_i = ih, i = 0, ..., n \)
Maschenweite \( h = (b-a)/n \)
Partielle Ableitung diskretisieren
Finiten Differenzen
\( \frac{d}{dt} \rho (x,t) = \frac{\rho (x,t + \delta t) - \rho (x,t)}{\delta t} \)
\( \frac{d}{dt} f(x,t) = \frac{f(x,t + \delta t) - f(x,t)}{\delta t} \)
...
Berechnung der Dichte am Ort \( x_{ij} \) zum Zeitpunkt \( t_{i+1} \)
\( \rho_{i,j+1} = \rho_{i,j} - \frac{\sigma t}{h} v_{max} ((1- \frac{\rho_{i+1,j}{\rho_{max}}) \rho_{i+1,j} - (1- \frac{\rho{i,j}}{\rho_{max}}) \rho_{i,j}) \)
Eine verbesserte Simulation
Verfahren von MacCormack
Verfahren ist stabil, solange \( \frac{\delta t}{h} \) hinreichend klein ist.
\( \rho_{i,j} = \rho_{i,j} - \frac{\delta}{2}(\frac{f_{i,j} - f_{i-1, j}}{h} + \frac{~{f_{i+1,j+1}} - ~{f_{i,j+1}}}{h}) \)
Signal- & Verkehrsgeschwindigkeit
Weshalb bildet sich in unserem Modell ein Dichtesprung? Warum verschiebt sich nicht nur die Flanke?
Antwort: Signalgeschwindigkeit \( f_\rho (\rho_{opt}) = 0 \). Bereich vor Stauende \( f_\rho > 0 \) und Bereich danach \( f_\rho < 0 \)
Signalgeschwindigkeit
\( f_\rho (\rho) := \frac{d}{d \rho} f(\rho) [Fzg/ h]/ [Fzg/km] = [km/h] \)
Beschreibt Auswirkung von Dichteänderung auf den Fluss.
Wenn Straße fast leer
\( \rho (x,t) \rightarrow 0, v(\rho) \rightarrow v_{max}, f(\rho) \rightarrow 0, f_\rho (\rho) \rightarrow v_{max} \)
Bei abrupten Bremsen
Merkt niemand das Bremsen
Wenn Straße etwas voller
\( \rho \rightarrow \rho_{max}, v \rightarrow 0, f \rightarrow 0, f_\rho \rightarrow -v_{max} \)
Bei abruptem Bremsen
Spüren andere Teilnehmer das, jedoch am Stellen weiter hinten.
Wellenförmige Ausbreitung
Zusammenfassung & Ausblick (N)
Mikroskopische Simulation von Straßenverkehr (2.)
Ziel: Straßennetz präzise auflösen & schneller an Ergebnisse kommen (Bevor Ergebnisse veraltet sind, weil Rechnung zu lange dauert).
Modellansatz
Straßenverkehr
Einspurige Fahrbahn (N)
Algorithmus 8.1 (Die Regelns des ZA-Modells)
Update für Fahrzeuge:
Beschleunigen: v_i := min { v
i +1, v
{max} }
Bremsen: \( v_i := d(i,i+1) \) falls \(v_i > d(i,i+1) \)
Bewegen: Fahrzeug i bewegt sich \( v_i \) Zellen vorwärts.
zentrale Modellannahmen
Erhaltung der Fahrzeuge
Kollisionsfreiheit (N)
Daten
Bsp: Ziel: 50 km/h in 10 km/h Schritten diskretisieren.
\( 5*7,5m/ \delta t = 5 km/h => \delta t = 2,7 s \) (N)
\( \rho_{max} = 133,3 Autos/km \)
Zellengröße 7,5 m
\( v_{max} = 5 Zellen/ Zeitschritt \)
Eine Zelle hat ein Auto oder nicht.
Zelluläre Automaten (ZA)
Grundcharakteristika
Zellraum
Zustandsmenge
Jede Zelle kann nur einen Zustand haben
Diskrete Zeit (N)
Zustand des ZA ändert sich in diskreten zeitschritten \( \delta t \)
lokale Übergangsfunktion (N)
Stochastische Erweiterung: Trödelfaktor (N)
Algorithmus 8.2 (Die Regeln des Nasch-Modells, SZA)
Update der Fahrzeuge:
Beschleunigen: v_i := min { v
i +1, v
{max} }
Bremsen: \( v_i := d(i,i+1) \) falls \(v_i > d(i,i+1) \)
Trödeln: v_i := max{v_i -1,0} mit Wahrscheinlichkeit p<1
Bewegen: Fahrzeug i bewegt sich \( v_i \) Zellen vorwärts.
Trödelschritt modelliert 3 Phänomene
Überreaktion beim Bremsen
Trödeln bei freier Fahrt
Verzögerung beim Beschleunigen
freier Verkehrsfluss
Höhere Dichten, Staus aus dem Nichts
Stauss aus dem Nichts entstehen durch Trödeln
Erhöhung der Trödelwahrscheinlichkeit
hartnäckigere Staus durch Erhöhung der Verkehrsdichte
Validierung und Kalibrierung: Fundamentaldiagramm
Fundamentaldiagramm wird verwendet um Modelle zu validieren. (N)
Modellierung von Verkehrsnetzen
Verzweigte Straßen, Kreuzungen, usw.
Verkehrsgraph
Knotenmenge V (N)
Kantenmenge E (N)
Kreuzungen
ungeregelte Kreuzungen ("Rechts vor Links")
Kreisverkehr
Kreuzungen mit geregelter Vorfahrt
Pläne & Vorhaben
Wohin soll es fahren?
Djikstra Algorithmus
Routenwahl durch Zufall
Modellverfeinerung
Exemplarisch aufzeigen wie aktuelles Modell verbessert werden kann.
LKW & Traktor einfügen
Motorräder & Fahrräder einführen
Sonntagsfahrer
Überholvorgänge
KE3
Stochastische Verkehrssimulation
Ziel: Gezeigt am Beispiel vom Drucker. Welche Leistung passt zu den Anforderungen?
Modellansatz
Ziel: Quantitative Analyse zur Leistungsbewertung
Beispiel Postamt
Optimierungsziel: Kunde & Post möglichst glücklich machen
Verweilzeit des Kunden & Filiale minimieren
Auslastung maximieren
Durchschnittliche Verweilzeit Kunde
Abbildung 9.1
Modellierung von Werte- & Bediensystem
Abbildung 9.2
Wartesystem
elementares Wartesystem (auch Bedienstation genannt: BS)
Abbildung 9.3
besteht aus
Warteschlange (WS)
identische Bedieneinheit (BE)
stochastische Prozesse
Begriffe (N)
Zwischenankunftszeit Abbildung 9.4
wird hier als Zufallsvariable betrachtet (N)
Ergebnisrisiko
Ist immer gleich hoch & unabhängig davon, wie lange wir schon warten
Ausfallsrate \( \lambda \) ist somit konstant
Das Wartezeitparadoxon (N)
Abbildung 9.6
Klassifizierung elementarer Wartesysteme
Kendall-Notation A/B/m [/k/n/D] (N)
Beispiele für typische Ankünfte & Bedienzeiten
D: Deterministische Verteilung
M: Exponentialverteilung
G: Allgemeine Verteilung
Beispiele
M/M/1 (N)
M/G/1 (N)
G/M/1 (N)
G/G/n (N)
Leistungskenngrößen & erste Ergebnisse
Verweilzeit y
y = w + b
Wartezeit w
Bedienzeit b
Füllung f (N)
Unterscheidung bei Warteplätzen/ Bedieneinheiten
belegt
beschäftigt
leere f = 0
Durchsatz d (N)
Grenzdurchsatz c (N)
elementares Wartesystem
Bei \( \lambda < \mu\) => langfristige Durchsatz = Ankunftsrate
Bei \( \lambda \geq \mu\) => langfristige Durchsatz = Bedienrate
reine Warteschlange \( d = \lambda \) und \( d = \mu \)
Auslastung \( \rho \) (N)
\( \rho = \frac{d}{c} \)
Bei voll ausgelasteten Wartesystemen \( \rho = 1 \)
Formeln von Little
Abbildung 9.7
Warteschlangennetze
(N)
Können als Graphen modelliert werden
Knoten = Bedienstationen
Kanten = potentielle Auftragswege
Beispiel: Abbildung 9.8
Unterscheidung
geschlossene Netze (N)
Anzahl der Aufträge konstant
Füllung konstant
offene Netze
Füllung variiert
Transitionshäufigkeit \( \rho_{ij} \) (N)
Parameter in Warteschlangennetzen
Index S kennzeichnet jeweilige Größe im System
Besuchzahl \( v_i \) (N)
Entspricht Verhältnis des Durchsatzes in i zu dem Netz
\( v_i = \frac{E(D_i)}{E(D_s)} = \frac{\rho_i}{E(D_s)} c_i \)
Verkehrsengpass VE (N)
Asymptotische Analyse
Systemdurchsatz \( E(D_s) \)
Verweildauer \( E(Y_s) \)
(deterministische) Füllung \( f_s \)
Abbildung 9.9
Sättigungsfüllung \( f^*_s \)
Passiert, weil sich Wartezeiten akummulieren
Je mehr Engpässe es gibt, desto schlechter wird die Annäherung
Analyse & Simulation
Zustandsgröße \( X(t) \)
Beispiel: Postamt
Zustandswahrscheinlichkeit \( \pi_i(t) := P(X(t)=i) \)
Phasen
Einschwingphase/ transiente Phase (N)
stationäre Phase (N)
Markov-Prozesse & Markov-Ketten
allgemeine Definition
Parameterraum T (N)
Zustandsraum Z (N)
diskrete Prozesse (N)
kontinuierliche Prozesse (N)
Zustand hängt immer vom aktuellen Zustand ab
Grundprinzip
Zustand & Zustandsübergänge
Knoten = Zustände
Kanten = mögliche Zustandsänderungen
Übergangswahrscheinlichkeit \( \rho_{ij} \)
Übergangsraten \( \lambda_{ij} = lim_{\delta t \rightarrow 0} \frac{P(X(t+ \delta t) 0 j| X(t) =i}{\delta t} \)
Beispiele
Münze Abbildung 9.10
Würfel Abbildung 9.11
Wartesysteme
Wartesystem stabil, wenn \( \lambda < m \mu \) (N)
M/M/1
Beispiel Postamt
M/M/m & M/M/\(\infty \)
Beispiel Multi-Server
Warteschlangennetze (N)
Simulation
diskrete Ereignissimulation
Ereignisliste
Nicht mehr zeitgetrieben sondern ereignisgetrieben
Wenn Warteschlangenprozesse immer komplexer werden
Petri-Netze zur Modellierung verwenden
Analytische Aussagen nicht mehr möglich
Deshalb muss simuliert werden
KE4
Populationsdynamik
(Richtung hier ausersehen vertauscht)
Zustandsraum
Anzahl Individuen der jeweiligen Art
Modell von Maltus
Wachstumsrate
\( \lambda = \gamma - \delta \)
Populationsänderung \( \dot{p}(t) \)
Lösung: \( p(t) = p_o e^{\lambda t} \) (N)
\( \dot{p}(t) = \lambda p(t) \)
Verfeinerte Ein-Spezies-Modelle
Lineares Modell mit Sättigung
\( \dot{p}(t) = \lambda_0 - \lambda_1 \varphi (t) \)
\( p = \tilde{p} := \lambda_0 / \lambda_1 \)
Gleichgewichtspunkt bei \( \dot{p} = 0 \)
stabiler Gleichgewichtspunkt (N)
Logistisches Wachstum (N)
Logistische Differentialgleichung: \( \dot{p}(t) = \lambda(p(t)) p(t) = a p(t) - b p(t)^2 \)
Modell hat zwei Gleichgewichtspunkte.
Mathematischer Hintergrund
Richtungsfeld der Lösungskurven für a = 1; b = 0,01 und verschiedene \(p_0\)
Lösung logistische Differentialgleichung: \( p(t) = \frac{a p_0}{bp_o + (a-bp_0)e^{-at}} \)
Zwei-Spezies-Modell
Modelle mit mehreren Arten, die miteinander in Wechselwirkungen stehen. (N)
Beispiel
Arten P & Q
Populationsgrößen \( p(t) \space{ } \& \space{ } q(t) \)
Annahmen
Modell von Malthus
Wachstum F (entspricht Wachstumsraten * Populationsgröße) \( \binom{\dot{p}}{\dot{q}} = \binom{f(p,q) p}{g(p,q) q} =: F(p,q) \)
logistischer Wachstum (Wachstumsrate pro Individuum & Zeit)
\( f(p,q) \) für \(P\) und \( g(p,q) \) für \(Q\)
\(p>0 \) und \(q>0 \) (N)
gesucht
\( f( \tilde{p}, \tilde{q}) = g( \tilde{p}, \tilde{q}) = 0 \)
Analyse der Stabilität des Gleichgewichtspunktes
rechte Seite von F linearisieren \( F(p,q) \dot{=} J_F (\tilde{p}, \tilde{q}) \binom{p-\tilde{p}}{q-\tilde{q}} \)
Jacobi-Matrix
Definition von f & g
\( f(p,q) = (a_1 - b_1 p -C_1 q) / \tilde{p} \) \( g(p,q) = (a_2 - c_2 p -b_2 q) / \tilde{q} \)
Jacobi-Matrix
Parameter festlegen, die folgende Bedingungen erfüllen
\( b_1 , b_2 \geq 0 \)
\( c_2 > 0 \)
\( a_2 > 0 \)
\( b_1 b_2 > C_1 C_2 \)
Lösung Abbildungen
Ein diskretes Ein-Spezies-Modell
diskrete Modelle sind unhandlicher als kontinuierliche
Zustandsraum diskrete Größe \( X(t) \)
Geburten & Sterbefälle müssen als zufällige Ereignisse modelliert werden
stochastischer Prozess nötig (N)
Gesucht: Zeitliche Entwicklung der Verteilung von X
\( \pi_x(t) := P(X(t) = x) \)
Zur Vereinfachung
Geburtenrate \( \gamma= konstant \) Sterberate \( \delta = 0 \)
Lösung: \( \pi_x(t) = e^{-\gamma t} (1-e^{-\gamma t})^{x-1} \)
Chaostheorie
