Das Distributionsnetz verständlich erklärt

Eine Kette beliefert ihre Filialen aus Fabriken über Lager. Jede Fahrt kostet Geld, und überall gibt es Grenzen. Warum kosten einfache Faustregeln mehr als ein Gesamtplan, und wo lohnt sich mehr Platz? Diese Seite erklärt es erst anschaulich, dann für Fachleute.

Zuletzt aktualisiert: 11. November 2026

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

Von der Fabrik bis in die Filiale

Wir erklären alles an vier erfundenen Beispielen. Im ersten Beispiel hat eine Handelskette acht Filialen, also acht Läden. Die Ware stammt aus drei Werken, das sind Fabriken. Sie fährt nicht direkt in die Läden. Zuerst geht sie in eines von drei Lagern, und von dort weiter zur Filiale. Fachleute nennen ein solches Lager Verteilzentrum.

Alles kostet Geld. Das Werk stellt die Ware her, das Lager schleust sie durch, und die Lastwagen fahren. Je länger die Strecke, desto teurer ist sie, denn sie braucht mehr Zeit und Sprit.

Es gibt aber Grenzen. Ein Werk schafft nur eine bestimmte Menge. Ein Lager kann in einer Lieferrunde nur eine bestimmte Menge durchschleusen. Auf jede Strecke passen nur so viele Lastwagen, wie die Straße verträgt. Jede Filiale braucht eine feste Menge. Ware zählen wir in Einheiten, zum Beispiel Kisten.

Gesucht ist der Plan, der alle Filialen beliefert und insgesamt am wenigsten kostet. Das ist ein vereinfachtes Rechenbild (Fachwort: Modell). Seine Aussagen beschreiben die Beispiele, nicht die Wirklichkeit.

Wenn es nicht für alle reicht

Manchmal geht nicht alles durch die Lager. Dann entsteht eine Lücke. Das Rechenbild kennt dafür eine Notlösung: Die Filiale bestellt eilig nach, zu einem Preis, der höher ist als jede normale Lieferung. Das heißt hier Notbeschaffung. Die Menge, die dann fehlt, heißt Fehlmenge.

Der Grund für diesen Kniff: So hat jede Aufgabe eine Antwort, auch wenn die Lager zu eng sind. Außerdem sieht man, wie viel sich nicht günstig liefern lässt. Im ersten Beispiel sind das 39 Einheiten.

Einfache Regeln und der Gesamtplan

Wie plant man das? Menschen nutzen oft einfache Regeln. Das Rechenbild vergleicht drei:

• Der Reihe nach, billigste Strecke: Jede Filiale nimmt, sobald sie dran ist, den billigsten Weg vom Werk über ein Lager, der noch frei ist.
• Größte zuerst: Dieselbe Regel, aber die Filiale mit dem größten Bedarf kommt zuerst dran.
• Nächstes Lager: Jede Filiale nimmt das nächstgelegene Lager, das noch frei ist, und dort das billigste Werk.

Dagegen steht der Gesamtplan. Er betrachtet alle Filialen gleichzeitig und darf frühere Entscheidungen wieder ändern. Im Rechenbild findet ein solches Verfahren die billigste Lösung. Mehrere unabhängige Programme rechnen den Gesamtplan nach. In allen vier Beispielen kommen sie auf dieselben Kosten.

Was die einfachen Regeln kosten

In den vier Beispielen kosten die einfachen Regeln zwischen 3 und 29 % mehr als der Gesamtplan. Im ersten Beispiel sind es 3 bis 4 %, in den anderen mehr. Wie so etwas entstehen kann, zeigt ein Bild: Eine Feier hat Tische mit begrenzten Plätzen. Setzt man Gäste der Reihe nach auf den nächsten freien Platz, fehlt am Ende der Platz für die letzte Gruppe. Mit etwas Umsetzen hätten alle gepasst.

