Dualität und Schattenpreise
Die lineare Optimierung liefert den besten Produktionsplan. Für die Planung ist aber oft eine zweite Frage genauso wichtig: Was ist eine zusätzliche Stunde an einer Engpass-Maschine wert? Die Antwort sind die Schattenpreise. Sie lösen ein eigenes Optimierungsproblem, das zum ursprünglichen gehört wie ein Spiegelbild – das duale Problem.
Ein Beispiel
Eine Holzwerkstatt baut Kinderstühle (Anzahl $x$, Deckungsbeitrag 25 € je Stück) und Hocker ($y$, 20 € je Stück). In der Säge braucht ein Stuhl 3 Stunden, ein Hocker 2; in der Lackiererei 1 bzw. 2 Stunden. Pro Monat stehen 120 Sägestunden und 80 Lackierstunden zur Verfügung, und mehr als 30 Stühle kann die Montage nicht schaffen:
Bester Plan: 20 Stühle und 30 Hocker mit einem Deckungsbeitrag von 1.100 €.
Was bringt eine Stunde mehr?
Bekäme die Werkstatt eine Sägestunde mehr (121 statt 120), verschöbe sich die beste Ecke ein wenig: Aus $3x + 2y = 121$ und $x + 2y = 80$ folgt $x = 20{,}5$ und $y = 29{,}75$, also $z = 25 \cdot 20{,}5 + 20 \cdot 29{,}75 = 1.107{,}50\,€$. Die Stunde ist 7,50 € wert – das ist der Schattenpreis der Säge. Genauso bringt eine zusätzliche Lackierstunde 2,50 €. Eine zusätzliche Montagemöglichkeit bringt nichts (Schattenpreis 0), denn dort ist ohnehin noch Platz.
Schattenpreis einer Nebenbedingung: Um so viel steigt der optimale Zielwert, wenn ihre rechte Seite um eine Einheit wächst. Er ist die Obergrenze dessen, was sich für eine zusätzliche Einheit dieser Kapazität zu zahlen lohnt – etwa für Überstunden oder eine gemietete Maschine.
Schattenpreise gelten nur, solange dieselben Bedingungen die beste Ecke bilden. In unserem Beispiel ist $x = \frac{b_1 - 80}{2}$, wenn die Säge $b_1$ Stunden hat. Ab $b_1 = 140$ wäre $x = 30$ erreicht, und die Montage würde zum neuen Engpass. Zwischen 80 und 140 Sägestunden bringt also jede weitere Stunde 7,50 €, darüber nichts mehr.
Das duale Problem
Die Schattenpreise $y_1, y_2, y_3$ kann man auch direkt als Lösung eines eigenen Problems bestimmen. Man stellt sich vor, ein Käufer möchte der Werkstatt ihre gesamten Kapazitäten abkaufen. Er bewertet jede Stunde mit einem Preis und will insgesamt möglichst wenig zahlen. Die Werkstatt verkauft aber nur, wenn sie für die Stunden eines Stuhls mindestens dessen Deckungsbeitrag bekommt – und ebenso beim Hocker:
Beim Aufstellen werden Zeilen zu Spalten: Aus jeder Nebenbedingung wird eine Variable, aus jeder Variablen eine Bedingung, aus „max“ wird „min“ und aus „≤“ wird „≥“. Die Lösung ist $y_1 = 7{,}5$, $y_2 = 2{,}5$, $y_3 = 0$ mit $w = 120 \cdot 7{,}5 + 80 \cdot 2{,}5 = 1.100$ – genau der maximale Deckungsbeitrag.
Schattenpreise im Simplex-Tableau
Wer mit dem Simplex-Verfahren rechnet, bekommt die Schattenpreise geschenkt: Im Endtableau stehen sie in der Zielzeile unter den Schlupfvariablen $u_1, u_2, \dots$. Die Einträge unter den eigentlichen Variablen heißen reduzierte Kosten; sie geben an, wie viel der Zielwert sinkt, wenn man ein bisher nicht hergestelltes Produkt in den Plan zwingt.
Rechner: Schattenpreise und duales Problem
Übung: Schattenpreise
Stufe 2: Dualität und Zusatzkapazität
-
Aufgabe 1
Ein Betrieb stellt die Produkte A und B her (Deckungsbeitrag 68 € bzw. 56 € je Stück). Maschine 1: 2 h je A, 2 h je B, 510 h verfügbar. Maschine 2: 4 h je A, 3 h je B, 840 h verfügbar. Optimal sind 75 Stück A und 180 Stück B. Die Schattenpreise sind y1 = 10 €/h und y2 = 12 €/h. Berechne den Wert des dualen Problems w = 510·y1 + 840·y2 und vergleiche mit dem maximalen Deckungsbeitrag.€w = 510 · 10 + 840 · 12 = 15.180 €
z max = 68 · 75 + 56 · 180 = 15.180 € – beide Werte sind gleich (Dualität). -
Aufgabe 2
Ein Betrieb stellt die Produkte A und B her (Deckungsbeitrag 20 € bzw. 40 € je Stück). Maschine 1: 3 h je A, 4 h je B, 560 h verfügbar. Maschine 2: 1 h je A, 4 h je B, 240 h verfügbar. Optimal sind 160 Stück A und 20 Stück B. Die Schattenpreise sind y1 = 5 €/h und y2 = 5 €/h. Um wie viel Euro steigt der maximale Deckungsbeitrag, wenn Maschine 1 2 Stunden länger laufen kann?€Zuwachs = 2 h · 5 €/h = 10 €
(Die neue Lösung 161 A und 19,75 B nutzt weiter beide Maschinen voll.) -
Aufgabe 3
Ein Betrieb stellt die Produkte A und B her (Deckungsbeitrag 40 € bzw. 50 € je Stück). Maschine 1: 5 h je A, 5 h je B, 1175 h verfügbar. Maschine 2: 3 h je A, 4 h je B, 770 h verfügbar. Optimal sind 170 Stück A und 65 Stück B. Die Schattenpreise sind y1 = 2 €/h und y2 = 10 €/h. Um wie viel Euro steigt der maximale Deckungsbeitrag, wenn Maschine 2 5 Stunden länger laufen kann?€Zuwachs = 5 h · 10 €/h = 50 €
(Die neue Lösung 165 A und 70 B nutzt weiter beide Maschinen voll.)
Tippe nur die Zahl ein – die Einheit steht schon daneben. Dezimalzahlen mit Komma (2,5), Zeiten als 2 h 15 min, Uhrzeiten als 14:35. Punkte: 10 für richtig beim ersten Versuch, 6 nach einem Fehlversuch, 5 mit Tipp. Deine Punkte siehst Du unter Mein Training.
Arbeitsblatt: Schattenpreise und duales Problem
Eine volle DIN-A4-Seite Aufgaben mit Lösungsblatt zum Ausdrucken – bei jedem Klick neue Aufgaben. Klasse 12–13.
Weiter geht’s
- Rechner für lineare Optimierung – grafisch und mit allen Simplex-Schritten
- Lineare Gleichungssysteme – Schattenpreise als Lösung eines LGS
- Verflechtung (Leontief) – Matrizen in der Produktionsplanung
Weiterlesen: Schattenpreis, Dualität (Mathematik), Komplementärer Schlupf bei Wikipedia