Kapitel 14: Mehrere Ziele — Pareto-Fronten statt Gewichte

14.1 In 5 Minuten gelöst

Und jetzt der Punkt. 80 Euro mehr sparen 450 Kilogramm CO₂ — 18 Cent je Kilogramm. Der europäische Emissionshandel bewegt sich um ein Vielfaches davon. Die Entscheidung ist damit keine Wertefrage mehr, sondern eine Rechnung.

Beachten Sie, was hier nicht passiert ist: Niemand musste ein Gewicht festlegen. Die zweite Zeile setzt eine Schranke („höchstens 2 % teurer”) und optimiert dann das andere Ziel. Das Ergebnis ist eine Aussage, die ein Kaufmann prüfen kann.

🎯 Merksatz „Wie wichtig ist Ihnen CO₂?” ist keine beantwortbare Frage. „Wir geben zwei Prozent mehr aus — was bringt das?” ist eine.

Warum funktioniert das? Weil aus zwei Zielen ein Ziel und eine Nebenbedingung geworden sind. Das ist die Grundidee des ε-Constraint-Verfahrens, um das sich dieses Kapitel dreht — und es ist der Grund, warum es ohne jedes Gewicht auskommt.

14.2 Lernziele

Nach diesem Kapitel können Sie …

1. … Pareto-Dominanz und Pareto-Front definieren und an einem Diagramm zeigen.
2. … erklären, warum die gewichtete Summe nur gestützte Lösungen findet — und was das geometrisch heißt.
3. … eine vollständige Pareto-Front mit dem ε-Constraint-Verfahren berechnen, mit so vielen Solverläufen, wie die Front Punkte hat.
4. … lexikografische Optimierung einsetzen, wenn es eine klare Rangfolge der Ziele gibt.
5. … einer Entscheiderin die Front so vorlegen, dass sie eine Wahl treffen kann.

14.3 Wann ein Kompromiss gut ist

Bei einem Ziel ist „besser” eindeutig. Bei zwei Zielen nicht mehr: Ein Plan kann billiger und schmutziger sein als ein anderer, und dann ist keiner von beiden besser.

Vergleichbar sind nur die Fälle, in denen ein Plan in keinem Ziel schlechter ist:

x \text{ dominiert } y \quad :\Longleftrightarrow \quad f_i(x) \le f_i(y)\ \text{ für alle } i \ \text{ und }\ f_j(x) < f_j(y)\ \text{ für mindestens ein } j

📖 Definition: Pareto-Front

Die Menge aller nicht dominierten Lösungen. Sie ist das vollständige Ergebnis eines Mehrzielproblems — nicht ein Punkt, sondern eine Liste.

Wer daraus einen einzelnen Punkt macht, trifft eine Entscheidung. Die Frage ist nur, ob er es merkt.

14.4 Der Reflex: alles in ein Ziel rühren

Der naheliegende Weg, zwei Ziele zu einem zu machen, ist die gewichtete Summe:

\min_{x \in X} \; c(x) + w \cdot e(x)

Das ist bequem, liefert zulässige Lösungen und wird in der Praxis fast immer so gemacht. Es hat nur einen Fehler, den man erst sieht, wenn man das Ergebnis mit der vollständigen Front vergleicht.

14.5 Das Programm

Zwölf Sendungen, drei Verkehrsträger, fünf freie Bahntrassen. Der Zielkonflikt entsteht nicht zwischen den Trägern — die Bahn ist immer billiger und sauberer als der LKW —, sondern durch die Knappheit der Trassen. Genau so sieht es in der Praxis aus.

#!/usr/bin/env python3

