Modellierung und Simulation 1 - fh-swf.de · Modellierung und Simulation 1 Prof. Dr. H. Schulze Prof. Dr. C. Lüders 4.1 Wichtige Begriffe Fehler (Failure): Ein Objekt erfüllt seine

Modellierung und Simulation 1

Prof. Dr. H. Schulze

Prof. Dr. C. Lüders

Modellierung und

Simulation 1

Prof. Dr. Henrik Schulze, Prof. Dr. Christian Lüders

Fachhochschule Südwestfalen

Standort Meschede

Fachbereich Ingenieur- und Wirtschaftswissenschaften

Tel.: 0291 / 99 10 -4300 | -4261

E-Mail: schulze.henrik | [email protected]

Kap. 4: Zuverlässigkeit und Verfügbarkeit

Kap. 5: Bediensysteme




Kap. 4: Zuverlässigkeit u. Verfügbarkeit

(in technischen Systeme)

4.1 Klärung wichtiger Begriffe

4.2 Zusammengesetzte Systeme

4.3 Stichproben und statistische Tests

Literatur

• A. Meyna, B. Pauli: Zuverlässigkeitstechnik – Quantitative Bewertungsverfahren, Hanser Verlag, 2010

• S. Eberlin, B. Hock: Zuverlässigkeit und Verfügbarkeit technischer Systeme : Eine Einführung in die Praxis,

Springer Fachmedien, 2014

• G. Linß: Qualitätssicherung – Technische Zuverlässigkeit, Hanser, 2016

• B. Bertsche, G. Lechner: Zuverlässigkeit im Fahrzeug- und Maschinenbau, Springer/VDI, 2004

• B. Bertsche, u.a.: Zuverlässigkeit mechatronischer Systeme, Springer/VDI, 2009




4.1 Wichtige Begriffe Fehler (Failure): Ein Objekt erfüllt seine vorgesehene Funktion nicht.

Objekt: Bauteil, technisches System, Industrieanlage

Fehlerrate: Fehlerwahrscheinlichkeit – Zahl zu erwartender Fehler

bezogen auf die Gesamtheit der betrachteten Objekte

Fehlerarten:

• vollständige Funktionsunfähigkeit

• eingeschränkte Leistungsfähigkeit

• Abweichung von Datenblättern / Spezifikationen

Behebbarkeit / Reparierbarkeit?

Dauer der Reparatur / des Austausches (Time to Repair)

Verfügbarkeit V (Availability): Wahrscheinlichkeit, dass System (zur Zeit t)

funktionsfähig

Unverfügbarkeit U = 1 – V




Fehler in Stichproben: Binomial-Verteilung

Zufallsvariable mit zwei exklusiven Ereignissen:

• E1 (z.B. Bauelement defekt) – Fehler-Wahrscheinlichkeit p

• E2 (z.B. Bauelement intakt) – Wahrscheinlichkeit q = 1 – p

Wie groß ist die Wahrscheinlichkeit bei einer Stichprobe von n Bauelementen

in einer Gesamtheit von N Bauelementen (N >> n) k defekte zu finden?

, ( ) (1 ) , 0,1,2,...,k n k

n p

nb k p p k n

k

!:

! ( )!

n nBinomial Koeffizient

k k n k

0 1 1 0

1, 1,(0) 1 (1 ) 1 , (1) 1 (1 )p pb p p p b p p p Beispiel: n = 1 Ziehung

! 1 2 3 ... , 0! 1n n




Binomial-Verteilung Beweis

Beweis über vollständige Induktion

• Aussage richtig für n = 1 (s.o.), Annahme: Aussage richtig für n - 1

• Nachweis der Richtigkeit für n:

, 1, 1,( ) ( 1) ( ) (1 )n p n p n pb k b k p b k p

( 1)! ( 1)!

( 1)! ( )! ! ( 1 )!

n n

k n k k n k

, ( ) (1 ) , 0,1,2,...,k n k

n p

nb k p p k n

k

1 1(1 ) (1 )

1

k n k k n kn n

p p p pk k

bisher:

k-1 Fehler

bisher:

k Fehler

kein

Fehler

jetzt:

Fehler

1 1

1

n n

k k

! !

! ( )! ! ( )!

k n n k n

n k n k n k n k

n

k




Kenngrößen der Binomial-Verteilung

Erwartungswert (für einen Fehler): E{K} = n p

(1 )K n p p

(1 )

0 ( )K p

C K für nE K n p

1 2

(1 )

pV K

n p p

0

0,05

0,1

0,15

0,2

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

p = 0,3 p = 0,5

0

0,05

0,1

0,15

0,2

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

p = 0,3 p = 0,5

Standard-Abweichung

Variationskoeffizient

n = 20

Schiefe

n = 40




Übungen zur Binomial-Verteilung a) Berechnen Sie mit Matlab die Fakultäten von N = 1 | 2 | 3 | 4 | 5 | 6 !

b) Berechnen Sie die Gamma-Funktion: gamma(N+1)! Was fällt Ihnen auf?

c) Plotten Sie die Funktion gamma(x) in den Bereichen 1 bis 4 bzw. 1 bis 40

bei einer logarithmischen Auftragung der y-Achse! Was fällt Ihnen auf?

d) Plotten Sie die Wahrscheinlichkeitsdichte der Binomial-Verteilung für:

• n = 4, p = 0,1 bzw. n = 40, p = 0,01

e) Wahrscheinlichkeit bei 4 Ziehungen 2 oder mehr defekte Bauteile zu finden?

f) Vergleichen Sie die Binomial- und Poisson-Verteilung für µ = p n !

g) Fehlerrate p = 0,01: Wie groß muss man n wählen, dass bei n Ziehungen

nicht mehr als 1,05 p n Fehler auftreten?

h) Erzeugen Sie Binomial-verteilte Zufallszahlen und das zugehörige Histogramm!




Zeitlicher Verlauf beim Ausfall von Objekten Zeit von einem Startpunkt bis zum Ausfall einer Baugruppe ist Zufallsvariable T mit

Wahrscheinlichkeitsfunktion (Failure): F(t) = PT(T ≤ t)

Ausfallwahrscheinlichkeit

Zuverlässigkeitsfunktion (Reliability): R(t) = 1 – F(t)

Überlebenswahrscheinlichkeit

Fehlerwahrscheinl. in Intervall Dt bei t: f(t) Dt

Mittlere Lebensdauer – Mean Time to Failure (MTTF)

Bei Reparatur: Mean Time Before Failure (MTBF)

Verfügbarkeit V: Wahrscheinlichkeit, dass funktionsfähig

Unverfügbarkeit U = 1 –V

= 1 – e–µt

= e–µt µDt

= e–µt

( )MTTF E T t f t dt

0

1µ tµ t e dtµ

Typisches Beispiel: Exponentieller Zerfall

MTBFV

MTBF MTTR




Zeitlicher Verlauf beim Ausfall von Objekten

L10: Zeit (Life Time), nach der 10% der Bauelemente ausgefallen sind

a(t): Anteil der Bauelemente, die pro Zeitintervall Dt ausfallen, unter denen,

die bis zur Zeit t überlebt haben Erläuterung im Folgenden

L10 = –µ-1 ln(1 – 0,1)

a(t) = µ

