21
Stochastische Simulation !"#"$% "& ’ ( ) Stochastische Simulation Literatur: J. Banks et al., Discrete Event System Simulation, Prentice Hall, 2001. A.M. Law and W.D. Kelton, 1991: Simulation, Modeling and Analysis, McGrawHill, 1991. P. Page, Diskrete Simulation, Springer-Verlag, 1992. Stochastische Simulation * !"#"$% "& ’ ( ) Simulation mit stochastischen Modellaspekten Stochastische Modelle sind Modelle mit Zufallsaspekten Es werden Zufallsaspekte eingebracht bei der Bestimmung von - Zwischenankunftszeiten - Bedienzeiten - Ausfallszeiten - Entscheidungen - ... Simulationsexperimente mit stochastischen Modellen sind Zufallsexperimente damit sind alle statistischen Verfahren für Auswertung von Ergebnisvariablen einsetzbar daneben gibt es eine Reihe von Besonderheiten für die Simulation

PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� ��������������� �!�"#� �"$%��"�&

�������'������( ������)

Stochastische Simulation

Literatur:

• J. Banks et al., Discrete Event System Simulation, Prentice Hall,

2001.

• A.M. Law and W.D. Kelton, 1991: Simulation, Modeling and

Analysis, McGrawHill, 1991.

• P. Page, Diskrete Simulation, Springer-Verlag, 1992.

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� �*�������������� �!�"#� �"$%��"�&

�������'������( ������)

Simulation mit stochastischen Modellaspekten

• Stochastische Modelle sind Modelle mit Zufallsaspekten

• Es werden Zufallsaspekte eingebracht bei der Bestimmung von

- Zwischenankunftszeiten

- Bedienzeiten

- Ausfallszeiten

- Entscheidungen

- ...

• Simulationsexperimente mit stochastischen Modellen sind

Zufallsexperimente

– damit sind alle statistischen Verfahren für Auswertung von Ergebnisvariablen

einsetzbar

– daneben gibt es eine Reihe von Besonderheiten für die Simulation

Page 2: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� ���������������� �!�"#� �"$%��"�&

�������'������( ������)

Diskrete Modellierung

Bei der Modellierung unterscheidet man:

• Modellparameter

– sind vom realen System vorgegeben

– müssen durch Beobachtung und Messung bestimmt und modelliert werden

– sind nicht beeinflussbar durch den Modellierer

– werden oft als Variablen bestimmter Zufallsverteilungen modelliert

• Eingriffsmöglichkeiten

– sind jene Parameter im System, die variiert werden können

– bestimmen die Systemkonfiguration, die untersucht wird

– „die Schrauben, an denen man drehen kann“

• Ergebnisdaten (Leistungsmerkmale)

– ergeben sich durch die Simulation und stellen das Ergebnis dar; bei der diskreten Simulation die Leistungsmerkmale

– sind oft stochastische Variablen

– müssen statistisch ausgewertet werden

Modell

reales System

Modellierer

Ergebnis-

daten

Eingriffsmöglichkeiten

Modellparameter

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� �+�������������� �!�"#� �"$%��"�&

�������'������( ������)

Diskrete Modellierung (2)

Beispiele für die unterschiedlichen Kategorien von Modellvariablen :

• Modellparameter

– Verarbeitungszeiten bestimmter Bedienstationen

– Ausfallzeiten von Maschinen

– Ankunftsraten von Kunden

– Geschwindigkeiten von Fahrzeuge oder Personen

– ...

• Eingriffsmöglichkeiten

– Menge und Art der eingesetzten Bedienstationen, Maschinen oder Transporter

– Menge der eingesetzten Werkzeuge und Hilfsmittel

– Größe der Warteräume und Bufferplätze

– Reihung in den Warteschlangen

– Anordnung der Systemkomponenten

– Gestaltung der Transportwege

– Varianten in der Ablaufsteuerung

– ...

• Ergebnisdaten (response variables)

– Durchsatz an Kunden/Werkstücke

– Wartezeit der Kunden

– Länge von der Warteschlangen

– Auslastung der Ressourcen

– ...

Page 3: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� �,�������������� �!�"#� �"$%��"�&

�������'������( ������)

Experimentierrahmen und Modell

• man unterscheidet grundsätzlich

– Systemmodell: Modell des zu untersuchenden Modells

– Experimentierrahmen (Experimental Frame): stellt das Experiment am Modell dar

