Netzwerkmodelle

Netzwerkmodelle (im Operations Research; engl. Network models) sind eine Klasse mathematischer Modelle, die ein Problem in Form eines Graphen (Netzwerks) darstellen, in dem Knoten Objekte oder Zustände und Kanten (Bögen) Verbindungen oder Prozesse zwischen ihnen repräsentieren. Im Kontext der Optimierung wird unter einem Netzwerk oft ein gerichteter Graph verstanden, der im Operations Research direkt als „Netzwerk“ bezeichnet wird. Die Knoten eines solchen Netzwerks werden als Knoten und die Kanten als Bögen bezeichnet.

Netzwerkmodelle sind ein leistungsstarkes Werkzeug zur Analyse und Optimierung komplexer Systeme in Bereichen wie Logistik, Telekommunikation, Projektmanagement und Finanzen. Ihre Stärke liegt in ihrem hohen Abstraktionsgrad: Ein Knoten kann eine Stadt, einen Computer-Router oder eine Projektphase repräsentieren, und ein Bogen eine Straße, einen Kommunikationskanal oder einen technologischen Vorgang.

Definition und Terminologie

Die Grundlage für Netzwerkmodelle bildet die Graphentheorie. Zentrale Begriffe sind:

• Flussnetzwerk (engl. flow network): ein gerichteter Graph, in dem jede Kante eine Kapazität (capacity) und einen Fluss (flow) besitzt. Im Graphen werden zwei spezielle Knoten unterschieden: eine Quelle (source), aus der der Fluss entspringt, und eine Senke (sink), in die er mündet.
• Flusserhaltungssatz: Für jeden Knoten, der weder Quelle noch Senke ist, muss der gesamte eingehende Fluss dem gesamten ausgehenden Fluss entsprechen. Diese Bedingung ist das diskrete Analogon physikalischer Erhaltungssätze.
• Netzwerkplanung: Ein Modell, das ein Projekt als einen Komplex von miteinander verbundenen Vorgängen (Bögen) und Ereignissen (Knoten) darstellt. Solche Netzwerke sind gerichtete azyklische Graphen, was die Reihenfolge der Arbeitsausführung widerspiegelt.

Schlüsseleigenschaften und Theoreme

Netzwerkmodelle weisen eine Reihe besonderer Eigenschaften auf, die den Einsatz hocheffizienter Algorithmen zu ihrer Lösung ermöglichen.

• Ganzzahligkeit der Lösungen: Viele Netzwerkoptimierungsprobleme (z. B. das Problem des maximalen Flusses oder des kürzesten Weges) besitzen die Eigenschaft der totalen Unimodularität der Nebenbedingungsmatrix. Dadurch ist die optimale Lösung, die mit Methoden der linearen Programmierung gefunden wird, ebenfalls ganzzahlig, sofern die Aufgabenparameter (Kapazitäten, Längen) ganzzahlig sind, ohne dass zusätzliche Ganzzahligkeitsbedingungen erforderlich sind.
• Max-Flow-Min-Cut-Theorem: Ein zentrales Ergebnis der Flusstheorie. Es besagt, dass der maximale Wert eines Flusses von einer Quelle zu einer Senke gleich der minimalen Kapazität aller Schnitte ist, die die Quelle von der Senke trennen. Dieses Theorem liefert ein Optimalitätskriterium für Flüsse und bildet die Grundlage vieler Algorithmen.
• Optimalitätsprinzip für kürzeste Wege: Wenn ein Pfad von Punkt A nach Punkt C der kürzeste ist, dann ist auch jeder seiner Teilabschnitte (z. B. von einem Zwischenpunkt B nach C) der kürzeste Pfad zwischen den entsprechenden Knoten. Diese Eigenschaft, die der dynamischen Programmierung zugrunde liegt, sichert die Korrektheit von Algorithmen wie dem Dijkstra-Algorithmus.
• Eigenschaften des minimalen Spannbaums (MST):
• Schnitt-Eigenschaft: Für jeden Schnitt eines Graphen gehört die Kante mit dem minimalen Gewicht, die den Schnitt überquert, zu mindestens einem minimalen Spannbaum.
• Zyklen-Eigenschaft: In jedem Zyklus eines Graphen gehört die Kante mit dem maximalen Gewicht zu keinem minimalen Spannbaum.

Auf diesen Eigenschaften beruht die Korrektheit der „gierigen“ Algorithmen von Prim und Kruskal.

Grundlegende Probleme der Netzwerkoptimierung

• Problem des kürzesten Weges: Finden eines Pfades mit minimaler Gesamtlänge (Gewicht) zwischen zwei gegebenen Knoten. Wird mit dem Dijkstra-Algorithmus (für nicht-negative Gewichte) oder dem Bellman-Ford-Algorithmus (für beliebige Gewichte) gelöst.
• Problem des maximalen Flusses: Bestimmung des maximal möglichen Flusses von einer Quelle zu einer Senke bei gegebenen Bogenkapazitäten. Eine klassische Lösungsmethode ist der Ford-Fulkerson-Algorithmus.
• Problem des minimalen Spannbaums: Finden eines Teilgraphen, der alle Knoten des Netzwerks verbindet und eine minimale Summe der Kantenkosten aufweist.
• Methode des kritischen Pfades (CPM): In Netzwerkplanungsmodellen die längste Abfolge von Vorgängen zu bestimmen, die die minimal mögliche Gesamtdauer des Projekts festlegt. Vorgänge auf diesem Pfad haben keine Pufferzeit.

Beispiele

• Kürzester Weg: Die Suche nach der optimalen Route durch ein Navigationssystem zwischen zwei Punkten auf einer Stadtkarte, bei der Knoten Kreuzungen und Bögen Straßen mit Gewichten sind, die der Länge oder Fahrzeit entsprechen.
• Maximaler Fluss: Die Bestimmung der maximalen Durchflusskapazität eines Rohrleitungsnetzes, bei dem Pumpstationen Knoten und Rohre Bögen mit begrenzter Kapazität sind.
• Minimaler Spannbaum: Die Planung eines Kommunikationsnetzes (z. B. die Verlegung von Glasfaserkabeln), um mehrere Städte mit minimaler Gesamtkabellänge zu verbinden.
• Kritischer Pfad: In einem Hausbauprojekt, bei dem die Arbeiten (Fundamentlegung, Wände errichten, Dachmontage) eine bestimmte Dauer und technologische Abhängigkeiten haben, bestimmt der kritische Pfad die minimale Fertigstellungszeit. Jede Verzögerung einer Arbeit auf diesem Pfad führt zu einer Verzögerung des gesamten Projekts.

Siehe auch

• Operations Research
• Graphentheorie
• Transportproblem
• Methode des kritischen Pfades
• PERT