Typisches Beispiel: Exponentieller Zerfall




)(

)|(BP

BAPBAP

Wahrscheinlichkeit, dass A eintritt unter der Bedingung, dass B vorliegt.

)(

)(

)(

)()|( AP

BP

BPAP

BP

BAPBAP

Falls A und B unabhängig sind:

Bedingte Wahrscheinlichkeit:

Wiederholung: Bedingte Wahrscheinlichkeiten

1 2 3 4 5 6

1 2 3 4 5 6 7

2 3 4 5 6 7 8

3 4 5 6 7 8 9

4 5 6 7 8 9 10

5 6 7 8 9 10 11

6 7 8 9 10 11 12

Bsp: Würfeln mit 2 Würfeln

A: Augenzahlsumme 7

12/736/21)( AP

B: erster Würfel zeigt 6

6/1

6/1

)()|(

BP

BAPBAP

B: erster Würfel gerade

3

2

2/1

36/12

)()|(

BP

BAPBAP




)(

)|(BP

BAPBAP


)(1

)()|],[(

tP

ttpüberlebttZeitzurbistttinAusfallPP

T

Tausfall

DDD

)(1

)(lim)(

0 tP

tp

t

Pt

T

Tausfall

t

D

D

Da

Wahrscheinlichkeit, dass Bauteil bis zur Zeit t ausfällt:

Verteilung: F(t) = PT( T ≤ t), Dichte: pT(t) = f(t) = F‘(t)

Ausfallrate:


Bestimmung der Übergangsrate:

• A: Ausfall im Intervall [t, t + Dt]

• B: bis zur Zeit t überlebt

Bedingte Wahrscheinlichkeiten u. Ausfallrate / Ende-Rate

Einheit: 1/s oder 1/h oder …




( ) ( )( )

1 ( ) ( )

T

T

p t f tt

P t R ta

Ausfallrate:

)exp()()( tµµtptf T

Exponential-Verteilung mit Parameter µ:

Dichte:

)exp(1)()( tµtPtF T

µµt

µtµ

tP

tpt

T

T

))exp(1(1

)exp(

)(1

)()(a

Ausfallrate

Sterberate

Ende-Rate

Bei einer Exponential-Verteilung ist die Ausfallrate konstant (µ) und hängt nicht

von der Vorgeschichte ab – Gedächtnislosigkeit (Memoryless)

Mittlere Lebensdauer (Mean Time Before Failure): MTBF = E{T} = t = 1/µ

Analog bei Zwischenankunftszeiten/ Reparaturzeiten gemäß Exponential-Verteilung:

Konstante Ankunftsrate l / Reparaturrate r : r = 1/MTTR (Mean Time To Restore)

Ausfallrate: Gedächtnislosigkeit Exponential-Verteilung




Zahlenbeispiele für e-Funktion als Zuverlässigkeit

10-2

10-1

100

101

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Zuverlässigkeitsfunktion R(t)

Zeit t /MTTF

Ausfall-Rate a(t): Anteil der Bauelemente, die pro Zeitintervall Dt ausfallen, unter denen,

die bis zur Zeit t überlebt haben

1 Fit (Failure in Time bei elektron. Bauelemente): a = 10–9 pro Betriebsstunde

Beispiel: Test von 100000 Widerständen, 72 Ausfälle in 10 Monaten

a = 72 / (105 7200 h) = 10–7 h–1 = 100 FIT

MTTF = 1 / a = 107 h = 1142 Jahre

L10 = 120 Jahre

nach 5 Jahren: ca. 430 Ausfälle

Wah

rsch

ein

lich

kei

t

Ausfallfunktion R(t)

L10 Halbwerts-

zeit

MTTF




Sterbedaten - Deutschland

de.wikipedia.org/wiki/Datei:Sterbetafel.svg

de.wikipedia.org/wiki/Datei:Altersspezifische_

Sterberaten_Deutschland.svg

Quelle Datengrundlage: Statistisches

Bundesamt, Wiesbaden 2011

Urheber bzw.

Nutzungsrechtinhaber gnosis

Datum 24. August 2012

Datum 11. Mai 2013, 13:37:50

Quelle Eigenes Werk with data from the Human

Mortality Database (http://www.mortality.org)

Urheber Sven Drefahl

http://www.mortality.org/

https://commons.wikimedia.org/wiki/User:SvenDr

https://commons.wikimedia.org/wiki/User:SvenDr




0

( ) ( )( ) lim

1 ( ) ( )

ausfall T

tT

P p t f tt

t P t R ta

D

D

D Ausfallrate:

Weibull-Verteilung mit Parameter µ, k:

Dichte:

k

T tµtPtF exp1)()(

1( )

( )1 ( )

kT

T

p tt k µ µ t

P ta

Ausfallrate

Sterberate

Enderate

Einfluss von k ?

kk

T tµtµµktptf

exp)()(1

Ausfallrate (Weibull-Verteilung)

t

r Badewannenkurve

Früh-

ausfälle Normalbereich Alterung

k = 1

k > 1 k < 1




Eigenschaften der Weibull-Verteilung

0 0.5 1 1.5 2 2.50

0.5

1

1.5

2

2.5

3Wahrscheinlichkeitsdichte - Weibull

x / xc

p(x

)

0 2 4 6 8 1010

-3

10-2

10-1

100Komplementäre Wahrscheinlichkeitsverteilung - Weibull

x / xc

1 -

P(x

)

0 0.5 1 1.5 2 2.50

0.2

0.4

0.6

0.8

1Wahrscheinlichkeitsverteilung - Weibull

x / xc

F(x

)

Charakteristischer Wert xc = 1 / µ

Wahrscheinlichkeitsfunktion:

F(x) = 1 – exp(–(x/xc)k )

Erwartungswert / „Mittelwert“

E(x) = xc G( 1 + 1/k)

Standard-Abweichung

(x) = xc ( G( 1 + 2/k) m – G2( 1 + 1/k) )½

Form-

Parameter

k = 0,5

k = 1

k = 2

k = 4

k = 8









Literatur





• B. Bertsche, G. Lechner: Zuverlässigkeit im Fahrzeug- und Maschinenbau, Springer/VDI, 2004

• B. Bertsche, u.a.: Zuverlässigkeit mechatronischer Systeme, Springer/VDI, 2009




System aus seriell geschalteten Teilen

1 2( ) ( ) ( ) ... ( )nR t R t R t R t

1 21 2

1 2

( )( ) ( )( )( ) ... ( ) ( ) ... ( )

( ) ( ) ( ) ( )

nn

n

f tf t f tf tt t t t

R t R t R t R ta a a a

1 2

1 1.

... n

MTBF bzw MTTFa a a a

1 2 ... nV V V V

Ausfall irgendeines Teilsystems Ausfall des Gesamtsystems

Gesamte Zuverlässigkeit R

Gesamte Verfügbarkeit V

Gesamt-Ausfallrate

Mean Time

To/Before Failure

1 2min , ,... , nT T T T

Ausfallzeit des Gesamt-Systems (mit Reparatur)




System aus parallel geschalteten Teilen

Ausfall des Gesamt-Systems nur, wenn alle Teilsysteme ausfallen (Redundanz)

Zuschalten der Redundanz erst bei Ausfall

1 2 ... nT T T T

1 2

1 2

1 2

1 1 ...

1 (1 ) (1 ) ... (1 )

...

n

n

n

V U U U U

V V V

V V V

1 2

1 2

( ) 1 (1 ( )) (1 ( )) ... (1 ( ))

( ) ( ) ... ( )

n

n

R t R t R t R t

R t R t R t



Ausfallzeit des Gesamt-Systems (mit Reparatur)

1 2 ... nMTTF MTTF MTTF MTTF





Ausfall des Gesamt-Systems nur, wenn alle Teilsysteme ausfallen (Redundanz)

1 2

1 2

( ) 1 (1 ( )) (1 ( )) ... (1 ( ))

( ) ( ) ... ( )

n

n

R t R t R t R t

R t R t R t

1 2max( , ,... , )nT T T T

1 2

1 2

1 2

1 1 ...

1 (1 ) (1 ) ... (1 )

...

n

n

n

V U U U U

V V V

V V V



Ausfallzeit des Gesamt-Systems (ohne Reparatur, alle Teilsysteme von Anfang an)

1

1 1: 1 ...

2gleiche Komponenten MTTF E T MTTF

n





k von n Teilsystemen müssen funktionsfähig für Gesamtfunktionsfähigkeit sein

???

Wie groß ist die Wahrscheinlichkeit bei

einer Stichprobe von n Bauelementen

k defekte zu finden?

, ( ) (1 ) , 0,1,2,...,k n k

n p

nb k p p k n

k




Parallel- und Serienschaltung

A B

H C

G D

F E

A B

H C

G D

F E

Beispiel: Richtfunk-Kommunikation

VA = 99,9 %




Übungen zu Ausfallzeiten

Betrachten Sie 4 Bauelemente mit exponential-verteilen Ausfallzeiten Ti, i = 1,.., 4,

mit einer Rate von 1000 FIT. Bestimmen Sie durch Simulation die Verteilungen

(Histogramme) der Ausfallzeiten für folgende 4 Fälle:

a) Serieller Betrieb

b) Paralleler Betrieb (heiße Reserve)

c) Paralleler Betrieb (kalte Reserve)

d) Nur ein Bauelement als Vergleich

Berechnen Sie zu allen Fällen auch Mittelwert und Standardabweichung und stellen

Sie diese Werte tabellarisch zusammen!









4.3.1 Grundlegende Begriffe und Bezeichnungen

4.3.2 Punktschätzungen von Parametern (bei bekannter Verteilung)

4.3.3 Intervallschätzung – Vertrauensintervall

4.3.4 Anpassung und Test von Verteilungen




4.3.1 Grundlegende Begriffe und Bezeichnungen

N: Anzahl der gleichartigen Objekte (Bauelemente) in einer Gesamtheit

X, T: Zufallsvariablen, die die Eigenschaften der Objekte charakterisieren

n: Anzahl der repräsentativ/zufällig ausgewählten Objekte in einer Stichprobe

n < N (meistens sogar n << N, im Folgenden vorausgesetzt mit n > 30)

x1, …xn: Werte der Zufallsvariablen X in der Stichprobe (oder auch t1, …tn)

k: Anzahl der defekten Objekte in der Stichprobe

Schätzer: Vorschrift (Funktion), um aus der Stichprobe einen Parameter der Gesamtheit

