Anhang A: Lösungen zu allen Übungsaufgaben

Wie Sie diesen Anhang benutzen: Erst rechnen, dann nachsehen. Bei Programmieraufgaben (⭐⭐⭐) ist meist der Lösungsweg mit den entscheidenden Codezeilen und den erwarteten Erkenntnissen angegeben, nicht das vollständige Programm — den Rest sollen Sie selbst bauen. Wo Zahlen von Live-Daten abhängen, steht die Struktur der erwarteten Antwort.

A.1 Lösungen zu Kapitel „Einführung in Operations Research — Vom Ursprung zur mathematischen Entscheidungsfindung“

1.1 — Analytik-Stufen. (a) deskriptiv (Vergangenheit beschreiben). (b) prädiktiv (Prognose). (c) präskriptiv (Handlungsanweisung unter Restriktionen). (d) prädiktiv (Klassifikation). (e) präskriptiv — hier kommt das begrenzte Budget ins Spiel, es muss zugeteilt werden. Beachten Sie das Paar (d)/(e): Die Prognose sagt, wer kündigen wird; die Optimierung sagt, wen man mit dem vorhandenen Geld halten kann.

1.2 — Hart oder weich? (a) hart — gesetzlich zwingend. (b) weich — Wunsch, mit Strafkosten. (c) hart — Patientensicherheit, rechtlich vorgeschrieben. (d) weich — Fairnessziel, über Strafterme. (e) hart, falls tariflich/gesetzlich fixiert, sonst weich mit sehr hoher Strafe. Faustregel: Hart ist nur, was rechtlich oder physikalisch unmöglich zu verletzen ist.

1.3 — Kombinatorik. (a) 12! = 479\,001\,600. (b) 479\,001\,600 / 5\cdot10^6 \approx 95{,}8 Sekunden \approx 1{,}6 Minuten. (c) 13! = 6\,227\,020\,800; das sind 1245 s \approx 20{,}8 Minuten — Faktor 13. Jeder weitere Auftrag multipliziert die Zeit mit der neuen Anzahl. (d) Eine Stunde = 3600 s \to 1{,}8\cdot10^{10} Prüfungen. 13! = 6{,}2\cdot10^9 ✓, 14! = 8{,}7\cdot10^{10} ✗. Also 13 Aufträge.

1.4 — Modell lesen. (a) Variablen x_1, x_2 \ge 0; Parameter (3,5) und die Kapazitäten (4,12,18); Zielfunktion \max 3x_1+5x_2; vier Nebenbedingungen inkl. Nichtnegativität. (b) (2,6): 2\le4 ✓, 12\le12 ✓, 6+12=18\le18 ✓ → zulässig, Z=36. (4,3): 4\le4 ✓, 6\le12 ✓, 12+6=18\le18 ✓ → zulässig, Z=27. (c) Beste ganzzahlige Lösung ist (2,6) mit Z=36 — sie ist hier bereits ganzzahlig, weil die Ecke des Polyeders zufällig auf Gitterpunkten liegt.

1.5 — Bäckerei.

from ortools.sat.python import cp_model
m = cp_model.CpModel()
x1 = m.NewIntVar(0, 1000, "Brote")
x2 = m.NewIntVar(0, 1000, "Broetchen_10er")
m.Add(5 * x1 + 6 * x2 <= 900)        # Mehl in 100-g-Einheiten (0,5 kg -> 5)
m.Add(4 * x1 + 3 * x2 <= 600)        # Ofenminuten
m.Add(x1 >= 40)                       # Vertrag
m.Maximize(250 * x1 + 300 * x2)       # Deckungsbeitrag in Cent
s = cp_model.CpSolver(); s.Solve(m)

Ergebnis: x_1 = 96 Brote, x_2 = 70 Zehnerpackungen, Deckungsbeitrag 450,00 €.

Probe: Mehl 0{,}5\cdot96 + 0{,}6\cdot70 = 48 + 42 = 90 kg ✓ (voll ausgelastet); Ofen 4\cdot96 + 3\cdot70 = 384+210 = 594 \le 600 ✓; Vertrag 96 \ge 40 ✓; Z = 2{,}5\cdot96 + 3\cdot70 = 240 + 210 = 450 ✓.

Zwei lehrreiche Beobachtungen: 1. Die Vertragsbedingung x_1 \ge 40 ist nicht bindend — der Solver backt freiwillig 96 Brote. Wer aus der Aufgabenstellung schließt, die Mindestmenge werde „gerade so“ erfüllt, liegt falsch. 2. Das kontinuierliche Optimum (40;\ 116{,}67) liefert denselben Zielwert 450. Das Problem hat also mehrere optimale Lösungen — die Zielfunktion verläuft parallel zur Mehlrestriktion (2{,}5/0{,}5 = 5 = 3{,}0/0{,}6). Prüfen Sie das nach: Genau deshalb ist hier auch die ganzzahlige Lösung ohne Verlust erreichbar.

1.6 — Sensitivität durch Ausprobieren. Schleife über RAM_GESAMT in range(54, 73, 2), jeweils Modell neu lösen. (a) Ab 62 GB steigt der Gewinn nicht mehr — dann bindet die vCPU-Grenze, RAM ist nicht mehr der Engpass. (b) Der Zuwachs je GB ist der Schattenpreis (Kapitel 5). Solange RAM bindet, liegt er bei 31,25 €/GB; danach fällt er auf 0.

1.7 — Eigenes Problem. Individuell. Prüfkriterien: Sind die Variablen wirklich entscheidbar (nicht bereits festgelegt)? Hat die Zielfunktion eine Einheit? Ist jede harte Bedingung wirklich unverhandelbar?

Finde den Denkfehler — Die Schreinerei verdoppelt ihren Gewinn

1. Nachrechnen. Der Plan lautet 40 Tische und 150 Stühle: 40 \cdot 3 + 150 \cdot 1 = \mathbf{270} Montagestunden bei 150 verfügbaren, und 40 \cdot 6 + 150 \cdot 1 = \mathbf{390} m² Material bei 240 verfügbaren. Beide Vorräte sind fast doppelt überzogen — der Plan ist in der Werkstatt nicht ausführbar.

2. Der Fehler. Die Nebenbedingungen stehen innerhalb der Produktschleife. Dadurch entsteht je Produkt eine eigene Kapazitätsgrenze („der Tisch allein darf 150 Stunden verbrauchen“, „der Stuhl allein darf 150 Stunden verbrauchen“) statt einer gemeinsamen Grenze über alle Produkte hinweg. Die Ressource wird so für jedes Produkt neu verteilt — im Modell existiert sie mehrfach.

Übersetzt in die Formelsprache aus Abschnitt 1.6: Programmiert wurde a_{ij} x_j \le b_i für jedes j einzeln, gemeint war \sum_j a_{ij} x_j \le b_i. Das Summenzeichen ist der ganze Unterschied.

3. Korrektur. Die Summe über alle Produkte gehört in die Bedingung, die Schleife läuft über die Ressourcen, nicht über die Produkte:

for r, index in [("Montagestunden", 1), ("Plattenmaterial", 2)]:
    s.Add(sum(x[p] * produkt[p][index] for p in produkt) <= vorrat[r])

4. Automatische Absicherung. Nach jedem Lösen den tatsächlichen Verbrauch gegen den Vorrat prüfen — mit kleiner Toleranz, weil Solver mit endlicher Genauigkeit rechnen (siehe Kapitel 3):

for r, index in [("Montagestunden", 1), ("Plattenmaterial", 2)]:
    verbrauch = sum(x[p].solution_value() * produkt[p][index] for p in produkt)
    assert verbrauch <= vorrat[r] + 1e-6, f"{r} ueberzogen: {verbrauch} > {vorrat[r]}"

Diese vier Zeilen sind das wichtigste Werkzeug des Kapitels: Sie prüfen die Lösung gegen die Wirklichkeit, nicht gegen das Modell. Ein Modellierungsfehler kann sich vor dem Solver verstecken, vor dieser Prüfung nicht.

Micro-Quiz

1 — (c) präskriptiv. Die Frage lautet „was tun“, und es gibt eine Restriktion (das Restbudget). Dass man für die Bewertung eine Prognose braucht, macht die Frage nicht prädiktiv — die Prognose ist hier Eingabeparameter, nicht Ergebnis.

2 — (a) als weiche Bedingung mit Strafkosten. INFEASIBLE heißt: Die harten Regeln widersprechen sich, es existiert kein einziger zulässiger Plan. Das ist eine Modellierungs-, keine Rechenfrage — ein schnellerer Solver (b) rechnet dieselbe Unlösbarkeit nur schneller nach. Antwort (c) ginge am Problem vorbei, weil nicht die Variablengrenzen, sondern eine Wunschregel den Widerspruch erzeugt.

3 — (b). 20! \approx 2{,}4 \cdot 10^{18}; Faktor 1000 verkürzt 77 Jahre auf knapp einen Monat — und bei 24 Aufträgen ist man wieder bei Jahrtausenden. Gegen multiplikatives Wachstum ist konstante Beschleunigung machtlos. (a) und (c) sind sachlich falsch: Solver nutzen sehr wohl mehrere Kerne, und die Ungenauigkeit großer Fakultäten ist nicht der Grund für die Rechenzeit.

Selbsttest

1. Über Entscheidungsvariablen bestimmt der Solver; Parameter sind vorgegebene Daten.
2. Weil die Zahl der Kombinationen multiplikativ wächst: Faktor 10⁶ Geschwindigkeit verschiebt die machbare Größe nur um wenige Elemente.
3. Entscheidungsvariablen, Parameter, Zielfunktion, Nebenbedingungen.
4. Kein Punkt erfüllt alle Bedingungen gleichzeitig; häufigste Ursache: zu viele oder widersprüchliche harte Bedingungen.
5. Weil sie dann nicht in der Modellformulierung sichtbar ist, kein Schattenpreis abgefragt werden kann — und weil eine zu eng gewählte Grenze stillschweigend ein falsches Optimum erzeugt.

A.2 Lösungen zu Kapitel „Das mathematische Fundament — Vektoren, Matrizen, Konvexität“

2.1 — Matrixform lesen. \max 4x_1 + x_2 + 6x_3 u. d. N. x_1 + 2x_2 \le 10, x_2 + 3x_3 \le 12, x \ge 0. 3 Variablen, 2 Nebenbedingungen (plus Nichtnegativität).

2.2 — Standardform. \min -7x_1 + 2x_2 u. d. N. -4x_1 - x_2 \le -20 (aus „\ge“ durch Multiplikation mit -1), x_1 - x_2 \le 3 und -x_1 + x_2 \le -3 (Gleichung als zwei Ungleichungen), x_1, x_2 \ge 0.

2.3 — Ecken von Hand. (b) Ecken: (0,0), (6,0), (4,4), (0,8). (c) Z: 0, 12, 20, 24 → Optimum (0,8) mit Z = 24. (d) Bei \max 2x_1+2x_2: Z(4,4) = 16, Z(0,8) = 16 — die Zielfunktion ist parallel zur Kante x_1+x_2=8. Es gibt dann unendlich viele optimale Lösungen (die ganze Kante), aber weiterhin mindestens eine in einer Ecke — der Fundamentalsatz bleibt gültig.

2.4 — Konvexität. (a) konvex (linear, sogar affin — Grenzfall, auch konkav). (b) konvex (f'' = 12x^2 \ge 0). (c) nicht konvex, sondern konkav (f'' = -\tfrac14 x^{-3/2} < 0). (d) nicht konvex, konkav (f'' = -1/x^2 < 0). (e) konvex (Summe konvexer Funktionen; Hesse-Matrix 2\mathbf{I} \succ 0). (f) konvexe Menge (Kreisscheibe). (g) konvexe Menge — der Bereich oberhalb der Hyperbel im positiven Quadranten ist konvex (Achtung, überraschend: die Funktion 1/x ist konvex, und die Menge \{x_2 \ge 1/x_1\} ist der Epigraph einer konvexen Funktion, also konvex).

2.5 — Positive Semidefinitheit. \mathbf{P}_1: Eigenwerte \approx (3{,}8;\ 9{,}2) → PSD ✓, Korrelation 1/\sqrt{4\cdot9} = 0{,}167 ✓. \mathbf{P}_2: Eigenwerte \approx (-0{,}6;\ 13{,}6) → nicht PSD; implizierte Korrelation 7/\sqrt{36} = 1{,}167 > 1 — unmöglich. \mathbf{P}_3: Eigenwerte (0{,}5;\ 0{,}5;\ 2{,}0) → PSD ✓.

2.6 — Bäckerei visualisieren. Ecken: (40,0), (150,0), (40,116{,}67) und der Schnittpunkt von Mehl- und Ofengrenze. Beste Ecke ist (40;\ 116{,}67) mit Z = 450 (im kontinuierlichen Fall).

2.7 — Eigenwert-Clipping.

def repariere(P):
    lam, V = np.linalg.eigh(P)
    return V @ np.diag(np.maximum(lam, 0.0)) @ V.T

Für \mathbf{P}_2 ergibt sich eine PSD-Matrix mit Korrelation exakt 1{,}0 — das Verfahren zieht die unmögliche Korrelation auf den nächstgelegenen zulässigen Wert. Für Kovarianzmatrizen setzt man in der Praxis auf einen kleinen positiven Wert statt auf 0 (np.maximum(lam, 1e-10)), damit die Matrix invertierbar bleibt.

Finde den Denkfehler — Die unauffällige Transposition

1. Warum nichts auffällt. \mathbf{A} ist quadratisch, also passen die Dimensionen auch transponiert. NumPy prüft Formen, nicht Bedeutungen; der Solver bekommt ein vollkommen zulässiges LP vorgelegt und löst es korrekt — nur eben ein anderes. Eine Transposition ist genau dann gefährlich, wenn sie folgenlos aussieht: Wäre die Matrix 2 \times 3 gewesen, hätte NumPy sofort einen Dimensionsfehler geworfen.

2. Der Plan an den echten Restriktionen. Mit \mathbf{A} = \begin{pmatrix} 1 & 2 \\ 3 & 1\end{pmatrix} und \mathbf{x} = (5{,}6;\ 0{,}8):

\mathbf{A}\mathbf{x} = \begin{pmatrix} 1\cdot5{,}6 + 2\cdot0{,}8 \\ 3\cdot5{,}6 + 1\cdot0{,}8\end{pmatrix} = \begin{pmatrix} 7{,}2 \\ 17{,}6 \end{pmatrix} \quad\text{gegen}\quad \mathbf{b} = \begin{pmatrix} 8 \\ 12\end{pmatrix}

Die zweite Ressource ist um 47 % überzogen (17,6 statt 12). Der Plan ist in der Werkstatt nicht ausführbar.

3. Warum „zu klein“ schlimmer ist als „zu groß“. Ein unerwartet hoher Zielwert weckt Misstrauen — man rechnet nach (siehe Abschnitt 1.10). Ein leicht niedrigerer Wert wirkt dagegen wie ein normales, etwas enttäuschendes Ergebnis: Niemand prüft nach, warum die Optimierung „nur“ 20,80 € statt der erhofften 22 € bringt. Fehler, die sich als Bescheidenheit tarnen, überleben am längsten.

4. Zwei Zeilen, die es aufgedeckt hätten. Erstens beim Einlesen die Form gegen die Bedeutung prüfen, zweitens nach dem Lösen den Verbrauch gegen den Vorrat:

assert A.shape == (len(b), len(c)), "A: Zeilen = Ressourcen, Spalten = Variablen"
assert np.all(A @ r.x <= b + 1e-9), f"Plan verletzt Restriktionen: {A @ r.x} > {b}"

Die erste Zeile hilft nur bei rechteckigem \mathbf{A} — die zweite immer. Sie ist die wichtigste Zeile in jedem Optimierungsskript: Sie prüft die Lösung nicht gegen das Modell, sondern gegen die Wirklichkeit, die das Modell abbilden sollte.

Vorbeugend hilft außerdem, Matrizen nie positionsweise abzutippen, sondern über benannte Spalten aus einer Tabelle zu erzeugen — genau das tut Excel_Bruecke.py aus Kapitel 1.

Micro-Quiz

1 — (b). Der Fundamentalsatz sagt nur, dass ein Optimum in einer Ecke angenommen wird. (a) ist falsch, weil es mehrere optimale Ecken geben kann (wenn die Zielfunktion parallel zu einer Kante verläuft) und dann sogar unendlich viele optimale Punkte auf der Verbindungsstrecke. (c) ist falsch, weil die Zahl der Eckenkandidaten kombinatorisch wächst: Bei 6 Variablen und 4 Ungleichungen plus 6 Nichtnegativitäten sind \binom{10}{6} = 210 Systeme zu prüfen — bei 50 Variablen wären es 10^{29}. Der Satz sagt, wo man suchen muss, nicht dass die Suche billig ist.

2 — (b). Faustregel \kappa = 10^{k} ⟹ etwa k signifikante Stellen verloren; bei 10^{11} bleiben von 16 rund 5. Das Modell ist deshalb nicht unlösbar (a) — es rechnet nur mit einer Genauigkeit, die den Ergebnissen nicht mehr anzusehen ist. (c) verwechselt die Konditionszahl mit einem Aufwandsmaß; sie sagt nichts über die Iterationszahl.

3 — (c). int() schneidet ab: int(0.99999998) == 0 macht aus einer Ja- eine Nein-Entscheidung (a). Den Wert unverändert weiterzureichen (b) verschiebt das Problem nur in die nachgelagerte Verarbeitung, wo dann irgendwann doch jemand int() schreibt. Richtig ist die Prüfung gegen die Toleranz mit Fehlermeldung im Zweifelsfall — die Funktion sichere_ganzzahl() aus Skalierung_Kondition.py.

Selbsttest

1. Die gewichtete Summe aller Variablen — Ergebnis ist ein Skalar (eine Zahl).
2. Weil die Matrix rechteckig ist: Jede Zeile muss so viele Einträge haben wie es Variablen gibt. Eine 0 bedeutet „diese Variable verbraucht nichts von dieser Ressource“.
3. Hat ein LP eine Optimallösung, liegt mindestens eine in einer Ecke. Nutzen: endlich viele Kandidaten statt unendlich vieler Punkte — die Grundlage des Simplex.
4. Weil der zulässige Bereich zu einem Punktgitter wird; zwischen zwei zulässigen Gitterpunkten liegen unzulässige Punkte, die Verbindungsstrecke verlässt also die Menge.
5. Das ist kein Bug, sondern das erwartete Verhalten bei nicht-konvexen Problemen: lokale Verfahren finden lokale Optima. Abhilfe: Multistart, konvexe Reformulierung oder globale Verfahren.

A.3 Lösungen zu Kapitel „Das Python-Ökosystem für OR — Solver, Bindings und Modellierungsschichten“

3.1 — Solverwahl. (a) CP-SAT (diskrete Zuordnung mit Zeitfenstern). (b) scipy.optimize.linprog (klassisches Mischungs-LP, klein). (c) CVXPY (konvexes QP). (d) MIQP — CVXPY mit Binärvariablen und MIQP-fähigem Solver, oder Heuristik. (e) MILP über highspy oder CP-SAT (Standortproblem mit Fixkosten). (f) scipy.optimize.minimize mit Multistart (nicht konvex).

3.2 — Bäckerei viermal. Alle vier müssen Z = 448 (ganzzahlig) bzw. 450 (kontinuierlich) liefern. Denken Sie an die Prozesstrennung, falls ortools und highspy kollidieren.

3.3 — CSR-Format. values = [3, 1, 2, 5, 4, 6], indices = [0, 3, 2, 0, 1, 3], starts = [0, 2, 3]. CSR speichert 6 Werte + 6 Indizes + 3 Startpositionen = 15 Zahlen; die volle Matrix hätte 3\times4 = 12. Bei dieser winzigen, dicht besetzten Matrix lohnt CSR nicht — der Vorteil entsteht erst bei großer, dünn besetzter Struktur (z. B. 1000×1000 mit 0,5 % Besetzung: 15 000 statt 1 000 000 Zahlen).

3.4 — Konvexitätsprüfung. \min x^3 wirft DCPError: Problem does not follow DCP rules, weil x^3 auf [-2,2] weder konvex noch konkav ist. \min x^2 läuft und liefert x=0. Der Unterschied: CVXPY akzeptiert nur Ausdrücke, deren Konvexität es beweisen kann — dafür garantiert es das globale Optimum.

3.5 — Laufzeitvergleich. Erwartetes Muster: linprog und highspy liegen bei kleinen Modellen gleichauf (Overhead dominiert); ab etwa n \gtrsim 500 zieht highspy davon, weil der Modellaufbau effizienter ist. CVXPY hat den größten festen Aufwand (Ausdrucksbaum-Kompilierung), der bei wiederholten Läufen mit cp.Parameter teilweise entfällt.

3.6 — Eigene Entscheidungshilfe. Ergänzungen: Bei kommerzieller Lizenz Gurobi/CPLEX über Pyomo oder CVXPY empfehlen; bei Lesbarkeitsanforderung Pyomo (algebraische Notation, Trennung von Daten und Modell).

Finde den Denkfehler — Der Solver, der angeblich dreimal schneller ist

1. Was da alles mitgemessen wird. Die Stoppuhr läuft ab der ersten Zeile, also mindestens über drei Dinge, die mit Lösegeschwindigkeit nichts zu tun haben:

1. Der import. CVXPY zieht beim ersten Import seine gesamte Solver-Erkennung hoch — allein das kostet regelmäßig über eine Sekunde. linprog steht in einem Prozess, der SciPy ohnehin schon geladen hat, praktisch sofort bereit.
2. Der Modellaufbau. CVXPY baut einen Ausdrucksbaum und kompiliert ihn in die Standardform des Solvers. Das ist echter Aufwand — aber Aufbau, nicht Rechnen.
3. Die Reihenfolge. CVXPY läuft zuerst und bezahlt dabei alles, was danach im Betriebssystem-Cache liegt: Bibliotheken, Speicherseiten, JIT-Wärme. Tauschen Sie die beiden Blöcke, und die Zahlen verschieben sich allein deshalb.

2. Warum das bei 60 Wiederholungen kippt. Import und Kompilierung fallen einmal an, das Lösen sechzigmal. Genau dafür hat CVXPY cp.Parameter: Man baut das Problem einmal, tauscht nur die Daten und löst erneut, ohne neu zu kompilieren. Gemessen wurde also ausgerechnet der Teil, der in der Zielanwendung fast nicht mehr vorkommt — die Entscheidung beruht auf der unwichtigsten Zahl.

3. Eine Messung, die trägt. Drei Regeln:

# 1. Importe VOR die Messung
import cvxpy as cp
from scipy.optimize import linprog

# 2. Aufwaermlauf: einmal alles durchlaufen lassen, Ergebnis verwerfen
loese_klein()

# 3. Aufbau und Loesen GETRENNT messen, ueber mehrere Wiederholungen
t0 = time.perf_counter()
problem = cp.Problem(cp.Minimize(kosten @ x), [A @ x == b])   # Aufbau
t_aufbau = time.perf_counter() - t0

zeiten = []
for _ in range(10):
    t0 = time.perf_counter()
    problem.solve()
    zeiten.append(time.perf_counter() - t0)
print(f"Aufbau {t_aufbau:.3f}s, Loesen Median {statistics.median(zeiten):.3f}s")

Und die vierte, wichtigste Regel: die Größe messen, die später auch läuft. Ein Vergleich bei 200 Variablen sagt nichts über das Verhalten bei 200 000 — die Kurven schneiden sich oft. Genau diese Trennung führt Vektorisierte_Modellgenerierung.py vor, und Kapitel 22 baut daraus eine vollständige Benchmark-Pipeline.

Micro-Quiz

1 — (b) CP-SAT. Es geht um diskrete Zuweisung mit logischen Regeln („nicht gleichzeitig“) — CP-SATs Kerngebiet, und Regeln dieser Art formuliert man dort direkt statt über Big-M-Umwege. (a) scheidet aus, weil CVXPY keine sinnvolle Ganzzahligkeit in dieser Größenordnung bietet; (c) findet bei einem diskreten Problem bestenfalls ein lokales Optimum und hat keinerlei Handhabe für „entweder–oder“-Regeln.

2 — (c) Modellaufbau vektorisieren. 32 von 40 Sekunden fallen an, bevor der Solver startet. Ein kommerzieller Solver (a) beschleunigt bestenfalls die verbleibenden 8 Sekunden — selbst bei Faktor 4 gewinnen Sie 6 der 40 Sekunden. Das Zeitlimit (b) betrifft den Abbruch, nicht die Geschwindigkeit. Die Regel dahinter: erst messen, wo die Zeit hingeht, dann optimieren.

3 — (b). Alle vier sind Modellierungsschichten über HiGHS. Deshalb liefern sie denselben Zielwert (bis auf Toleranz) und unterscheiden sich in der reinen Rechenzeit kaum — wohl aber im Aufbauaufwand und in der Lesbarkeit. (a) ist falsch: Niemand von ihnen implementiert den Simplex in Python, das wäre um Größenordnungen zu langsam. (c) ist falsch: Nicht-konvexe Probleme global zu lösen kann keines dieser Werkzeuge — dafür braucht es spezialisierte globale Solver (Kapitel 11).

Selbsttest

1. Modellierungsschicht (Python) und Solver-Schicht (C++). Die Trennung erlaubt Solvertausch ohne Modelländerung.
2. CVXPY prüft die Konvexität und lehnt ab, was es nicht garantieren kann; minimize prüft nichts und liefert ein lokales Optimum.
3. Werte, Spaltenindizes und Zeilenstartpositionen der Nicht-Null-Einträge. Entscheidend, weil reale Modelle extrem dünn besetzt sind.
4. Wegen des Kompilierungsaufwands des Ausdrucksbaums. Kein Argument dagegen, weil dieser Aufwand einmalig ist, die Lesbarkeit hoch und die Konvexitätsprüfung wertvoll.
5. Bei rein kontinuierlichen Problemen (CP-SAT kennt nur ganze Zahlen) und bei reinen Routing-Problemen (dort ist die Routing-Bibliothek überlegen).

