Teil I: Grundlagen des Operations Research

Kapitel 1: Einführung in Operations Research — Vom Ursprung zur mathematischen Entscheidungsfindung

1.1 In 5 Minuten gelöst

Bevor wir über Theorie sprechen, lösen Sie ein echtes Problem. Kopieren Sie den folgenden Block, führen Sie ihn aus, sehen Sie das Ergebnis — die Erklärung kommt danach.

Und jetzt der Punkt, auf den es ankommt. Fragen Sie sich ehrlich: Was hätten Sie geantwortet? Die naheliegende Antwort lautet „möglichst viele Tische“ — der Tisch bringt mit 240 € schließlich den vierfachen Deckungsbeitrag eines Stuhls. Rechnen wir das durch:

Das Bauchgefühl kostet 1 200 € pro Woche, rund 62 000 € im Jahr — bei einem Problem mit sage und schreibe zwei Produkten und zwei Ressourcen. Genau das ist Operations Research: nicht das Ausrechnen von Zahlen, die man ohnehin kennt, sondern das Auffinden von Entscheidungen, auf die man von allein nicht kommt.

Warum funktioniert das? Der Solver macht sich zunutze, dass keines der beiden Produkte in beiden Ressourcen das bessere ist. Pro Montagestunde bringt der Tisch 80 €, der Stuhl nur 60 € — pro Quadratmeter Plattenmaterial dagegen bringt der Stuhl 60 €, der Tisch nur 40 €. Wo kein Produkt durchgehend gewinnt, gibt es eine Mischung, die beide Engpässe gleichzeitig ausschöpft. Diese Mischung von Hand zu finden ist schon bei zwei Produkten mühsam und bei zwanzig unmöglich. Wie der Solver sie findet, zeigt Kapitel 5; was die einzelnen Zeilen des Programms bedeuten, klärt der Rest dieses Kapitels.

1.2 Lernziele

Nach diesem Kapitel können Sie …

1. … in eigenen Worten erklären, wodurch sich Operations Research von Business Intelligence und maschinellem Lernen unterscheidet.
2. … abschätzen, ab welcher Problemgröße vollständiges Durchprobieren scheitert — und diese Abschätzung selbst rechnen.
3. … die vier Bausteine eines Modells benennen und einem konkreten Problem zuordnen.
4. … entscheiden, ob eine Bedingung eine harte oder eine weiche Nebenbedingung ist.
5. … ein einfaches Modell mit Google OR-Tools aufschreiben, lösen und das Ergebnis interpretieren.

1.3 Was ist Operations Research wirklich?

Im Alltag lösen wir Probleme intuitiv: durch Ausprobieren, Daumenregeln, Erfahrung. Das funktioniert erstaunlich gut — bis eine bestimmte Schwelle überschritten wird. Dann bricht die Intuition nicht langsam ein, sondern schlagartig zusammen.

Drei Beispiele:

• Ein Disponent soll 40 Lastwagen auf 300 Lieferorte verteilen. Es gibt mehr mögliche Routenkombinationen als Atome im bekannten Universum: 300! \approx 3{,}06 \times 10^{614}.
• Eine Klinik muss 200 Pflegekräfte einteilen — unter Berücksichtigung von 15 gesetzlichen Arbeitszeitregeln, Urlaubsanträgen, Qualifikationsstufen und Notfallreserven.
• Ein Fondsmanager muss 10 Millionen Euro so auf 50 Aktien aufteilen, dass bei einer erwarteten Mindestrendite von 8 % das Verlustrisiko im schlechtesten Marktszenario minimal bleibt.

Ein naiver Ansatz — Brute Force, das vollständige Durchrechnen aller Möglichkeiten — würde selbst auf den schnellsten Supercomputern der Welt Milliarden Jahre dauern.

📖 Definition: Operations Research

Operations Research (OR), deutsch etwa Unternehmensforschung oder mathematische Entscheidungsoptimierung, ist die wissenschaftliche Disziplin, reale Entscheidungsprobleme in formale mathematische Modelle zu überführen und mithilfe exakter oder heuristischer Algorithmen (Solver) die beweisbar beste (optimale) oder eine messbar hochwertige Lösung zu finden.

Die drei Stufen der Analytik

OR beantwortet nicht die beschreibende Frage „Was ist passiert?“ und nicht die vorhersagende Frage „Was wird passieren?“, sondern die vorschreibende (präskriptive) Kernfrage:

\textbf{„Was ist unter den gegebenen Bedingungen die beste Handlung?“}

Die Stufen bauen aufeinander auf, ersetzen einander aber nicht. Eine Umsatzprognose sagt Ihnen, dass die Nachfrage im März um 20 % steigt. Sie sagt Ihnen nicht, welche der sieben Maschinen Sie dafür wann mit welchem Auftrag belegen sollen. Genau dort beginnt OR — und deshalb ist eine Prognose in diesem Buch fast immer nur eine Eingangsgröße des Modells, nie sein Ergebnis.

🎯 Merksatz Maschinelles Lernen sagt Ihnen, was kommt. Operations Research sagt Ihnen, was Sie deswegen tun sollen.

1.4 Warum Ausprobieren scheitert — mit eigener Rechnung

Die Behauptung „vollständiges Durchprobieren ist unmöglich“ wird oft aufgestellt und selten belegt. Rechnen wir sie einmal selbst nach — das Ergebnis prägt sich besser ein als jede Zahl im Text.

✏️ Handrechnung 1.1: Wie schnell wächst „alle Möglichkeiten“?

Angenommen, Sie sollen n Aufträge in eine Reihenfolge bringen. Für den ersten Platz haben Sie n Kandidaten, für den zweiten n-1, für den dritten n-2 und so fort. Die Gesamtzahl der Reihenfolgen ist damit die Fakultät:

n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1

Nehmen wir großzügig an, ein Rechner prüfe eine Milliarde (10^9) Reihenfolgen pro Sekunde. Wie lange dauert es?

n	n!	Rechenzeit bei 10^9 Prüfungen/s
5	120	unmessbar kurz
10	3 628 800	0,004 Sekunden
15	1{,}3 \times 10^{12}	22 Minuten
20	2{,}4 \times 10^{18}	77 Jahre
25	1{,}6 \times 10^{25}	490 Millionen Jahre
30	2{,}7 \times 10^{32}	8{,}4 \times 10^{15} Jahre

Der springende Punkt: Zwischen n = 15 (22 Minuten, machbar) und n = 20 (77 Jahre, hoffnungslos) liegen nur fünf zusätzliche Aufträge. Es gibt keine sanfte Verschlechterung — es gibt eine Wand.

Und die Rechnung ist noch geschönt: Ein schnellerer Rechner hilft praktisch nicht. Selbst eine Beschleunigung um den Faktor eine Million verschiebt die Grenze von n=20 nur auf etwa n=24. Gegen kombinatorisches Wachstum ist Hardware machtlos.

Das folgende Programm macht diesen Effekt erfahrbar. Es löst dasselbe Zuordnungsproblem zweimal — einmal durch vollständiges Durchprobieren, einmal mit einem OR-Solver — und vergleicht die Laufzeiten.

#!/usr/bin/env python3

# Brute_Force_Vergleich.py
"""
Kapitel Einfuehrung: Warum Ausprobieren scheitert.
Vergleicht vollständige Enumeration mit einem Constraint-Solver an einem
Zuordnungsproblem wachsender Größe (n Mitarbeiter auf n Aufgaben).
"""

