Klausur Logistik II SS 04 (neue PO) Prof. Dr. Bernhard Fleischmann - Lehrstuhl für Produktion und Logistik - Universität Augsburg B. Becker ist Bäcker. Seine Bäckerei bendet sich im Knoten 1. Er beliefert jeden Morgen seine Filialen (Knoten 2 bis 7) mit einem Lieferwagen. Die Kantenbewertungen geben die Längen möglicher Straÿenverbindungen in [km] an. 7 2 4 4 1 1 6 5 3 3 7 4 5 2 6 3 9 7 5 1. (50 Minuten) a) Bestimmen Sie für Herrn Becker mit der Heuristik des Besten Nachfolgers eine zulässige Rundreise, die bei Knoten 1 beginnt und endet! Geben Sie die Länge der Rundreise an! b) Nennen Sie zwei weitere Heuristiken, mit denen man symmetrische Traveling Salesman Probleme lösen kann! c) Berechnen Sie eine untere Schranke für die optimale Rundreise mit Hilfe der 1-Baum- Relaxation, wobei Knoten 1 im Zyklus enthalten sein soll! Geben Sie unter Verwendung des Ergebnisses aus 1.a) ein Intervall [LB; UB] an, in dem die Länge der optimalen Rundreise liegt! Welcher relative GAP folgt daraus? d) Einige Kunden von Herrn Becker wohnen in den Straÿen, die im Graph oben eingezeichnet sind. Er überlegt sich, einen Direktbelieferungsservice für diese Kunden einzurichten, falls die zurückzulegende Entfernung dabei nicht zu groÿ wird. Bestimmen Sie dazu eine optimale Briefträgertour! Geben Sie die Länge an! e) Beckers Bäckerei expandiert, weshalb sich der Bedarf der sechs Filialen bald verdoppeln wird. Sie bekommen dann je 10 Kisten Gebäck, wobei der Lieferwagen nur Kapazität für insgesamt 30 Kisten hat. Deshalb kauft Becker einen zweiten Lieferwagen, ebenfalls mit der Kapazität von 30 Kisten. Zudem sollen die Filialen 2 und 3 beide als erstes um genau 6:00 Uhr beliefert werden, weshalb Becker bereits folgenden unvollständigen Tourenplan notiert hat: Tour 1: 1 - 2 - ... - 1 Tour 2: 1 - 3 - ... - 1 Sie haben gehört, dass man anstelle des Savings-Verfahrens auch das Einfüge-Verfahren zur Erstellung eines Tourenplans verwenden kann, wobei Sie nacheinander die Knoten 4, 5, 6, 7 in Beckers Tourenplan einfügen wollen. Erläutern Sie dafür eine parallele und eine sequentielle Vorgehensweise! Keine Rechnung erforderlich! (Bitte wenden!) 1 Klausur Logistik II SS 04 (neue PO) Prof. Dr. Bernhard Fleischmann - Lehrstuhl für Produktion und Logistik - Universität Augsburg 2. (40 Minuten) Im selben Straÿennetz wie bei Aufgabe 1 hat ein Kurierdienst (Depot D entspricht Knoten 1) heute 3 Fahraufträge (A1, A2, A3) zu erledigen, nämlich von 5 nach 7 (A1), von 3 nach 4 (A2) und von 1 nach 6 (A3). Die Aufträge sollen von nur einem Fahrzeug nacheinander ausgeführt werden, da ein Auftrag das Fahrzeug jeweils komplett auslastet. Da es keine Einschränkungen hinsichtlich der Reihenfolge gibt, bieten die Leerfahrten zwischen den Aufträgen Optimierungspotenzial. Hierzu wurde bereits folgende (asymmetrische) Leerfahrten-Matrix aufgestellt: nach D A1 A2 A3 von D ∞ 11 3 0 A1 6 ∞ 3 6 A2 9 2 ∞ 9 A3 5 12 4 ∞ a) Geben Sie, ausgehend von dieser Matrix, eine untere Schranke für die Leerfahrten an, indem Sie die Lower Bound Berechnung nach dem Branch & Bound Verfahren von Little anwenden! b) Verzweigen Sie das Ausgangsproblem (P0 ) und berechnen Sie die Lower Bounds für die beiden entstehenden Teilprobleme! Verwenden Sie dazu die Spezikation des Branch & Bound Verfahrens von Little! (Keine weiteren Verzweigungen verlangt!) c) Mittels einer Heuristik wird nun die zulässige Auftragsabfolge D → A3 → A2 → A1 → D mit Leerfahrtenlänge 12 ermittelt. Ist diese zulässige Lösung auch optimal ? Begründen Sie anhand eines kleinen B&B Entscheidungsbaums der folgenden Form unter Verwendung der Ergebnisse aus b). P0 P1 P2 Viel Erfolg! 2
© Copyright 2024 ExpyDoc