• zum Experimentierrahmen gehört

– Lastmodell: stellt den Ankunftsstrom der zu bediendenden/verarbeitenden Entities dar

– Ergebnisdaten: zu beobachtende Werte im Modell und deren Auswertung

– Steuerung des Experiments: Anfangsbedingungen und Bedingungen für Ende eines Experiments

Anmerkung: Experimentierrahmen und Modell sollten möglichst unabhängig voneinander sein (lässt sich aber oft schwer erreichen)

– Testen und Vergleich mehrere Modellvarianten unter dem gleichen Experimentierrahmen

– Simulation und Analyse eines Modells unter unterschiedlichen experimentellen Bedingungen

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� �-�������������� �!�"#� �"$%��"�&

�������'������( ������)

Lastmodell

• stellt den Ankunftsstrom der zu bedienenden/verarbeitenden Entities dar

• Für die Modellierung der Lastmodelle gibt es folgende Möglichkeiten:

– Trace-Driven Simulation: man verwendet reale Beobachtungen

– Stochastisches Modell: man charakterisiert Ankunftsstrom mittels Zufallsverteilungen

• Zufallsverteilung für Zwischenankunftszeiten

• Zufallsverteilung für Generierung der unterschiedlichen Arten von Entities

(mit unterschiedlichen Arbeitsaufträgen)

– Maximale Last: System wird bei maximaler Last getestet, d.h. es

stehen jederzeit Entities zur Verarbeitung bereit

Page 4: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� �.�������������� �!�"#� �"$%��"�&

�������'������( ������)

Durchführung von Simulationsprojekten (1)

• Festlegen der Zielsetzung des Simulationsprojekts

– Entscheidungskriterien

– Festlegen der Ergebnisvariablen

– Bestimmen der Eingriffsmöglichkeiten

• Modellierung

– Modellstruktur mit möglichen Modellvariationen

– Modellierung der Modellparameter

• Bestimmung geeigneter Zufallsverteilungen

• Modellverifikation und Modellvalidierung

– Modellverifikation: Zeigen der Korrektheit des Modells

– Modellvalidierung Prüfen, dass Realität adäquat abgebildet wurde (durch

Vergleich der Simulationsdaten mit realen Daten)

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� �/�������������� �!�"#� �"$%��"�&

�������'������( ������)

Durchführung von Simulationsprojekten

• Durchführung von Simulationsexperimenten

– Simulationsläufe als Zufallsexperimente

• Transientes Verhalten

• Steady-State Analyse, d.h. System im eingeschwungenen Zustand

– statistische Auswertung der Ergebnisdaten

• Beobachtung von bestimmten Leistungsmerkmalen

• Bestimmung von statistischen Größen wie Min, Max, Mittelwert, Varianz,

Konfidenzintervalle

• Entscheidungsfindung und Sensitivitätsanalyse

– Variation von bestimmten Parametern und Beobachtung der Wirkung

– Variation der Modellstruktur und Steuerung

• Optimierung

– Festlegen der möglichen Parametervariationen und einer Zielfunktion

– gezielte Suche nach Modellparametern, die zu einer optimalen Systemleistung

führen

– Einsatz von heuristischen oder stochastischen Optimierungsverfahren

Page 5: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� �0�������������� �!�"#� �"$%��"�&

�������'������( ������)

Bestimmung von Zufallsverteilungen für Modellparameter

• ausgehend von Messungen und Beobachtungen soll eine

Zufallsverteilung für einen Modellparameter bestimmt werden

• Vorgehen

– Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu

machen

– Wahl einer Verteilung (z.B. Normalverteilung), die die das Histogramm

möglichst annähert

– Bestimmung der Parameter der Verteilung aus den Messdaten

– Goodness-of-Fit-Tests, z.B. X2-Test

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� �1�������������� �!�"#� �"$%��"�&

�������'������( ������)

Zufallsverteilungen für Modellparameter: Vorgehen (1)

• Histogramm

• Wahl der Verteilung, z.B. Normalverteilung

• Parameter der Verteilung bestimmt durch Maßzahlen der Messungen (z.B. Mittelwert und Varianz)

Page 6: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� �2�������������� �!�"#� �"$%��"�&

�������'������( ������)

Zufallsverteilungen für Modellparameter: Vorgehen (2)

• Test, ob Messdaten der gewählten Verteilung gehorchen (z.B. X2-Test)