A.4 Lösungen zu Kapitel „Vom Management-Wunsch zum Modell“

4.1 — Die fehlende Lesart. Eine dritte Lesart: „Der Umsatzanteil der Stammkunden darf nicht unter 30 % fallen.” Sie zielt weder auf einzelne Aufträge noch auf einzelne Kunden, sondern auf das Gesamtbild. Sie beschreibt einen Betrieb, dem die Struktur seines Geschäfts wichtig ist — etwa weil Stammkunden verlässlicher zahlen oder weil eine zu große Abhängigkeit von Neukunden als Risiko gilt. Sie lässt zu, dass ein einzelner Stammkunde in einem Quartal leer ausgeht, solange die Summe stimmt.

Der Punkt der Aufgabe: Alle drei Lesarten sind vertretbar, und keine ist aus dem Satz ableitbar. Die Wahl trifft man — im Zweifel unbewusst.

4.2 — Frage 5 anwenden. Wird die durchschnittliche Wartezeit minimiert, lohnt es sich, viele leichte Fälle schnell abzuarbeiten und die aufwendigen nach hinten zu schieben: Ein Fall mit vier Stunden Wartezeit zählt genauso viel wie vier Fälle mit einer Stunde. Der optimale Plan behandelt also bevorzugt Bagatellen und lässt schwere Fälle warten — medizinisch das Gegenteil des Gewollten.

Das ist genau der Ertrag von Frage 5: Der Plan lässt sich ablehnen, und aus der Ablehnung folgt die richtige Zielgröße — etwa die maximale Wartezeit je Dringlichkeitsstufe, oder die Einhaltung von Zielzeiten je Triage-Kategorie.

4.3 — Der Kompromiss dazwischen. Je Stammkunde eine Nebenbedingung: Die Summe der zugeteilten Stunden dieses Kunden muss mindestens die Hälfte seiner angefragten Stunden betragen.

for kunde in STAMMKUNDEN:
    stunden_kunde = [a[3] if a[1] == kunde else 0 for a in AUFTRAEGE]
    je_kunde_ub.append([-s for s in stunden_kunde])
    je_kunde_b.append(-0.5 * sum(stunden_kunde))

Erwartung: Das Ergebnis liegt zwischen Lesart A und B — die Regel bindet stärker als „ein Auftrag genügt”, aber schwächer als „alle Aufträge”. Der Lehrpunkt ist nicht die Zahl, sondern dass sich zwischen zwei Lesarten beliebig fein abstufen lässt, sobald man sie einmal als Ungleichung geschrieben hat.

4.4 — Zwei Ziele gleichzeitig. Bei \lambda = 0 ergibt sich der DB-Plan (78 500 € DB), bei großem \lambda der Umsatzplan (66 000 € DB). Dazwischen kippt es an genau einer Stelle — und zwar sprunghaft, nicht allmählich: Weil die Entscheidungsvariablen binär sind, gibt es nur endlich viele Pläne, und der Wechsel erfolgt, sobald ein anderer Plan den höheren gewichteten Wert hat.

Der Kippwert sagt dem Betrieb etwas Konkretes: „Erst wenn Ihnen ein Euro Umsatz mehr wert ist als λ Euro Deckungsbeitrag, ändert sich Ihr Plan.” Das ist eine Frage, die ein Kaufmann beantworten kann — anders als „welche Gewichtung hätten Sie gern?“.

4.5 — Die Anforderung schreiben. Eine tragfähige Anforderung enthält mindestens:

• Entscheidung: Für jede Anfrage im Planungszeitraum: annehmen oder ablehnen.
• Ziel: Deckungsbeitrag maximieren (Umsatz minus Material).
• Hart: Die Summe der Maschinenstunden angenommener Aufträge überschreitet die verfügbare Kapazität nicht.
• Weich: Je abgelehntem Stammkundenauftrag 6 000 € Strafe. (Begründung dokumentieren — der Wert ist eine kaufmännische Entscheidung, keine technische.)
• Bei Unlösbarkeit: Kann es nicht geben, weil alle Regeln außer der Kapazität weich sind. Sollte die Kapazität selbst verletzt sein, liegt ein Datenfehler vor → Abbruch mit Meldung, kein Plan.
• Auszuweisen: angenommene Aufträge, Deckungsbeitrag, Umsatz, Auslastung, Liste der abgelehnten Stammkundenaufträge mit dem jeweils verdrängten Deckungsbeitrag.

Der letzte Punkt ist der, den man am ehesten vergisst und am dringendsten braucht: Ohne ihn kann niemand nachvollziehen, warum ein Stammkunde abgelehnt wurde (Abschnitt 22.3, Erklärbarkeit).

Finde den Denkfehler — „Die Engpassmaschine soll zu mindestens 92 % ausgelastet sein“

Fehler 1: Auslastung ist ein Ergebnis, keine Anforderung.

Die Vorgabe zwingt das Modell, Aufträge anzunehmen, nur damit die Maschine läuft. In einem Monat mit schwacher Nachfrage heißt das: Aufträge mit minimalem oder negativem Deckungsbeitrag werden angenommen, weil die Alternative — Leerlauf — verboten ist. Die Kennzahl wird erfüllt, das Ergebnis leidet. Das ist Goodharts Gesetz in Reinform: Sobald eine Kennzahl zum Ziel wird, hört sie auf, ein gutes Maß zu sein.

Fehler 2: Die Abnahme konnte den Fehler gar nicht finden.

Mit den Daten des letzten Quartals reicht die Nachfrage weit über die Kapazität hinaus — der Deckungsbeitragsplan erreicht ohnehin 100 % Auslastung. Die Nebenbedingung ist in diesem Datensatz nicht bindend: Sie ändert nichts, also fällt sie nicht auf. Der Abnahmetest prüfte eine Regel, die gar nicht wirkte.

Nachgerechnet mit den Daten dieses Kapitels:

Im schwachen Monat ist die Vorgabe schlicht nicht erfüllbar — es gibt nicht genug Arbeit. Das Modell liefert dann gar keinen Plan mehr, und der Nachtlauf bricht ab.

Was geholfen hätte:

1. Die Vorgabe nicht als Nebenbedingung, sondern als Kennzahl im Bericht. Auslastung gehört gemessen, nicht vorgeschrieben.
2. Wenn sie doch ins Modell muss: weich. Eine Strafe für Leerlaufstunden macht das Modell nie unlösbar und macht sichtbar, was der Leerlauf kostet.
3. Abnahme mit einem Datensatz, in dem die Regel bindet. Eine Nebenbedingung, die im Testdatensatz nichts ändert, ist ungetestet — dasselbe Argument wie beim Mutationstest in Kapitel 23.

Micro-Quiz

1. b) Die Zielfunktion ist eine vollständige Aussage darüber, was zählt. Was nicht darin steht, ist für das Modell nicht „weniger wichtig”, sondern wertlos. (a) und (c) sind frei erfunden — an der Rechengenauigkeit liegt es nicht.

2. b) Eine harte Regel, die einmal nicht erfüllbar ist, macht das ganze Modell unzulässig: Statt eines schlechteren Plans kommt gar keiner. (a) stimmt tendenziell sogar umgekehrt — harte Regeln schränken den Suchraum ein und beschleunigen oft. (c) ist falsch, ändern lässt sich alles; es merkt nur niemand rechtzeitig.

3. b) Bei knapper Kapazität ist die volle Maschine die Voreinstellung, nicht die Leistung. Zu entscheiden ist ausschließlich, womit sie gefüllt wird — und genau das misst die Auslastung nicht.

Selbsttest

1. Auf „Was ist Ihnen wichtig?” antwortet jeder Betrieb mit einer Liste, in der alles wichtig ist — das ergibt keine Zielfunktion. „Welche Zahl steht im Jahresbericht?” liefert dagegen genau eine Größe und nebenbei die Information, wonach die Beteiligten beurteilt werden. Das erklärt, warum „Umsatz” gesagt wird, wo „Deckungsbeitrag” gemeint ist.
2. Beispiele: Anzahl bearbeiteter Tickets (belohnt das Abarbeiten einfacher Fälle), Termintreue in Prozent (belohnt das Aufgeben ohnehin verspäteter Aufträge), Lagerreichweite (belohnt Überbestände), Auslastung (belohnt lange, unrentable Aufträge).
3. Ab einer hinreichend großen Strafe wählt der Optimierer nie mehr die bestrafte Variante — das Ergebnis ist identisch. Der Unterschied zählt genau dann, wenn die Regel nicht erfüllbar ist: Die harte Variante liefert dann nichts, die weiche den am wenigsten schlechten Plan.
4. Lesart 1: Jeder Mitarbeiter höchstens zwei Wochenenden — eine Regel je Person. Lesart 2: Im Durchschnitt zwei Wochenenden — Ausgleich über das Team möglich. Sie fallen auseinander, sobald jemand krank wird: Unter Lesart 1 bleibt eine Schicht unbesetzt, unter Lesart 2 springt jemand ein drittes Mal ein.
5. Eine brauchbare Antwort nennt die Reihenfolge, in der Regeln aufgegeben werden, und wer informiert wird. „Das kommt nicht vor” ist keine Antwort, weil es eine Prognose über die Zukunft ist, die niemand einhalten kann — und weil der Fall erfahrungsgemäß genau dann eintritt, wenn die Planung am dringendsten gebraucht wird.

A.5 Lösungen zu Kapitel „Lineare Programmierung — Simplex, Dualität und Schattenpreise“

5.1 — Schlupf deuten. (a) Ressourcen 1 und 3 (Schlupf 0). (b) Ja: Überall ist s_i \cdot y_i = 0. (c) In Ressource 3 — der höchste Schattenpreis (9,8) bedeutet den größten Grenznutzen.

5.2 — Vorzeichen. Er hat die Zielfunktion für linprog negiert und die Dualwerte nicht zurückgedreht. Der korrekte Schattenpreis ist +45 €.

5.3 — Simplex von Hand. Starttableau mit s_1, s_2 in der Basis. Erste Iteration: Pivotspalte x_1 (-5), Quotienten 24/6 = 4 und 6/1 = 6 → Pivotzeile 1. Nach dem Tausch: x_1 = 4, Z = 20. Zweite Iteration: Pivotspalte x_2, Pivotzeile 2 → x_1 = 3, x_2 = 1{,}5, Z = 21. Optimum: \mathbf{x}^* = (3;\ 1{,}5), Z^* = 21, Schattenpreise y^* = (0{,}75;\ 0{,}50).

5.4 — Duales Problem. \min 24y_1 + 6y_2 u. d. N. 6y_1 + y_2 \ge 5, 4y_1 + 2y_2 \ge 4, y \ge 0. Lösung y^* = (0{,}75;\ 0{,}50). Probe der Restriktionen: 6\cdot0{,}75 + 0{,}5 = 5 ✓ (mit Gleichheit, weil x_1 > 0), 4\cdot0{,}75 + 2\cdot0{,}5 = 4 ✓ (ebenfalls Gleichheit, weil x_2 > 0). Zielwert 24\cdot0{,}75 + 6\cdot0{,}5 = 18 + 3 = 21 = Z^* ✓ — starker Dualitätssatz bestätigt.

5.5 — Unbeschränktheit. Der Solver wirft „Problem ist unbeschränkt“. Geometrisch: Der zulässige Bereich \{x_1 - x_2 \le 5,\ x \ge 0\} ist nach oben offen — man kann x_1 und x_2 gemeinsam beliebig wachsen lassen (z. B. x_1 = x_2 = t für t \to \infty), ohne eine Bedingung zu verletzen, und Z = 2t wächst mit. In der Praxis fehlt fast immer eine Kapazitätsgrenze.

5.6 — Gültigkeitsbereich. (a) Bei ca. 66,7 Stunden Prüfkapazität wird die Lackierzeit zum Engpass; der Schattenpreis der Prüfung fällt dann. (b) Zukaufen lohnt bis zu dem Punkt, an dem der Schattenpreis unter 18 €/h fällt. (c) Der Gewinnverlauf ist stückweise linear und konkav: Jedes Teilstück hat die Steigung des jeweils gültigen Schattenpreises, und die Steigungen werden immer flacher — jede zusätzliche Einheit bringt weniger, weil andere Engpässe nachrücken.

5.7 — Phase 1. Ansatz: Für jede Zeile mit b_i < 0 (nach Umformung zu \ge) eine künstliche Variable a_i \ge 0 einführen, Hilfszielfunktion \min \sum a_i lösen. Ist das Minimum 0, existiert eine zulässige Basislösung, und man startet Phase 2 mit dem erreichten Tableau. Ist es > 0, ist das Problem unzulässig. Für das Beispiel: Optimum (12;\ 0), Z = 36.

Finde den Denkfehler — Die 380 000-Euro-Maschine

1. Eine Ableitung gilt lokal. y_i = \partial Z^*/\partial b_i beschreibt die Steigung der Zielfunktion am aktuellen Punkt. Sie sagt: „Die nächste Stunde ist 50 € wert“ — nicht: „jede der nächsten 2 000 Stunden ist 50 € wert“. Der Werksleiter behandelt eine Ableitung wie eine Konstante und multipliziert sie mit einer großen Zahl. Genau daran scheitert die Rechnung.

2. Der wahre Verlauf ist stückweise linear und knickt ab. Solange der Lackierofen der Engpass bleibt, gilt tatsächlich 50 €/h. Irgendwann ist aber genug Ofenzeit da — dann bindet eine andere Ressource, und weitere Ofenstunden bringen nichts mehr. Am Beispiel aus dem Kapitelanfang (Zusatzstunden h am Lackierofen):

Bei h = 60 ist der Plan bei (0;\ 80) angekommen: Es werden nur noch Rahmen gebaut, und die Montage ist zum Engpass geworden. Ab dort fällt der Schattenpreis des Lackierofens auf 0. Der wahre Jahresnutzen der zweiten Maschine beträgt 3 000 €, nicht 100 000 € — die Hochrechnung überschätzt um Faktor 33. Die Amortisation dauert nicht 3,8 Jahre, sondern rund 127 Jahre.

Der Fehler geht dabei immer in dieselbe Richtung: Die lineare Hochrechnung ist stets zu optimistisch, weil der Schattenpreis mit wachsender Kapazität nur fallen, nie steigen kann. Wer so rechnet, kauft systematisch zu teuer ein.

3. Zwei fehlende Prüfungen. Erstens der Entartungstest: Sind mehr Nebenbedingungen aktiv als Variablen vorhanden, ist der Wert 50 € nur einer von vielen möglichen und hätte gar nicht als Einzelwert berichtet werden dürfen (siehe Toleranzen_und_Entartung.py). Zweitens der Gültigkeitsbereich: Bis zu welcher Kapazitätserhöhung bleibt dieser Schattenpreis überhaupt bestehen? Ohne diese Spanne ist die Zahl nicht interpretierbar.

4. Nicht extrapolieren — nachrechnen. Der zusätzliche Nutzen ergibt sich aus einem zweiten Solverlauf, nicht aus einer Multiplikation:

z_basis = -linprog(c, A_ub=A, b_ub=b, bounds=(0, None)).fun
b_neu = b.copy(); b_neu[0] += 2000                 # zweiter Lackierofen
z_neu = -linprog(c, A_ub=A, b_ub=b_neu, bounds=(0, None)).fun
print(f"Tatsaechlicher Zusatznutzen: {z_neu - z_basis:,.0f} EUR")   # 3.000 EUR

Das ist die allgemeine Regel für jede Sensitivitätsaussage über mehr als eine Grenzeinheit: Der Schattenpreis zeigt die Richtung, die Neuberechnung liefert den Betrag. Bei einer Investitionsentscheidung kostet ein zusätzlicher Solverlauf Millisekunden — und hier hätte er 380 000 € gespart.

Micro-Quiz

1 — (b). Genau der Satz vom komplementären Schlupf: s_i \cdot y_i = 0. Ist Schlupf vorhanden, muss der Dualwert null sein. (a) hat die Aussage in ihr Gegenteil verkehrt; (c) verwechselt Schlupf mit Auslastung — s_i = 12 heißt gerade, dass 12 Einheiten übrig sind.

2 — (b) Entartung. 7 aktive Bedingungen bei 5 Variablen bedeuten: Die Ecke ist überbestimmt, es gibt mehrere optimale Dualvektoren, und welchen der Solver zeigt, hängt vom gewählten Verfahren ab. (a) verharmlost genau den Fall, der Fehlentscheidungen produziert; (c) verwechselt Entartung mit Unlösbarkeit — der Plan selbst ist völlig in Ordnung und eindeutig.

3 — (b). Der Schlupf ist Solver-Rauschen in der Größenordnung der Maschinengenauigkeit — rechnerisch null, aber nicht == 0.0. Richtig ist abs(schlupf) < 1e-7. (a) unterstellt dem Solver einen Fehler, den er nicht gemacht hat; (c) ist frei erfunden — Schlupfwerte sind bei korrekt aufgestelltem Modell nie negativ, abgesehen von genau diesem Rauschen.

Selbsttest

1. Ungenutzte Kapazität; der Wert 0 kennzeichnet einen Engpass (bindende Bedingung).
2. Minimaler Quotient über positive Spalteneinträge. Nähme man die erste Zeile, würde eine Basisvariable negativ — die Lösung wäre unzulässig.
3. s_i y_i = 0: Entweder hat eine Ressource Reserven (dann ist sie nichts wert), oder sie ist knapp (dann kann sie einen positiven Preis haben).
4. Weil zur Maximierung die Zielfunktion negiert wurde; die Ableitung nach b_i dreht damit ebenfalls das Vorzeichen.
5. Eine fehlende Kapazitätsbeschränkung — der zulässige Bereich ist in Richtung der Zielfunktion offen.

A.6 Lösungen zu Kapitel „Gemischt-ganzzahlige Optimierung — Diskrete Entscheidungen und Branch-and-Bound“

6.1 — Runden widerlegen. Beispiel: \max x_1 + x_2 u. d. N. 10x_1 + 10x_2 \le 15, ganzzahlig. LP-Optimum Z = 1{,}5; Abrunden ergibt (0,0) mit Z = 0 — 100 % Verlust. Das ganzzahlige Optimum ist (1,0) mit Z = 1. Prinzip: kleine Zahlen plus knappe Kapazität.

6.2 — Big-M wählen. M = 250 (die bekannte Kapazität). Bei M = 10^6 bleibt das Modell korrekt, aber die LP-Relaxation wird extrem schwach: y_j darf schon bei x_j/10^6 liegen, die Schranke ist praktisch wertlos, und Branch-and-Bound muss weit mehr Knoten durchsuchen.

6.3 — Regeln übersetzen. (a) y_A + y_B \le 1. (b) \sum_{j=1}^4 y_j \ge 2. (c) y_1 + y_2 - 1 \le y_{\text{Lager}}. (d) 500\,y \le x \le 2000\,y mit y \in \{0,1\}. (e) \sum_{j=1}^3 y_j = 1.

6.4 — Branch-and-Bound. LP-Relaxation der Wurzel: nach Nutzen/Gewicht sortieren (8/5=1{,}6; 11/7=1{,}57; 6/4=1{,}5; 4/3=1{,}33). Gierig füllen: x_1=1 (Rest 9), x_2=1 (Rest 2), x_3 = 0{,}5 → Z_{LP} = 8+11+3 = 22. Verzweigen über x_3. Ast x_3=0: x_1=1,x_2=1,x_4=2/3 → Z = 21{,}67; weiter verzweigen → beste ganzzahlige Lösung (1,1,0,0) mit Z=19. Ast x_3=1: x_1=1, x_3=1, Rest 5 → x_2=5/7 → Z = 21{,}86; verzweigen führt auf (1,0,1,1) mit Z = 18 und (0,1,1,0) mit Z=17. Optimum: (1,1,0,0), Z = 19.

6.5 — Kardinalität variieren. (a) Ab K = 3 steigt der Ertrag nicht mehr wesentlich, weil bereits drei Positionen à 40 000 € das Budget von 100 000 € abdecken können. (b) Rechenzeit steigt zunächst (mehr Kombinationen), fällt bei großem K wieder (Restriktion bindet nicht mehr). (c) Der faire Preis ist die Differenz der Netto-Erträge zwischen K=3 und K=4 — bei den gegebenen Daten nahe null, weil die Obergrenze von 40 000 € bereits bindet.

6.6 — Big-M-Effekt. Erwartetes Muster: Knotenzahl und Laufzeit steigen deutlich mit M. Bei M = 10^9 ist die Relaxation so schwach, dass der Solver kaum noch prunen kann.

6.7 — Standortplanung. Modell wie in Projekt P4. Prüfen Sie: Gesamtkapazität der eröffneten Lager \ge Gesamtbedarf (140); bei Kapazität 80 je Lager sind mindestens \lceil 140/80 \rceil = 2 Lager nötig.

Finde den Denkfehler — Elf Lager, die keine Fixkosten kosten

1. Warum die Zahl kleiner ist. Ein größeres M lockert die Nebenbedingung \sum_j x_{ij} \le M y_i. Der zulässige Bereich des Modells wird also größer, und in einem größeren Bereich kann das Minimum nur kleiner oder gleich bleiben. Bei einem korrekt formulierten Modell dürfte das aber gar nicht auffallen: Solange y_i wirklich binär ist, ist M \cdot 1 = M ohnehin größer als jede mögliche Liefermenge — die Lockerung wäre wirkungslos. Dass sich der Zielwert überhaupt ändert, ist deshalb schon der Beweis, dass y_i nicht wirklich binär ist.

2. Die Binärvariablen. Sie stehen bei rund 4 \cdot 10^{-8} — nicht bei 0 und nicht bei 1. Die Ganzzahltoleranz von HiGHS (wie der meisten Solver) beträgt 10^{-6}. Alles, was näher als das an einer ganzen Zahl liegt, gilt als ganzzahlig. 4 \cdot 10^{-8} ist damit für den Solver eine saubere 0: „Lager geschlossen“.

Zugleich ist M so groß, dass

\sum_j x_{ij} \le \underbrace{7{,}2 \cdot 10^{9}}_{M} \cdot \underbrace{4 \cdot 10^{-8}}_{y_i} \approx 289

immer noch reichlich Liefermenge erlaubt. Das Lager liefert also, ohne offiziell offen zu sein. Der Fachbegriff für dieses Muster ist trickle flow: Ein verschwindend kleiner Schaltwert lässt einen großen Fluss durch, weil er mit einer riesigen Zahl multipliziert wird.

3. Die Bilanz. In der „Lösung“ liefern 11 von 12 Lagern tatsächlich Ware. Verbucht werden dafür 0,00 € Fixkosten statt der real anfallenden 35 847,91 €. Der gemeldete Zielwert von 12 441,96 € ist damit nicht etwa etwas zu optimistisch, sondern schlicht falsch: Die tatsächlichen Kosten dieses Plans betragen 48 289,86 € — fast das Doppelte der korrekten Lösung (26 525,28 €).

Und das ist die eigentliche Gemeinheit: Der Fehler tarnt sich als Erfolg. Niemand hinterfragt ein Ergebnis, das 53 % günstiger ausfällt als erwartet — man freut sich darüber.

4. Die Prüfung. Drei Tests, zusammen keine zwanzig Zeilen, die in jedes MILP-Auswertungsskript gehören:

# 1. Sind die Binaervariablen wirklich binaer?
assert np.abs(y - np.round(y)).max() <= 1e-6, "y ist nicht ganzzahlig"

# 2. Widerspricht sich die Loesung selbst?
liefert = x.sum(axis=1) > 1e-6
assert not (liefert & (y < 0.5)).any(), "Lager liefert, gilt aber als geschlossen"

# 3. Stimmt der Zielwert mit den Kosten der Loesung ueberein?
echte_kosten = FIXKOSTEN[liefert].sum() + (TRANSPORT * x).sum()
assert abs(echte_kosten - zielwert) < 1e-4 * echte_kosten, \
    f"Zielwert {zielwert} passt nicht zu den echten Kosten {echte_kosten}"

Test 3 ist der wichtigste. Er vergleicht nicht Modell mit Modell, sondern Modell mit Wirklichkeit — er rechnet die Kosten aus der ausgegebenen Lösung neu aus, ganz ohne Solver. Damit fängt er nicht nur den Big-M-Fehler, sondern jeden Fehler, bei dem die Zielfunktion etwas anderes bilanziert als der Plan tatsächlich kostet.

Vorbeugend gilt weiter die Regel aus dem Kapitel: M so klein wie möglich, hergeleitet aus einer echten Kapazität. Hier wäre das schlicht die Lagerkapazität — mehr kann ein Lager ohnehin nicht ausliefern.

Micro-Quiz

1 — (b). Der Gap (48\,200 - 47\,100)/48\,200 = 2{,}3\,\% ist eine Garantie, keine Schätzung: Besser als 47 100 € kann es nachweislich nicht werden, also ist der vorliegende Plan höchstens 2,3 % zu teuer. (a) wirft eine völlig brauchbare Lösung weg — genau der Fehler, den if status == OPTIMAL: ... else: return None produziert. (c) verwechselt die Schranke mit einem erreichbaren Wert: 47 100 € ist eine untere Schranke, es ist völlig offen, ob ein Plan mit diesen Kosten überhaupt existiert.

2 — (b). Die Laufzeit (a) ist ein realer, aber beherrschbarer Nachteil — man merkt ihn und kann reagieren. Der Trickle Flow dagegen ist still: Das Modell meldet Optimal, liefert eine Zahl, und niemand sieht, dass die Fixkosten verschwunden sind. Ein Fehler, den man bemerkt, ist immer harmloser als einer, den man nicht bemerkt. (c) ist frei erfunden — negative Kosten entstehen dabei nicht.

3 — (c). Ein Hinweis ist für CP-SAT unverbindlich: Er wird als Startlösung ausprobiert und verworfen, wenn er nicht zulässig ist. Das Ergebnis bleibt in jedem Fall korrekt (b ist also falsch), und INFEASIBLE bezieht sich immer auf das Modell, nie auf einen Hinweis (a ist falsch). Praktische Konsequenz: Prüfen Sie Ihre Startlösung selbst auf Zulässigkeit — sonst messen Sie einen Warm-Start-Effekt, den es gar nicht gibt.