# Mehrziel_Pareto.py
"""
Kapitel Mehrziel: Kosten gegen CO2 - und warum Gewichte nicht genuegen.

Eine Spedition vergibt zwoelf Sendungen an drei Verkehrstraeger: LKW (schnell,
teuer, schmutzig), Bahn (billig und sauber, aber nur fuenf Trassen frei) und
Kombinierten Verkehr (dazwischen). Zwei Ziele stehen gegeneinander:
Transportkosten und CO2-Ausstoss.

Der uebliche Reflex ist, beide Ziele zu einem zusammenzuruehren:

    minimiere   Kosten + w * CO2

Das ist bequem, liefert zulaessige Loesungen - und ist unvollstaendig. Bei
ganzzahligen Entscheidungen gibt es Kompromisse, die auf diesem Weg
GRUNDSAETZLICH nicht erreichbar sind, egal welches w man waehlt. Nicht "schwer
zu finden", sondern beweisbar unerreichbar.

Das Programm zeigt in vier Teilen:

  1. Die beiden Extreme - was jedes Ziel allein kostet.
  2. Die lineare Skalarisierung ueber ein feines Gewichtsraster.
  3. Die vollstaendige Pareto-Front ueber das eps-Constraint-Verfahren.
  4. Den Nachweis, dass die Luecke keine Frage des Rasters ist, sondern
     Geometrie: Die fehlenden Punkte liegen strikt oberhalb der konvexen
     Huelle und koennen deshalb von keiner Geraden gestuetzt werden.

Benoetigt: numpy, scipy
"""

from __future__ import annotations

import numpy as np
from scipy.optimize import linprog

TRAEGER = ["LKW", "Bahn", "Kombiniert"]
BAHN_TRASSEN = 5          # so viele Sendungen passen hoechstens auf die Bahn
SAAT = 5


def erzeuge_sendungen(anzahl: int = 12, saat: int = SAAT):
    """Kosten und CO2 je Sendung und Verkehrstraeger.

    Die Bahn ist immer billiger und sauberer als der LKW - der Zielkonflikt
    entsteht nicht zwischen den Traegern, sondern durch die KNAPPHEIT der
    Trassen. Genau so sieht es in der Praxis aus.
    """
    rng = np.random.default_rng(saat)
    kosten = np.zeros((anzahl, 3))
    co2 = np.zeros((anzahl, 3))
    for i in range(anzahl):
        grund_kosten = rng.integers(600, 2400)
        grund_co2 = rng.integers(400, 1800)
        kosten[i] = [grund_kosten,
                     grund_kosten * rng.uniform(0.55, 0.85),
                     grund_kosten * rng.uniform(0.70, 1.00)]
        co2[i] = [grund_co2,
                  grund_co2 * rng.uniform(0.15, 0.35),
                  grund_co2 * rng.uniform(0.40, 0.70)]
    return np.round(kosten).astype(int), np.round(co2).astype(int)


KOSTEN, CO2 = erzeuge_sendungen()
N = len(KOSTEN)


def plane(ziel: np.ndarray, co2_grenze: float | None = None,
          kosten_grenze: float | None = None):
    """Jede Sendung genau einem Traeger zuordnen; Trassen sind knapp.

    'ziel' ist die zu minimierende Matrix (Kosten, CO2 oder eine Mischung).
    Die beiden Grenzen sind das Werkzeug fuer eps-Constraint und
    lexikografische Optimierung - sie machen aus einem Ziel eine Schranke.
    """
    gleichungen = np.zeros((N, N * 3))
    for i in range(N):
        gleichungen[i, i * 3:(i + 1) * 3] = 1.0        # genau ein Traeger

    ungleichungen = [[1.0 if j == 1 else 0.0 for _ in range(N) for j in range(3)]]
    grenzen = [float(BAHN_TRASSEN)]
    if co2_grenze is not None:
        ungleichungen.append(CO2.reshape(-1).astype(float))
        grenzen.append(float(co2_grenze))
    if kosten_grenze is not None:
        ungleichungen.append(KOSTEN.reshape(-1).astype(float))
        grenzen.append(float(kosten_grenze))

    ergebnis = linprog(ziel.reshape(-1).astype(float),
                       A_ub=ungleichungen, b_ub=grenzen,
                       A_eq=gleichungen, b_eq=np.ones(N),
                       bounds=(0, 1), integrality=1, method="highs")
    if not ergebnis.success:
        return None
    plan = np.round(ergebnis.x).astype(int)
    return (int(KOSTEN.reshape(-1) @ plan), int(CO2.reshape(-1) @ plan), plan)