– Hypothese: H0: die Beobachtungen gehorchen einer bestimmten

Verteilung, H1: die Beobachtungen gehorchen nicht dieser Verteilung

– Bilden des X2-Wertes als Quadrate der Abstände von beobachteten und

berechneten Werten

mit hi = beobachtete Wahrscheinlichkeit und ei ist Wahrscheinlichkeit aus

Verteilung

– Ermittlung des kritischen Wertes c aus Tablle der X2-Verteilung mit f

Freiheitsgraden und einem bestimmten Wahrscheinlichkeitswertes α, wobei f sich ergibt aus der Anzahl der Klassen der Beobachtungen minus 1 minus

Anzahl der freien Parameter der Verteilung (z.B. Normalverteilung 2 freie

Parameter)

– Test der Hypothese nach

Ist X2-Wert größer als c so muß H0 verworfen werden

( )�

−=Χ

i i

ii

e

eh2

2

( ) α=>Χ cP2

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� +*�������������� �!�"#� �"$%��"�&

�������'������( ������)

Häufigkeitsfunktion von Wahrscheinlichkeitsverteilungen

• diskrete Verteilung : Gibt die

Wahrscheinlichkeit für das Auftreten

eines Wertes x an

• stetige Verteilung:

Wahrscheinlichkeitsdichte f

�=≤<b

a

dvvfbxaP )()(

)()( xhxP =

Page 7: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� +��������������� �!�"#� �"$%��"�&

�������'������( ������)

Verteilungsfunktion von Wahrscheinlichkeitsverteilungen

• diskrete Verteilung : Gibt die

kummulierte Häufigkeit aller

Wahrscheinlichkeiten für Werte <= x an

• stetige Verteilung:

�∞−

=x

dvvfxF )()(

�≤

=≤=xx

j

j

xhxXPxF )()()(

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� ++�������������� �!�"#� �"$%��"�&

�������'������( ������)

• Binomialverteilung

– Wahrscheinlichkeit p(x) für x Erfolge bei n Versuchen, wobei die Versuche

unabhängig sind und die Erfolgswahrscheinlichkeit jeweils p ist

– Parameter: p und n

• Poissonverteilung

– Wahrscheinlichkeit p(x), dass in einem bestimmten Zeitintervall x

Ereignisse auftreten

– Parameter: λ Mittelwert für Anzahl der Ereignisse

• Exponentialverteilung

– Zwischenankunftszeit bei einem Poisson-Prozess

– Parameter: λ Mittelwert für Anzahl der Ereignisse

• k-Erlangsche Verteilung

– Prozess mit k-Phasen mit jeweils exponentialverteilten Zeiten = Summe

von k exponentialverteilten Prozessen

– Parameter: λ Mittelwert für exponentialverteilten Prozess, k Anzahl der unabhängigen Prozesse

• Normalverteilung

– modelliert eine Verteilung für Prozesse, die sich aus vielen

Einzelprozessen ergeben (zentraler Grenzwertsatz)

– Parameter: Mittelwert µ und Varianz σ

Gebräuchliche Zufallsverteilungen (1)

Page 8: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� +,�������������� �!�"#� �"$%��"�&

�������'������( ������)

• Weibull-Verteilung

– nähert die Lebenszeit von Systemen, die aus mehrere Einzelteilen

bestehen, wobei der Ausfall eines Teils den Ausfall des Gesamtsystems

bedeutet

• Triangularverteilung

– Verwendet, wenn nur minimaler, maximaler und wahrscheinlichster Wert

bekannt sind

– Parameter: Minimum, Maximum, Modalwert

• Gleichverteilung

– gleiche Wahrscheinlichkeit der Werte zwischen Minimum und Maximum

– Parameter: Minimum und Maximum

• Diskrete Tabelle

– diskrete Werte

– Wahrscheinlichkeiten direkt aus Beobachtungen

– Parameter: Liste von Paaren mit Wert und Wahrscheinlichkeit des

Auftretens

• Kontinuierliche Tabelle:

– Wahrscheinlichkeiten der Werte aus Beobachtungen

– Stützpunkte der Verteilung in Form von Werten - Wahrscheinlichkeiten

– Interpolation der Zwischenwerte

• und weitere

Gebräuchliche Zufallsverteilungen (2)

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� +-�������������� �!�"#� �"$%��"�&

�������'������( ������)

Generierung von Zufallszahlen bestimmter Verteilungen (1)

• Bei der Simulation müssen für die Modellgrößen fortlaufend

Zufallszahlen generiert werden, die den modellierten Verteilungenentsprechen

• Ausgangsbasis dafür sind klassische Zufallszahlengeneratoren, die

gleichverteilte Zufallszahlen im Intervall [0,1] erzeugen

• mit Hilfe der Umkehrfunktion der Verteilungsfunktion werden daraus Zufallszahlen nach der vorgegebenen Verteilung generiert

Zufallszahlen-generator

inverseTransformation

[0,1]-gleichverteilte

Zufallszahlen

Zufallszahlender vorgegeben

Verteilung

Page 9: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� +.�������������� �!�"#� �"$%��"�&

�������'������( ������)

Generierung von Zufallszahlen bestimmter Verteilungen (2)

• gegeben Verteilungsfunktion

(kumulierte Häufigkeit)

)(1rFx

−=

• erzeuge eine gleichverteilte Zufallszahl r

zwischen 0 und 1

• löse die Gleichung F(x) = r nach x, d.h.

�∞−

=x

dyyfxF )()( �≤

=xy

yhxF )()(

stetig diskret

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� +/�������������� �!�"#� �"$%��"�&

�������'������( ������)

Gleichverteilte Zufallszahlen UD (a,b) in einem beliebigen Intervall [a, b]

0

1

a b a x b

r

1/(b-a)

f(x) F(x)

)(1

abraxab

r

ax−⋅+=�

−=

Page 10: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� +0�������������� �!�"#� �"$%��"�&

�������'������( ������)

Exponentialverteilung ED(1/λλλλ)

• Zwischenzeiten bei Poissonprozessen

• z.B. für Zwischenankunftszeiten, Zeiten zwischen Ausfällen

• wobei λ die Ankunftsrate und 1/ λ der Mittelwert der Zwischenankunftszeiten ist

rx

rx

rexFx

ln1

)1ln(1

1)(

λ

λ

λ

−=

−−=

=−= −1

x

r

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� +1�������������� �!�"#� �"$%��"�&

�������'������( ������)

Normalverteilung (Gaußverteilung) ND(µµµµ, σσσσ)

• Für F-1 gibt es keine geschlossene Formel

• aber es gibt zwei Verfahren, um normalverteilte Zufallszahlen zu erzeugen:

1) Verfahren basierend auf zentralem Grenzwertsatz

