Warteschlangentheorie

Warteschlangentheorie
FT 2014
Übung 1
Dr. Andreas Löpker
Aufgabe 1: Eine Zufallsvariable X mit Werten in der Menge N = {1, 2, . . .} besitzt die Wahrscheinlichkeitsfunktion
f (n) = P (X = n) = 2−n ,
n ∈ N.
(a) Berechnen Sie P (X = 2), P (X < 2) und P (X > 2).
(b) Berechnen Sie E(3−X ).
Aufgabe 2: In einer Warteschlange sei T1 die Ankunftszeit des ersten Kunden. Die Verteilungsfunktion von T1 sei


; x<2
0
F (x) = P (T1 ≤ x) = 91 (x − 2)2 ; x ∈ [2, 5)

1
; x≥5
(a) Zeichnen Sie F (x). Ist F wirklich eine Verteilungsfunktion?
(b) Berechnen Sie die zugehörige Dichte f (x).
(c) Berechnen Sie P (X ≤ 3).
(d) Berechnen Sie P (X ∈ (3, 4]).
(e) Wie groß ist der Erwartungswert von X?
(f) Berechnen Sie die Varianz von X.
Aufgabe 3: X besitze eine Binomialverteilung mit n = 10 und p = 0.1. Berechnen Sie P (X ≤ 3).
Aufgabe 4? : X sei eine Zufallsvariable, die nur die beiden Werte a und b annimmt. Es gelte
P (X = a) = p,
P (X = b) = 1 − p.
Zeigen Sie, dass die Varianz von X niemals größer als
a−b 2
2
ist.
Warteschlangentheorie
Übung 2
FT 2014
Dr. Andreas Löpker
Aufgabe 5: In einer Warteschlange seien die Zwischenankunftszeiten A1 , A2 , . . . exponentiell
verteilt mit Parameter λ = 2 min−1 .
(a) Wie lange dauert eine Zwischenankunftszeit im Mittel?
(b) Wie groß ist die Wahrscheinlichkeit, dass der erste Kunde erst nach mehr als drei Minuten
erscheint?
(c) Angenommen der erste Kunde erreicht die Warteschlange vor Ende der zweiten Minute. Wie
groß ist die Wahrscheinlichkeit dass er erst nach der ersten Minute erschien?
(d) Mit welcher Wahrscheinlichkeit kommt der sechste Kunde vor der zweiten Minute an?
Aufgabe 6: Es sei N (t) ein Poisson-Prozess der den Ankunftsprozess einer Warteschlange beschreibt.
Die Ankunftsrate betrage 10 Kunden pro Stunde.
(a) Wie groß ist die Wahrscheinlichkeit, dass in 5 Minuten mehr als ein Kunde erscheint?
(b) Sie schließen die Wette ab, dass in den ersten 12 Minuten kein Kunde ankommt. Ihr Wetteinsatz ist ein Euro. Die Wettquote beträgt q, d.h. wenn sie Recht behalten, erhalten Sie q
Euro. Berechnen Sie q (in Abhängigkeit von x) so, dass sie im Mittel x Euro gewinnen bzw.
verlieren. Bei welchem q machen Sie im Mittel weder Gewinn noch Verlust?
Aufgabe 7: Es sei Y eine geometrisch Verteilte Zufallsvariable vom Typ II (siehe Vorlesung).
Berechnen Sie für ein beliebiges m ∈ {0, 1, 2, 3, . . .} die Wahrscheinlichkeit, dass X ≥ m ist.
Warteschlangentheorie
Übung 3
FT 2014
Dr. Andreas Löpker
Aufgabe 8: In einer Warteschlange mit einer Bedienstation, kommen die ersten 7 Kunden zu den
Zeiten
2, 6, 7, 10, 17, 18 und 25 Minuten
an. Ihre Bedienzeiten betragen jeweils
9, 4, 1, 2, 3, 3 und 2 Minuten.
Zeichnen Sie den Verlauf des Prozesses Xt , der die Anzahl der Kunden im System beschreibt, für 0 ≤
t ≤ 28. Tragen Sie die die Leer- und Besetztzeiten, die Ankunftszeitpunkte und Abgangszeitpunkte
ein.
Aufgabe 9: In einer M/M/1-Wartschlange beträgt die mittlere Zwischenankunftszeit 7 Minuten.
Die Bearbeitungszeit dauert im Mittel 5 Minuten.
(a) Wie viele Kunden sind im Mittel nach 10 Minuten angekommen?
(b) Nach 10 Minuten ist das Wartesystem bereits seit 3 Minuten leer. Wie groß ist die Wahrscheinlichkeit, dass das System noch weitere 3 Minuten leer bleibt.
(c) Nach 20 Minuten ist ein Kunde in Bearbeitung. Wie groß ist die Wahrscheinlichkeit, dass
dieser Kunde noch mindestens 8 Minuten im System verbleibt?
(d) Berechnen Sie die Verkehrsintensität.
(e) Wie groß ist die Wahrscheinlichkeit im System mehr als m Kunden vorzufinden?
(f) Mit welcher Wahrscheinlichkeit muss ein ankommender Kunde nicht warten?
Aufgabe 10: Eine M/M/1-Warteschlange erreichen im Schnitt stündlich 10 Kunden. Die durchschnittliche Bearbeitungszeit eines Kunden ist 5 Minuten. Angenommen, die Warteschlange befinde
sich im stationären Zustand.
(a) Wie groß ist die Auslastung.
(b) Wie groß ist die Wahrscheinlichkeit im System exakt 3 Kunden anzutreffen? Wie groß ist die
Wahrscheinlichkeit, dass sich mehr als 3 Kunden im System befinden?
(c) Wie groß ist die erwartete Kundenzahl im System?
(d) Um wie viel Prozent erhöht sich die erwartete Kundenzahl, wenn die Ankunftsrate um 1%
steigt?
Warteschlangentheorie
FT 2014
Übung 4
Dr. Andreas Löpker
Aufgabe 11: An einem Schalter werden Konzertkarten verkauft. Es kommt im Mittel ein Kunde
pro Minute an. Die Zwischenankunftszeiten und die Bedienzeiten seien exponentiell verteilt. Für
den Verkauf einer Karte werden im Mittel 50 Sekunden benötigt. Eine Karte kostet regulär 15 Euro.
(a) Wie viele Kunden sind im Mittel im System? Wie groß ist die Wahrscheinlichkeit, dass mehr
als 10 Kunden im System sind?
(b) Wie lange warten die Kunden durchschnittlich in der Schlange?
(c) Ein Ticketverkäufer bietet folgenden Deal an. Kunden zahlen für die Konzertkarte 20 Euro,
wenn sie weniger als 10 Minuten in der Warteschlange warten. Ansonsten ist die Karte schon
für 2 Euro zu haben. Lohnt sich das für die Kunden?
(d) Ein Kunde erreicht den Schalter und findet 6 Kunden in der Warteschlange, sowie einen
Kunden am Schalter vor. Er hat nur 5 Minuten Zeit. Wie groß ist die Wahrscheinlichkeit,
dass er noch eine Karte bekommt und rchtzeitig das System verlässt?
Aufgabe 12: Eine Markovkette Xn mit drei Zuständen 1, 2 und 3 besitze die folgende Übergangsmatrix.