Selbsttest

1. Weil die Relaxation mehr Lösungen zulässt (alle ganzzahligen plus gebrochene) — das Maximum über einer größeren Menge ist mindestens so groß.
2. Teilproblem unzulässig; Schranke schlechter als der Incumbent; LP-Lösung bereits ganzzahlig.
3. L\,y \le x \le U\,y mit binärem y.
4. Weil die LP-Relaxation dadurch schwächer wird: Die berechnete Schranke liegt weiter vom wahren Optimum entfernt, es kann weniger gekappt werden.
5. Die beste gefundene Lösung ist höchstens 3 % vom beweisbaren Optimum entfernt.

A.7 Lösungen zu Kapitel „Constraint Programming mit CP-SAT — Logik, Scheduling und Zuweisung“

7.1 — Propagation. Aus x_1 + x_2 = 8 und x_1 < x_2 folgt x_1 < 4, also x_1 \in \{2,3\} (denn x_2 = 8-x_1 \le 6 verlangt x_1 \ge 2) und entsprechend x_2 \in \{5,6\}. Aus 36 Kombinationen werden 2 zulässige.

7.2 — Hart oder weich. (a) hart. (b) weich, mittlere Strafe (~50). (c) hart. (d) weich, mittlere Strafe (~80, weil geteilte Dienste stark belasten). (e) hart, falls gesetzlich; sonst weich mit sehr hoher Strafe (~1000).

7.3 — Regeln ergänzen. (a) for s in (2,3): modell.Add(x["Frau_Albrecht", s] == 0) (b) Hilfsvariablen arbeitet_bauer, arbeitet_koch per AddMaxEquality an die Zuweisungssummen koppeln, dann modell.Add(arbeitet_bauer + arbeitet_koch <= 1). (c) Belohnung = negative Strafe: strafterme.append(-30 * folge_var), wobei folge_var per AddBoolAnd/OnlyEnforceIf an x_{p,0} \wedge x_{p,1} gekoppelt wird.

7.4 — Infeasibility. Mit MAX_VERTRETUNGEN = 0 meldet der Solver INFEASIBLE. Nach Einbau der Schlupfvariablen lässt der Solver alle vier Stunden ausfallen (4 × 10 000 = 40 000 Strafpunkte) — es geht nicht anders. Interessanter wird es bei MAX_VERTRETUNGEN = 1: Dann fällt genau die Stunde aus, für die am wenigsten qualifiziertes Personal zur Verfügung steht.

7.5 — Sudoku.

x = [[m.NewIntVar(1, 9, f"x{i}{j}") for j in range(9)] for i in range(9)]
for i in range(9): m.AddAllDifferent(x[i])                       # Zeilen
for j in range(9): m.AddAllDifferent([x[i][j] for i in range(9)]) # Spalten
for bi in range(3):
    for bj in range(3):
        m.AddAllDifferent([x[3*bi+i][3*bj+j] for i in range(3) for j in range(3)])
for i in range(9):
    for j in range(9):
        if vorgabe[i][j]: m.Add(x[i][j] == vorgabe[i][j])

Etwa 10 Zeilen Modellcode — und der Solver löst jedes Sudoku in Millisekunden. Das ist die Stärke globaler Constraints.

7.6 — Job-Shop erweitern. (a) Rüstzeiten: AddNoOverlap durch paarweise Disjunktionen mit Übergangszeit ersetzen, oder AddCircuit je Maschine mit Übergangsmatrix. (b) Verspätung: tardiness = MaxEquality(0, ende - faellig), in die Zielfunktion. (c) AddCumulative(intervalle, [1]*n, 2) statt AddNoOverlap für die Doppelmaschine.

7.7 — Wochendienstplan. Siehe Projekt P2. Kernpunkte: Nachtschicht-Folgeregel über AddImplication; „höchstens 5 Tage in Folge“ über gleitende Fenster (sum(x[p,t..t+5]) <= 5).

Finde den Denkfehler — Die Betriebsvereinbarung, die niemanden interessiert

1. Warum die Regel verletzt wird. Weil sie einen Preis hat. Eine weiche Nebenbedingung verbietet nichts — sie verteuert. Der Solver vergleicht in jedem Schritt, was ihn eine Verletzung kostet und was sie ihm einbringt. Bei einem Gewicht von 1 gegen 10 lohnt sich eine Drei-Tage-Serie, sobald sie auch nur ein Zehntel eines Wunsches rettet. Der Solver hat genau das getan, was im Modell steht — er hat nur nicht getan, was gemeint war.

2. Was (1, 10) wörtlich bedeutet. Nicht „Wunschfrei ist wichtiger“, sondern:

„Zehn Verstöße gegen die Betriebsvereinbarung sind für uns genauso schlimm wie ein einziger abgelehnter Wunschfrei-Tag. Bis zu diesem Verhältnis tauschen wir gerne.“

So ausgesprochen, würde niemand diesem Satz zustimmen. Genau das ist der Punkt: Gewichte sind Wechselkurse, keine Rangfolgen. Sie legen fest, wie viele Einheiten der einen Regel gegen eine Einheit der anderen getauscht werden — und wer sie nach Bauchgefühl setzt, unterschreibt einen Kurs, den er nie gelesen hat.

3. Der Kipppunkt. Die Tabelle aus Strafgewichte.py:

Ab Gewicht 30 verschwinden die Serien vollständig. Der Preis dafür sind 14 statt 6 abgelehnte Wünsche. Beachten Sie: Zwischen 30 und 100 ändert sich nichts mehr — ist die Regel einmal teuer genug, macht noch mehr Strafe keinen Unterschied. Es gibt also keinen Grund, „sicherheitshalber“ 10 000 zu nehmen; das verschlechtert nur die Konditionierung (Abschnitt 2.7).

Bemerkenswert ist außerdem, dass sich zwischen 1 und 2 gar nichts tut, zwischen 5 und 10 dagegen sehr viel. Wer ein einziges Gewicht ausprobiert, weiß nicht, ob er zufällig auf einem Plateau oder direkt an einer Kante steht.

4. Die Frage, die vorher zu stellen ist. Nicht „wie wichtig ist Ihnen diese Regel?“ — darauf lautet die Antwort immer „sehr“. Sondern:

„Wie viele abgelehnte Wunschfrei-Tage nehmen Sie in Kauf, um eine Drei-Tage-Serie zu vermeiden?“

Das ist eine Frage, die eine Zahl als Antwort hat. Und wenn der Auftraggeber sie nicht beantworten kann, legt man ihm die Tabelle aus (c) vor und lässt ihn eine Zeile auswählen. Das dauert eine Stunde und ersetzt drei Abstimmungsrunden.

Und wann gehört eine Regel gar nicht in die Zielfunktion? Wenn sie unverhandelbar ist. Gesetzliche Ruhezeiten, Qualifikationsanforderungen, eine Betriebsvereinbarung — das sind harte Nebenbedingungen. Dass das Modell dann INFEASIBLE melden kann, ist kein Nachteil, sondern die ehrliche Auskunft: Mit diesem Personalbestand ist kein zulässiger Plan möglich. Diese Aussage ist für die Klinikleitung wertvoller als ein Plan, der formal optimal ist und die Vereinbarung zwölfmal bricht.

Der Merksatz dazu: Alles, was einen Preis hat, wird irgendwann gekauft.

Micro-Quiz

1 — (b) wirkungslos. INFEASIBLE ist kein Abbruch, sondern ein Beweis: CP-SAT hat gezeigt, dass keine zulässige Lösung existiert. Mehr Zeit (a) oder mehr Arbeiter (c) ändern daran nichts — sie bestätigen dasselbe Ergebnis nur schneller. Der Unterschied zu UNKNOWN ist genau dieser: Dort wurde nichts gefunden, hier gibt es nichts. Die Ursache liegt in den harten Regeln; Anhang C zeigt, wie man die widersprüchliche Teilmenge isoliert.

2 — (b). AddNoOverlap ist kompakter und propagiert stärker, weil der spezialisierte Propagator alle Intervalle gemeinsam betrachtet statt paarweise. (a) ist falsch: Beide Formulierungen beschreiben dieselbe Menge zulässiger Lösungen, also auch dasselbe Optimum — der Unterschied liegt in der Laufzeit, nicht in der Qualität. (c) ist falsch: CP-SAT rechnet ausschließlich mit ganzen Zahlen, kontinuierliche Zeiten kann es gerade nicht.

3 — (b). Mehrfache Optima sind bei Scheduling der Normalfall, kein Fehler. (a) verwechselt Eindeutigkeit mit Korrektheit; (c) unterstellt ein Genauigkeitsproblem, das es nicht gibt — alle gefundenen Pläne haben exakt denselben Makespan. Praktische Konsequenz: assert plan == erwarteter_plan besteht mal und scheitert mal, ohne dass sich am Code etwas geändert hat. Prüfen Sie stattdessen assert makespan == 11 und die Einhaltung aller Regeln. Wer eine reproduzierbare Ausgabe braucht — etwa für ein Buch —, fixiert num_workers und random_seed.

Selbsttest

1. Sie entfernt Werte aus den Wertebereichen, die aufgrund der Bedingungen unmöglich sind — bevor gesucht wird. Dadurch schrumpft der Suchbaum drastisch.
2. Stärkere Propagation: Der spezialisierte Algorithmus betrachtet die Struktur als Ganzes (Matching-Theorie), nicht nur Paare.
3. Eine Variable mit Start, Dauer und Ende; sie garantiert automatisch start + dauer == ende.
4. Weil jede zusätzliche harte Bedingung das Risiko von INFEASIBLE erhöht — und eine Fehlermeldung dem Anwender nicht hilft.
5. Weil Anwender die Frage „Warum ich?“ stellen. Ohne Antwort wird das System umgangen.

A.8 Lösungen zu Kapitel „Graphen, Flüsse und Touren — Min-Cost-Flow, Matching und VRP“

8.1 — Flusserhaltung. b_i = (15+3) - (12+8) = -2 → Senke (Nettobedarf 2).

8.2 — Unlösbarkeit. Die Summe aller Flusserhaltungsgleichungen ergibt \sum_i b_i = 0 (jede Kante taucht einmal mit +1 und einmal mit -1 auf). Ist die Summe ungleich null, widersprechen sich die Gleichungen. Bei Angebotsüberschuss führt man einen künstlichen Dummy-Senkenknoten mit dem Restbedarf und Kosten 0 ein.

8.3 — Transportproblem. (a) Angebot 30+25+45 = 100, Bedarf 25+30+20+25 = 100 ✓ (b) Optimale Kosten: 790. Transportplan:

Beachten Sie, dass Werk 3 seine günstigste Verbindung (L4 zu 5) voll ausschöpft und W2 ausschließlich L1 beliefert (9), obwohl L4 mit 7 billiger wäre — dort ist der Bedarf bereits von W3 gedeckt. (c) Die Lösung ist ganzzahlig, obwohl nicht gefordert — die Transportmatrix ist total unimodular, alle Ecken sind ganzzahlig.

8.4 — Zuordnung mit Verboten. Kosten auf einen sehr hohen Wert setzen (kosten[2][2] = 1e6) oder mit np.inf arbeiten (bei linear_sum_assignment erlaubt). Die Lösung weicht auf die zweitbeste Zuordnung für Carla aus; die Gesamtkosten steigen um die Differenz.

8.5 — Engpass finden. Die Dualwerte der Kapazitätsschranken (res.upper.marginals bei linprog) zeigen es direkt; alternativ jede Kapazität einzeln um 1 erhöhen und neu rechnen. Im Beispiel ist die Kante Werk_A → Umschlag der Engpass (voll ausgelastet, günstigster Weg).

8.6 — VRP variieren. (a) Mit 3 Fahrzeugen werden die Touren länger, die Gesamtfahrzeit steigt leicht, die Auslastung deutlich. (b) Unlösbar, sobald \text{Kapazität} \times \text{Fahrzeuge} < \text{Gesamtbedarf} (hier: bei 3 Fahrzeugen à 10 sind 30 < 37 → unlösbar) oder wenn Zeitfenster nicht mehr eingehalten werden können. (c) 1 s liefert meist eine brauchbare, 30 s eine spürbar bessere Lösung — die Metaheuristik verbessert kontinuierlich. (d) Doppelte Servicezeit kann Zeitfenster verletzen → möglicherweise unlösbar.

8.7 — TSP mit MTZ. Erwartetes Ergebnis: Bei 8 Städten löst das MILP in Sekunden. Ab etwa 12–15 Städten wird die schwache MTZ-Relaxation zum Problem, und die Laufzeit steigt stark — während OR-Tools weiterhin in Sekundenbruchteilen sehr gute Touren liefert.

Finde den Denkfehler — Die vergessene Dimension

1. Was die Fahrzeuge tun. Fahrzeuge 1, 2 und 3 fahren gar nicht — sie stehen mit null Stopps im Depot. Fahrzeug 4 bedient alle 16 Kunden und lädt dabei 37 Paletten bei einer Kapazität von 10. Es ist um 270 % überladen. Physikalisch ist dieser Plan nicht ausführbar; im Modell ist er die beste Lösung.

Dass ein einzelnes Fahrzeug alles fährt, ist übrigens völlig folgerichtig: Ohne Ladungsgrenze ist jede zusätzliche Tour reine Zusatzstrecke (der Weg vom Depot zum ersten Kunden und zurück). Ein Optimierer, der nur Kilometer minimiert, wird deshalb immer alles auf ein Fahrzeug legen. Das leere Depot ist das Symptom.

2. Warum die Bibliothek nichts gemerkt hat. Weil im Modell keine Ladung existiert. Die Routing-Bibliothek kennt keine Kapazität als Begriff — sie kennt Dimensionen: benannte Größen, die sich entlang einer Tour aufsummieren und begrenzt werden können. Distanz ist eine Dimension, Zeit ist eine, Ladung wäre eine.

Dass KAPAZITAETEN = [10, 10, 10, 10] im Datenteil steht, ändert daran nichts. Eine Liste in Ihrem Python-Programm ist keine Nebenbedingung. Sie wird erst zu einer, wenn AddDimensionWithVehicleCapacity sie dem Modell übergibt. Das ist eine allgemeine Lehre, nicht nur für Routing: Daten, die kein Constraint anfasst, sind Dekoration.

3. Warum das bessere Ergebnis das gefährliche ist. Ein Modellfehler, der zu INFEASIBLE oder zu absurd hohen Kosten führt, fällt sofort auf. Dieser hier führt zu einem Ergebnis, das 43 % besser aussieht als die korrekte Lösung — und das verteidigt man gegenüber dem Auftraggeber, statt es zu hinterfragen. Es ist dasselbe Muster wie bei der Big-M-Falle in Abschnitt 6.10: Der Fehler tarnt sich als Erfolg.

Die Regel dazu lautet: Ein Optimierungsergebnis, das deutlich besser ausfällt als erwartet, ist zuerst ein Fehlerverdacht. Freuen Sie sich erst, nachdem Sie nachgerechnet haben.

4. Die Prüfung — und warum sie unabhängig sein muss.

for fahrzeug, (ladung, kapazitaet) in enumerate(zip(ladungen, KAPAZITAETEN)):
    assert ladung <= kapazitaet, \
        f"Fahrzeug {fahrzeug + 1}: {ladung} Paletten bei Kapazitaet {kapazitaet}"

Dabei wird ladung aus der ausgegebenen Tour aufsummiert — also aus der Liste der angefahrenen Kunden und deren Bedarfen. Entscheidend ist, was man dafür nicht benutzt:

# FALSCH als Pruefung:
ladung = loesung.Value(routing.GetDimensionOrDie("Ladung").CumulVar(index))

Diese Zeile fragt das Modell, ob das Modell sich an sich selbst hält. Existiert die Dimension „Ladung“ gar nicht, stürzt sie ab — und existiert sie, kann sie per Konstruktion nie verletzt sein. Sie prüft also entweder nichts oder gar nichts.

Die allgemeine Regel: Eine Prüfung, die dieselben Bausteine verwendet wie das Modell, prüft das Modell gegen sich selbst. Nützlich ist nur eine Prüfung, die von der ausgegebenen Lösung ausgeht und die Anforderungen der Wirklichkeit unabhängig nachrechnet — genau wie die Kostengegenrechnung in Abschnitt 6.10 und die Verbrauchsprüfung in Abschnitt 1.10.

Micro-Quiz

1 — (b) totale Unimodularität. Jede quadratische Teilmatrix hat Determinante 0, +1 oder -1; bei ganzzahliger rechter Seite sind deshalb alle Ecken des zulässigen Bereichs ganzzahlig. Da das LP-Optimum nach dem Fundamentalsatz in einer Ecke liegt, ist es automatisch 0/1-wertig. (a) unterschätzt das: Es ist kein Zufall, sondern eine Struktureigenschaft, die für jede Kostenmatrix gilt. (c) ist falsch — linprog rundet nichts.

2 — (b) die Struktur geht verloren. „Höchstens 4 von 12“ ist eine Kardinalitätsregel; ihre Zeile passt nicht in das Schema, das die totale Unimodularität sichert. Die Relaxation kann dann Brüche liefern (etwa vier Monteure zu je 0,75 Überstunden), und man braucht Binärvariablen und Branch-and-Bound. (a) ist die gefährliche Fehlannahme: Die Eigenschaft ist zerbrechlich, eine einzige zusätzliche Zeile genügt. (c) verwechselt „schwerer zu lösen“ mit „unlösbar“.

3 — (b) fehlende Dimension. Ohne begrenzende Dimension ist jede zusätzliche Tour reine Zusatzstrecke — ein Optimierer legt dann folgerichtig alles auf ein Fahrzeug. Genau dieses Bild zeigt Abschnitt 8.7. (a) wäre zu prüfen, wenn die Lösung schlecht aussähe, nicht wenn sie verdächtig gut ist. (c) ist zwar eine sinnvolle Datenprüfung, erklärt aber nicht, warum drei Fahrzeuge unbenutzt bleiben.

Selbsttest

1. Abfluss minus Zufluss = Knotensaldo; entspricht der Kirchhoffschen Knotenregel.
2. Wegen totaler Unimodularität sind alle Ecken des Polyeders ganzzahlig, und das LP-Optimum liegt in einer Ecke.
3. Isolierte Kreise, die das Depot nicht enthalten. MTZ führt Rangvariablen ein, die entlang benutzter Kanten streng wachsen müssen — in einem Kreis unmöglich.
4. Weil die MTZ-Relaxation sehr schwach ist und spezialisierte Metaheuristiken um Größenordnungen bessere Ergebnisse in kürzerer Zeit liefern.
5. Kapazität < Bedarf (Summen vergleichen); Zeitfenster physisch unerreichbar (Direktfahrt prüfen); zu wenige Fahrzeuge für die Zeitfenster (Fahrzeugzahl variieren).

A.9 Lösungen zu Kapitel „Metaheuristiken — wenn der exakte Solver aussteigt“

9.1 — Die Kurzsichtigkeit von Hand. Ab Schwarz wählt die Faustregel: Schwarz → Dunkelrot (26) → Rot (5) → … und muss dann in die helle Gruppe: Rot → Weiß (50) → Elfenbein (2) → Beige (2). Summe 85 Minuten — also noch einen Deut schlechter als die 84 ab Weiß. Der Grund ist derselbe: Die Regel erwischt den Gruppenwechsel an der teuersten Stelle. Bemerkenswert ist aber, dass der Startpunkt kaum etwas ändert. Das ist typisch: Eine kurzsichtige Regel scheitert nicht am Anfang, sondern an der Reihenfolge, in der sie ihre Möglichkeiten verbraucht.

9.2 — Zuggröße und Temperatur. Gesucht ist T mit e^{-70/T} = e^{-1}, also T = 70. Die getesteten Temperaturen liegen zwischen 0,5 und 8 — allesamt eine Größenordnung darunter. Bei T_0 = 8 hat eine mediane Verschlechterung die Annahmewahrscheinlichkeit e^{-70/8} \approx 0{,}00016. Genau das ist der Punkt der Warnung im Kapitel: Die verbreitete Regel „20 bis 50 % Annahmequote“ würde hier T_0 \approx 50 verlangen, und bei dieser Temperatur ist die Suche ein reiner Zufallslauf.

9.3 — Die teure Bewertung. Statt delta_verschieben die Reihenfolge tatsächlich umbauen und gesamtruestzeit() neu rechnen. Bei n = 200 kostet das rund 200 Matrixzugriffe statt sechs. Erwartung: Die Zugzahl je Sekunde bricht um etwa zwei Größenordnungen ein. Bei gleichem Zeitbudget kommt die Suche entsprechend weniger weit; bei gleichem Zugbudget ist das Ergebnis identisch (die Bewertung ist ja korrekt, nur langsam). Genau diese Unterscheidung ist der Lehrpunkt: Die Implementierung ändert nicht das Verfahren, sondern nur, wie viel davon in das Zeitbudget passt.

9.4 — Der Umschlagpunkt genauer. Sinnvolle Zwischengrößen sind 250, 300, 350 und 400. Zu erwarten ist ein verwaschener Übergang, kein scharfer Punkt: Der exakte Solver verschlechtert sich nicht sprunghaft, sondern sein Gap wächst, und irgendwann liegt seine beste gefundene Lösung über der heuristischen. Wo genau das passiert, hängt zusätzlich vom Zeitlimit ab — mit 300 Sekunden statt 30 verschiebt sich der Punkt nach oben. Die belastbare Aussage ist deshalb nie „ab n = 380“, sondern immer „ab n \approx 380 bei diesem Zeitbudget“.

9.5 — Zerstören nach Maß. Die kostenbasierte Zerstörung entfernt gezielt dort, wo etwas zu holen ist, und findet deshalb pro Runde mehr. Sie hat aber zwei Nachteile: Sie muss die Übergangskosten jedes Mal sortieren, und die entfernten Aufträge liegen über den ganzen Plan verstreut — das Teilproblem für CP-SAT ist damit schwieriger als ein zusammenhängendes Fenster gleicher Größe, weil auch alle Einfügestellen offen sind.

Die Aufgabe ist bewusst so gestellt, dass die Antwort gemessen werden muss. Wer nur die Ergebniswerte vergleicht, kann Strategie und Rundenzahl nicht trennen. Die saubere Auswertung protokolliert beides: Verbesserungen je Runde (Güte der Strategie) und Runden je Sekunde (ihr Preis).

Finde den Denkfehler — „Unsere Heuristik ist 6 % besser“

Es fehlt die Schranke.

Alles, was der Kollege sagt, stimmt. Der Fehler liegt darin, was er nicht sagt: Die Ersparnis wird gegen die bisherige Praxis gemessen, nicht gegen das Mögliche. Damit beantwortet die Zahl eine andere Frage als die, die das Management stellt.

Metaheuristik_vs_Exakt.py liefert die fehlende Zahl in der Spalte Schranke: 1 768 Minuten. Der Abstand der vorgestellten Lösung zum Bestmöglichen beträgt also bis zu 25 %, nicht 0 %. In derselben Nacht, in der 640 Stunden gefeiert werden, liegen möglicherweise weitere 2 000 Stunden ungenutzt herum.

Die Konsequenz ist keine Absage an das Projekt — 6,2 % sind echt und werden verdient. Die Konsequenz ist eine ehrliche Fortschreibung: „Wir heben 6,2 % und wissen, dass bis zu einem Viertel noch offen ist. Der nächste Schritt ist LNS.“ Wer die Schranke verschweigt, erklärt das Projekt für abgeschlossen und lässt den größeren Teil liegen.

Dasselbe Muster in anderer Verkleidung: Kapitel Handelsmaschine, Data_Snooping.py — dort fehlt nicht die Schranke, sondern die Zahl der Versuche. Beide Male macht eine weggelassene Kennzahl aus einem korrekten Ergebnis eine irreführende Aussage.

Micro-Quiz

1. b) Eine lokale Suche lebt von der Zahl geprüfter Züge. Die volle Summe kostet O(n) statt O(1) — bei 500 Aufträgen zwei Größenordnungen weniger Züge im selben Zeitbudget. Numerisch ist an der vollen Summe nichts falsch (a), und die Konvergenzaussagen zu Simulated Annealing hängen nicht an der Bewertungsfunktion (c).

2. b) Die angenommenen Verschlechterungen summieren sich. 0,29 % von mehreren hunderttausend Zügen sind einige hundert angenommene Verschlechterungen zu je rund 70 Minuten — genug, um die Suche auf das 2,1-fache der Startlösung zu tragen. Die Annahmewahrscheinlichkeit sinkt im Lauf (a ist falsch), und numerisch instabil ist nichts (c).

3. b) Die untere Schranke. Sie ist unabhängig davon, wie gut die gefundene Lösung ist, und die einzige verfügbare Aussage darüber, wie viel Luft noch nach oben ist. (c) klingt plausibel, ist hier aber falsch: Die CP-SAT-Lösung war schlechter als die Faustregel und damit als Startlösung unbrauchbar.

Selbsttest

1. Kurzsichtig heißt: Sie bewertet einen Schritt nach seinen Kosten, nicht nach dem, was er übrig lässt. Das ist nicht dasselbe wie schlecht — im Schnellstart trifft sie die ersten drei Schritte genau richtig, und bei 500 Aufträgen ist sie besser als ein abgebrochener exakter Lauf.
2. Weil sich beim Umdrehen eines Teilstücks alle Übergänge innerhalb des Stücks umkehren. Bei s_{i,j} = s_{j,i} heben sie sich weg und es bleiben zwei geänderte Kanten; bei s_{i,j} \neq s_{j,i} ändern sich alle, und die Bewertung kostet wieder O(n).
3. Die untere Schranke — aus einem exakten Lauf mit Zeitlimit. Ohne sie ist „12 % Verbesserung“ eine Aussage über die Vergangenheit, nicht über die Güte.
4. Erstens Sättigung: Das Fenster ist zu klein für die nötigen Umbauten — erkennbar an vielen Runden mit sehr wenigen Verbesserungen. Zweitens Erschöpfung: Der Plan ist für diese Nachbarschaft austherapiert — erkennbar daran, dass auch ein größeres Fenster nichts mehr findet. Der erste Fall ruft nach einem größeren Fenster, der zweite nach einer anderen Zerstörungsstrategie.
5. Weil er von der Problemstruktur abhängt (wie gut die Relaxation ist, wie stark die Symmetrie), vom Zeitbudget und von der Qualität der Startheuristik. Für die Standortplanung aus Kapitel MILP liegt er woanders als für die Rüstzeiten hier.

