Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Wo lagern, wo liefern, was kostet's? Das Transport-Problem ist eines der ältesten OR-Probleme (Kantorovich 1939, Hitchcock 1941) und Klausurstandard in 6/8 OR-Programmen.
Klausur-Tipp: Bei "Lösen Sie das Transport-Problem" IMMER 2-Phasen-Ansatz: 1) Start-Lösung mit Nordwest-Ecke (schnell für Klausur) oder Vogel (besser), 2) MODI-Iteration für Optimum. Balanciertheit prüfen — bei Ungleichgewicht IMMER Dummy einfügen (Kosten 0).
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Wo lagern, wo liefern, was kostet's? Das Transport-Problem ist eines der ältesten OR-Probleme (Kantorovich 1939, Hitchcock 1941) und Klausurstandard in 6/8 OR-Programmen.
Transport-Problem: Wieviel von Quelle
i(mLager) an Senkej(nKunden) liefern, um Gesamttransportkosten zu minimieren — bei gegebenem Angebot und Bedarf?
min z = Σ_(i=1)^(m) Σ_(j=1)ⁿ c_(ij) x_(ij)
unter:
Σ_(j=1)ⁿ x_(ij) = a_i (Angebot in Quelle i); Σ_(i=1)^(m) x_(ij) = b_j (Bedarf in Senke j); x_(ij) ≥ 0
x_(ij) = Liefermenge von i nach jc_(ij) = Transportkosten pro Einheita_i = Angebot in Quelle ib_j = Bedarf in Senke jBalanciertheits-Bedingung:
Σ_i a_i = Σ_j b_j
Bei Ungleichgewicht: Dummy-Quelle/Senke mit Kosten 0 einfügen.
Schnellste Heuristik:
(1, 1)).x_(11) = min(a₁, b₁).a₁ erschöpft → gehe nach unten. Wenn b₁ erschöpft → gehe nach rechts.Vorteil: Sehr schnell. Nachteil: Berücksichtigt keine Kosten — Start-Lösung meist weit vom Optimum.
Bessere Start-Heuristik:
Vorteil: Oft schon nahe Optimum. Nachteil: Aufwendiger als Nordwest-Ecke.
Wähle das Feld mit den geringsten Kosten + weise maximal mögliche Menge zu. Wiederhole.
MODI = Modified Distribution Method. Iterative Verbesserung der Start-Lösung:
u_i, v_j für alle Basis-Felder via u_i + v_j = c_(ij).u₁ = 0 als Ausgangspunkt.Δ_(ij) = c_(ij) - (u_i + v_j).Δ_(ij) ≥ 0 → Optimal.Δ_(ij) in Basis auf → Kreis (Stepping Stone Path).Allgemeines Netzwerk-Fluss-Problem:
G = (V, E)c_(ij) und Kapazitäten u_(ij)s, Senke ts, tMaximiere Fluss von
snachtunter Kapazitäts-Beschränkungen.
Algorithmus: Ford-Fulkerson (1956)
s → t im Residual-Graph.Max-Flow-Min-Cut-Theorem: max flow = min cut. Der minimale Schnitt im Graph entspricht dem maximalen Fluss.
Minimiere Transportkosten bei vorgegebenem Fluss-Volumen.
Verallgemeinerung des Transport-Problems mit Zwischen-Knoten.
Spezialfall von Netzwerkflüssen mit Einheitsfluss:
O((V + E) log V) mit Min-HeapO(VE)O(V³)| Problem | Anwendung |
|---|---|
| Transport | Lager → Filialen, Werk → Kunde |
| Assignment | Mitarbeiter → Aufgaben (n×n, Hungarian Algorithm) |
| Max-Flow | Netzwerk-Bandbreite, Pipeline-Kapazität |
| Min-Cost-Flow | Lieferketten mit Zwischenlager |
| Kürzeste Wege | GPS-Navigation, Internet-Routing |
| Travelling Salesman | Tourplanung Lieferdienste (NP-schwer!) |
1. Balanciertheit prüfen: Σ a_i = Σ b_j. Sonst Dummy einfügen.
2. 2-Phasen-Ansatz: Start-Heuristik (Nordwest/Vogel/MinKosten) → MODI-Verbesserung.
3. Nordwest-Ecke ignoriert Kosten — schnell aber nicht-optimal. Vogel ist besser.
4. MODI-Test auf Optimalität: alle Δ_(ij) ≥ 0 → optimal.
5. Anzahl Basis-Felder: m + n - 1 (sonst entartet).
6. Ford-Fulkerson für Max-Flow — wiederhole augmentierende Pfade.
1. Unbalanciertes Problem nicht erkannt. Σ a ≠ Σ b → ohne Dummy keine Lösung. Dummy-Quelle bei Über-Bedarf, Dummy-Senke bei Über-Angebot, Kosten 0.
2. Nordwest-Ecke als Endlösung sehen. Nordwest ist NUR START. Optimum braucht MODI/Stepping-Stone.
3. Entartung übersehen. Wenn weniger als m + n - 1 Basis-Felder → entartet. Mit ε-Methode auffüllen.
4. MODI-Dual-Variablen falsch berechnen. u₁ = 0 setzen, dann iterativ u_i + v_j = c_(ij) für Basis-Felder.
5. Reduzierte Kosten falsch interpretieren. Δ_(ij) = c_(ij) - (u_i + v_j). Wenn negativ → Verbesserung möglich. Wenn ≥ 0 für alle → optimal.
6. Transport vs. Max-Flow verwechseln. Transport: feste Mengen, min Kosten. Max-Flow: kein fester Bedarf, max Fluss.
3 Lager (Quellen) → 4 Filialen (Senken). Toggle Nordwest-Ecke vs. Vogel-Approximation um die Kosten-Unterschiede zu sehen.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei "Lösen Sie das Transport-Problem" IMMER 2-Phasen-Ansatz: 1) Start-Lösung mit Nordwest-Ecke (schnell für Klausur) oder Vogel (besser), 2) MODI-Iteration für Optimum. Balanciertheit prüfen — bei Ungleichgewicht IMMER Dummy einfügen (Kosten 0).
6 Aufgaben zu Modell, Methoden und Netzwerkflüssen.
Klausurfragen mit Lösungen (6)
Antwort: Σ Angebot = Σ Bedarf (Balanciertheit)
Erklärung: Klassisches Transport-Problem ist BALANCIERT: Gesamt-Angebot = Gesamt-Bedarf. Bei Ungleichgewicht: Dummy-Quelle (wenn Bedarf > Angebot) oder Dummy-Senke (wenn Angebot > Bedarf) mit Kosten 0 einfügen. Anzahl Quellen vs. Senken können beliebig sein (m × n).
Antwort: Vogel-Approximation
Erklärung: Vogel-Approximation (VAM) berechnet Strafkosten pro Zeile/Spalte (2. günstigste − günstigste) und priorisiert Zeilen/Spalten mit hoher Strafe. Berücksichtigt damit Kosten und findet oft schon Optimum oder fast-Optimum. Nordwest-Ecke ignoriert Kosten komplett — wird nur durch Position bestimmt.
Zuordnungen:
Erklärung: Transport-Methoden: Nordwest = Start-Heuristik (schnell, ignoriert Kosten). MODI = Optimierung (Modified Distribution Method, iterativ verbessern). Ford-Fulkerson = Max-Flow-Algorithmus mit augmentierenden Pfaden. Dijkstra = Kürzeste-Wege-Algorithmus für nicht-negative Kanten.
Typ: Zuordnung
Antwort: 6 Felder
Erklärung: Anzahl Basis-Felder = m + n − 1 = 3 + 4 − 1 = 6. Diese Formel gilt für nicht-entartete Transport-Probleme. Bei weniger als 6 → entartet, dann Epsilon-Methode anwenden. Klausur-Falle: m · n (Anzahl Felder gesamt = 12) verwechseln mit m + n − 1.
Antwort: Wahr
Erklärung: RICHTIG. Max-Flow-Min-Cut-Theorem (Ford & Fulkerson 1956): max flow von s nach t = min cut zwischen s und t. Ein Schnitt teilt das Netzwerk in zwei Teile (s-Seite + t-Seite), die Schnitt-Kapazität ist die Summe der Kanten-Kapazitäten von s-Seite nach t-Seite. Dieser Satz erlaubt Lösung des Max-Flow-Problems durch Suche nach minimalem Schnitt.
Typ: Wahr/Falsch
Antwort: Bellman-Ford
Erklärung: Bellman-Ford (1958) kann negative Kanten — findet kürzesten Pfad in O(VE). Dijkstra geht NUR bei nicht-negativen Kanten (sonst können bereits 'final' gesetzte Knoten überschrieben werden). Floyd-Warshall (1962) kann auch negative Kanten (für alle Paare, O(V³)). Negative Zyklen müssen ausgeschlossen sein — sonst gibt es keinen kürzesten Pfad.
6 typische Klausurfragen zu Algorithmen, MODI und Netzwerkflüssen.
Klausurfragen mit Lösungen (6)
Antwort: Lester Ford Jr. & Delbert Fulkerson
Erklärung: Ford-Fulkerson-Algorithmus für Max-Flow: Lester Ford Jr. & Delbert Fulkerson, RAND Corporation 1956. Wichtig: Bellman-Ford ist ANDERES Paar (Richard Bellman + Lester Ford Jr.) für kürzeste Wege. Ford Jr. war in beiden Algorithmen-Paaren beteiligt.
Antwort: Dummy-Senke mit Kosten 0 einfügen
Erklärung: Σ Angebot > Σ Bedarf: Lager produzieren MEHR als benötigt → fiktive Dummy-Senke mit Kosten c = 0 für alle Quellen + Bedarf = Überschuss. Bei Σ Bedarf > Σ Angebot umgekehrt: Dummy-Quelle. Mit Dummy ist das Problem balanciert + lösbar.
Lösungen pro Lücke:
Erklärung: MODI: 1) u_1 = 0 setzen (willkürlich), 2) für alle Basis-Felder u_i + v_j = c_ij lösen → Werte für alle u_i, v_j, 3) reduzierte Kosten Δ_ij = c_ij − (u_i + v_j) für Nicht-Basis berechnen, 4) wenn alle Δ_ij ≥ 0 → Optimum. Wenn ein Δ_ij < 0 → bessere Lösung möglich, Stepping-Stone-Pfad.
Typ: Lückentext
Richtige Reihenfolge:
Erklärung: Transport-Algorithmus: 1) Balanciertheit (Σa = Σb) prüfen + ggf. Dummy. 2) Start-Lösung mit Heuristik (Nordwest/Vogel). 3) MODI-Optimalitäts-Test (alle reduzierten Kosten ≥ 0?). 4) Wenn nicht optimal: Stepping-Stone-Pfad finden + Verbesserung. Iteriere 3+4 bis Optimum.
Typ: Reihenfolge
Antwort: Travelling Salesman Problem
Erklärung: TSP (Travelling Salesman) ist NP-schwer — keine polynomiale exakte Lösung bekannt. Andere drei sind polynomial: Transport (Simplex O(n³) im Praxis), Max-Flow (Ford-Fulkerson polynomial mit Edmonds-Karp), Assignment (Hungarian O(n³)). Wichtige Klausur-Unterscheidung: einfache Netzwerk-Probleme sind 'leicht', TSP fängt das NP-Schwer-Reich an.
Antwort: Falsch
Erklärung: FALSCH. Nordwest-Ecke liefert nur eine GÜLTIGE Start-Lösung, NICHT die optimale. Sie ignoriert Kosten komplett — wird nur durch Position (oben-links) bestimmt. Optimum braucht Phase 2 (MODI, Stepping-Stone). Klassischer Klausur-Fehler. Vogel-Approximation findet oft direkt das Optimum oder kommt sehr nahe — aber auch hier ist die finale Optimalitäts-Prüfung mit MODI nötig.
Typ: Wahr/Falsch