def pareto_front():
    """Vollstaendige Front ueber das eps-Constraint-Verfahren.

    Der Ablauf ist der eigentliche Inhalt dieser Funktion: Erst das
    Kostenminimum bestimmen (der eine Rand der Front), dann die CO2-Schranke
    schrittweise um genau ein Kilogramm unter den zuletzt erreichten Wert
    druecken. Jeder Lauf liefert den naechsten Punkt - und wenn keiner mehr
    zulaessig ist, ist die Front vollstaendig.

    Das braucht so viele Solveraufrufe, wie die Front Punkte hat. Ein Raster
    ueber alle moeglichen CO2-Werte braeuchte hier fast tausend.
    """
    front = []
    start = plane(KOSTEN)
    grenze = start[1]
    while True:
        ergebnis = plane(KOSTEN, co2_grenze=grenze)
        if ergebnis is None:
            break
        front.append((ergebnis[0], ergebnis[1]))
        grenze = ergebnis[1] - 1
    return front


def skalarisierung(gewichte):
    """Was 'Kosten + w * CO2' fuer viele w hergibt - als Menge von Punkten."""
    gefunden = {}
    for w in gewichte:
        ergebnis = plane(KOSTEN + w * CO2)
        if ergebnis:
            gefunden.setdefault((ergebnis[0], ergebnis[1]), []).append(w)
    return gefunden


def untere_huelle(punkte):
    """Untere linke konvexe Huelle - genau die Punkte, die eine Gerade stuetzt.

    Der Zusammenhang, um den es geht: 'Kosten + w*CO2 minimieren' heisst
    geometrisch, eine Gerade der Steigung -1/w von links unten an die
    Punktwolke zu schieben. Sie beruehrt immer einen Eckpunkt der konvexen
    Huelle. Punkte, die oberhalb liegen, werden nie beruehrt - fuer kein w.
    """
    huelle = []
    for punkt in sorted(punkte):
        while len(huelle) >= 2:
            (x1, y1), (x2, y2) = huelle[-2], huelle[-1]
            if (x2 - x1) * (punkt[1] - y1) - (y2 - y1) * (punkt[0] - x1) <= 0:
                huelle.pop()
            else:
                break
        huelle.append(punkt)
    return huelle