A.10 Lösungen zu Kapitel „Spaltengenerierung“

10.1 — Das Abbruchkriterium. Die Eins ist der Zielfunktionskoeffizient eines Musters: Jedes geschnittene Muster verbraucht genau eine Mutterrolle, und die Zielfunktion lautet \min \sum_p x_p. Die reduzierten Kosten einer neuen Spalte sind c_p - \pi^\top a_p = 1 - \sum_i \pi_i a_{ip}; sie sind negativ — die Spalte lohnt sich also —, wenn \sum_i \pi_i a_{ip} > 1.

Wäre die Zielfunktion eine andere — etwa „minimiere den Verschnitt in Millimetern” —, stünde dort statt der Eins der Verschnitt des Musters. Die Eins ist also kein Zauberwert, sondern schlicht die Kosten der Spalte.

10.2 — Die Startbasis. Ein Muster, das nur eine einzige Breite enthält, ist immer zulässig: \lfloor W / b_i \rfloor Stücke der Breite i passen in jede Rolle. Mit diesen n Mustern lässt sich jeder Bedarf decken — notfalls sehr verschwenderisch, aber zulässig.

Eine leere Startmenge wäre ein Problem, weil das Master-LP dann unzulässig ist: Es gibt keine Spalten, mit denen sich die Bedarfszeilen erfüllen ließen. Ohne zulässige Lösung gibt es keine Dualwerte, und ohne Dualwerte kann das Pricing nicht arbeiten. Die Schleife käme nie in Gang.

(In der Literatur behilft man sich alternativ mit künstlichen Variablen und sehr hohen Strafkosten — dieselbe Idee wie die Big-M-Phase des Simplex aus Kapitel 5.)

10.3 — Die Kennzahl prüfen. Zu erwarten ist ein deutlicher, monotoner Zusammenhang: Je mehr Stücke auf eine Rolle passen, desto kleiner die Ersparnis. Bei zwei Stücken je Rolle entscheidet jede Paarung, und die Faustregel verschenkt regelmäßig ganze Rollen; ab acht bis zehn Stücken ist sie praktisch immer optimal.

Der Grund ist ein Verhältnis: Der Verschnitt einer Rolle ist höchstens so groß wie das kleinste nicht mehr passende Stück. Sind die Stücke klein gegen die Rolle, ist auch dieser Rest klein — und der Gesamtverschnitt nähert sich der theoretischen Untergrenze \lceil \sum_i b_i d_i / W \rceil, die jede Methode erreichen muss.

10.4 — Dienstplanung. Eine „Spalte” ist ein vollständiger zulässiger Wochenplan einer Person: an welchen Tagen sie welche Schicht übernimmt.

• Ins Master gehört, was Personen miteinander koppelt: Jede Schicht muss besetzt sein (\sum_p a_{sp} x_p \ge Bedarf je Schicht s), und jede Person bekommt genau einen Plan.
• Ins Teilproblem gehört, was innerhalb einer Person gilt: Höchstarbeitszeit, Ruhezeiten, Qualifikation, keine zwei Schichten am selben Tag, höchstens zwei Wochenenden im Monat.

Das ist der eigentliche Gewinn der Zerlegung: Die komplizierten arbeitsrechtlichen Regeln stehen im Teilproblem und werden dort einmal je Person geprüft, statt das Master zu überfrachten. Das Teilproblem ist meist ein kürzester Weg über ein Zeit-Zustands-Netz (Kapitel 8) statt eines Rucksacks.

10.5 — Branch-and-Price. Das Problem: Verzweigt man auf einer Mustervariablen (x_p \le 3 gegen x_p \ge 4), so ist diese Bedingung im Pricing nicht darstellbar. Das Teilproblem erzeugt Muster, es kennt keine Verzweigungsentscheidungen über einzelne Spalten — es könnte im nächsten Schritt genau das ausgeschlossene Muster wieder erzeugen.

Branch-and-Price löst das, indem es auf Originalgrößen verzweigt statt auf Spalten: etwa „in wie vielen Rollen kommen Breite i und Breite j gemeinsam vor?” Solche Bedingungen lassen sich ins Pricing-Teilproblem einbauen, weil sie über die Struktur eines Musters sprechen und nicht über seine Identität.

Für das Kapitel genügt der einfachere Weg: das ganzzahlige Master über die erzeugten Spalten. Es ist nicht garantiert optimal, liegt in der Praxis aber fast immer auf oder dicht bei der Schranke — hier exakt darauf (73 gegen 72,92).

Finde den Denkfehler — „Die LP-Lösung sagt 72,92 — also runden wir auf“

Das Aufrunden kostet sechs Rollen — acht Prozent.

Nachgerechnet mit denselben 38 Mustern:

Der Fehler steckt in der Vorstellung, „aufrunden” koste höchstens eine Rolle. Aufgerundet wird nicht eine Zahl, sondern dreizehn — je Muster eine. Jede einzelne Aufrundung kostet bis zu eine Rolle, und in der Summe sind es sechs.

Die Schranke sagt: Weniger als 73 Rollen sind unmöglich. Sie sagt nicht: Jede zulässige Lösung liegt höchstens eine Rolle darüber. Das ist die Verwechslung von unterer Schranke und Gütegarantie — dieselbe Verwechslung wie beim MIP-Gap in Abschnitt 6.8, nur in die andere Richtung.

Was der Kollege stattdessen hätte tun müssen: das Master ein zweites Mal lösen, diesmal mit integrality=1 über genau die Spalten, die er ohnehin schon erzeugt hat. Das ist eine Zeile, dauert Millisekunden und liefert 73 statt 79. Er hatte alles dafür bereits vorliegen.

🎯 Die allgemeine Lehre Eine gebrochene LP-Lösung ist kein Plan, sondern eine Schranke. Der Weg zur ganzzahligen Lösung führt über den Solver, nicht über ceil().

Micro-Quiz

1. b) Das Mustermodell kennt keine einzelnen Rollen und damit keine austauschbaren Objekte — die Symmetrie verschwindet. (a) trifft zufällig auch zu, ist aber nicht der Grund; (c) ist falsch, die LP-Lösung ist hier gerade nicht ganzzahlig (72,92).

2. b) Ein Rucksackproblem: Nutzen sind die Schattenpreise, Gewichte die Breiten, Kapazität die Rollenbreite. (c) beschreibt eine Heuristik — dann wäre das Verfahren nicht mehr exakt, weil man nie sicher wüsste, ob es wirklich kein lohnendes Muster mehr gibt.

3. b) Die untere Schranke von 33,60 beweist, dass mindestens 34 Rollen nötig sind. Damit weiß man, dass die 35 der Faustregel höchstens eine daneben liegen — und kann aufhören zu suchen. Genau diese Aussage kann eine Heuristik allein nie liefern (Kapitel 9).

Selbsttest

1. Freie Antwort. Typische Fälle: identische Maschinen, identische Fahrzeuge, identische Schichten, identische Behälter. Immer dort, wo mehrere gleichartige Objekte indiziert werden, beschreibt jede Lösung sich selbst in vielen Umbenennungen.
2. Eine Spalte ist ein Schnittmuster: Sie sagt für jede bestellte Breite, wie viele Stücke davon aus einer Mutterrolle geschnitten werden. Der Vektor a_p hat eine Zeile je Breite.
3. Aus den Dualwerten des Master-LPs — den Schattenpreisen der Bedarfszeilen (Abschnitt 5.6). Sie sagen, was ein zusätzliches Stück jeder Breite an Rollen kostet.
4. Weil das Abbruchkriterium eine Aussage über alle Muster macht: Das Pricing sucht das beste unter sämtlichen zulässigen Mustern. Findet es keines mit reduzierten Kosten unter null, gibt es auch keines — die LP-Lösung ist über der vollständigen Spaltenmenge optimal.
5. Die durchschnittliche Stückzahl je Behälter, also Behältergröße geteilt durch mittlere Stückgröße. Liegt sie bei zwei bis drei, lohnt sich exakte Optimierung; ab sechs bis acht ist eine Faustregel meist schon so gut wie das Optimum.

A.11 Lösungen zu Kapitel „Quadratische und nichtlineare Optimierung — KKT, Lagrange, Konvexität“

11.1 — Konvexität einordnen. PSD (alle \ge 0) → konvex, aber nicht streng konvex; die Lösung ist nicht notwendig eindeutig. Der Eigenwert 0 bedeutet eine flache Richtung: Entlang des zugehörigen Eigenvektors ändert sich der quadratische Term nicht — es gibt eine Rinne statt eines Punktes.

11.2 — Komplementärer Schlupf. Ja, verträglich: \lambda_i w_i = 0 gilt für alle i (w_2 = 0 mit \lambda_2 > 0; die anderen mit \lambda = 0). \lambda_2 = 0{,}03 bedeutet: Würde man Titel 2 zwingen, ein kleines positives Gewicht zu tragen, verschlechterte sich der Zielwert um 0,03 je Einheit — die Nichtnegativitätsschranke ist dort bindend.

11.3 — KKT von Hand. \mathcal{L} = x_1^2 + x_2^2 + \lambda(4 - x_1 - x_2). Stationarität: 2x_1 = \lambda, 2x_2 = \lambda → x_1 = x_2. Bindend (\lambda > 0): x_1 + x_2 = 4 → x_1 = x_2 = 2, \lambda = 4. Prüfung: \lambda = 4 > 0 ✓, f = 8. Interpretation: Würde die Forderung auf \ge 4{,}1 steigen, stiege f um etwa 4 \cdot 0{,}1 = 0{,}4. Probe: 2\cdot(2{,}05)^2 = 8{,}405 ✓.

11.4 — Unmögliche Korrelationsmatrix. Eigenwerte \approx (-0{,}62;\ 1{,}0;\ 2{,}62) → nicht PSD, also unmöglich. Anschaulich: Wenn A stark positiv mit B korreliert und B stark positiv mit C, kann A nicht gleichzeitig stark negativ mit C korrelieren — Korrelation ist eingeschränkt transitiv. Formal: \rho_{AC} \ge \rho_{AB}\rho_{BC} - \sqrt{(1-\rho_{AB}^2)(1-\rho_{BC}^2)} = 0{,}81 - 0{,}19 = 0{,}62; verlangt waren -0{,}9.

11.5 — Gewichtung untersuchen. Erwartetes Muster: Größeres \alpha → mehr Rendite, mehr Konzentration im Titel mit höchstem \mu. Größeres \beta → gleichmäßigere Gewichte, Entropie steigt Richtung \ln 4 = 1{,}386. Ab etwa \beta \approx 0{,}1 dominiert die Entropie und man nähert sich der Gleichgewichtung. Empfehlung an einen Ausschuss: Nicht mit \beta argumentieren, sondern mit der resultierenden Maximalposition — „mit dieser Einstellung liegt keine Position über 40 %“ ist verständlich, „\beta = 0{,}015“ nicht.

11.6 — Nicht-Konvexität demonstrieren. Mit der bewusst fehlerhaft konstruierten Matrix finden 20 Startpunkte typischerweise mehrere verschiedene Optima; die „Portfoliovarianz“ w^\top\Sigma w kann bei geeigneten Gewichten negativ werden (der zugehörige Eigenvektor liegt allerdings teilweise außerhalb des zulässigen Bereichs w \ge 0{,}001, \sum w = 1 — deshalb fällt der Fehler bei naiver Prüfung nicht auf).

Finde den Denkfehler — Die Kovarianzmatrix aus dem Controlling

1. Ohne zu rechnen. Stellen Sie sich die drei Anlagen als drei Personen vor, die nebeneinander gehen. A und B gehen fast im Gleichschritt (0{,}9). B und C gehen fast im Gleichschritt (0{,}9). Können A und C dann in entgegengesetzte Richtungen laufen? Nein — wenn A B folgt und B C folgt, muss A ungefähr auch C folgen. Korrelation ist zwar nicht transitiv im strengen Sinne, aber sie ist eingeschränkt: Zwei starke Bindungen zwingen die dritte in einen engen Bereich.

Genau beziffern lässt sich das. Damit eine 3\times3-Korrelationsmatrix überhaupt existieren kann, muss gelten:

\rho_{AC} \in \left[\ \rho_{AB}\rho_{BC} - \sqrt{(1-\rho_{AB}^2)(1-\rho_{BC}^2)},\ \ \rho_{AB}\rho_{BC} + \sqrt{(1-\rho_{AB}^2)(1-\rho_{BC}^2)}\ \right]

Mit \rho_{AB} = \rho_{BC} = 0{,}9 ergibt das [0{,}620;\ 1{,}000]. Der angesetzte Wert -0{,}9 liegt weit außerhalb. Diese drei Zahlen können nicht gleichzeitig zutreffen — mindestens eine der drei Quartalsauswertungen misst etwas anderes, als der Analyst annimmt (anderer Zeitraum, andere Frequenz, andere Bereinigung).

2. Die Eigenwerte von \mathbf{R} lauten (-0{,}8;\ 1{,}9;\ 1{,}9). Ein negativer Eigenwert bedeutet: Die Matrix ist nicht positiv semidefinit. Es gibt eine Richtung im Gewichtsraum — hier ungefähr (0{,}58;\ -0{,}58;\ 0{,}58), der Eigenvektor zu -0{,}8 —, entlang derer die quadratische Form negativ wird. Genau diese Richtung hat scipy gefunden: Das Ergebnis (1{,}5;\ -2{,}0;\ 1{,}5) ist ein Vielfaches davon.

Der Test dafür ist eine Zeile und gehört vor jede Risikorechnung:

eigenwerte = np.linalg.eigvalsh(S)
assert eigenwerte.min() >= -1e-10, \
    f"Kovarianzmatrix nicht positiv semidefinit: kleinster Eigenwert {eigenwerte.min():.3f}"

3. Warum das kein Rechenfehler ist. scipy hat exakt die Aufgabe gelöst, die man ihm gestellt hat: „minimiere \mathbf{w}^\top\mathbf{S}\mathbf{w}“. Dass dieser Ausdruck bei nicht positiv semidefinitem \mathbf{S} beliebig negativ werden kann, ist eine Eigenschaft der Eingabe, nicht des Verfahrens. success: True heißt hier — wie in Abschnitt 11.6 — nur: „Ich bin an einer Stelle angekommen, an der es nicht weiter bergab geht.“ Dass es überhaupt bis -0{,}254 bergab ging, lag allein an den Schranken \pm 2; ohne sie liefe das Verfahren gegen -\infty.

Eine Varianz ist definitionsgemäß eine erwartete quadratische Abweichung und damit \ge 0. Ein negativer Wert ist kein „besonders gutes Portfolio“, sondern der Beweis, dass die Eingabegrößen keine gemeinsame Wirklichkeit beschreiben.

4. Warum die Fehlermeldung das Wertvollste war. CVXPY prüft vor dem Rechnen, ob das Problem konvex ist. Bei einem nicht positiv semidefiniten \mathbf{S} ist quad_form(w, S) es nicht — und CVXPY verweigert die Arbeit, statt eine bedeutungslose Zahl zu liefern. Der DCPError war also keine Einschränkung der Bibliothek, sondern eine Diagnose: Er hat auf einen Datenfehler hingewiesen, den drei Quartalsberichte und ein Analyst übersehen hatten.

Der Ausweg auf scipy hat das Warnsystem umgangen, nicht das Problem gelöst. Richtig ist:

1. Prüfen, ob die Matrix positiv semidefinit ist (Zeile aus (b)) — beim Einlesen, nicht beim Optimieren.
2. Die Ursache suchen. Korrelationen aus verschiedenen Quellen, Zeiträumen oder Frequenzen sind fast nie widerspruchsfrei. Schätzen Sie die Matrix aus einem konsistenten Datensatz.
3. Ist das nicht möglich, die Matrix reparieren: negative Eigenwerte auf null setzen und rekonstruieren (Eigenwert-Clipping, siehe die Aufgabe Konvexität einer Kovarianzmatrix reparieren in Kapitel 2) oder gleich einen Shrinkage-Schätzer verwenden, der positive Semidefinitheit garantiert (Kapitel 18).

Der Merksatz dazu: Eine Kovarianzmatrix ist kein Behälter für einzeln geschätzte Zahlen, sondern ein geometrisches Objekt. Nicht jede Kombination von Korrelationen existiert.

Micro-Quiz

1 — (b). Der DCPError ist eine inhaltliche Aussage: Für diese Formulierung kann es keine Optimalitätsgarantie geben. Auf scipy auszuweichen (a) beseitigt die Meldung, nicht die Ursache — man bekommt dann ein lokales Ergebnis ohne Garantie und ohne Warnung, wie Abschnitt 11.8 zeigt. Toleranzen (c) haben mit Konvexität nichts zu tun. Richtig ist, zwischen zwei bewussten Wegen zu wählen: konvex umformulieren, oder lokal rechnen und das im Bericht kenntlich machen.

2 — (b) ein lokales Minimum. success: True beschreibt die Konvergenz des Verfahrens, nicht die Qualität des Ergebnisses. Bei Mengenrabatten ist die Zielfunktion nicht konvex, also kann es mehrere lokale Minima geben — im Kapitelbeispiel fünf, mit 8 % Spanne. (a) wäre nur bei einem konvexen Problem richtig. (c) ist zu pessimistisch: Ein lokales Minimum ist es sehr wohl, die Zulässigkeit wird von SLSQP eingehalten.

3 — (c) Schattenpreis. \lambda^* ist die Ableitung des optimalen Zielwerts nach der rechten Seite der Nebenbedingung — dieselbe Bedeutung wie der Dualwert im LP (Kapitel 5), nur für allgemeine, auch krumme Nebenbedingungen. (a) und (b) verwechseln den Multiplikator mit einer Verletzungszahl beziehungsweise mit dem Schlupf; der Schlupf ist bei einer bindenden Bedingung gerade null (komplementärer Schlupf).

Selbsttest

1. Semidefinit → konvex, Optimum global, aber evtl. nicht eindeutig. Definit → streng konvex, Optimum eindeutig.
2. Am Optimum heben sich der „Zug“ der Zielfunktion und der „Druck“ der bindenden Nebenbedingungen exakt auf.
3. Weil eine Ungleichungsschranke nur in eine Richtung wirken kann („drücken“, nicht „ziehen“). Ein negativer Multiplikator hieße, die Bedingung sei gar nicht bindend.
4. \boldsymbol{\Sigma} = \mathbf{D}\mathbf{C}\mathbf{D} mit Volatilitätsdiagonalmatrix \mathbf{D} und gültiger (PSD) Korrelationsmatrix \mathbf{C}.
5. Weil es nur lokale Optima findet; übereinstimmende Ergebnisse aus vielen Startpunkten sind ein Indiz (kein Beweis) für Konvexität.

A.12 Lösungen zu Kapitel „Optimierung unter Unsicherheit — Monte-Carlo, Stochastik, Robustheit“

12.1 — Fluch des Durchschnitts. Weil sich Verzögerungen fortpflanzen und die Verteilung rechtsschief ist: Ein Gewerk, das früher fertig wird, beschleunigt selten den Gesamtablauf (der nächste Schritt ist noch nicht bereit), ein verspätetes verzögert alles. Weitere Beispiele: Wartezeiten in Warteschlangen (nichtlinear in der Auslastung), Projektkosten mit Nachträgen.

12.2 — Ansatz wählen. (a) robust (Ausfall ist existenziell, Wahrscheinlichkeiten unzuverlässig). (b) stochastisch (Verteilung bekannt). (c) robust bzw. Extremwertstatistik (seltene Ereignisse, katastrophale Folgen). (d) stochastisch (Szenarien mit Wahrscheinlichkeiten liegen vor). (e) Chance Constraint — die Zusage ist bereits als Quote formuliert („an 99 % aller Wintertage“). Robust wäre hier zu teuer (es gibt immer einen kälteren Tag), der Erwartungswert zu schwach (er sagt nichts über die Zusage).

12.3 — Zweistufig rechnen. (a) Mit Spot = 60: Ableitung bei x \in (100,250): 40 - 60\cdot0{,}5 + 5\cdot0{,}5 = 40-30+2{,}5 = +12{,}5 > 0 → Kapazität senken. Bei x < 100: 40 - 60 = -20 < 0 → erhöhen. Optimum daher x^* = 100. (b) Billige Nachbesserung macht Vorhalten unattraktiv. (c) Bei x = 225 optimal müsste die Ableitung dort das Vorzeichen wechseln — das ist bei diskreten Szenarien nur zufällig der Fall; der Mittelwert ist nur bei symmetrischen Kosten und stetiger Verteilung optimal.

12.4 — EVPI interpretieren. Selbst eine perfekte Prognose wäre nur 8 400 € pro Jahr wert. Eine Lösung für 15 000 € kann sich also niemals rechnen — unabhängig von ihrer Güte. Argument: „Der theoretische Maximalnutzen liegt unter dem Preis.“

12.5 — Monte-Carlo erweitern. (a) Servicelevel 95 %: Kapazität = 95 %-Quantil des Bedarfs (ca. 485). Die Zusatzkosten gegenüber dem Kostenoptimum (180) betragen ein Vielfaches — Servicelevel ist teuer, und genau diese Zahl braucht die Geschäftsleitung für die Entscheidung. (b) cvar = kosten[kosten >= np.quantile(kosten, 0.95)].mean(). (c) Erwartetes Bild: Bei kleiner Kapazität ist die Kostenverteilung stark rechtsschief (seltene, teure Notzukäufe); bei großer Kapazität schmal und nach rechts verschoben.

12.6 — Den Preis der Zusage selbst bestimmen. (a) Die Kosten je Prozentpunkt steigen weiter steil an; der Mix verschiebt sich dabei fast nur noch zugunsten des Gaskraftwerks, weil Biomasse längst an ihrer Ausbaugrenze liegt. Wind und Sonne bleiben bei einem kleinen Rest — sie senken über ihre Gegenläufigkeit die Norm, tragen zur gesicherten Leistung aber kaum bei. (b) Der Unterschied ist nicht numerisch, sondern inhaltlich. Bei 200 MW Biomasse liefert selbst der Vollausbau in der Kältewelle nur rund 440 MW — 7,5 % der Szenarien sind schlicht nicht bedienbar, egal wie viel Geld man ausgibt. Das Szenariomodell sieht diese Fälle in den Daten und meldet korrekt infeasible, sobald die Zusage über 92 % steigt. Das analytische Modell kennt sie nicht: Für eine Normalverteilung ist jede Zusage unter 100 % erfüllbar, wenn man nur genug Streuung wegkauft. Es meldet optimal — und der Plan hält gemessen 87,4 %. Glauben sollte man dem Szenariomodell: Ein infeasible ist hier die richtige Antwort. Es sagt, dass die Zusage nicht am Budget scheitert, sondern am Kraftwerkspark, und dass nicht mehr Geld hilft, sondern nur eine andere Anlage oder eine kleinere Zusage. (c) Sinngemäß: „99,99 % kosten nicht 5 % mehr als 99 %, sondern ein Vielfaches — der letzte Prozentpunkt ist bereits 4,5-mal so teuer wie der erste. Sagen Sie mir, was ein Ausfalltag das Unternehmen kostet, dann rechne ich aus, welche Quote sich lohnt. Und die Zusage gilt nur für die Wetterlagen, die wir modelliert haben — die Kältewelle gehört hinein.“

12.7 — Budgeted Uncertainty.

abzug = cp.sum_largest(cp.multiply(UNSICHERHEIT, w), Gamma)
ziel = cp.Maximize(MU_SCHAETZUNG @ w - abzug - 0.5*LAMBDA*cp.quad_form(w, SIGMA))

\Gamma = 0 entspricht dem nominalen Fall, \Gamma = n dem vollen Worst Case. Dazwischen steuert \Gamma die Vorsicht stufenlos — der praktisch nützlichste Bereich liegt meist bei \Gamma \approx \sqrt{n}.

Finde den Denkfehler — Warum jedes Projekt zu spät fertig wird

1. Warum 14,38 statt 11,34 Tage. Der Projektleiter hat den Mittelwert der Einzeldauer berechnet und ihn für den Mittelwert der Projektdauer gehalten. Das sind zwei verschiedene Größen:

\mathbb{E}\big[\max(D_1,\dots,D_5)\big] \;\ne\; \max\big(\mathbb{E}[D_1],\dots,\mathbb{E}[D_5]\big)

Anschaulich: Das Projekt ist fertig, wenn das letzte Gewerk fertig ist. Ein Gewerk, das statt 11 nur 7 Tage braucht, bringt niemandem etwas — die anderen sind ja noch dran. Ein Gewerk, das 17 Tage braucht, hält alle auf. Die guten Ausreißer verpuffen, die schlechten schlagen voll durch.

Damit gilt für das Maximum immer \mathbb{E}[\max] \ge \max(\mathbb{E}). Die Differenz ist kein Schätzfehler, sondern eine systematische Verzerrung — sie geht immer in dieselbe Richtung, und sie wächst mit der Streuung der Einzelschätzungen.

2. Warum 95,5 %. Damit das Projekt die geplanten 11,33 Tage hält, müssen alle fünf Gewerke gleichzeitig ihren Mittelwert unterbieten. Für die Dreiecksverteilung (6;\ 10;\ 18) ist die Wahrscheinlichkeit dafür je Gewerk

F(11{,}33) = 1 - \frac{(18-11{,}33)^2}{(18-6)(18-10)} = 1 - \frac{44{,}4}{96} = 0{,}537

— knapp über der Hälfte, weil die Verteilung rechtsschief ist und der Mittelwert deshalb über dem wahrscheinlichsten Wert (10) liegt. Für alle fünf zusammen bleibt davon:

0{,}537^5 = 0{,}045 \quad\Rightarrow\quad \textbf{95,5 \% reißen den Plan.}