– die Summe von 12 gleichverteilten Werten UD(0,1) ist eine Näherung für eine Normalverteilung mit Mittelwert 6 und Varianz 1

– normierte Normalverteilung ND(0,1)

– Normalverteilung mit beliebigen Mittelwert µ und Standardabweichung σ

6)1,0(*12 −= UDz

µσ += zx

Page 11: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� +2�������������� �!�"#� �"$%��"�&

�������'������( ������)

Normalverteilung (Gaußverteilung) ND(µµµµ, σσσσ) (2)

2) Näherung von Werten der Normalverteilung mittels Tabelle

- gegeben ist eine Tabelle mit einigen Stützpunkten der normierten Normalverteilung

ND(0,1)

- Erzeuge eine gleichverteilte Zahl r = UD(0,1) zwischen 0 und 1

- Durch Interpolation (lineare) berechne einem Wert z der normierten

Normalverteilung aus der Tabelle

- Normalverteilung mit beliebigen Mittelwert µ und Standardabweichung σ durch

µσ += zx

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� ,*�������������� �!�"#� �"$%��"�&

�������'������( ������)

Triangularverteilung

• Triangularverteilung ist gegeben durch minimalen, maximalen und Mittelwert

• einfacher Ersatz für Normalverteilung

• oder wenn wenig Messdaten vorhanden

��� ������ ���

��

� ��� ������ ���

��

�� �

Page 12: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� ,��������������� �!�"#� �"$%��"�&

�������'������( ������)

Empirische Verteilung

• Viele Messungen in der Realität lassen sich nicht optimal durch die gängigen Verteilungen abbilden

• Beobachtungen zur Erzeugung von Zufallszahlen (empirische Verteilungen)

– Beobachtungen

– Klassenbildung mit relativen Häufigkeiten

– kumulierte Häufigkeit

– Interpolation

1 2 3 4 5 6 7

1

f(X)

X1 2 3 4 5 6 7

1

F(X)

X

r

x=F-1(r)

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� ,+�������������� �!�"#� �"$%��"�&

