/
/
·
·
/
/
·
·
  • Einführung
  • Die Idee in einem Satz
  • Mathematisches Modell
  • Lösungsverfahren: 2-Phasen-Ansatz
  • Netzwerkflüsse, Verallgemeinerung
  • Kürzeste-Wege-Probleme
  • Anwendungen
  • Klausur-Faustregeln
  • Häufige Stolpersteine
ThemenBusiness AnalyticsTransport-Problem & Netzwerk-Flüsse
Business Analytics·4Lerneinheiten·20min·Stand17.07.2026

Transport-Problem & Netzwerk-Flüsse.

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 iii (mmm Lager) an Senke jjj (nnn Kunden) liefern, um Gesamttransportkosten zu minimieren, bei gegebenem Angebot und Bedarf?

min⁡  z=∑i=1m∑j=1ncij xij\min\;z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} \, x_{ij}minz=i=1∑m​j=1∑n​cij​xij​

unter:

∑j=1nxij=ai(Angebot in Quelle i)∑i=1mxij=bj(Bedarf in Senke j)xij≥0\begin{aligned} \sum_{j=1}^{n} x_{ij} &= a_i \quad (\text{Angebot in Quelle } i) \\ \sum_{i=1}^{m} x_{ij} &= b_j \quad (\text{Bedarf in Senke } j) \\ x_{ij} &\ge 0 \end{aligned}j=1∑n​xij​i=1∑m​xij​xij​​=ai​(Angebot in Quelle i)=bj​(Bedarf in Senke j)≥0​

Variablen:

  • xijx_{ij}xij​ = Liefermenge von iii nach jjj
  • cijc_{ij}cij​ = Transportkosten pro Einheit
  • aia_iai​ = Angebot in Quelle iii
  • bjb_jbj​ = Bedarf in Senke jjj

Balanciertheits-Bedingung:

∑iai=∑jbj\sum_i a_i = \sum_j b_ji∑​ai​=j∑​bj​

Bei Ungleichgewicht: Dummy-Quelle/Senke mit Kosten 0 einfügen.

Phase 1, Start-Lösung (zulässige Basis-Lösung)

Nordwest-Ecke-Methode

Schnellste Heuristik:

  1. Starte oben links (Position (1,1)(1, 1)(1,1)).
  2. Liefere x11=min⁡(a1,b1)x_{11} = \min(a_1, b_1)x11​=min(a1​,b1​).
  3. Wenn a1a_1a1​ erschöpft → gehe nach unten. Wenn b1b_1b1​ erschöpft → gehe nach rechts.
  4. Wiederhole bis alle Quellen/Senken erschöpft.

Vorteil: Sehr schnell. Nachteil: Berücksichtigt keine Kosten, Start-Lösung meist weit vom Optimum.

Vogel-Approximation (VAM)

Bessere Start-Heuristik:

  1. Für jede Zeile + Spalte: berechne Strafkosten = (2. günstigste − günstigste) Kosten.
  2. Wähle Zeile/Spalte mit höchster Strafkosten.
  3. In dieser Zeile/Spalte: weise dem günstigsten Feld die maximal mögliche Menge zu.
  4. Streiche erschöpfte Zeilen/Spalten.
  5. Wiederhole.

Vorteil: Oft schon nahe Optimum. Nachteil: Aufwendiger als Nordwest-Ecke.

Minimal-Kosten-Methode (Spalten-/Matrixminimum)

Wähle das Feld mit den geringsten Kosten + weise maximal mögliche Menge zu. Wiederhole.

Phase 2, Optimierung (MODI-Verfahren)

MODI = Modified Distribution Method. Iterative Verbesserung der Start-Lösung:

  1. Berechne Dual-Variablen ui,vju_i, v_jui​,vj​ für alle Basis-Felder via ui+vj=ciju_i + v_j = c_{ij}ui​+vj​=cij​.
  2. Setze u1=0u_1 = 0u1​=0 als Ausgangspunkt.
  3. Für Nicht-Basis-Felder: berechne reduzierte Kosten Δij=cij−(ui+vj)\Delta_{ij} = c_{ij} - (u_i + v_j)Δij​=cij​−(ui​+vj​).
  4. Wenn alle Δij≥0\Delta_{ij} \ge 0Δij​≥0 → Optimal.
  5. Sonst: nimm Feld mit kleinstem Δij\Delta_{ij}Δij​ in Basis auf → Kreis (Stepping Stone Path).
  6. Verschiebe Menge entlang Kreis → neue Basis-Lösung.