Genau der Wert, den die Simulation misst. Sehen Sie sich den Exponenten an: Es ist die Zahl der parallelen Stränge, die die Erfolgswahrscheinlichkeit auffrisst. Bei einem einzigen Gewerk wären es 53,7 %, bei fünf nur noch 4,5 %.

Damit es 50 % wären, müsste man den Median der Projektdauer einplanen, nicht den Mittelwert der Einzeldauern.

Das ist die eigentliche Lehre: Eine Terminzusage ist immer eine Aussage über ein Quantil, nie über einen Mittelwert.

3. Bei zehn Gewerken steigt die erwartete Projektdauer auf 15,35 Tage (90-%-Quantil: 17,00). Der Zuwachs von fünf auf zehn Gewerke ist mit knapp einem Tag deutlich kleiner als der von einem auf fünf — das Maximum wächst logarithmisch, nicht linear. Aber es wächst, und zwar allein durch das Hinzufügen paralleler Arbeit, ohne dass ein einziges Gewerk langsamer geworden wäre.

Praktische Konsequenz: Mehr Parallelität macht Projekte nicht nur nicht schneller, sie macht die Terminprognose schlechter. Wer ein Projekt in mehr parallele Stränge zerlegt, muss den Puffer vergrößern, nicht verkleinern.

4. Die Zahl für den Projektplan. Bei einer geforderten Sicherheit von 90 % gehört das 90-%-Quantil in den Plan: 16,6 Tage, aufgerundet 17. Das sind 47 % mehr als die ursprünglich geplanten 11,3 Tage.

puffer = np.quantile(projekt, 0.90)
print(f"Termin mit 90 % Sicherheit: {np.ceil(puffer):.0f} Tage")

Und die Formulierung gegenüber dem Auftraggeber lautet nicht „der Umbau dauert 17 Tage“, sondern: „In 9 von 10 Fällen sind wir nach 17 Tagen fertig; im Mittel nach 14,4.“ Diese zwei Zahlen sind eine belastbare Zusage — eine einzelne ist es nie.

Micro-Quiz

1 — (b). Das kritische Verhältnis 1400/(1400+120) = 0{,}921 gibt an, wie weit man sich auf die günstigere Fehlerseite stellen soll: Bestellt wird das 92,1-%-Quantil des Bedarfs, hier 38 Stück. (a) ignoriert die Kostenasymmetrie und kostet im Kapitelbeispiel 160 % mehr. (c) verwechselt die Fragestellung: Die Kapitalbindung ist bereits in den 120 € je überzähligem Stück enthalten — sie rechtfertigt keine zusätzliche Kürzung.

2 — (b). Der Unterschied liegt darin, was man wissen muss: Stochastische Optimierung setzt eine Wahrscheinlichkeitsverteilung voraus und minimiert den Erwartungswert; robuste Optimierung kommt mit einer bloßen Bandbreite aus und sichert den ungünstigsten Fall darin ab. Keines ist „genauer“ (a) — sie beantworten verschiedene Fragen. (c) trifft es nicht: Robuste Optimierung betrachtet nicht mehr Szenarien, sondern eine ganze Menge auf einmal, und interessiert sich darin nur für den schlechtesten Punkt.

3 — (c). Bei durchgehender Linearität und ohne nachgelagerte Entscheidung gilt \mathbb{E}[f(X)] = f(\mathbb{E}[X]) — dann ist Rechnen mit Mittelwerten korrekt. Sobald aber ein Maximum, ein Minimum, ein Betrag oder eine Nachbesserungsentscheidung auftaucht, gilt das nicht mehr: Genau das sind die beiden Fälle aus Schnellstart (asymmetrische Kosten über maximum) und Abschnitt 12.9 (Maximum über parallele Vorgänge). (a) ist die Fehlannahme, um die es im ganzen Kapitel geht; (b) ist zu absolut — es gibt den linearen Fall, in dem es tatsächlich zulässig ist.

Selbsttest

1. Wegen der Jensenschen Ungleichung: Bei konvexen Kosten ist \mathbb{E}[f(X)] \ge f(\mathbb{E}[X]) — Planung mit dem Mittelwert unterschätzt die Kosten systematisch.
2. Stufe 1 wird vor Bekanntwerden des Zufalls festgelegt (eine Entscheidung); Stufe 2 danach, je Szenario individuell.
3. Die Differenz zwischen Kosten unter Unsicherheit und Kosten bei perfektem Wissen — eine Obergrenze für den Wert jeder Prognoseverbesserung.
4. Weil sie nur eine Menge möglicher Werte braucht, nicht deren Verteilung — sie optimiert gegen das schlechteste Element dieser Menge.
5. Für einfache Mengen (Box, Ellipsoid) lässt sich das innere Maximum geschlossen ausrechnen und wird zu einem Abzugsterm; das Gesamtproblem bleibt konvex.
6. Weil die Streuung der Summe \mathbf{a}^\top\mathbf{x} nicht die Summe der Streuungen ist: \sqrt{\mathbf{x}^\top\boldsymbol{\Sigma}\mathbf{x}} enthält die Kovarianzen. Ein fester Zuschlag je Variable wäre linear und würde deshalb übersehen, dass sich gegenläufige Größen teilweise aufheben — die Norm belohnt Mischung, ein linearer Aufschlag nicht.
7. Weil die Zusage nur so gut ist wie die unterstellte Verteilung. Die Normalverteilung kennt keine Ereignisse, in denen alle Quellen gleichzeitig ausfallen; ihre schwachen Korrelationen unterschätzen genau den Fall, der die Zusage bricht. Die szenariobasierte Formulierung hat diese Fälle in den Daten und trifft die Quote — erkauft mit Mehrkosten und mit dem Risiko, sich an die verwendete Stichprobe anzupassen.

A.13 Lösungen zu Kapitel „Dynamische Programmierung — Die Bellman-Gleichung und Order-Execution“

13.1 — Bausteine. Stufe = Tag 1–5; Zustand = verbleibende Distanz (ggf. plus Erschöpfungsgrad); Aktion = heutige Tagesetappe; Wertfunktion = minimale Restanstrengung. Nicht in den Zustand gehören: bereits gelaufene Kilometer (redundant, wenn die Restdistanz bekannt ist) und das Wetter von gestern (ohne Einfluss auf die Zukunft).

13.2 — Optimalitätsprinzip. Weil der Wert eines Zustands nur von den künftigen Entscheidungen abhängt, kann man ihn ab dem Ende rekursiv berechnen. Hängen die Kosten zusätzlich von früheren Aktionen ab, ist die Markov-Eigenschaft verletzt — die Lösung: die relevante Vergangenheit in den Zustand aufnehmen (dann wächst allerdings der Zustandsraum).

13.3 — Rückwärtsinduktion. Mit C(n) = n^2 + 2n und 5 Einheiten in 3 Perioden ergibt sich als optimaler Pfad 2 \to 2 \to 1 (oder eine Permutation davon) mit Gesamtkosten 8 + 8 + 3 = 19. Alles auf einmal kostet 25 + 10 = 35.

13.4 — Rucksack als DP.

V = np.zeros((n + 1, kapazitaet + 1))
for i in range(1, n + 1):
    for c in range(kapazitaet + 1):
        V[i][c] = V[i-1][c]
        if gewicht[i-1] <= c:
            V[i][c] = max(V[i][c], V[i-1][c - gewicht[i-1]] + nutzen[i-1])

Ergebnis identisch zum MILP (110). Laufzeit O(n \cdot C) — bei kleinen ganzzahligen Kapazitäten schneller als Branch-and-Bound, bei großen oder nicht-ganzzahligen Kapazitäten schlechter (dann ist das MILP überlegen). Man nennt das pseudopolynomiell.

13.5 — Risikoaversion kalibrieren. (a) Zwischen \lambda = 10^{-5} (41 %) und 10^{-4} (78 %); genauer etwa bei \lambda \approx 3\cdot10^{-5}. (b) Höheres \lambda → höhere Gesamtkosten (man kauft Sicherheit mit Slippage). (c) Iterativ: \lambda so wählen, dass der Anteil der Marktauswirkungskosten an den Gesamtkosten bei 20 % liegt — im Programm ausrechnen und per Bisektion einstellen.

13.6 — Zustandsraum erweitern. Der Zustand wird zu (Restbestand, Orderbuchtiefe); der Zustandsraum verdreifacht sich, die Rechenzeit ebenfalls. Die Strategie wird zustandsabhängig: Bei tiefem Buch wird mehr verkauft, bei dünnem gewartet. Genau diese Adaptivität ist der Mehrwert von DP gegenüber einem festen Pfad.

Finde den Denkfehler — Der Zustand, der zu wenig weiß

1. Die fehlende Information. Die Zeile

kosten = (RUESTKOSTEN if p > 0 else 0) + ...

berechnet die Rüstkosten allein daraus, ob in dieser Periode produziert wird. Die tatsächliche Regel lautet aber: Rüstkosten fallen an, wenn produziert wird und in der Vorperiode nicht. Ob in der Vorperiode produziert wurde, steht nirgends im Zustand (t, lager) — die Funktion kann es gar nicht wissen.

Das Modell nimmt deshalb an, dass jede Produktionsperiode eine Rüstung kostet. Es bestraft laufende Produktion, obwohl sie in Wirklichkeit gratis weiterläuft.

2. Der unsichtbare Vorteil. Der Plan (3, 1, 4, 2) produziert in allen vier Perioden. Real fällt dafür genau eine Rüstung an (in Periode 0), zusammen 30 €. Das falsche Modell rechnet mit vier Rüstungen, also 120 € — und verwirft den Plan als viel zu teuer. Genau der Vorteil, den dieser Plan hat, ist im Modell nicht darstellbar.

Stattdessen wählt es (5, 0, 5, 0): wenige Produktionsperioden, dafür große Lose. Aus Sicht seiner eigenen Kostenannahme ist das folgerichtig.

57 % Mehrkosten — nicht durch einen Rechenfehler, sondern durch einen zu kleinen Zustand.

3. Der korrigierte Zustand lautet (t, lager, lief_vorher) mit einem zusätzlichen Wahrheitswert:

@functools.lru_cache(None)
def V(t, lager, lief_vorher):
    ...
    kosten = (RUESTKOSTEN if (p > 0 and not lief_vorher) else 0) + ...
    rest, plan = V(t + 1, neu, p > 0)

Damit findet die Rückwärtsinduktion (3, 1, 4, 2) für 70 € — das nachgerechnete Optimum. Der Zustandsraum verdoppelt sich (je Lagerstand zwei Varianten, „lief“ und „lief nicht“). Das ist der übliche Preis: Vollständigkeit des Zustands kostet Größe, und genau hier beginnt der Fluch der Dimensionalität.

4. Warum der richtige Betrag das Tückische ist. Man würde erwarten, dass ein falsches Modell auch einen falschen Kostenbetrag ausgibt — dann fiele es beim Nachrechnen auf. Hier nicht: Für den von ihm gewählten Plan (5,0,5,0) stimmt die Rechnung zufällig, weil in diesem Plan tatsächlich jede Produktionsperiode auf eine Pause folgt. Modellannahme und Wirklichkeit fallen für genau diese eine Lösung zusammen.

Eine Prüfung, die nur den ausgegebenen Plan nachrechnet, bestätigt also alles. Der Fehler liegt nicht in der Bewertung der gefundenen Lösung, sondern darin, dass die bessere Lösung nie in Betracht gezogen wurde. Solche Fehler findet man nur auf zwei Wegen:

1. Die Zustandsprobe: „Wenn ich nur den Zustand kenne und nicht den Weg dorthin — kann ich dann noch richtig weiterentscheiden?“ Hier lautet die Antwort nein, denn ohne zu wissen, ob gerade produziert wird, sind die Kosten der nächsten Aktion nicht bestimmbar.
2. Ein zweites, unabhängiges Verfahren. Bei kleinen Instanzen genügt vollständige Enumeration: 6^4 = 1296 Pläne sind in Millisekunden durchgerechnet — und hätten die 70 €-Lösung sofort gezeigt.

Micro-Quiz

1 — (b). V_t setzt V_{t+1} voraus: Eine Entscheidung lässt sich erst bewerten, wenn feststeht, was sie für die Zukunft bedeutet. Am Ende ist dieser Wert bekannt (V_T = g), deshalb beginnt die Rechnung dort. (a) verwechselt ein mathematisches Erfordernis mit einer Implementierungsfrage; (c) ist frei erfunden und hätte mit der Rechenrichtung ohnehin nichts zu tun.

2 — (b). Das Optimalitätsprinzip sagt, dass jedes Reststück einer optimalen Lösung selbst optimal ist. Deshalb genügt es, je Zustand einen einzigen Wert zu speichern, statt alle Wege dorthin zu unterscheiden. (a) ist die verbreitetste Fehldeutung — sie beschriebe gieriges Vorgehen, und genau das scheitert im Schnellstart dieses Kapitels (21 statt 14 Minuten). (c) ist eine Allgemeinplatz-Aussage ohne Bezug zum Prinzip.

3 — (b). Der Rabatt hängt von der bisher kumulierten Menge ab; ohne diese Größe im Zustand kann das Modell die Kosten der nächsten Bestellung nicht bestimmen — dasselbe Muster wie in Abschnitt 13.7. (a) übersieht genau das: Kosten, die von der Vorgeschichte abhängen, sind Zustandsinformation. (c) ist zu absolut — DP bleibt anwendbar, der Zustandsraum wird nur größer; ob sich stattdessen ein MILP lohnt, ist eine Frage der Größe, nicht der Eignung.

Selbsttest

1. Jeder Teilabschnitt einer optimalen Strategie ist selbst optimal für den Zustand, in dem er beginnt.
2. Weil V_{t+1} bekannt sein muss, um V_t zu berechnen — und am Ende ist der Wert bekannt.
3. Alles, was die Zukunft beeinflusst, und nichts weiter. Unvollständig ist er, wenn die Kosten oder Übergänge zusätzlich von der Vorgeschichte abhängen.
4. Der Aufwand wächst multiplikativ mit jeder Zustandsdimension. Gegenmittel: gröbere Diskretisierung/Zustandsreduktion, Funktionsapproximation (ADP), Reinforcement Learning.
5. Weil sie eine unabhängige Prüfung ermöglicht — Größenordnungsfehler und Vorzeichenfehler fallen sofort auf.

A.14 Lösungen zu Kapitel „Mehrere Ziele — Pareto-Fronten statt Gewichte“

14.1 — Dominanz prüfen. P (14 000 €, 6 000 kg) und Q (13 800 €, 6 100 kg): keiner dominiert den anderen. Q ist billiger, P ist sauberer — beide sind pareto-optimal, die Wahl ist eine Präferenzfrage.

R (14 000 €, 6 100 kg) dagegen wird von beiden dominiert: gleich teuer wie P, aber schmutziger; schmutziger als Q und teurer. R kann man wegwerfen, ohne jemanden zu fragen — und genau das ist der Zweck des Dominanzbegriffs: Er trennt die Fälle, in denen der Modellierer entscheiden darf, von denen, in denen er es nicht darf.

14.2 — Der Schattenpreis in der Praxis. Man geht die Front von unten durch, solange der Schattenpreis unter 0,90 €/kg liegt. Aus der Ausgabe: 0,58 — 0,93 — 0,40 — 0,59 — 0,77 — 0,65 — 0,77 — 1,09 — 1,32. Die Werte steigen nicht monoton, weil die Front bei ganzzahligen Modellen keine glatte Kurve ist; maßgeblich ist deshalb nicht der einzelne Schritt, sondern der Gesamtschattenpreis gegenüber dem Kostenminimum.

Der letzte Punkt, dessen Gesamtschattenpreis unter 0,90 € liegt, ist 14 189 € / 5 632 kg: 646 € Aufpreis für 843 kg Ersparnis, also 0,77 €/kg. Der nächste Punkt kostet 1,09 €/kg und liegt damit über dem internen Preis.

Begründung in einem Satz: „Für 646 Euro sparen wir 843 Kilogramm CO₂ — zu 77 Cent je Kilogramm, während wir intern mit 90 Cent rechnen.“

14.3 — Mehr Trassen. Mit 8 statt 5 Trassen wird der Engpass schwächer. Zu erwarten ist eine kürzere Front: Der Zielkonflikt entsteht ja allein aus der Knappheit; je mehr Trassen, desto näher rücken Kostenminimum und CO₂-Minimum zusammen. Im Grenzfall genügend vieler Trassen fallen beide zusammen — die Bahn ist billiger und sauberer, also gibt es gar keinen Konflikt mehr und die Front schrumpft auf einen Punkt.

Der Lehrpunkt: Ein Zielkonflikt ist keine Eigenschaft der Ziele, sondern der Knappheit. Wer ihn auflösen will, sollte zuerst prüfen, ob sich die Ressource vermehren lässt, statt über Gewichte zu verhandeln.

14.4 — Die Front der Relaxation. Ohne integrality ist der zulässige Bereich konvex, und die Pareto-Front liegt vollständig auf ihrer eigenen unteren konvexen Hülle. Es gibt also keinen Punkt oberhalb — jeder Punkt der Front ist durch ein passendes Gewicht erreichbar.

Genau das ist der Grund, warum das Problem in Lehrbüchern zur linearen Programmierung nicht vorkommt und in der betrieblichen Praxis ständig: Sobald „welcher Träger“, „welches Lager“ oder „welche Schicht“ entschieden wird, zerfällt der Bereich in einzelne Punkte, und zwischen ihnen entstehen die Einbuchtungen, in denen die nicht gestützten Lösungen liegen.

14.5 — Drei Ziele. Die Front wird zu einer Fläche im dreidimensionalen Zielraum. Das ε-Verfahren braucht dann ein Gitter über zwei Schranken statt einer Folge über eine — der Aufwand wächst von O(k) auf O(k^2), bei m Zielen auf O(k^{m-1}).

Zwei praktische Folgerungen: Erstens ist bei drei und mehr Zielen die vollständige Front meist nicht mehr bezahlbar; man arbeitet dann mit einer Stichprobe oder mit Metaheuristiken, die eine Front approximieren (NSGA-II, in pymoo enthalten). Zweitens ist eine Front mit hunderten Punkten für die Entscheidung ohnehin unbrauchbar — ab drei Zielen ist die bessere Frage meist, ob sich zwei davon zusammenfassen lassen.

Finde den Denkfehler — „Wir haben die Gewichte sauber kalibriert“

Der Lösungsraum wurde nicht vollständig abgetastet — und zwar aus prinzipiellen Gründen.

500 Gewichte sind nicht zu wenige. Auch 500 000 wären zu wenige. Die gewichtete Summe kann ausschließlich Punkte auf der unteren konvexen Hülle erreichen; alles, was darüber liegt, ist für jedes w unerreichbar. Im Kapitelbeispiel sind das 4 von 10 Punkten — 40 % der Alternativen, die die Geschäftsführung nie zu sehen bekam.

Die Behauptung „die Entscheidung hat der Fachbereich getroffen“ ist damit nur halb wahr. Der Fachbereich hat aus einer vorgefilterten Auswahl gewählt, und die Vorfilterung stammt vom Team — unbeabsichtigt und unbemerkt, aber sie stammt von dort.

Zum zweiten Teil: Nein, niemand hätte es bemerkt.

Das ist der eigentlich beunruhigende Punkt. Alle vorgelegten Pläne waren pareto-optimal, also einwandfrei. Es fehlte kein schlechter Plan, sondern es fehlten gute. Ein fehlender Kompromiss hinterlässt keine Spur: Es gibt keine Fehlermeldung, keinen auffälligen Wert, keinen Test, der anschlägt. Die Auswahl sah vollständig aus, weil Vollständigkeit von innen nicht überprüfbar ist.

Deshalb genügt es nicht, sorgfältig zu sein — man braucht ein Verfahren mit einer Vollständigkeitsgarantie. Das ε-Constraint-Verfahren hat sie: Wenn kein zulässiger Plan mehr existiert, ist die Front nachweislich vollständig.

Was das Team hätte tun sollen: ε-Constraint statt Gewichtsraster. Es hätte die vollständige Front geliefert — mit zehn statt 500 Solverläufen.

Micro-Quiz

1. b) Geometrisch heißt „gewichtete Summe minimieren“: eine Gerade von links unten an die Punktwolke schieben. Sie berührt immer einen Eckpunkt der unteren konvexen Hülle; Punkte darüber werden nie zuerst getroffen. (a) klingt plausibel und ist falsch — ein feineres Raster ändert nichts, wie die Gegenprobe über die Hülle im Programm zeigt.

2. b) Ein Lauf für das Kostenminimum, danach ein Lauf je Frontpunkt, und ein letzter, der unzulässig ist und die Schleife beendet. Der Aufwand hängt also an der Länge der Front, nicht an der Feinheit eines Rasters — das ist der praktische Vorteil des Verfahrens.

3. b) Es gibt mehrere kostenminimale Pläne, und der Solver gibt normalerweise einen beliebigen davon zurück. Die lexikografische Formulierung sucht unter allen den saubersten — die CO₂-Ersparnis kostet dann tatsächlich nichts. (c) ist ein guter Verdacht, trifft hier aber nicht zu: Auch bei exakt gleichem Budget bliebe der Effekt.

Selbsttest

1. Freie Antwort. Ein tragfähiges Beispiel enthält zwei Größen, die man nicht in dieselbe Einheit bringen kann, ohne eine Wertung vorzunehmen — etwa Personalkosten gegen Reaktionszeit oder Lagerbestand gegen Lieferfähigkeit.
2. Bei einem LP ist der zulässige Bereich konvex; die Pareto-Front liegt vollständig auf ihrer eigenen konvexen Hülle, und die gewichtete Summe erreicht jeden Punkt. Bei einem MILP zerfällt der Bereich in einzelne Punkte, zwischen denen Einbuchtungen entstehen — und die dort liegenden Lösungen sind unerreichbar.
3. Erstens ist w kein Regler zwischen 0 und 1, sondern ein Wechselkurs mit einer Einheit: Euro je Kilogramm. „0,5“ heißt also „ein Kilogramm CO₂ ist mir 50 Cent wert“ — eine sehr konkrete und keineswegs neutrale Aussage. Zweitens gibt es keinen neutralen Wert, weil weite Gewichtsbereiche dieselbe Lösung liefern und es dazwischen springt.
4. Man optimiert nur das erste Ziel und schreibt dem zweiten eine Obergrenze vor. Diese Grenze setzt man zunächst auf den Wert, der beim reinen Kostenoptimum ohnehin anfällt, und drückt sie dann Schritt für Schritt weiter herunter. Sobald kein zulässiger Plan mehr existiert, hat man alle Kompromisse.
5. Den Schattenpreis — Aufpreis geteilt durch Ersparnis, hier in Euro je Kilogramm. Ohne ihn ist die Front eine Liste von Zahlenpaaren; mit ihm ist sie mit dem internen CO₂-Preis vergleichbar und damit entscheidbar.

A.15 Lösungen zu Kapitel „Predict-then-Optimize“

15.1 — Andere Preise. Der Überhang kostet nur noch 1,50 €, die Fehlmenge weiterhin 6 €. Das kritische Verhältnis steigt von 6/9 = 0{,}667 auf 6/7{,}5 = 0{,}80. Die Bestellmenge verschiebt sich also nach oben — man bestellt jetzt das 80-%-Quantil statt des 66,7-%-Quantils.

Das ist die richtige Richtung und leicht zu merken: Je billiger der Überhang, desto großzügiger darf man ansetzen. Im Grenzfall kostenloser Entsorgung (c_+ \to 0) geht das kritische Verhältnis gegen 1 — man bestellt so viel, dass praktisch nie etwas fehlt.

15.2 — Wann ist der Mittelwert richtig? Nur wenn c_- = c_+ und die Nachfrageverteilung symmetrisch ist. Dann liegt das kritische Verhältnis bei 0,5, das 50-%-Quantil ist der Median, und bei Symmetrie fällt der Median mit dem Mittelwert zusammen.

Beide Bedingungen sind unrealistisch. Fehlmenge und Überhang kosten fast nie dasselbe — bei Frischware ist der Überhang teurer, bei Ersatzteilen die Fehlmenge um Größenordnungen. Und Nachfrageverteilungen sind meist rechtsschief. Der Mittelwert ist damit die Ausnahme, nicht die Regel — er wird nur benutzt, weil Regressionsmodelle ihn standardmäßig liefern.

15.3 — Die Kennzahl der Prognoseabteilung. Die Rangfolge bleibt: Die Punktprognose gewinnt auch beim MAPE, weil beide Maße den Erwartungswert belohnen — der MAPE etwas anders gewichtet, aber ebenfalls symmetrisch in dem Sinne, dass er nicht weiß, dass Unterschätzung teurer ist als Überschätzung.

Das ist kein Zufall, sondern der Kern des Kapitels: Jedes rein statistische Fehlermaß ignoriert die Kostenasymmetrie. Man kann das Problem nicht lösen, indem man das Fehlermaß wechselt; man muss die Kosten selbst messen. (Die einzige Ausnahme ist der Pinball Loss — genau das Maß, das die Quantilregression minimiert, und das ist eben kein allgemeines Prognosemaß, sondern eines für ein bestimmtes Quantil.)

15.4 — Zwei Quantile. Das Band ist an Aktionstagen deutlich breiter — dort ist die Streuung im Modell fast viermal so groß. Genau das ist die Information, die eine Punktprognose plus fester Zuschlag wegwirft.

Ein praktischer Nebeneffekt: Ein solches Band ist die verständlichste Form, Unsicherheit an die Disposition zu berichten. „Zwischen 130 und 210” sagt einem Menschen mehr als „170 ± Sicherheitszuschlag”.

15.5 — Der Wert der Merkmale. Zu erwarten ist, dass die Kosten stärker steigen als der MSE. Der Grund: Das Merkmal „Aktion” trägt zwei verschiedene Informationen — es verschiebt den Erwartungswert (um 45 Stück) und die Streuung (von 8 auf 30). Der MSE bemerkt nur den ersten Teil; die Entscheidungskosten spüren beide.