import itertools
import math
import time

import numpy as np
from ortools.sat.python import cp_model


def erzeuge_kostenmatrix(n: int, seed: int = 7) -> np.ndarray:
    """Zufällige, aber reproduzierbare Kosten: Wer bearbeitet welche Aufgabe wie teuer?"""
    rng = np.random.default_rng(seed)
    return rng.integers(low=10, high=100, size=(n, n))


def loese_brute_force(kosten: np.ndarray) -> tuple[float, tuple, int]:
    """
    Probiert ALLE n! Zuordnungen durch und behält die beste.
    Rückgabe: (bester Kostenwert, beste Permutation, Anzahl geprüfter Kombinationen)
    """
    n = len(kosten)
    bester_wert = math.inf
    beste_zuordnung = None
    geprueft = 0

    # itertools.permutations(range(n)) liefert nacheinander jede Reihenfolge
    for zuordnung in itertools.permutations(range(n)):
        # zuordnung[i] = Aufgabe, die Mitarbeiter i übernimmt
        wert = sum(kosten[i][zuordnung[i]] for i in range(n))
        geprueft += 1
        if wert < bester_wert:
            bester_wert = wert
            beste_zuordnung = zuordnung

    return bester_wert, beste_zuordnung, geprueft


def loese_mit_solver(kosten: np.ndarray) -> tuple[float, tuple]:
    """Dasselbe Problem als Constraint-Programm — der Solver probiert NICHT alles durch."""
    n = len(kosten)
    modell = cp_model.CpModel()

    # x[i][j] = 1  <=>  Mitarbeiter i übernimmt Aufgabe j
    x = [[modell.NewBoolVar(f"x_{i}_{j}") for j in range(n)] for i in range(n)]

    for i in range(n):
        modell.AddExactlyOne(x[i][j] for j in range(n))   # jeder genau eine Aufgabe
    for j in range(n):
        modell.AddExactlyOne(x[i][j] for i in range(n))   # jede Aufgabe genau einmal

    modell.Minimize(sum(int(kosten[i][j]) * x[i][j] for i in range(n) for j in range(n)))

    loeser = cp_model.CpSolver()
    loeser.parameters.max_time_in_seconds = 30.0
    status = loeser.Solve(modell)
    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        raise RuntimeError("Solver fand keine Lösung.")

    zuordnung = tuple(
        next(j for j in range(n) if loeser.Value(x[i][j]) == 1) for i in range(n)
    )
    return loeser.ObjectiveValue(), zuordnung


if __name__ == "__main__":
    print("=" * 72)
    print("   VOLLSTÄNDIGES DURCHPROBIEREN  vs.  OPERATIONS RESEARCH")
    print("=" * 72)
    print(f"{'n':>3} | {'Kombinationen':>18} | {'Brute Force':>14} | {'Solver':>10} | gleich?")
    print("-" * 72)

    for n in [4, 6, 8, 9, 10]:      # n = 11 dauert bereits ~2 Minuten
        kosten = erzeuge_kostenmatrix(n)

        t0 = time.perf_counter()
        wert_bf, zuord_bf, geprueft = loese_brute_force(kosten)
        zeit_bf = time.perf_counter() - t0

        t0 = time.perf_counter()
        wert_or, zuord_or = loese_mit_solver(kosten)
        zeit_or = time.perf_counter() - t0

        gleich = "ja" if abs(wert_bf - wert_or) < 1e-9 else "NEIN!"
        print(f"{n:>3} | {geprueft:>18,} | {zeit_bf:>11.4f} s | {zeit_or:>7.4f} s | {gleich}")

    print("-" * 72)
    # Hochrechnung: Wie lange bräuchte Brute Force bei n = 20?
    kombis_20 = math.factorial(20)
    # Messbasis: Prüfungen pro Sekunde aus dem letzten Lauf schätzen
    pro_sekunde = geprueft / max(zeit_bf, 1e-9)
    jahre = kombis_20 / pro_sekunde / (60 * 60 * 24 * 365.25)
    print(f"Hochrechnung für n = 20: {kombis_20:,} Kombinationen")
    print(f"Bei gemessenen {pro_sekunde:,.0f} Prüfungen/s wären das {jahre:,.0f} Jahre.")
    print("Der Solver löst dieselbe Instanz in Sekundenbruchteilen.")
    print("=" * 72)

Erwartete Ausgabe (Zeiten hardwareabhängig):

========================================================================
   VOLLSTÄNDIGES DURCHPROBIEREN  vs.  OPERATIONS RESEARCH
========================================================================
  n |      Kombinationen |    Brute Force |     Solver | gleich?
------------------------------------------------------------------------
  4 |                 24 |      0.0001 s |  0.0408 s | ja
  6 |                720 |      0.0021 s |  0.0067 s | ja
  8 |             40,320 |      0.1088 s |  0.0088 s | ja
  9 |            362,880 |      1.0596 s |  0.0120 s | ja
 10 |          3,628,800 |     12.0897 s |  0.0252 s | ja
------------------------------------------------------------------------
Hochrechnung für n = 20: 2,432,902,008,176,640,000 Kombinationen
Bei gemessenen 300,157 Prüfungen/s wären das 256,845 Jahre.
Der Solver löst dieselbe Instanz in Sekundenbruchteilen.
========================================================================

Lesen Sie die Tabelle von oben nach unten: Bei n = 4 ist das Durchprobieren noch 400-mal schneller als der Solver — der Solveraufruf hat einen festen Startaufwand von einigen Millisekunden, der sich bei winzigen Problemen nicht lohnt. Ab n = 8 kippt das Verhältnis, und ab n = 10 ist der Solver bereits 480-mal schneller. Entscheidend ist nicht der Faktor, sondern die Richtung: Die Brute-Force-Zeit verzehnfacht sich mit jedem zusätzlichen Element, die Solver-Zeit wächst kaum merklich.

💻 Code-Durchgang

Zeile / Stelle	Was passiert	Warum
itertools.permutations(range(n))	erzeugt nacheinander alle n! Reihenfolgen	die Definition von „alles durchprobieren“
wert = sum(kosten[i][zuordnung[i]] ...)	bewertet eine einzelne Kombination	das ist die Zielfunktion, nur eben von Hand ausgewertet
modell.NewBoolVar(...)	legt eine Ja/Nein-Entscheidungsvariable an	n^2 Variablen statt n! Kombinationen
modell.AddExactlyOne(...)	„genau eine davon ist wahr“	die Nebenbedingungen
modell.Minimize(...)	die zu minimierende Summe	die Zielfunktion, jetzt deklariert statt ausgerechnet
loeser.Solve(modell)	der Solver sucht — aber nicht stur	er nutzt Struktur (Schranken, Propagation), statt abzuzählen

Die entscheidende Beobachtung: Beide Programme liefern denselben Zielwert (Spalte „gleich?“). Der Solver rät also nicht und liefert keine Näherung — er findet dasselbe beweisbare Optimum, nur ohne alles anzusehen.

⚠️ Typische Fehler

• „Dann nehme ich eben eine schnellere Sprache.“ C++ ist etwa 50-mal schneller als Python. Bei n=20 verkürzt das 157 Millionen Jahre auf 3 Millionen Jahre. Das Problem ist nicht die Sprache, sondern der Ansatz.
• „Ich probiere nur die plausiblen Kombinationen.“ Genau das tut ein Solver — nur systematisch, mit einem Beweis, dass die weggelassenen Zweige nichts Besseres enthalten. Eine handgestrickte Auswahl hat diesen Beweis nicht.