Allgemeines Netzwerk-Fluss-Problem:

  • Gerichteter Graph G=(V,E)G = (V, E)G=(V,E)
  • Kantenkosten cijc_{ij}cij​ und Kapazitäten uiju_{ij}uij​
  • Quelle sss, Senke ttt
  • Fluss-Erhaltung in allen Knoten außer s,ts, ts,t

Maximum-Fluss-Problem

Maximiere Fluss von sss nach ttt unter Kapazitäts-Beschränkungen.

Algorithmus: Ford-Fulkerson (1956)

  1. Finde augmentierenden Pfad s→ts → ts→t im Residual-Graph.
  2. Verschiebe maximalen Fluss entlang Pfad.
  3. Wiederhole bis kein Pfad mehr existiert.

Max-Flow-Min-Cut-Theorem: max flow=min cut\text{max flow} = \text{min cut}max flow=min cut. Der minimale Schnitt im Graph entspricht dem maximalen Fluss.

Min-Cost-Flow-Problem

Minimiere Transportkosten bei vorgegebenem Fluss-Volumen.

Verallgemeinerung des Transport-Problems mit Zwischen-Knoten.

Spezialfall von Netzwerkflüssen mit Einheitsfluss:

  • Dijkstra (1959): nicht-negative Kanten, O((V+E)log⁡V)O((V + E) \log V)O((V+E)logV) mit Min-Heap
  • Bellman-Ford (1958): erlaubt negative Kanten, O(VE)O(VE)O(VE)
  • Floyd-Warshall (1962): alle Paare kürzeste Wege, O(V3)O(V^3)O(V3)
  • A* (1968): heuristische Suche mit Schätzfunktion
ProblemAnwendung
TransportLager → Filialen, Werk → Kunde
AssignmentMitarbeiter → Aufgaben (n×n, Hungarian Algorithm)
Max-FlowNetzwerk-Bandbreite, Pipeline-Kapazität
Min-Cost-FlowLieferketten mit Zwischenlager
Kürzeste WegeGPS-Navigation, Internet-Routing
Travelling SalesmanTourplanung Lieferdienste (NP-schwer!)

1. Balanciertheit prüfen: ∑ai=∑bj\sum a_i = \sum b_j∑ai​=∑bj​. 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\Delta_{ij} \ge 0Δij​≥0 → optimal.

5. Anzahl Basis-Felder: m+n−1m + n - 1m+n−1 (sonst entartet).

6. Ford-Fulkerson für Max-Flow, wiederhole augmentierende Pfade.

1. Unbalanciertes Problem nicht erkannt. ∑a≠∑b\sum a \neq \sum b∑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−1m + n - 1m+n−1 Basis-Felder → entartet. Mit ϵ\epsilonϵ-Methode auffüllen.

4. MODI-Dual-Variablen falsch berechnen. u1=0u_1 = 0u1​=0 setzen, dann iterativ ui+vj=ciju_i + v_j = c_{ij}ui​+vj​=cij​ für Basis-Felder.

5. Reduzierte Kosten falsch interpretieren. Δij=cij−(ui+vj)\Delta_{ij} = c_{ij} - (u_i + v_j)Δij​=cij​−(ui​+vj​). 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.

Lade Visualisierung...

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

Wenn du fertig bist: jetzt üben.

Aktives Abrufen festigt Wissen schneller als nochmal lesen.

War das hilfreich?

Verwandte Themen

  • Marketing-Konzept & Marketing-Mix (4P/7P)
  • Was ist Wirtschaftsinformatik?
  • BPMN 2.0: Grundelemente
  • Anwendungssysteme, Klassifikation
  • IT-Strategie & Business-IT-Alignment

Tools

Bald: Karteikarten · Spaced-Repetition · Mind-Map-Export

Fachliche Qualität
Noch nicht klassifiziertNoch nicht geprüft.

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.

Klausur-ÜbersichtKomplette Übersicht: alle Tabs als linearer Text zum Lernen
▾

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).

Inhalt dieser Übersicht

  1. Erklärung(Erklärung)
  2. Interaktiv verstehen(Visualisierung / Interaktiv)
  3. Praxis-Übung(Quiz / Klausurfragen)
  4. Klausur-Quiz(Quiz / Klausurfragen)
Teil 1·Erklärung

Erklärung

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.

Die Idee in einem Satz

Transport-Problem: Wieviel von Quelle i (m Lager) an Senke j (n Kunden) liefern, um Gesamttransportkosten zu minimieren, bei gegebenem Angebot und Bedarf?