Die einfachen Regeln setzen niemanden um. Frühe Filialen belegen die günstigen Strecken, und für die späten bleibt, was übrig ist. Im ersten Beispiel lassen die Regeln nicht mehr Ware unbedient als der Gesamtplan, liefern aber auf teureren Wegen. Laut Nachrechnung trifft bei zwei der drei Regeln die ganze Lücke die Filiale, die zuletzt an der Reihe ist. In den anderen Beispielen kommt bei den Regeln auch mehr Fehlmenge dazu.

Wo mehr Platz sich lohnt

Der Gesamtplan beantwortet noch eine Frage: Wo lohnt sich mehr Platz? Für jedes ausgelastete Werk, Lager und jede ausgelastete Strecke verrät er, wie viel eine weitere Einheit Platz spart. Dieser Wert heißt Schattenpreis. Er ist dort hoch, wo es am engsten ist.

Im ersten Beispiel liegt der Engpass bei den drei Lagern, nicht bei den Werken. Ein Bild dazu ist der Supermarkt: Wenn die Kassen der Engpass sind, hilft mehr Ware im Regal nichts. Dazu passt: Können alle Werke zusammen 20 % weniger herstellen, steigen die Gesamtkosten um weniger als 1 %. Baut man das Lager Nummer 1 um 50 % aus, sinken die Gesamtkosten dieses Beispiels um 29 %. Die Lücke verschwindet.

Vorrat für die Spitze

Bisher ging es um eine einzige Lieferrunde. Das Rechenbild kann auch mehrere Runden nacheinander planen. Dann dürfen Lager Ware in die nächste Runde mitnehmen, gegen Lagerkosten. Ein Bild dazu ist das Grillfest: Wer weiß, dass der Laden am Festtag überfüllt ist, kauft schon vorher ein.

Steigt die Nachfrage in den mittleren Runden an, baut der Gesamtplan davor Bestand auf. Die drei einfachen Regeln sind so gebaut, dass sie von Runde zu Runde planen und nie Ware mitnehmen. Bleibt die Nachfrage in jeder Runde gleich, lohnt sich Vorrat nie. Er könnte nur helfen, wenn eine Runde mehr Platz hat als die anderen. Bei gleicher Nachfrage ist das nie der Fall.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren, die Demo. Der erste Knopf unten öffnet sie, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht. Dort laden Sie die vier Beispiele und verstellen die Größe des Netzes.

Häufige Missverständnisse

• „Eine Lücke heißt, dass der Plan schlecht ist.“ Nein. Im ersten Beispiel bleibt sie auch im besten Plan, weil die drei Lager zusammen weniger durchschleusen, als die Filialen brauchen. Die Lücke zeigt, wo Platz fehlt.
• „Der Wert einer Zusatzeinheit gilt für jede weitere Einheit.“ Nein. Er bleibt ungefähr gleich, solange noch eine Lücke zu schließen ist, und ist danach null. Baut man das Lager Nummer 1 um genau die 39 fehlenden Einheiten aus, ist laut Nachrechnung schon alles gespart. Jede weitere Einheit bringt nichts. Umgerechnet auf alle zugebauten Einheiten, sinkt die Ersparnis je Einheit deshalb.
• „Eine der einfachen Regeln ist die beste.“ Nicht in jedem Beispiel. In zwei der vier gewinnt „nächstes Lager“, in den anderen beiden je eine der anderen Regeln. Welche Regel in einem anderen Netz vorn liegt, zeigen vier Beispiele nicht.

Woran Sie das im Alltag erkennen

• Vor dem Eingang eines Konzerts staut sich eine Schlange, obwohl drinnen viel Platz ist. Eine einzige enge Stelle, hier die Kontrolle, bestimmt, wie viele durchkommen.
• Vor Feiertagen füllen Läden ihre Regale schon früh auf, weil am Tag davor die Lieferwagen nicht mehr alles schaffen.

Wie ernst ist das Rechenbild zu nehmen?

