Optimierung unter Unsicherheit · Verständlich erklärt

Der Wert der Information verständlich erklärt

Wer Kapazität wählen muss, bevor die Nachfrage bekannt ist, kann zwei Dinge fragen: was Vorwissen wert wäre (EVPI) und was es bringt, die Streuung zu modellieren (VSS). Diese Seite erklärt beides zuerst ohne Formeln und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen. Die Demo dazu ist eine von mehreren zum Thema Optimierung unter Unsicherheit.

Zuletzt aktualisiert:

Teil 1 · Für Einsteiger

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Planen, bevor man die Nachfrage kennt

Manche Entscheidungen fallen vor der Nachfrage: Man legt fest, wie viel Kapazität man vorhält, und erst danach zeigt sich, was gebraucht wird. Reicht die Kapazität an einem Standort nicht, bleiben drei Auswege: ungenutzte Kapazität eines anderen Standorts umlagern, Fehlendes teuer zukaufen oder eine Fehlmenge hinnehmen, die besonders hoch bestraft wird.

Unter dieser Unsicherheit stellt man zwei Fragen, die man gern verwechselt. Die erste: Was wäre es wert, die Nachfrage vorher zu kennen? Dieser Wert heißt EVPI, Wert der vollständigen Information. Die zweite: Was bringt es, die Streuung überhaupt in die Planung zu nehmen, statt mit dem Durchschnitt zu planen? Das heißt VSS, Wert der stochastischen Lösung.

Vier Informationsstände

Die Demo rechnet dieselben denkbaren Nachfragen, die Szenarien, unter vier Informationsständen durch. Beim Durchschnittsplan plant man für die mittlere Nachfrage und bezahlt dann, was wirklich eintritt. Kennt man die Verteilung der Nachfrage, wählt man den einen Plan, der im Mittel am billigsten ist. Der Hellseher kennt vorab das eintretende Szenario und wählt dafür den besten Plan. Bei der Teilinformation kennt man nur einen gemeinsamen Faktor, der alle Standorte zugleich bewegt, und plant für jede Stufe dieses Faktors neu.

EVPI ist der Kostenabstand zwischen dem Plan bei bekannter Verteilung und dem Hellseher. VSS ist der Kostenabstand zwischen dem Durchschnittsplan und dem Plan bei bekannter Verteilung.

Zwei Fragen, keine Schranken füreinander

EVPI und VSS begrenzen sich nicht gegenseitig. Es gibt Einstellungen, in denen Vorwissen viel wert wäre, der Durchschnittsplan aber fast so gut ist wie der Plan, der die Streuung kennt. Dann gehört Geld in bessere Prognosen, nicht in ein aufwendigeres Planungsmodell. Es gibt auch Einstellungen, in denen der Durchschnittsplan deutlich versagt, und sogar solche, in denen der VSS größer ist als der EVPI.

Der Durchschnittsplan kürzt an einem Standort die Kapazität so weit, dass der erlaubte Zukauf im Durchschnittsfall gerade noch reicht. Wird die Nachfrage höher, landet jede weitere Einheit in der hoch bestraften Fehlmenge. Der Plan, der die Streuung kennt, hält dort mehr vor.

Wo liegt der Haken?

Ob der Durchschnittsplan versagt, hängt in der Demo weniger an der Streuung als an den Möglichkeiten nach der Nachfrage. Kann man umlagern, gleicht das den Durchschnittsplan weitgehend aus. Ohne Umlagerung wird er teurer. Das gilt für diese Kostenstruktur, bei anderen kann es anders aussehen.

Außerdem ist der EVPI eine Obergrenze: Kein reales Informationssystem liefert das einzelne Szenario vorab. Und beide Werte beziehen sich nur auf den Durchschnitt der Kosten. Ein Plan, der im Mittel am billigsten ist, kann im Tail, also bei den teuersten Szenarien, sehr teuer werden. Darüber sagen EVPI und VSS nichts.

Wie ernst ist das Modell zu nehmen?

In der Demo sind die Szenarien die Verteilung selbst. Es gibt also keine Schätzung aus einer Stichprobe, und die Instanz mit ihren Standorten, Preisen und Grenzen ist erfunden. Die Demo zeigt, wie Vorwissen und Streuungsmodell wirken, nicht wie viel eine reale Planung gewinnen würde.

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.