if __name__ == "__main__":
    print("=" * 80)
    print("  KOSTEN GEGEN CO2 - UND WARUM GEWICHTE NICHT GENUEGEN")
    print("=" * 80)
    print(f"{N} Sendungen, {len(TRAEGER)} Verkehrstraeger, "
          f"{BAHN_TRASSEN} freie Bahntrassen.\n")

    # --- 1. Die beiden Extreme -------------------------------------------
    guenstigst = plane(KOSTEN)
    saubersten = plane(CO2)
    print("1. Was jedes Ziel allein ergibt\n")
    print(f"  {'':<22} {'Kosten':>10} {'CO2':>10}")
    print("  " + "-" * 44)
    print(f"  {'nur Kosten minimal':<22} {guenstigst[0]:>10,} {guenstigst[1]:>9,} kg")
    print(f"  {'nur CO2 minimal':<22} {saubersten[0]:>10,} {saubersten[1]:>9,} kg")
    print(f"\n  Der Zielkonflikt ist echt, aber klein: "
          f"{saubersten[0] - guenstigst[0]:,} EUR mehr")
    print(f"  ({(saubersten[0] - guenstigst[0]) / guenstigst[0] * 100:.1f} %) sparen "
          f"{guenstigst[1] - saubersten[1]:,} kg CO2 "
          f"({(guenstigst[1] - saubersten[1]) / guenstigst[1] * 100:.1f} %).")
    print("  Genau solche Zahlen will die Geschaeftsfuehrung sehen - nicht ein")
    print("  Gewicht, das niemand interpretieren kann.")

    # --- 2. Die lineare Skalarisierung -----------------------------------
    gewichte = np.concatenate([np.linspace(0.0, 3.0, 1201),
                               np.geomspace(3.0, 1000.0, 200)])
    gefunden = skalarisierung(gewichte)
    print("\n" + "-" * 80)
    print(f"2. Lineare Skalarisierung: 'Kosten + w * CO2' fuer "
          f"{len(gewichte):,} Gewichte\n")
    print(f"  {'Kosten':>10} {'CO2':>10}   {'gefunden bei w':>16}")
    print("  " + "-" * 46)
    for (k, c), ws in sorted(gefunden.items()):
        print(f"  {k:>10,} {c:>9,} kg   {min(ws):>7.3f} bis {max(ws):>7.3f}")
    print(f"\n  {len(gefunden)} verschiedene Plaene - fuer {len(gewichte):,} Gewichte.")
    print("  Das Gewicht ist also gar keine Feineinstellung: Weite Bereiche")
    print("  liefern dasselbe Ergebnis, und dazwischen springt es.")

    # --- 3. Die vollstaendige Front --------------------------------------
    front = pareto_front()
    print("\n" + "-" * 80)
    print(f"3. Die vollstaendige Pareto-Front ueber eps-Constraint "
          f"({len(front)} Solverlaeufe)\n")
    print(f"  {'Kosten':>10} {'CO2':>10}   {'Aufpreis':>9} {'CO2-Ersparnis':>14} "
          f"{'EUR je kg':>10}")
    print("  " + "-" * 60)
    for k, c in front:
        auf = k - guenstigst[0]
        ersparnis = guenstigst[1] - c
        preis = auf / ersparnis if ersparnis else 0.0
        print(f"  {k:>10,} {c:>9,} kg   {auf:>8,} {ersparnis:>13,} "
              f"{preis:>10.2f}")

    # --- 4. Der Nachweis --------------------------------------------------
    huelle = untere_huelle(front)
    unerreichbar = [p for p in front if p not in huelle]
    print("\n" + "-" * 80)
    print("4. Was die Skalarisierung nicht findet\n")
    erreicht = [p for p in front if p in gefunden]
    print(f"  Pareto-Punkte insgesamt:              {len(front)}")
    print(f"  davon von der Skalarisierung gefunden: {len(erreicht)}")
    print(f"  nie gefunden:                          {len(front) - len(erreicht)}")
    print()
    print("  Diese Kompromisse sind fuer KEIN Gewicht erreichbar:\n")
    print(f"  {'Kosten':>10} {'CO2':>10}   {'Aufpreis':>9} {'CO2-Ersparnis':>14}")
    print("  " + "-" * 50)
    for k, c in unerreichbar:
        print(f"  {k:>10,} {c:>9,} kg   {k - guenstigst[0]:>8,} "
              f"{guenstigst[1] - c:>13,}")

    stimmt = sorted(unerreichbar) == sorted(p for p in front if p not in gefunden)
    print(f"\n  Gegenprobe ueber die Geometrie: {'bestanden' if stimmt else 'ABWEICHUNG'}")
    print("  Genau die Punkte, die das Gewichtsraster verfehlt, liegen strikt")
    print("  oberhalb der unteren konvexen Huelle. Das ist kein Rasterproblem -")
    print("  eine Gerade, die von links unten an die Wolke geschoben wird,")
    print("  beruehrt immer einen Eckpunkt der Huelle und nie einen Punkt")
    print("  darueber. Ein feineres Raster aendert daran nichts.")

    # --- 5. Lexikografisch -------------------------------------------------
    print("\n" + "-" * 80)
    print("5. Lexikografisch: erst Kosten, dann CO2 im Rahmen eines Budgets\n")
    print(f"  {'Kostenbudget':>14} {'Kosten':>10} {'CO2':>10} {'gegenueber Minimum':>20}")
    print("  " + "-" * 58)
    for aufschlag in (0.00, 0.01, 0.02, 0.05, 0.10):
        budget = guenstigst[0] * (1 + aufschlag)
        ergebnis = plane(CO2, kosten_grenze=budget)
        if ergebnis is None:
            print(f"  {aufschlag:>13.0%} unzulaessig")
            continue
        print(f"  {aufschlag:>13.0%} {ergebnis[0]:>10,} {ergebnis[1]:>9,} kg "
              f"{guenstigst[1] - ergebnis[1]:>15,} kg weniger")

    print("\n  Das ist die Form, die im Betrieb am ehesten trifft: Nicht 'wie")
    print("  wichtig ist CO2?', sondern 'wir geben zwei Prozent mehr aus - was")
    print("  bringt das?'. Die Frage kann ein Kaufmann beantworten.")

    print("\n" + "=" * 80)
    print("  WAS MAN DARAUS MITNIMMT")
    print("=" * 80)
    print("Ein Gewicht zu setzen heisst, die Entscheidung heimlich zu treffen -")
    print("und dabei einen Teil der Moeglichkeiten gar nicht erst zu sehen.")
    print()
    print("Die Pareto-Front ist die ehrlichere Antwort: Sie legt dem Betrieb")
    print("alle sinnvollen Kompromisse vor und ueberlaesst ihm die Wahl. Die")
    print("Spalte 'EUR je kg' macht sie entscheidbar - man vergleicht sie mit")
    print("dem CO2-Preis, den das Unternehmen ohnehin ansetzt.")
    print("=" * 80)