Der Lehrsatz dahinter: Der Wert eines Merkmals hängt davon ab, wofür man es benutzt. Eine Merkmalsauswahl, die nach MSE-Beitrag sortiert, wirft möglicherweise genau die Merkmale weg, die für die Entscheidung am wichtigsten sind — nämlich die, die etwas über die Unsicherheit sagen.

Finde den Denkfehler — „Wir haben die Prognose um 18 % verbessert“

Der Sicherheitszuschlag stammt aus den Residuen des alten Modells.

Das ist die vollständige Antwort auf den zweiten Teil, und sie ist präziser als „bessere Prognose kann schlechter sein”. Der Ablauf im Einzelnen:

1. Das alte Modell hatte größere Residuen, also einen größeren Sicherheitszuschlag.
2. Der Zuschlag wurde nie neu berechnet — er ist „seit Jahren unverändert”.
3. Das neue Modell prognostiziert besser, also näher am Erwartungswert. Auf denselben Zuschlag addiert ergibt das eine niedrigere Bestellmenge als vorher.
4. Aber der richtige Zuschlag hängt an der Reststreuung des aktuellen Modells und am kritischen Verhältnis, nicht an der Gewohnheit.

Es ist also nicht die bessere Prognose, die schadet, sondern die nicht mitgezogene zweite Stufe. Die beiden Stufen wurden unabhängig gepflegt, obwohl sie voneinander abhängen.

Was das Team hätte messen müssen: die Entscheidungskosten. Sie hätten auf denselben Testdaten die Bestellmengen beider Modelle durchgerechnet und die Newsvendor-Kosten verglichen — eine Zahl in Euro, die die Disposition sofort verstanden hätte. Der Fehler wäre vor dem Produktivgang aufgefallen statt sechs Wochen danach.

Und die eigentliche Konsequenz: Der Zuschlag gehört gar nicht in die Disposition, sondern ins Modell. Wer das kritische Quantil direkt schätzt, kann diesen Fehler nicht machen — es gibt keinen zweiten, separat gepflegten Parameter mehr.

Micro-Quiz

1. b) Die Kostenasymmetrie verschiebt das Optimum vom Erwartungswert zum kritischen Quantil. (a) und (c) sind reale Probleme, aber nicht dieses: Selbst bei perfekt bekannter, normalverteilter Nachfrage wäre der Erwartungswert die falsche Bestellmenge.

2. b) Ein jährlich neu berechneter Zuschlag ist besser als ein veralteter, bleibt aber für alle Tage gleich. Die Unsicherheit hängt hier von den Merkmalen ab (Aktionstage), und das kann ein einzelner Wert nicht abbilden — im Kapitel gemessen: 3,5 gegen 12,3 Stück. (c) ist zu pauschal; Residuen sind ein brauchbarer Schätzer, nur eben ein globaler.

3. b) Ein einzelner Vergleich ohne Streuungsangabe ist keine belastbare Aussage. (a) verwechselt die Diagnose mit einem Rezept — 730 Testtage hat in der Praxis kaum jemand, und die Antwort ist Kreuzvalidierung statt einer Mindestzahl. (c) ist übertrieben: Der MSE ist ein brauchbares Maß für Prognosegüte, nur eben nicht für Entscheidungsgüte.

Selbsttest

1. Die erste Stufe wird auf ein statistisches Maß trainiert (MSE), die zweite erzeugt ökonomische Kosten mit asymmetrischer Struktur. An der Naht geht die Information über die Unsicherheit verloren: Weitergereicht wird eine einzelne Zahl, obwohl die Entscheidung die ganze Verteilung bräuchte.
2. Das kritische Quantil c_-/(c_- + c_+) der Nachfrageverteilung. Der Wert kommt aus den Kosten der Entscheidung, nicht aus den Daten — er ist bekannt, bevor man die erste Zeile Code schreibt.
3. Weil die Unsicherheit heteroskedastisch ist: Sie hängt selbst von den Merkmalen ab. Ein einziger Zuschlag ist an ruhigen Tagen zu groß und an unruhigen zu klein.
4. „Wie ändern sich die Entscheidungskosten?” — und, als Zusatz, „ist der Sicherheitszuschlag mitgezogen worden?”
5. So viele, dass der Unterschied zwischen den Modellen größer ist als die Schwankung des Maßes zwischen verschiedenen Zeitfenstern. Wie viele das sind, kann man nur messen — durch Kreuzvalidierung oder rollierende Auswertung.

A.16 Lösungen zu Kapitel „Die Strukturbrücke — dieselbe Mathematik, zwei Welten“

16.1 — Die dritte Ressource. „Liquidität” — wie schnell sich eine Position ohne Kursabschlag verkaufen lässt — entspricht in der Werkstatt der Umrüstbarkeit oder der Vorlaufzeit: Wie schnell lässt sich die Fertigung von diesem Produkt wieder wegdrehen, wenn der Auftrag storniert wird? In beiden Fällen ist es eine knappe Größe, die nichts mit dem Ertrag zu tun hat und trotzdem die Auswahl einschränkt.

Im Modell ist es schlicht eine weitere Zeile in kapazitaeten und ein weiterer Eintrag in jedem verbrauch. Genau das ist der Punkt des Kapitels: Eine neue Ressource kostet keinen Modellcode.

16.2 — Den Schattenpreis lesen. Bis zu 602,60 € für 10 Einheiten (10 × 60,26 €) lohnt sich der Kauf — darüber nicht.

Die Einschränkung aus Abschnitt 5.9: Der Schattenpreis gilt nur lokal, solange sich die optimale Basis nicht ändert. Nach einer gewissen Erhöhung wird eine andere Nebenbedingung bindend (hier voraussichtlich das Kapital), und ab dort ist die zusätzliche Einheit weniger wert. Bei 10 Einheiten auf 90 ist das eine Erhöhung um 11 % — schon groß genug, dass man es nachrechnen sollte, statt zu extrapolieren.

Zweite Einschränkung: Bei Entartung ist der Schattenpreis nicht eindeutig. Verschiedene Solver können dann verschiedene, gleichermaßen gültige Werte liefern — auch das steht in Abschnitt 5.9.

16.3 — Die Brücke rückwärts. Shrinkage hilft, wenn man eine Kovarianzmatrix aus wenigen Beobachtungen schätzt. Bei Lieferzeiten tritt genau dasselbe Problem auf, sobald man die Korrelationen zwischen Lieferanten braucht — und die braucht man, sobald Lieferanten gemeinsame Ursachen haben: derselbe Hafen, dasselbe Vorprodukt, dieselbe Region.

Bei 40 Lieferanten hat die Kovarianzmatrix 820 zu schätzende Einträge. Wer dafür 36 Monatswerte hat, schätzt 820 Zahlen aus 36 Beobachtungen — dasselbe Missverhältnis wie bei Aktienrenditen, mit denselben Folgen (Kovarianz_Falle.py).

Benötigt würden: Lieferzeit-Zeitreihen je Lieferant über denselben Zeitraum, gleich getaktet. Genau daran scheitert es in der Praxis meist — die Daten liegen in Bestellvorgängen, nicht in einer Matrix.

16.4 — CVaR mit Ganzzahligkeit. Man ergänzt Binärvariablen y_j je Lieferant und die Kopplung w_j \le y_j sowie \sum_j y_j \le 3. Da CVXPY gemischt-ganzzahlige Probleme unterstützt, genügt cp.Variable(n, boolean=True).

Zu erwarten ist ein höherer CVaR: Der zulässige Bereich wird kleiner, und die Feinabstimmung über sechs Lieferanten fällt weg. Der Aufschlag ist der Preis der Vertragswirklichkeit — und genau die Zahl, die man dem Einkauf vorlegt, wenn dort jemand sagt, drei Lieferanten seien genug.

16.5 — Die eigene Brücke. Freie Antwort. Eine gute Bearbeitung nennt das Modell, die Entsprechung und die Zeile der Grenztabelle, die im Weg steht — meist ist es die dritte (Teilbarkeit) oder die erste (gemessen gegen geschätzt). Wenn keine im Weg steht, ist die Übertragung wahrscheinlich zu oberflächlich geprüft.

Finde den Denkfehler — „Das ist doch dasselbe Problem“

Fehler 1: Varianz ist hier das falsche Risikomaß — genau der Fall, für den es CVaR gibt.

Markowitz minimiert die Varianz, und die bestraft Abweichungen nach beiden Seiten gleich. Ein Lieferant, der manchmal zwei Tage zu früh liefert, erhöht die Varianz genauso wie einer, der zwei Tage zu spät liefert — obwohl das eine harmlos und das andere teuer ist.

Schwerer wiegt die Verteilungsform: Lieferzeiten haben einen einseitig fetten Rand. Im Normalfall schwankt es um wenige Tage, im seltenen Ausfall sind es zwei Wochen. Die Varianz mittelt diesen Rand weg; sie ist bei genau diesen Verteilungen am unzuverlässigsten. Das Kapitel führt die CVaR-Funktion nicht ohne Grund über beide Welten — die Übertragung wäre richtig gewesen, nur eben mit dem richtigen Risikomaß.

Fehler 2: Die Teilbarkeit — die dritte Zeile der Grenztabelle.

Markowitz liefert stetige Anteile: 7,3 % bei Lieferant A, 4,1 % bei B. Ein Lieferantenportfolio funktioniert so nicht. Es gibt Mindestabnahmemengen, Rahmenverträge, Qualifizierungskosten je Lieferant und eine praktische Obergrenze, wie viele Lieferanten der Einkauf betreuen kann. Aus dem QP wird ein MIQP mit Kardinalitätsbedingung und Mindestmengen (Kapitel 6, Muster 5) — und dessen Lösung sieht anders aus als die gerundete stetige.

Was das Kapitel dazu sagt, und was nicht. Fehler 2 steht ausdrücklich in der Grenztabelle. Fehler 1 nicht — er ist ein Fehler innerhalb der Finanzwelt, den die Kollegin mit übernommen hat: Auch dort ist die Varianz für Verteilungen mit fetten Rändern das falsche Maß (Kapitel 20). Wer eine Methode überträgt, überträgt eben auch ihre Schwächen mit.

Micro-Quiz

1. b) Beide Probleme haben dieselbe Struktur: knappe Größen auf konkurrierende Verwendungen verteilen. (a) ist falsch — Produktionsproblem ist streng typisiert und validiert beim Einlesen; genau deshalb ist es aussagekräftig, dass die Depotdaten durchkommen. (c) ist frei erfunden.

2. b) Der Schattenpreis ist der Dualwert der Nebenbedingung: der zusätzliche Zielwert je zusätzlicher Einheit — lokal gültig. (a) verwechselt ihn mit der Auslastung, (c) mit den Kosten.

3. c) Die Teilbarkeit. In der Produktion sind Entscheidungen ganzzahlig (halbe Maschinen, halbe Schichten, halbe Lieferanten gibt es nicht), an den Finanzmärkten sind Anteile normal. Deshalb ist Teil II voller MILP und Teil IV fast frei davon — es liegt an der Welt, nicht an der Methode.

Selbsttest

1. Montagestunden ↔︎ Kapital; Plattenmaterial ↔︎ Risikobudget; Deckungsbeitrag je Stück ↔︎ erwarteter Ertrag je 1 000 €. (Weitere: Mindestlosgröße ↔︎ Mindestordergröße, Rüstkosten ↔︎ Ordergebühr, Sortimentsbreite ↔︎ Kardinalitätsgrenze.)
2. Ein LP sieht eine Matrix, einen Kapazitätsvektor und einen Zielvektor — Bedeutung kommt darin nicht vor. Das ist hier ein Vorteil, weil derselbe geprüfte, getestete Code beide Domänen bedient; man erbt die Verlässlichkeit mit.
3. „Stellen Sie sich vor, Ihre Engpassmaschine wäre nicht die Fräse, sondern eine Vorschrift: Sie dürfen nur eine bestimmte Menge Risiko in den Büchern haben. Der Schattenpreis sagt dann, was eine Lockerung dieser Vorschrift wert wäre — genau wie bei einer zusätzlichen Maschinenstunde.”
4. Fette Ränder (seltene, aber sehr große Abweichungen). Die Standardabweichung mittelt sie weg und bestraft außerdem Abweichungen nach oben genauso wie nach unten; CVaR sieht ausschließlich auf den schlechten Rand.
5. 1. Sind die Zahlen gemessen oder geschätzt — und wie groß ist der Schätzfehler im Verhältnis zu den Unterschieden? (b) Ist der datengenerierende Prozess stabil, oder reagiert er auf das Modell? (c) Sind die Entscheidungen teilbar oder ganzzahlig?

A.17 Lösungen zu Kapitel „Supply-Chain und Energieeinsatz unter Unsicherheit“

17.1 — Der Umschlagpunkt. Bei 60 MW statt 120 MW halbiert sich die Grenzkostendifferenz je Stunde (83 €/MWh × 60 MW = 4 980 €/h). Der Umschlagpunkt verdoppelt sich auf 7,7 Stunden.

Das ist plausibel: Je kleiner die abzudeckende Leistung, desto länger dauert es, bis der Grenzkostenvorteil des großen Blocks seine Anfahrkosten einspielt. Ein Kernblock lohnt sich für eine kleine Restlast noch weniger als für eine große — was erklärt, warum Grundlastblöcke gerade dann unwirtschaftlich werden, wenn viel Wind einspeist und nur eine kleine Restlast bleibt.

17.2 — Die fehlende Nebenbedingung. Analog zum Anfahren braucht man eine Abfahr-Indikatorvariable b_{k,t} \ge u_{k,t-1} - u_{k,t} und dann:

u_{k,\tau} \le 1 - b_{k,t} \qquad \text{für } \tau = t, \dots, t + M_k - 1

In Worten: Wer abfährt, bleibt M_k Stunden aus.

Der reale Sachverhalt: Ein abgeschalteter Dampfblock kühlt aus und darf aus werkstofftechnischen Gründen nicht sofort wieder hochgefahren werden — die Temperaturwechsel würden das Material schädigen. Bei Gasturbinen ist die Mindeststillstandszeit kurz oder null, bei Kernblöcken beträgt sie viele Stunden.

17.3 — Wie viele Szenarien? Zu erwarten ist, dass der Commitment-Plan ab einer gewissen Szenarienzahl stabil bleibt — oft schon bei 20 bis 40. Der Grund: Die erste Stufe ist binär und grob; sie kann nur ganze Blockstunden verschieben. Feine Unterschiede in der Szenarienmenge ändern daran nichts mehr.

Der Zusammenhang mit Abschnitt 15.6 ist der interessante Teil: Dort ging es um die Zahl der Beobachtungen bei einer Bewertung, hier um die Zahl der Szenarien in einem Modell. Beide Male lautet die Frage nicht „wie viele sind genug?“, sondern „ab wann ändert sich die Antwort nicht mehr?” — und beide Male beantwortet man sie, indem man es ausprobiert, statt eine Faustregel zu übernehmen.

17.4 — Der Wert eines Speichers. Der Speicher braucht Variablen für Ladung, Entladung und Füllstand je Szenario und Stunde, mit der Bilanz F_{t} = F_{t-1} + \eta\, L_t - E_t/\eta und Grenzen für Leistung und Kapazität. Er gehört in die zweite Stufe: Wann geladen wird, darf sich am Tag selbst entscheiden.

Zu erwarten ist ein deutlicher Rückgang der erwarteten Kosten, und zwar aus zwei Quellen: Er verschiebt Energie aus billigen in teure Stunden und er ersetzt Vorhaltung — ein Speicher ist in Sekunden verfügbar, ein Kernblock in acht Stunden. Der zweite Effekt ist der größere und wird bei einer Betrachtung ohne Szenarien komplett übersehen.

Der Wert je MWh Kapazität ergibt sich als Kostenersparnis geteilt durch 400 MWh. Er ist mit den Investitionskosten vergleichbar — dieselbe Rechnung wie der Schattenpreis in Kapitel 5, nur über einen ganzen Tag.

17.5 — Wenn es größer wird. Mit 20 Blöcken und 168 Stunden hat die erste Stufe 3 360 Binärvariablen statt 120, und die Szenarienkopplung vervielfacht die kontinuierlichen Variablen. Zu erwarten ist, dass der MIP-Gap nach dem Zeitlimit nicht mehr auf null geht.

Zwei Wege aus Kapitel 9: Erstens — und in der Praxis meist ausreichend — den Gap akzeptieren; 1 bis 2 % sind bei Unit Commitment üblich und betriebswirtschaftlich belanglos. Zweitens LNS: Das Commitment eines Tages herausbrechen und exakt neu optimieren, während der Rest der Woche festbleibt. Das ist genau die Struktur aus Large_Neighborhood_Search.py — ein zusammenhängendes Fenster zerstören und mit dem exakten Solver reparieren.

Was nicht funktioniert: eine reine Metaheuristik ohne Solver. Die Fahrweise ist bei gegebenem Commitment ein LP mit tausenden Variablen; die will man nicht heuristisch lösen.

Finde den Denkfehler — „Wir rechnen mit dem P50-Szenario“

Fehler 1: Der Median ist keine Absicherung, sondern eine Wette auf die Hälfte der Fälle.

„Die Hälfte fällt besser aus, die Hälfte schlechter, im Mittel gleicht sich das aus” — der letzte Halbsatz ist falsch. Er würde stimmen, wenn die Kosten symmetrisch um den Median lägen. Sie tun es nicht: Zu viel Erzeugung kostet ein paar tausend Euro Brennstoff, zu wenig kostet Lastabwurf zu 3 000 €/MWh. Das ist dieselbe Asymmetrie wie beim Newsvendor (Kapitel 15) — nur um Größenordnungen schärfer.

Im Programm gemessen: Der Erwartungswert-Plan (nahe am P50) führt in 28 von 40 Szenarien zum Lastabwurf und kostet 149 % mehr. Nichts daran gleicht sich aus.

Fehler 2: Eine prozentuale Leistungsreserve löst das falsche Problem.

Sehen Sie sich an, was der zweistufige Plan tatsächlich verändert hat: Er hat sechs zusätzliche Blockstunden vorgehalten — er fährt einen Block früher an und lässt ihn länger laufen. Das ist eine Entscheidung über Verfügbarkeit, nicht über Leistung.

Eine Reserve von „5 % der Last” beschreibt dagegen eine Leistungsmenge. Sie hilft, wenn ein laufender Block etwas mehr liefern muss. Sie hilft nicht, wenn der benötigte Block gar nicht am Netz ist — und genau das ist der Fall, wenn der Wind ausbleibt und ein Kernblock mit acht Stunden Mindestlaufzeit um 18 Uhr nicht mehr herbeigerufen werden kann.

Die Reserve ist also nicht zu klein, sondern von der falschen Art. Was fehlt, sind nicht Megawatt, sondern angefahrene Megawatt.

Was das Team hätte tun sollen: Die Szenarien ins Modell nehmen, statt sie durch einen Repräsentanten plus Pauschalzuschlag zu ersetzen. Die Rechenzeit dafür liegt hier bei gut einer Sekunde.

Micro-Quiz

1. b) Anfahrkosten und Mindestlaufzeiten koppeln die Stunden. Die Merit-Order ist eine Sortierung und kennt keine Kopplung über die Zeit; sie ist für einen einzelnen Zeitpunkt richtig. (a) und (c) sind reale Themen, aber nicht der Grund für diese Aussage.

2. b) Die erste Stufe ist binär. Eine Kapazität lässt sich anteilig anpassen, ein Kraftwerk nicht zu 30 % anfahren — deshalb ist die Vorabentscheidung hier unwiderruflich grob. (a) ist eine Größenfrage, kein struktureller Unterschied; (c) trifft nur auf die dritte Variante zu.

3. b) Bei 3 000 €/MWh ist Vorhaltung schon im Erwartungswert billiger als Lastabwurf; die Schranke ist dann nicht bindend. Erst ein zu niedrig angesetzter Schaden macht Abwurf rechnerisch attraktiv, und dort greift sie. (a) und (c) unterstellen numerische Probleme, die es nicht gibt.

Selbsttest

1. Weil die Entscheidung einer Stunde die folgenden bindet: Anfahrkosten fallen einmal an, Mindestlaufzeiten erzwingen den Weiterbetrieb. Ein Regal füllt man unabhängig von der Reihenfolge, einen Kraftwerkspark nicht.
2. „Here and now” ist das An/Aus je Block und Stunde — binär, für alle Szenarien gleich, am Vorabend festgelegt. „Wait and see” ist die Fahrweise, also die Leistung jedes laufenden Blocks; sie darf je Szenario verschieden sein.
3. Weil die zu knappe Entscheidung nicht revidierbar ist. Ein Plan auf den Mittelwert hält in der Hälfte der Fälle zu wenig vor, und bei einer anpassbaren Größe wäre das halb so schlimm. Ein nicht angefahrener Block steht auch dann nicht zur Verfügung, wenn der Preis auf 3 000 € steigt.
4. Sie ändert etwas, wenn der Schaden im Zielfunktionsterm zu niedrig bewertet ist — dann nimmt der risikoneutrale Plan Schäden in Kauf, die man nicht hinnehmen will. Ist der Schaden realistisch bepreist, erzwingt schon die Erwartungswertminimierung die Absicherung, und die Schranke ist nicht bindend.
5. 46 € je vermiedener MWh. Entstanden als Quotient aus dem Kostenaufschlag der Absicherung (844 € je Tag) und der dadurch vermiedenen Fehlmenge im CVaR der schlechtesten 10 % (18,4 MWh). Die Zahl ist mit dem volkswirtschaftlichen Schaden eines Ausfalls vergleichbar — und damit verhandelbar.

A.18 Lösungen zu Kapitel „Finanzdaten-Modellierung — Renditen, Kovarianz und Shrinkage“

18.1 — Renditeart. (a) diskret. (b) logarithmisch. (c) logarithmisch (bzw. diskret kumuliert über Produkt). (d) logarithmisch (statistische Eigenschaften).

18.2 — Mittelwertfalle. (a) Arithmetisches Mittel: (60-40+60-40)/4 = +10\,\%. (b) 10\,000 \cdot 1{,}6 \cdot 0{,}6 \cdot 1{,}6 \cdot 0{,}6 = 10\,000 \cdot 0{,}9216 = \mathbf{9216\ €} — ein Verlust. (c) Geometrisches Mittel: 0{,}9216^{1/4} - 1 = -2{,}0\,\% p. a. Der Unterschied zwischen +10\,\% und -2\,\% ist der Grund, warum Fondswerbung gern arithmetische Mittel zeigt.

18.3 — Konditionszahl. Erwartetes Muster: Bei T = 40 < N = 30… (hier T > N, aber knapp): sehr große Konditionszahl, kleinster Eigenwert nahe null. Bei T = 100: deutlich besser. Bei T = 1000: stabil. Faustregel T \ge 5N bis 10N.

18.4 — Spaltenreihenfolge. raw["Close"].columns ist alphabetisch; raw["Close"][tickers] stellt die eigene Reihenfolge her. Existiert ein Ticker nicht, wirft [tickers] einen KeyError — das ist erwünscht: lieber ein lauter Fehler als eine stille Verschiebung.

18.5 — Beide Ziele vergleichen. Erwartetes Ergebnis: Das Konstant-Korrelations-Ziel schneidet bei Aktien meist etwas besser ab, weil es die unterschiedlichen Einzelvolatilitäten erhält. Der Unterschied ist aber kleiner als der Unterschied zwischen „mit“ und „ohne“ Shrinkage — die Wahl des Ziels ist zweitrangig gegenüber der Entscheidung, überhaupt zu schrumpfen.

18.6 — Error-Maximizer messen. (a)/(b) Erwartetes Ergebnis: Die Gleichgewichtung schlägt die Stichproben-Optimierung bis etwa T/N \approx 5–10; Ledoit-Wolf schlägt sie schon früher. (c) Praktische Folgerung: Bei knapper Datenlage ist 1/N ein ernstzunehmender Kandidat, und jede Optimierung muss sich daran messen lassen.

Finde den Denkfehler — Das risikofreie Portfolio

1. Der Rang. Eine aus T Beobachtungen geschätzte Kovarianzmatrix hat höchstens den Rang T-1 — hier also 19 statt der nötigen 30. Geometrisch heißt das: Die 20 beobachteten Renditevektoren spannen nur einen 19-dimensionalen Unterraum des 30-dimensionalen Anlageraums auf. Es bleiben 11 Richtungen übrig, über die die Daten schlicht nichts aussagen.

In genau diesen Richtungen misst die Matrix eine Varianz von exakt null. Nicht, weil dort kein Risiko wäre — sondern weil sie blind dafür ist. Der kleinste Eigenwert im Programm beträgt -6{,}5 \cdot 10^{-20}: numerisch null, mit einem Vorzeichen, das es gar nicht geben dürfte.

2. Warum der Optimierer das findet. Weil er genau danach sucht. Die Aufgabe lautet „minimiere \mathbf{w}^\top\mathbf{S}\mathbf{w}“ — und es gibt Richtungen, in denen dieser Ausdruck null ist. Ein Optimierer, der Freiheit hat, wird sie unfehlbar ansteuern.

Das ist der Kern des Error-Maximizer-Effekts: Ein Optimierer sucht nicht nach der besten Anlage, sondern nach dem größten Fehler in Ihren Schätzungen. Je mehr Freiheit Sie ihm geben, desto gründlicher findet er ihn. Er tut damit genau das, worum Sie ihn gebeten haben — die Schwäche liegt in den Daten, nicht im Verfahren.

3. Der Hebel von 3,8. Die Summe der Beträge aller Gewichte beträgt 3,8, obwohl sie sich zu 1 summieren. Das heißt: Es wird in erheblichem Umfang leerverkauft. Für je 100 € Kapital werden rund 240 € gekauft und 140 € leerverkauft.

Ein solches Portfolio ist nicht nur riskant, es ist auch praktisch kaum umsetzbar: Leerverkäufe kosten Leihgebühren, binden Sicherheiten und sind für viele Mandate schlicht untersagt. Ledoit-Wolf senkt den Hebel auf 1,8 — das Portfolio wird nebenbei handelbarer, nicht nur stabiler.