0 0.5 0.5
P =  0.5 0.5 0 
1
0
0
(a) Zeichnen Sie ein Übergangsdiagramm.
(b) Berechnen Sie P (X1 = 2|X0 = 1) und P (X3 = 1|X0 = 3)
Aufgabe 13: Ein Markovkette in stetiger Zeit besitzt

−3 2.4
Q =  1 −2
0.4 3.6
folgende Intensitätsmatrix:

0.6
1
−4
(a) Bestimmen Sie λ und P .
(b) Wie viele Lösungen besitzt das lineare Gleichungssystem Q · x = 0?
Warteschlangentheorie
FT 2014
Übung 5
Dr. Andreas Löpker
Aufgabe 14: An einem Flughafen warten Taxis mit vier Sitzplätzen auf Gäste. Ein Taxi wartet
jeweils solange, bis alle Plätze belegt sind und fährt dann sofort los. Das nächste Taxi rückt unmittelbar nach. Der Ankunftsprozess der Kunden sei ein Poissonprozess, es kommen im Mittel 6
Kunden in einer Stunde an. Es sei Kt die Zahl der wartenden Kunden.
(a) Beschreiben Sie Kt als Markovkette in stetiger Zeit mit vier Zuständen {0, 1, 2, 3}. Zeichnen
Sie ein Übergangsdiagramm.
(b) Geben Sie die Intensitätsmatrix an.
(c) Die stationäre Verteilung π erfüllt die Gleichungen π0 + . . . + π3 = 1 und
πQ = 0.
Lösen Sie die Gleichung.
Aufgabe 15: Gegeben Sei eine Warteschlange mit einer Bedienstation, exponentiellen Ankünften
und exponentiellen Bedienzeiten mit einer mittleren Dauer von 2 Minuten. Die Ankunftsrate λ(k)
sei von der Zahl der Kunden k im System abhängig (Kunden werden durch eine lange Warteschlange
abgeschreckt), es gelte:
λ(k) =
5
min−1
1+k
Es sei wie üblich Xt die Anzahl der Kunden im System.
(a) Geben Sie ein Übergangsdiagramm für den Geburts- und Todesprozess Xt an.
(b) Ist der Prozess rekurrent und ergodisch?
(c) Wie lautet die stationäre Verteilung?
∞
X
k
x
x /k! = e
Hinweis:
k=0
Aufgabe 16: Folgende Übergangsdiagramme gehören zu drei Geburts- und Todesprozessen. Stellen
Sie fest, unter welchen Bedingungen eine Grenzverteilung existiert und bestimmen Sie diese.
Warteschlangentheorie
Übung 6
FT 2014
Dr. Andreas Löpker
Aufgabe 17: In einer Telefonzelle dauern die Gespräche im Mittel 160 Sekunden. Es kommt
im Mittel jede Minute ein Kunde an, der telefonieren möchte. Ist die Zelle besetzt, so gehen die
Kunden weiter zur nächsten Telefonzelle. Wie groß ist die Wahrscheinlichkeit eine besetzte Zelle
vorzufinden?
Aufgabe 18: Pro Tag erreichen durchschnittlich 6 Touristen einen Urlaubsort. Sie bleiben im
Mittel 5 Tage (die Aufenthaltszeit sei exponentiell verteilt). Wie groß ist die Wahrscheinlichkeit, in
dem Ort exakt 25 Touristen anzutreffen.
Aufgabe 19: Berechnen Sie für die M/M/1/K-Warteschlange den Grenzwert für K → ∞ der
Wahrscheinlichkeit zurückgewiesen zu werden. Unterscheiden Sie die Fälle % < 1, % = 1 und % > 1.
Aufgabe 20: Eine Arztpraxis möchte einen Warterraum einrichten. Sie rechnet mit einem Patientenaufkommen von 9 Patienten pro Stunde. Eine Konsultation dauert im Mittel 6 Minuten. Wie
viele Patienten muss das Wartezimmer aufnehmen können, wenn die Wahrscheinlichkeit ein volles
Wartezimmer anzutreffen weniger als 5 Prozent betragen soll?
Aufgabe 21: In einer M/M/1/2 Warteschlange mit Ankunftsrate 1 min−1 soll die Wahrscheinlichkeit einer Zurückweisung 10 Prozent betragen. Wie schnell muss die Bedienstation arbeiten?
Warteschlangentheorie
Übung 7
FT 2014
Dr. Andreas Löpker
Aufgabe 22: An einem Würstchenstand gibt es 3 Mitarbeiter. Die Zubereitung und der Verkauf
eines Würstchens dauert im durchschnittlich 45 Sekunden. Im Mittel besuchen 200 Kunden pro
Stunde den Stand.
(a) Wie groß ist die Wahrscheinlichkeit, dass alle drei Mitarbeiter nichts zu tun haben?
(b) Wie groß ist die Wahrscheinlichkeit, dass ein Kunde nicht warten muss?
(c) Wie lange muss man im Mittel warten?
Aufgabe 23: An einer Autowaschstation gibt es 8 Plätze an denen Autos vom Benutzer gewaschen
werden können. Im Durchschnitt dauert so ein Vorgang 10 Minuten. Stündlich erreichen im Mittel
30 Autos die Anlage. Sie warten gegebenenfalls auf einem Parkplatz vor der Station bis ein Platz
in der Station frei wird.
(a) Wie groß ist die Wahrscheinlichkeit nicht warten zu müssen ?
(b) Wie viele Kunden findet man im System durchschnittlich vor?
(c) Wie lange muß man durchschnittlich warten?
Aufgabe 24: In einer Maschine werden Schokoladen verpackt. Dabei können bis zu drei Tafeln
gleichzeitig verpackt werden. Die Verpackung einer Tafel dauert im Mittel 2 Sekunden, pro Minute
kommen im Mittel 60 Tafeln auf einem Transportband an. Ist die Maschine komplett ausgelastet,
so müssen die ankommenden Tafeln zur nächsten Maschine (die hier nicht betrachtet wird) weitergeleitet werden.
(a) Wie viel Prozent der Tafeln werden an dieser Maschine bedient?
(b) Wie viele Tafeln sind im Mittel in der Maschine in Bearbeitung?
Warteschlangentheorie
Übung 8
FT 2014
Dr. Andreas Löpker
Aufgabe 25: Ein Wartezimmer bei einem Arzt hat 4 Warteplätze. Pro Tag (10h) besuchen im
Durchschnitt 60 Patienten den Arzt. Jeder von Ihnen bleibt im Mittel 12 Minuten. Wir groß ist die
Wahrscheinlichkeit, dass ein Patient ein volles Wartezimmer antrifft.
Aufgabe 26: Auf einer Party befinden 20 Raucher, von denen jeder einmal in 120 Minuten auf den
Balkon geht um eine Zigarette zu rauchen (Verweilzeit im Durchschnitt 2 Minuten). Leider können
nur maximal zwei Personen gleichzeitig den kleinen Balkon betreten. Mit welcher Wahrscheinlichkeit
werden Partygäste am Rauchen gehindert, weil sie einen vollen Balkon vorfinden?
Aufgabe 27: In einer Fabrik stehen 10 Maschinen, die im Durchschnitt in einer Woche sechsmal
ausfallen. Ein Team von 3 Mitarbeitern ist für die Reparatur zuständig. Diese dauert im Mittel
einen Tag. Wie groß ist die Wahrscheinlichkeit, dass eine ausfallende Maschine nicht sofort repariert
werden kann?
Aufgabe 28:
An einer Leuchtreklame gibt es 20 Lichter, die jeweils für eine exponentielle
Zeitspanne (Mittelwert 2 Sekunden) leuchten und dann für eine exponentielle Zeitspanne (Mittelwert 1 Sekunde) aus sind. Die Leuchtreklame wird fotografiert. Wie groß ist die Wahrscheinlichkeit,
dass auf dem Foto genau die Hälfte der Lichter leuchten?