Mathematisches Modell

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

Variablen:

  • x_(ij) = Liefermenge von i nach j
  • c_(ij) = Transportkosten pro Einheit
  • a_i = Angebot in Quelle i
  • b_j = Bedarf in Senke j

Balanciertheits-Bedingung: Σ_i a_i = Σ_j b_j

Bei Ungleichgewicht: Dummy-Quelle/Senke mit Kosten 0 einfügen.

Lösungsverfahren: 2-Phasen-Ansatz

Phase 1, Start-Lösung (zulässige Basis-Lösung)

Nordwest-Ecke-Methode

Schnellste Heuristik:

  1. Starte oben links (Position (1, 1)).
  2. Liefere x_(11) = min(a₁, b₁).
  3. Wenn a₁ erschöpft → gehe nach unten. Wenn b₁ erschöpft → gehe nach rechts.
  4. Wiederhole bis alle Quellen/Senken erschöpft.

Vorteil: Sehr schnell. Nachteil: Berücksichtigt keine Kosten, Start-Lösung meist weit vom Optimum.

Vogel-Approximation (VAM)

Bessere Start-Heuristik:

  1. Für jede Zeile + Spalte: berechne Strafkosten = (2. günstigste − günstigste) Kosten.
  2. Wähle Zeile/Spalte mit höchster Strafkosten.
  3. In dieser Zeile/Spalte: weise dem günstigsten Feld die maximal mögliche Menge zu.
  4. Streiche erschöpfte Zeilen/Spalten.
  5. Wiederhole.

Vorteil: Oft schon nahe Optimum. Nachteil: Aufwendiger als Nordwest-Ecke.

Minimal-Kosten-Methode (Spalten-/Matrixminimum)

Wähle das Feld mit den geringsten Kosten + weise maximal mögliche Menge zu. Wiederhole.

Phase 2, Optimierung (MODI-Verfahren)

MODI = Modified Distribution Method. Iterative Verbesserung der Start-Lösung:

  1. Berechne Dual-Variablen u_i, v_j für alle Basis-Felder via u_i + v_j = c_(ij).
  2. Setze u₁ = 0 als Ausgangspunkt.
  3. Für Nicht-Basis-Felder: berechne reduzierte Kosten Δ_(ij) = c_(ij) - (u_i + v_j).
  4. Wenn alle Δ_(ij) ≥ 0 → Optimal.
  5. Sonst: nimm Feld mit kleinstem Δ_(ij) in Basis auf → Kreis (Stepping Stone Path).
  6. Verschiebe Menge entlang Kreis → neue Basis-Lösung.

Netzwerkflüsse, Verallgemeinerung

Allgemeines Netzwerk-Fluss-Problem:

  • Gerichteter Graph G = (V, E)
  • Kantenkosten c_(ij) und Kapazitäten u_(ij)
  • Quelle s, Senke t
  • Fluss-Erhaltung in allen Knoten außer s, t
Maximum-Fluss-Problem

Maximiere Fluss von s nach t unter Kapazitäts-Beschränkungen.

Algorithmus: Ford-Fulkerson (1956)

  1. Finde augmentierenden Pfad s → t im Residual-Graph.
  2. Verschiebe maximalen Fluss entlang Pfad.
  3. Wiederhole bis kein Pfad mehr existiert.

Max-Flow-Min-Cut-Theorem: max flow = min cut. Der minimale Schnitt im Graph entspricht dem maximalen Fluss.

Min-Cost-Flow-Problem

Minimiere Transportkosten bei vorgegebenem Fluss-Volumen.

Verallgemeinerung des Transport-Problems mit Zwischen-Knoten.

Kürzeste-Wege-Probleme

Spezialfall von Netzwerkflüssen mit Einheitsfluss:

  • Dijkstra (1959): nicht-negative Kanten, O((V + E) log V) mit Min-Heap
  • Bellman-Ford (1958): erlaubt negative Kanten, O(VE)
  • Floyd-Warshall (1962): alle Paare kürzeste Wege, O(V³)
  • A* (1968): heuristische Suche mit Schätzfunktion

Anwendungen

ProblemAnwendung
TransportLager → Filialen, Werk → Kunde
AssignmentMitarbeiter → Aufgaben (n×n, Hungarian Algorithm)
Max-FlowNetzwerk-Bandbreite, Pipeline-Kapazität
Min-Cost-FlowLieferketten mit Zwischenlager
Kürzeste WegeGPS-Navigation, Internet-Routing
Travelling SalesmanTourplanung Lieferdienste (NP-schwer!)

