Besprechung 04: Sonderfälle & Graphentheorie

Grundlagen Operations Research

Themen dieser Besprechung

Diese Besprechung deckt Block 3 ab: Sonderfälle linearer Optimierungsprobleme und Graphentheorie (Vorlesungen 5 und 6). Behandelte Inhalte: Dualität, Degeneration, Unzulässigkeit, Unbeschränktheit, FIFO-Algorithmus, kompakte Speicherung.

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: Sonderfälle linearer Optimierungsprobleme

Gegeben ist das folgende Optimierungsproblem:

minimiere F=4W1+2W2u.d.N.W1+W2≥2−W1−W2≥5W1,W2≥0 \begin{aligned} \text{minimiere } \; & F = 4 W_1 + 2 W_2 \\ \text{u.d.N.} \quad & W_1 + W_2 \ge 2 \\ & -W_1 - W_2 \ge 5 \\ & W_1, W_2 \ge 0 \end{aligned}

  1. Lösen Sie die duale Problemstellung mit einem geeigneten Simplexverfahren.

  2. Überführen Sie die Problemstellung in das äquivalente primale Problem.

  3. Begründen Sie, um welchen Sonderfall es sich bei der primalen Lösung des Problems handelt. Können Sie aus dem primalen Sonderfall den Sonderfall der dualen Lösung ableiten?

  4. Gegeben ist das folgende Optimierungsproblem:

minimiere F=X1+2X2u.d.N.2X1+X2≤6X1+3X2=6X1,X2≥0 \begin{aligned} \text{minimiere } \; & F = X_1 + 2 X_2 \\ \text{u.d.N.} \quad & 2 X_1 + X_2 \le 6 \\ & X_1 + 3 X_2 = 6 \\ & X_1, X_2 \ge 0 \end{aligned}

Überführen Sie die Problemstellung in das äquivalente duale Problem.

  1. Überprüfen Sie Ihre Ergebnisse aus Aufgabenteil d) in Julia, indem Sie jeweils das primale und das duale Problem lösen. Was fällt Ihnen bei den Simplex-Multiplikatoren und den Werten der Entscheidungsvariablen auf?

Aufgabe 2: Graphentheorie

Gegeben ist der folgende Graph:

  1. Nennen Sie Quelle und Senke im Graphen.

  2. Stellen Sie die kompakte Speicherung des Graphen auf.

  3. Finden Sie den schnellsten Weg von Knoten 1 zu Knoten 6. Verwenden Sie dabei den FIFO-Algorithmus. Lösen Sie das Problem erneut, diesmal mit dem FIFO-LIFO-Algorithmus. In welchem Verfahren benötigen Sie weniger Iterationen?

  4. Überprüfen Sie Ihren schnellsten Weg in Julia.