Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Jedes LP hat einen Zwilling — und der ist Gold wert. Dualität ist eine der mächtigsten Konzepte in der mathematischen Optimierung — Klausurpflicht in 5/8 OR-Programmen, oft mit Schattenpreis-Aufgaben.
Klausur-Tipp: Bei "Berechnen Sie die Schattenpreise" IMMER das Dual aufstellen + an aktiven Restriktionen lösen (per Komplementärem Schlupf). Schattenpreis = Wert einer zusätzlichen Einheit der Ressource. Bei inaktiver Restriktion ist Schattenpreis automatisch 0.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Jedes LP hat einen Zwilling — und der ist Gold wert. Dualität ist eine der mächtigsten Konzepte in der mathematischen Optimierung — Klausurpflicht in 5/8 OR-Programmen, oft mit Schattenpreis-Aufgaben.
Dualität: Zu jedem LP (Primal) gibt es ein zweites LP (Dual), dessen Lösung den gleichen Optimalwert hat — und dessen Variablen die Schattenpreise der Ressourcen sind.
Gegeben Primal-Problem in Standardform:
max z = c^T x s.t. A x ≤ b, x ≥ 0
Dann ist das Dual-Problem:
min w = b^T y s.t. A^T y ≥ c, y ≥ 0
| Primal (max) | Dual (min) |
|---|---|
Zielfunktion: max c^T x | Zielfunktion: min b^T y |
A x ≤ b | A^T y ≥ c |
x ≥ 0 | y ≥ 0 |
m Restriktionen | m Variablen |
n Variablen | n Restriktionen |
Eselsbrücke "Vertauschen":
c ↔ RHS bA wird transponiert: A → A^T≤ ↔ ≥Primal (Produktions-Sicht):
max z = 3 x₁ + 5 x₂
unter:
2 x₁ + 1 x₂ ≤ 8; 1 x₁ + 3 x₂ ≤ 12; x₁, x₂ ≥ 0
Dual (Ressourcen-Bewertungs-Sicht):
min w = 8 y₁ + 12 y₂
unter:
2 y₁ + 1 y₂ ≥ 3; 1 y₁ + 3 y₂ ≥ 5; y₁, y₂ ≥ 0
Interpretation:
y₁, y₂ = Schattenpreise der RessourcenFür JEDE zulässige Primal-Lösung
xund Dual-Lösungygilt:
c^T x ≤ b^T y
(bei max-min-Paar)
Bedeutung: Jede Dual-Lösung gibt eine obere Schranke für das Primal-Optimum.
Wenn beide Probleme zulässig und beschränkt sind, gilt im Optimum:
c^T x^* = b^T y^*
z = w**. Beide Probleme haben denselben Optimalwert.
Im Optimum gilt für alle i, j:
y_i^* · (b_i - a_i^T x^*) = 0 und x_j^* · (a^T_j y^* - c_j) = 0
Bedeutung:
a_i^T x^* = b_i) → entsprechende Dual-Variable kann > 0 seina_i^T x^* < b_i) → entsprechende Dual-Variable ist = 0Das ist die wichtigste Konsequenz der Dualität: Schattenpreis einer Ressource im Überfluss ist 0.
Schattenpreis
y_i^*= Wert einer zusätzlichen Einheit der Ressourcei.
Konkret: Wenn man b_i um 1 erhöht, steigt z^* um y_i^* (innerhalb des Sensitivitäts-Bereichs).
Anwendung:
| Primal (max) | Dual (min) |
|---|---|
a_i^T x ≤ b_i | y_i ≥ 0 |
a_i^T x ≥ b_i | y_i ≤ 0 |
a_i^T x = b_i | y_i frei |
x_j ≥ 0 | a_j^T y ≥ c_j |
x_j ≤ 0 | a_j^T y ≤ c_j |
x_j frei | a_j^T y = c_j |
Symmetrie: Dual des Duals = Primal. Daher: man kann zwischen Sichten beliebig wechseln.
Was passiert mit z^*, wenn man die Daten ändert?
b_i)In gewissem Bereich ändert sich z^* linear:
Δ z^* = y_i^* · Δ b_i
Außerhalb des Bereichs werden andere Restriktionen aktiv — Schattenpreis ändert sich.
c_j)In gewissem Bereich bleibt die Basis-Lösung optimal, z^* ändert sich linear:
Δ z^* = x_j^* · Δ c_j
1. Konstruktions-Regel: A → A^T, c ↔ b, max → min, ≤ → ≥.
2. Starke Dualität: z^* = w^*. Beide Probleme haben denselben Optimalwert.
3. Komplementärer Schlupf: Aktive Restriktion → y_i^* > 0 möglich. Inaktive Restriktion → y_i^* = 0.
4. Schattenpreis = Wert pro Einheit der Ressource. Antwort auf "Wieviel sind 1 zusätzliche h Maschine wert?"
5. Dual des Duals = Primal. Daher beliebige Sicht-Wechsel möglich.
6. Anzahl Variablen ↔ Anzahl Restriktionen. Primal n Variablen + m Restriktionen → Dual m Variablen + n Restriktionen.
1. Konstruktion vergessen, A zu transponieren. A^T ist Pflicht — sonst gibt es das falsche Dual.
2. RHS und Zielfunktion-Koeffizienten verwechseln. b wird Zielfunktion im Dual, c wird RHS im Dual. Häufiges Versehen.
3. Schattenpreis aus inaktiver Restriktion berechnen. Wenn Restriktion i inaktiv ist (a_i^T x^* < b_i), dann ist y_i^* = 0. Mehr Ressource bringt nichts.
4. Schwache vs. starke Dualität verwechseln. Schwach: c^T x ≤ b^T y für ALLE Paare. Stark: c^T x^* = b^T y^* NUR im Optimum.
5. Sensitivitäts-Bereich ignorieren. Δ z^* = y_i^* · Δ b_i gilt nur in gewissem Bereich. Bei großen Änderungen muss neu gerechnet werden.
6. Dual-Variable als negative Zahl bei ≤-Restriktion. Bei max-Problem mit ≤-Restriktion: y_i ≥ 0. Bei ≥: y_i ≤ 0. Bei =: y_i frei.
Sieh wie sich Primal-LP und Dual-LP verhalten — RHS-Slider verändert die Ressourcen, beide Probleme aktualisieren sich live + Schattenpreise zeigen den Effekt.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei "Berechnen Sie die Schattenpreise" IMMER das Dual aufstellen + an aktiven Restriktionen lösen (per Komplementärem Schlupf). Schattenpreis = Wert einer zusätzlichen Einheit der Ressource. Bei inaktiver Restriktion ist Schattenpreis automatisch 0.
6 Aufgaben zu Primal-Dual-Konstruktion, Schattenpreisen und Sensitivität.
Klausurfragen mit Lösungen (6)
Antwort: min b^T y mit A^T y ≥ c und y ≥ 0
Erklärung: Standard-Konstruktion: max c^T x mit Ax ≤ b → min b^T y mit A^T y ≥ c. Beachte: max ↔ min, A ↔ A^T, c ↔ b, ≤ ↔ ≥. Alle Vorzeichen y ≥ 0 wenn x ≥ 0 im Primal.
Antwort: z*_Primal = w*_Dual im Optimum
Erklärung: Starke Dualität: Wenn beide Probleme zulässig und beschränkt sind, dann z*_Primal = w*_Dual im Optimum. Beide haben denselben Optimalwert. Schwache Dualität: c^T x ≤ b^T y für ALLE Paare (nicht nur Optimum). Bei max-min-Konstellation.
Zuordnungen:
Erklärung: Primal-Dual-Mapping: c ↔ b (vertauschen), A ↔ A^T (transponieren), max ↔ min. Vorzeichen: bei max-LP mit ≤-Restriktion entspricht y_i ≥ 0 (positiver Schattenpreis). Anzahl Variablen Primal ↔ Anzahl Restriktionen Dual.
Typ: Zuordnung
Antwort: y_1 = 0 (Komplementärer Schlupf)
Erklärung: Komplementärer Schlupf: y_i · (b_i − a_i^T x*) = 0. Wenn Restriktion inaktiv (b_i − a_i^T x* > 0), muss y_i = 0 sein. Interpretation: Ressource im Überfluss hat Schattenpreis 0 — eine zusätzliche Einheit bringt nichts. Klausur-Klassiker mit Aussage zu Engpass-Identifikation.
Antwort: Wahr
Erklärung: RICHTIG. Schattenpreis y_i = ∂z*/∂b_i. Δz* = y_i · Δb_i. Anwendung: Wieviel sind 1 h zusätzliche Maschinen-Kapazität wert? Antwort = Schattenpreis. Wichtig: Sensitivitäts-Bereich begrenzt — bei zu großer Änderung wechselt die optimale Basis, Schattenpreis ändert sich.
Typ: Wahr/Falsch
Antwort: Das ursprüngliche Primal-LP
Erklärung: Dualität ist symmetrisch: Dual(Dual(P)) = P. Daher kann man bei Bedarf zwischen Primal- und Dual-Sicht beliebig wechseln. Vorteil: manche Probleme sind im Dual einfacher zu lösen (z.B. weniger Variablen, einfachere Restriktionen).
6 typische Klausurfragen zu Dualitätstheoremen, Schattenpreisen und Komplementärem Schlupf.
Klausurfragen mit Lösungen (6)
Antwort: m
Erklärung: Dual hat IMMER eine Variable pro Primal-Restriktion. Also m Dual-Variablen. Umgekehrt: m Dual-Restriktionen (eine pro Primal-Variable). Anzahl Variablen ↔ Anzahl Restriktionen ist eine Schlüssel-Eigenschaft der Dualität.
Antwort: c^T x ≤ b^T y für alle zulässigen x, y (bei max-min)
Erklärung: Schwache Dualität: c^T x ≤ b^T y für JEDES Paar zulässiger Lösungen (max-min-Setup). Damit ist Dual-Wert eine OBERE Schranke fürs Primal-Maximum. Starke Dualität (Antwort B) gilt nur IM OPTIMUM. Beide Theoreme zusammen: Primal-Maximum + Dual-Minimum sind gleich.
Lösungen pro Lücke:
Erklärung: Dual-Konstruktion: A → A^T (transponiert), c ↔ b (vertauscht), max ↔ min, ≤ ↔ ≥. Schattenpreise = Dual-Variablen y_i. Diese 4 Schritte musst du blind beherrschen — Klausur-Standard.
Typ: Lückentext
Richtige Reihenfolge:
Erklärung: Hierarchie: 1) Schwache Dualität — gilt für ALLE zulässigen Paare (Grundaussage). 2) Starke Dualität — Folgerung: im Optimum sind Werte gleich. 3) Komplementärer Schlupf — präzise Aussage zu aktiven Restriktionen ↔ positiven Schattenpreisen (folgt aus starker Dualität). Theoreme bauen aufeinander auf.
Typ: Reihenfolge
Antwort: y₁ = 0 (Restriktion ist NICHT aktiv: 2·4 + 3·2 = 14)
Erklärung: Restriktion-Wert: 2·4 + 3·2 = 14 = RHS. Restriktion IST aktiv (mit Gleichheit). Bei aktiver Restriktion KANN y₁ > 0 sein (muss aber nicht). Falls Aufgabe sagt 2·4 + 3·2 = 14 < 18, dann inaktiv → y₁ = 0 zwingend. Im Beispiel hier: 14 = 14, also aktiv, also y₁ ≥ 0 (nicht eindeutig).
Antwort: Wahr
Erklärung: RICHTIG. Δz* = y_i · Δb_i gilt nur, solange die optimale BASIS (welche Restriktionen aktiv sind) gleich bleibt. Bei großen Änderungen ändern sich aktive Restriktionen → Schattenpreis springt auf neuen Wert. Sensitivitäts-Analyse berechnet den Bereich [b_i^min, b_i^max], in dem y_i konstant bleibt. Klausur-Anwendung: 'Ist der Kauf von 100 zusätzlichen Stunden lohnend?' Nicht direkt y_i · 100 — sondern erst prüfen ob 100 im Sensitivitäts-Bereich.
Typ: Wahr/Falsch