zu erhalten (z.B. Mittelwert als Schätzer für Erwartungswert)

Index S: Wert des Schätzers S für die Stichprobe wird mit dem Index S bezeichnet

a, b: Irrtumswahrscheinlichkeiten (bei der Schätzung)




Kriterien für Schätzfunktionen

Erwartungswerttreue:

Erwartungswert der Schätzfunktion = Wert des zu schätzenden Parameters

Effizienz: möglichst kleine Varianz

Konsistenz:

Für sehr große n strebt die Wahrscheinl. vom Parameterwert abzuweichen gegen Null.

Suffizienz:

Schätzer berücksichtigt alle Informationen aus der Stichprobe.




4.3.2 Parameter-Schätzung

a) über Mittelwert und Standardabweichung

( )Sµ mean X

1 2 3

1( ...)SMTTF t t t

n

n zufällige Stichproben einer Zufallsvariablen X: x1, x2, .. , xn

Schätzwerte für Erwartungswert (Mittelwert) µ und Standardabweichung

Beispiel – Normal-Verteilung:

( ) exp( )f t ta a

( ) (1 1/ ) ( ) ( 30)S std X n std X n

2

22

1 ( )( ) exp

22

x µf t

, ( ) (1 ) , 0,1,2,...,k n k

n p

nb k p p k n

k

Beispiel – Exponential-Verteilung: 1

S

SMTTFa

Beispiel – Binomial-Verteilung:

S

kp

nFehler-Wahrscheinlichkeit (bei k Fehlern)




Parameter-Schätzung über Mittelwert und Standardabw.

F(x) = 1 – exp(–(x/xc)k )

Erwartungswert:

µ = E(X) = xc G( 1 + 1/k)

Standardabweichung:

(x) = xc ( G( 1 + 2/k) – G2( 1 + 1/k) )½

G(1 + n) = n!

0.5 1 1.5 2 2.5 3 3.5 40

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Formparameter k


weichungStandardab

MittelwertC

cxWert charakt.

Mittelwert

Beispiel: Weibull-Verteilung

Gesucht: Charakt. Wert xc

Formparameter k

Gamma-Funktion


Standardabweichung

Mittelwert C =

C = 0,4

k = 2,7

xc = MW / 0,9

Nicht explicit nach k auflösbar!!!




4.3.2 b) Maximum-Likelihood-Schätzung

1 2 3 1 2 3( , , ,...; ) ( ; ) ( ; ) ( ; ) ...Gf x x x f x f x f xl l l l

1 2 3 1 2 3( ) ln ( , , ,...; ) ln ( ; ) ln ( ; ) ln ( ; ) ...GL f x x x f x f x f xl l l l l

1 2 3( ) ln( ) ( ...)L n t t ta a a 1 2 3

1 1( ...)S

S

MTTF t t tna

Zufallsvariable X mit Parameter-abhängiger W-Dichte f(x; l) u. Messwerten x1, x2, .. , xn

unabhängige Messungen Gesamtwahrscheinlichkeitsdichte als Produkt

Maximum-Likelihood: Bestimme Schätzwert lS so, dass fG maximal wird.

Beim Logarithmieren ändert sich die Lage des Maximums nicht Logarithmieren

( ) 0S

Ll

l

Maximum:

Beispiel – Exponential-Verteilung: ( ) exp( )f t ta a

( ) 0S

La

a




Maximum-Likelihood-Schätzung (Pareto-Verteilung)

1 2 3 1 2 3( ) ln ( , , ,...; ) ln ( ; ) ln ( ; ) ln ( ; ) ...GL f x x x f x f x f xl l l l l

Maximum-Likelihood: Bestimme Schätzwert lS so, dass fG maximal wird.

Beim Logarithmieren ändert sich die Lage des Maximums nicht Logarithmieren

( ) 0S

Ll

l

Maximum:

Beispiel – Pareto-Verteilung: minmin( ) 1 ,

kx

F x x xx

min( )

kxk

f xx x

min min 1( , ) ln( ) ln( ) ( 1) ln( ) ... ln( )nL k x n k n k x k x x

min min 10 ( , ) ln( ) ln( ) ... ln( )s n

s

L nk x n x x x

k k

1

1 min minln( / ) ... ln( / ) /s nk x x x x n

min 1min( ,..., )nx x x




4.3.3 Intervallschätzung – Vertrauensintervall

Im vorherigen Abschnitt: Schätzung wichtiger Parameter einer als bekannt voraus-

gesetzten Verteilung.

- Erwartungswert E{X} als Mittelwert

- Standardabweichung

In diesem Abschnitt: Genauigkeit der Schätzung (des Erwartungswert)

- Vertrauensintervall

- zu einer statistischen Sicherheit 1 – a

- Irrtumswahrscheinlichkeit a (typischerweise a = 0,05)

Berechnung mit Hilfe der Standardabweichung und des zentralen Grenzwertsatzes

x

,E X x x x x D D




Der zentrale Grenzwertsatz (s. Skript, Kap. 2.8)

Praktische Anwendung: in den allermeisten Fällen gilt für n > 30 in guter Näherung

Der Mittelwert der n Zufallsvariablen ist Gauß-verteilt 1 2( ... ) /nX X X X n

mit Mittelwert: 1 1µ E X E X µ

und Standardabweichung: 1

n

„am Mittelwert ändert sich nichts“

„Standardabweichung fällt mit

Wurzel aus n ab“

i

i

n n

n

n n

i i

1




Summe von Zufallszahlen mit gleicher Verteilung (1)

-4 -3 -2 -1 0 1 2 3 40

0.5

1

1.5

2x 10

4 1

summe

Häufigkeit

-4 -3 -2 -1 0 1 2 3 40

0.5

1

1.5

2x 10

4 2

summe

Häufigkeit

-4 -3 -2 -1 0 1 2 3 40

0.5

1

1.5

2x 10

4 4

summe

Häufigkeit

-4 -3 -2 -1 0 1 2 3 40

0.5

1

1.5

2x 10

4 16

summe

Häufigkeit

1XS 21 XXS

4321 XXXXS 161521 ... XXXXS

Gleich-

verteilung

Dreieck

als

Faltung

Gauß-ähnlich

12/11 12 2

14 4

116 16




0 1 2 3 4 5 60

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Normal-Verteilung und ihre Quantile

50 %:

±0,67

95 %: ±1,96

90 %: ±1,64

68 %: ±1,00

99 %: ±2,58

µ

F(t

) b

zw. f

(t)

+ - ,x x x x D D

( )( / 2)

std Xx q

naD

Vertrauensintervall

für den Mittelwert bei einer

Stichprobe von n (n > 30)

Werten bei einer statistischen

Sicherheit von 1 – a

( )std X

Xn

Standardabweichung des

Mittelwerts

q (0,1 / 2)




Hypothesen-Test

H0 liegt vor H0 liegt nicht vor

Annahme von H0 Entscheidung richtig Fehler 2. Art (b-Fehler)

Irrtumswahrsch. b

Verwerfung von H0 Fehler 1. Art (a-Fehler)

Irrtumswahrsch. a

Entscheidung richtig

Null-Hypothese H0: Die Hypothese, von der erst einmal ausgegangen wird.

Test durch Vergleich eines aus einer Stichprobe ermittelten Wertes mit Schwellwert.

Annahme oder Verwerfung

Alternativ-Hypothese H1: Die Hypothese, von der bei Verwerfung von

H0 ausgegangen wird.




Operationscharakteristik für Zuverlässigkeitstest

0 1 2 3 4 5 6 0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Qualitätsmaß

Wahrs

chein

lichkeit

Abnehmer-

Risiko b

Hersteller-

Risiko a

RQL AQL RQL: Rejectable Quality Level

ACL: Acceptable Quality Level

a Operationscharakteristik OC

Wie groß ist die Wahrscheinlichkeit, dass in der Gesamtheit der Mittelwert µN kleiner

als der Wert der x-Achse ist, wenn in der Stichprobe der Mittelwert µn gemessen wurde?

Null-Hypothese

H0

Alternativ-

Hypothese

H1




Operationscharakteristik für Zuverlässigkeitstest

0 1 2 3 4 5 6 0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Qualitätsmaß

Wahrs

chein

lichkeit

Abnehmer-

Risiko b

Hersteller-

Risiko a

RQL AQL RQL: Rejectable Quality Level

ACL: Acceptable Quality Level

Operationscharakteristik OC

Wie groß ist die Wahrscheinlichkeit, dass in der Gesamtheit der Mittelwert µN kleiner

als der Wert der x-Achse ist, wenn in der Stichprobe der Mittelwert µn gemessen wurde?

4-fache

Stichprobe




4.3.4 Anpassung und Test von Verteilung

Welche Verteilung passt am Besten zu einer Zufallsvariablen X

Messwerten x1, x2, .. , xn ? Und wie kann man das testen?