1.5 Historischer Kontext und Evolution

Der Begriff entstand im Vorfeld des Zweiten Weltkriegs in Großbritannien. Militärische Führungsstäbe standen vor neuartigen logistischen und strategischen Fragen: Wie platziert man die neu entwickelten Radaranlagen an der Küste optimal? Wie groß müssen Schiffskonvois sein, um U-Boot-Angriffe bei minimalem Geleitschutzaufwand abzuwehren?

Wissenschaftler wie George Dantzig, Patrick Blackett und John von Neumann entwickelten daraufhin mathematische Formalismen. 1947 erfand George Dantzig den Simplex-Algorithmus zur Lösung linearer Programme — ein Durchbruch, der die industrielle Planung in den 1950er-Jahren revolutionierte und den wir in Kapitel 5 selbst programmieren werden.

Heute treibt OR die Kernsysteme moderner Industrien an:

• Tech-Konzerne: Server-Scheduling, Datenrouting in Glasfasernetzen, Werbeplatzierungsauktionen.
• Luftfahrt & Logistik: Crew-Scheduling, Flugzeugumlaufplanung, Paketlogistik (etwa das System ORION von UPS, das durch Routenoptimierung jährlich zweistellige Millionenbeträge an Treibstoff einspart).
• Energie: Kraftwerkseinsatzplanung, Netzausbau, Speicherbewirtschaftung.
• Gesundheitswesen: OP-Saal-Belegung, Dienstpläne, Rettungsmittel-Standorte.
• Finanzindustrie: Arbitrage-Freiheit, Portfolio-Optimierung, Liquiditäts- und Orderausführungsmanagement — der Gegenstand von Teil IV dieses Buches.

1.6 Die vier universellen Bausteine jedes OR-Problems

Dies ist der wichtigste Abschnitt des Kapitels. Jedes Optimierungsproblem der Welt lässt sich — unabhängig von der Branche — auf vier Elemente reduzieren. Wenn Sie später vor einem neuen Problem sitzen, ist dies Ihre Checkliste.

Baustein 1 — Entscheidungsvariablen (x)

Die Stellschrauben des Modells: Werte, die der Algorithmus aktiv festlegen darf.

Die Leitfrage: Worüber darf ich überhaupt entscheiden? Alles, was feststeht, ist kein Variable, sondern Parameter. Die häufigste Ursache für unbrauchbare Modelle ist eine falsch gewählte Variablendefinition — nicht ein falscher Solver.

Baustein 2 — Parameter / Eingabedaten (c, A, b)

Die unveränderlichen Fakten der Realität: historische Renditen, Maschinenstundensätze, Lagerkapazitäten, Steuerquoten, Entfernungen, Qualifikationen.

Die Leitfrage: Was ist gegeben und wird nicht entschieden? Parameter sind der Ort, an dem Datenqualität über Modellqualität entscheidet. Kapitel 18 zeigt am Beispiel der Kovarianzmatrix, wie ein schlecht geschätzter Parameter ein mathematisch perfektes Modell wertlos macht.

Baustein 3 — Zielfunktion (f(x))

Ein mathematischer Ausdruck, der die Güte einer Lösung zu einer einzigen Zahl verdichtet:

\min_{x} f(x) \qquad \text{oder} \qquad \max_{x} f(x)

📐 Formel-Lesehilfe

• f(x) — die Bewertungsfunktion: „Wie gut ist die Lösung x?“
• \min_x — „wähle dasjenige x, das f so klein wie möglich macht“
• Das x unter dem \min sagt, worüber minimiert wird (über die Variablen, nicht etwa über die Parameter).

Ohne Formel gesagt: Von allen erlaubten Handlungsmöglichkeiten suchen wir diejenige mit den geringsten Kosten (bzw. dem höchsten Gewinn).

Die Leitfrage: Was genau soll besser werden — und in welcher Einheit? Wenn Sie die Einheit nicht nennen können (Euro, Minuten, Strafpunkte), ist die Zielfunktion noch nicht fertig. Mehrere gleichzeitige Ziele müssen entweder gewichtet in eine Zahl überführt oder hierarchisch nacheinander optimiert werden.

Baustein 4 — Nebenbedingungen (Constraints)

Regeln, die den Raum der erlaubten Lösungen einschränken:

g_i(\mathbf{x}) \le b_i \qquad \text{bzw.} \qquad h_j(\mathbf{x}) = 0

Harte Nebenbedingungen (hard constraints) sind zwingend: gesetzliche Ruhezeit \ge 11 Stunden, Summe der Portfoliogewichte = 100\,\%, maximales Verlustrisiko \le 5\,\%. Wird eine einzige harte Bedingung verletzt, ist die Lösung mathematisch unzulässig (infeasible) — sie existiert für den Solver schlicht nicht.

Weiche Nebenbedingungen (soft constraints) sind Wünsche: Mitarbeiterpräferenzen, möglichst wenig Umschichtung, gleichmäßige Lastverteilung. Sie werden über Strafkosten (penalties) in die Zielfunktion integriert und dürfen im Notfall verletzt werden — es kostet dann eben.

🎯 Merksatz Harte Bedingung = „darf nicht“. Weiche Bedingung = „soll möglichst nicht, sonst kostet es X“. Die Entscheidung zwischen beiden ist eine der folgenreichsten im ganzen Modell: Zu viele harte Bedingungen erzeugen unlösbare Modelle (Kapitel 22), zu wenige erzeugen Lösungen, die niemand akzeptiert.

Die vier Bausteine als eine Formel

Setzt man die vier Bausteine zusammen, entsteht die Standardform, in der Ihnen jedes Optimierungsmodell dieses Buches begegnen wird. Sie sieht auf den ersten Blick sperrig aus — deshalb steht daneben, was jede Zeile in Alltagssprache bedeutet.

\max_{\mathbf{x}}\ \sum_{j=1}^{n} c_j x_j \qquad \text{u. d. N.} \qquad \sum_{j=1}^{n} a_{ij} x_j \le b_i \quad \forall i = 1,\dots,m, \qquad x_j \ge 0

Das \forall („für alle“) ist dabei das Zeichen mit der größten praktischen Wirkung: Es verwandelt eine Zeile Mathematik in eine for-Schleife und damit in beliebig viele Nebenbedingungen. Im Schreinerei-Programm oben steckt es in den zwei s.Add(...)-Zeilen — bei 40 Ressourcen wären es 40, geschrieben in derselben einen Schleife.

Die Bausteine in der Praxis: eine Vorlage

Damit die Zerlegung zur Gewohnheit wird, hier eine Vorlage, die Sie bei jedem neuen Problem ausfüllen können — vor der ersten Codezeile.

✏️ Handrechnung 1.2: Zerlegen Sie dieses Problem

Eine Bäckerei backt Brot und Brötchen. Ein Brot bringt 2,50 € Deckungsbeitrag und braucht 0,5 kg Mehl und 4 Minuten Ofenzeit; 10 Brötchen bringen 3,00 € und brauchen 0,6 kg Mehl und 3 Minuten Ofenzeit. Verfügbar sind 90 kg Mehl und 600 Minuten Ofenzeit. Aus Vertragsgründen müssen mindestens 40 Brote gebacken werden.

