Besprechung 05: Transport & ganzzahlige Optimierung

Grundlagen Operations Research

Themen dieser Besprechung

Diese Besprechung deckt Block 4 ab: das Transportproblem und die ganzzahlige Optimierung (Vorlesungen 7 und 8). Behandelte Inhalte: Kruskal-Algorithmus, 1-Bäume, Vogelsche Approximationsmethode, MODI-Methode, Branch-&-Bound-Verfahren.

WichtigBonuspunkte in den Besprechungen

• Sie können die freiwilligen Aufgaben der Aufgabensammlung in den Besprechungen vorstellen und sich dafür bis zu 2 Bonuspunkte für die Klausur verdienen.
• Vorstellen können Sie nur Aufgaben, die Ihnen in STiNE zugewiesen wurden.
• Möchten mehrere Studierende dieselbe Aufgabe vorstellen, entscheidet ein Losverfahren.
• Bereiten Sie sich so vor, dass Sie Ihre Ergebnisse zeigen können (Live-Rechnung, Fotos, Präsentation — ganz wie Sie möchten). Auch bei kleineren Fehlern sind Bonuspunkte möglich, wenn Sie sich ernsthaft mit der Aufgabe auseinandergesetzt haben.
• Die Lehrenden leiten die Diskussion, präsentieren aber keine Lösungen.

Aufgaben aus der Aufgabensammlung

Die folgenden Aufgaben sind freiwillig. Sie können sie in der Besprechung vorstellen (siehe Hinweise oben). Lösungen werden hier nicht veröffentlicht.

Aufgabe 1: Minimal spannende Bäume und das Transportproblem

1. Bestimmen Sie die minimalen 1-Bäume für die alternativen Wurzelknoten $i = 3$ und $i = 9$.

2. Gegeben ist das folgende Transportproblem:

Bestimmen Sie mit der Vogelschen Approximationsmethode eine Startlösung. Wenden Sie anschließend die MODI-Methode an, um die Startlösung zu überprüfen und gegebenenfalls zu verbessern.

3. Überprüfen Sie Ihre Lösung des Transportproblems in Julia.

Aufgabe 2: Ganzzahlige Optimierung

Gegeben ist folgender Branch-&-Bound-Baum. Alle Teilprobleme, die nicht weiter verzweigt wurden, sind unzulässig („unzul.”) oder weisen eine ganzzahlige Lösung auf. Jeder Kasten zeigt das Teilproblem $P_i$ und seine Schranke $\underline{F}_i$:

1. Handelt es sich um ein Minimierungs- oder um ein Maximierungsproblem?

2. Welche Knoten und in welcher Reihenfolge werden bei der Breitensuche betrachtet? Verzweigen Sie immer zuerst nach rechts. Nennen Sie darüber hinaus immer die aktuelle globale Schranke und geben Sie an, welche Probleme ausgelotet worden sind. Verwenden Sie folgende Begründungen:

• a: Der Zielfunktionswert ist größer oder gleich der aktuellen globalen Schranke.
• b: Die Lösung des relaxierten Teilproblems ist zulässig für das unrelaxierte Teilproblem und liefert eine verbesserte Schranke.
• c: Die optimale Lösung des relaxierten Teilproblems ist unzulässig.

3. Welche Knoten und in welcher Reihenfolge werden bei der verzweigten Tiefensuche mit der Minimum-Lower-Bound-Regel betrachtet? Verzweigen Sie immer zuerst nach links. Verwenden Sie ebenfalls die Begründungen a–c beim Ausloten und nennen Sie die globalen Schranken.