Erwartete Ausgabe:

================================================================================
  KOSTEN GEGEN CO2 - UND WARUM GEWICHTE NICHT GENUEGEN
================================================================================
12 Sendungen, 3 Verkehrstraeger, 5 freie Bahntrassen.

1. Was jedes Ziel allein ergibt

                             Kosten        CO2
  --------------------------------------------
  nur Kosten minimal         13,543     6,475 kg
  nur CO2 minimal            14,821     5,506 kg

  Der Zielkonflikt ist echt, aber klein: 1,278 EUR mehr
  (9.4 %) sparen 969 kg CO2 (15.0 %).
  Genau solche Zahlen will die Geschaeftsfuehrung sehen - nicht ein
  Gewicht, das niemand interpretieren kann.

--------------------------------------------------------------------------------
2. Lineare Skalarisierung: 'Kosten + w * CO2' fuer 1,401 Gewichte

      Kosten        CO2     gefunden bei w
  ----------------------------------------------
      13,543     6,475 kg     0.000 bis   0.398
      13,724     6,022 kg     0.400 bis   1.002
      14,036     5,711 kg     1.005 bis   1.935
      14,189     5,632 kg     1.938 bis   3.471
      14,592     5,517 kg     3.574 bis  20.599
      14,821     5,506 kg    21.210 bis 1000.000

  6 verschiedene Plaene - fuer 1,401 Gewichte.
  Das Gewicht ist also gar keine Feineinstellung: Weite Bereiche
  liefern dasselbe Ergebnis, und dazwischen springt es.

--------------------------------------------------------------------------------
3. Die vollstaendige Pareto-Front ueber eps-Constraint (10 Solverlaeufe)

      Kosten        CO2    Aufpreis  CO2-Ersparnis  EUR je kg
  ------------------------------------------------------------
      13,543     6,475 kg          0             0       0.00
      13,635     6,317 kg         92           158       0.58
      13,718     6,286 kg        175           189       0.93
      13,724     6,022 kg        181           453       0.40
      13,868     5,927 kg        325           548       0.59
      13,978     5,912 kg        435           563       0.77
      14,036     5,711 kg        493           764       0.65
      14,189     5,632 kg        646           843       0.77
      14,592     5,517 kg      1,049           958       1.09
      14,821     5,506 kg      1,278           969       1.32

--------------------------------------------------------------------------------
4. Was die Skalarisierung nicht findet

  Pareto-Punkte insgesamt:              10
  davon von der Skalarisierung gefunden: 6
  nie gefunden:                          4

  Diese Kompromisse sind fuer KEIN Gewicht erreichbar:

      Kosten        CO2    Aufpreis  CO2-Ersparnis
  --------------------------------------------------
      13,635     6,317 kg         92           158
      13,718     6,286 kg        175           189
      13,868     5,927 kg        325           548
      13,978     5,912 kg        435           563

  Gegenprobe ueber die Geometrie: bestanden
  Genau die Punkte, die das Gewichtsraster verfehlt, liegen strikt
  oberhalb der unteren konvexen Huelle. Das ist kein Rasterproblem -
  eine Gerade, die von links unten an die Wolke geschoben wird,
  beruehrt immer einen Eckpunkt der Huelle und nie einen Punkt
  darueber. Ein feineres Raster aendert daran nichts.