Teil 2 · Für Fachleute

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

  • Instanz: sechs Standorte mit mittlerer Nachfrage zwischen 60 und 140 (bestimmt durch den Zufalls-Seed der Instanz). Die Nachfrage ist lognormal mit Erwartungswert gleich Mittel, einstellbarer Log-Streuung \(\sigma\) und einem einstellbaren gemeinsamen Faktor \(\rho\). 200 gleich wahrscheinliche Szenarien sind die Verteilung: Die Demo misst keine Schätzung aus einer Stichprobe.
  • Stufe 1: Kapazität \(x_j \ge 0\) je Standort zu Kosten \(c\) je Einheit, Summe höchstens \(B\), ein einstellbarer Anteil der Gesamtnachfrage.
  • Stufe 2 nach der Nachfrage: Die Kapazität eines Standorts deckt den eigenen Bedarf, ungenutzte Kapazität kann umgelagert werden (Transportkosten 0,35 · (0,3 + Abstand), abschaltbar). Der Rest geht in den Zukauf (Preis einstellbar, höchstens 50 % der mittleren Nachfrage) oder in eine dreifach bestrafte Fehlmenge. Die zweite Stufe kostet \(Q(x,\xi)\) bei Plan \(x\) und Nachfrage \(\xi\).
  • Lösung: Jeder Informationsstand ist ein einziges lineares Programm (HiGHS über scipy.optimize.linprog), in dem die Szenarien einer Gruppe einen Plan teilen.

Drei Kosten

Mit \(S\) gleich wahrscheinlichen Szenarien \(\xi_s\) und dem Plan \(\bar x\) für die mittlere Nachfrage \(\bar\xi = \tfrac1S\sum_s \xi_s\) gibt es drei Kosten. RP (Verteilung bekannt) sind die Kosten des einen Plans, der im Mittel am billigsten ist:

\[\mathrm{RP}=\min_x\; c\,\mathbf 1^\top x+\tfrac1S\sum_s Q(x,\xi_s)\]

WS (Hellseher) wählt je Szenario den eigenen besten Plan, als kenne er die Nachfrage vorher:

\[\mathrm{WS}=\tfrac1S\sum_s \min_{x}\big[c\,\mathbf 1^\top x+Q(x,\xi_s)\big]\]

EEV plant für die mittlere Nachfrage und wird dann über alle Szenarien ausgewertet:

\[\mathrm{EEV}=c\,\mathbf 1^\top \bar x+\tfrac1S\sum_s Q(\bar x,\xi_s),\qquad \bar x \in \arg\min_x\; c\,\mathbf 1^\top x+Q(x,\bar\xi)\]

Die Teilinformation (ein Plan je Stufe des gemeinsamen Faktors, fünf gleich große Stufen) liegt zwischen WS und RP. Beim einen Standort ist alles geschlossen (lognormale Teilerwartung); dort ist WS gleich Vorhaltungskosten mal Mittel.

EVPI und VSS

Der Wert der vollständigen Information ist der Abstand zwischen Verteilung bekannt und Hellseher:

\[\mathrm{EVPI}=\mathrm{RP}-\mathrm{WS}\ge 0\]

Der Wert der stochastischen Lösung ist \(\mathrm{VSS}=\mathrm{EEV}-\mathrm{RP}\ge 0\), also gilt die Kette \(\mathrm{WS}\le \mathrm{RP}\le \mathrm{EEV}\). Der erste Schritt gilt, weil jede Entscheidung, die für alle Szenarien gleich ist, auch je Szenario erlaubt wäre. Der zweite, weil \(\bar x\) für das Problem unter Unsicherheit zulässig, aber nicht optimal sein muss (vorausgesetzt: \(\bar x\) ist für jede Nachfrage zulässig, hier durch die Fehlmenge gesichert). Beide Werte werden in Prozent der Kosten des Plans unter Unsicherheit (RP) angegeben.

Befunde

Alle Zahlen stammen aus der Messreihe der Demo (jede steht in deren Tests). Sie gelten für sechs Standorte mit dem Zufalls-Seed der Voreinstellung (7); ein Seed ist kein Befund, deshalb steht die Spannweite über drei feste Instanzen (kleinster bis größter Wert) in Klammern. EVPI und VSS sind in Prozent der Kosten des Plans unter Unsicherheit angegeben.