�������'������( ������)

Diskrete, empirische Verteilung

• Beispiel: Länge von Dateien in

Spuren

Spuren (i) Häufigkeits

verteilung (f(i))

kummulierte

Häufigkeiten (F(i))

1 0,06 0,06

2 0,17 0,23

3 0,238 0,468

... ... ...

10 = n 0.003 1,0

��� ���� �������� ����� ��

���������������

�� ������������ ��� �!������

��� � ���

"

Page 13: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� ,,�������������� �!�"#� �"$%��"�&

�������'������( ������)

Statistische Auswertung

• Simulationsexperimente sind Zufallsexperimente;

Ergebnisvariablen sind stochastische Variablen

� alle statistischen Verfahren anwendbar

– Mittelwert

– Varianz

– Konfidenzintervalle

– ...

• um statistisch signifikante Ergebnisse zu bekommen

– viele Experimente

– und/oder lange Läufe (Batchmittelwertverfahren)

• Es gibt einige spezielle Phänomene bei der Simulation, die

besonders beachtet werden müssen

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� ,-�������������� �!�"#� �"$%��"�&

�������'������( ������)

Leistungsmerkmale (1)

Folgend sind typische Leistungsmerkmale für Systeme aufgelistet

Allgemeines:

– Beobachtungszeitraum (time)

– Anzahl der Beobachtungen obs (observations)

– Raten (rate)

– mittlere Zwischenzeit (mean)

• Ankunftsprozesse :

– erzeugte Werkstücke (arrived)

– Ankunftsrate λλλλ (arrival rate)

– Zwischenankunftszeit ia_time (interarrival time)

• Durchsatz:

– bearbeitete Werkstücke solved

– Durchsatz throughput

time

obsrate =

ratemean

1=

time

arrived=λ

λ

1_ =timeia

time

solvedthroughput =

Page 14: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� ,.�������������� �!�"#� �"$%��"�&

�������'������( ������)

Leistungsmerkmale (2)

• Umlaufzeit tat (turnaround time):

– Zeitintervall zwischen Ankunft und Verlassen eines (Teil-)Systems

• Arbeit

– Arbeitszeit time_busy

– Auslastung utilization

– Freizeit time-idle

• Warteschlangen

– Länge von Warteschlangen = Anzahl der Werkstücke in der

Warteschlange queue_length

– Wartezeit eines Kunden in der Warteschlange waiting_time

time

busytimenutilizatio

_=

busytimetimeidletime __ −=

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� ,/�������������� �!�"#� �"$%��"�&

�������'������( ������)

Zeitgewichtete und nicht-zeitgewichtete Statistiken

In der Simulation unterscheidet man grundsätzlich zwei Arten von

Statistiken:

• nicht-zeitgewichtete Statistiken (auch Observational oder Tallygenannt)

– Statistik pro Beobachtung

– oft verwendet für Mittelwerte über Zeiten

– Bsp.: durchschnittliche Bedienzeit, Wartezeit oder Umlaufzeit pro

Werkstück

• zeitgewichtete Statistiken (auch Timed oder Accumulate genannt)

– Statistik über eine Zeit

– verwendet für sich über die Zeit ändernde Zustände

– Bsp.: Durchschnitt der Länge einer Warteschlange in einer Zeitspanne,

Auslastung einer Bedienstation, etc.

Page 15: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� ,0�������������� �!�"#� �"$%��"�&

�������'������( ������)

Nicht-zeitgewichteter Mittelwerte und Standardabweichung

genBeobachtunderAnzahl

WertederSumme

n

xx

i==

�Mittelwert:

Standardabweichung: 2ss =

Varianz:

��

���

−= �

=

n

j

j xnxn

s1

222

1

1��

���

−= ��

==

2

11

