Besprechung 03: Dualer Simplex & Zweiphasenmethode

Grundlagen Operations Research

Themen dieser Besprechung

Diese Besprechung deckt Block 2 ab: den dualen Simplex-Algorithmus sowie Dualität und die Zweiphasenmethode (Vorlesungen 3 und 4). Behandelte Inhalte: primaler Simplex, dualer Simplex, Schlupfvariablen, grafische Lösung, reduzierte Kosten, Dualität, Zweiphasenmethode.

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.
• Sie wählen frei, welche Aufgabe Sie vorstellen möchten. 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: Dualer Simplex

Gegeben ist das folgende Optimierungsproblem:

$$\begin{aligned} \text{minimiere } \; & F = 4 X_1 + X_2 \\ \text{u.d.N.} \quad & 3 X_1 + X_2 \ge 12 \\ & X_1 + X_2 \ge 6 \\ & X_1 \ge 3 \\ & X_1, X_2 \ge 0 \end{aligned}$$

1. Lösen Sie das Optimierungsproblem mit den geeigneten Simplexverfahren.

2. Nennen Sie für jede Iteration des Simplex-Algorithmus die zugehörigen Simplex-Multiplikatoren.

3. Überprüfen Sie Ihre Lösung der Minimierung grafisch.

4. Was passiert mit dem Zielfunktionswert, wenn Sie die Ressource der zweiten Nebenbedingung ($X_1 + X_2 \ge 6$) um eine Einheit erhöhen? Was passiert, wenn Sie sie um eine Einheit senken? Begründen Sie Ihre Entscheidung kurz.

Aufgabe 2: Dualität und die Zweiphasenmethode

Gegeben ist das folgende Optimierungsproblem:

$$\begin{aligned} \text{maximiere } \; & F = 5 X_1 - 2 X_2 + 4 X_3 \\ \text{u.d.N.} \quad & 2 X_1 + X_2 - X_3 \le 6 \\ & X_1 - X_2 + 2 X_3 \ge 5 \\ & 3 X_1 + X_2 - 4 X_3 \ge 4 \\ & X_1, X_2, X_3 \ge 0 \end{aligned}$$

1. Lösen Sie das Optimierungsproblem mit der Zweiphasenmethode.

2. Dualisieren Sie die Problemstellung.

3. Überprüfen Sie die Lösung der dualisierten Problemstellung in Julia.