Übungsblatt 2

Operations Research und Wirtschaftsinformatik
Prof. Dr. P. Recht // Christin Otto, M.Sc. Wirt.-Math.
Operations Research
Übungsblatt 2
Abgabetermin Mittwoch 04.11.2015 bis 10 Uhr im Kasten 20 (Mathefoyer)
Aufgabe 97
Welche der folgenden drei Graphen besitzen einen Hamilton-Kreis? Bitte geben Sie entweder
jeweils einen solchen an oder begründen Sie, wieso keiner existiert!
a)
b)
c)
(5 Punkte)
Aufgabe 99
13 Politiker besuchen eine 6-tägige Konferenz und essen abends gemeinsam an einem großen
runden Tisch im nahe gelegenen Nobelrestaurant. Ihre Aufgabe als Restaurantbesitzer ist es
nun, die Tischordnung für die 6 Abende so vorzunehmen, dass es während dieser Zeit keinen
Abend gibt, an dem zwei Personen nebeneinander sitzen, die an einem anderen Abend ebenfalls
bereits schon einmal nebeneinander gesessen haben.
a) Welchem Entscheidungsproblem auf einem Graphen entspricht Ihre Aufgabe?
b) Geben Sie bitte eine mögliche Lösung an.
c) Wie viele verschiedene Hamiltonkreise gibt es in einem vollständigen Graphen mit 13 Knoten? (Diese Hamilton-Kreise müssen nicht den unter a) geforderten Anforderungen genügen.)
(4 Punkte)
Aufgabe 101
Betrachten Sie bitte folgende Problemstellung:
Auf einer Maschine sollen die Aufträge Ai , i = 1, . . . , n bearbeitet werden. Die Maschine
kann nur jeweils einen Auftrag bearbeiten und muss vor der Bearbeitung eines neuen Auftrags
erst entsprechend umgerüstet werden. Dabei befindet sich die Maschine zu Beginn und nach
Bearbeitung der Aufträge in einem ungerüsteten Zustand. Die Rüstzeit ist jeweils sowohl vom
vorher bearbeiteten Auftrag k als auch vom nun zu bearbeitenden Auftrag l abhängig und
beträgt Rkl Zeiteinheiten für k, l ∈ {1, . . . , n}. Dabei gilt Rkl = Rlk ∀ k, l ∈ {1, . . . , n}. Die
Zeit zum Aufrüsten der ungerüsteten Maschine zur Bearbeitung von Auftrag i beträgt A+
i
Zeiteinheiten, die Zeit zum Abrüsten nach Bearbeitung des als letzten bearbeiteten Auftrags i
auf den ungerüsteten Zustand beträgt A−
i Zeiteinheiten. Die reine Bearbeitungszeit eines Auftrags i ist durch Zi , i = 1, . . . , n gegeben. Ziel des Betriebs ist es, die gesamte Bearbeitungszeit
möglichst gering zu halten.
a) Wodurch unterscheidet sich das geschilderte Problem vom Travelling Salesman Problem?
b) Formulieren Sie bitte das Problem nun als TSP, indem Sie
• die Entscheidungsfragen und -variablen,
• die Entscheidungsschranken und Nebenbedingungen und
• die Zielfunktion
angeben.
(4 Punkte)

Download Report