Die Werke, Lager und Filialen sind erfunden und zufällig auf einer Karte verteilt. Die Prozentzahlen stammen aus vier solchen Beispielen und zeigen nur, wie verschieden die Regeln abschneiden. Wie sie sich ändern, wenn die Notbeschaffung teurer oder billiger wird, ist für die Regeln nicht untersucht. Die Bilder mit der Feier, den Kassen und dem Grillfest erklären nur; gemessen wurden die Zahlen.

Was Sie mitnehmen:

• Suchen Sie in jedem Ablauf zuerst die engste Stelle, bevor Sie irgendwo anders mehr Platz schaffen.
• Fragen Sie bei einer Faustregel, ob sie spätere Entscheidungen blockiert, die sich nicht mehr ändern lassen.
• Fragen Sie vor einer Spitze, ob früherer Vorrat sich gegen seine Lagerkosten lohnt.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Das Modell ist ein kapazitiertes Transportproblem mit Zwischenlagern (Transshipment) auf zufällig erzeugten Netzen; alle Zahlen gelten nur für die vier Beispielfälle unten.

• Netz: Werke, Verteilzentren (DC) und Filialen liegen zufällig auf einer quadratischen Karte (Werke oben, DCs in der Mitte, Filialen unten). Ein Werk \(p\) hat Produktionskosten je Einheit und eine Produktionskapazität. Ein DC \(k\) hat Umschlagkosten je Einheit und eine Durchsatzgrenze \(\bar d_k\). Eine Filiale \(s\) hat eine feste Nachfrage \(q_s\). Jede Strecke Werk → DC und DC → Filiale hat eine Kapazität (etwa eine Lkw-Ladung je Route und Periode), ihre Kosten je Einheit sind proportional zur euklidischen Entfernung. Es gibt ein einziges Gut; Mengen und Kapazitäten der Werke, DC-Durchsätze und Strecken sind ganzzahlig; die Lagerkapazität ist größer als der Durchsatz und nicht ganzzahlig.
• Notbeschaffung: Ein Hilfsknoten SRC speist die Werke und zusätzlich jede Filiale direkt, zu Strafkosten \(\mu = 500\) € je Einheit; ein Hilfsknoten SINK sammelt die Nachfrage. Die Höhe von \(\mu\) ist eine Setzung, sie soll über den Kosten jeder regulären Lieferung liegen. Die Menge, die über die Notbeschaffung kommt, heißt Fehlmenge.
• Mehrere Perioden: Ab zwei Perioden werden Werke, DC-Ein- und -Ausgänge und Filialen je Periode dupliziert; Produktions- und Durchsatzkapazität gelten je Periode. Ein DC kann Bestand über eine Lagerkante in die nächste Periode mitnehmen (Kosten \(h_k\) je Einheit und Periode, Kapazität \(\bar l_k\), größer als der Durchsatz). SRC und SINK bleiben je ein Knoten für alle Perioden.
• Drei Lieferregeln: Alle drei reservieren je Filiale ganze Routen Werk → DC → Filiale und nehmen eine Reservierung nie zurück. Eine Route gilt als frei, solange alle vier Kanten (SRC → Werk, Werk → DC-Eingang, DC-Eingang → DC-Ausgang, DC-Ausgang → Filiale) Restkapazität haben; die Menge ist das Minimum aus der Restkapazität der Route und der offenen Nachfrage. Bleibt Nachfrage ohne freie Route, geht der Rest in die Notbeschaffung. Bei mehreren Perioden werden die Perioden nacheinander bearbeitet, ohne Lagerkante. (1) Billigste Route (FCFS, first come first served): Filialen in der Reihenfolge ihrer Nummern, jede wählt die freie Route mit den geringsten Kosten je Einheit aus Produktion, Transport, Umschlag und Transport. (2) Größte Nachfrage zuerst: dieselbe Routenwahl, aber je Periode nach fallender Nachfrage. (3) Regional: Reihenfolge wie bei (1); jede Filiale nimmt das nächste DC mit freier Route und dort das billigste Werk.
• Drei exakte Löser: ein eigener Netzwerksimplex (Spannbaum-Basis, Big-M-Startlösung), OR-Tools SimpleMinCostFlow (Cost-Scaling-Push-Relabel) und HiGHS als allgemeines LP auf der Inzidenzmatrix. OR-Tools rechnet mit auf ein Zehntausendstel gerundeten Kosten und auf ganze Zahlen gerundeten Kapazitäten.
• Beispielfälle: vier erzeugte Netze, je ein Zufallsnetz mit festem Startwert. Normalfall: drei Werke, drei DCs, acht Filialen, eine Periode. DC-Engpass: gedrosselter Durchsatz der DCs. Knappe Werkskapazität: verringerte Produktionskapazität. Nachfragespitze: mehrere Perioden; in den beiden mittleren Perioden ist die Nachfrage um etwa die Hälfte höher. Alle Abstände unten sind Einzelwerte dieser vier Netze, keine Mittelwerte.