Praktischer Hinweis: Eine Nebenbedingung w >= 0 (keine Leerverkäufe) wirkt schon für sich als kräftige Regularisierung. Sie ist oft die billigste verfügbare Absicherung gegen diesen Fehler.

4. Warum 1/N gewinnt — und was das allgemein bedeutet. Die Gleichgewichtung schätzt nichts. Sie hat deshalb auch keinen Schätzfehler, den ein Optimierer ausnutzen könnte. Der rohe Optimierer dagegen bezahlt seine theoretische Überlegenheit mit einer Anfälligkeit für Rauschen, die bei T < N jeden Vorteil auffrisst. Dieser Befund ist in der Literatur breit belegt (DeMiguel, Garlappi, Uppal 2009) und für Optimierungsfachleute unbequem.

Die Lehre reicht weit über die Finanzwelt hinaus:

Jedes Optimierungsergebnis ist höchstens so gut wie die Daten, auf denen es beruht — und anders als ein Mensch hinterfragt ein Optimierer diese Daten nie.

Dasselbe Muster tritt überall auf, wo geschätzte Größen in ein Modell gehen: Bearbeitungs- zeiten aus zwanzig Stichproben, Ausfallraten aus drei Vorfällen, Nachfrageprognosen aus einer kurzen Historie. Drei Gegenmittel, in dieser Reihenfolge:

1. Mehr Daten — die einzige echte Lösung, sofern verfügbar.
2. Schrumpfen — die Schätzung zu einer stabilen, groben Struktur ziehen (Ledoit-Wolf, Regularisierung, Bayessche Priors).
3. Die Freiheit begrenzen — Nebenbedingungen wie „keine Leerverkäufe“, Ober- und Untergrenzen je Position, maximale Abweichung von einer Referenzlösung. Was der Optimierer nicht darf, kann er auch nicht falsch machen.

Und immer: außerhalb des Schätzzeitraums prüfen. Ein Modell, das nur im eigenen Datenfenster gut aussieht, sagt nichts aus. Genau diese Trennung führt Kapitel 21 als Walk-Forward-Verfahren aus.

Micro-Quiz

1 — (b) bei 75 %. 1{,}0 \cdot 0{,}5 \cdot 1{,}5 = 0{,}75. Prozentuale Änderungen verknüpfen sich multiplikativ; ein Verlust wiegt schwerer als ein gleich großer Gewinn, weil er von einer größeren Basis abgeht und der Gewinn auf eine kleinere aufsetzt. (a) ist die verbreitetste Fehlvorstellung überhaupt im Umgang mit Renditen. (c) verwechselt die Rechnung mit einem zweiten Halbierungsschritt.

2 — (b). Es geht um die Richtung der Summation: Über die Zeit addieren sich logarithmische Renditen (\ln(a \cdot b) = \ln a + \ln b), über die Anlagen eines Portfolios die diskreten (R_p = \sum_i w_i R_i). Keine der beiden ist „genauer“ (a) — sie sind exakt ineinander umrechenbar. (c) ist frei erfunden; mit der Länge des Zeitraums hat die Wahl nichts zu tun.

3 — (b). 40 Beobachtungen für 50 Anlagen ergeben eine Matrix vom Rang höchstens 39 — singulär, mit mindestens 11 Richtungen scheinbar null Risikos. (a) verkennt, dass es nicht auf die absolute Zahl der Beobachtungen ankommt, sondern auf ihr Verhältnis zur Zahl der Anlagen; die Faustregel lautet T \gtrsim 10 \cdot N. (c) wäre eine Notlösung, die Information wegwirft — Shrinkage nutzt alle 50 Anlagen und ist praktisch immer die bessere Wahl.

Selbsttest

1. Log-Renditen sind Differenzen von Logarithmen — die addieren sich über die Zeit. Diskrete Renditen sind lineare Anteile am Kapital — die addieren sich über gewichtete Positionen.
2. Die Optimierung sucht die Richtungen kleinster geschätzter Varianz — genau jene, deren Eigenwerte am stärksten nach unten verzerrt sind. Sie optimiert dadurch in das Schätzrauschen hinein.
3. Der Rang von \mathbf{X}^\top\mathbf{X} ist höchstens T < N — die Matrix ist nicht invertierbar, das GMV-Problem hat unendlich viele Lösungen.
4. Stichprobenmatrix (unverzerrt, verrauscht) mit strukturiertem Ziel (verzerrt, stabil). \delta wird analytisch so bestimmt, dass der erwartete quadratische Fehler minimal wird.
5. Skalierte Einheitsmatrix (sklearn) und Konstant-Korrelations-Ziel (LW 2003).

A.19 Lösungen zu Kapitel „Die moderne Portfoliotheorie nach Markowitz“

19.1 — Diversifikationseffekt.

Rechenweg für (0{,}5;\ 0{,}5): \sigma_p^2 = 0{,}25\cdot0{,}0625 + 0{,}25\cdot0{,}0144 + 2\cdot0{,}25\cdot(-0{,}2)\cdot0{,}25\cdot0{,}12 = 0{,}015625 + 0{,}0036 - 0{,}003 = 0{,}016225, also \sigma_p = 12{,}74\,\%.

Beste Sharpe Ratio unter den vier Kandidaten: (0{,}3;\ 0{,}7). Das exakte Optimum liegt bei w_1 = 0{,}318. Bemerkenswert: Die Mischung (0{,}3;\ 0{,}7) hat mit 10,08 % eine geringere Volatilität als beide Einzeltitel (25 % und 12 %) — genau der Diversifikationseffekt, den die negative Korrelation ermöglicht.

19.2 — Lambda deuten. Von \lambda=0 (GMV, linker unterer Punkt der Kurve) wandert die Lösung entlang der Effizienzgrenze nach rechts oben, bis sie bei \lambda\to\infty im Titel mit der höchsten Rendite endet (bzw. an der Positionsobergrenze).

19.3 — Korn-Transformation. \text{SR}(c\mathbf{w}) = \frac{c\mathbf{w}^\top\boldsymbol{\mu}-r_f}{\sqrt{c^2\mathbf{w}^\top\boldsymbol{\Sigma}\mathbf{w}}} — bei einem Portfolio mit \sum w_i = 1 und Überrenditen geschrieben als \mathbf{w}^\top(\boldsymbol{\mu}-r_f\mathbf{1}) kürzt sich c heraus. Mit der Bedingung \sum w_i = 1 ist die Skala jedoch fixiert, man kann also nicht frei skalieren. Die Transformation ersetzt diese Bedingung durch \sum y_i = \kappa mit freiem \kappa und normiert stattdessen die Überrendite auf 1 — dadurch wird die Skala wieder frei und das Problem konvex.

19.4 — Restriktionen kosten. Erwartetes Muster: Sharpe Ratio sinkt monoton mit strengerer Grenze. Unlösbar wird es bei w_{\max} < 1/n — dann kann die Summe der Gewichte 1 nicht mehr erreicht werden.

19.5 — Den Sektorfehler nachstellen. (a) AAPL, AMZN, CVX, GS statt AAPL, MSFT, NVDA, AMZN. (b) Die Gewichte unterscheiden sich deutlich, weil die eigentlich zu begrenzenden Tech-Titel frei laufen. (c) Nein — die Kennzahlen sehen völlig plausibel aus. Genau das macht den Fehler so gefährlich.

19.6 — Kardinalität. Erwartung: Die Sharpe Ratio sinkt leicht, die Rechenzeit steigt deutlich (MIQP statt QP). Bei K \ge 5 und w_{\max} = 0{,}20 ist die Restriktion praktisch nicht mehr bindend.

19.7 — Out-of-Sample. Typisches Ergebnis: Max-Sharpe schneidet in der zweiten Hälfte schlechter ab als in der ersten — es hat Schätzrauschen mitoptimiert. GMV ist stabiler (keine Renditeprognose nötig), 1/N oft überraschend gut. Mit Ledoit-Wolf verbessern sich GMV und Max-Sharpe spürbar. Praxisfolgerung: Renditeprognosen sind viel unzuverlässiger als Risikoschätzungen — Modelle, die ohne sie auskommen, sind robuster.

Finde den Denkfehler — Zwölf gleiche Anlagen, ein sehr ungleiches Portfolio

1. Woher die Spanne kommt. Aus reinem Rauschen. Der Mittelwert von 250 Beobachtungen einer Größe mit Standardabweichung \sigma = 1{,}2\,\% hat selbst noch den Standardfehler

\frac{\sigma}{\sqrt{T}} = \frac{0{,}012}{\sqrt{250}} = 0{,}00076 = 0{,}076\,\%

Das ist fast das Doppelte der wahren Rendite von 0,040 %. Bei zwölf unabhängigen Schätzungen liegen höchster und niedrigster Wert typischerweise rund drei Standardfehler auseinander — gemessen wurden 0,243 Prozentpunkte, also das 6,1-Fache des wahren Werts.

Die Anlagen sind identisch. Die Schätzungen sind es nicht — und der Optimierer sieht nur die Schätzungen.

2. Wie viele Beobachtungen nötig wären. Damit der Standardfehler klein gegen die wahre Rendite wird, etwa \sigma/\sqrt{T} \le \mu/2:

T \ge \left(\frac{2\sigma}{\mu}\right)^2 = \left(\frac{2 \cdot 0{,}012}{0{,}0004}\right)^2 = 60^2 = 3600 \text{ Beobachtungen}

Das sind rund 14 Jahre Tagesdaten — für eine einzige Anlage, unter der Annahme, dass sich ihre Eigenschaften in dieser Zeit nicht ändern. Genau daran scheitert die Renditeschätzung grundsätzlich, nicht nur bei diesem Beispiel.

3. Warum Renditen schlimmer sind als Kovarianzen. Zwei Gründe:

1. Statistisch. Eine Varianz konvergiert deutlich schneller als ein Mittelwert. Grob: Der relative Fehler einer Varianzschätzung fällt mit \sqrt{2/T}, während der einer Renditeschätzung mit \sigma/(\mu\sqrt{T}) fällt — und \sigma/\mu ist bei Aktien typischerweise 30 und größer. Bei denselben 250 Beobachtungen ist die Kovarianz brauchbar und der Mittelwert nicht.
2. Strukturell. Die Renditen stehen im linearen Teil der Zielfunktion. Eine kleine Änderung von \mu_i verschiebt die Lösung sofort und ungedämpft; der quadratische Risikoterm wirkt dagegen ausgleichend. Deshalb reagieren die Gewichte auf Renditeschätzfehler viel heftiger als auf Kovarianzfehler.

Zusammen ergibt das das beobachtete Bild: 38 % Konzentration in einer Anlage, obwohl alle zwölf identisch sind.

4. Drei Gegenmittel.

1. Renditeschätzung ganz vermeiden. Das Minimum-Varianz-Portfolio minimiert nur \mathbf{w}^\top\boldsymbol{\Sigma}\mathbf{w} und braucht überhaupt kein \boldsymbol{\mu}. Damit fällt die unzuverlässigste Eingangsgröße ersatzlos weg. Das ist das wirksamste Mittel, weil es das Problem nicht abmildert, sondern beseitigt — man kann eine Größe nicht falsch schätzen, die man nicht verwendet.
2. Stark schrumpfen. Wenn Renditen gebraucht werden, zieht man sie kräftig zum Gesamtmittel (James-Stein) oder zu einer Gleichgewichtsannahme (Black-Litterman) — deutlich stärker als bei Kovarianzen, aus den Gründen unter (c).
3. Freiheit begrenzen. Obergrenzen je Position (etwa 15 %), Sektorgrenzen, maximale Abweichung von einer Referenzgewichtung. Was der Optimierer nicht darf, kann er auch nicht auf Rauschen setzen — dasselbe Rezept wie in Abschnitt 18.8.

Und die Kontrollfrage für den Alltag: Rechnen Sie Ihr Modell mit den Daten des halben Zeitraums und dann mit denen der anderen Hälfte. Wenn die Gewichte dabei stark springen, optimieren Sie Rauschen — unabhängig davon, wie gut die Kennzahlen im Schätzzeitraum aussehen.

Micro-Quiz

1 — (b). Das renditestärkste Portfolio auf der Effizienzlinie hat notwendig das schlechteste Rendite-Risiko-Verhältnis (im Kapitelbeispiel 0,44 gegenüber 0,75 beim Optimum) und besteht vollständig aus der renditestärksten Einzelanlage — Diversifikation findet dort gar nicht mehr statt. (a) und (c) sind sachlich falsch: Der Punkt ist numerisch völlig unproblematisch und wird von CVXPY ohne Weiteres gefunden.

2 — (b) es braucht keine Renditeschätzung. Renditen sind die mit Abstand unzuverlässigste Eingangsgröße (Standardfehler größer als der geschätzte Wert selbst); wer sie nicht benötigt, umgeht das Problem vollständig. (a) trifft nicht zu — die Nebenbedingungen sind dieselben. (c) ist falsch: Das Minimum-Varianz-Portfolio erzielt erwartungsgemäß weniger Rendite; sein Vorteil liegt in der Verlässlichkeit, nicht in der Höhe.

3 — (b) Schätzfehler. Eine Konzentration von 44 % auf einen von zwölf Titeln ist das typische Bild eines Optimierers, der einem Rauschsignal folgt — im Kapitelbeispiel entsteht sie sogar dann, wenn alle Anlagen nachweislich identisch sind. (a) mag zutreffen, ist aber die unwahrscheinlichere Erklärung und muss belegt werden, nicht angenommen. (c) beschriebe ein anderes Fehlerbild: Eine falsch skalierte Kovarianzmatrix führt zu unplausiblen Risikowerten, nicht zu Konzentration.

Selbsttest

1. Weil sich Schwankungen teilweise ausgleichen (Korrelationsterm), während sich die Renditen linear mitteln.
2. Das GMV. Es benötigt nur \boldsymbol{\Sigma}, keine Renditeprognose — und Renditeprognosen sind die unzuverlässigste Zutat.
3. Sie ist ein Quotient. Die Korn-Transformation normiert den Zähler auf 1, wodurch das Maximieren des Quotienten zum Minimieren des Nenners wird — ein QP.
4. Alle mit \kappa mitskalieren: aus w_i \le c wird y_i \le c\kappa.
5. Weil sie keinerlei Schätzung benötigt und damit keinen Schätzfehler enthält — sie schlägt optimierte Portfolios out of sample überraschend häufig.

A.20 Lösungen zu Kapitel „Tail-Risiko, CVaR und Transaktionskosten“

20.1 — VaR und CVaR von Hand. Sortierte Verluste: -2{,}0; -1{,}2; -0{,}8; -0{,}4; 0{,}3; 0{,}6; 1{,}1; 2{,}1; 5{,}4; 8{,}9. Das 80 %-Quantil ist der 8. Wert: \text{VaR}_{80\%} = 2{,}1. $_{80%} = $ Mittel der schlechtesten 20 % = (5{,}4+8{,}9)/2 = \mathbf{7{,}15}.

20.2 — Subadditivität. Ein Risikomaß sollte Diversifikation nie bestrafen: Das Risiko eines zusammengelegten Portfolios darf nicht größer sein als die Summe der Einzelrisiken. Wird das verletzt, hätte eine Bank einen Anreiz, Portfolios künstlich aufzuspalten, um Eigenkapitalanforderungen zu senken — ökonomisch unsinnig.

20.3 — Rockafellar-Uryasev nachvollziehen. (a) Schlechtestes Drittel von (1,4,9) ist \{9\} → CVaR = 9. (b) Mit \frac{1}{S(1-\alpha)} = \frac{1}{3\cdot(1/3)} = 1: \gamma=0: 0 + (1+4+9) = 14. \gamma=1: 1 + (0+3+8) = 12. \gamma=4: 4 + (0+0+5) = \mathbf{9}. \gamma=5: 5+4 = 9. \gamma=9: 9+0 = 9. (c) Minimum ab \gamma = 4 bei 9 — identisch mit (a) ✓. (Das Minimum wird auf einem ganzen Intervall angenommen, weil die Funktion stückweise linear ist — genau der Grund, warum der CVaR nicht streng konvex ist.)

20.4 — Einheiten prüfen. In einem Modell, das annualisierte Rendite gegen täglichen CVaR verrechnet, wirkt 1{,}5 effektiv als 1{,}5/252 \approx 0{,}006 auf Tagesbasis — der Risikoterm ist also um Faktor 252 zu leicht gewichtet. Um dieselbe Wirkung wie RISIKOAVERSION = 1.5 im konsistenten Tagesmodell zu erzielen, hätte man dort lambda_risk = 1.5 * 252 = 378 setzen müssen.

20.5 — Risikoaversion kalibrieren. (a) Konkav, ähnlich der Markowitz-Frontier, aber im Rendite-CVaR-Raum. (b) Bei Normalverteilung entspricht CVaR-Optimierung ungefähr der Varianz-Optimierung; die Ergebnisse divergieren umso stärker, je schiefer die Verteilung ist. (c) Empfehlung ohne Fachjargon: „Bei dieser Einstellung liegt der durchschnittliche Verlust an den schlechtesten fünf Prozent der Tage bei X Prozent — bei einer erwarteten Rendite von Y Prozent.“ Das ist entscheidbar; „\lambda = 4“ ist es nicht.

20.6 — Grenze statt Strafe. (a) Mit engerer Grenze sinkt die erreichbare Rendite; bei \tau = 0 bleibt das Altportfolio. (b) Vorteil der Grenze: garantierte Obergrenze für die Handelsaktivität — wichtig, wenn Liquidität oder Compliance eine harte Schranke verlangen. Nachteil: Sie kann das Modell unlösbar machen und ignoriert, dass ein sehr lohnender Trade den Aufwand wert wäre. (c) Strafe bei ökonomischer Abwägung, Grenze bei regulatorischen oder Liquiditätsvorgaben.

Finde den Denkfehler — Das Risikobudget, das durch Diversifikation stieg

1. Die entscheidende Wahrscheinlichkeit. Bei zwei unabhängigen Anleihen mit je 4 % Ausfallwahrscheinlichkeit fällt mindestens eine aus mit

1 - (1 - 0{,}04)^2 = 1 - 0{,}9216 = 0{,}0784 = \mathbf{7{,}84\,\%}

Das ist mehr als 5 % — und damit rutscht der Ausfall in genau den Bereich, den der VaR(95) betrachtet. Einzeln lag er mit 4 % darunter und blieb unsichtbar.

Der Sprung von -4 € auf +98 € ist also kein Rechenfehler, sondern die korrekte Antwort auf eine schlecht gestellte Frage.

2. Warum eine ausfallgefährdete Anleihe „Gewinn“ meldet. Der VaR(95) ist das 95-%- Quantil der Verlustverteilung: der Verlust, der an höchstens 5 % der Fälle überschritten wird. Bei einer einzelnen Anleihe passiert in 96 % der Fälle nichts (Kupon +2 €, also Verlust -2 €). Das 95-%-Quantil liegt damit mitten im guten Bereich — bei -2 €.

Der Totalverlust findet in den restlichen 4 % statt, also jenseits der Schwelle. Der VaR schaut dort nicht hin. Er ist nicht falsch berechnet; er beantwortet schlicht eine andere Frage als die, die das Risikomanagement stellt.

3. Verletzt wird die Subadditivität — die Forderung

\rho(A + B) \le \rho(A) + \rho(B)

Auf Deutsch: Ein Portfolio darf nie riskanter sein als seine Teile zusammen; Diversifikation darf nicht schaden. Ein Maß, das das erfüllt (zusammen mit drei weiteren Eigenschaften), heißt kohärent.

Was das praktisch bedeutet, ist gravierender, als es klingt. Eine Organisation tut mit Kennzahlen immer dasselbe: Sie verteilt sie auf Einheiten und zählt sie wieder zusammen. Genau das ist beim VaR unzulässig:

• Budgets lassen sich nicht aufteilen. Zwei Abteilungen, die je ihr VaR-Limit einhalten, können zusammen weit darüber liegen.
• Es entstehen Fehlanreize. Eine Position, deren Verlustwahrscheinlichkeit knapp unter dem VaR-Niveau liegt, erscheint im Bericht als risikolos — je katastrophaler und seltener, desto unsichtbarer. Wer nach VaR gesteuert wird, hat einen direkten Anreiz, genau solche Positionen aufzubauen.
• Diversifikation wird bestraft statt belohnt — das Gegenteil dessen, wozu Risikosteuerung da ist.

4. Warum der CVaR das nicht kann. Der CVaR mittelt über den gesamten Schwanz, statt an seiner Grenze stehenzubleiben. Damit sieht er den Ausfall in jedem der drei Fälle, und das Ergebnis verhält sich wie erwartet: 79,59 € und 79,66 € einzeln, 101,33 € zusammen statt 159,24 € — die Diversifikation senkt das Risiko um rund ein Drittel.

Formal folgt die Subadditivität daraus, dass der CVaR sich als Maximum über Erwartungswerte schreiben lässt (Darstellungssatz für kohärente Risikomaße), und Maxima von Erwartungswerten sind stets subadditiv. Anschaulicher: Ein Mittelwert über eine Menge verhält sich gutartig, wenn man Mengen zusammenlegt; ein Quantil nicht — es kann springen, sobald sich die Reihenfolge der Szenarien ändert.

Die praktische Konsequenz ist die Umstellung der Bankenaufsicht mit Basel III vom VaR auf den Expected Shortfall — dieselbe Größe, die hier CVaR heißt. Und für Ihre eigenen Modelle, auch außerhalb der Finanzwelt: Wo immer Sie eine Risikokennzahl über Einheiten aggregieren wollen, prüfen Sie zuerst, ob das Maß das überhaupt zulässt.

Micro-Quiz

1 — (b) nichts. Der VaR ist ein Quantil: Er markiert die Schwelle und sagt nichts über den Bereich dahinter. Genau das zeigt der Schnellstart dieses Kapitels — zwei Anlagen mit identischem VaR von 3,00 %, aber CVaR 3,00 % gegen 9,17 %. (a) verwechselt die Schwelle mit dem, was hinter ihr liegt. (c) ist ebenfalls falsch: Anlage B hat zwar die höhere Schwankung, aber die Schwankung allein sagt nichts über die Form des Schwanzes — genau deshalb reicht auch die Varianz als Risikomaß nicht aus.

2 — (b). Rockafellar und Uryasev zeigen, dass sich der CVaR als Minimum über eine Hilfsvariable \gamma schreiben lässt; mit Schlupfvariablen für die Terme \max(\cdot, 0) wird daraus ein gewöhnliches LP. Die VaR-Minimierung ist dagegen nicht-konvex (das Quantil springt) und hat viele lokale Optima — dasselbe Problem wie in Abschnitt 11.6. (a) ist zwar zutreffend, aber nicht der entscheidende Grund; (c) ist eine wahre Aussage ohne Bezug zur Optimierbarkeit.

3 — (b) CVaR wegen der Subadditivität. Nur ein subadditives Maß erlaubt es, Kennzahlen über Einheiten zusammenzufassen, ohne dass Diversifikation bestraft wird. (a) verkennt, dass gerade die Verbreitung des VaR das Problem ist — er wird laufend addiert, obwohl er es nicht darf. (c) ist falsch, und der Denkfehler dieses Kapitels ist das Gegenbeispiel: Die beiden Anleihen dort sind gerade unabhängig, und genau deshalb tritt die Verletzung auf.

Selbsttest

1. Die Höhe der Verluste jenseits der Schwelle — der VaR kennt nur die Schwelle selbst.
2. Er ist in der Szenario-Darstellung stückweise linear; das Minimum kann auf einem ganzen Intervall angenommen werden.
3. Sie ist eine freie Hilfsvariable, die im Optimum automatisch den VaR annimmt — man muss ihn also nicht vorher kennen.
4. Weil die L_1-Norm dünn besetzte Lösungen begünstigt (im Gegensatz zur L_2-Norm, die viele kleine Änderungen bevorzugt).
5. Weil der Gewichtungsparameter dann eine andere Bedeutung hat, als er zu haben scheint — das Modell ist nicht mehr kalibrierbar.

A.21 Lösungen zu Kapitel „Die vollständige quantitative Handelsmaschine“

21.1 — Lookahead erkennen. (a) sauber (:heute). (b) Lookahead — gesamter Zeitraum. (c) Lookahead — Volatilität über den ganzen Zeitraum enthält Zukunft. (d) sauber — Gewichte aus Daten bis heute, angewendet auf heute (idealerweise auf morgen). (e) Survivorship-Bias — das Universum wird danach gefiltert, wer über den gesamten Zeitraum Daten hat.

21.2 — Kennzahlen deuten. A: Sharpe = (12-2)/22 = 0{,}45, Calmar = 12/35 = 0{,}34. B: Sharpe = (8-2)/9 = 0{,}67, Calmar = 8/12 = 0{,}67. Empfehlung: B — für einen Pensionsfonds ist der Drawdown entscheidend, weil laufende Auszahlungen in einer Verlustphase Substanz vernichten. B ist in beiden risikoadjustierten Maßen besser.

21.3 — Rebalancing-Kalender. Etwa 25–30 % der Termine fallen aus. Die Kennzahlen ändern sich messbar — in welche Richtung, ist zufällig. Genau das ist der Punkt: Der Fehler verzerrt, ohne aufzufallen.

21.4 — Rebalancing-Frequenz. Typisches Muster: Turnover und Kosten steigen etwa linear mit der Frequenz, der Bruttoertrag verbessert sich nur unterproportional. Bei 0,15 % Gebühren ist monatlich meist vertretbar, bei 0,5 % eher quartalsweise. Ein Toleranzband (nur handeln bei Abweichung > x %) schlägt fast immer die feste Frequenz.

21.5 — Krisenverhalten. Erwartung: Die Überrendite ist selten stabil; oft stammt sie aus wenigen Perioden. Folgerung: Eine gute Gesamtkennzahl kann von einer einzigen glücklichen Phase getragen sein — immer nach Teilzeiträumen aufschlüsseln.

