Flüsse in Netzwerken

Mit den in Kapitel 3 vorgestellten Verfahren können unkapazitierte Transport- und Umladeprobleme optimal gelöst werden. In der Praxis treten jedoch auch Kapazitätsbeschränkungen auf, die auf den Pfeilen in einem bewerteten Digraphen zu berücksichtigen sind. Zur Lösung dieser kapazitierten Transport- und Umladeprobleme wird im Folgenden auf Netzwerkflussprobleme eingegangen, da Transport- und Umladeprobleme unter Berücksichtigung von Kapazitätsbeschränkungen auch als Probleme der Bestimmung eines kostenminimalen Flusses in einem Digraphen formuliert werden können. Weiterhin lässt sich die Bestimmung des größtmöglichen Durchsatzes in einem Distributionsnetz oder der größtmögliche Verkehrsfluss als Berechnung eines optimalen Flusses in einem Netzwerk mit Kapazitätsbeschränkungen behandeln. Nach der Einführung notwendiger Grundbegriffe zu Flüssen und Netzwerken wird die Anwendbarkeit von Netzwerkflussproblemen auf kapazitierte Transport- und Umladeprobleme vorgestellt