Die Formeln

Min-Cost-Flow. Gegeben ist ein gerichteter Graph \(G=(V,E)\). Die Knoten \(V\) sind die Werke, Ein- und Ausgang jedes DC, die Filialen und die Hilfsknoten SRC und SINK. Jede Kante \((i,j)\) hat Kosten \(c_{ij} \ge 0\) je Einheit und eine Kapazität \(u_{ij} \ge 0\). Jeder Knoten \(i\) hat eine Bilanz \(b_i\) (positiv: Angebot, negativ: Nachfrage, null: Durchgang) mit \(\sum_i b_i = 0\). Gesucht sind Flüsse \(x_{ij}\), die die Gesamtkosten minimieren:

\[\min \sum_{(i,j) \in E} c_{ij}\, x_{ij}\]

unter den Bilanzbedingungen

\[\sum_{j:(i,j)\in E} x_{ij} - \sum_{j:(j,i)\in E} x_{ji} = b_i \quad \forall i \in V\]

und den Kapazitätsgrenzen

\[0 \leq x_{ij} \leq u_{ij} \quad \forall (i,j) \in E\]

Zwei Kniffe. Erstens wird jedes DC \(k\) in einen Eingang \(k_{\text{in}}\) und einen Ausgang \(k_{\text{out}}\) gespalten, verbunden durch eine Kante mit Kapazität \(\bar d_k\); so wird aus der Knotenkapazität eine Kantenkapazität. Zweitens gleicht der Hilfsknoten SRC aus: \(b_{\text{SRC}} = \sum_s q_s\) und \(b_{\text{SINK}} = -\sum_s q_s\). Die Kante SRC → \(s\) (Notbeschaffung) hat Kosten \(\mu\) und Kapazität \(q_s\), die Kante \(s\) → SINK Kosten null und Kapazität \(q_s\).

Zeitexpansion. Für \(T\) Perioden kommt je DC \(k\) und Periodenübergang eine Lagerkante hinzu:

\[(k_{\text{out}}@t,\ k_{\text{out}}@(t{+}1)) \in E, \quad u = \bar{l}_k, \quad c = h_k \qquad t = 0, \ldots, T{-}2\]

Optimalität und Schattenpreis. Zu einer Basislösung (ein Spannbaum \(T_B\subseteq E\)) gehören Knotenpotenziale \(\pi_i\) mit \(\pi_i - \pi_j = c_{ij}\) auf allen Baumkanten. Die reduzierten Kosten einer Nicht-Baum-Kante sind

\[\bar{c}_{ij} = c_{ij} - \pi_i + \pi_j\]

Die Basislösung ist optimal, wenn \(\bar c_{ij} \ge 0\) für jede Nicht-Baum-Kante an der unteren Schranke \(x_{ij}=0\) und \(\bar c_{ij} \le 0\) an der oberen Schranke \(x_{ij}=u_{ij}\) gilt. Für eine volle Kante mit \(\bar c_{ij} < 0\) ist \(-\bar c_{ij}\) der Schattenpreis: die Kostenersparnis je zusätzlicher Einheit Kapazität, solange die Basis optimal bleibt.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo.

