Schattenpreise und Dualität verständlich erklärt
Ein Lager überlegt, ob es sich lohnt, eine zusätzliche Arbeitsstunde zu bezahlen. Was diese Stunde dem Lager einbringt, lässt sich ausrechnen. Doch die Zahl gilt nur ein Stück weit. Wer sie weiter hochrechnet, rechnet falsch.
Zuletzt aktualisiert:
Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.
Ein Lager mit drei knappen Dingen
Stellen Sie sich ein kleines Versandlager vor. Es verschickt zwei Sorten von Sendungen, Eilpakete und Paletten. Ein Eilpaket bringt 3 Gewinn, eine Palette 5.
Drei Dinge sind knapp. Von jedem gibt es nur einen festen Vorrat:
- Zeit an der Laderampe, wo die Lastwagen halten. Sie reicht für höchstens vier Eilpakete. Paletten brauchen sie nicht.
- Arbeitsstunden, in denen Mitarbeiter die Ware zusammensuchen. Es gibt 12. Eine Palette braucht zwei Stunden, ein Eilpaket keine.
- Lagerplätze. Es gibt 18. Ein Eilpaket belegt drei, eine Palette zwei.
Das Lager ist ein vereinfachtes Rechenbild (Fachwort: Modell). Es kennt nur Gewinn und Verbrauch. Beides wächst gleichmäßig mit der Menge, und Mengen dürfen Bruchteile sein. Die Aussagen in diesem Teil beschreiben dieses Rechenbild, nicht die Wirklichkeit.
Der beste Plan
Ein Rechenverfahren findet die beste Mischung: zwei Eilpakete und sechs Paletten. Das bringt 36 Gewinn. Alle 12 Stunden und alle 18 Plätze sind dann verbraucht. An der Rampe bleibt Zeit für zwei weitere Eilpakete übrig.
Was eine zusätzliche Einheit wert ist
Ein Verleiher bietet eine zusätzliche Arbeitsstunde an. Wie viel darf sie das Lager höchstens kosten? Das hängt davon ab, wie viel Gewinn sie dem besten Plan zusätzlich einbringt. Diese Zahl nennen wir den Wert einer zusätzlichen Einheit.
Lagerplatz. Drei zusätzliche Plätze lassen ein weiteres Eilpaket zu, denn die Rampe hat noch Zeit dafür. Das bringt 3 Gewinn. Jeder zusätzliche Platz ist also einen Gewinn von eins wert.
Arbeitsstunden. Zwei zusätzliche Stunden erlauben eine Palette mehr: 5 Gewinn. Die Palette belegt aber zwei Plätze, und die fehlen den Eilpaketen. Diese zwei Plätze hätten den Eilpaketen einen Gewinn von zwei gebracht. Zwei Stunden bringen also nur 3. Eine einzelne Stunde ist damit anderthalb wert. Der Verleiher darf höchstens anderthalb je Stunde verlangen. Bei einem Preis von zwei je Stunde lohnt sich das Zukaufen für dieses Lager nicht.
Rampenzeit. Sie wird schon jetzt nicht ganz gebraucht. Zusätzliche Zeit bringt nichts, ihr Wert ist null.
Fachleute nennen den Wert einer zusätzlichen Einheit Schattenpreis. Er sagt, bis zu welchem Preis sich das Zukaufen lohnen kann.
Zwei Rechnungen, ein Ergebnis
Mit diesen Werten lässt sich der Gewinn auch auf einem zweiten Weg ausrechnen. Eine Palette verbraucht zwei Stunden, die zusammen 3 wert sind, und zwei Plätze, die zusammen zwei wert sind. Das ergibt 5, genau ihren Gewinn. Ein Eilpaket verbraucht drei Plätze. Auch das ergibt 3, genau seinen Gewinn.
Zählt man den Wert aller Vorräte zusammen, kommt der Gewinn heraus. Alle Stunden sind 18 wert, alle Plätze 18, zusammen 36. Das ist eine Probe auf den Plan: Stimmen beide Summen überein, kann kein anderer Plan mehr Gewinn bringen. Fachleute nennen diese Doppelrechnung Dualität. Dieselbe Aufgabe wird einmal von den Sendungen aus gerechnet und einmal von den Vorräten aus.
Wie weit gilt der Wert?
Die Werte gelten nur für kleine Änderungen. Ein Bild dafür ist ein Taxitarif: Innerhalb einer Zone kostet jeder Kilometer gleich viel. Hinter der Zonengrenze gilt ein anderer Satz.
Beim Lagerplatz gilt der Wert nur zwischen 12 und 24 Plätzen. Unter 12 Plätzen müsste das Lager Paletten streichen. Über 24 Plätzen hilft jeder weitere Platz nichts mehr. Der Grund: Mit jedem Platz mehr stellt das Lager mehr Eilpakete her. Bei 24 Plätzen sind es vier, und die Rampe ist voll.
Bei den Arbeitsstunden gilt ihr Wert bis 18 Stunden. Dann füllen allein Paletten das ganze Lager. Eine weitere Stunde bringt darüber nichts mehr.
Was passiert, wenn man viel zukauft?
Nun ein zweites, größeres Lager mit fünf Sorten und vier Vorräten. Dort ist eine Arbeitsstunde zu Beginn 5 wert. Das Lager kauft Stunden zu einem Preis von zwei je Stunde zu. Jede Stunde scheint dann 3 Gewinn zu bringen. Die Regel „Wert minus Preis, mal gekaufte Menge“ ergibt bei 135 gekauften Stunden 405 Gewinn.
Rechnet man in Etappen nach, jede mit ihrem eigenen Wert, bleiben nur 160.
Der Grund: Der Wert von 5 gilt nur für die ersten Stunden. Dann ändert sich der Plan, weil andere Vorräte zum Engpass werden. Die nächsten Stunden sind weniger wert, die letzten unter 3. Richtig ist also: bis zur Grenze kaufen, den Wert neu ausrechnen, dann weiterkaufen. Man hört auf, sobald der Wert auf den Preis von zwei gefallen ist.
Wenn zwei Grenzen zusammenfallen
Zurück zum ersten Lager. Manchmal ist der Wert nicht eindeutig. Nehmen wir an, ein Lieferwagen fasst genau so viele Sendungen, wie der beste Plan ohnehin verschickt. Dann drückt der Plan an zwei Grenzen zugleich. Zwei Stunden mehr bringen nun zwei Gewinn. Zwei Stunden weniger kosten 3.
Der Grund: Mit mehr Stunden verdrängt jede neue Palette wegen des vollen Lieferwagens ein Eilpaket. Mit weniger Stunden fällt eine Palette weg, und die frei werdenden Plätze reichen nur für Eilpakete, die weniger einbringen. Der Wert hängt also von der Richtung ab.
Auch wenn Waren von Lagern zu Kunden fahren und Angebot und Nachfrage genau aufgehen, ist der Wert nicht eindeutig. Man kann die Werte der Lager anheben und die der Kunden gleich stark senken. Die Summe der Werte bleibt dieselbe.
Wie fest ist der Plan?
Auch die Gewinne je Sendung sind in der Praxis Schätzungen. Im größeren Lager wurde 50-mal getestet. Dabei wurden alle Gewinne je Sendung zufällig leicht verändert, mit einer Streuung von 5 %. Danach wurde der beste Plan neu berechnet. In 50 % der Versuche bestimmten andere Sorten und andere Vorräte den Plan. Vermutlich ändern schon kleine Verschiebungen der Gewinne die Rangfolge der Pläne. Wie stark sich der Plan ändert, sagt die Messung nicht.
Häufige Missverständnisse
- „Wert null heißt: unwichtig.“ Nein. Die Rampe hat Wert null, weil Zeit übrig ist. Sinkt ihr Vorrat auf unter zwei, fehlt Zeit für die zwei Eilpakete des Plans, und der Gewinn sinkt.
- „Der Wert ist der Preis, den der Markt verlangt.“ Nein. Der Wert entsteht allein aus Gewinn und Verbrauch im Plan. Ein Verleiher darf mehr oder weniger verlangen.
Woran Sie das im Alltag erkennen
- Etwas ist ganz aufgebraucht, etwa Zeit vor einer Abgabe oder Geld bis Monatsende, und Sie überlegen, ob sich mehr davon lohnt.
- Die erste zusätzliche Hilfe bringt viel, die nächste weniger, und irgendwann bringt sie nichts mehr.
Wie ernst ist das Modell zu nehmen?
Beide Lager sind erfunden. Das größere ist so gebaut, dass der beste Plan und die Werte vorgegeben sind. Nichts davon wurde in einem echten Lager gemessen. Echte Lager verschicken ganze Pakete, und dann sind solche Werte schwerer zu deuten.
Was Sie mitnehmen:
- Fragen Sie vor jedem Zukauf: Ist das, wovon ich mehr will, überhaupt knapp?
- Fragen Sie bei jedem Wert nach seiner Grenze. Rechnen Sie in Etappen: bis zur Grenze, neu bewerten, weiter.
- Fragen Sie, wie sicher Ihre Gewinnzahlen sind. Hält der Plan, wenn sie etwas anders ausfallen?
Zu dieser Seite gehört eine Anwendung zum Ausprobieren im Browser, die Demo. Sie erreichen sie über den ersten Knopf unten. Dort lässt sich ein Vorrat ändern, und das Programm stellt den vorhergesagten Gewinn dem neu berechneten gegenüber. Zum Verstehen reicht dieser Text. Der zweite Knopf führt zum Teil für Fachleute mit Formeln und Messwerten.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Modell und Annahmen
Gegenstand ist die Auslastungsplanung eines Distributionszentrums als Lineares Programm: Gesucht sind Mengen \(x \ge 0\) von \(n\) Diensten, die den Gewinn \(c^\top x\) unter \(m\) Bedingungen \(a_i^\top x \le b_i\) maximieren (\(c_j\): Deckungsbeitrag je Einheit, \(a_i\): Verbrauch der Ressource \(i\), \(b_i\): ihr Bestand). Ein Teil der Instanzen hat auch Mindestmengen (Zeilen mit \(\ge\)) und Gleichungen. Das duale Programm ist \(\min b^\top y\) unter \(A^\top y \ge c\), mit \(y_i \ge 0\) bei \(\le\)-Zeilen, \(y_i \le 0\) bei \(\ge\)-Zeilen und freiem \(y_i\) bei Gleichungen. Die Zahl \(y_i\) heißt Schattenpreis der Ressource \(i\): der Wert einer zusätzlichen Einheit des Bestands \(b_i\).
- Lehrbuchbeispiel: zwei Dienste, Express-Pakete (\(x_1\), Deckungsbeitrag 3) und Palettenversand (\(x_2\), Deckungsbeitrag 5), und drei Ressourcen: Rampenzeit \(x_1 \le 4\), Kommissionierstunden (Arbeitsstunden zum Zusammenstellen der Aufträge) \(2 x_2 \le 12\), Lagerfläche (Platz im Lager) \(3 x_1 + 2 x_2 \le 18\).
- Entartete Ecke: das Lehrbuchbeispiel mit einer vierten Ressource \(x_1 + x_2 \le 8\), die durch das Optimum läuft.
- Distributionszentrum: fünf Dienste, vier Ressourcen (Kommissionierstunden, Lagerfläche, Rampenzeit, Fahrzeugkapazität), rückwärts konstruiert: Optimum \(x\) und Schattenpreise \(y\) werden vorgegeben, die Deckungsbeiträge folgen daraus als \(c_j = y^\top a_j - r_j\) mit \(r_j = 0\) für die produzierten Dienste und \(r_j = 3{,}5\) für Sperrgut und Retouren. Diese beiden sind knapp unrentabel: Sperrgut hat den Deckungsbeitrag 20, der Wert seines Verbrauchs ist \(y^\top a_j = 23{,}5\). Die vollständigen Zahlen (\(c\), \(A\), \(b\)) stehen im Quelltext der Demo (Link unter Quellen).
- Erzeugte Instanzen: Zufall (alle Ressourcen begrenzt): Deckungsbeiträge und Verbrauchskoeffizienten gleichverteilt in festen Bereichen, Verbrauchsmatrix halb besetzt (Dichte 0,5; jede Zeile und Spalte hat mindestens einen Eintrag, die erste Zeile ist dicht), Bestände gleichverteilt. Mischung (mit \(\ge\) und \(=\)): wie Zufall, aber die Bestände entstehen aus einem zulässigen Punkt, die Zeilenart ist zufällig (überwiegend \(\le\)). Transport: Lager und Kunden zufällig in einer Ebene, Kosten gleich den gerundeten Entfernungen, Nachfragen zufällige ganze Zahlen, Angebote ganzzahlig so verteilt, dass ihre Summe die Nachfrage deckt. Größen schreibt die Seite als Ressourcen × Dienste, beim Transport als Lager × Kunden; die Instanzen reichen bis 12 × 12, der Transport bis 5 × 8.
Der Löser ist ein dichter Tableau-Simplex mit Zwei-Phasen-Start, Dantzig-Regel und der Bland-Regel als Notbremse gegen Zyklen. Die Anfangsbasis besteht aus Einheitsspalten. Darum steht \(B^{-1}\) im Endtableau unter diesen Spalten und \(y\) in der Zielzeile. Als Gegenprobe dient HiGHS aus SciPy; der Löser selbst kommt ohne SciPy aus.
Die Formeln
Für die optimale Basis \(B\) (\(c_B\), \(x_B\): Deckungsbeiträge und Werte der Basisvariablen, \(a_j\): Spalte \(j\) von \(A\)) sind die Schattenpreise und die reduzierten Kosten \(r_j\) der Spalten:
\[y^\top = c_B^\top B^{-1}\]
\[r_j = y^\top a_j - c_j \ge 0\]
\(r_j \ge 0\) für alle Spalten heißt: \(y\) ist dual zulässig, die Basis optimal. Dann gelten starke Dualität (\(x^*\): optimale Menge, \(y^*\): optimale Duale) und der komplementäre Schlupf in beiden Richtungen (Schlupf: der ungenutzte Rest \(b_i - a_i^\top x\) einer Ressource):
\[c^\top x^* = b^\top y^*\]
\[y_i (b_i - a_i^\top x) = 0\]
\[x_j (a_j^\top y - c_j) = 0\]
Wird der Bestand \(b_i\) um \(\delta\) geändert (\(e_i\): \(i\)-ter Einheitsvektor), bleibt die Basis zulässig, solange gilt:
\[x_B(\delta) = x_B + \delta\, B^{-1} e_i \ge 0\]
Das liefert ein Intervall \([\delta_{\min}, \delta_{\max}]\), das Ranging der rechten Seite. Für den Deckungsbeitrag eines Dienstes gilt: Ein Dienst außerhalb der Basis bleibt draußen, solange \(c_j \le y^\top a_j\). Ein Basisdienst in Zeile \(p\) des Tableaus (\(\alpha_{pk}\): Tableau-Eintrag in Zeile \(p\), Spalte \(k\)) lässt die Basis optimal, solange für alle Nichtbasisspalten \(k\) gilt:
\[r_k + \delta\, \alpha_{pk} \ge 0\]
Bei mehreren optimalen Dualen (Entartung) bilden diese mit den oben genannten Vorzeichenbedingungen an \(y\) eine Seitenfläche, wobei \(z^*\) der Optimalwert ist:
\[\{y : A^\top y \ge c,\ b^\top y = z^*\}\]
Herleitung: warum der Schattenpreis eine Steigung ist
Standardherleitung für eine optimale, nicht entartete Basis \(B\):
- Schritt 1, Wert der Basis: Es ist \(x_B = B^{-1} b\) und \(x_N = 0\), also \(c^\top x = c_B^\top B^{-1} b = y^\top b\).
- Schritt 2, nur \(b_i\) ändert sich: Die reduzierten Kosten enthalten kein \(b\). Die Basis bleibt also optimal, solange sie zulässig bleibt, das heißt \(x_B(\delta) \ge 0\). In diesem Intervall gilt \(z^*(b_i + \delta) = z^*(b_i) + y_i\,\delta\): \(y_i\) ist die Steigung der Wertfunktion \(z^*\) nach \(b_i\).
- Schritt 3, außerhalb: Wird eine Basisvariable negativ, ist die alte Basis unzulässig, und eine andere Basis mit anderem \(y_i\) gilt (oder das Programm ist unzulässig, dann gibt es keine Basis mehr). \(z^*\) ist als Minimum linearer Funktionen \(b^\top y\) über die dual zulässigen Ecken konkav und stückweise linear in \(b\), in \(c\) als Maximum linearer Funktionen \(c^\top x\) konvex. Die Steigung kann daher bei diesem Maximierungsproblem mit wachsendem \(b_i\) nur abnehmen.
- Schritt 4, Dualität: Für jedes zulässige \(x\) und jedes dual zulässige \(y\) folgt für \(\le\)-Zeilen \(c^\top x \le y^\top A x \le y^\top b\) (schwache Dualität; bei Zeilen mit \(\ge\) oder \(=\) entsprechend mit den Vorzeichen von \(y\)). Die optimale Basis liefert \(y\) mit \(r \ge 0\) und \(b^\top y = c^\top x\). Beide Schranken fallen zusammen.
- Schritt 5, Entartung: Ist eine Basisvariable null, kann eine der beiden Intervallgrenzen \(0\) sein, und links- und rechtsseitige Steigung können verschieden sein. Für dieses Maximierungsproblem ist die rechtsseitige Steigung der kleinste, die linksseitige der größte Wert von \(y_i\) auf der Seitenfläche. Die gemessenen Werte im Beispiel unten sind die beiden Enden des Intervalls für \(y_2\).
Ein nicht entarteter optimaler Eckpunkt hat ein eindeutiges Dual. Diese Aussage ist Standardwissen und nicht Teil der Messung; die Messung bestätigt sie unten nur auf den erzeugten Instanzen.
Durchgerechnet: das Lehrbuchbeispiel
Optimum: \(x = (2, 6)\) mit Wert 36. Die Rampenzeit hat Schlupf 2; Kommissionierstunden und Lagerfläche sind aufgebraucht.
| Ressource | Bestand | Schattenpreis \(y_i\) | Bereich des Bestands, in dem \(y_i\) gilt |
|---|---|---|---|
| Rampenzeit | 4 | 0 | ab 2 |
| Kommissionierstunden | 12 | 1,5 | 6 bis 18 |
| Lagerfläche | 18 | 1 | 12 bis 24 |
Kontrolle von Primal und Dual: \(c^\top x = 3 \cdot 2 + 5 \cdot 6 = 36\) und \(b^\top y = 12 \cdot 1{,}5 + 18 \cdot 1 = 36\). Beide Dienste sind in der Basis, ihre reduzierten Kosten sind null: \(y^\top a_1 = 3 \cdot 1 = 3 = c_1\) und \(y^\top a_2 = 2 \cdot 1{,}5 + 2 \cdot 1 = 5 = c_2\) (Rechnung dieser Seite). Die Rampenzeit hat Schlupf und deshalb den Preis 0 (komplementärer Schlupf).
Die Kostenbereiche sind \(c_1 \in [0; 7{,}5]\) und \(c_2 \in [2; \infty)\). Sie folgen daraus, dass \(c\) in der Menge der nichtnegativen Kombinationen der Normalen der beiden aufgebrauchten Ressourcen liegen muss, \((0, 2)\) und \((3, 2)\). Das gibt \(c_1 \le 1{,}5\, c_2\), bei \(c_2 = 5\) also 7,5, und \(c_2 \ge \tfrac{2}{3}\, c_1\), bei \(c_1 = 3\) also 2 (Rechnung dieser Seite).
Jenseits der Lagerflächen-Grenze 24 ist die Rampenzeit für die Express-Pakete bindend (\(x_1 = 4\)): Zusätzliche Fläche bringt nichts mehr, die Wertfunktion verläuft waagerecht (Rechnung dieser Seite, keine Messung der Demo).
Entartete Ecke: Mit der vierten Ressource wählt der Löser \(y = (0; 1{,}5; 1; 0)\), optimal sind aber alle Duale mit \(y_2 \in [1; 1{,}5]\), \(y_3 \in [0; 1]\) und \(y_4 \in [0; 3]\). Ein Beispiel ist \(y = (0; 1; 0; 3)\) mit \(b^\top y = 12 \cdot 1 + 8 \cdot 3 = 36\) (Rechnung dieser Seite). Die Steigung des Optimalwerts nach den Kommissionierstunden ist links 1,5 und rechts 1,0.
Zukauf: Preis gegen Bereich
Kauft man bei einer \(\le\)-Ressource \(i\) Kapazität \(u \ge 0\) zum Preis \(q\) je Einheit zu, ist der exakte Optimalwert der eines Programms mit einer Zusatzspalte: Kapazität \(b_i + u\), Kosten \(q\,u\). Die Schattenpreis-Regel rechnet in Schritten: Solange \(y_i > q\), kaufe bis zur oberen Bereichsgrenze, löse neu und bepreise neu. Die naive Rechnung \((y_i - q) \cdot u\) nimmt \(y_i\) für die ganze Menge. Weil \(y_i\) mit wachsendem \(b_i\) nur abnehmen kann, überschätzt sie bei gleicher Menge den Gewinn (Rechnung dieser Seite).
Befunde
Die Zahlen sind Messungen der Demo an den oben beschriebenen Instanzen; alle Instanzen und Rauschziehungen entstehen aus festen Startwerten des Zufallsgenerators (deterministisch). Drei Stichproben kommen vor: einzelne feste Instanzen (Lehrbuch, Zentrum, entartete Ecke), Mediane über fünf feste Zufallsinstanzen je Größe (Bereichsbreiten) und Anteile über 50 Läufe (Rauschen, Entartung; bei Zentrum und Lehrbuch sind es 50 Rauschziehungen auf derselben festen Instanz, sonst je Lauf eine eigene Instanz mit eigener Ziehung, dann mischen die Anteile beide Quellen).
| Frage | Befund |
|---|---|
| Stimmen die Zertifikate? (Zertifikat: ein zulässiges \(x\) und ein dual zulässiges \(y\) mit \(c^\top x = b^\top y\); daraus folgt die Optimalität beider) | Auf 303 Instanzen stimmt das Optimum mit HiGHS überein: die drei festen Beispiele (Lehrbuch, Zentrum, entartete Ecke) und erzeugte kleine Instanzen (Zufall, Mischung mit ≥ und =, Transport; höchstens 8 Ressourcen und 8 Dienste, nicht die größeren Instanzen der Tabellen unten). Primal und dual sind zulässig (dual bis 1e-6), starke Dualität und beide Arten komplementären Schlupfs gelten jeweils bis 1e-7. Bei nicht entarteter Endbasis sind die Duale gleich den Marginals (den Dualen, die HiGHS ausgibt). Das Dual-LP liefert mit dem eigenen Löser und mit HiGHS denselben Wert. |
| Das Zentrum | Optimum 720 bei \(x = (20, 10, 10, 0, 0)\), Schattenpreise \(y = (5; 0{,}5; 4; 0)\), Schlupf der Fahrzeugkapazität 160. Sperrgut und Retouren haben reduzierte Kosten 3,5; die Endbasis bleibt für den Deckungsbeitrag von Sperrgut bis 23,5 optimal, bei 23,52 werden 7,78 Einheiten produziert und der Optimalwert steigt auf 720,18. Bereiche der Bestände: Kommissionierstunden 70 bis 90, Lagerfläche 172 bis 217,5, Rampenzeit 52,31 bis 58,89. |
| Ist der Schattenpreis die Ableitung? | Im Bereich ist der Differenzenquotient der Neulösung gleich \(y\) (eigener Löser und HiGHS, 1e-6). An 99,9 % der Grenze bleibt die Basis gleich, an 100,1 % wechselt sie. Rampenzeit im Zentrum: oberhalb fällt \(y\) auf 0, unterhalb steigt es auf 7,25. Die Wertfunktion ist konkav und stückweise linear (zweite Differenzen höchstens 1e-7), in \(c\) konvex. |
| Vorhersage \(y \cdot \Delta\) gegen Neulösung | Lagerfläche im Zentrum (\(y = 0{,}5\), obere Grenze 17,5), Erweiterung \(\Delta\) um das 0,5-, 1-, 2- und 4-fache der Grenze: Vorhersage 4,4 / 8,8 / 17,5 / 35, Neulösung 4,4 / 8,8 / 8,75 / 8,75. Kommissionierstunden im Zentrum (Grenze 10): Vorhersage 25 / 50 / 100 / 200, Neulösung 25 / 50 / 91,2 / 160,8. |
| Zukauf von Kommissionierstunden im Zentrum, Preis \(q = 2\) | Die Regel kauft in 3 Schritten 135 Einheiten (Schattenpreis 5 → 4,125 → 2,833). Der Gewinn nach Zukaufskosten ist 160, der Optimalwert 880, gleich dem exakten Programm mit Zusatzspalte. Die naive Rechnung \((y - q) \cdot u = 3 \cdot 135\) verspricht 405, mit \(q = 2\) und \(u = 135\). Zum Preis \(q = 3\) kauft die Regel 30 Einheiten in 2 Schritten und gewinnt 42,5 statt der naiv erwarteten 60. Bei \(q \ge y\) wird nichts gekauft. |
Bereichsbreiten: Erhöhung und Senkung sind der Anteil des Bestands, bis zu dem der Schattenpreis einer bindenden Ressource gilt (Median über alle bindenden Ressourcen mit endlicher Grenze). Der Kostenbereich ist die Breite des Bereichs eines Basisdienstes als Anteil von \(c_j\) (Median über alle Basisdienste, deren beide Grenzen endlich sind). Bei den Zufallsgrößen gehen die Werte aus fünf festen Instanzen in einen gemeinsamen Median ein (je Spalte 8 bis 18 Werte). Zentrum und Lehrbuch sind je eine Instanz.
| Instanzen | Erhöhung | Senkung | Kostenbereich |
|---|---|---|---|
| Zentrum | 8,8 % | 12,5 % | 9,5 % |
| Lehrbuch | 41,7 % | 41,7 % | 250 % |
| Zufall 6 × 8 | 50 % | 42 % | 68 % |
| Zufall 10 × 10 | 16 % | 37 % | 76 % |
| Mischung 8 × 8 | 47 % | 48 % | 163 % |
| Transport | 0 % (entartet) | – | – |
Beim Lehrbuch zählt im Kostenbereich nur der Express-Dienst, denn beim Palettenversand ist die Obergrenze unendlich. Die 250 % sind also ein einziger Wert (Rechnung dieser Seite).
Kostenrauschen: Anteil der 50 Läufe, in denen multiplikatives, normalverteiltes Rauschen der angegebenen Stärke \(s\) auf allen Deckungsbeiträgen die optimale Basis ändert: Jeder Deckungsbeitrag wird mit \(1 + s\,g\) multipliziert, \(g\) ist standardnormalverteilt.
| Instanzen | Stärke 1 % | Stärke 5 % | Stärke 10 % |
|---|---|---|---|
| Zentrum | 0 % | 50 % | 82 % |
| Zufall 10 × 10 | 4 % | 26 % | 40 % |
| Zufall 6 × 8 | 4 % | 14 % | 22 % |
| Mischung 8 × 8 | 6 % | 16 % | 22 % |
| Transport 3 × 5 | 14 % | 52 % | 76 % |
| Lehrbuch | 0 % | 0 % | 0 % |
Entartung: Anteil der 50 Instanzen mit entarteter Endbasis und mit nicht eindeutigen Dualen. Die Eindeutigkeit wird über die optimale Seitenfläche der Duale geprüft.
| Instanzen | entartete Endbasis | Duale nicht eindeutig |
|---|---|---|
| Zufall 6 × 8 und 10 × 10 | 0 % | 0 % |
| Mischung 8 × 8 | 0 % | 0 % |
| Mischung 10 × 10 | 4 % | 4 % |
| Transport 3 × 5 und 4 × 8 | 100 % | 100 % |
Beim Transport (Lager als \(\le\)-Zeilen, Kunden als \(\ge\)-Zeilen, Summe der Angebote gleich Summe der Nachfragen) hängen die Zeilen voneinander ab, ihr Rang ist um eins kleiner als ihre Zahl, und alle Zeilen sind bindend. Das erklärt die entartete Endbasis in allen gemessenen Fällen. Die Seitenfläche ist unbeschränkt: Hebt man alle Lagerduale um \(t \ge 0\) an und senkt alle Kundenduale um \(t\), bleiben die Zulässigkeit und \(b^\top y\) erhalten (Rechnung dieser Seite). Die obere Bereichsgrenze der Bestände liegt deshalb beim Bestand selbst (Erhöhung 0 %); Senkung und Kostenbereich sind für den Transport nicht berichtet. In keiner der gemessenen Instanzen war eine nicht entartete Endbasis mit mehrdeutigen Dualen verbunden.
Grenzen: was die Messung zeigt und was nicht
Was die Messung zeigt:
- Die Zertifikate (Optimalität gegen HiGHS, starke Dualität, komplementärer Schlupf) auf den erzeugten Instanzen, jeweils innerhalb der genannten Toleranz.
- Die Vorhersage \(y \cdot \Delta\) gegen die Neulösung: Sie stimmt innerhalb des Bereichs und weicht jenseits ab, wie die Zeilen für Lagerfläche und Kommissionierstunden zeigen.
- Die Größenordnung der Bereichsbreiten: Bei Erhöhung und Senkung betragen die Mediane in allen gemessenen Zeilen etwa 50 % des Bestands oder weniger, beim Zentrum etwa ein Zehntel. Die Kostenbereiche sind breiter (bis 250 %).
Was sie nicht belegt:
- Bereichsbreiten stehen auf wenigen Werten. Beim Zentrum sind es drei bindende Ressourcen, beim Lehrbuch zwei, bei den Zufallsgrößen 8 bis 18 Werte je Spalte aus nur fünf Instanzen (Rechnung dieser Seite). Die Streuung zwischen den Instanzen ist nicht ausgewiesen; kleine Unterschiede zwischen den Zeilen sind nicht belastbar.
- Die Anteile beim Rauschen haben nur 50 Läufe. Der Standardfehler eines Anteils von 26 % liegt bei dieser Stichprobe bei etwa sechs, der eines Anteils von 50 % bei etwa sieben Prozentpunkten (Rechnung dieser Seite). Unterschiede von einigen Prozentpunkten, etwa 14 % gegen 16 %, sind keine Aussage. Ein Basiswechsel sagt außerdem nichts über die Größe der Änderung von Plan oder Gewinn.
- Das Rauschen ist eine Wahl. Es ist multiplikativ und normalverteilt, nur auf den Deckungsbeiträgen und auf allen zugleich. Für Rauschen auf Beständen oder Verbrauch sagt die Messung nichts.
- Entartung folgt der Bauart der Instanzen. Gemessen ist: in 50 Instanzen je Größe keine entartete Endbasis bei Zufall, 0 % bis 4 % bei Mischung und 100 % bei den erzeugten Transportproblemen. Das ist keine allgemeine Aussage über Zufall oder Transport.
- Das Messverfahren zählt. Die einseitigen Differenzenquotienten allein hätten beim Transport 0 % nicht eindeutige Duale gemeldet, denn eine Seite ist bei ausgeglichenem Angebot unzulässig. Erst die Seitenfläche zeigt die Mehrdeutigkeit.
- Die Bereiche sind gegen Neulösungen geprüft, nicht gegen das Ranging eines Standardlösers. Gegen HiGHS sind die Duale und die Seitenfläche geprüft.
- Ranging gilt für einen Parameter allein. Gleichzeitige Änderungen (100-%-Regel) und parametrische Programmierung über mehrere Parameter sind nicht umgesetzt.
- Zukauf nur für Ressourcen mit \(\le\). Bei Zeilen mit \(\ge\) oder \(=\) gibt es keine Kapazität. Unzulässige und unbeschränkte Instanzen haben kein optimales Dual und werden nicht analysiert.
- Jede Neulösung beginnt von vorn. Ein Warmstart von der alten Basis (dualer Simplex) ist nicht Teil der Messung.
- Kleine, synthetische Instanzen. Sie reichen bis 12 Ressourcen und 12 Dienste. Schattenpreise in echten Netzen sind schwerer zu deuten (Entartung, Nebenwirkungen, ganzzahlige Entscheidungen), und sie sagen nur Grenzwerte, keine Gesamteffekte; das zeigt der Zukauf im Zentrum.
Quellen
- Gale, D., Kuhn, H. W., & Tucker, A. W. (1951): Linear programming and the theory of games. In T. C. Koopmans (Hrsg.), Activity Analysis of Production and Allocation, 317–329. Wiley.
- Dantzig, G. B. (1963): Linear Programming and Extensions. Princeton University Press.
- Gal, T. (1979): Postoptimal Analyses, Parametric Programming, and Related Topics. McGraw-Hill (in der Dokumentation der Demo nur genannt).
- Quelltext und Messreihen der Demo: github.com/sebastian-hanisch/lp-dualitaet-demo.
Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Angaben stammen aus der Dokumentation der Demo. Standardwissen und nicht aus der Demo: die Herleitung von Schattenpreis und Bereich und die Konkavität der Wertfunktion. Die Deutung der einseitigen Steigungen als Enden der Seitenfläche wird in der Demo gegen HiGHS geprüft. Die Dualitätssätze gehen auf frühere Arbeiten (von Neumann, Dantzig) zurück; das ist aus dem Gedächtnis, nicht geprüft.