Besprechung 02: Grafische Lösung & primaler Simplex

Grundlagen Operations Research

Themen dieser Besprechung

Diese Besprechung deckt Block 1 ab: grafische Lösung linearer Optimierungsprobleme und den primalen Simplex-Algorithmus (Vorlesungen 1 und 2). Behandelte Inhalte: LOP, grafische Lösung, primaler Simplex, Simplex-Multiplikatoren.

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: Grafische Lösung

Gegeben ist das folgende Optimierungsproblem:

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

1. Lösen Sie das Optimierungsproblem grafisch.

2. Wie lautet die Lösung bei einer Minimierung des Optimierungsproblems?

3. Überführen Sie das Optimierungsproblem in ein Gleichungssystem.

4. Benötigen Sie alle Nebenbedingungen, um den zulässigen Bereich des Lösungsraumes zu beschränken?

5. Überprüfen Sie Ihre Lösung in Julia.

Aufgabe 2: Primaler Simplex

Gegeben ist das folgende Optimierungsproblem:

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

1. Lösen Sie das Optimierungsproblem mit dem primalen Simplex-Algorithmus.

2. Überprüfen Sie Ihre Lösung der Maximierung grafisch.

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

4. Überprüfen Sie Ihre Lösung in Julia.

5. Ihnen ist zusätzlich die Nebenbedingung $X_1 \le 4$ mit $X_1 \in \mathbb{Q}$ gegeben. Wie können Sie diese Nebenbedingung in einem allgemeinen linearen Optimierungsproblem abbilden?