Warum jede Aufgabe lösbar ist und jede Filiale genau \(q_s\) erhält.

• Schritt 1: Die Bilanzen summieren sich zu null, denn SRC liefert \(\sum_s q_s\) und SINK nimmt ebenso viel ab; alle anderen Knoten sind Durchgang.
• Schritt 2: Schickt man für jede Filiale \(q_s\) Einheiten über die Notbeschaffungskante und weiter über die Kante nach SINK, sind alle Bilanzen und Kapazitäten erfüllt. Dieser Fluss ist zulässig und kostet \(\mu \sum_s q_s\); das Netz ist also unabhängig von allen Kapazitätsreglern lösbar.
• Schritt 3: SRC gibt genau \(\sum_s q_s\) ab, und die Kanten nach SINK fassen zusammen genau diese Menge. Also sind sie alle voll, und jede Filiale erhält genau \(q_s\), regulär oder über die Notbeschaffung. Die Fehlmenge einer Filiale ist der Fluss auf ihrer Notbeschaffungskante.

Warum die Fehlmenge im Normalfall mindestens 39 beträgt.

• Schritt 1: Alles, was nicht über die Notbeschaffung kommt, läuft durch ein DC. Die regulär gelieferte Menge ist daher höchstens \(\sum_k \bar d_k\).
• Schritt 2: Also gilt Fehlmenge \(\ge \sum_s q_s - \sum_k \bar d_k\). Im Normalfall liegt die Summe der Durchsatzgrenzen um 39 Einheiten unter der Gesamtnachfrage.
• Schritt 3: Der Gesamtplan erreicht diese Untergrenze: Seine Fehlmenge beträgt 39 Einheiten. Die Notbeschaffung kostet dann \(39 \cdot 500 = 19\,500\) €.

Warum eine zusätzliche ganze Einheit Kapazität höchstens \(\mu\) spart. Bedingungen: nichtnegative Kosten, ganzzahlige Kapazität der betrachteten Kante, Notbeschaffung wie oben.