Optische Test: Auftragungen

• der Häufigkeitsverteilung der Messwerte

• der zugehörigen kumulierten und normierten Häufigkeitsverteilung

• der zugehörigen komplementären Häufigkeitsverteilung

Besondere Auftragungsarten

• Logarithmische Auftragung auf der y-Achse: Exponential-Verteilung Gerade (Abb. 30 im Skript)

• Logarithmische Auftragung auf beiden Achsen: Pareto-Verteilung Gerade

• Logarithm. Auftragung auf x-Achse, doppelt log. auf y-Achse: Weibull-Verteilung Gerade

• P-P-Plot und Q-Q-Plot (s.u.)

Ausprobieren mehrerer Verteilungen und statistische Tests (s.u.)




0 0.2 0.4 0.6 0.8 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Pt

Pe

P-P-Plot

Pt

Pe

P-P-Plot

0 0.5 1 1.5 2 2.5 3 3.5 40

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0 0.5 1 1.5 2 2.5 30

0.5

1

1.5

2

2.5

3

Qe

Qt

Q-Q-Plot

Q-Q-Plot Q: Quantil

Qt

Qe

Zeit t

F(t

) =

P

(T ≤

t)

Optische Analyse von experimentell

ermittelten Verteilungen am Beispiel

der Exponential-Verteilung

theoretisch

experimentell




Beispiel: Einwohner-Zahlen von Städten in Deutschland

x = Einwohnerzahl x = Einwohnerzahl

PX(X ≤ x) = F(x) (CDF)

PX(X > x) = 1 – F(x) (IDF)

Wah

rsch

ein

lich

kei

t P

Wah

rsch

ein

lich

kei

t P

W

ahrs

chei

nli

chk

eit

P

minmin( ) 1 ,

kx

F x x xx

minmin1 ( ) ,

kx

F x x xx

Hypothese: Pareto-Verteilung

Daten-Quelle: www.wikipedia.org

Liste der Groß- und Mittelstädte in Deutschland




Pareto-Verteilung

minmin( ) ( ) 1 für

k

X

xF x P x x x

x

100

101

102

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1Wahrscheinlichkeitsverteilung - Pareto

x

P(x

)

100

101

102

10-4

10-3

10-2

10-1

100

101

Wahrscheinlichkeitsdichte - Pareto

x

p(x

)

xmin = 1

k = 4 3 2 1 0.5

k

0.5

1

2

3 k = 4

k > 0: Form-Parameter

xmin > 0: Minimal-Wert

min1

kE X x

k

min

1 2

x kX

k k

min( )

kxk

f xx x

xmin = 1




Passt eine theoretische Verteilung zu einer empirischen?

A) Optischer Test: Verteilungen oder komplementäre Verteilungen

auftragen (eventuell logarithmisch)

Beispiel: Verteilung von Email-Längen (Zwei Modelle)

0,0100

0,1000

1,0000

1 10 100 1000 10000

ko

mp

lem

entä

re V

erte

ilu

ng

: 1

- F

e(x

)

Email-Größe / kByte

347,06,1

1)(

x

kBytexXPth

398,06,2

1)(

x

kBytexXPth

0,0000

0,2000

0,4000

0,6000

0,8000

1,0000

0 1000 2000 3000 4000 5000

ko

mp

lem

entä

re V

erte

ilu

ng

: 1

- F

e(x

)

Email-Größe / kByte





B) Optischer Test: P-P-Plot

-0,2000

0,0000

0,2000

0,4000

0,6000

0,8000

1,0000

0,0000 0,2000 0,4000 0,6000 0,8000 1,0000

0,0000

0,2000

0,4000

0,6000

0,8000

1,0000

0,0000 0,2000 0,4000 0,6000 0,8000 1,0000

347,06,1

1)(

x

kBytexXPth398,0

6,21)(

x

kBytexXPth

)( xXPe

)( xXPe

Pth

(X ≤

x)

Pth

(X ≤

x)

x = 1,5 kB

x = 5 kB

x = 10 kB

x = 50 kB

x = 1,5 kB

x = 5 kB

x = 10 kB

x = 50 kB





1,0

10,0

100,0

1000,0

10000,0

1,0 10,0 100,0 1000,0 10000,0


C) Optischer Test: Q-Q-Plot (Quantile)

347,06,1

1)(

x

kBytexFth

Theo

reti

sches

Quan

til

(Per

zenti

l)

x = 1,5 kB

x = 5 kB

x = 10 kB

x = 50 kB


Empirisches Quantil (Perzentil)

Email-

Größe x /

kByte He(X ≤x) Pe(X ≤x)

1,5 0 0,0000

5 1094 0,2250

10 2083 0,4283

20 2636 0,5421

50 3239 0,6660

100 3563 0,7327

200 3863 0,7944

500 4199 0,8635

1000 4407 0,9062

2000 4615 0,9490

5000 4771 0,9811

10000 4830 0,9932

20000 4860 0,9994




0 0


Quantitativ: Kolmogorow-Smirnow-Test

x1 x2 x3 x4 x5 x6 x7 x8 xk

)()( nthnen xPxPd

)()(~

1 nthnen xPxPd

P(x)

x

geordnete Zufallszahlen …

Pth(x)

Pe(x)

)(0)()(: nxPxPIdee the

Pe(x2) n

ddTest kk

)2/ln(5,0~,max:

a

Null-Hypothese: Pth passt zu Pe

Verwerfe Null-Hypothese mit

Irrtumswahrscheinlichkeit a:




101

102

103

104

10-3

10-2

10-1

100

n

Verw

erf

ungsgre

nze

Verwerfungsgrenzen für den Kolmogorow-Smirnow-Test

für verschiedene Werte der Irrtumswahrscheinlichkeit a

1% 5%

10%

50%

90%

95%

y = 336436x-1,289

R² = 0,9968

0,0010

0,0100

0,1000

1,0000

10.000 100.000 1.000.000 10.000.000

P(X

> x

) x = Einwohnerzahl

Maximale Abweichung 0,037

bei n = 690 Städten

Bsp: Verteilung von EW in Städten





Quantitativ: chi2-Test (c2-Test)

2

)1,1(

1 ,

2

,,

M

M

m mth

mthme

h

hhac

Idee: Abweichung von empirischen Häufigkeiten und theoretischen geht gegen Null

Vorgehen:

• Es liegen N Stichproben einer Zufallsvariablen X vor.

• Teile Wertebereich der Zufallsvariable X in M disjunkte Intervalle: I1, I2, … IM

• Es sollten mindestens 5 Stichproben in jedem Intervall liegen.

• Ermittle empirische Häufigkeiten he,m für alle Im

• Ermittle theoretischen Häufigkeiten

hth,m = N Pth(X Im) für alle Im

0

50

100

150

200

250

300

0 50 100 150 200

Ver

wer

fun

gsg

ren

ze

Anzahl Intervalle M

0,1 0,05 0,01 0,001

Verwerfe mit

Irrtumswahr. a,

wenn




Übungen zur Parameter- und Verteilungsschätzung

Analysiert werden sollen die Verteilungen von Windgeschwindigkeiten an 3 Standorten

(eine auswählen, Quelle: DWD). Diese sind in Excel-Dateien gespeichert. Häufig wird

für Windgeschwindigkeiten eine Weibull-Verteilung angenommen. Dies ist zu testen!

a) Lesen Sie die Excel-Datei ein und erstellen Sie ein Histogramm.

b) Berechnen Sie Mittelwert, Median, Standardabweichung, Variationskoeffizient.

c) Schätzen Sie daraus die Parameter der zugehörigen Weibull-Verteilung (Folie!)!

d) Fertigen Sie einen Plot mit der theoretischen und gemessenen Wahrscheinlich-

keitsverteilung an! Passen Sie gut zusammen!

e) Analysieren Sie die Messdaten mit dem Matlab DistributionFitter-Tool!

f) Welche Parameter erhalten Sie jetzt für die Hypothese Weilbull-Verteilung?

g) Versuchen Sie es mit einer alternativen Hypothese (andere Verteilung)!




Modellierung und

Simulation 1

Prof. Dr. Henrik Schulze, Prof. Dr. Christian Lüders

Fachhochschule Südwestfalen

Standort Meschede

Fachbereich Ingenieur- und Wirtschaftswissenschaften

Tel.: 0291 / 99 10 -4300 | -4261

E-Mail: schulze.henrik | [email protected]

Kap. 4: Zuverlässigkeit und Verfügbarkeit






5.1 Begriffe und Beispiele

5.2 Markov-Ketten (zeit-diskret)

5.3 Markov-Prozesse (zeit-kontinuierlich)

5.4 Ereignisorientierte Simulation

Literatur





• U. Hedtstück: Simulation diskreter Prozesse, Springer – Vieweg, 2013

• K.-H. Waldmann, W.E. Helm, Simulation stochastischer Syteme, Springer Gabler, 2016

