Document

Aufgabe 1
Hinweis: im Folgenden ist mit Graph ein schlichter Graph gemeint, kein Multigraph.
a) Wie ist eine Euler-Tour in einem Graphen G = (V, E) definiert?
(1 Punkt)
b) Unter welchen Bedingungen existiert in einem Graphen G = (V, E) eine Euler-Tour?
(2 Punkte)
c) Was ist bei einem Briefträgerproblem in einem gewichteten Graphen G = (V, E, c)
gesucht?
(1 Punkt)
d) Betrachten Sie den durch folgende Zeichnung gegebenen gewichteten Graphen G =
(V, E, c):
2
3
2
4
3
2
1
1
2
4
Lösen Sie in diesem Graphen das Briefträgerproblem! Machen Sie dabei deutlich,
welche Schritte Sie allgemein beim Lösen eines Briefträgerproblems durchführen müssen. Geben Sie insbesondere die Briefträger-Tour und deren Länge an. (6 Punkte)
e) Wie bestimmt man den zu einem Graphen G = (V, E) gehörigen Linegraph L(G)
(auch Kantengraph genannt)?
(1 Punkt)
f) Zeigen Sie bitte: Wenn ein Graph G = (V, E) eulersch ist, so ist der zugehörige Linegraph L(G) hamiltonsch.
(2 Punkte)
g) Zeigen Sie bitte: Wenn ein Graph G = (V, E) eulersch ist, so ist auch der zugehörige
Linegraph L(G) eulersch.
(2 Punkte)
Operations Research 2
Aufgabe 2
a) Das Fahrradteilezubehörfachgeschäft Rudis Radlershop“ vertreibt überregional alles,
”
um ein Fahrrad in Bezug auf Leistung und Optik aufzuwerten. Mittlerweile ist das Unternehmen bis auf 42 Filialen gewachsen. Der Gründer der Kette, Rudolf D. Oping bittet
Sie als Fachmann/-frau nun, das Konzept der DEA-Effizienz in einem 30-minütigen
Vortrag zu erläutern.
(i) Bei der Vorstellung des DEA-Konzeptes fragt Sie Herr Oping, wann genau Sie eine
Filiale als DEA-effizient“ bezeichnen. Beantworten Sie ihm bitte nur diese
”
Frage!
(2 Punkte)
(ii) In Ihrem Vortrag sitzen auch Mitarbeiter des Unternehmens, die zur Darstellung
des Problems nur die folgende Form kennen:
n
P
max i=1
m
P
(k)
xi Oi
(k)
j=1
u. d. N.
m
X
j=1
(r)
y j Ij
≥
n
X
y j Ij
(r)
xi Oi
für alle r = 1, . . . , s
i=1
x1 , . . . , xn , y1 , . . . , ym > 0.
Ein solcher Mitarbeiter möchte von Ihnen wissen, ob man durch geeignete Modifikation des Modells einen Standard-LP-Löser nutzen kann, um eine Modelllösung zu erzeugen. Bitte begründen und entwickeln Sie Ihre Antwort. (5 Punkte)
(iii) Welche Auskunft gibt Ihnen eine für das Modell aus a)(ii) gefundene Optimallösung
in Bezug auf die Effizienz der Filiale k?
(2 Punkte)
(iv) Nach der Effizienzanalyse stehen für alle Filialen die Effizienzwerte zur Verfügung.
Filiale Bochum (Nr. 17) stellt die Analyse in Frage und behauptet, die gesamte
Untersuchung (und damit ihre Einstufung als ineffizient) sei fehlerhaft, da ein –aus
Sicht der Filiale– völlig unwichtiger Output mit in die Analyse einbezogen
wurde. Würde die Untersuchung ohne diesen Output wiederholt, so hätte die
Filiale Bochum einen Effizienzwert von 1.
Aufgrund dieser Kritik tritt Herr Oping erneut an Sie heran und fragt, ob die Wegnahme von Inputs bzw. Outputs eine Verbesserung des Effizienzwertes
zur Folge haben kann. Beantworten Sie bitte auch diese Frage und begründen Sie
Ihre Antwort anhand eines Beispiels, wenn es möglich ist.
(2 Punkte)
b) Erinnern Sie sich an die in der Veranstaltung behandelten Lösungsmethoden für das
Transportproblem.
(i) Zur Ermittlung einer Startlösung ist Ihnen aus der Vorlesung das NordwestEcken-Verfahren bekannt. Ein Kommilitone behauptet, dass auch ein analoges
Nordost-Ecken-Verfahren“ möglich ist. Wie würde ein solches aussehen? Hat
”
er recht? Begründen Sie bitte Ihre Antwort.
(2 Punkte)
(ii) Erläutern Sie bitte ausführlich die Bedeutung von elementaren Kreisen im
Stepping-Stone-Verfahren.
(2 Punkte)
Operations Research 3
Aufgabe 3
a) Der Familienbetrieb Dörthe-Deko“ (DD) vertreibt über eine Onlineplattform Blumen
”
und Vasen. Im Versand arbeitet ganztags (8 Stunden am Tag) Dörthes Mann Heinrich. Dieser packt ein Paket mit einem Blumenstrauß in 5 Minuten und ein Paket
mit einer Vase in 2 Minuten (aus organisatorischen Gründen werden jeder Blumenstrauß und jede Vase einzeln verpackt). Täglich treffen durchschnittlich Bestellungen von 80 Blumensträußen und 30 Vasen ein (in welchen Zeitabständen
diese Bestellungen eintreffen, ist aber unbekannt). Wir betrachten den Verpackungsvorgang, in dem die Aufträge – von denen beliebig viele gespeichert werden können –
in der Reihenfolge des Umsatzes des jeweiligen Kunden bearbeitet werden.
(i) Wie setzt sich die Kendall’sche Notation zusammen? Beschreiben Sie kurz! Wie
lässt sich das betrachtete Wartesystem mittels dieser Notation klassifizieren?
(kurze Begründung)
(2,5 Punkte)
(ii) Ist dieses Wartesystem stabil? Begründen Sie!
(2 Punkte)
(iii) Dörthes und Heinrichs Tochter, Mandy, möchte ihr Taschengeld aufbessern und
dazu im Versand aushelfen. Da Heinrich eh kürzer treten wollte, kommt ihm dies
sehr gelegen. Er ist bereit, nur noch 6 Stunden am Tag zu arbeiten und Mandy
2 Stunden am Tag übernehmen zu lassen. Da die Verpackung von Blumensträußen wesentlich schwieriger ist, möchte er diese nicht an Mandy abtreten, die für
das Verpacken von Vasen schon 3 Minuten benötigt. Sie soll sich allein und
ausschließlich um die Verpackung der Vasen kümmern.
Auf diese Art und Weise entstehen 2 Wartesysteme, jeweils eines für die Verpackung der Blumensträuße und eines für die Verpackung der Vasen. Beantworten Sie bitte die Frage a)(ii) für jedes der beiden Wartesysteme! (4 Punkte)
b) Die Präsentkorbboutique Madame Claudette’s Präsentkörbe“ (MCP) hat folgendes Ge”
schäftskonzept: Die Kunden vom MCP melden sich einen Tag, bevor sie den gewünschten
Präsentkorb mit Madame Claudette zusammenstellen möchten. In einem kurzen Beratungsgespräch wird grob abgesprochen, welche Art von Präsentkorb gewünscht wird (dadurch weiß Madame Claudette, wie lange das Erstellen des Präsentkorbs dauern
wird). Außerdem geben die Kunden an, wann sie am folgenden Tag in die Boutique
kommen und wann sie diese spätestens verlassen wollen. Da Madame Claudette
eine Meisterin ihres Fachs ist, bleiben die Kunden in jedem Fall solange, bis sie an die
Reihe kommen und ihr jeweiliger Präsentkorb fertig ist. Madame Claudette arbeitet
grundsätzlich allein, um die hohe Qualität ihrer Präsentkörbe zu gewährleisten.
Kunde Nr. i
Präsentkorberstellungsdauer (in Stunden) pi
Ankunft Kunde (Uhrzeit) ri
erwünschte Abfahrt Kunde (Uhrzeit) di
Kunde 1
2
8
12
Kunde 2
1
10
13
Kunde 3
2
11
13
Kunde 4
1
12
13
(i) Bitte modellieren Sie dieses Problem als Ein-Maschinen-Reihenfolgeproblem, indem Sie ein entsprechendes (gemischt-ganzzahliges) lineares Programm angeben!
Die Zielsetzung bestehe darin, die größte Unpünktlichkeit eines Jobs zu minimieren.
(3 Punkte)
Operations Research 4
(ii) Berechnen Sie bitte die maximale Verspätung sowie die durchschnittliche
Verspätung der Jobs für den Schedule S = (J2 , J1 , J4 , J3 ).
(2 Punkte)
(iii) Nun wollen Sie statt der Zielfunktion in b)(i) die Gesamtdurchlaufzeit minimieren. Wie müssen Sie dazu das Modell in b)(i) abändern?
(1,5 Punkte)
Operations Research 5

Download Report