--------------------------------------------------------------------------------
5. Lexikografisch: erst Kosten, dann CO2 im Rahmen eines Budgets

    Kostenbudget     Kosten        CO2   gegenueber Minimum
  ----------------------------------------------------------
             0%     13,543     6,475 kg               0 kg weniger
             1%     13,635     6,317 kg             158 kg weniger
             2%     13,724     6,022 kg             453 kg weniger
             5%     14,189     5,632 kg             843 kg weniger
            10%     14,821     5,506 kg             969 kg weniger

  Das ist die Form, die im Betrieb am ehesten trifft: Nicht 'wie
  wichtig ist CO2?', sondern 'wir geben zwei Prozent mehr aus - was
  bringt das?'. Die Frage kann ein Kaufmann beantworten.

================================================================================
  WAS MAN DARAUS MITNIMMT
================================================================================
Ein Gewicht zu setzen heisst, die Entscheidung heimlich zu treffen -
und dabei einen Teil der Moeglichkeiten gar nicht erst zu sehen.

Die Pareto-Front ist die ehrlichere Antwort: Sie legt dem Betrieb
alle sinnvollen Kompromisse vor und ueberlaesst ihm die Wahl. Die
Spalte 'EUR je kg' macht sie entscheidbar - man vergleicht sie mit
dem CO2-Preis, den das Unternehmen ohnehin ansetzt.
================================================================================

14.6 Was die gewichtete Summe nicht sieht

Die Front hat zehn Punkte. Ein Raster aus 1 401 Gewichten findet sechs davon. Vier Kompromisse sind für kein Gewicht erreichbar — und das ist keine Frage der Rasterweite.

Warum es keine Frage des Rasters ist. „c(x) + w\,e(x) minimieren” heißt geometrisch: eine Gerade der Steigung -1/w von links unten an die Punktwolke schieben und schauen, welchen Punkt sie zuerst berührt. Eine Gerade berührt immer einen Eckpunkt der unteren konvexen Hülle. Punkte, die oberhalb der Hülle liegen, werden von keiner Geraden zuerst getroffen — für kein w, bei beliebig feiner Abstufung.

Das Programm rechnet diese Hülle in untere_huelle() unabhängig aus und vergleicht: Genau die vier Punkte, die das Gewichtsraster verfehlt, liegen strikt oberhalb. Die Gegenprobe steht in der Ausgabe.

Was Sie in der Abbildung sehen. Die beiden Geraden haben dieselbe Steigung, also dasselbe Gewicht w. Die untere berührt die Hülle in zwei Ecken — eine von beiden meldet der Solver als Optimum. Die obere geht durch einen pareto-optimalen Punkt, der damit für dieses Gewicht chancenlos ist, und zwar nicht knapp: Er liegt eine ganze Stufe darüber. Verschieben Sie die Steigung, verschiebt sich die Berührung von einer Ecke zur nächsten — über den Punkt dazwischen springt sie hinweg. Die waagerechte Linie zeigt den Ausweg, um den es in Abschnitt 14.7 geht: Eine Schranke für den CO₂-Ausstoß statt eines Gewichts findet genau diesen Punkt.

⚠️ Der Grund liegt in der Ganzzahligkeit

Bei einem reinen LP ist der zulässige Bereich konvex, und die Pareto-Front liegt vollständig auf ihrer eigenen konvexen Hülle — dort findet die gewichtete Summe alles. Sobald Entscheidungen ganzzahlig werden (welcher Träger, welches Lager, welche Schicht), zerfällt der Bereich in einzelne Punkte, und zwischen ihnen entstehen Einbuchtungen.