Füllen Sie die Vorlage aus, bevor Sie weiterlesen. — Auflösung:

• Variablen: x_1 = Anzahl Brote, x_2 = Anzahl Brötchen-Zehnerpackungen; beide ganzzahlig \ge 0.
• Parameter: Deckungsbeiträge (2{,}50;\ 3{,}00); Mehlbedarf (0{,}5;\ 0{,}6); Ofenzeit (4;\ 3); Kapazitäten (90;\ 600); Mindestmenge 40.
• Zielfunktion: \max\ 2{,}5x_1 + 3{,}0x_2 (Einheit: Euro).
• Harte Bedingungen: 0{,}5x_1 + 0{,}6x_2 \le 90 (Mehl); 4x_1 + 3x_2 \le 600 (Ofen); x_1 \ge 40 (Vertrag).
• Weiche Bedingungen: keine.

Dieses Problem lösen Sie in der Aufgabe Die Bäckerei programmieren (Abschnitt 1.9) selbst.

Die Vorlage lässt sich fast wörtlich in Code übersetzen — wer die fünf Zeilen ausgefüllt hat, hat den größten Teil der Modellierungsarbeit schon erledigt:

#!/usr/bin/env python3

# Bausteine_Vorlage.py
"""
Kapitel Einfuehrung: Die Bausteine-Vorlage als ausfuellbares Python-Geruest.

Uebersetzt die Vier-Bausteine-Vorlage aus dem Abschnitt 'Die vier
universellen Bausteine jedes OR-Problems' direkt in Code: Wer sie
auf Papier ausgefuellt hat, kann sie fast unveraendert in ein loesbares
Modell umsetzen. Angewendet auf das Baeckerei-Beispiel der Handrechnung.
"""

from dataclasses import dataclass
from ortools.sat.python import cp_model


@dataclass
class Bausteine:
    """Die vier Bausteine jedes OR-Problems - wortwoertlich aus der Vorlage
    im Abschnitt 'Die vier universellen Bausteine' uebernommen."""
    variablen: str
    parameter: str
    zielfunktion: str
    harte_bedingungen: str
    weiche_bedingungen: str

    def zeige(self) -> None:
        print("=" * 78)
        print("  AUSGEFUELLTE BAUSTEINE-VORLAGE")
        print("=" * 78)
        for feld, wert in [
            ("Entscheidungsvariablen", self.variablen),
            ("Parameter", self.parameter),
            ("Zielfunktion", self.zielfunktion),
            ("Harte Bedingungen", self.harte_bedingungen),
            ("Weiche Bedingungen", self.weiche_bedingungen),
        ]:
            print(f"{feld:<24}: {wert}")
        print("=" * 78)


# --- Baeckerei-Beispiel aus der Handrechnung ---------------------------------
VORLAGE = Bausteine(
    variablen="x1 = Anzahl Brote, x2 = Anzahl Broetchen-Zehnerpackungen "
              "(beide ganzzahlig >= 0)",
    parameter="Deckungsbeitraege (2,50; 3,00) EUR; Mehlbedarf (0,5; 0,6) kg; "
              "Ofenzeit (4; 3) min; Kapazitaeten (90 kg, 600 min); Mindestmenge 40 Brote",
    zielfunktion="max 2,5*x1 + 3,0*x2  (Einheit: Euro Deckungsbeitrag)",
    harte_bedingungen="0,5*x1 + 0,6*x2 <= 90 (Mehl); 4*x1 + 3*x2 <= 600 (Ofen); "
                      "x1 >= 40 (Vertrag)",
    weiche_bedingungen="keine",
)


def loese_baeckerei():
    """Baut aus der ausgefuellten Vorlage mechanisch ein CP-SAT-Modell."""
    modell = cp_model.CpModel()
    x1 = modell.NewIntVar(40, 1000, "Brote")            # Vertrag: mindestens 40
    x2 = modell.NewIntVar(0, 1000, "Broetchen_Zehner")

    modell.Add(5 * x1 + 6 * x2 <= 900)      # Mehl, x10 fuer Ganzzahligkeit
    modell.Add(4 * x1 + 3 * x2 <= 600)      # Ofenzeit

    modell.Maximize(25 * x1 + 30 * x2)      # Deckungsbeitrag x10

    loeser = cp_model.CpSolver()
    status = loeser.Solve(modell)
    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        raise SystemExit(f"Keine Loesung: {loeser.StatusName(status)}")
    return loeser.Value(x1), loeser.Value(x2), loeser.ObjectiveValue() / 10


if __name__ == "__main__":
    VORLAGE.zeige()

    print("\n--- Aus der Vorlage mechanisch abgeleitetes Modell ---")
    brote, broetchen, gewinn = loese_baeckerei()
    print(f"Optimale Brote:              {brote}")
    print(f"Optimale Broetchen-Zehner:   {broetchen}")
    print(f"Maximaler Deckungsbeitrag:   {gewinn:.2f} EUR")
    print()
    print("Genau diese drei Codezeilen (Variablen, Add, Maximize) entstehen")
    print("direkt aus den fuenf Zeilen der Vorlage - das ist der ganze Trick.")

Erwartete Ausgabe:

==============================================================================
  AUSGEFUELLTE BAUSTEINE-VORLAGE
==============================================================================
Entscheidungsvariablen  : x1 = Anzahl Brote, x2 = Anzahl Broetchen-Zehnerpackungen (beide ganzzahlig >= 0)
Parameter               : Deckungsbeitraege (2,50; 3,00) EUR; Mehlbedarf (0,5; 0,6) kg; Ofenzeit (4; 3) min; Kapazitaeten (90 kg, 600 min); Mindestmenge 40 Brote
Zielfunktion            : max 2,5*x1 + 3,0*x2  (Einheit: Euro Deckungsbeitrag)
Harte Bedingungen       : 0,5*x1 + 0,6*x2 <= 90 (Mehl); 4*x1 + 3*x2 <= 600 (Ofen); x1 >= 40 (Vertrag)
Weiche Bedingungen      : keine
==============================================================================

--- Aus der Vorlage mechanisch abgeleitetes Modell ---
Optimale Brote:              42
Optimale Broetchen-Zehner:   115
Maximaler Deckungsbeitrag:   450.00 EUR

Genau diese drei Codezeilen (Variablen, Add, Maximize) entstehen
direkt aus den fuenf Zeilen der Vorlage - das ist der ganze Trick.

Mehl und Deckungsbeitrag stehen im selben Verhältnis für Brote wie für Brötchen (je 5 € pro kg Mehl) — deshalb ist die Aufteilung zwischen 42/115 nicht eindeutig, solange die 90 kg Mehl restlos verplant sind und mindestens 40 Brote gebacken werden; der maximale Deckungsbeitrag von 450 € dagegen ist es.

1.7 Erstes Python-Vollbeispiel: Ressourcenallokation im Rechenzentrum

Szenario

Ein quantitatives Handelshaus betreibt Serverkapazitäten für zwei Algorithmentypen:

• Algorithmus A (Arbitrage-Bot): erzeugt 150\,\text{€} Gewinn pro Tag, benötigt 2 Rechenkerne (vCPUs) und 4\,\text{GB} Arbeitsspeicher.
• Algorithmus B (Trendfolge-Bot): erzeugt 250\,\text{€} Gewinn pro Tag, benötigt 5 Rechenkerne und 6\,\text{GB} Arbeitsspeicher.