• M. Harchol-Balter: Perfomance Modelling and Design of Computer Systems, Cambridge UP, 2013




5.1 Bediensysteme: Begriffe und Beispiele

Quellen

Sources Warteschlange

Queue

Bedieneinheit

Server

Senke

Sink

Zeit

zufällige Startzeiten

zufällige Bedienzeiten




Bediensysteme – Typische Fragen

1. Welcher Anteil der Anforderungen wurde erfolgreich bedient?

2. Wie groß war die gesamte Bedienzeit? (im Mittel, in 90% der Fälle)

3. Wie groß war die Wartezeit? (im Mittel, in 90% der Fälle)

4. Wie viele Server werden benötigt?

5. Wie viele Warteplätze werden benötigt?

6. Was ist die geeignete Abfertigungsmethode? (FIFO, Priorität)

7. Lassen sich die einzelnen Prozesse besser anordnen? (parallel)

8. Wie lässt sich die „Kundenzufriedenheit“ steigern?

9. Wie stark sind die einzelnen Server ausgelastet?

10. …




Bediensysteme - Beispiele

1. Postschalter

2. Funkkanalzuteilung

3. Zugriffe auf ein BUS-System

4. Dimensionierung & Abfertigungsstrategien bei Routern

5. Dimensionierung von Servern

6. Lagerhaltung, Bestückung von Automaten

7. Geschäftsprozesse

8. Produktionsprozesse

9. …




R, tX t

Menge „gleichartiger“ Zufallsvariablen, die i.Allg. abhängig voneinander sind

Index wird vielfach als Zeit t (diskretisierte Zeit n) interpretiert

Wertebereich der Zufallsvariablen: Zustandsraum

0N, nX ndiskret: kontinuierlich

Markov-Kette Markov-Prozess

Spezialfall:

• Zustandsraum diskret

• Gedächtnislosigkeit

• Memoryless (M)

Stochastischer Prozess




Beispiele für stochastische Prozesse 1. Anzahl der Sonnenstunden in Meschede am Tag n im Jahr

2. Globale Durchschnittstemparatur im Jahr n

3. Tabellenplatz von Schalke 04 am Spieltag n

4. Position des Fußballs im Spiel zur Zeit t

5. Buchstabe in einem Text an Position n

6. Windgeschwindigkeit an einem Standort zur Zeit t

7. Anzahl laufender Telefonate in einer Funkzelle zur Zeit t

8. Anzahl von insgesamt abgewickelter Telefonate am Tag n

9. Anzahl der Zugriffe auf einen Server

10. Aufgerufene Internetseite in einer Session nach Klick n

11. Bestand eines bestimmten Bauteils in einem Lager am Tag n

12. Zustand (defekt, intakt) eines Bauteils zur Zeit t