0 1 0
Aufgabe 29: Gegeben Sei die Matrix P = 0.5 0 0.5.
0.5 0 0


1 0 0
(a) Berechnen Sie die Matrix (I − P )T . Dabei ist I = 0 1 0 die Einheitsmatrix.
0 0 1
 
0
(b) Lösen Sie das lineare Gleichungssystem (I − P )T x = λ.
0
Aufgabe 30: (?) An einer M/M/1-Warteschlange kommen im Mittel 20 Kunden pro Stunde an. Das
System befinde sich im Gleichgewicht. Wie groß ist die Wahrscheinlichkeit, dass nach t Zeiteinheiten
die Zahl der bereits vollständig bedienten Kunden kleiner ist, als die Zahl der Kunden die zu dem
Zeitpunkt im System sind?
Warteschlangentheorie
Übung 9
FT 2014
Dr. Andreas Löpker
Aufgabe 31: Eine M/M/1-Warteschlange befinde sich im stationären Zustand. Es sei λ = 4 h−1 ,
µ = 5 h−1 . Wie lange dauert es im Mittel bis der erste Kunde das System verlässt?
Aufgabe 32: Gegeben sei folgendes Netzwerk von M/M -Warteschlangen:
(a) Berechnen Sie die Grenzverteilung des obigen Netzwerks.
(b) Bestimmen Sie die Wahrscheinlichkeit zwei, einen und keinen Kunden in den Warteschlangen
1, 2 und 3 vorzufinden.
(c) Mit welcher Wahrscheinlichkeit befinden sich in den drei Wartesystemen gleich viele Kunden?
Aufgabe 33: Gegeben sei folgendes Tandem-Warteschlangensystem mit Rücklauf.
(a) Bestimmen Sie die Grenzverteilung.
(b) Es sei p = 1/2, λ = 2 und µ1 = µ2 = 6. Wie groß ist die Wahrscheinlichkeit dass sich in der
ersten Warteschlange nicht weniger Kunden befinden, als in de zweiten?
Warteschlangentheorie
Übung 10
FT 2014
Dr. Andreas Löpker
Aufgabe 34: Im folgenden Netzwerk befinden sich drei Wartesysteme mit insgesamt drei Kunden.
Bestimmen Sie die Grenzverteilung. Berechnen Sie die Wahrscheinlichkeit in jeder Station genau
einen Kunden anzutreffen.
Aufgabe 35: Zwei Kunden halten sich in folgendem Netzwerk auf. Bestimmen Sie die gemeinsame
Grenzverteilung für die Kundenzahl in den 4 Wartesystemen.
Aufgabe 36: Gegeben sei folgendes System mit drei Servern und drei Warteschlangen.
Die Bedienzeiten seien 3h,1h und 4h. Im System befinden sich 5 Kunden. Bestimmen Sie die
gemeinsame Grenzverteilung der Kundenzahlen.