Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7–1 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle Abschnitt 7.1 M/G/1–Modell 7.1 M/G/1–Modell 7–2 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Beschreibung Erweiterung auf allgemeine Bedienzeitverteilungen ➸ Weiterhin unabhängige exponentiell verteilte Zwischenankunftszeiten ☞ Poissonscher Ankunftsprozeß mit Rate λ. ➸ Allgemeiner verteilte Bedienzeiten, jedoch einige Einschränkungen ☞ unabhängig und identisch verteilt gemäß ZV S (→ auch M/GI/1–Modell), ☞ erstes und zweites Moment existiert (zur Berechnung von E[N ], E[W ], E[V ]), ☞ Verkehrsintensität und Auslastung a = ρ = λE[S] (analog zu M/M/1). Bezeichnungen ➸ Sukzessive Abgangszeiten (Zeiten der Fertigstellung von Bedienungen) t1, t2, . . . ➸ N (t) = Anzahl der Kunden im System zur Zeit t (wie gewohnt). Damit ist (Xn)n∈IN+ mit Xn := N (tn), i ∈ IN+ ein stochastischer Prozeß mit diskreter Parametermenge, und Xn ist die Anzahl von Kunden, die der n-te Kunde zurückläßt. 7–3 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell 7.1.1 Eingebettete Markovkette Bezeichne die ZV A die Anzahl von Kunden, die während einer Bedienung ankommen. Dann Xn+1 = ½ Xn − 1 + A, falls Xn > 0, A, falls Xn = 0. ➸ Bedienzeiten unabhängig und identisch verteilt wie ZV S ☞ Bedienzeit des (n + 1)-ten Kunden unabhängig von Bedienzeiten anderer Kunden, von Nummer des Kunden und von Anzahl der Kunden im System. ➸ Poissonscher Ankunftsprozeß, also stationäre Zuwächse ☞ ZV A hängt nur von S ab, unabhängig von Startzeit der Bedienzeit or Anzahl von Kunden im System. ☞ Verteilung unabhängig von Nummer des bedienten Kunden, da Bedienzeiten iid. ⇒ Xn+1 hängt nur von Xn und der unabhängigen ZV A ab, nicht von Xn−1, Xn−2, . . . Also Satz: (Xn) ist eine diskrete Markovkette. 7–4 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Verteilung von A Poissonscher Ankunftsprozeß, aber Bedienzeit beliebige ZV, also A nicht Poisson-verteilt. Es gilt aber für jedes t e−λt(λt)n P (A = n|S = t) = (Poisson–Verteilung) n! sowie Z ∞ Z ∞ −λt e (λt)n P (A = n|S = t)dFS (t) = dFS (t), n ∈ IN. kn := P (A = n) = n! 0 0 Einschub: Stieltjes–Integral (mit beliebiger Funktion g) ➸ Für stetige ZV X mit Verteilungsfunktion F und Dichte f Z ∞ Z ∞ g(x)dF (x) = g(x)f (x)dx. 0 0 ➸ Für diskrete ZV X mit Verteilung pi = P (X = xi) Z ∞ ∞ X g(x)dF (x) = g(xi)pi. 0 i=0 7–5 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Übergangswahrscheinlichkeiten Offensichtlich gilt für die ÜWK pij = P (Xn+1 = j|Xn = i) = P (A = j − i + 1), i>0 Z ∞ = P (A = j − i + 1|S = t)dFS (t), i>0 0 = Z 0 ∞ −λt e (λt)j−i+1 · dFS (t), falls j ≥ i − 1, i > 0, (j − i + 1)! 0, falls j < i − 1, i > 0. Es fehlen noch die ÜWK pij für i = 0. Wenn bei Abgang eines Kunden das System leer ist , dann ist kein Übergang in (Xn) vor der Ankunft des nächsten Kunden möglich ⇒ nächster Übergang, wenn dieser Kunde das System verläßt (seine Bedienung beendet). ⇒ ÜWK pij für i = 0 und i = 1 sind gleich, also p0j = p1j , j ∈ IN. 7–6 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Übergangsmatrix Übergangsmatrix P der diskreten Markovkette (Xn) Also mit kn := P (A = n), n ∈ IN k0 k1 k2 k3 k4 . . . k0 k1 k2 k3 k4 . . . pij = kj−i+1, i > 0, P = 0 k0 k1 k2 k3 . . . . p0j = kj . 0 0 k 0 k1 k2 . . . .. .. .. .. .. Erwartungswert von A Z ∞ ∞ X X nP (A = n) = nkn = E[A] = n=0 = Z ∞ n=0 −λt e 0 = λ (λt) ∞ X (λt)n n=0 Z 0 ∞ n! ∞ e−λt 0 dFS (t) = λ ∞ X n(λt)n n=0 Z 0 tfS (t)dt = λE[S] = a = ρ. ∞ n! tdFS (t) dFS (t) 7–7 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell 7.1.2 Stationäre Zustandsverteilung Jede ergodische (irreduzible, aperiodische, positiv rekurrente) Markovkette besitzt eine stationäre Verteilung. Beachte: (Xn) ist irreduzibel und aperiodisch wegen ∀n ∈ IN kn > 0 und ∀i ∈ IN pii > 0. Für Ergodizität müssen wir also nur noch positive Rekurrenz zeigen. Dazu benötigen wir folgenden Satz (ohne Beweis) zu diskreten Markovketten Satz: Kriterium für positive Rekurrenz Eine diskrete Markovkette (Xn)n∈IN ist positiv rekurrent, falls eine nichttriviale Lösung des folgenden Ungleichungssystems existiert. ∞ X j=0 p0j xj < ∞ und ∞ X j=0 pij xj ≤ xi − 1, i > 0. Die xj sind dabei reelle Koeffizienten (nichttrivial: nicht aus lauter Nullen bestehend). 7–8 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Existenz einer stationären Verteilung Sei ρ = E[A] < 1, xj := j 1−ρ , j ∈ IN. Eingebung“ also, daß diese xj eine Lösung sind. ” Dann für i > 0 ∞ ∞ ∞ X X X j j pij xj = pij = kj−i+1 · 1−ρ 1−ρ j=0 j=0 j=i−1 1 = (k0(i − 1) + k1i + k2(i + 1) + k3(i + 2) + · · · ) 1−ρ 1 ((k0(i − 1) + k1(i − 1) + k2(i − 1) + · · · ) + (k1 + 2k2 + 3k3 + · · · )) = 1−ρ ∞ ∞ i−1 X 1 X = kj + jkj 1 − ρ j=0 1 − ρ j=1 i−1 ρ i = + = − 1 = xi − 1 ≤ xi − 1. 1−ρ 1−ρ 1−ρ 7–9 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Existenzkriterium für stationäre Verteilung Außerdem ∞ X ∞ X ρ jkj p0j xj = = <∞ 1−ρ 1−ρ j=0 j=0 ⇒ positiv rekurrent. Damit ist (Xn) ergodisch und hat somit eine stationäre Verteilung. Man kann weiter zeigen ➸ für ρ = 1 ist (Xn) nullrekurrent, für ρ > 1 ist (Xn) transient. Also Satz: Existenzkriterium für eine stationäre Verteilung (Xn) hat eine stationäre Verteilung genau dann, wenn ρ < 1. Das ist konsistent mit der intuitiven Vorstellung, daß das System genau dann stabil ist, wenn während einer Bedienung im Mittel weniger als ein neuer Kunde ankommt. 7–10 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Berechnung einer stationären Verteilung Im folgenden also nun immer Annahme ρ < 1. Stationäre Verteilung von (Xn) wie üblich mittels π = πP mit Normierungsbedingung ∞ ∞ X X πipij , πi = 1. ∀j ∈ IN : πj = i=0 i=0 Mit den eingeführten Notationen und der Struktur von P π i = π 0 ki + i+1 X j=1 πj ki−j+1, i ∈ IN. Zur Berechnung der stationären Verteilung seien X die stationäre Anzahl von Kunden zu den Abgangszeiten, also P (X = n) = πn, n ∈ IN und die erzeugenden Funktionen von X und A ∞ ∞ X X πi z i , K(z) := GA(z) = ki z i . π(z) := GX (z) = i=0 i=0 7–11 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Erzeugende Funktion Wir erhalten i+1 1X π0ki+1z i+1 i i i+1 π i z = π 0 ki z + πj ki−j+1z − , z j=0 z Beachte, daß i+1 X i ∈ IN. πj ki−j+1 eine Faltung ist, und summiere über i. Dann folgt (→ Tafel) j=0 à ! ! Ã∞ ∞ ∞ ∞ X X 1 X i X π 0 i j ki z + ki z π j z − π 0 k0 − ki z i − k 0 π(z) = π0 z z i=0 i=0 i=0 j=0 = π0K(z) + Beachte π(1) = 1 π0 (K(z)π(z) − π0k0) − (K(z) − k0) . z z ∞ X i=0 πi = 1 = ∞ X j=0 ki = K(1), K ′(1) = E[A] = ρ. 7–12 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Existenz und Form der stationären Zustandsverteilung Mit der Regel von de L’Hopital folgt π0 π0 ((1 − z)K ′(z) − K(z)) π0K(1) = = . 1 = π(1) = lim π(z) = lim z→∞ z→∞ K ′(z) − 1 1−ρ 1−ρ Also: π0 = 1 − ρ, woraus die πn, n > 0 berechnet werden können. Wir haben also für ρ < 1 die stationäre Verteilung der Anzahl von Kunden zu den Abgangszeiten. Man kann zeigen, daß die stationäre Verteilung zu beliebigen Zeitpunkten für ρ < 1 existiert und zu unserer identisch ist, also pn = P (N = n) = πn = P (X = n), n ∈ IN. Insbesondere gilt also π(z) = GX (z) = GN (z) = (1 − ρ)(1 − z)K(z) . K(z) − z 7–13 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell 7.1.3 Pollaczek–Khintchine–Formeln Wir haben: Formel für die stationäre Verteilung von N. Wir wollen noch: Formel für den Erwartungswert von N. Aus folgt (1 − ρ)(1 − z)K(z) π(z) = GX (z) = GN (z) = . K(z) − z ′′ ′′ (1) K G ′ A (1) E[N ] = GN (1) = ρ + = . 2(1 − ρ) 2(1 − ρ) Dummerweise wissen wir nicht viel über G′′A(1) . . . kennen aber die Bedienzeitverteilung. Jetzt mit Laplace–Stieltjes–Transformierten (LST) S ∗(ϑ) der Bedienzeit S und dS ∗(ϑ) E[S] = − |ϑ=0, dϑ d2S ∗(ϑ) E[S] = |ϑ=0. 2 dϑ 7–14 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Zusammenhänge £ 2¤ Mit VAR[X] = E X − E[X]2 für beliebige ZV X folgt speziell £ 2¤ E A = VAR[A] + E[A]2 = G′′A(1) + G′A(1) = K ′′(1) + K ′(1). Außerdem ∞ X GA(z) = K(z) = kn z n = n=0 = Z 0 ∞ −λt λtz e e dFS (t) = Z ∞ e−λt 0 Z ∞ X (λtz)j j=0 ∞ j! dFS (t) e−(λ−λz)tdFS (t) 0 = S ∗(λ − λz) = S ∗(λ(1 − z)). Die erzeugende Funktion von A kann also durch die LST von S ausgedrückt werden GA(z) = S ∗(λ(1 − z)). Jetzt Darstellung von E[A] = ρ durch die gesuchten Ableitungen G′A(1), G′′A(1). 7–15 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Varianten der Pollaczek–Khintchine–Formel Aus der eingerahmten Formel folgt G′A(z) = −λS ∗(1)(λ(1 − z)), G′′A(z) = λ2S ∗(2)(λ(1 − z)), wobei S ∗(i) die i-te Ableitung der LST S ∗ bezeichnet. Insbesondere gilt G′A(1) = −λS ∗(1)(0) = λE[S] = ρ, Einsetzen in E[N ] = G′N (1) G′′A(1) = λ2S ∗(2)(0) = λ2E[S 2]. K ′′(1) G′′A(1) =ρ+ = 2(1 − ρ) 2(1 − ρ) liefert verschiedene Varianten der Pollaczek–Khintchine–Formel λ2VAR[S] + ρ2 ρ2(1 + νS2 ) λ2E[S 2] = ρ+ = ρ+ , E[N ] = ρ ∗ 2(1 − ρ) 2(1 − ρ) 2(1 − ρ) √ VAR[S] wobei in der letzten Gleichung νS := E[S] den Variationskoeffizienten von S bezeichnet. 7–16 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle Transformationgleichungen Einsetzen von GA(z) = S ∗(λ(1 − z)) in GN (z) = (1 − ρ)(1 − z)K(z) (1 − ρ)(1 − z)GA(z) = K(z) − z GA(z) − z liefert schließlich die Pollaczek–Khintchine–Transformationsgleichung (1 − ρ)(1 − z)S ∗(λ(1 − z)) GN (z) = S ∗(λ(1 − z)) − z Einsetzen in liefert £ 2¤ E A = VAR[A] + E[A]2 = G′′A(1) + G′A(1) = K ′′(1) + K ′(1) £ 2¤ £ 2¤ 2 E A = λ E S + ρ. Damit jetzt Zusammenhang zur Verweilzeit herstellen... 7.1 M/G/1–Modell 7–17 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Zusammenhang zur Verweilzeit Mit dem Satz der totalen Z ∞ Wahrscheinlichkeit pn = πn = P (n Ankünfte während einer Verweilzeit R|R = t)dFR (t) 0 Z = ∞ 0 n (λt) e−λt · dFR (t). n! Also GN (z) = ∞ X pn z n = n=0 = Z 0 ∞ Z ∞ e−λt 0 e−λteλtz dFR (t) = ∞ X (λtz)j j! j=0 Z 0 ∞ dFR (t) e−λ(1−z)tdFR(t) = R∗(λ(1 − z)). Somit als Variante der Pollaczek–Khintchine–Transformationsgleichung (1 − ρ)ϑS ∗(ϑ) ∗ . R (ϑ) = ϑ + λ(S ∗(ϑ) − 1) 7–18 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Verallgemeinerung von Little Ableiten von GN liefert G′N (z) dR∗(ϑ) dϑ dR∗(ϑ) |ϑ=λ(1−z) = −λ |ϑ=λ(1−z) = dϑ dz dϑ Z ∞ = λ te−λt(1−z)dFR(t). 0 Also E[N ] = G′N (1) = λ Z ∞ tdFR (t) = λE[R], 0 womit wir gerade das Gesetz von Little für den Spezialfall M/G/1 hergeleitet haben. Analog zur obigen Herleitung erhält man (aber nur für M/G/1) E[N (N − 1)(N − 2) · · · (N − k + 1)] = (k) GN (1) also eine Verallgemeinerung des Gesetzes von Little. £ k¤ = λ E R , k k > 0, 7–19 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.1 M/G/1–Modell Wartezeiten Aus der Beziehung R = W + S und entsprechend für die LST R∗(ϑ) = W ∗(ϑ) · S ∗(ϑ) erhält man für die LST der Wartezeit als weitere Variante der Pollaczek–Khintchine– Transformationsgleichung (1 − ρ)ϑ W ∗(ϑ) = . ∗ ϑ + λ(S (ϑ) − 1) Abschließend noch (ohne Herleitung oder Beweis) die Rekurrenzformel von Takacs £ i+1¤ µ ¶ k £ k¤ £ k−i¤ λ X k E S E W = E W , 1 − ρ i=1 i (i + 1) wobei selbstverständlich alle Momente existieren müssen. Als Folgerung k µ ¶ £ i¤ £ k−i¤ £ k¤ X k E S E W . E R = i i=0 7–20 Werner Sandmann: Modellierung und Analyse Kapitel 7 Analyse elementarer nicht-Markovscher Modelle 7.2 G/M/1–Modell und G/G/1–Modell Abschnitt 7.2 G/M/1–Modell und G/G/1–Modell siehe Kopien... (→ Haverkort, Chapter 7) 7–21
© Copyright 2024 ExpyDoc