22 )(1

1

1 n

j

j

n

j

j xn

xn

s�=

−−

=n

j

j xxn

s1

22 )(1

1oder oder

Schätzwerte für Mittelwert und Varianz:

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� ,1�������������� �!�"#� �"$%��"�&

�������'������( ������)

Zeitgewichteter Mittelwert

time

txx

xj

jj�=

)*(

xi

s

T

txi

• Schätzwert für Mittelwert (für einen Simulationslauf)

– Ergibt sich aus der Fläche der Zustandstrajektorie / Zeit

mit xi ist der Zustandswert und mit txi sei die Zeit bezeichnet, die der

Zustand xi gesetzt ist

Page 16: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� ,2�������������� �!�"#� �"$%��"�&

�������'������( ������)

Konfidenzintervalle

P(u1 ≤ u ≤ u2) = γ

Die Wahrscheinlichkeit, daß der Parameter u zwischen u1 und u2 liegt beträgt γ

oder

Konfidenzintervall ist jenes Intervall [u1, u2], sodaß mit Wahrscheinlichkeit γgarantiert werden kann, daß der Parameterwert u in [u1, u2] liegt.

Beispiele:

• die mittlere Warteschlangenlänge ist mit 99 % Sicherheit zwischen [7.8, 9,2]

• die Auslastung der Verarbeitungseinheit liegt mit 95 % Sicherheit im Bereich [0.72,

0.84]

Berechnung:

mit z abhängig von Wahrscheinlichkeitsniveau γ

(z = 1,64 für γ=90%, z = 1,96 für γ=95%, z = 2,58 für γ=99%,

��

���

+−

n

szx

n

szx ,

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� -*�������������� �!�"#� �"$%��"�&

�������'������( ������)

Beispiel

# $�������� ��%���������&�� � ������ ������������������� ��������%����������'���������� ���������� ������ �����������(�) ���������*������������ ��������&��������������� ������ ����� ���������������� �+�

# ,���� ����������������� ��� ������*��������������������������������������������������������*� �����+�

# -*� ����.������/����0(�� ��1(23

# -*� ����.�������� �������0�� ���(11456���

# )������ ������ ����7��������8α�����9���������������� *����� �� �������µ &�*���� �����'�� *���������������� ���������� ��� �������������������'����� �� ���8���� �'��������������� ������ *�������� ������� ��� �� ����8α � �'�'����%����������������� ���� ������� *��(�

# �� ���:�9���������������� *���������;�(:2�5(;2;1

4.25=X4�4,9,2,2

5.5=X3�5,5,7,5

4.5=X2�6,8,1,3

4=X1�7,2,3,4

�=

−=4

1

22 )(3

1

i

i XXs

]3484.5,7766.3[4

)95.0(,4

)95.0( 33 =��

���

+−

stX

stX

Page 17: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� -��������������� �!�"#� �"$%��"�&

�������'������( ������)

Beispiel Konfidenzintervalle

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� -+�������������� �!�"#� �"$%��"�&

�������'������( ������)

Terminating versus Steady-State Simulation

Zwei grundsätzliche Arten von Simulationsexperimenten:

• Terminating Simulation (Transientes Systemverhalten )

– Es gibt eine definierten Anfang und ein definiertes Ende der

Simulationsexperiments

– Bsp.: In einem Produktionsbetrieb von Beginn bis Ende des Arbeitstages

• Steady-State Simulation:

– Es gibt keinen definierten Anfang und kein Ende

– man ist vielmehr an einem durchschnittlichen Langzeitverhalten interessiert

– dabei bedeutet Steady-State nicht dass der Zustand stabil ist sonder

dass sich die Wahrscheinlichkeiten für das Auftreten von bestimmten Zuständen nicht mehr ändern !!!

� Steady-State-Simulation sind wesentlich schwieriger

– wann ist Steady-State erreicht??

– Problem der Anlaufphase (welche stört und statistisch nicht signifikant ist)

Page 18: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� -,�������������� �!�"#� �"$%��"�&

�������'������( ������)

Anlaufphase bei Simulationsexperimenten

Simulationsexperimente durchlaufen gewöhnlich verschiedene Phasen– Anfangszustand

– transiente Phase: Größen x stark von Zeit t abhängig

– stationäre Phase: Größen x nicht von Zeit t abhängig

T

X

transient stationär

Transiente Phase am Anfang verfälscht statistische Ergebnisse

� diese solle in der statistischen Auswertung oft nicht berücksichtigt werden

Heuristiken zur Bestimmung der transienten Phasen:

• über einen Zeitraum keine neuen (signifikaten) Minimas und Maximas (Ende der

steigenden Phase)

• über längere Zeit keine größeren Veränderungen von x

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� -.�������������� �!�"#� �"$%��"�&

�������'������( ������)

AnyLogic: Zufallsverteilungen

• AnyLogic 4.5 bietet eine Reihe von Verteilungen als Klassen

implementiert abgeleitet von �����

� ������������ ������������� ������������� ������������� �

� ������ �� ������ �� ������ �� ������ ��

� �������� ��������� ��������� ��������� �

� ��������������������������������������������

– ...

• Objekte können zur Generierung von Zeiten bei

� ������������������������

� �������������������������������� von �� ���� ���� ���� ���� ���� ���� ���� ��-Transitionen

Page 19: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� -/�������������� �!�"#� �"$%��"�&

�������'������( ������)

AnyLogic: statistische Auswertung

� � � ���� � ���� � ���� � ��� ist ein Modellelement zur Berechung von Statistiken

• Werte werden durch

�������� �������� �������� �������� ��������

dem � � ���� � ���� � ���� � ��� angefügt.

• Es wird über die Werte berechnet:

– Minimum und Maximum

– Mittelwert

– Varianz und Standardabweichung

– Konfidenzintervall für Mittelwert

– Histogramm (bei entsprechenden Einstellungen)

• Zeitgewichtete Statistik mit Einstellung

��������������������

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� -0�������������� �!�"#� �"$%��"�&

�������'������( ������)

AnyLogic: Beispiel statistische Auswertung available von Resource

� � � ���� � ���� � ���� � ��� � ���� � � ���� � � ���� � � ���� � für Statistik

über Verfügbarkeit einer Resource

� � ���� � ���!� � ���� � ���!� � ���� � ���!� � ���� � ���!�" wenn verfügbar

� � ���� � ���#� � ���� � ���#� � ���� � ���#� � ���� � ���#�" wenn nicht verfügbar

• Auswertung als ��������������������-Statistik mit

entsprechenden Ergebnissen

Page 20: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� -1�������������� �!�"#� �"$%��"�&

�������'������( ������)

AnyLogic: Steuerung der Simulationsexperimente

$���%����$���%����$���%����$���%����-Dialog bietet Möglichkeiten zur

– Durchführung mehrerer Simulationsläufe

– Abbruch bei bestimmten Bedingungen

• Konfidenzintervall klein genug

• Erreichen eines Zustandswertes

• Benutzerdefinierte Bedingung

– Einstellung der Zufallszahlengeneratoren

• fixed seed

• random seed

– Optimierung

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� -2�������������� �!�"#� �"$%��"�&

�������'������( ������)

Simulation und Optimierung

• Kombination von (stochastischen, heuristischen)

Optimierungsverfahren und Simulation

– Optimierung gibt beeinflußbare Parameter und Zielfunktion vor

– Simulation liefert die Ergebnisse für eine bestimmte Parametervariation

– Optimierungsverfahren variiert die Parameter entsprechend der

Ergebnisse und initiiert neue Simulationsläufe

Parameter

Zielfunktion

ErgebnisseHeuristischesOptimierungs-

verfahren

HeuristischesOptimierungs-

verfahren

SimulationSimulation

Page 21: PowerPoint - 12-StochastischeSimulation · – Aufstellen eines Histogramms, um die Verteilung der Messwerte sichtbar zu machen – Wahl einer Verteilung (z.B. Normalverteilung),

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� .*�������������� �!�"#� �"$%��"�&

�������'������( ������)

Optimierungsverfahren

• Methode des gleichförmigen Rasters

• reine stochastische Suche

• Simulated Annealing

• Methode des steilsten Anstieges (Hill-Climbing)

• Einzelfaktormethode

• Mutationsmethode (Genetische und Evolutionäre Algorithmen)

Sto

ch

as

tis

ch

e S

imu

lati

on

����������������� ������������������� ��������� .��������������� �!�"#� �"$%��"�&

�������'������( ������)

Zusammenfassung

• Simulation bedeutet Experimentieren mit Modellen, dabei handelt es

sich häufig um Zufallsexperimente, d.h. bzgl. Experimentdesigns

(welche Verteilung von Inputs) als auch bzgl. Interpretation der Outputs

sind statistische Verfahren notwendig.

• Modellierer:

– Hypothese über die Verteilung von exogenen Parametern (Test z.B. Chi-

Quadrat)

– Protokollierung von Kenngrößen und statistische Auswertung (Mittelwert,

Varianz, Konfidenzintervalle)

• Simulationsprogrammierer:

– Wahl bzw. Implementierung eines Zufallszahlengenerators z.B. ein

PMMLCG, der eine Uniforme Verteilung berechnet

– darauf basierend zur Verfügungstellung von gebräuchlichen Verteilungen,

z.B. Poisson, Exponential, Normal etc.