FrageBefund
Voreinstellung: lohnt Information, reicht der Durchschnitt?EVPI 7,4 %, VSS 0,13 % (Instanz mit Zufalls-Seed 7; über die drei festen Instanzen mit den Zufalls-Seeds 100000 bis 100002 VSS 0,15 bis 0,43 %): Der Durchschnittsplan ist praktisch so gut wie der Plan unter Unsicherheit, Vorwissen wäre bis zu 7,4 % wert.
Was holt ein einzelner gemeinsamer Faktor vom EVPI?39 % in der Voreinstellung, 8 bis 11 % ohne Umlagerung und mit knappem Budget, rund 50 % bei hoher Streuung und weitem Budget.
Wann versagt der Durchschnittsplan?Ohne Umlagerung und mit Budget 0,85: VSS 3,8 % (Zufalls-Seed 7; 4,4 bis 4,9 % über die drei festen Instanzen).
Ist der Durchschnittsplan bei hoher Streuung automatisch schlecht?Nein: bei σ = 0,5, Umlagerung und Budget 1,3 liegt der EVPI bei 19,5 %, der VSS bei 0,14 %.
Kann der VSS größer als der EVPI sein?Ja: σ = 0,10, Budget 0,8, keine Umlagerung: VSS 4,1 %, EVPI 1,2 %.
Was bewirkt die Streuung?Der EVPI wächst mit σ (mit Umlagerung von 1,6 % bei σ = 0,1 auf 11,4 % bei σ = 0,6). Der VSS steigt nicht mit: mit Umlagerung 0,25 bis 0,39 %, ohne 1,4 bis 2,5 %.

Der Durchschnittsplan kürzt einen Standort bis auf gut die Hälfte der mittleren Nachfrage, denn der Zukauf deckt den Rest im Mittel gerade; der Plan unter Unsicherheit hält dort mehr vor.

Grenzen

  • Die Szenarien sind die Verteilung. Bei einer echten Stichprobe aus unbekannter Verteilung sind EVPI und VSS selbst Schätzungen, und der Optimalwert einer Stichprobe ist nach unten verzerrt. Dieser Fehler ist hier ausgeklammert; ihn behandelt die Stichproben-Demo (SAA) zum Thema.
  • EVPI ist eine Obergrenze. Kein reales Informationssystem liefert das einzelne Szenario vorab; die Teilinformation zeigt nur, wie viel ein einzelner gemeinsamer Faktor schon holt.
  • Nur der Erwartungswert. Ein Plan, der im Mittel am billigsten ist, kann im Tail sehr teuer werden; EVPI und VSS sagen darüber nichts. Das Risiko als Ziel zeigt die CVaR-Demo zum Thema.
  • Eine Familie von Instanzen. Sechs Standorte, lognormal, ein gemeinsamer Faktor, feste Preise und Grenzen. Das Experiment zeigt die Spannweite über drei feste Instanzen, nicht über alle möglichen.
  • Das Bild hängt an der Umlagerung. Der VSS ist hier vor allem eine Folge der Möglichkeiten nach der Realisierung, nicht der Streuung; mit anderen Kostenstrukturen kann es anders aussehen.
  • Nur ein Informationsstand dazwischen. Die Teilinformation nutzt den gemeinsamen Faktor in fünf Stufen; andere Teilinformation (einzelne Standorte, verrauschte Hinweise) ist nicht abgebildet. Mehrstufige Entscheidungen fehlen: Es gibt eine Entscheidung vor der Nachfrage, danach nur den Fluss.

Quellen

  • Birge und Louveaux: Introduction to Stochastic Programming, Springer, 2. Auflage 2011 (die Begriffe EVPI und VSS).
  • Arrow, Harris und Marschak: Optimal Inventory Policy, Econometrica 19(3), 1951, Seiten 250 bis 272 (das kritische Verhältnis, dort in einem allgemeineren Modell).
  • Quelltext, Messreihe und Tests der Demo: github.com/sebastian-hanisch/newsvendor-evpi-demo.

Die beiden Arbeiten wurden für diese Seite nicht nachgeschlagen; die Angaben stammen aus dem Expander „📐 Mathematische Formulierung“ der Demo.