Deshalb betrifft dieses Problem praktisch jedes betriebliche Mehrzielmodell. Wer mit Gewichten arbeitet, verliert nicht ein paar Nachkommastellen, sondern ganze Alternativen — im Beispiel 40 % der Front.

Das Gewicht ist keine Feineinstellung

Die zweite Beobachtung aus derselben Tabelle: 1 401 Gewichte erzeugen sechs verschiedene Pläne. Weite Gewichtsbereiche liefern dasselbe Ergebnis, und dazwischen springt es.

Das macht die verbreitete Vorgehensweise — „wir probieren ein paar Gewichte und schauen, was herauskommt” — zu einem Glücksspiel. Man weiß nie, ob man einen neuen Kompromiss gefunden hat oder nur denselben noch einmal.

14.7 Das ε-Constraint-Verfahren

Der Ausweg ist unspektakulär: Man macht aus dem zweiten Ziel eine Nebenbedingung.

\min_{x \in X} \; c(x) \qquad \text{unter} \qquad e(x) \le \varepsilon

Für jedes \varepsilon liefert das einen Punkt der Front. Die Kunst besteht nur darin, die \varepsilon geschickt zu wählen — und dafür gibt es ein Verfahren, das genau so viele Solverläufe braucht, wie die Front Punkte hat:

1. Kostenminimum bestimmen. Das ist der eine Rand der Front; nebenbei fällt sein CO₂-Wert an.
2. \varepsilon auf ein Kilogramm unter diesen Wert setzen und erneut lösen.
3. Schritt 2 wiederholen, bis kein zulässiger Plan mehr existiert.

Im Beispiel sind das zehn Läufe. Ein Raster über alle möglichen CO₂-Werte bräuchte fast tausend, ein Gewichtsraster findet auch mit 1 401 Läufen nur sechs Punkte.

🎯 Merksatz ε-Constraint ist das Arbeitspferd der Mehrzieloptimierung: vollständig, mit minimal vielen Solverläufen, und ohne dass jemand ein Gewicht erfinden muss.

Wenn es eine klare Rangfolge gibt: lexikografisch

Manchmal ist ein Ziel wirklich vorrangig. Dann optimiert man lexikografisch: erst das erste Ziel, dann das zweite unter der Bedingung, dass das erste (fast) erhalten bleibt.

Der Sprung von +1 % auf +2 % ist der interessante: Das zweite Prozent bringt fast dreimal so viel wie das erste. Solche Unregelmäßigkeiten sind bei ganzzahligen Modellen die Regel — und ein weiteres Argument gegen Gewichte, die eine gleichmäßige Abwägung suggerieren.

Beachten Sie außerdem: Die Zeile „+0 %” ist ein Sonderfall, der sich auszahlt. Sie sucht unter allen kostenminimalen Plänen den saubersten. Gibt es mehrere optimale Lösungen — und das ist bei ganzzahligen Modellen fast immer so —, bekommt man die CO₂-Ersparnis geschenkt. Ein Solver, der nur ein Ziel kennt, gibt einfach die erstbeste zurück.

14.8 Wie man die Front vorlegt

Eine Front mit zehn Punkten ist kein Ergebnis, sondern eine Speisekarte. Damit sie entscheidbar wird, gehört eine Spalte dazu, die im Programm EUR je kg heißt:

\text{Schattenpreis} = \frac{\text{Aufpreis gegenüber dem Kostenminimum}} {\text{eingesparte Kilogramm}}

Diese Zahl ist mit etwas vergleichbar, das das Unternehmen ohnehin kennt: dem internen CO₂-Preis oder dem Zertifikatspreis. Liegt der Schattenpreis darunter, ist die Entscheidung kaufmännisch schon getroffen.

💻 Code-Durchgang: die drei Bausteine

Stelle	Was sie tut
plane(ziel, co2_grenze, kosten_grenze)	eine Funktion für alle Varianten. Welches Ziel und welche Schranke — mehr Unterschied gibt es zwischen den fünf Teilen des Programms nicht
pareto_front()	das ε-Verfahren: Grenze jeweils um 1 kg unter den zuletzt erreichten Wert drücken, bis nichts mehr geht
untere_huelle()	rechnet die Hülle unabhängig aus, damit die Aussage „unerreichbar“ nicht auf dem Gewichtsraster beruht, sondern auf Geometrie

