Aufgabe 1 a) Wie ist ein (ungerichteter) Graph definiert? (1 Punkt) b) Wie ist eine Eulersche Tour definiert, wie ein Euler-Graph? (1 Punkt) c) Wie lässt sich mit Hilfe einer Aussage aus dem Skript leicht überprüfen, ob ein gegebener zusammenhängender Graph Eulersch ist? (1 Punkt) d) Wie ist das klassische Briefträgerproblem (Chinese Postman Problem) definiert? Was ist insbesondere gegeben und was gesucht? (2 Punkte) e) Wie lässt sich das klassische Briefträgerproblem als ökonomische Problemstellung interpretieren? (2 Punkte) f) Lösen Sie bitte das klassische Briefträgerproblem auf folgendem Graphen. 2 3 6 3 3 1 1 2 4 4 Erläutern Sie dabei bitte Ihr Vorgehen. 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. (4 Punkte) g) Wie ändert sich der Zielfunktionswert der Lösung des klassischen Briefträgerproblems, wenn Sie dem Graphen aus Aufgabenteil f) die Kante (1, 3) mit Gewicht 2 (zusätzlich zu den vorhandenen Kanten) hinzufügen? Begründen Sie bitte. (2 Punkte) h) Erläutern Sie bitte, wieso beim Briefträgerproblem stets eine optimale Lösung existiert, bei der die dem Graphen hinzugefügten Wege kantendisjunkt sind. (2 Punkte) Operations Research 2 Aufgabe 2 a) Erläutern Sie bitte die Problemstellung des Rundreiseproblems (Traveling Salesman Problem). Was ist insbesondere gegeben und was gesucht? (1 Punkt) b) Wie lässt sich das Rundreiseproblem als ökonomische Problemstellung interpretieren? (1 Punkt) c) Bestimmen Sie bitte für das durch den folgenden Graphen gegebene Rundreiseproblem eine Lösung mit Hilfe des Verfahrens Nächster Nachbar“. Erläutern Sie dabei ” auch das allgemeine Vorgehen beim Verfahren. Beginnen Sie das Verfahren bitte in Knoten 1. (3 Punkte) 2 3 6 3 3 1 1 2 4 4 d) Erläutern Sie bitte das 2-opt-Verfahren allgemein. Gehen Sie dabei insbesondere auf die Komponenten des Verfahrens ein. (4 Punkte) e) Verbessern Sie bitte die in c) gefundene Lösung mit Hilfe einer Iteration des 2-optVerfahrens. Stellen Sie Ihren Rechenweg ausführlich dar. (3 Punkte) f) Zeigen Sie bitte, dass der folgende Graph G nicht hamiltonsch ist! (3 Punkte) Operations Research 3 Aufgabe 3 a) Ihnen sei ein Standard-Transportproblem mit 4 Anbietern A1 , . . . , A4 und 3 Nachfragern B1 , . . . , B3 gegeben. Die Transportkosten sowie Angebots- und Nachfragemengen entnehmen Sie bitte folgenden Tabellen. cij A1 A2 A3 A4 B1 5 6 2 3 B2 1 8 4 5 B3 3 3 5 7 bj B1 B2 B3 120 100 80 ai A1 100 A2 50 A3 70 A4 80 (i) Bestimmen Sie bitte mittels Nordwest-Ecken-Algorithmus eine Startlösung sowie dessen Zielfunktionswert und markieren Sie im zugehörigen TransportTableau die Basisvariablen dieser Lösung. (2 Punkte) (ii) Bestimmen Sie bitte nur für die Zelle (i, j) = (3, 1) einen zu ihrer Startlösung gehörenden elementaren Kreis, wie Sie es im Stepping-Stone-Algorithmus tun müssten und markieren ihn in Ihrem vorherigen Transport-Tableau. Berechnen Sie bitte c̄31 und überlegen Sie zudem, welchen Einfluss die Aufnahme der Variablen x31 in die Menge der Basisvariablen auf den Zielfunktionswert hätte. Führen Sie bitte einen Basiswechsel gemäß dem Stepping-Stone-Algorithmus durch und geben Sie das neue Transport-Tableau an. (5 Punkte) b) Erinnern Sie sich an das kostenminimale Zuordnungsproblem (Matching-Problem)? Gegeben sei eine Menge von n Maschinen M1 , M2 , M3 , . . . , Mn sowie eine Menge von n Personen P1 , P2 , P3 , . . . , Pn . Jede dieser Maschinen soll von einer der Personen bedient werden (also nicht von mehreren). Dabei soll eine Person allerdings auch nur eine Maschine bedienen, nicht mehrere. Die Bedienung die Maschine Mj durch die Person Pi lässt Kosten cij entstehen. Gesucht wird eine Zuordnung (ein Matching“) der Personen zu den ” Maschinen derart, dass die entstehenden Gesamtkosten minimal sind. Formulieren Sie das Problem bitte als Simultan-Modell. Geben Sie dabei insbesondere (i) Zustandsvariablen und -bereiche, deren Bedeutung, (ii) Steuervariablen und -bereiche, deren Bedeutung, (iii) Übergangsfunktionen und (iv) Kostenfunktionen und Zielfunktion an. (8 Punkte) Operations Research 4