Systemressourcen: höchstens 40 vCPUs, höchstens 60\,\text{GB} RAM, und aus Marktliquiditätsgründen höchstens 8 Arbitrage-Bots.

Frage: Wie viele Instanzen von A und B maximieren den Tagesgewinn?

Mathematische Formulierung

Entscheidungsvariablen:

x_A \in \mathbb{N}_0,\quad x_B \in \mathbb{N}_0

Zielfunktion:

\max_{x_A, x_B} \; Z = 150\,x_A + 250\,x_B

Nebenbedingungen:

\begin{aligned} 2x_A + 5x_B &\le 40 && \text{(vCPU-Limit)}\\ 4x_A + 6x_B &\le 60 && \text{(RAM-Limit)}\\ x_A &\le 8 && \text{(Marktliquidität)}\\ x_A,\, x_B &\ge 0,\ \text{ganzzahlig} \end{aligned}

📐 Formel-Lesehilfe

• x_A, x_B — Anzahl gestarteter Bots je Typ. Ganzzahlig, weil ein halber Bot nicht existiert.
• Z = 150x_A + 250x_B — der Tagesgewinn in Euro: pro Arbitrage-Bot 150 €, pro Trendfolge-Bot 250 €.
• 2x_A + 5x_B \le 40 — jeder A-Bot belegt 2 Kerne, jeder B-Bot 5; zusammen dürfen es höchstens 40 sein.

Ohne Formel gesagt: Starte so viele Bots wie möglich, aber verbrauche nicht mehr Rechenkerne und Arbeitsspeicher, als da sind — und nicht mehr als acht Arbitrage-Bots.

✏️ Handrechnung 1.3: Das Optimum zu Fuß finden

Bei nur zwei Variablen können wir die Kandidaten abgehen. Weil B mehr Gewinn bringt (250 € gegen 150 €), liegt die Vermutung nahe, möglichst viele B-Bots zu starten.

Kandidat (x_A, x_B)	vCPU 2x_A+5x_B \le 40	RAM 4x_A+6x_B \le 60	Z
(0, 8)	40 \le 40 ✓	48 \le 60 ✓	2000 €
(3, 6)	36 ✓	48 ✓	1950 €
(5, 6)	40 ✓	56 ✓	2250 €
(8, 4)	36 ✓	56 ✓	2200 €
(7, 5)	39 ✓	58 ✓	2300 €
(6, 6)	42 > 40 ✗	—	unzulässig
(8, 5)	41 > 40 ✗	—	unzulässig

Optimum: x_A^* = 7, x_B^* = 5, Z^* = 2300\,\text{€}.

Beachten Sie das Überraschende: Die naive Strategie „nur den lukrativeren Bot“ (0, 8) liefert 2000 € — ganze 300 € weniger als die Mischung. Genau solche Effekte machen Optimierung nötig: Der beste Gesamtplan besteht selten aus lauter lokal besten Einzelentscheidungen.

Umsetzung mit Google OR-Tools

#!/usr/bin/env python3

# Bot_Allokation.py
"""
Kapitel Einfuehrung: Erstes Optimierungsmodell mit Google OR-Tools (CP-SAT).
Problem: Server-Allokation für Trading-Bots.

Modell mit expliziter Nebenbedingung statt versteckter Variablengrenze,
vollständiger Statusauswertung und Ergebnisprüfung.
"""

from ortools.sat.python import cp_model

# --- Parameter (die "Fakten" des Problems) ---------------------------------
GEWINN_A, GEWINN_B = 150, 250      # Euro pro Bot und Tag
CPU_A, CPU_B = 2, 5                # vCPU-Bedarf je Bot
RAM_A, RAM_B = 4, 6                # GB Arbeitsspeicher je Bot
CPU_GESAMT, RAM_GESAMT = 40, 60    # verfügbare Kapazitäten
MAX_ARBITRAGE = 8                  # Marktliquiditätsgrenze