4.2 Markov-Ketten




)(

)|(BP

BAPBAP


)(

)(

)(

)()|( AP

BP

BPAP

BP

BAPBAP




1 2 3 4 5 6

1 2 3 4 5 6 7

2 3 4 5 6 7 8

3 4 5 6 7 8 9

4 5 6 7 8 9 10

5 6 7 8 9 10 11

6 7 8 9 10 11 12

Bsp: Würfeln mit 2 Würfeln

A: Augenzahlsumme 7

12/736/21)( AP

B: erster Würfel zeigt 6

6/1

6/1

)()|(

BP

BAPBAP

B: erster Würfel gerade

3

2

2/1

36/12

)()|(

BP

BAPBAP




A

)(

)|(BP

BAPBAP


)(

)(

)(

)()|( AP

BP

BPAP

BP

BAPBAP



)()|( BPBAPBAP

i

ii

i

i BPBAPBAPAP )()|(

B1 B2 B3

B4 B5 B6

B7 B8 B9


Zerlegung von B in disjunkte Teil-Mengen Bi

P(Bi A)

Übergangswahrscheinlichkeiten




Diskreter stochastischer Prozess mit diskretem Zustandsraum und folgender Eigenschaft

für die bedingten Wahrscheinlichkeiten:

)|(),,...,,( 1100112211 nnnnnnnnnn jXjXPjXjXjXjXjXP

Nur der unmittelbar vorhergehende Zustand spielt eine Rolle, nicht die Vorgeschichte.

Übergangswahrscheinlichkeiten von Zustand i j: pi j

)|()( 1 iXjXPnp nnji

Homogene Kette: Übergangswahrscheinlichkeiten unabhängig von n: pi j

1 2 k 0

10p 21p 32p 1, kkp

1,1kp32p21p10p

00p

Definition einer Markov-Kette

Übergangsgraph

für die Zustände 0, 1, 2, … k, k+1, …




Die Übergangswahrscheinlichkeiten erlauben es, die Wahrscheinlichkeit für den

Zustand j zur Zeit n iterativ zu berechnen:

Zustandswahrscheinlichkeiten zur Zeit n als Zeilenvektor:

Iterative Berechnung der Zustandswahrscheinlichkeiten:

)()()()( 11 iPpiXPpjXPjP n

i

jin

i

jinn

............

...

...

...

222120

121110

020100

ppp

ppp

ppp

TP

...),2(),1(),0( nnnn PPPP

Tnn PP P 1

n

Tn PP P 0

Übergangswahrscheinlichkeiten als Elemente der

Übergangs-Matrix (Transission T):

Stationärer Zustand: Tstst PP P Eigenvektor der Übergangsmatrix z. Eigenwert 1

Wann existiert ein stationärer Zustand? Wann gilt: ? n

Tn

st PP P

0lim

Zeilensumme = ? Warum?

Markov-Kette: Übergangsmatrix u. stationärer Zustand

)|( 1 iXjXPp nnji




Beispiel 1: System mit Ausfall und Reparatur

Ausfallrate, MTBF, MTTR, …

Mittlere Lebensdauer – Mean Time to Failure (MTTF)

Bei Reparatur: Mean Time Before Failure (MTBF)

Verfügbarkeit V: Wahrscheinlichkeit, dass funktionsfähig

( )MTTF E T t f t dt

MTBFV

MTBF MTTR

a(t): Anteil der Bauelemente, die pro Zeitintervall Dt ausfallen, unter denen,

die bis zur Zeit t überlebt haben

0

1µ tµ t e dtµ

a(t) = µ

Bei einer Exponential-Verteilung ist die Ausfallrate konstant (a = µ) und hängt nicht





Ausfallwahrscheinlichkeit in Zeit Dt: a = a Dt für Dt << MTBF




Beispiel 1: System mit Ausfall und Reparatur

1 0

r

a 1-a 1-r

rr

aapppp

1

1),(),( 1010

rpapp 100 )1( aprpp 011 )1(

rpap 100 aprp 010

Gerät in

Ordnung

Gerät

defekt

Stationärer Zustand

in Matrix-Form

Wahrscheinlichkeit

• für Ausfall an Tag n: a

• für Reparatur an Tag n: r Gleichgewicht

bei 0

GGW

bei 1

p0 a = p1 r Gleichgewicht auf Link

B.1: MATLAB-Übung

[V, D] = eig(A)

D: Diagonalmatrix mit Eigenwerten von A

V: Matrix mit Eigenvektoren von A

als Spalten

Normierung des 1. Eigenvektors (Warum?)

VN = V(:, 1) / sum( V(:, 1) )

• Berechne: Eigenvektor

• Berechne: PT^n, n = 1, 2, 4, 8, …

• Plot: n erste Zeile von PT^n

• Interpretation der Ergebnisse

01 pr

ap

00101 pr

appp

ra

rp

0

ra

ap

1

Normierung:

Ergebnis:

Vergleich für 2 Parametersätze




Beispiel 2: Erweiterte Systeme mit Reparatur

1 0

r1

a1

1- a1 – a2

3 2

1 0

r

a 1-a

Gerät in

Ordnung

Gerät

defekt

2

1 - r

l

1 - l

Nicht

reparabel

a2 r2

Wahrscheinlichkeit

• für Ausfall an Tag n: a

• für Reparatur an Tag n: r

• für Neubeschaffung am Tag n: l

r1

a1

a2 r2

1- r1 – a2

1- r1 – r2 1- a1 – r2

Ausfallwahrscheinlichkeit

• falls beide Teile erforderlich: 1 – p0

• falls Teile redundant sind: p3

Ausfall eines Geräts aus zwei Teilen Nicht-reparabler Defekt




Bediensystem mit einem Server und Warteschlange

• Diskreter, konstanter Zeittakt Dt

• unbegrenzte Warteplätze

• Zustand:

• Anzahl Kunden k im System

• Neuankunft Kunde: pa = l Dt

• Bedienzeit-Ende: pe = µ Dt

• Last: a = l / m < 1

1 Server, 1 Warteplatz

1 2 0

m m m

3

m

l l l l

1lm 1lm 1lm

1l

l pk = µ pk+1 a pk = pk+1

pk = ak p0 p0 = 1 – a

1 2 0

m m

l l

1lm

1l 1m

Mittlere Kundenzahl im System: E{K} = a/(1 – a)

B.2 MATLAB-Übung

• Übergangsmatrix PT aufstellen

• Eigenwerte / -vektoren berechnen

• PT^n berechnen

• Wartewahrscheinlichkeit?

• Serverauslastung?

• Mittlere Kundenzahl




Weitere Beispiele für Markov-Ketten

0 1

q

p

3 2

p

q

q q p p

01 11

00 10

21

20

02 12 22

0

3 4

0,5

0,5

1 2 0,5

0,5

0,75

0,25

0,5 0,5

0,5 0,5

B.4 MATLAB-Übung

• Erzeuge PT

• Berechne: PT^n,

• n = 50, 51, 52, 53

• Was fällt auf?

• Woran liegt das?

• ….

Zweidimensionaler Prozess

„Random Walk“

Überlegung

• Was geschieht langfristig?

• Pn im stationärem Zustand?

• ….




Internet-Suche als Markov-Kette

Einfaches Beispiel mit 5 verlinkten Seiten

5

2 4

3

1

p1j = (0, ¼, ¼ , ¼, ¼)

p2j = (½ , 0, 0 , ½, 0)

p3j = (0, 0, 0 , 1, 0)

p4j = (0, 1, 0 , 0, 0)

p5j = (1/3 ,1/3, 0 ,1/3, 0)

Übergangswahrscheinlichkeiten

aus dem Zustand i heraus: 1/L

L: Anzahl der Links

Wie sieht die stationäre Verteilung aus?

Ranking der Seiten nach

Wahrscheinlichkeit (stationär)

B.5a: MATLAB-Übung

• Übergangsmatrix PT einlesen

• liegt als Excel-Tabelle vor

• PT = xlsread(`www5.xlsx´)

• PT^n berechnen




Internet-Suche als Markov-Kette

Einfaches Beispiel mit 6 verlinkten Seiten

5

2 4

3

1

p1j = (1- a) p1j + a / N

Problem?

6 Absorbierende

Zustände

Prozess läuft irgendwann in die

absorbierenden Zustände 3 und 6

und kehrt nicht mehr zurück

Lösung?

„Steuersatz“ a bei allen Zuständen

Link p34 gestrichen

Jetzt: immer ein Link zurück

B.5b: MATLAB-Übung

• Übergangsmatrix PT einlesen

• PT = xlsread(`www6.xlsx´)

• PT^n berechnen

• Mit Steuersatz modifizieren




Für eine (positiv) rekurrente, aperiodische und irreduzible Markov-Kette gilt:

- Der folgende Grenzwert für die Übergangsmatrix existiert:

)(/1 kPstk t

- Es existiert ein eindeutiger stationärer Zustand (Eigenvektor): Tstst PP P

Wichtige Ergebnisse für Markov-Ketten

n

Tn

T PP

lim

- Alle Zeilen von sind identisch und gleich

TP stP

- Mittlere Zeit für die Rückkehr in den Zustand k:

- Das Verhalten der Markov-Kette ist ergodisch:

Erwartungswert/Ensemble-Mittel = zeitliches Mittel

k

st kPkKE )(

N

n

nN

t KN

K1

1lim

z.B. Mittlere

Kundenzahl

Gilt auch für andere Größen.




Bediensystem mit einem Server und Warteschlange

• Diskreter, konstanter Zeittakt Dt

• unbegrenzte Warteplätze

• Zustand:

• Anzahl Kunden k im System

• Neuankunft Kunde: pa = l Dt

• Bedienzeit-Ende: pe = µ Dt

• Last: a = l / m < 1

1 Server, 1 Warteplatz

1 2 0

m m m

3

m

l l l l

1lm 1lm 1lm

1l

l pk = µ pk+1 a pk = pk+1

pk = ak p0 p0 = 1 – a

1 2 0

m m

l l

1lm

1l 1m

Mittlere Kundenzahl im System: E{K} = a/(1 – a)

B.2 MATLAB-Übung

• Übergangsmatrix PT aufstellen

• Eigenwerte / -vektoren berechnen

• PT^n berechnen

• Wartewahrscheinlichkeit?

• Serverauslastung?

• Mittlere Kundenzahl




Explizite Simulation einer Markov-Kette (Bsp. M/M/1) nmax = 100000; % Maximale Laufzeit

lambda = 0.06; % Erzeugungswahrscheinlichkeit

mu = 0.1; % Ende-Wahrscheinlichkeit

a = lambda/mu; % Last

k = 0; % aktuelle Zahl: Kunden im System

K = zeros(1, nmax); % speichert Kunden in jedem Zeitschritt

N = 0; % aktuelle Anzahl erzeugter Kundenwünsche

for n = 1:nmax, % Schleife über Zeitschritte

if(rand(1,1) < lambda + mu), % Änderung der Kundenzahl

% mit p = lambda + mu

if( rand(1, 1) > a /(1 + a) ) % Verringerung Kundenzahl (Ende)

k = max(0, k - 1);

else % Erhöhung der Kundenzahl

k = k + 1;

end

end

K(n) = k; % Füge aktuelle Kundenzahl zu

end % Kundenzahlvektor hinzu

Statistische Auswertung, Diagramme




Zeitlicher Verlauf der Kundenzahl und Histogramm

der Zustandswahrscheinlichkeiten für M/M/1-System

0 500 1000 1500 20000

1

2

3

4

5

6Kundenzahl im System als Funktion der Zeit

Zeitschritt

Kundenzahl im

Syste

m

0 2 4 6 8 100

0.5

1

1.5

2

2.5

3

3.5

4x 10

4 Histogramm der Kundenzahl im System

Kundenzahl

Häufigkeit

Parameter wie auf vorheriger Folie

zeitlicher

Mittelwert




Aufg. B.3: Simulationsaufgaben zur Markov-Kette (M/M/1)

• Wie groß muss man nmax wählen, um ca. 20000 Ankünfte zu simulieren?

• Ergänzen Sie das Simulationsprogramm diskretMM1 um

– die Ausgabe der tatsächlichen Ankünfte

– ein Diagramm zum zeitlichen Verlauf der Kundenzahl sowie mit dem Histogramm

– die Ausgabe des Ensemble-Mittelwerts E{K} und des zeitlichen Mittelwerts der Kundenzahl

• Simulieren Sie das System für zwei verschiedene Werte der Last und vergleichen

Sie die Ergebnisse mit den Werten für die Formeln zum stationären Zustand.

• Simulieren Sie das System zweimal mit der Last a = 1! Was stellen Sie fest?

• Ergänzen Sie das Programm um die Möglichkeit des Abweisens (Blockierung B)

eines Kundenwunsches bei einer endlichen Warteschlangenlänge (z.B. nur 1 Platz)!

• Bauen Sie einen Zähler für die Anzahl von Blockierungen ein und geben Sie die die

Blockierwahrscheinlichkeit aus.

• Simulieren Sie das System für zwei verschiedene Werte der Last und vergleichen

Sie die Ergebnisse mit den Werten für die Formeln zum stationären Zustand.




4.3 Markov-Prozesse

(und ähnliche Prozesse)

- zeit-kontinuierlich




Markov-Kette (diskrete Zeitschritte)

)|(),,...,,( 1100112211 nnnnnnnnnn jXjXPjXjXjXjXjXP

Nur der unmittelbar vorhergehende Zustand spielt eine Rolle, nicht die Vorgeschichte.

Übergangswahrscheinlichkeiten von Zustand i j: )|( 1 iXjXPp nnji

Markov-Prozess und Übergangsraten (1)

)()|()( iXPiXjXPjXP t

i

ttttt DD

)(

)|()()(iXP

t

iXjXP

t

jXPjXPt

i

jitttttt D

D

DD

)()( tPtdt

dPi

i

ji

j

b

Markov-Prozess (Zeit kontinuierlich)

0Dt

)()()()( 11 iPpiXPpjXPjP n

i

jin

i

jinn 1 Zeilensumme j

jip

jjji

jii

ji PP

bb j

jzz

zji

jii

ji PP

bb

0z

zib

Übergangsraten: bij




in Zustand j

hinein

aus Zustand j

heraus

Markov-Prozess und Übergangsraten (2)

)()|()( iXPiXjXPjXP t

i

ttttt DD

)(

)|()()(iXP

t

iXjXP

t

jXPjXPt

i

jitttttt D

D

DD

dt

dPj

Übergangsraten i j : bij

0Dt

j

jzz

zji

jii

ji PP

bb

0eZeilensumm0 j

jib

„Wahrscheinlichkeitsfluss“

0: dt

dPjZustandrstationäre




)(

)|(BP

BAPBAP


)(1

)()|],[(

tP

ttpüberlebttZeitzurbistttinAusfallPP

T

Tausfall

DDD

)(1

)(lim)(

0 tP

tp

t

Pt

T

Tausfall

t

D

D

Da

z.B. Wahrscheinlichkeit, dass Bauteil bis zur Zeit t ausfällt:

Verteilung: F(t) = PT( T ≤ t), Dichte: pT(t) = f(t) = F‘(t)

Ausfallrate:


Durch Reparatur bzw. Ausfall eines Bauteils / Ende oder Beginn eines Prozesses

ändert sich der Zustand eines Systems von i auf j = i ± 1

Bestimmung der Übergangsrate:

Bedingte Wahrscheinlichkeiten u. Ausfallrate / Ende-Rate




)(1

)()(

tP

tpt

T

T

aAusfallrate:

)exp()()( tµµtptf T

Exponential-Verteilung mit Parameter µ:

Dichte:

)exp(1)()( tµtPtF T

µµt

µtµ

tP

tpt

T

T

))exp(1(1

)exp(

)(1

)()(a

Ausfallrate

Sterberate

Ende-Rate

Bei einer Exponential-Verteilung ist die Ausfallrate konstant (µ) und hängt nicht





Ausfallrate: Gedächtnislosigkeit Exponential-Verteilung




Kendall-Notation für Bediensysteme A / B / s / q / K / SD

• A: Verteilung der Zwischen-Ankunftszeiten

• M: Memoryless (Exponential) D: Deterministisch

• G: General (beliebige Verteilung) P: Pareto ….

• B: Verteilung der Bedienzeiten

• Siehe A

• s: Anzahl der Bedieneinheiten 1, 2, 3, …

• q: Anzahl der Bedieneinheiten + Warteplätze s, s+1, s+2, …,

• K: maximale Anzahl der Kunden

• K = 1, 2, 3, …,

• SD: Sevice-Disziplin

• FIFO: First In First Out LIFO: Last In Last Out

• SJF: Shortest Job First PRIO: Prioriry …

Rot: Default-Werte

können weggelassen

werden, z.B.

• M/M/1 =

• M/M/1///FIFO

• M/M/8/8 =

• M/M/8/8//FIFO




Mehrere Bedienplätze s, unbegrenzte Warteplätze: M/M/s

1 2 s 0

l l l l l l

1m 2m 3m sm sm sm

l

sm

k

l l

km k1m

Kunden im System: k

Anzahl Server: s

Ankunftsrate: l

Mittlere Bearbeitungszeit: t

Ende-Rate: µ = 1/t

Gesamtlast A = l/µ = l t

Last pro Server a = A/s

veränderlich

8

60 h-1

6 min = 0,1 h

10 h-1

60 h-1 0,1 h = 6 Erl

0,75 Erl pro Server

Parameter Zahlenbeispiel (kleines Callcenter)

Was passiert bei Lasterhöhung?

0,95 Erl pro Server

Pseudo-Einheit

Erlang (Erl)

Agner Krarup Erlang

Dän. Mathematiker u. Ingenieur




Mehrere Bedienplätze s, unbegrenzte Warteplätze: M/M/s

1 2 s 0

l l l l l l

1m 2m 3m sm sm sm

l

sm

l pk + kµ pk = l pk-1 + (k+1)µ pk+1

l pk + sµ pk = l pk-1 + s µ pk+1

kµ pk = l pk-1

l p0 = 1µ p1

sµ pk = l pk-1

1 kk pk

Ap

0!

pk

Ap

k

k

1 kk pap

0!

pas

Ap sk

s

k

k = 1, 2, …., s – 1,

k = s, s+1, ….

1

11

0

0 )1(!!

a

s

A

k

Ap

ss

k

k

k

l l

km k1m Kunden im System: k

Anzahl Server: s



Gleichgewicht bei Gleichgewicht bei

Normierung

Mittlere Länge

Warteschlange

Mittlere Anzahl

Kunden im System

02)1(!p

a

a

s

AK

s

W

WKAK




M/M/s/s-System, keine Warteplätze Verlustsystem

1 2 s 0

l l l

1m 2m 3m

l

sm

0!

pk

Ap

k

k

1

0

0!

s

k

k

k

Ap

k

l l

km k1m

Kunden im System: k

Anzahl Server: s


0!

)|( ps

ApAnkunftskPB

s

s

Gesamtlast A = l / µ

Ankunftsrate l

Serverauslastung: A (1 – B)

Eintrittsrate: le l (1 – B)

System

Zustandswahrscheinlichkeiten für s ???

Blockierwahrscheinlichkeit (Erlang-B-Formel)

10-2

10-1

100

10-1

100

101

102

Last pro Server

Blo

ckin

g B

/ %

Neuankunft

Blockierung

s = 2 4 8 16 32

s =1




Poisson-Prozess

Ak

k ek

Ap

!Wahrscheinlichkeit für k Kunden:

System ohne Begrenzungen:

Zwischenankunftszeiten exponential-verteilt, Bedienzeiten exponential-verteilt

Anzahl Kunden Kt im System zur Zeit t ist ein Poisson-Prozess

tKEµ

A l

0 5 10 150

0.1

0.2

0.3

0.4

0.5

k

pk

0 5 10 150

0.1

0.2

0.3

0.4

0.5

k

pk

0 5 10 150

0.1

0.2

0.3

0.4

0.5

k

pk

0 5 10 150

0.1

0.2

0.3

0.4

0.5

k

pk

A = 0,75 A = 1,5

A = 3 A = 6




Theorem von Little Verweilzeiten im System

T1

T2

T3

T4

T5

T6

T7

T8

Ka

Dt1 Dt2 Dt3 Dt4

11

aK

j

jT

Ke

T

<<

GFTeK

j

j

1

1

DI

i

ii tkGFFlächeGraue1

D

I

i

iiT

t tkT

KKE1

1lim

aa K

j

j

a

a

K

j

j TKT

KT

T 11

11

TE l

Ergodischer Prozess (ohne Verluste)

TEKKE t l

Mittlere Kunden-

Zahl im System

Mittlere

Verweilzeit

Ankunfts-

rate = x

t

k

QQ TEKE l

TEBKE l)1(

in der Queue

mit Blockierung:

benötigt Markov-Eigenschaft nicht!!!




Warte- & Verweilzeiten bei M/M/s über Theorem von Little

1 2 s 0

l l l l l l

1m 2m 3m sm sm sm

l

sm

1

11

0

0 )1(!!

a

s

A

k

Ap

ss

k

k

02)1(!p

a

a

s

AK

s

W

WKAK

k

l l

km k1m Kunden im System: k

Anzahl Server: s

Gesamtlast A = l / µ


Normierung

Mittlere Länge

Warteschlange

Mittlere Anzahl

Kunden im System

l/WW KT

WW T

µKAKT

1// ll

Mittlere Wartezeit Mittlere Verweildauer

Verteilung der Wartezeit Verteilung der Verweildauer

TttTP /exp1 WWW TtptTP /exp1




Jackson-Netz: Netz aus M/M/1-Systemen

µ1 µ1

µ1 µ2 µ1

µ2

µ3

µ1

µ2

µ3 l2

l1

l1

l2 l1

l3 l1 l2

l3 ql1

l2 1q)l1

l1

Last an Bedieneinheit i: ai = li / mi

1el

2el

3el

4el

43211 eeee lllll

1el

11 )1( eq ll

q

n

i

i

k

in aakkkp i

1

11 )1(),...,(Zustandswahrsch.

nges KKKK ...21Mittl. Kundenzahl:

emee

gesKT

lll ...21 Mittl. Verweilzeit:

Eintrittsraten der für externe (e) Quellen: ejl

1el1el

1el

2el




S-Bahn-Station

An einer belebten S-Bahn-Station treffen im Mittel

10 Bahnen pro Stunde ein.

Ein Fahrgast trifft zu zufälligen Zeit ein. Wie lange

muss er im Mittel auf eine Bahn warten?

0 1 2 3 t / h

0 1 2 3 t / h

18 min

Mittlere Wartezeit: 0,3 1 min + 0,7 21 min = 15 min




Pollaczek–Khinchine-Formel für M/G/1-System

2

)1( 2

,,

CTT MWGW

Mittlere

Wartedauer

Zwischenankunftszeiten: exponentialverteilt mit Rate l

Bedienzeiten T mit beliebiger Verteilung G = G(T)

• Mittelwert t

• Standardabweichung

• Variationskoeffizient C = / t

• Last a = l t

für ein beliebiges G

kein Markov-Prozess

• Index M: M/M/1-System

• Index G: M/G/1-System

2

)1( 2

,,

CKK MWGW

Mittlere Länge

Warteschlange

t WG TTMittlere

Verweilzeit

aKK GWG ,

Mittlere

Kundenzahl

Exponentialverteilung

C = ?




Bedien-Disziplinen

ohne Pre-emption mit Pre-emption

Ohne Prioritäten

First In First Out (FIFO) =

First Come First Serve (FCFS)

Last In First Out (LIFO)

Random (RAND)

Priority

Shortest Remaining

Processing Time (SRPT)

Ohne Prioritäten

Processor Sharing (PS)

= Time Div. Multiplex (TDM)

= Round Robin (RR)

Forground Background (FB)

Priority (PRIO)

• Shortest Job First (SJF)

• Job Type

• Transmission Quality

• Proportional Fair

• Nearest Deadline

Pre-emption: Vorkaufsrecht, Verdrängung

i.A. keine analytischen Formeln

Simulation




4.4 Ereignisorientierte Simulation

(von Bediensystemen)

Komplexere Systeme mit beliebigen Bedienzeit-

Verteilungen und komplexen Zuteilungsstrategien

nicht analytisch behandelbar




Ereignisorientierte Simulation

Nachteile von festen, diskreten Zeitschritten (Perioden-Orientierung) bei Zufallsprozessen

• Zeitschritt groß: mehrere „gleichzeitige“ Ereignisse in einem Zeitschlitz

• Zeitschlitz klein: in den meisten Zeitschlitzen geschieht nichts (ineffizient)

Lösung: Ereignisorientierte Simulation (Discrete Event (System) Simulation)

• Nur die Zeitpunkte werden betrachtet, an denen sich der Zustand des Systems ändert

• Ereignis: Zustandsänderung

• Abzuarbeitende Ereignisse werden in eine dynamische EventList eingetragen

• Kennzeichen eines Events: Eintrittszeitpunkt, Typ, zugeordneter Prozess (Kunde, Paket), …

• Abhängig von Typ wird zum Eintrittszeitpunkt bestimmte Routine (Funktion) abgearbeitet

• Je nach Ergebnis können neue Events erzeugt werden (zu zufälligen Zeiten)

• Abzuarbeitende Prozesse / erzeugte Pakete speichern ihren Lebenslauf

• Wann ist was passiert?




Illustration: Ereignisorientierte Simulation

E1 E2 E3 E4 E5 E7 E8 E9 E10 E11

Packet 3

• pnr

• state

• type

• length

• origin

• Statistics

(Lebenslauf)

P 1 P 2 P 4

Event 6

• time

• type

• pnr

Generator

• RandomGenerator1

- verschiedene Param.

Ankunftszeit

• RandomGenerator2

- verschiedene Param.

Paketlänge

• weitere Parameter

Prozessor belegt:

Einreihen in Warteschlange

Prozessor frei:

Start der Bearbeitung

Ende festlegen

Bearbeitung abgeschlossen

Neues Paket in Warteschlange?

Zeit t

Zwischenankunftszeit Bearbeitungszeit Wartezeit

P 3




Startzeiten von Prozessen / Paketen switch Generator.type

case 'deterministic'

NextTime = time + Generator.par1;

case 'uniformly_distributet'

dt = Generator.par2 - Generator.par1;

NextTime = time + Generator.par1 + dt*rand(1, 1);

case 'exponential'

lambda = Generator.par1; % hier nur par1 benötigt

NextTime = time - log(rand(1,1)) / lambda;

case 'weibull'

????????????;

case 'pareto'

????????????;

otherwise

NextTime = time

end

SetEvent(NextTime, 'generate', PacketNr)

Struktur Generator

Generator.type

Generator.par1

Generator.par2

analog für Paketlängen

Es lassen sich auch Ankunftszeiten

aus Dateien (Messungen) einbringen.




Hauptprogramm und Abarbeitung von Events function t = ProcNextEvent()

…

…

% suche nächstes Event in der Liste –

% das mit dem niedrgsten Zeitwert t

% n ist die Position in der Liste

[t, n] = min([EventList.time]);

% führe die Verarbeitung für das Event

% gemäß Typ aus

switch EventList(n).type

case 'generate'

GeneratePacket(t);

case 'process'

ProcessPacket(t, EventList(n).Pnr);

case 'delete'

DeletePacket(t, EventList(n).Pnr);

otherwise

warning('Fehler Event.type')

end

% Lösche abgearbeitetes Event aus Liste

EventList(n) = [];

Initialisierung • Generator

• Bedieneinheit

• Event- und PacketList leer

MaxSimTime =1000; % maximale Zeit

time = 0; % aktuelle Zeit

pnr = 1; % 1. Paket

SetEvent(time, 'generate', pnr);

while time < MaxSimeTime;

time = ProcNextEvent();

end

Statistische Auswertung • Warte- und Verweilzeiten (Verteilung, MW, …)

• Erzeugte Anforderungen, Blockierungen

• Kundenzahl, Warteschlangenlänge (Vert., MW)

• Zeitlicher Verlauf, ….




Bearbeitung eines ankommenden Paketes function ProcessPacket(time, PacketNr) …..

mch = Processor.channels; % Anzahl Bedieneinheiten (Kanäle)

q1 = min(find(queue1 == 0)); % suche ersten freien Warteplatz Prio1

if bch < mch, % Kanal frei? bch: busy channels

ach = min(maxchpp, mch - bch); % Anzahl zugeteilter Kanäle

PacketList(PacketNr).challoc = ach; % Paket kennt Anzahl zugeteilter Kanäle

bch = bch + ach; % ach Kanäle mehr belegt

duration = packet.length/(ach*rate); % Dauer der Bearbeitung

SetEvent(time + duration, 'delete', PacketNr); % Beende nach Verarbeitung

PacketList(PacketNr).start = time;

else

if packet.prio == 1,

if length(q1) == 0, % falls nicht vorhanden

PacketList(PacketNr).state = 'deletet'; % Blockierung

PacketList(PacketNr).blocking = 1;

warning('blocking prio1')

else % falls Warteplatz q frei

queue1(q1) = PacketNr; % trage Paketnummer dort ein

end

end

…

… % Aktualisiere Zustand Bediensystem




Beendigung eines Prozesses (Paket verarbeitet) function DeletePacket(time, PacketNr)

PacketList(PacketNr).end = time; % Verarbeitung von PacketNr. beendet

PacketList(PacketNr).state = 'deleted'; % Setze Zustand auf 'deleted'

Processor.bch = bch - PacketList(PacketNr).challoc; % Kanäle freigeben

q1 = min(find(queue1 ~= 0));

if(q1 > 0) % Falls Warteschlange belegt,

p1 = queue1(1); % Hole nächstes Paket aus Queue1 (FIFO)

queue1(1) = 0; % Warteplatz freigeben

queue1 = circshift(queue1', -1)'; % die anderen Pakete nachrücken lassen

Packet = PacketList(p1); % zu verarbeitendes Packet

PacketList(p1).start = time; % setze Startzeit der Verabeitung

SetEvent(time+0.01, 'process', Packet.nr); % Starte Verarbeitung

….

else

…

end

Processor.queue1 = queue1; % Aktualisiere Zustand Bediensystem




Aufg. B.6: Simulation einfacher Bedienprozesse

a) Simulieren Sie mit Hilfe der vorliegenden SW ein M/M/1-System für zwei verschiedene

sinnvolle Werte für die Last. Stellen Sie MaxSimTime so ein, dass ca. 10000 Pakete erzeugt

werden.

– Wie groß ist die mittlere Zahl der Kunden im Systeme, wie groß die Auslastung pro Kanal?

– Speichern Sie die (komplementären) Verteilungsfunktionen für die Warte- und Verweilzeit in einem

Word-Dokument und notieren Sie dabei die eingestellte Last.

– Was fällt Ihnen beim Vergleich der beiden Diagramme auf? Wie kann man die

Wartewahrscheinlichkeit ablesen?

– Überprüfen Sie, inwieweit das Gesetz von Little erfüllt ist!

b) Simulieren Sie mit Hilfe der vorliegenden SW ein M/M/s-System für eine selbst gewählte

Kanalzahl s > 1. Erhöhen Sie dabei die Last auf das s-fache gegenüber (a). Vergleichen Sie

die Ergebnisse mit denen für (a)!

c) Simulieren Sie ein M/G/1-System für eine Verteilung G Ihrer Wahl (z.B. Weibull, determin.,

nicht exponentiell). Dazu müssen beim Paketlängen-Generator den entsprechenden

Zufallszahlengenerator implementieren. Vergleichen Sie die Ergebnisse mit denen für (a)!

d) Simulieren Sie ein M/M/1-System mit einer anderen Bediendisziplin als FIFO (z.B. LIFO).

Dazu sind Änderungen in „DeletePacket“ vorzunehmen. Vergleichen Sie die Ergebnisse mit

denen für (a)!

Documents

Modellierung und Simulation 1 - fh-swf.de · Modellierung und Simulation 1 Prof. Dr. H. Schulze Prof. Dr. C. Lüders 4.1 Wichtige Begriffe Fehler (Failure): Ein Objekt erfüllt seine