• Schritt 1: Sei \(C(\gamma)\) das Kostenminimum, wenn die Kapazität einer Kante \(a\) gleich \(\gamma\) ist, und \(x'\) ein ganzzahliger optimaler Fluss für \(\gamma+1\). Ist \(x'_a \le \gamma\), dann ist \(x'\) auch für \(\gamma\) zulässig, und es spart nichts.
• Schritt 2: Sonst fließt mindestens eine Einheit über \(a\), auf einem Weg von SRC nach SINK (Flusszerlegung; Kreise lassen sich wegen \(c_{ij} \ge 0\) ohne Mehrkosten entfernen).
• Schritt 3: Nimmt man eine Einheit dieses Wegs heraus, fehlt sie bei der Filiale \(s\), an der er endet. Deren Notbeschaffungskante hat dafür Platz, weil dort höchstens \(q_s - 1\) Einheiten fließen. Füllt man die Lücke dort, ist der neue Fluss für \(\gamma\) zulässig und kostet höchstens \(\mu\) mehr als \(x'\), denn der entfernte Weg hatte nichtnegative Kosten.
• Folge: \(C(\gamma) - C(\gamma+1) \le \mu\). Das begrenzt zunächst nur den ganzen Schritt. Sind alle übrigen Daten ganzzahlig, liegen die Knickpunkte von \(C\) bei ganzen Kapazitäten (totale Unimodularität der Inzidenzmatrix); dann ist \(C\) zwischen \(\gamma\) und \(\gamma+1\) linear, und die rechte Steigung gleicht dem Schritt, liegt also höchstens bei \(\mu\). Gemessen liegen alle Schattenpreise im Beispiel unter 500 €.

Warum Vorrat bei flacher Nachfrage nie optimal ist. Bedingungen: In jeder Periode sind Nachfrage, Kosten und Kapazitäten gleich, und alle Lagerkosten \(h_k\) sind positiv.

• Schritt 1: Sei \(x^t\) der Fluss der Periode \(t\) ohne Lagerkanten und \(y^t \ge 0\) der Bestand von Periode \(t\) nach \(t+1\). An jedem DC-Ausgang gilt in Periode \(t\): Zufluss plus \(y^{t-1}\) gleich Abfluss plus \(y^t\), mit \(y^{-1} = y^{T-1} = 0\).
• Schritt 2: Summiert man über alle Perioden, heben sich die Bestände auf. Der Mittelwert \(\bar x = \frac{1}{T}\sum_t x^t\) erfüllt daher die Bilanzen einer einzelnen Periode, und wegen gleicher Kapazitäten auch deren Grenzen. Er ist für die Ein-Perioden-Aufgabe zulässig und kostet mindestens \(C^*\), deren Optimum.
• Schritt 3: Die Gesamtkosten sind die Summe der Periodenkosten plus Lagerkosten, also mindestens \(T\,C^*\) plus Lagerkosten. Unabhängige Ein-Perioden-Optima ohne Bestand kosten genau \(T\,C^*\). Jeder Bestand \(y^t > 0\) macht den Plan also strikt teurer.

Durchgerechnet: der Normalfall

Rechnung dieser Seite aus den Zahlen des Normalfalls und aus eigenen Nachrechnungen der vier Beispielfälle; was nicht aus der Demo stammt, steht in Worten.

• Anteil der Notbeschaffung: 19 500 € von 43 852 € sind knapp die Hälfte der Gesamtkosten. Jeder Prozentabstand in der Tabelle unten ist auf dieses Gesamt bezogen und deshalb kleiner, als er auf die übrigen Kosten bezogen wäre. Auf diese bezogen liegen die Abstände der drei Regeln im Normalfall zwischen knapp fünf und siebeneinhalb Prozent.
• Wer bleibt unbedient: Alle drei Regeln lassen im Normalfall dieselbe Menge unbedient wie der Gesamtplan, also die Untergrenze aus der Herleitung. Der Kostenabstand entsteht allein im Transport zwischen DCs und Filialen; Produktion, Umschlag und Transport Werk → DC sind bei Regeln und Gesamtplan gleich. Bei der billigsten Route und bei Regional trifft die ganze Fehlmenge die Filiale mit der höchsten Nummer, also die zuletzt bediente; der Gesamtplan verteilt sie auf zwei andere Filialen.
• Ausbau eines DC: Als Beispiel dient DC 1, das DC mit dem größten Durchsatz; die Nachrechnung erweitert es um 1 bis 60 Einheiten und löst jeweils neu. Sein Schattenpreis ist 329 € je Einheit. Baut man es um 50 % aus (von 101 auf 152 Einheiten), spart das 12 570 €, im Mittel 246 € je zusätzlicher Einheit. Die Nachrechnung zeigt den Grund: Schon bei 39 zusätzlichen Einheiten ist die Fehlmenge beseitigt und die ganze Ersparnis erreicht; der Durchschnitt je Einheit liegt dort etwas über dreihundertzwanzig Euro, also nahe am Schattenpreis. Die Ersparnis der einzelnen Einheit fällt vorher vom Schattenpreis bis knapp unter dreihundert Euro (letzte Einheit). Die übrigen zwölf Einheiten sparen nichts mehr und drücken den Durchschnitt.
• Die drei anderen Fälle: Im DC-Engpass, bei knapper Werkskapazität und in der Nachfragespitze lassen die Regeln mehr Nachfrage unbedient als das Optimum. Bei knapper Werkskapazität ist es rund das Sechsfache; die dafür zu zahlende Strafe ist größer als der ganze Kostenabstand, die Regeln sparen an anderen Kosten. Dort bleibt bei den Regeln ein Teil der Werkskapazität ungenutzt (bei einem Werk knapp ein Fünftel seiner Kapazität), während Nachfrage fehlt: Der Weg zu den letzten Filialen ist durch früher reservierte Mengen verstopft, und eine Reservierung wird nie zurückgenommen.

Befunde

Jede Zeile gilt für ein einziges Zufallsnetz je Beispielfall. Der Abstand einer Regel ist ihre Mehrkosten gegenüber dem Optimum, geteilt durch die Kosten des Optimums; beide enthalten die Notbeschaffung. In allen vier Fällen liefern die drei exakten Löser dieselben Kosten.

Beispielfall (Kosten des Optimums)	Billigste Route (FCFS)	Größte Nachfrage zuerst	Regional	Beste Regel
Normalfall (43 852 €)	3,95 %	4,13 %	2,59 %	Regional
DC-Engpass (68 043 €)	10,13 %	8,34 %	9,24 %	Größte Nachfrage zuerst
Knappe Werkskapazität (31 877 €)	28,07 %	28,80 %	26,15 %	Regional
Nachfragespitze (197 481 €)	10,37 %	13,16 %	13,15 %	Billigste Route (FCFS)

Die Regeln liegen zwischen 2,6 und 28,8 % über dem Optimum; ein Teil davon ist zusätzliche Fehlmenge (siehe unten). Regional liegt in drei der vier Fälle unter der billigsten Route, in der Nachfragespitze darüber. Größte Nachfrage zuerst gewinnt nur im DC-Engpass und ist im Normalfall, obwohl dort die DCs ebenfalls knapp sind, die schlechteste Regel.

Frage	Befund
Was kostet eine Änderung des Normalfalls? (43 852 €, Fehlmenge 39 Einheiten)	DC 1 um 50 % ausbauen: −12 570 € (−28,7 %), die Fehlmenge verschwindet. Werk 1 schließen: +2 648 € (+6,0 %), Fehlmenge 46. Werkskapazität aller Werke −20 %: +114 € (+0,3 %), Fehlmenge unverändert. Nachfrage aller Filialen +20 %: +25 049 € (+57,1 %), Fehlmenge 90. Notbeschaffung 100 % teurer: +19 500 € (39 mal 500), die Fehlmenge bleibt.
Wo sind die größten Schattenpreise? (Normalfall)	Durchsatz-Engpässe der DCs: DC 2 393,93 €, DC 3 380,00 €, DC 1 329,15 € je Einheit; danach Werk 3 → DC 1 mit 35,81 €.
Wie gut stimmt die Gegenprobe (Kapazität + 1, neu rechnen)?	Bei 19 von 20 geprüften Engpässen (die fünf größten je Fall) genau gleich. Im DC-Engpass spart DC 1 nachgerechnet 345,43 € statt 351,28 €: Der Schattenpreis liegt dort an einem Knickpunkt der Kostenfunktion, die Basis wechselt.
Schattenpreise in den anderen Fällen	Knappe Werkskapazität: die drei Werke mit 343,24 / 340,29 / 316,82 €. Nachfragespitze: DC 1 in Periode 3 mit 367,38 €. In allen vier Fällen liegen alle Schattenpreise unter 500 €.
Wie wächst die Laufzeit mit der Netzgröße?	Ein Netz je Größenstufe, bis 10 Werke, 14 DCs, 60 Filialen (100 Knoten, 1 124 Kanten, 295 Simplex-Iterationen). Laut Demo ist OR-Tools unter den exakten Lösern auf allen Stufen am schnellsten (von dieser Seite nicht nachgemessen), der eigene Simplex wächst mit Iterationen mal Netzgröße, HiGHS hat einen festen Startaufwand. Laufzeiten sind rechnerabhängig und schwanken von Lauf zu Lauf, die Iterationen nicht; Zeiten nennt diese Seite deshalb nicht.

Was die Messung zeigt und wo die Grenzen liegen

Was sie belegt:

• Die Kosten des Optimums und die Abstände der drei Regeln in den vier Fällen; sie sind nachgerechnet und stimmen mit der Tabelle überein. Dass keine Regel das Optimum unterbietet, folgt aus dessen Definition und wird geprüft.
• Die Übereinstimmung der drei exakten Löser in den vier Fällen und auf zufälligen kleinen Netzen; sie wird mit einer kleinen Toleranz geprüft, nicht auf die letzte Stelle.
• Der Satz „der Vorrat lohnt bei flacher Nachfrage nie“ für die Bedingungen der Herleitung; die Regeln nehmen wegen ihrer Bauart nie Bestand mit.

Was sie nicht belegt:

• Rangfolge der Regeln: Es sind vier Einzelnetze, ohne Streuung. Unterschiede von ein bis zwei Prozentpunkten innerhalb eines Netzes sagen nichts über andere Netze. Die Reihenfolge der Filialen ist ihre Nummer; andere Reihenfolgen sind nicht untersucht. Wie sich die Abstände mit der Höhe von \(\mu\) ändern, ist nicht untersucht: Die Was-wäre-wenn-Rechnung „Notbeschaffung verteuern“ löst nur den Gesamtplan.
• Abstände bestehen teils aus Strafe: In drei der vier Fälle lassen die Regeln mehr Nachfrage unbedient als das Optimum (Nachrechnung dieser Seite). Ein Teil ihres Abstands ist dort Strafe für zusätzliche Fehlmenge, kein Unterschied im Transport. Ob der Grund fehlendes Umplanen oder die Wahl der Reihenfolge ist, trennt die Messung nicht.
• Schattenpreise sind Steigungen: Sie gelten für eine zusätzliche Einheit, solange die Basis optimal bleibt. Geprüft sind nur die fünf größten Engpässe je Fall. Dass der Wert mit dem Ausbau fällt, liegt im Normalfall am Schließen der Lücke (Nachrechnung dieser Seite); für andere Fälle ist es nicht geprüft. Die Instanzparameter der vier Netze (Wertebereiche, Startwerte) stehen im Quelltext der Demo und werden hier nicht wiederholt.
• Vorrat: Die Regeln können keinen Bestand aufbauen. Die Nachfragespitze zeigt daher, was Vorausplanung bringen kann, nicht, was eine Regel mit eigener Vorratslogik brächte; eine solche ist nicht getestet.
• Modellgrenzen: ein einziges Gut, feste und bekannte Nachfrage, lineare Kosten ohne Fixkosten, keine Standortwahl, keine Mindestbestellmengen. Preise und Kapazitäten sind erzeugt, nicht gemessen. Rechenzeiten hängen vom Rechner ab.

Erweiterungen und Verweise

Verwandte Seiten und Demos dieser Website:

• Wie der Löser arbeitet: Die netzwerksimplex-demo zeigt Pivot für Pivot, wie ein Spannbaum mit Schattenpreisen die eintretende Kante bestimmt und Fluss um einen Kreis wandert.
• Andere Wege zum billigsten Fluss: Die ssp-demo füllt in jeder Runde den billigsten Weg im Restgraphen auf. Die cycle-canceling-demo verbessert einen zulässigen Fluss, indem sie Umleitungen löscht, die Geld sparen; das ist die Art von Umplanen, die den Regeln hier fehlt.
• Mehrere Warengruppen: Hier gibt es ein Gut. Die multicommodity-demo zeigt, was passiert, wenn mehrere Warengruppen dieselben Kanten teilen.
• Der Engpass als Grenze: Die Seite Maximaler Fluss verständlich erklärt behandelt, warum der Engpass eines Netzes festlegt, wie viel Ware hindurchpasst.

Quellen

• Ahuja, Magnanti, Orlin (1993): Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Kapitel 11 (Netzwerksimplex).
• Quelltext, Beispielfälle und Tests der Demo: github.com/sebastian-hanisch/network-flow-demo.

Die genannte Arbeit wurde für diese Seite nicht nachgeschlagen; die Angabe stammt aus der Demo und ist nicht geprüft. Die Befundtabellen geben die Messungen der Demo wieder; Herleitungen und Nachrechnungen sind Rechnungen dieser Seite.