21.6 — Data Snooping messen. Erwartetes Ergebnis: Die beste In-Sample-Sharpe-Ratio liegt deutlich über dem Mittelwert aller Varianten; auf dem zurückgehaltenen Zeitraum fällt sie Richtung Mittelwert zurück. Die Differenz zwischen (a) und (c) ist der Selektionseffekt — genau das, was die Deflated Sharpe Ratio korrigieren soll.

Finde den Denkfehler — Die Strategie mit dem hochsignifikanten Ergebnis

1. Warum ein korrekter Backtest wertlos sein kann. Der Backtest misst genau das, was er messen soll: die Wertentwicklung dieser einen Strategie. Die Frage, die beantwortet werden soll, lautet aber anders — nämlich: „Ist dieses Ergebnis besser, als es Zufall erklären kann?“

Und für diese Frage ist entscheidend, dass die Strategie als Beste aus hundert ausgewählt wurde. Ein p-Wert von 0,0094 bedeutet: „Wenn diese Strategie keinen Vorteil hätte, sähe sie in 0,94 % der Fälle so gut aus.“ Bei hundert Versuchen erwartet man aber rund fünf Ergebnisse unter dem 5-%-Niveau — allein durch Zufall. Genau das zeigt die Tabelle: Auf reinem Rauschen liefert die Beste von hundert im Mittel Sharpe 1,13 und p = 0,0094. Dieselben Zahlen.

Der Fehler steckt nicht im Backtest, sondern in der Auswahl. Deshalb ist er auch durch noch so sorgfältiges Programmieren nicht zu verhindern.

2. Warum die konstante Spalte der Kern ist. Ein Test zum 5-%-Niveau irrt in 5 % der Fälle — das ist seine Definition, nicht sein Fehler. Der Anteil bleibt deshalb bei jedem Stichprobenumfang gleich.

Was sich ändert, ist die absolute Zahl:

Und nun kommt der entscheidende Schritt: Berichtet wird immer nur die beste Strategie. Von den fünf zufälligen Treffern bei hundert Versuchen sieht der Vorgesetzte genau einen — den erfolgreichsten. Die 99 verworfenen Varianten tauchen in keiner Präsentation auf. Der Auswahlprozess ist unsichtbar, das Ergebnis sichtbar.

3. Die fehlende Zahl ist die Anzahl der Versuche. Sie steht in keinem Backtest, in keiner Kennzahl und in keinem Programm — sie existiert nur im Kopf der Person, die die Arbeit gemacht hat. Ohne sie ist weder der p-Wert noch die Sharpe-Kennzahl interpretierbar.

Deshalb: Führen Sie ein Protokoll. Jede probierte Variante, auch die schnell verworfenen, auch die „nur mal geschaut“. Diese Liste ist kein bürokratischer Ballast, sondern die Voraussetzung dafür, dass das Endergebnis überhaupt eine Aussage hat.

4. Drei Gegenmittel.

1. Zählen. Siehe (c). Das kostet nichts und ist die Grundlage für alles Weitere.
2. Korrigieren. Die Bonferroni-Korrektur teilt die Signifikanzschwelle durch die Zahl der Versuche: Bei 100 Varianten muss p < 0{,}0005 gelten statt p < 0{,}05. Der Wert 0,0094 aus dem Beispiel besteht diese Hürde deutlich nicht. Für Handelsstrategien gibt es verfeinerte Verfahren (Deflated Sharpe Ratio nach Bailey und López de Prado), die dasselbe Prinzip verfolgen und dabei die Korrelation zwischen den Varianten berücksichtigen.
3. Zurückhalten. Legen Sie einen Zeitraum beiseite, bevor Sie anfangen, und rühren Sie ihn nicht an.

Warum das dritte Mittel nur einmal wirkt: Der zurückgehaltene Zeitraum ist genau so lange ein unabhängiger Test, wie er keinerlei Einfluss auf Ihre Entscheidungen hatte. In dem Moment, in dem Sie das Ergebnis sehen und daraufhin irgendetwas ändern — einen Parameter, ein Fenster, auch nur die Auswahl unter mehreren fertigen Kandidaten —, ist er Teil der Suche geworden. Ab dann misst er nicht mehr die Strategie, sondern wieder Ihre Anpassungsfähigkeit.

Ein zweiter Blick auf denselben Testzeitraum ist deshalb kein „nochmal prüfen“, sondern der 101. Versuch. Wer ihn braucht, braucht neue Daten — oder muss warten, bis die Zukunft welche liefert. Das ist unbequem und der Grund, warum diese Regel so oft gebrochen wird.

Micro-Quiz

1 — (b) nichts. Beide Kennzahlen sind Mittelwerte über die Zeit und blind für die Reihenfolge. Der Schnellstart dieses Kapitels zeigt es an denselben Tagesrenditen, nur anders angeordnet: identische Rendite (8,88 %), identische Sharpe (0,61), Rückschlag 19 % gegen 98,7 %. (a) ist die verbreitete Fehlannahme, die dazu führt, dass Rückschläge gar nicht berichtet werden. (c) ist falsch — die Schwankung ist in beiden Reihen exakt gleich, sie enthalten ja dieselben Zahlen.

2 — (b) unauffällig. Bei 50 Versuchen erwartet man rein zufällig 50 \cdot 0{,}05 = 2{,}5 Ergebnisse unter dem 5-%-Niveau; ein p-Wert von 0,01 ist in dieser Menge nichts Besonderes. Die Bonferroni-Schwelle liegt bei 0{,}05/50 = 0{,}001 — davon ist 0,01 um den Faktor zehn entfernt. (a) interpretiert den p-Wert so, als wäre es der einzige Test gewesen — genau der Denkfehler dieses Kapitels. (c) ist zu pauschal: Der p-Wert ist brauchbar, sofern man die Zahl der Versuche berücksichtigt.

3 — (b). Unabhängigkeit ist keine Eigenschaft der Daten, sondern des Verfahrens: Sobald das Ergebnis eine Entscheidung beeinflusst hat, ist der Zeitraum Teil der Suche. (a) trifft die Sache nicht — auch frische Daten wären nach der ersten Verwendung verbraucht. (c) ist frei erfunden; an der Berechnung ändert sich bei Wiederholung nichts.

Selbsttest

1. Zum Zeitpunkt t darf nur Information verwendet werden, die zu t vorlag.
2. Weil sie oft auf Wochenenden oder Feiertage fallen und dann nicht im Handelstage-Index enthalten sind — das Rebalancing entfällt still.
3. Man verändert künstlich die Daten nach dem Stichtag und prüft, ob sich das Signal davor ändert. Wirksam, weil er die Fehlerklasse mechanisch abdeckt statt auf Aufmerksamkeit zu setzen.
4. Weil sich die Gewichte zwischen Rebalancings durch Kursbewegungen von selbst verändern. Ohne Drift unterstellt man implizit tägliches kostenloses Rebalancing.
5. Weil er im Arbeitsprozess entsteht und im Code unsichtbar ist — man sieht dem Programm nicht an, wie viele Varianten verworfen wurden.

A.22 Lösungen zu Kapitel „Praxisfallen und der Weg zum produktiven Einsatz“

22.1 — Hart oder weich, revisited. (a) hart: gesetzliche Ruhezeit, Qualifikationspflicht. (b) weich: individuelle Wunschtage, Vermeidung von Freistunden. (c) diskutabel: Höchstzahl Vertretungsstunden pro Tag (tariflich vs. Notfall), gleichmäßige Wochenendverteilung.

22.2 — Zeitlimit wählen. (a) 1–3 s, Gap 5–10 % (Echtzeit schlägt Optimalität). (b) 1–5 min, Gap 1–2 %. (c) Stunden, Gap ~0 % (einmalige, folgenreiche Entscheidung). (d) 30–60 s, Gap 1 % — die Datenunsicherheit ist ohnehin größer.

22.3 — Relaxation einbauen. Muster wie in Infeasibility_Diagnose.py: Schlupfvariable je Mindestbesetzung, Strafe deutlich über allen weichen Zielen, aber endlich. Wichtig: gestaffelte Strafen, damit der Solver die am wenigsten schmerzhafte Verletzung wählt.

22.4 — Erklärbarkeit. Report-Struktur: (1) Zielwert und Aufschlüsselung nach Bestandteilen; (2) je Entscheidung die bindenden Bedingungen; (3) Schattenpreise der knappsten Ressourcen mit Handlungsempfehlung.

22.5 — Den Bericht in die Irre führen. (a) Der Plan kippt: Rahmen fällt von 47,5 auf 40 — das Minimum aus dem Liefervertrag —, Deckel steigt von 97,5 auf 120, die Marktgrenze. Der Deckungsbeitrag springt von 3 930 € auf 5 190 €. Mit ihm wechselt die Engpassstruktur: „Kapazität Lackieren” bindet nicht mehr, dafür bindet jetzt „Liefervertrag Rahmen” — und zwar als Kosten von 25 € je Stück, weil der Vertrag zur Herstellung eines inzwischen unattraktiven Produkts zwingt. Alle Schattenpreise steigen deutlich (Träger von 18 € auf 58 €). Der entscheidende Punkt der Aufgabe: Der Satz „Teuerste Bindung ist Liefervertrag Träger” steht wörtlich unverändert im Bericht — obwohl die Zahl dahinter sich mehr als verdreifacht hat und ein anderer Engpass die Fabrik begrenzt. Ein Bericht, der sich nicht ändert, ist kein Beweis dafür, dass sich nichts geändert hat. (b) Etwa: „Unter der Annahme eines Deckungsbeitrags von 9 € je Deckel ist ‚Liefervertrag Träger’ die teuerste Bindung (18 € je Stück).” Die Aussage bekommt damit ihre Voraussetzung mit — und wird angreifbar, was sie sein soll. (c) Mindestens eines von beidem: den Gültigkeitsbereich jedes Schattenpreises (bis wohin gilt er?), oder das Ergebnis einer Sensitivitätsrechnung über die unsichersten Eingangsgrößen — etwa „bei ±20 % Deckungsbeitrag Deckel bleibt die Rangfolge/kippt sie”. Das Programm rechnet den Gültigkeitsbereich für die auffälligste Stellschraube bereits aus; ihn für alle auszuweisen ist eine kleine Erweiterung.

22.6 — Gap gegen Laufzeit. Erwartetes Muster: Von 10 % auf 2 % kostet wenig Zeit; von 1 % auf 0 % kann die Laufzeit um Größenordnungen steigen, ohne dass sich der Zielwert nennenswert verbessert. Empfehlung: Gap dort ansetzen, wo die Kurve knickt — typischerweise 1–2 %.

22.7 — Post-Mortem. Bewertungskriterien: Wird zwischen Symptom, Ursache und fehlender Prüfung unterschieden? Ist die abgeleitete Regel allgemein genug, um beim nächsten Projekt zu helfen (z. B. „Nach jeder Vorzeichenumkehr eine numerische Gegenprobe“), aber konkret genug, um überprüfbar zu sein?

Finde den Denkfehler — Das Modell, das seit einem Jahr nicht mehr optimiert

1. Warum die konstante Laufzeit das Symptom ist. Ein Solver, der fertig wird, braucht so lange, wie das Problem eben dauert — und diese Zeit wächst mit den Daten. Eine Laufzeit, die über Jahre exakt bei 3,00 Sekunden liegt, kann deshalb nur eines bedeuten: Der Job wird nicht fertig, sondern abgeschnitten.

Genau darin liegt die Tücke. Die übliche Betriebsüberwachung achtet auf zwei Dinge: Abstürze und Laufzeitspitzen. Hier gibt es weder das eine noch das andere — im Gegenteil, das Zeitlimit sorgt für eine bemerkenswert gleichmäßige Laufzeit. Das System sieht besser aus als eines, das ehrlich langsamer wird.

Es ist der umgekehrte Fall zum Alarm, den man erwartet: Ein Optimierungsjob mit Zeitlimit wird bei wachsenden Daten nicht langsamer, sondern schlechter. Und Qualität steht in keinem Betriebsprotokoll.

2. Die drei fehlenden Größen:

Nur die Kosten zu protokollieren, ist das Äquivalent dazu, bei einem Messgerät den Anzeigewert abzulesen und die Fehlermeldung daneben zu ignorieren.

3. Am frühesten warnt die Zeitausschöpfung. Sie ist eine stetige Größe und beginnt zu steigen, lange bevor das Limit erreicht wird — im Beispiel von 0,57 s über 1,50 s bis zum Anschlag. Status und Gap springen dagegen erst, wenn es bereits passiert ist: Bis 2024-Q3 lauten sie „Optimal“ und 0,00 %, ab 2025-Q1 plötzlich „Time limit“ und 8,4 %.

Eine Warnung bei 50 % Ausschöpfung hätte hier rund ein halbes Jahr Vorlauf gegeben — genug, um in Ruhe zu reagieren: Zeitlimit anheben, Modell straffen, oder einen bewussten Zielgap festlegen (etwa „1 % genügt uns“), statt eine unbekannte Verschlechterung hinzunehmen.

Faustregel: Warnen Sie bei 50 % Zeitausschöpfung, alarmieren Sie bei 80 %. Und protokollieren Sie den Gap immer — auch dann, wenn er null ist. Eine Reihe von Nullen ist die beste Nachricht, die ein Betriebsprotokoll enthalten kann.

4. Warum sich die Mehrkosten nicht beziffern lassen. Der Gap von 17,2 % ist eine Obergrenze, keine Messung: Er besagt, dass die gefundene Lösung höchstens 17,2 % über dem theoretisch Bestmöglichen liegt. Ob sie tatsächlich 17 % oder nur 3 % darüber liegt, weiß niemand — dazu müsste man das Optimum kennen, und genau das hat der Job ja nicht berechnet.

Nachträglich lässt sich das nur teilweise klären: Man kann die alten Instanzen erneut lösen, diesmal ohne Zeitlimit, und die Differenz ausrechnen. Was sich nicht rekonstruieren lässt, sind die Entscheidungen, die auf den schlechteren Plänen beruhten — welches Lager wurde nicht geschlossen, welche Tour wurde ein Jahr lang unnötig gefahren. Diese Kosten sind angefallen und nicht mehr zuzuordnen.

Das ist das eigentliche Argument für die Überwachung: Nicht, dass ein Gap von 17 % schlimm wäre — er kann völlig hinnehmbar sein —, sondern dass man ihn kennen muss, um darüber zu entscheiden. Ein bewusst akzeptierter Gap ist eine Managemententscheidung; ein unbemerkter ist ein Betriebsrisiko.

Micro-Quiz

1 — (b) das Zeitlimit greift. Eine Laufzeit, die exakt dem Limit entspricht und über Monate konstant bleibt, ist kein Stabilitätsbeleg, sondern zeigt, dass der Solver jedes Mal abgebrochen wird. (a) ist die Fehldeutung, um die es im Denkfehler geht. (c) läge nahe, wenn die Laufzeit schwankte oder das Limit überschritte — hier ist die Ursache aber im Modell und in der Datenmenge zu suchen, nicht in der Hardware.

2 — (b) aus dem ausgegebenen Tourenplan. Eine Prüfung muss von der Lösung ausgehen und die Anforderungen unabhängig nachrechnen. (a) fragt die Ladungsdimension — also ausgerechnet den Baustein, dessen Fehlen der Fehler war (siehe Abschnitt 8.7); existiert sie nicht, stürzt die Prüfung ab, existiert sie, kann sie per Konstruktion nie verletzt sein. (c) prüft gar nichts: Ob eine Kapazität in der Zielfunktion bepreist ist, sagt nichts darüber, ob sie eingehalten wurde.

3 — (c) hierarchisch lockern. INFEASIBLE sagt nur, dass ein Widerspruch existiert, nicht welche Regeln ihn erzeugen. Ersetzt man harte Verbote durch sehr teure Strafkosten, liefert der Solver wieder eine Lösung — und die verletzten Regeln stehen benannt in der Kostenzerlegung. Genau das tut Infeasibility_Diagnose.py. (a) hilft nicht: INFEASIBLE ist ein Beweis, kein Abbruch. (b) verschiebt das Problem und verliert die Gelegenheit, die Ursache zu finden, solange sie noch frisch ist.

Selbsttest

1. Durch hierarchische Relaxation: Schlupfvariablen mit hohen, gestaffelten Strafkosten für die verletzbaren Bedingungen.
2. Warum diese Lösung? Warum nicht die Alternative? Was würde sie verbessern?
3. Weil die Datenunsicherheit (oft ±10 %) die verbleibende Optimalitätslücke bei Weitem übersteigt.
4. Jeder Lauf arbeitet auf einem unveränderlichen, mit ID versehenen Datenstand — nur so sind Ergebnisse reproduzierbar und belegbar.
5. Die Einführung: mangelnde Akzeptanz, weil Ergebnisse nicht nachvollziehbar sind.
6. Sie berührt den Plan, ohne ihn zu verteuern — die Lösung liegt genau auf ihrer Grenze, wäre aber auch ohne sie dieselbe (Entartung). Für eine Nachverhandlung folgt: nichts tun. Der Aufwand brächte 0 €. „Bindend” ist ein geometrischer, „teuer” ein wirtschaftlicher Befund.
7. Weil der Schattenpreis nur für die nächste Einheit gilt und sein Gültigkeitsbereich endet, sobald ein anderer Engpass bindend wird. Realistische Lockerungen sind unterschiedlich groß — eine Sonderschicht bringt 50 Einheiten, ein nachverhandelter Vertrag 10. Der Preis je Einheit sagt daher nichts darüber, welcher Hebel insgesamt am meisten bringt; dafür muss man die Lockerung rechnen, nicht den Preis multiplizieren.

Zurück zum Wegweiser oder weiter zu [Anhang B](anhang-modellierungsmuster.html#anhang-modellierungsmuster) — Modellierungsmuster

A.23 Lösungen zu Kapitel „Testen, Messen, Ausliefern“

23.1 — Den Schnellstart reparieren. Zwei Wege: (a) Abrunden statt runden — np.floor statt np.round. Das ist immer zulässig, weil weniger produzieren nie eine Kapazität sprengt, kostet aber Deckungsbeitrag und ist im Allgemeinen nicht die optimale ganzzahlige Lösung. (b) Ganzzahlig modellieren — linprog(..., integrality=1) bzw. IntVar. Das ist der richtige Weg.

Warum das ein eigenes Kapitel wert ist (Kapitel 6): Runden ist nicht nur ungenau, sondern kann beliebig danebenliegen. Es gibt Instanzen, bei denen die gerundete LP-Lösung nicht nur suboptimal, sondern unzulässig ist — genau das zeigt der Schnellstart — und andere, bei denen zwischen gerundetem LP und echtem Optimum Welten liegen (Runden_Gegenbeispiel.py).

23.2 — Eine Invariante mehr.

def test_kapazitaeten_verdoppeln(bauer):
    problem = schreinerei()
    doppelt = Produktionsproblem(
        produkte=problem.produkte,
        kapazitaeten={r: 2 * k for r, k in problem.kapazitaeten.items()})
    basis, gross = bauer(problem), bauer(doppelt)
    assert gross.zielwert == pytest.approx(2 * basis.zielwert, rel=1e-9)

Bei einem LP gilt das exakt: Der zulässige Bereich wird um den Faktor 2 gestreckt, und weil die Zielfunktion linear ist, skaliert das Optimum mit. Bei einem MILP gilt es nicht: Die Ganzzahligkeitsbedingung skaliert nicht mit. Aus 30,67 wird beim Verdoppeln 61,33 — und ob dazwischen eine bessere ganzzahlige Lösung liegt, hängt vom Einzelfall ab. Der Test wäre dort also falsch.

23.3 — Eine eigene Mutation. Zwei lohnende Kandidaten:

("Kapazitaetspruefung mit falschem Vergleich",
 "if ist > grenze + toleranz:", "if ist < grenze - toleranz:"),
("Toleranz mit falschem Vorzeichen",
 "if (mengen < -toleranz).any():", "if (mengen < toleranz).any():"),

Die erste wird getötet (test_pruefung_findet_kapazitaetsverletzung). Die zweite ist interessanter: Sie macht die Prüfung strenger statt schwächer — eine Lösung mit einer Menge von exakt 0 würde als negativ beanstandet. Ob sie überlebt, hängt daran, ob die Suite eine Instanz enthält, in der ein Produkt mit Menge 0 vorkommt. In der Schreinerei ist das nicht der Fall — die Mutation überlebt also und zeigt eine echte Lücke: Es fehlt eine Testinstanz, in der ein Produkt nicht produziert wird.

23.4 — Der Benchmark mit MILP. Zu erwarten ist, dass sich die Reihenfolge ändert. Beim reinen LP entscheidet vor allem der Modellaufbau in Python; beim MILP verschiebt sich das Gewicht zum Lösen, und dort spielen die Branch-and-Bound-Heuristiken der Bibliotheken gegeneinander. Die Spalte „Anteil” sollte bei allen deutlich fallen — nicht weil der Aufbau schneller würde, sondern weil das Lösen langsamer wird. Genau deshalb steht im Kapitel, dass die Tabelle nichts über MILPs sagt.

23.5 — Der Dienst mit Zeitlimit. Der Modellbauer in or_kern.py nimmt bisher kein Zeitlimit entgegen — das ist der erste Schritt (bei GLOP solver.SetTimeLimit(millisekunden)). Danach im Arbeiter durchreichen und den Status auswerten: Liefert der Solver ZEITLIMIT, ist stand weiterhin gescheitert, aber mit einer anderen Begründung als bei UNZULAESSIG — der Unterschied zwischen „rechne länger” und „ändere das Modell” (Kapitel 6).

Für den Test braucht es eine Instanz, die das Limit reißt. Ein LP eignet sich schlecht dafür; nehmen Sie ein MILP mit einigen hundert Binärvariablen und ein Limit von 0,1 Sekunden.

Finde den Denkfehler — „Die Suite ist grün, das Modell stimmt”

Alle Prüfungen benutzen dieselbe falsche Zahl.

Die Abnahmeprüfung rechnet den Verbrauch mit problem.verbrauchsmatrix() nach — also mit denselben 0,4 Stunden, mit denen der Solver gerechnet hat. Der Plan ist bezogen auf die hinterlegten Daten vollkommen korrekt: Er hält jede Kapazität ein, der Zielwert passt zu den Mengen, jede Invariante gilt. Der Fehler steckt nicht im Modell, sondern in der Wirklichkeit dahinter.

Kein Test dieser Welt findet das, solange er aus derselben Datenquelle liest. Genau darauf weist der Schnellstart hin: Die Prüfung kommt aus einer anderen Richtung, aber nicht aus einer anderen Quelle.

Was geholfen hätte — drei Dinge, keines davon ein Unit-Test:

1. Plausibilitätsgrenzen auf den Stammdaten. „Lackierzeit je Stück zwischen 0,5 und 20 Stunden” ist eine fachliche Aussage, die man in das Pydantic-Modell schreiben kann. 0,4 wäre beim Einlesen aufgeflogen — dieselbe Idee wie die Kapazitätsprüfung PositiveZahl, nur mit fachlichen statt technischen Grenzen.
2. Abgleich von Plan und Wirklichkeit. Der geplante Lackierverbrauch gegen den tatsächlich gebuchten aus der Betriebsdatenerfassung, einmal pro Woche. Eine systematische Abweichung um den Faktor 10 fällt in der ersten Woche auf. Das ist die Überwachung aus Kapitel 22, angewandt auf die Eingabe statt auf den Solver.
3. Vieraugenprinzip bei Stammdatenänderungen. Unspektakulär und wirksam.

🎯 Die allgemeine Lehre Tests prüfen die Übereinstimmung von Code und Absicht. Ob die Daten stimmen, ist eine andere Frage, und sie wird nicht im Testrahmen beantwortet, sondern durch Plausibilitäts- grenzen beim Einlesen und durch den Abgleich mit der Wirklichkeit im Betrieb.

Micro-Quiz

1. b) Es gibt keine unabhängige Quelle für die richtige Antwort — sonst bräuchte man den Solver nicht. (a) ist bei festgelegtem Seed und Zeitlimit meist beherrschbar; (c) löst man mit pytest.approx, das ist kein grundsätzliches Hindernis.

2. b) Überlebt heißt: Die Suite bleibt grün, obwohl der Code jetzt falsch ist. Sie hätte diesen Fehler durchgehen lassen. (a) verwechselt „von den Tests nicht bemerkt” mit „harmlos” — die beiden Überlebenden im Kapitel waren gerade nicht harmlos.

3. b) Gut drei Viertel der Zeit gehen in den Modellaufbau in Python. Ein schnellerer Solver würde am verbleibenden Viertel ansetzen. (a) ist der naheliegende Fehlschluss: Gemessen wurde nicht der Solver, sondern die Bindung davor.

Selbsttest

1. Eigenschaften (Kapazitäten eingehalten), Invarianten (Produktreihenfolge ändert nichts), Regression (die Schreinerei mit 10 800 €), Fehlerfälle (die Prüfung schlägt bei einer kaputten Lösung an).
2. Weil ein Test, der nur GLOP sieht, nicht unterscheiden kann, ob eine Eigenschaft vom Modell oder von der Bibliothek kommt. Läuft er über beide, muss die Aussage im Modell liegen.
3. „Grün” heißt nur, dass kein Test fehlgeschlagen ist — das gilt auch für eine Suite aus lauter assert True. „Prüft etwas” heißt, dass die Tests bei einem eingebauten Fehler rot würden; genau das misst der Mutationstest.
4. Weil sonst nicht erkennbar ist, welche Hälfte die Zeit kostet. Im Kapitel gehen bei OR-Tools 78 % in den Aufbau — wer nur die Gesamtzeit sieht, wechselt den Solver und ändert damit fast nichts.
5. Weil die Rechnung Sekunden bis Minuten dauert. Eine synchrone Antwort läuft in den Timeout des Reverse Proxy und blockiert währenddessen einen Arbeiter. 202 heißt „angenommen, noch nicht fertig” — genau die richtige Aussage.
6. Ein Threadpool genügt, wenn der Solver den GIL freigibt — das tun die C++-Bibliotheken (OR-Tools, HiGHS) während Solve(), im Kapitel mit Faktor 3,5 bei vier Threads gemessen. Eine in reinem Python geschriebene Heuristik hält den GIL; für sie braucht es Prozesse.