Klausur-Faustregeln

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.

Häufige Stolpersteine

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.

Teil 2·Visualisierung / Interaktiv

Interaktiv verstehen

Transport-Problem als Bipartit-Graph

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).

Teil 3·Quiz / Klausurfragen

Praxis-Übung

Transport-Problem, Praxis-Übung

6 Aufgaben zu Modell, Methoden und Netzwerkflüssen.

Klausurfragen mit Lösungen (6)

F1.Welche Voraussetzung muss für ein klassisches Transport-Problem erfüllt sein?

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).

F2.Welche Heuristik berücksichtigt Kosten beim Erstellen der Start-Lösung?

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.

F3.Ordne Methode dem Algorithmus zu.

Zuordnungen:

  • Nordwest-Ecke → Schnelle Start-Heuristik (oben-links beginnend)
  • MODI → Optimierungs-Schritt: u_i + v_j = c_ij + reduzierte Kosten
  • Ford-Fulkerson → Maximum-Fluss via augmentierende Pfade
  • Dijkstra → Kürzester Pfad mit nicht-negativen Kanten, O((V+E) log V)

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

F4.Bei einem Transport-Problem mit 3 Quellen und 4 Senken: Wieviele Basis-Felder hat eine nicht-entartete Lösung?

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.

F5.Das Max-Flow-Min-Cut-Theorem besagt, dass der maximale Fluss in einem Netzwerk gleich der Kapazität des minimalen Schnittes ist.

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

F6.Welcher Algorithmus findet kürzeste Pfade in einem Netzwerk mit NEGATIVEN Kantengewichten?

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.

Teil 4·Quiz / Klausurfragen

Klausur-Quiz

Transport-Problem, Klausur-Quiz

6 typische Klausurfragen zu Algorithmen, MODI und Netzwerkflüssen.

Klausurfragen mit Lösungen (6)

F1.Wer entwickelte den Ford-Fulkerson-Algorithmus?

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.

F2.Bei einem unbalancierten Transport-Problem (Σ Angebot > Σ Bedarf), wie löst man es?

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.

F3.In der MODI-Methode setzt man {{1}} = 0 als Ausgangspunkt. Für jedes Basis-Feld gilt {{2}} = c_ij. Reduzierte Kosten für Nicht-Basis-Felder: Δ_ij = c_ij − ({{3}}). Wenn alle Δ_ij ≥ 0, ist die Lösung {{4}}.

Lösungen pro Lücke:

  • {{1}}: u_1 / u1
  • {{2}}: u_i + v_j / ui + vj
  • {{3}}: u_i + v_j / ui + vj
  • {{4}}: optimal

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

F4.Bringe die Schritte zur Lösung eines Transport-Problems in die richtige Reihenfolge.

Richtige Reihenfolge:

  1. Balanciertheit prüfen + Dummy einfügen falls nötig
  2. Start-Lösung mit Nordwest-Ecke / Vogel / MinKosten
  3. MODI-Optimalitäts-Test (alle Δ_ij ≥ 0?)
  4. Stepping-Stone-Pfad: Verbesserungs-Iteration

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

F5.Welches Problem ist NICHT polynomial lösbar?

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.

F6.Die Nordwest-Ecke-Methode liefert IMMER eine optimale Lösung, wenn das Transport-Problem balanciert ist.

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

Zur KategorieBusiness Analytics.Mehr Themen entdeckenZum Themen-Hub.

UniProMax ist eine themenbasierte Lernplattform für Studierende an deutschen Unis.

Wir glauben, dass Verstehen besser ist als Auswendiglernen. Wir bauen Lerneinheiten die zeigen statt erzählen. Code, Visualisierung, Quiz. Auf Deutsch.

Marke

UniProMaxUniProMax

Themenbasiert, visuell, interaktiv.

Inhalte

  • Alle Themen (Hub)
  • Programmiergrundlagen
  • Algorithmen
  • Mathematik
  • Statistik
  • Datenbanken
  • Rechnungswesen
  • VWL

Studiengang-Filter

  • Informatik
  • Wirtschaftsinformatik
  • BWL
  • Data Science
  • VWL
  • Wirtschaftsingenieurwesen
  • Mathe
  • Psychologie
  • weitere Studiengänge folgen

Plattform

  • Mein Fortschritt
  • Impressum
  • Datenschutz
© 2026 UniProMaxAlle Systeme onlinev0.2 / Sommersemester 2026
UniProMaxUniProMaxUniProMaxUniProMax