def loese_bot_allokation(zeitlimit_s: float = 10.0):
    """Baut das Modell, löst es und gibt eine Auswertung aus."""

    # 1. Modell instanziieren
    modell = cp_model.CpModel()

    # 2. Entscheidungsvariablen anlegen
    #    NewIntVar(untere_grenze, obere_grenze, name)
    #    Die obere Grenze ist bewusst großzügig; die echte Beschränkung
    #    formulieren wir unten als Nebenbedingung, damit das Modell die
    #    mathematische Formulierung 1:1 abbildet.
    x_a = modell.NewIntVar(0, 100, "Arbitrage_Bots")
    x_b = modell.NewIntVar(0, 100, "Trend_Bots")

    # 3. Nebenbedingungen definieren
    c_cpu = modell.Add(CPU_A * x_a + CPU_B * x_b <= CPU_GESAMT)      # vCPU-Limit
    c_ram = modell.Add(RAM_A * x_a + RAM_B * x_b <= RAM_GESAMT)      # RAM-Limit
    c_liq = modell.Add(x_a <= MAX_ARBITRAGE)                          # Marktliquidität

    # 4. Zielfunktion: Maximiere den Tagesgewinn
    modell.Maximize(GEWINN_A * x_a + GEWINN_B * x_b)

    # 5. Solver konfigurieren und ausführen
    loeser = cp_model.CpSolver()
    loeser.parameters.max_time_in_seconds = zeitlimit_s
    status = loeser.Solve(modell)

    # 6. Status auswerten -- IMMER alle Fälle behandeln
    status_text = loeser.StatusName(status)
    if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        print(f"Keine verwertbare Lösung. Solver-Status: {status_text}")
        if status == cp_model.INFEASIBLE:
            print("Das Modell ist unlösbar - die Bedingungen widersprechen sich.")
        return None

    a, b = loeser.Value(x_a), loeser.Value(x_b)
    gewinn = loeser.ObjectiveValue()

    # 7. Ergebnis ausgeben
    print("=" * 58)
    print("  OPTIMALE BOT-ALLOKATION")
    print("=" * 58)
    print(f"Solver-Status:         {status_text}"
          f"{'  (beweisbar optimal)' if status == cp_model.OPTIMAL else '  (zulässig, nicht bewiesen)'}")
    print(f"Arbitrage-Bots (x_A):  {a} Instanzen")
    print(f"Trendfolge-Bots (x_B): {b} Instanzen")
    print(f"Täglicher Max-Gewinn:  {gewinn:,.2f} EUR")

    genutzt_cpu = CPU_A * a + CPU_B * b
    genutzt_ram = RAM_A * a + RAM_B * b
    print("-" * 58)
    print(f"CPU-Auslastung:        {genutzt_cpu} / {CPU_GESAMT} vCPUs "
          f"({genutzt_cpu / CPU_GESAMT * 100:.1f} %)")
    print(f"RAM-Auslastung:        {genutzt_ram} / {RAM_GESAMT} GB "
          f"({genutzt_ram / RAM_GESAMT * 100:.1f} %)")
    print(f"Arbitrage-Limit:       {a} / {MAX_ARBITRAGE}")

    # 8. Selbstkontrolle: Sind wirklich alle Bedingungen eingehalten?
    assert genutzt_cpu <= CPU_GESAMT, "vCPU-Limit verletzt!"
    assert genutzt_ram <= RAM_GESAMT, "RAM-Limit verletzt!"
    assert a <= MAX_ARBITRAGE, "Arbitrage-Limit verletzt!"

    # 9. Zum Vergleich: die naive Strategie "nur der lukrativere Bot"
    naiv_b = min(CPU_GESAMT // CPU_B, RAM_GESAMT // RAM_B)
    naiv_gewinn = GEWINN_B * naiv_b
    print("-" * 58)
    print(f"Naive Strategie (nur Trendfolge): {naiv_b} Bots -> {naiv_gewinn:,.2f} EUR")
    print(f"Vorteil der Optimierung:          {gewinn - naiv_gewinn:,.2f} EUR pro Tag "
          f"({(gewinn / naiv_gewinn - 1) * 100:.1f} %)")
    print("=" * 58)
    return a, b, gewinn


if __name__ == "__main__":
    loese_bot_allokation()

Erwartete Ausgabe:

==========================================================
  OPTIMALE BOT-ALLOKATION
==========================================================
Solver-Status:         OPTIMAL  (beweisbar optimal)
Arbitrage-Bots (x_A):  7 Instanzen
Trendfolge-Bots (x_B): 5 Instanzen
Täglicher Max-Gewinn:  2,300.00 EUR
----------------------------------------------------------
CPU-Auslastung:        39 / 40 vCPUs (97.5 %)
RAM-Auslastung:        58 / 60 GB (96.7 %)
Arbitrage-Limit:       7 / 8
----------------------------------------------------------
Naive Strategie (nur Trendfolge): 8 Bots -> 2,000.00 EUR
Vorteil der Optimierung:          300.00 EUR pro Tag (15.0 %)
==========================================================

Das Ergebnis deckt sich mit der Handrechnung Das Optimum zu Fuß finden — ein gutes Zeichen. Prüfen Sie Solver-Ergebnisse wo immer möglich gegen eine unabhängige Rechnung, gerade am Anfang.

💻 Code-Durchgang

Stelle	Was passiert	Didaktischer Hinweis
Konstanten oben	alle Parameter an einer Stelle	Nie Zahlen im Modellcode verstreuen — sonst findet man sie beim Ändern nicht wieder
NewIntVar(0, 100, ...)	ganzzahlige Variable mit weiten Grenzen	Grenzen müssen endlich sein; 100 ist bewusst unkritisch groß
modell.Add(x_a <= MAX_ARBITRAGE)	Marktlimit als Nebenbedingung	Alternativ liesse sich dieses Limit auch in die Variablengrenze packen. Beides funktioniert — aber als Nebenbedingung bleibt das Modell zur mathematischen Formulierung deckungsgleich und man kann später den Schattenpreis abfragen
loeser.StatusName(status)	echter Status statt fester Text	Ein fest codierter Text wie „OPTIMAL“ würde unabhängig vom tatsächlichen Ergebnis ausgegeben — deshalb immer den echten Solver-Status auswerten
assert ...	Selbstkontrolle nach dem Lösen	Kostet nichts und fängt Modellierungsfehler, die der Solver nicht bemerken kann
Vergleich mit naiver Strategie	quantifiziert den Nutzen	Die Frage „Was bringt die Optimierung überhaupt?“ kommt in jedem Projekt — beantworten Sie sie ungefragt

⚠️ Typische Fehler

• Variablengrenzen zu eng gewählt. NewIntVar(0, 5, ...) würde hier stillschweigend die Lösung x_B = 5 erzwingen und ein falsches „Optimum“ liefern. Grenzen sind Nebenbedingungen — behandeln Sie sie als solche.
• Status nicht geprüft. Ein Programm, das bei INFEASIBLE weiterläuft und solver.Value(...) abfragt, liefert entweder Unsinn oder stürzt ab.
• Ganzzahligkeit vergessen. Mit kontinuierlichen Variablen liefert dasselbe Modell x_A = 7{,}5, x_B = 5{,}0 und Z = 2375 € — ein Wert, den es real nicht gibt. Warum man solche Werte nicht einfach runden darf, ist Thema von Kapitel 6.

📎 Warum dieses Programm alles selbst macht

Wenige Seiten weiter, in der Excel-Brücke, steht ein Programm, das mit 96 Zeilen auskommt, weil es die immer gleichen Arbeitsschritte aus dem gemeinsamen Modul or_kern.py bezieht (Abschnitt 22.6). Warum tut Bot_Allokation.py das nicht auch?

Weil es hier nicht darum geht, wenig Code zu schreiben, sondern darum zu sehen, wie ein Modell entsteht: Variablen, Nebenbedingungen, Zielfunktion, Status, Prüfung — jeder Schritt einzeln und sichtbar. Eine Abstraktion, die diese Schritte zusammenfasst, ist genau dann ein Gewinn, wenn man sie schon einmal von Hand gegangen ist; vorher versteckt sie nur, was man verstehen will.

Das ist eine allgemeine Regel für eigene Projekte: Erst die Wiederholung rechtfertigt die Abstraktion. Wer sein erstes Modell gleich als Framework baut, hat ein Framework für einen Fall — und die Erfahrung, welche Fälle es tragen müsste, hat er noch nicht gemacht.

1.8 Von Excel zu Python: Ihre Daten liegen schon da

In den allermeisten Betrieben liegen die Zahlen, die ein Optimierungsmodell braucht, nicht in einer Datenbank, sondern in einer Tabellenkalkulation. Und viele Leserinnen und Leser kennen Optimierung bisher genau von dort: über Daten → Solver in Excel. Dieser Abschnitt schlägt die Brücke — in beide Richtungen.

Was Sie damit gewinnen ist weniger die Rechenleistung als die Nachvollziehbarkeit: Ein Python-Modell lässt sich versionieren, testen, in einer Schleife über hundert Szenarien laufen lassen und einem Kollegen erklären. Eine gewachsene Excel-Mappe mit Formeln quer über vier Blätter kann das alles nicht — und niemand traut sich mehr, sie anzufassen.

Das folgende Programm zeigt den ganzen Weg an einem Stück. Es legt die Eingabemappe beim ersten Start selbst an, damit Sie es sofort ausführen können; danach ersetzen Sie die Datei durch Ihre eigene. Solange die Spalten gleich heißen, ändert sich am Code nichts.

📎 Zum Modul or_kern.py

Die vier Arbeitsschritte — lesen, lösen, prüfen, schreiben — stehen nicht in diesem Programm, sondern in or_kern.py. Das ist ein gemeinsamer Unterbau, den alle Programme dieses Buchs benutzen können; er liegt im selben Verzeichnis und ist in Abschnitt 22.6 vollständig abgedruckt und erklärt.

Sie müssen ihn jetzt noch nicht verstehen. Wichtig ist nur die Aufteilung: Hier steht, was diesen Fall ausmacht — dort steht, was jedes Optimierungsprogramm braucht. Genau deshalb ist der Code unten so kurz.

#!/usr/bin/env python3

# Excel_Bruecke.py
"""
Kapitel Einfuehrung: Vom Excel-Solver zu Python - dieselbe Rechnung, dieselbe Datei.

Das Programm bildet den vollstaendigen Arbeitsweg ab, den ein Excel-Modell im
Betrieb sonst von Hand geht:

    Tabellenblatt lesen -> Modell bauen -> loesen -> Ergebnis zurueckschreiben

Damit es ohne Vorbereitung laeuft, legt es die Eingabedatei beim ersten Start
selbst an. Ersetzen Sie sie durch Ihre eigene Datei - solange die Spalten
gleich heissen, aendert sich am Code nichts.

Die vier Arbeitsschritte kommen aus or_kern.py (Kapitel Praxisfallen). Was
hier steht, ist nur noch das, was diesen Fall ausmacht - der Rest ist
gemeinsamer Unterbau. Wer das Modul nicht kennt: Es ist im Buch vollstaendig
abgedruckt und liegt im selben Verzeichnis.

Erzeugte Dateien (im Arbeitsverzeichnis):
    produktionsmix.xlsx           Eingabe:  Blaetter 'Produkte' und 'Kapazitaeten'
    produktionsmix_ergebnis.xlsx  Ausgabe:  Blaetter 'Plan' und 'Kennzahlen'

Benoetigt: pandas, openpyxl, ortools, pydantic (ueber or_kern)
"""

from __future__ import annotations

import os

import pandas as pd

from or_kern import (lade_produktionsproblem, loese_mit_glop, pruefe_loesung,
                     schreibe_ergebnis)

EINGABE = "produktionsmix.xlsx"
AUSGABE = "produktionsmix_ergebnis.xlsx"


def lege_beispieldatei_an(pfad: str) -> None:
    """Schreibt die Eingabemappe, wie sie auch aus dem Controlling kaeme."""
    produkte = pd.DataFrame({
        "Produkt": ["Tisch", "Stuhl", "Regal"],
        "Deckungsbeitrag": [240.0, 60.0, 130.0],
        "Montagestunden": [3.0, 1.0, 2.0],
        "Plattenmaterial": [6.0, 1.0, 4.0],
    })
    kapazitaeten = pd.DataFrame({
        "Ressource": ["Montagestunden", "Plattenmaterial"],
        "Verfuegbar": [150.0, 240.0],
    })
    with pd.ExcelWriter(pfad, engine="openpyxl") as mappe:
        produkte.to_excel(mappe, sheet_name="Produkte", index=False)
        kapazitaeten.to_excel(mappe, sheet_name="Kapazitaeten", index=False)


if __name__ == "__main__":
    if not os.path.exists(EINGABE):
        lege_beispieldatei_an(EINGABE)
        print(f"Beispiel-Eingabedatei angelegt: {EINGABE}")

    # 1. Lesen und pruefen. Faellt hier etwas auf, ist der Fehler noch
    #    zuzuordnen - spaeter waere er nur noch eine merkwuerdige Zahl.
    problem = lade_produktionsproblem(EINGABE)

    # 2. Loesen. Einzige solverabhaengige Zeile des ganzen Programms -
    #    'loese_mit_scipy' waere ein Einzeiler-Wechsel.
    loesung = loese_mit_glop(problem)

    # 3. Abnahmepruefung gegen die Anforderungen, ohne den Solver zu fragen.
    beanstandungen = pruefe_loesung(problem, loesung)
    if beanstandungen:
        raise SystemExit("Abnahmepruefung fehlgeschlagen:\n  - "
                         + "\n  - ".join(beanstandungen))

    # 4. Zurueckschreiben - im Format, das die Fachabteilung ohnehin benutzt.
    schreibe_ergebnis(AUSGABE, problem, loesung)

    print("=" * 66)
    print("  PRODUKTIONSPLAN AUS DER EXCEL-MAPPE")
    print("=" * 66)
    for produkt in problem.produkte:
        menge = loesung.werte[produkt.name]
        print(f"{produkt.name:<18} {menge:8.1f} Stueck "
              f"{menge * produkt.deckungsbeitrag:12,.2f} EUR")
    print("-" * 66)
    print(loesung.als_bericht())
    print("Abnahmepruefung: bestanden\n")

    # Die Schattenpreise beantworten die Frage, die der Plan nicht stellt:
    # Was waere eine zusaetzliche Einheit dieser Ressource wert?
    for ressource, preis in loesung.schattenpreise.items():
        print(f"  eine Einheit {ressource:<18} mehr waere wert: {preis:7.2f} EUR")
    print("=" * 66)
    print(f"Ergebnis geschrieben nach: {AUSGABE}")

Erwartete Ausgabe:

Beispiel-Eingabedatei angelegt: produktionsmix.xlsx
==================================================================
  PRODUKTIONSPLAN AUS DER EXCEL-MAPPE
==================================================================
Tisch                  30.0 Stueck     7,200.00 EUR
Stuhl                  60.0 Stueck     3,600.00 EUR
Regal                   0.0 Stueck         0.00 EUR
------------------------------------------------------------------
Status: optimal | Zielwert: 10,800.00 | Gap: 0.00% | Zeit: 0.00s
Abnahmepruefung: bestanden

  eine Einheit Montagestunden     mehr waere wert:   40.00 EUR
  eine Einheit Plattenmaterial    mehr waere wert:   20.00 EUR
==================================================================
Ergebnis geschrieben nach: produktionsmix_ergebnis.xlsx

💻 Code-Durchgang

Stelle	Was passiert	Warum es so gebaut ist
lade_produktionsproblem(EINGABE)	liest die Mappe und prüft sie	Leere Zellen, fehlende Spalten, Kapazitäten von null oder Ressourcen ohne Kapazitätsangabe scheitern hier — nicht erst beim Lösen, wo der Fehler nur noch eine merkwürdige Zahl wäre.
loese_mit_glop(problem)	die einzige solverabhängige Zeile	loese_mit_scipy wäre ein Einzeiler-Wechsel. Alles davor und danach bleibt unverändert.
pruefe_loesung(problem, loesung)	Abnahmeprüfung ohne Solver	Sie bekommt nur die ausgegebene Lösung und die Anforderungen. Eine Prüfung aus denselben Bausteinen wie das Modell prüft das Modell gegen sich selbst.
raise SystemExit(...)	bricht bei Beanstandung ab	Ein Programm, das trotz durchgefallener Prüfung eine Datei schreibt, ist gefährlicher als eines, das abstürzt.
loesung.schattenpreise	Dualwerte aus dem Lösungsobjekt	Sie sind ein solverunabhängiger Begriff und stehen deshalb im Ergebnis, nicht im Solvercode.

Das Ergebnis liest sich von selbst: Das Regal — obwohl mit 130 € Deckungsbeitrag scheinbar attraktiv — wird gar nicht gebaut. Die Schattenpreise sagen warum: Ein Regal verbraucht 2 Montagestunden zu je 40 € und 4 m² Material zu je 20 €, bindet also Ressourcen im Wert von 2 \cdot 40 + 4 \cdot 20 = 160 € und bringt nur 130 € ein. Es verdient seinen Platz in der Werkstatt nicht. Diese Art von Aussage — begründet, in Euro, für den Chef nachvollziehbar — ist der eigentliche Ertrag der Optimierung.

⚠️ Typische Fehler beim Umstieg von Excel

• Zellbezüge statt Namen. Wer im Code mit df.iloc[:, 3] arbeitet, baut denselben Fehler nach, der in Excel-Mappen =SUMME(D2:D40) so gefährlich macht: Eine eingefügte Spalte verschiebt alles. Sprechen Sie Spalten über ihren Namen an.
• Einheiten mischen. Wenn eine Spalte Stunden und eine Minuten enthält, merkt das weder Excel noch der Solver — nur der Disponent, wenn der Plan nicht aufgeht.
• Das Ergebnis nur auf den Bildschirm schreiben. Was nicht in einer Datei landet, die die Fachabteilung öffnen kann, wird nicht benutzt.

1.9 Übungsaufgaben

Lösungen zu allen Aufgaben: Abschnitt A.1.

Aufgabe 1.1 ⭐ — Abgrenzung. Ordnen Sie jede Frage der richtigen Analytik-Stufe (deskriptiv / prädiktiv / präskriptiv) zu und begründen Sie in einem Satz: (a) „Wie viele Pakete haben wir letzten Monat zugestellt?“ (b) „Wie viele Pakete werden wir nächsten Dezember zustellen?“ (c) „Welche Tour soll Fahrzeug 3 morgen fahren?“ (d) „Welche Kunden werden voraussichtlich kündigen?“ (e) „Welchen dieser Kunden sollen wir mit unserem begrenzten Rabattbudget halten?“

Aufgabe 1.2 ⭐ — Hart oder weich? Entscheiden Sie für jede Bedingung eines Klinik-Dienstplans, ob sie hart oder weich modelliert werden sollte, und begründen Sie: (a) Gesetzliche Ruhezeit von 11 Stunden zwischen zwei Diensten. (b) Frau Meier möchte freitags nicht arbeiten. (c) In jeder Nachtschicht muss mindestens eine examinierte Fachkraft anwesend sein. (d) Die Dienste sollen gleichmäßig über das Team verteilt sein. (e) Niemand arbeitet mehr als 10 Tage am Stück.

Aufgabe 1.3 ⭐⭐ — Kombinatorik selbst rechnen. Ein Speditionsdisponent muss 12 Aufträge auf einen einzigen Lkw in eine Reihenfolge bringen. (a) Wie viele Reihenfolgen gibt es? (b) Der Rechner prüft 5 Millionen Reihenfolgen pro Sekunde. Wie lange dauert das vollständige Durchprobieren? (c) Wie lange dauert es bei 13 Aufträgen? Um welchen Faktor ist das mehr? (d) Wie viele Aufträge könnte man in einer Stunde noch vollständig durchprobieren?

Aufgabe 1.4 ⭐⭐ — Modell lesen. Gegeben sei das Modell \max\ 3x_1 + 5x_2 \quad \text{u. d. N.} \quad x_1 \le 4,\ \ 2x_2 \le 12,\ \ 3x_1 + 2x_2 \le 18,\ \ x_1, x_2 \ge 0. (a) Benennen Sie die vier Bausteine. (b) Ist (2, 6) zulässig? Ist (4, 3) zulässig? Berechnen Sie jeweils Z. (c) Finden Sie durch Probieren die beste ganzzahlige Lösung.

Aufgabe 1.5 ⭐⭐⭐ — Die Bäckerei programmieren. Setzen Sie das Bäckerei-Problem der Handrechnung Zerlegen Sie dieses Problem mit CP-SAT um. Geben Sie die optimale Produktionsmenge, den Deckungsbeitrag und die Auslastung von Mehl und Ofen aus. Prüfen Sie Ihr Ergebnis mit assert-Anweisungen.

Aufgabe 1.6 ⭐⭐⭐ — Sensitivität durch Ausprobieren. Erweitern Sie Bot_Allokation.py so, dass es das Modell in einer Schleife für RAM-Kapazitäten von 54 bis 72 GB (in Schritten von 2) löst und eine Tabelle RAM | x_A | x_B | Gewinn | Gewinnzuwachs pro zusätzlichem GB ausgibt. (a) Ab welcher RAM-Menge steigt der Gewinn nicht mehr? Warum? (b) Was sagt Ihnen der „Gewinnzuwachs pro GB“ intuitiv? (Der Begriff dafür — Schattenpreis — folgt in Kapitel 5.)

Aufgabe 1.7 ⭐⭐⭐ — Eigenes Problem zerlegen. Wählen Sie ein Entscheidungsproblem aus Ihrem eigenen Alltag oder Beruf (Beispiele: Wochenplan für Sportkurse, Sitzordnung bei einer Feier, Aufteilung eines Budgets auf Projekte, Reihenfolge von Hausarbeiten). Füllen Sie die Vorlage aus Abschnitt 1.6 vollständig aus. Notieren Sie außerdem: Woher kämen die Daten? Wer müsste das Ergebnis akzeptieren? — Heben Sie diese Notiz auf; sie ist der Ausgangspunkt für Ihr eigenes Projekt in der Projektwerkstatt.

1.10 Finde den Denkfehler

Ein Programm, das abstürzt, ist harmlos — Sie sehen sofort, dass etwas nicht stimmt. Gefährlich sind Programme, die fehlerfrei durchlaufen, einen Status OPTIMAL melden und eine Zahl liefern, die betriebswirtschaftlich Unsinn ist. Genau solche Fälle üben wir hier.

🎯 Merksatz Ein Optimierungsergebnis, das deutlich besser ausfällt als erwartet, ist zuerst einmal ein Fehlerverdacht — kein Grund zur Freude. Freuen Sie sich erst, nachdem Sie nachgerechnet haben, dass die Lösung alle Regeln einhält.

1.11 Micro-Quiz

1.12 Selbsttest

Antworten: Anhang A.

1. Was unterscheidet eine Entscheidungsvariable von einem Parameter?
2. Warum hilft ein 1000-mal schnellerer Rechner bei kombinatorischer Explosion praktisch nicht?
3. Nennen Sie die vier Bausteine eines OR-Modells.
4. Was bedeutet der Solver-Status INFEASIBLE, und was ist die häufigste Ursache?
5. Warum ist es gefährlich, eine Beschränkung nur als Variablengrenze statt als Nebenbedingung zu formulieren?

1.13 Zusammenfassung

• Operations Research ist präskriptiv: Es beantwortet nicht, was war oder was kommt, sondern was zu tun ist.
• Kombinatorische Explosion ist eine Wand, keine Steigung. Zwischen „in Minuten machbar“ und „in Jahrmillionen unmöglich“ liegen oft nur wenige zusätzliche Objekte. Solver umgehen das nicht durch Geschwindigkeit, sondern durch Struktur.
• Jedes Modell besteht aus vier Bausteinen: Entscheidungsvariablen, Parameter, Zielfunktion, Nebenbedingungen. Diese Zerlegung ist die eigentliche Arbeit; die Solverwahl ergibt sich danach fast von selbst.
• Harte und weiche Bedingungen sind eine Entwurfsentscheidung mit großen Folgen für Lösbarkeit und Akzeptanz.
• Ihre Daten liegen schon in Excel. pandas.read_excel() holt sie ab, der Solver rechnet, to_excel() gibt das Ergebnis im gewohnten Format zurück. Der Gewinn gegenüber einer Solver-Mappe ist nicht Rechenleistung, sondern Nachvollziehbarkeit: versionierbar, testbar, hundertmal in einer Schleife ausführbar.
• Prüfen Sie jedes Ergebnis — gegen eine Handrechnung, gegen assert-Anweisungen und gegen eine naive Vergleichsstrategie. Ein unerwartet gutes Ergebnis ist ein Fehlerverdacht, keine gute Nachricht.

Ausblick. Kapitel 2 liefert die Sprache, um Modelle mit hunderten Variablen kompakt aufzuschreiben: Vektoren, Matrizen und die geometrische Sicht auf den zulässigen Bereich. Dort lernen wir auch die Eigenschaft kennen, die darüber entscheidet, ob ein Problem verlässlich lösbar ist: Konvexität.