Der Vergleich am Ende von Teil 4 ist bewusst ein assert-artiger Abgleich: Wenn Gewichtsraster und Hüllenrechnung verschiedene Punktmengen liefern, stimmt eines von beidem nicht — und das steht dann in der Ausgabe.

14.9 Übungsaufgaben

Lösungen: Abschnitt A.14.

Aufgabe 14.1 ⭐ — Dominanz prüfen. Plan P kostet 14 000 € und stößt 6 000 kg aus, Plan Q kostet 13 800 € und stößt 6 100 kg aus. Dominiert einer den anderen? Und wie steht es mit R (14 000 €, 6 100 kg)?

Aufgabe 14.2 ⭐ — Der Schattenpreis in der Praxis. Der interne CO₂-Preis des Unternehmens beträgt 0,90 € je Kilogramm. Welchen Punkt der Front würden Sie empfehlen — und wie begründen Sie ihn in einem Satz?

Aufgabe 14.3 ⭐⭐ — Mehr Trassen. Erhöhen Sie BAHN_TRASSEN von 5 auf 8. Was passiert mit der Länge der Front und mit der Zahl der unerreichbaren Punkte? Erklären Sie den Zusammenhang.

Aufgabe 14.4 ⭐⭐ — Die Front der Relaxation. Lassen Sie integrality weg, sodass Anteile erlaubt sind. Berechnen Sie die Front erneut (mit einem ε-Raster, da es nun unendlich viele Punkte gibt). Wie viele Punkte liegen jetzt oberhalb der konvexen Hülle — und warum?

Aufgabe 14.5 ⭐⭐⭐ — Drei Ziele. Ergänzen Sie die Laufzeit als drittes Ziel (LKW schnell, Bahn langsam). Die Front wird zu einer Fläche. Wie ändert sich das ε-Verfahren, und warum wächst der Aufwand so schnell?

14.10 Finde den Denkfehler

14.11 Micro-Quiz

14.12 Selbsttest

1. Erklären Sie Pareto-Dominanz an einem Beispiel aus Ihrem Arbeitsumfeld.
2. Warum ist „gewichtete Summe” bei einem reinen LP unproblematisch und bei einem MILP nicht?
3. Ein Kollege sagt: „Ich nehme w = 0{,}5, das ist neutral.” Was ist daran falsch?
4. Beschreiben Sie das ε-Constraint-Verfahren in drei Sätzen, ohne Formeln.
5. Sie legen einer Geschäftsführung eine Front mit zwölf Punkten vor. Welche Spalte brauchen Sie, damit die Entscheidung fallen kann?

14.13 Zusammenfassung

• Bei mehreren Zielen ist „besser” nur noch über Dominanz definiert. Das vollständige Ergebnis ist keine Lösung, sondern die Pareto-Front.
• Die gewichtete Summe findet nur Punkte auf der unteren konvexen Hülle. Bei ganzzahligen Modellen liegen regelmäßig Pareto-Punkte darüber — im Beispiel 4 von 10, also 40 % der Alternativen. Das ist kein Rasterproblem, sondern Geometrie.
• Das Gewicht ist außerdem keine Feineinstellung: 1 401 Gewichte erzeugten sechs verschiedene Pläne, mit Sprüngen dazwischen.
• Das ε-Constraint-Verfahren macht aus dem zweiten Ziel eine Schranke und liefert die vollständige Front mit so vielen Solverläufen, wie sie Punkte hat.
• Lexikografisch optimiert man, wenn es eine echte Rangfolge gibt — „höchstens 2 % teurer, dafür so sauber wie möglich” ist eine Frage, die ein Kaufmann beantworten kann.
• Die Front wird erst entscheidbar durch die Spalte € je kg: Sie ist mit dem internen CO₂-Preis vergleichbar und verwandelt eine Wertefrage in eine Rechnung.