Timm Pliefke
Ein polynominaler primaler Netzwerk Simplex Algorithmus zur Berechnung von
Flüssen mit minimalen Kosten
ISBN: 978-3-8366-2112-0
Herstellung: Diplomica® Verlag GmbH, Hamburg, 2008
Zugl. Universität Augsburg, Augsburg, Deutschland, Diplomarbeit, 2004
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden und der Verlag, die Autoren oder
Übersetzer übernehmen keine juristische Verantwortung oder irgendeine Haftung für evtl.
verbliebene fehlerhafte Angaben und deren Folgen.
© Diplomica Verlag GmbH
http://www.diplomica.de, Hamburg 2008
Vorwort
Während der Anfertigung dieser Arbeit haben mich zahlreiche Menschen mo-
tiviert und unterstützt. Bei Ihnen möchte ich mich an dieser Stelle bedanken.
Vielen Dank an Herrn Priv.-Doz. Dr. Dirk Hachenberger, Akademischer Rat
am Lehrstuhl für Optimierung und Operations Research für die wohlwollende
Unterstützung und Förderung dieser Arbeit.
Bei meinen Freunden Oliver Eckelmann, Sebastian Eiteljörge und Kaya Taner
bedanke ich mich für die anregenden Diskussionen und die kritische Ausein-
andersetzung mit meinem Diplomarbeitsthema. Überdies haben sie in mir in
schwierigen Situationen immer den nötigen Beistand geleistet, um die Moti-
vation zur Fertigstellung dieser Arbeit aufrechtzuerhalten.
Mein besonderer Dank gilt meiner Familie:
Meinen Eltern, Frau Doris und Herrn Dr. Engelbert Pliefke, sowie meiner
Schwester Sabine. Erst ihre tatkräftige Unterstützung ermöglichte es mir, das
Studium der Wirtschaftsmathematik an der Universität Augsburg erfolgreich
zu beenden.
Ihnen widme ich diese Arbeit.
Königsbrunn, im August 2004
Timm Pliefke
Inhaltsverzeichnis
Einführung
2
1 Grundlagen
6
1.1 Graphen, Netzwerke und Flüsse . . . . . . . . . . . . . . . . .
6
1.2 Eigenschaften maximaler Flüsse . . . . . . . . . . . . . . . . .
9
2 Das Minimum Cost Flow Problem (MCFP)
17
2.1 Die Problemstellung . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 MCFP Zulässigkeit . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 MCFP Optimalität . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Der Netzwerk Simplex Algorithmus
35
3.1 Baumlösungen und Baumstrukturen . . . . . . . . . . . . . . . 37
3.2 Initialisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.3 Der Netzwerk Simplex Algorithmus . . . . . . . . . . . . . . . 54
4 Der Premultiplier Algorithmus
77
4.1 Der allgemeine Premultiplier Algorithmus . . . . . . . . . . . 78
4.2 Der skalierte Premultiplier Algorithmus . . . . . . . . . . . . . 89
5 Details zur Implementierung
109
5.1 Implementierung des Netzwerk Simplex Algorithmus . . . . . 112
5.2 Implementierung des Premultiplier Algorithmus . . . . . . . . 134
5.3 Implementierung des skalierten Premultiplier Algorithmus . . 152
1
INHALTSVERZEICHNIS
2
Zusammenfassung und Ausblick
159
Literaturverzeichnis
163
Einführung
,,Es gibt zwei Wege, die Rentabilität der Arbeit eines Geschäfts, eines Unter-
nehmens oder eines ganzen Industriezweiges zu vergrößern. Ein Weg besteht
in verschiedenen Verbesserungen der Technik, z.B. neuem Zubehör für die
einzelnen Maschinen, Änderungen der technischen Prozesse und der Entde-
ckung neuer, besserer Arten von Rohmaterial. Der andere Weg, der bis jetzt
viel weniger genutzt wurde, besteht in der Verbesserung der Organisation der
Planung."
Dieses Zitat geht auf den russischen Mathematiker Kantorowicz zurück, der
im Jahre 1939 mit seinem Buch ,,Mathematische Methoden in der Organisa-
tion und Planung der Produktion" die erste Arbeit auf dem Gebiet der ma-
thematischen Optimierung veröffentlichte und somit den Grundstein für den
großen Aufschwung der linearen Optimierung in den Folgejahren legte. Als
Meilenstein in der Geschichte der linearen Optimierung gilt die Entwicklung
des Simplex Algorithmus durch G.B. Dantzig [13] im Jahre 1947. Bis heu-
te ist der Simplex Algorithmus eines der mächtigsten und das in der Praxis
am weitesten verbreitete Verfahren zur Lösung linearer Programme. Komple-
xe Problemstellungen mit tausenden von Variablen und Restriktionen lassen
sich mit modernen Implementierungen des Algorithmus
1
innerhalb kürzester
Zeit lösen.
Zahlreiche Optimierungsprobleme aus dem täglichen Anwendungsbereich,
wie z.B
· die Ermittlung von kürzesten Wegen innerhalb von Verkehrs- und Kom-
munikationsnetzen (Shortest Path Problem, SPP),
· die Maximierung des Verkehrsflusses auf einem vorgegebenen Straßen-
netz (Maximum Flow Problem, MFP),
· oder der kostenminimale Transport von Gütern zwischen Produzenten
und Käufern (Minimum Cost Flow Problem, MCFP),
1
wie z.B. CPLEX
3
EINFÜHRUNG
4
weisen eine spezielle Struktur auf, welche es erlaubt, diese, selbst bei kom-
plexen Zusammenhängen, anhand von geeigneten Graphen und Netzwerken
zu modellieren. Probleme dieser Art werden in der Kategorie Netzwerk-
probleme zusammengefasst. Innerhalb dieser Kategorie nimmt das zuletzt
aufgeführte MCFP eine zentrale Position ein, da es möglich ist, eine Vielzahl
anderer Netzwerkprobleme auf dieses zurückzuführen.
Obwohl die oben skizzierten Netzwerkprobleme eine spezielle Klasse linearer
Programme bilden, ist eine Darstellung dieser Probleme als lineare Program-
me denkbar ungünstig, da die resultierenden Programme sehr groß und mit
einer immensen Degeneriertheit behaftet sind. Somit ist eine Lösung dieser
Netzwerkprobleme mittels des traditionellen Simplex Algorithmus nur mit
sehr hohem Zeit- und Rechenaufwand möglich und folglich nicht diskutabel.
Hier gelang es Dantzig [12] 1951 das Kernkonzept des von ihm entwickelten
Simplex Algorithmus auf die strukturellen Besonderheiten von Netzwerken zu
transformieren und somit eine graphentheoretische Spezialisierung des Ver-
fahrens, den sogenannten Netzwerk Simplex Algorithmus, zu entwickeln.
Obwohl sich dieser in zahlreichen Varianten in der Praxis bewährt hat, blieb
es über lange Zeit ein offenes Problem, die polynomiale Beschränktheit der
Komplexität eines Netzwerk Simplex Algorithmus für das MCFP nachzuwei-
sen. Dieses Problem wurde 1995 von Orlin gelöst, der mit dem sogenannten
Premultiplier Algorithmus eine Spezialform des Netzwerk Simplex Algo-
rithmus entwickelte, welcher für ein MCFP mit polynomialer Komplexität
eine Optimallösung generiert.
Das Ziel der vorliegenden Arbeit besteht darin, durch systematisches
Vorgehen ein weit reichendes Verständnis für die Problematik des Netzwerk
Simplex Algorithmus zur Lösung eines MCFP zu schaffen, die Einflussgrößen
der Komplexität des Verfahrens darzulegen und aufbauend auf den erzielten
Befunden die Polynomialität des Premultiplier Algorithmus nachzuweisen.
Ferner soll auf Grundlage geeigneter Datenstrukturen eine Implementierung
der Algorithmen auf Basis der in der Literatur gebräuchlichen, an PASCAL
orientierten Pseudocodes dokumentiert werden.
Hierfür werden wir im ersten Kapitel zunächst die grundlegenden Begrifflich-
keiten und Ergebnisse der algorithmischen Graphentheorie und der Fluss-
theorie bereitstellen.
Eine Einführung in die Problematik des Minimum Cost Flow Problems wer-
den wir im zweiten Kapitel dieser Arbeit aufführen und überdies bereits erste
Grundgedanken zur Optimierung des Problems entwickeln.
Im dritten Kapitel werden wir den Netzwerk Simplex Algorithmus in seiner
EINFÜHRUNG
5
allgemeinen Form vorstellen und die wesentlichen Einflussgrößen der Laufzeit
des Verfahrens diskutieren.
Aufbauend auf diesen Erkenntnissen werden wir im vierten Kapitel dieser
Arbeit mit dem Premultiplier Algorithmus eine Spezialform des Netzwerk
Simplex Algorithmus kennen lernen und durch eine detaillierte Laufzeitana-
lyse die theoretische Effizienz des Verfahrens nachweisen.
Eine ausführlich dokumentierte Implementierung der vorgestellten Netzwerk
Simplex Algorithmen auf Grundlage von Pseudocodes werden wir in Kapitel
fünf dieser Arbeit darlegen.
Mit einer komprimierten Zusammenstellung der entwickelten Ergebnisse, so-
wie mit Vorschlägen zur Verbesserung bestehender Implementierungen wer-
den wir diese Arbeit abschließen.
Kapitel 1
Grundlagen
In diesem einführenden Kapitel werden wir einige grundlegende Begriffe und
Ergebnisse aus dem Bereich der algorithmischen Graphentheorie, sowie der
Flusstheorie zusammenstellen, welche im Folgenden als theoretisches Funda-
ment dieser Arbeit dienen werden. Im Fokus der Betrachtung wird hierbei
stehen, charakteristische Eigenschaften von Flüssen auf Netzwerken zu stu-
dieren, deren Kenntnis für die sich anschließende Diskussion des Minimum
Cost Flow Problems eine notwendige Voraussetzung darstellt.
Im ersten Abschnitt dieses Kapitels werden wir zunächst einige elementare
Definitionen der Graphentheorie bereitstellen und schließlich den Übergang
von der Graphen- zur Flusstheorie einleiten. Der darauf folgende zweite Ab-
schnitt wird sich im Wesentlichen auf die Herleitung bestimmter Optimali-
tätseigenschaften von maximalen Flüssen auf Netzwerken konzentrieren.
1.1
Graphen, Netzwerke und Flüsse
Bevor wir uns in diesem Abschnitt der Charakterisierung von Netzwerken
und Flüssen widmen werden, ist es zunächst notwendig, hierfür die funda-
mentalsten Begriffe der algorithmischen Graphentheorie bereitzustellen.
1.1.1 Definition (gerichteter Graph). Ein gerichteter Graph G = (V, E)
ist ein Paar bestehend aus einer Menge V von Knoten und einer Menge
E V × V von Kanten, wobei für jede Kante zwischen dem Anfangs- und
Endknoten zu unterscheiden ist. Bezeichnet e = (v, w) eine Kante der Menge
E, so heißt e
-
:= v der Anfangs- und e
+
:= w der Endknoten von e. Schließ-
lich sind durch |V | = n und durch |E| = m die Mächtigkeiten der beiden
Mengen V und E gegeben.
6
KAPITEL 1. GRUNDLAGEN
7
Wir werden im weiteren Verlauf immer davon ausgehen, dass auf den betrach-
teten Graphen jeder Knoten von jedem anderen Knoten aus über eine Folge
von paarweise verschiedenen Kanten, einem so genannten einfachen Kanten-
zug oder Weg, erreicht werden kann und die Graphen somit zusammenhän-
gend sind. Dies wird keineswegs eine Einschränkung der Allgemeinheit dar-
stellen, da wir bei nicht zusammenhängenden Graphen unsere Betrachtungen
für jede Zusammenhangskomponente getrennt durchführen können.
In den folgenden Kapiteln werden wir besonders an speziellen Unterstruktu-
ren gerichteter Graphen interessiert sein, welche durch die nächsten beiden
Definitionen beschrieben werden.
1.1.2 Definition (Kreis). Sei G = (V, E) ein gerichteter Graph. Ist durch
eine Folge paarweise verschiedener Kanten (e
1
, ..., e
n
) eine Folge von Knoten
(v
0
, ..., v
n
) gegeben, so dass e
i
= (v
i-1
, v
i
) oder e
i
= (v
i
, v
i-1
) erfüllt ist, so
heißt der Kantenzug (e
1
, ..., e
n
) bzw. die entsprechende Folge von Knoten
(v
0
, ..., v
n
) ein Kreis, falls v
0
= v
n
Gültigkeit besitzt. Dabei bezeichnet man
e
i
= (v
i-1
, v
i
) als Vorwärtskante und e
i
= (v
i
, v
i-1
) als Rückwärtskante des
Kreises. Besteht der Kreis nur aus Vorwärtskanten, so handelt es sich um
einen gerichteten Kreis.
1.1.3 Definition (aufspannender Baum). Sei G = (V, E) ein gerichteter
Graph. Ein aufspannender Baum T des Graphen G = (V, E) kennzeich-
net einen speziellen Teilgraphen, welcher die Knotenmenge V vollständig
überdeckt, während die Kantenmenge F des Baumes eine Teilmenge der ur-
sprünglichen Kantenmenge E bildet. Zusätzlich hat ein aufspannender Baum
T die folgenden beiden Anforderungen zu erfüllen:
· T ist zusammenhängend,
· T ist kreisfrei.
Des Weiteren bezeichnen wir einen Knoten v des Baumes T als Blatt, falls v
inzident mit genau einer Baumkante der Menge F ist.
Entsprechend dieser Definition ist offensichtlich, dass für zwei beliebige Kno-
ten der Menge V auf dem aufspannenden Baum T stets ein eindeutiger Weg
existiert, welcher diese beiden Knoten verbindet. Somit resultiert das Hin-
zufügen einer beliebige Kante der Menge E\F zum Baum T in der Bildung
eines eindeutigen Kreises. Wird wiederum eine beliebige Kante dieses Kreises
entfernt, so liegt erneut ein aufspannender Baum des Graphen G = (V, E)
KAPITEL 1. GRUNDLAGEN
8
vor. Dieser ist genau dann vom vorigen aufspannenden Baum verschieden,
wenn sich die hinzugefügte und die entfernte Kante unterscheiden.
Wir werden uns mit diesen Überlegungen in den folgenden Kapiteln sehr
detailliert auseinandersetzen, da sie eine zentrale Rolle bei der Diskussion
des Netzwerk Simplex Algorithmus einnehmen.
Auf Grundlage gerichteter Graphen werden wir an dieser Stelle das Konstrukt
erweitern, indem wir auf der Kantenmenge E des Graphen G = (V, E) spe-
zielle Abbildungen definieren werden. Somit gelangen wir von Graphen zu
sogenannten Netzwerken.
1.1.4 Definition ((Fluss-)Netzwerk). Sei G = (V, E) ein gerichteter
Graph. Ist auf der Kantenmenge E des Graphen G eine Abbildung w : E R
definiert, so bildet das Paar (G, w) ein Netzwerk. Die Funktion w wird in
diesem Kontext häufig auch als Länge, Kapazität, Kosten, Dauer, Gewicht
etc. interpretiert.
Zeichnet die Knotenmenge V zusätzlich zwei besondere Knoten s und t aus,
wobei der Knoten s als Quelle, der Knoten t als Senke bezeichnet wird, so
ist durch N = (G, w, s, t) ein F lussnetzwerk gegeben.
Ist die Funktion w durch eine Abbildung c : E R
+
spezifiziert, welche
obere Kapazitätsfunktion heißt, so kennzeichnet N = (G, c, s, t) ein Fluss-
netzwerk mit oberer Kapazitätsfunktion c.
Aufgrund der starken Verwandtschaft der Begriffe werden wir im Folgenden
die exakte Abgrenzung der Definitionen Netzwerk, Flussnetzwerk und Fluss-
netzwerk mit oberer Kapazitätsfunktion etwas vernachlässigen und häufig
synonym verwenden.
Auf einem Flussnetzwerk N = (G, c, s, t) lässt sich nun wie folgt ein Fluss
definieren.
1.1.5 Definition (Fluss). Es sei N = (G, c, s, t) ein Flussnetzwerk. Eine
Abbildung f : E R wird als Fluss auf N bezeichnet, falls sie die folgenden
beiden Bedingungen erfüllt:
1. Kapazitätsbeschränkung:
0 f (e) c(e),
für alle e E.
2. Flusserhaltung:
e
+
=v
f (e) =
e
-
=v
f (e),
für alle v V \{s, t}.
KAPITEL 1. GRUNDLAGEN
9
Dabei signalisieren uns die Summationsindizes, dass die Summe über alle
Kanten e E gebildet wird, deren Anfangsknoten e
-
bzw. Endknoten e
+
identisch mit dem Knoten v ist.
Schließlich ist der Wert des Flusses f durch
w(f ) =
e
-
=s
f (e) -
e
+
=s
f (e)
bestimmt. Ein Fluss f
heißt maximal auf N, falls die Ungleichung w(f
)
w(f ) für alle weiteren Flüsse f auf N erfüllt ist. Die Suche nach einem maxi-
malen Fluss auf einem Flussnetzwerk N bezeichnet man als Maximum Flow
Problem (MFP).
Durch die Kapazitätsbeschränkungen in Definition 1.1.5 ist für jede Kan-
te e E des Netzwerkes N sowohl eine minimale als auch eine maximale
Flussmenge vorgegeben, die ein Fluss vom Anfangs- zum Endknoten der be-
trachteten Kante e transportieren darf. Überdies wird durch die Flusserhal-
tungsbedingungen für jeden von der Quelle s und der Senke t verschiedenen
Knoten sichergestellt, dass die gleiche Flussmenge in den Knoten hinein- wie
hinausfließt und somit kein Fluss innerhalb des Netzwerkes ,,verloren" geht.
Ferner beschreibt der Wert eines Flusses f genau diejenige Flussmenge, die
netto aus der Quelle s hinausfließt. Schließlich wird durch die Flusserhal-
tungsbedingungen, welche für alle von s und t verschiedenen Knoten des
Netzwerkes zu erfüllen sind, gewährleistet, dass w(f ) gleichzeitig derjenigen
Flussmenge entspricht, die netto in die Senke t hineinfließt.
1.2
Eigenschaften maximaler Flüsse
Nachdem wir im letzten Abschnitt die für uns relevanten Grundbegriffe der
Graphen- und Flusstheorie vorgestellt haben, werden wir uns nun mit der
Charakterisierung maximaler Flüsse auf Netzwerken beschäftigen. Bevor wir
im weiteren Verlauf konkrete Bedingungen herleiten werden, die einen maxi-
malen Fluss auf einem Netzwerk beschreiben, ist es notwendig, die Existenz
solcher Flüsse sicherzustellen. Hierfür sind die folgenden beiden Vorausset-
zungen zu erfüllen:
1. Zulässigkeit: Das Flussnetzwerk muss so beschaffen sein, dass es mög-
lich ist, einen Fluss auf den Kanten des Netzwerkes zu definieren, der
sowohl die Kapazitätsrestriktionen, als auch die Flusserhaltungsbedin-
gungen erfüllt.
KAPITEL 1. GRUNDLAGEN
10
2. Beschränktheit: Es muss eine obere Schranke existieren, die den Wert
des Flusses nach oben hin begrenzt. Überdies sollte gewährleistet sein,
dass der Wert des Flusses die durch die obere Schranke gegebene Zahl
auch annehmen kann.
Die Bedingung der Zulässigkeit stellt für die in diesem Abschnitt betrachteten
Flussnetzwerke keine Einschränkung dar, weil durch den Nullfluss f (e) = 0
für alle Kanten e E stets ein Fluss gegeben ist, der sowohl den Kapazitäts-
restriktionen, als auch den Flusserhaltungsbedingungen nachkommt. Dem-
nach sind MFP auf diesen Netzwerken immer zulässig.
Für Netzwerke, die zusätzlich zur oberen Kapazitätsschranke c eine beliebi-
ge untere Kapazitätsschranke b aufweisen, ist die Zulässigkeit dagegen nicht
notwendigerweise gewährleistet. In diesem Fall kann die Zulässigkeit durch
geeignete Transformationen der Problemstellung überprüft werden.
1
Da die Existenz eines Flusses auf den hier betrachteten Netzwerken durch den
Nullfluss erwiesen ist, werden wir uns nun mit der Herleitung einer oberen
Schranke für den Flusswert beschäftigen. Es ist leicht nachvollziehbar, dass
der Wert (f ) eines Flusses f stets durch die Zahl
e
-
=s
c(e) nach oben
hin begrenzt ist, da jeder Fluss die Kapazitätsrestriktionen einzuhalten hat.
Wegen der zusätzlich zu erfüllenden Flusserhaltungsbedingungen ist diese
Lösung jedoch im Allgemeinen nicht zulässig. Für die Konstruktion einer
oberen Schranke, die der Wert des Flusses auch annehmen kann, benötigen
wir zunächst das Konstrukt des Schnittes.
1.2.1 Definition (Schnitt). Sei N = (G, c, s, t) ein Flussnetzwerk. Unter
einem Schnitt von N versteht man eine Zerlegung V = S T der Knoten-
menge V in zwei disjunkte Teilmengen S und T , wobei s S und t T .
Dabei ist die Kapazität des Schnittes durch die Zahl
c(S, T ) =
e
-
S
e
+
T
c(e)
gegeben. Ein Schnitt (S, T ) heißt minimal auf N, wenn für alle weiteren
Schnitte (S , T ) von N die Bedingung c(S, T ) c(S , T ) erfüllt ist.
Die Kapazität eines Schnittes beschreibt demnach anschaulich die maximale
Flussmenge, die bei gegebener Knotenpartition von der Knotenmenge S zur
Knotenmenge T transportiert werden kann, ohne die Kapazitätsbeschränkun-
gen des zugrunde liegenden Netzwerkes zu verletzen. Aus dieser Überlegung
heraus können wir nun eine obere Schranke für den Flusswert herleiten.
1
vergleiche Ahuja et al. [1] S.193
KAPITEL 1. GRUNDLAGEN
11
1.2.2 Lemma. Sei N = (G, c, s, t) ein Flussnetzwerk und f bezeichne einen
Fluss auf N. Ist durch (S, T ) ein beliebiger Schnitt von N gegeben, so ist die
Ungleichung
w(f ) c(S, T )
stets erfüllt.
Beweis. Nach Definition 1.1.5 ist der Wert des Flusses f durch die Gleichung
w(f ) =
e
-
=s
f (e) -
e
+
=s
f (e)
gegeben. Da die Partitionsmenge S des Schnittes die Quelle s, nicht aber die
Senke t enthält, folgt mit den Flusserhaltungsbedingungen:
w(f ) =
vS
e
-
=v
f (e) -
e
+
=v
f (e)
=
=
e
-
S
e
+
S
f (e) -
e
+
S
e
-
S
f (e) +
e
-
S
e
+
T
f (e) -
e
+
S
e
-
T
f (e) =
=
e
-
S
e
+
T
f (e) -
e
+
S
e
-
T
f (e).
Mit Hilfe der Kapazitätsbeschränkungen lässt sich nun aus obiger Gleichungs-
kette die folgende Abschätzung herleiten:
w(f ) =
e
-
S
e
+
T
f (e) -
e
+
S
e
-
T
f (e)
e
-
S
e
+
T
c(e) -
e
+
S
e
-
T
0 = c(S, T ),
so dass die Behauptung folgt.
Da nun erwiesen ist, dass der Wert eines Flusses f auf einem Netzwerk N
stets durch die Kapazität eines Schnittes (S, T ) nach oben hin beschränkt
ist, stellt sich nun die Frage, wie genau obige Abschätzung für den Wert
eines maximalen Flusses ist. In der Absicht, dieser Frage nachzugehen, bedarf
es zunächst einer Charakterisierung maximaler Flüsse, wofür die folgende
Definition die Grundlage bildet.
1.2.3 Definition (augmentierender Weg). Sei f ein Fluss auf einem
Flussnetzwerk N = (G, c, s, t). Ein Weg P von einem Knoten v V zu
einem anderen Knoten w V wird als augmentierender oder zunehmender
Weg bezüglich f bezeichnet, falls die beiden folgenden Bedingungen erfüllt
sind:
KAPITEL 1. GRUNDLAGEN
12
1. f (e) < c(e), für jede Kante e mit (e
-
, e
+
) P ,
2. f (e) > 0, für jede Kante e mit (e
+
, e
-
) P .
Dabei ist durch (e
-
, e
+
) eine Vorwärtskante und durch (e
+
, e
-
) eine Rück-
wärtskante des Weges P gegeben. Startet man an dem Knoten v, so trifft man
bei Durchschreitung des Weges P im Falle einer Vorwärtskante zunächst auf
den Anfangsknoten e
-
und schließlich auf den Endknoten e
+
der betrachteten
Kante. Eine Rückwärtskante lässt eine analoge Interpretation zu.
Mit Hilfe von augmentierenden Wegen lässt sich nun eine Bedingung zur
Identifizierung maximaler Flüsse herleiten.
1.2.4 Satz (augmenting path theorem). Ein Fluss f ist auf einem Netz-
werk N genau dann maximal, wenn kein augmentierender Weg bezüglich f
von der Quelle s zur Senke t existiert.
Beweis. Wir beweisen zunächst die Hinrichtung und gehen davon aus, dass
durch f ein maximaler Fluss auf N gegeben ist. Entgegen der Behauptung
nehmen wir an, dass in N ein augmentierender Weg P bezüglich f von s
nach t existiert. Es seien hierzu die Werte
1
,
2
und wie folgt definiert:
·
1
:= min{c(e) - f (e) : (e
-
, e
+
) P },
·
2
:= min{f (e) : (e
+
, e
-
) P },
· := min{
1
,
2
}.
Da nach unserer Annahme ein augmentierender Weg existiert, ist nach De-
finition 1.2.3 offensichtlich > 0 erfüllt. Betrachten wir nun eine Abbildung
f : E R, mit
f (e) :=
f (e) +
falls (e
-
, e
+
) P,
f (e) -
falls (e
+
, e
-
) P,
f (e)
sonst.
so kommt f nach Konstruktion von sowohl den Kapazitätsbeschränkungen,
als auch den Flusserhaltungsbedingungen nach und ist somit ebenfalls ein
Fluss auf N. Für den Wert von f ergibt sich
w(f ) = w(f ) + > w(f ),
KAPITEL 1. GRUNDLAGEN
13
was im Widerspruch zur Maximalität von f steht.
Zum Beweis der Rückrichtung nehmen wir an, dass in N kein augmentieren-
der Weg bezüglich f von s nach t existiert. Wir definieren durch S die Menge
aller Knoten, die, von s aus, auf einem augmentierenden Weg erreichbar sind
und T sei die Menge der verbleibenden Knoten, also T := V \S. Nach unserer
Annahme ist offensichtlich, dass s S und t T erfüllt und somit durch
(S, T ) ein Schnitt von N gegeben ist. Da nach Konstruktion der Mengen S
und T der Fluss f auf jeder Kante e mit e
-
S und e
+
T den Wert
c(e) annehmen und auf jeder Kante e mit e
+
S und e
-
T den Wert 0
repräsentieren muss, besitzt die folgende Gleichungskette Gültigkeit:
w(f ) =
e
-
S
e
+
T
f (e) -
e
+
S
e
-
T
f (e) =
e
-
S
e
+
T
c(e) -
e
+
S
e
-
T
0 = c(S, T )
Damit folgt die Behauptung aus Lemma 1.2.2.
1.2.5 Bemerkung. Der im Beweis skizzierte Übergang von f zu f wird als
die Augmentierung von f entlang des Weges P bezeichnet.
Der nun folgende berühmte Satz beantwortet schließlich unsere Frage nach
der Qualität der, durch die Kapazität eines Schnittes gegebenen, oberen
Schranke für den Wert eines Flusses, und belegt, dass der Wert eines ma-
ximalen Flusses auf einem Netzwerk N und die Kapazität eines minimalen
Schnittes stets übereinstimmen müssen.
1.2.6 Satz (max-flow min-cut theorem). Ein Fluss f ist auf einem Fluss-
netzwerk N genau dann maximal, wenn einen minimaler Schnitt (S,T) exis-
tiert, der die Bedingung
w(f ) = c(S, T )
erfüllt.
Beweis. Es sei durch f ein maximaler Fluss gegeben. Nach Satz 1.2.4 kann
somit kein augmentierender Weg von der Quelle s zur Senke t des Netzwer-
kes N existieren. Aufbauend auf dieser Nichtexistenz haben wir im Beweis
von Satz 1.2.4 bereits eine Methode vorgestellt, einen Schnitt (S, T ) so zu
konstruieren, dass
w(f ) = c(S, T )
KAPITEL 1. GRUNDLAGEN
14
erfüllt ist. Nach Lemma 1.2.2 ist dieser Schnitt bereits minimal.
Die Rückrichtung des Beweises ist eine unmittelbare Folgerung aus Lemma
1.2.2 .
Durch die minimale Kapazität eines Schnittes ist somit stets eine obere Be-
grenzung für den Wert eines Flusses gegeben, welche die eingangs gestellten
Anforderungen erfüllt. Da auf einem Flussnetzwerk nur endlich viele Schnitte
konstruiert werden können, ist die Existenz eines minimalen Schnittes immer
gewährleistet. Neben der Zulässigkeit ist also nun auch die Beschränktheit
des Wertes eines Flusses nachgewiesen, und wir können folgern, dass stets
ein maximaler Fluss existiert.
Nachdem wir nun die fundamentalen Zusammenhänge zwischen maximalen
Flüssen, augmentierenden Wegen und minimalen Schnitten auf Netzwerken
in kompakter Weise dargestellt haben, werden wir an dieser Stelle abschlie-
ßend eine Charakterisierung residualer Netzwerke aufführen. Mit diesen wird
uns ein nützliches Werkzeug zur Verfügung stehen, um zunehmende Wege
aufzuspüren und Flüsse entlang dieser Wege zu augmentieren.
1.2.7 Definition (residuales Netzwerk). Gegeben sei ein Flussnetzwerk
N = (G, c, s, t) und ein Fluss f auf N. Das zu N und f gehörige residuale
Netzwerk N
f
= (G
f
, r
f
) mit Knotenmenge V , Kantenmenge E
f
und Residu-
alkapazitätsfunktion r
f
: E
f
R
+
kann nun wie folgt konstruiert werden:
· Für jede Kante e = (e
-
, e
+
) E des zugrunde liegenden Netzwerkes
N mit f (e) < c(e) wird im residualen Netzwerk N
f
eine Vorwärtskante
e
f
1
= (e
-
, e
+
) mit gleicher Orientierung eingeführt. Die Residualkapa-
zität dieser Kante wird durch r
f
(e
f
1
) := c(e) - f (e) festgelegt.
· Für jede Kante e = (e
-
, e
+
) E des zugrunde liegenden Netzwerkes
N mit f (e) > 0 wird im residualen Netzwerk N
f
eine Rückwärtskan-
te e
f
2
= (e
+
, e
-
) mit entgegengesetzter Orientierung eingeführt. Die
Residualkapazität dieser Kante ist durch r
f
(e
f
2
) := f (e) bestimmt.
Durch Abbildung (1.1) wird die Struktur eines residualen Netzwerkes gra-
phisch veranschaulicht. Bei genauerer Betrachtung dieser Abbildung wird
deutlich, dass für jedes Paar von Knoten v und w, die im zugrunde liegen-
den Netzwerk N eine Kante e teilen, also adjazent sind, auch im residualen
Netzwerk N
f
mindestens eine Kante e
f
existiert, welche die beiden Knoten
KAPITEL 1. GRUNDLAGEN
15
Abbildung 1.1: residuales Netzwerk
verbindet. Die Orientierung der Kante(n) e
f
ist dabei abhängig vom Fluss f
auf N.
Ist f (e) = 0 erfüllt, so bezeichnet man f als straff an der unteren Kapazi-
tätsschranke der Kante e und die Orientierung von e
f
entspricht der von e.
Die Kante e wird also als Vorwärtskante e
f
1
im residualen Netzwerk reprä-
sentiert.
Gilt hingegen f (e) = c(e), so ist f straff an der oberen Kapazitätsschranke
der Kante e, und entsprechend ist die Orientierung von e
f
der von e ent-
gegengesetzt. Somit wird die Kante e als Rückwärtskante e
f
2
im residualen
Netzwerk repräsentiert.
Eine Kante e wird als gesättigt bezeichnet, falls f entweder an der unteren
oder an der oberen Kapazitätsschranke der Kante e straff ist.
Ist schließlich 0 < f (e) < c(e) gegeben, so ist f locker an beiden Kapazitäts-
schranken der Kante e, und im residualen Netzwerk N
f
werden zwei Kanten
e
f
1
und e
f
2
eingeführt, wobei wie zuvor die Orientierung der Kante e
f
1
mit
der Orientierung von e identisch ist, währenddessen die Orientierung von e
f
2
der von e entgegensteht. In diesem Fall bezeichnet man die Kante e als frei.
Der Zusammenhang des Graphen G = (V, E) bleibt demnach beim Übergang
zu G
f
= (V, E
f
) für jeden Fluss f erhalten.
Durch die Residualkapazität r
f
einer Kante e
f
im Netzwerk N
f
ist ein Indi-
kator für den maximal möglichen Wert einer Augmentierung von f entlang
der Kante e im Netzwerk N gegeben. Sie erteilt, ausgehend von f , Auskunft
darüber, wie viel Fluss auf der Kante e im Netzwerk N maximal verschoben
werden kann, ohne die Kapazitätsbeschränkungen zu verletzen. Dabei ist die
Richtung der Flussverschiebung identisch mit der Orientierung von e
f
.
Eine Suche nach einem augmentierenden Weg P bezüglich eines Flusses f
KAPITEL 1. GRUNDLAGEN
16
zwischen zwei Knoten v und w eines Netzwerkes N ist, entsprechend dieser
Überlegungen, äquivalent zur Suche eines gerichteten Weges P
f
von v nach
w im residualen Netzwerk N
f
. Existiert solch ein augmentierender Weg, so
kann f entlang P um := min{r
f
(e
f
) : e
f
P
f
} Einheiten augmentiert
werden.
Die Bestimmung eines maximalen Flusses auf einem gegebenen Flussnetz-
werk zählt zu den wichtigsten Problemen der Flusstheorie. Es stehen eine
Vielzahl effizienter Algorithmen zur Verfügung, die ein MFP in polynomialer
Zeit lösen.
2
Wir werden uns in dieser Arbeit hauptsächlich mit dem soge-
nannten Minimum Cost Flow Problem (MCFP) befassen, welches sich mit
der Bestimmung von Flüssen mit minimalen Kosten auf Netzwerken beschäf-
tigt. Da es möglich ist, das MFP auf das MCFP zurückzuführen, besitzen
oben stehende Überlegungen auch im Kontext des MCFP eine große Bedeu-
tung, wie das nächste Kapitel zeigen wird.
2
eine gute Übersicht bietet u.a. Ahuja et al. [1] S.207
Kapitel 2
Das Minimum Cost Flow
Problem (MCFP)
In diesem Kapitel werden wir eine Einführung in die Problematik des Mi-
nimum Cost Flow Problems geben. Das MCFP befasst sich mit der Frage-
stellung, wie in einem Netzwerk zur Verfügung stehendes Angebot auf die
kostengünstigste Weise transportiert werden kann, um im Netzwerk ander-
weitig lokalisierte Nachfrage zu befriedigen. Dabei existieren zudem für die
einzelnen Transporte sowohl untere, als auch obere Kapazitätsrestriktionen,
die jeweils einzuhalten sind. Das MCFP besitzt einen sehr hohen Stellenwert
innerhalb der Kategorie der Flussprobleme, da es eine Verallgemeinerung
der wichtigsten der Probleme dieser Klasse darstellt und diese folglich auf
das MCFP zurückgeführt werden können.
Nach einer formellen Beschreibung des Problems im ersten Abschnitt wer-
den wir unter Verwendung der Ergebnisse des vorigen Kapitels im zweiten
Abschnitt die Frage klären, unter welchen Bedingungen ein MCFP zulässig
ist. Der letzte Abschnitt dieses Kapitels wird schließlich charakteristische Ei-
genschaften von Optimallösungen des Problems aufzeigen und somit einen
wesentlichen Beitrag für die Entwicklung von Algorithmen zur Lösung des
MCFP leisten.
2.1
Die Problemstellung
Ausgangspunkt der Betrachtung des MCFP ist ein Netzwerk N, das zusätz-
lich zur oberen Kapazitätsfunktion c eine untere Kapazitätsfunktion b besitzt,
welche für alle Kanten e E die Bedingung b(e) c(e) erfüllt. Des Weiteren
wird die im vorigen Kapitel unterstrichene Ausnahmerolle der Knoten s und
17
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
18
t im Kontext des MCFP aufgehoben. Vielmehr werden in der hier betrachte-
ten Problemstellung im Allgemeinen mehrere Knoten als Quellen und Senken
fungieren, abhängig vom Vorzeichen einer Angebotsfunktion s, die auf der
Menge der Knoten des Netzwerkes definiert wird. Überdies werden neben
den Quellen und Senken auch einige Knoten des Netzwerkes die Funktion als
Durchlaufpunkte übernehmen.
Zusätzlich zu den Kapazitätsfunktionen wird auf der Menge der Kanten E
eine weitere Abbildung : E R definiert, welche als Kostenfunktion be-
zeichnet wird. Sie gibt für jede Kante e E die Kosten an, die das Durchflie-
ßen einer Flusseinheit durch die Kante e verursacht. Gesucht wird anschlie-
ßend ein Fluss, der, unter Einhaltung der Kapazitätsrestriktionen, mit Hilfe
des Angebots der Quellen die Nachfrage der Senken befriedigt und dabei die
geringsten Kosten verursacht.
Formal lässt sich das MCFP wie folgt erfassen:
2.1.1 Definition (Minimum Cost Flow Problem). Sei G = (V, E) ein
gerichteter Graph. Auf der Menge der Kanten E des Graphen seien eine
Abbildung f : E R, sowie die beiden Kapazitätsfunktionen b : E R
und c : E R definiert, die b(e) c(e) für alle e E erfüllen. Zusätzlich
sei auf E eine Kostenfunktion : E R bestimmt, welche die Kosten pro
transportierter Flusseinheit vom Anfangs- zum Endknoten auf jeder Kante
festlegt. Ferner sei s : V R eine auf der Menge der Knoten V definierte
Angebotsfunktion, so dass
vV
s(v) = 0 erfüllt wird. Das Minimum Cost
Flow Problem ist schließlich durch
Minimiere
eE
(e)f (e)
unter
e
-
=v
f (e) -
e
+
=v
f (e) = s(v)
(M1)
b(e) f (e) c(e)
(M2)
bestimmt.
Im Kontext des MCFP wird ein Knoten v als Quelle bezeichnet, falls das
Angebot von v positiv ist, wenn also s(v) > 0 erfüllt ist. Nach Definition
der Angebotsfunktion zeichnen sich Quellen dadurch aus, dass eine größere
Flussmenge aus ihnen hinausfließt, als in sie hineinfließt, und sie folglich die
Differenzflussmenge zur Verfügung stellen, also anbieten. Wird einem Knoten
v durch die Angebotsfunktion s hingegen ein negatives Angebot zugewiesen,
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
19
so gilt s(v) < 0 und der Knoten v heißt Senke. In diesem Fall ist die Fluss-
menge, die in den Knoten hineinfließt, größer, als die Flussmenge die aus ihm
hinausfließt, es wird also von der Senke die Differenzflussmenge verbraucht
oder nachgefragt. Im verbleibenden Fall s(v) = 0 fließt in den Knoten v die
gleiche Flussmenge hinein wie hinaus und der Knoten v wird Durchlaufpunkt
genannt. Es ist nun entsprechend dieser Überlegungen leicht nachvollziehbar,
dass die Angebote aller Quellen zusammen genau der Summe der Nachfragen
aller Senken entsprechen müssen, um die Existenz einer zulässige Lösung für
das MCFP zu gewährleisten. Dieses wird durch die Gleichung
vV
s(v) = 0
zum Ausdruck gebracht.
Die Abbildung f ist in diesem Zusammenhang ein Fluss, falls sie die Ange-
botsrestriktionen (M1) erfüllt. Genügt f zusätzlich den Kapazitätsrestriktio-
nen (M2), so wird f als zulässiger Fluss bezeichnet.
Schließlich notieren wir für die Kosten eines zulässigen Flusses f im weiteren
Verlauf auch kurz (f ) :=
eE
(e)f (e).
Um in der sich anschließenden Diskussion der Zulässigkeit eines MCFP Red-
undanzen zu vermeiden, werden wir zum Abschluss dieses Abschnittes eine
Transformation des MCFP vornehmen, welche unsere entsprechend Defini-
tion 2.1.1 allgemein formulierte Problemstellung auf den Spezialfall mit un-
terer Kapazitätsschranke b(e) = 0 eingrenzt. Dies wird jedoch keinesfalls
eine Einschränkung der Allgemeinheit darstellen, da die beiden Problemstel-
lungen vor und nach der Transformation absolut äquivalent im Bezug auf
Zulässigkeit sein werden. Überdies werden sich die Kosten der sich entspre-
chenden zulässigen Flüsse der beiden Probleme nur durch eine Konstante
unterscheiden, welche wir separat erfassen und im Verlauf der gesamten Op-
timierungsphase ignorieren können. Ist schließlich eine Optimallösung für das
restriktivere Problem gefunden, so ist diese, nach Addition der Kostenkon-
stanten, exakt gleichwertig zu einer Lösung des allgemeinen Problems mit
minimalen Kosten.
2.1.2 Satz (MCFP Transformation). Gegeben sei ein entsprechend De-
finition 2.1.1 formuliertes MCFP. Transformiert man das MCFP durch
b
(e) := 0,
für alle e E
c
(e) := c(e) - b(e),
für alle e E
s
(v) := s(v) +
e
+
=v
b(e) -
e
-
=v
b(e),
für alle v V
auf ein Problem MCFP
, welches durch
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
20
Minimiere
eE
(e)f
(e)
unter
e
-
=v
f
(e) -
e
+
=v
f
(e) = s
(v)
0 f
(e) c
(e)
eindeutig beschrieben ist, so ist f
genau dann ein zulässiger Fluss für das
MCFP
, falls f := f
+ b ein zulässiger Fluss für das MCFP ist. Ferner
unterscheiden sich die Kosten der beiden Flüsse (f
) und (f ) nur durch
eine Konstante :=
eE
(e)b(e).
Beweis. Es sei durch f
ein zulässiger Fluss für das MCFP
gegeben. Defi-
nieren wir durch f (e) := f
(e) + b(e), für alle e E eine Abbildung auf der
Kantenmenge E, so ist die folgende Ungleichungskette erfüllt:
0 f
(e) c
(e)
0 f (e) - b(e) c(e) - b(e)
b(e) f (e) c(e).
Somit erfüllt f also für alle Kanten e E die Kapazitätsrestriktionen (M2).
Zum Nachweis, dass f für alle Knoten v V auch den Angebotsrestriktionen
(M1) genügt, betrachten wir das folgende Gleichungssystem:
s
(v) =
e
-
=v
f
(e) -
e
+
=v
f
(e)
=
e
-
=v
(f (e) - b(e)) -
e
+
=v
(f (e) - b(e))
=
e
-
=v
f (e) -
e
+
=v
f (e) +
e
+
=v
b(e) -
e
-
=v
b(e).
Nach Definition der Angebotsfunktion s
folgt unmittelbar, dass f den Ange-
botsrestriktionen nachkommt. Damit ist f ein zulässiger Fluss für das MCFP.
Zum Beweis der Rückrichtung gehen wir von einer zulässigen Lösung f des
MCFP aus. In diesem Fall setzen wir f
(e) := f (e) - b(e) für alle Kan-
ten e E und zeigen durch analoges Vorgehen die Zulässigkeit von f
für
MCFP
.
Schließlich stehen die Kosten der beiden Flüsse (f
) und (f ) wie folgt
zueinander in Beziehung:
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
21
(f
) =
eE
(e)f
(e) =
eE
(e)(f (e) - b(e))
=
eE
(e)f (e) -
eE
(e)b(e) = (f ) - ,
womit auch die letzte Behauptung folgt.
Nach Satz 2.1.2 können wir weiteren Verlauf o.B.d.A. unsere Betrachtungen
auf MCFPs einschränken, welche eine untere Kapazitätsschranke b(e) = 0
aufweisen.
2.2
MCFP Zulässigkeit
Bevor wir uns mit der Charakterisierung und der Bestimmung eines zuläs-
sigen Flusses mit minimalen Kosten, also mit der Optimierung des MCFP
auseinandersetzen werden, muss zunächst einmal für jede Probleminstanz
individuell entschieden werden, ob grundsätzlich ein zulässiger Fluss exis-
tiert. Dieses Zulässigkeitsproblem kann durch die Einführung eines geeigne-
ten Hilfsflussnetzwerkes gelöst werden, das auf einfache Weise aus unserem
Graphen G = (V, E), sowie den zur Verfügung stehenden Daten über Kapa-
zitäten der Kanten und Angebote der Knoten konstruiert werden kann. Die
Kosten sind bei der Prüfung auf Zulässigkeit und damit bei der Erstellung
unseres Hilfsflussnetzwerkes nicht relevant. Das spezielle Hilfsflussnetzwerk
entspricht strukturell exakt den in Kapitel 1 betrachteten Problemstellungen,
so dass wir obige Resultate nutzen können, um schließlich auf Zulässigkeit
bzw. Unzulässigkeit einer Probleminstanz des MCFP zu folgern.
2.2.1 Definition. Sei MCFP ein entsprechend Definition 2.1.1 festgelegtes
Problem mit zugrunde liegendem Graphen G = (V, E), unterer Kapazitäts-
schranke 0, oberer Kapazitätsfunktion c, sowie einer Angebotsfunktion s.
Dann lässt sich hierzu das Hilfsflussnetzwerk N = (G , c , s, t) auf die folgen-
de Weise konstruieren:
· Erweitere die Knotenmenge V des Graphen G = (V, E) um eine Su-
perquelle s und eine Supersenke t und erhalte die neue Knotenmenge
des modifizierten Graphen G = (V , E ) durch V := V {s, t}.
· Erweitere für alle Quellen v mit s(v) > 0 die Kantenmenge E des Gra-
phen G = (V, E) um die Kanten (s, v). Füge für alle Senken v mit
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
22
s(v) < 0 die Kanten (v, t) zu E hinzu und erhalte die neue Kanten-
menge des modifizierten Graphen G = (V , E ) durch
E := E {(s, v) : v V, s(v) > 0} {(v, t) : v V, s(v) < 0}.
· Erweitere die Kapazitätsfunktion c auf die Kantenmenge E und erhalte
die neue Kapazitätsfunktion c : E R durch
c (e) :=
c(e),
falls e E,
s(v),
falls e = (s, v),
-s(v),
falls e = (v, t).
Ferner seien auch die neu hinzugefügten Kanten durch 0 nach unten
hin beschränkt.
Offenbar ist c (e) 0, für alle e E erfüllt, und das entsprechend obiger
Vorschriften konstruierte Hilfsflussnetzwerk N = (G , c , s, t) entspricht somit
exakt den im vorigen Kapitel betrachteten Flussnetzwerken mit Quelle s,
Senke t und oberer Kapazitätsfunktion c . Die Bestimmung eines maximalen
Flusses auf diesem Hilfsflussnetzwerk liefert uns nun wichtige Information
über die Zulässigkeit des zugrunde liegenden MCFP, wie der folgende Satz
belegt.
2.2.2 Satz. Für ein entsprechend Definition 2.1.1 formuliertes MCFP mit
zugrunde liegendem Graphen G = (V, E), unterer und oberer Kapazitäts-
schranke 0 bzw. c und Angebotsfunktion s existiert genau dann eine zulässige
Lösung f , wenn für das gemäß Definition 2.2.1 konstruierte Hilfsflussnetz-
werk N = (G , c , s, t) ein maximaler Fluss f existiert, der für alle mit der
Superquelle s inzidenten Kanten straff an der oberen Kapazitätsrestriktion c
ist.
Beweis. Sei zunächst f ein maximaler Fluss auf N = (G , c , s, t), der für al-
le mit s inzidenten Kanten straff an c ist. Da f nach Annahme insbesondere
ein Fluss auf N ist, erfüllt f nach Definition 1.1.5 sowohl die Kapazitätsre-
striktionen für jede Kante e E , als auch die Flusserhaltungsbedingungen
für jeden Knoten v aus V = V \{s, t}. Betrachten wir nun die Einschränkung
f von f auf die Kantenmenge des Graphen G = (V, E), also f := f |
E
, so
wird nach Definition der Kapazitätsfunktion c unmittelbar ersichtlich, dass
f die Kapazitätsrestriktionen (M2) des MCFP für alle Kanten e E erfüllt.
Für den Nachweis, dass f ebenfalls den Angebotsrestriktionen (M1) für alle
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
23
v V nachkommt, müssen wir nun die Knotenmenge V in Quellen, Senken
und Durchlaufpunkte unterteilen, und die Bedingungen (M1) für jede Kno-
tenklasse getrennt belegen.
Da jede Quelle v mit s(v) > 0 nach Konstruktion des Hilfsflussnetzwerkes
N genau durch eine eindeutige Kante (s, v) mit der Superquelle s verbunden
und sonst nur inzident mit Kanten der ursprünglichen Menge E ist, ergibt
sich mit den Flusserhaltungsbedingungen für alle mit s benachbarten Knoten
v die folgende Gleichungskette:
e
-
=v
f (e) =
e
+
=v
f (e)
e
-
=v
f (e) =
e
+
=v
f (e) + f ((s, v))
e
-
=v
f (e) =
e
+
=v
f (e) + c ((s, v))
e
-
=v
f (e) =
e
+
=v
f (e) + s(v)
s(v)
=
e
-
=v
f (e) -
e
+
=v
f (e).
Damit erfüllt f die Angebotsrestriktionen (M1) des MCFP für alle Knoten
v V mit s(v) > 0.
Da die Flussmenge, die netto aus der Quelle s hinausfließt in jedem Fluss-
netzwerk genau derjenigen Flussmenge entspricht, die netto in die Senke t
hineinfließt, folgt, dass der Fluss f auch auf allen mit der Senke t inziden-
ten Kanten e straff an der oberen Kapazitätsschranke c (e) ist. Weil nach
Konstruktion des Netzwerkes N jede Senke v mit s(v) < 0 genau durch ei-
ne eindeutige Kante (v, t) mit der Supersenke t verbunden und sonst nur
inzident mit Kanten der ursprünglichen Menge E ist, ergibt sich mit den
Flusserhaltungsbedingungen für alle mit t benachbarten Knoten v:
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
24
e
+
=v
f (e) =
e
-
=v
f (e)
e
+
=v
f (e) =
e
-
=v
f (e) + f ((v, t))
e
+
=v
f (e) =
e
-
=v
f (e) + c ((v, t))
e
+
=v
f (e) =
e
-
=v
f (e) - s(v)
s(v)
=
e
-
=v
f (e) -
e
+
=v
f (e).
Damit erfüllt f auch die Angebotsrestriktionen (M1) des MCFP für alle Kno-
ten v V mit s(v) < 0.
Die verbleibenden Durchlaufpunkte v V mit s(v) = 0 sind nur inzident mit
Kanten der ursprünglichen Menge E, auf der sich die Abbildungen f und f
entsprechen. Deshalb folgt für diese Knoten die Einhaltung der Angebotsre-
striktionen (M1) unmittelbar aus den Flusserhaltungsbedingungen.
Zusammenfassend erfüllt f sowohl die Angebotsrestriktionen (M1), als auch
die Kapazitätsrestriktionen (M2) und ist somit eine zulässige Lösung des
MCFP.
Zum Beweis der Gegenrichtung nehmen wir an, dass durch f eine zulässige
Lösung für das MCFP gegeben ist. Es erfordert nun nicht viel Aufwand diese
Funktion f auf die Kantenmenge E zu erweitern und somit eine Abbildung
f auf N zu erhalten. Dies geschieht wie folgt:
f (e) :=
f (e),
falls e E,
c (e),
falls e E \E.
Nach Definition der Kapazitätsfunktion c und der Konstruktion des Fluss-
netzwerkes N ist sofort ersichtlich, dass die entsprechend obiger Vorschrift
erzeugte Abbildung f die Kapazitätsrestriktionen für alle Kanten e E ,
sowie die Flusserhaltungsbedingungen für alle Knoten v V \{s, t} erfüllt
und somit ein Fluss auf N ist. Zum Nachweis der Maximalität von f sei
durch ({s}, V \{s}) ein Schnitt von N gegeben, dessen Kapazität durch den
folgenden Wert repräsentiert wird:
c({s}, V \{s}) =
e
-
= s
e
+
V \{s}
c (e).
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
25
Für den Wert des Flusses f ergibt sich nach Konstruktion von f und Defi-
nition von c :
w(f ) =
e
-
=s
f (e) -
e
+
=s
f (e) =
e
-
=s
f (e) =
e
-
=s
c (e).
Der Wert des Flusses f und die Kapazität des Schnittes ({s}, V \{s}) stim-
men demnach überein, so dass die Behauptung unmittelbar aus Satz 1.2.6
folgt.
Mit Satz 2.2.2 steht uns an dieser Stelle ein geeignetes Hilfsmittel zur Ver-
fügung, um für ein gegebenes MCFP einen zulässigen Fluss zu konstruieren,
bzw. festzustellen, dass ein solcher nicht existiert. Der folgende Algorith-
mus geht dieser Aufgabe nach, indem er, ausgehend vom Fluss f (e) = 0,
fortwährend augmentierende Wege bzgl. f auf dem Hilfsflussnetzwerk N =
(G , c , s, t) von s nach t bestimmt und f entlang dieser Wege augmentiert.
Kann schließlich nach einer bestimmten Anzahl von Iterationen bezüglich des
aktuellen Flusses f kein augmentierender Weg von s nach t mehr ausfindig
gemacht werden, so ist f nach Satz 1.2.4 bereits maximal. Ist der Wert des
maximalen Flusses durch w(f ) =
vV,s(v)>0
s(v) gegeben, so sättigt f al-
le mit der Superquelle s inzidenten Kanten, und die Einschränkung f von
f auf die Kantenmenge E liefert nach Satz 2.2.2 einen zulässigen Fluss für
das MCFP. Andernfalls existiert kein zulässiger Fluss, und das MCFP ist
unzulässig. Der Algorithmus lässt sich demnach wie folgt formulieren:
2.2.3 Algorithmus (MCFP Zulässigkeit). Gegeben sei ein MCFP mit
zugrunde liegendem Graphen G = (V, E), unterer und oberer Kapazitäts-
funktion 0 bzw. c, sowie einer Angebotsfunktion s.
(1)
Konstruiere das Hilfsflussnetzwerk N = (G , c , s, t) gemäß Definition
2.2.1;
(2)
Setze f (e) := 0 für alle e E ;
(3)
while f ist nicht maximal do
(4)
suche augmentierenden Weg P bzgl. f von s nach t in N;
(5)
if augmentierender Weg P existiert
(6)
then augmentiere f entlang P
(7)
else f ist maximal
(8)
fi
(9)
od
(10) if w(f ) =
vV,s(v)>0
s(v)
(11)
then f := f |
E
ist zulässiger Fluss für MCFP
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
26
(12)
else MCFP ist unzulässig
(13) fi
Im Verlauf des Algorithmus 2.2.3 erfolgt die Bestimmung eines maximalen
Flusses auf dem Flussnetzwerk N = (G , c , s, t) analog zum Verfahren von
Ford-Fulkerson
1
. Selbstverständlich kann zu diesem Zwecke auch jeder ande-
rer Algorithmus zur Bestimmung eines maximalen Flusses auf einem Fluss-
netzwerk Verwendung finden. Die hier dargestellte Version bietet lediglich
die größtmögliche Konformität zur Diskussion des ersten Kapitels.
Zum Abschluss der Zulässigkeitsdiskussion werden wir ein Existenzkriterium
für zulässige Flüsse für das MCFP aufführen, welches als eine Spezialform
des bekannten supply-and-demand theorems
2
aufgefasst werden kann. Zuvor
ist es jedoch notwendig, das Konstrukt des Schnittes auf die Problemstellung
dieses Kapitels auszudehnen.
2.2.4 Bemerkung. Da wir im Kontext des MCFP auf der Menge der Kno-
ten nicht explizit eine Quelle s und eine Senke t hervorheben, ist in diesem
Zusammenhang ein Schnitt (S,T) durch eine beliebige Partition der Knoten-
menge V gegeben. Hierbei kann auch eine der beiden Partitionsmengen leer
sein.
2.2.5 Satz. Für ein entsprechend Definition 2.1.1 formuliertes MCFP mit
unterer Kapazitätsschranke 0 existiert genau dann ein zulässiger Fluss, falls
für jeden Schnitt (S, T ) die folgende Ungleichung erfüllt ist:
c(S, T )
vS
s(v).
Beweis. Wir werden den Beweis des Satzes wie folgt strukturieren:
1. Ausgehend von einem zulässigen Fluss f für das MCFP und zwei be-
liebigen Partitionsmengen S und T der Menge V werden wir, wie im
Beweis von Satz 2.2.2 skizziert, zunächst einen maximalen Fluss f auf
dem Hilfsflussnetzwerk N konstruieren.
2. Anschließend werden wir mit Hilfe der Mengen S und T einen Schnitt
(S , T ) auf dem Hilfsflussnetzwerk N definieren und den Wert des Flus-
ses w(f ) in bekannter Weise durch die Kapazität des Schnittes c(S , T )
abschätzen.
1
vergleiche Jungnickel [22] S.206
2
vergleiche Jungnickel [22] S.295
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
27
3. Schließlich werden wir die Kapazitäten der Schnitte (S , T ) und (S, T )
zueinander in Beziehung setzen und unter Verwendung obiger Abschät-
zung die Behauptung belegen.
Sei also f ein zulässiger Fluss für das MCFP. Überdies sei durch S und T
eine beliebige Partition der Knotenmenge V gegeben. Wie im Beweis von
Satz 2.2.2 bereits veranschaulicht, können wir durch die Festlegung
f (e) :=
f (e),
falls e E,
c (e),
falls e E \E.
einen maximalen Fluss f auf dem Hilfsflussnetzwerk N definieren, der nach
Konstruktion alle mit der Superquelle s inzidenten Kanten sättigt. Dabei ist
der Wert des Flusses durch w(f ) =
vV,s(v)>0
s(v) gegeben.
Definieren wir S := S {s} und T := T {t}, so liegt durch (S , T ) offen-
sichtlich ein Schnitt von N vor. Nach Lemma 1.2.2 besteht somit zwischen
dem Wert des Flusses w(f ) und der Kapazität des Schnittes c(S , T ) der
folgende Zusammenhang:
w(f ) =
v V
s(v)> 0
s(v) c(S , T )
(2.1)
Da sich die Mengen S und S nur durch die Quelle s und die Mengen T
und T nur durch die Senke t voneinander unterscheiden, ist es möglich, die
Kapazität des Schnittes (S , T ) mit Hilfe der Kapazität des Schnittes (S, T )
darzustellen. Zur Berechnung der Kapazität eines Schnittes sind nur die Ka-
pazitäten derjenigen Kanten relevant, deren Anfangs- und Endknoten jeweils
in verschiedenen Partitionsmengen des Schnittes liegen. Bezogen auf unsere
beiden Schnitte (S , T ) und (S, T ) impliziert dies, dass Kapazitätsunterschie-
de lediglich durch Kanten hervorgerufen werden können, die inzident mit der
Quelle s bzw. der Senke t sind. Alle anderen, für die Kapazitäten der Schnitte
maßgeblichen Kanten haben ihren Anfangspunkt in S und ihren Endpunkt in
T , respektive umgekehrt, und sind damit für die Kapazitäten beider Schnitte
in gleicher Weise Wert beitragend.
Es sind demnach folgende Überlegungen anzustellen:
1. Sei e = (s, v) eine mit s inzidente Kante der Menge E \E. Nach Kon-
struktion des Netzwerkes N ist der Knoten v mit einem positiven An-
gebot s(v) > 0 behaftet und die Kapazität der Kante e ist durch
c (e) = s(v) gegeben. Nun sind zwei Fälle zu unterscheiden:
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
28
(a) Der Endknoten v der Kante e liegt in der Partitionsmenge S.
Damit liegen sowohl Anfangs-, als auch Endknoten der Kante e in
der Menge S , und folglich ist e bei der Berechnung der Kapazität
des Schnittes (S , T ) irrelevant.
(b) Der Endknoten v der Kante e liegt in der Partitionsmenge T . Da-
mit gehört der Anfangsknoten der Kante e der Menge S an, wäh-
rend der Endknoten von e in der Menge T enthalten ist. Folglich
liefert die Kante e als Vorwärtskante einen positiven Wertbeitrag
zur Kapazität des Schnittes (S , T ), und zwar in Höhe von s(v).
Da die Kante e in der Menge E \E liegt, ist sie bei der Berechnung
der Kapazität des Schnittes (S, T ) nicht zu berücksichtigen.
2. Sei e = (v, t) eine mit t inzidente Kante der Menge E \E. Nach Kon-
struktion des Netzwerkes N besitzt der Knoten v ein negatives Angebot
s(v) < 0 und die Kapazität der Kante e ist durch c (e) = -s(v) gege-
ben. Auch hier ist wieder eine differenzierte Betrachtung erforderlich:
(a) Der Anfangsknoten v der Kante e liegt in der Partitionsmenge T .
Damit liegen sowohl Anfangs-, als auch Endknoten der Kante e in
der Menge T und folglich ist e bei der Berechnung Kapazität des
Schnittes (S , T ) irrelevant.
(b) Der Anfangsknoten v der Kante e liegt in der Partitionsmenge S.
Damit gehört der Anfangsknoten der Kante e der Menge S an,
während der Endknoten von e in der Menge T enthalten ist. Folg-
lich liefert die Kante e als Vorwärtskante einen positiven Wertbei-
trag zur Kapazität des Schnittes (S , T ), und zwar in Höhe von
-s(v). Da die Kante e in der Menge E \E liegt, ist sie bei der
Berechnung der Kapazität des Schnittes (S, T ) nicht zu berück-
sichtigen.
Entsprechend dieser Überlegungen besteht nun die folgende Beziehung zwi-
schen den Kapazitäten der beiden Schnitte (S , T ) und (S, T ):
c(S , T ) = c(S, T ) -
v S
s(v)< 0
s(v) +
v T
s(v)> 0
s(v)
(2.2)
Das Einsetzen von Gleichung (2.2) in Abschätzung (2.1) liefert:
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
29
c(S, T ) -
v S
s(v)< 0
s(v) +
v T
s(v)> 0
s(v)
v V
s(v)> 0
s(v)
c(S, T ) -
v S
s(v)< 0
s(v)
v S
s(v)> 0
s(v)
c(S, T )
vS
s(v),
so dass die Behauptung folgt.
2.3
MCFP Optimalität
Durch die Ergebnisse des vorangegangenen Abschnittes sind wir an dieser
Stelle in der Lage, für ein gegebenes MCFP über Zulässigkeit bzw. Unzu-
lässigkeit zu entscheiden und gegebenenfalls eine zulässige Lösung zu kon-
struieren. In diesem Abschnitt werden wir uns mit der Fragestellung ausein-
andersetzen, wann eine zulässige Lösung für das MCFP optimal ist, wann
also ein zulässiger Fluss bereits minimale Kosten aufweist. Der Existenz von
Zertifikaten für optimale Lösungen wird insbesondere bei der Konstruktion
von Algorithmen zur Lösung des MCFP eine große Bedeutung beigemessen,
da uns mit diesen ein adäquates Abbruchkriterium zur Verfügung steht. Es
signalisiert uns, wann ein Fluss minimale Kosten besitzt und somit nicht
weiter verbessert werden kann. Überdies werden wir durch die hier angestell-
ten Überlegungen bereits konkrete Ideen für den Prozess der Optimierung
entwickeln, die später in den Algorithmen umgesetzt werden.
Es werden in der Literatur im Wesentlichen drei charakteristische Optima-
litätseigenschaften für das MCFP diskutiert, die in sich äquivalent sind und
somit ineinander überführt werden können. Neben der negativen Kreis Op-
timalitätseigenschaft sind dies die reduzierte Kosten Optimalitätseigenschaft
und die komplementäre Schlupf Optimalitätseigenschaft. Wir werden uns mit
unseren Betrachtungen in diesem Abschnitt auf die negative Kreis Optimali-
tätseigenschaft konzentrieren, da diese unter den drei aufgeführten die wohl
gängigste ist und überdies die größtmögliche Konformität mit obiger Nota-
tion bietet. Bei der sich anschließenden Diskussion des Netzwerk Simplex
Algorithmus im nächsten Kapitel, werden wir die Optimalität einer zuläs-
sigen Lösung für das MCFP mit Hilfe der reduzierten Kosten nachweisen,
wofür uns an dieser Stelle jedoch noch einige Begrifflichkeiten fehlen.
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
30
Bevor wir unser erstes Optimalitätskriterium formulieren können, ist es zu-
nächst notwendig, das Konstrukt des residualen Netzwerkes durch Einfüh-
rung einer Kostenfunktion zu erweitern und somit in den Kontext des MCFP
zu übertragen.
2.3.1 Definition (residuales Kostennetzwerk). Gegeben sei ein MCFP
mit zugrunde liegendem Graphen G = (V, E), oberer Kapazitätsfunktion c,
Angebotsfunktion s, Kostenfunktion , sowie ein zulässiger Fluss f . Ferner
sei N
f
= (G
f
, r
f
) das entsprechend Definition 1.2.7 konstruierte zugehörige
residuale Netzwerk. Definiert man auf der Kantenmenge E
f
des residualen
Netzwerkes N
f
eine Kostenfunktion durch
· (e
f
1
) = (e), wobei die Kante e
f
1
des residualen Netzwerkes N
f
und
die zugehörige Kante e des zugrunde liegenden Graphen G = (V, E)
gemäß Definition 1.2.7 die gleiche Orientierung haben,
· (e
f
2
) = -(e), wobei die Kante e
f
2
des residualen Netzwerkes N
f
und
die zugehörige Kante e des zugrunde liegenden Graphen G = (V, E)
gemäß Definition 1.2.7 entgegengesetzte Orientierungen haben,
so bildet das Tripel K
f
= (G
f
, r
f
, ) das zu f gehörige residuale Kostennetz-
werk.
Neben dem residualen Kostennetzwerk bildet die folgende Definition eine
notwendige Voraussetzung für das Verständnis der sich anschließenden Op-
timalitätsbedingung.
2.3.2 Definition. Gegeben sei ein entsprechend Definition 2.1.1 definiertes
MCFP, wobei die Angebotsfunktion s(v) für alle Knoten v V den Wert 0
annehme. Dann bezeichnet man einen zulässigen Fluss g : E R für dieses
spezielle MCFP als Zirkulation.
Nun sind wir in der Lage, das negative Kreis Optimalitätskriterium zu for-
mulieren.
2.3.3 Satz (negative cycle optimality condition). Eine zulässige Lösung
f für das MCFP ist genau dann optimal, wenn das residuale Kostennetzwerk
K
f
keine gerichteten Kreise negativer -Länge enthält.
Beweis. Sei zunächst C
f
ein gerichteter Kreis negativer -Länge innerhalb
des residualen Kostennetzwerkes K
f
und somit die Bedingung
e
f
C
f
(e
f
) <
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
31
0 erfüllt. Offensichtlich ist ein gerichteter Kreis innerhalb des residualen Kos-
tennetzwerkes K
f
äquivalent zu einem augmentierenden Kreis im zugrunde
liegenden Netzwerk. Ist durch
:= min{r
f
(e
f
) : e
f
C
f
}
das Minimum der Residualkapazitäten der auf dem Kreis C
f
liegenden Kan-
ten e
f
definiert, so lässt sich f entlang dieses Kreises wie folgt augmentieren:
f (e) :=
f (e) +
e
f
1
C
f
,
f (e) -
e
f
2
C
f
,
f (e)
sonst.
Nach Definition der Residualkapazitäten r
f
und der Tatsache, dass f entlang
eines Kreises augmentiert wird, ist sofort klar, dass f ebenfalls eine zulässige
Lösung für das MCFP darstellt. Für die Kostendifferenz der beiden Lösungen
f und f ergibt sich:
e E
(e)f (e) -
e E
(e)f (e)
=
e
f1
C
f
(e) -
e
f2
C
f
(e)
=
e
f
C
f
(e
f
)
<
0.
Damit ist f eine zulässige Lösung mit geringeren Kosten und somit der Fluss
f nicht optimal.
Zum Beweis der Rückrichtung nehmen wir an, dass das zur zulässigen Lösung
f gehörige residuale Kostennetzwerk K
f
keine gerichteten Kreise negativer
-Länge enthält. Ferner sei durch f
ein beliebiger weiterer zulässiger Fluss
für das MCFP gegeben. Zum Nachweis der Behauptung ist es ausreichend
zu zeigen, dass die Kosten des Flusses f
mindestens so hoch sind wie die
Kosten des Flusses f . In dieser Absicht definieren wir eine weitere Abbildung
g : E R durch g(e) := f
(e) - f (e), für alle e E. Wegen der Zulässig-
keit der beiden Flüsse f und f
ist sofort klar, dass diese Abbildung g für
alle Knoten v V ein Angebot von Null aufweist und somit eine Zirkulati-
on auf unserem Graphen G = (V, E) darstellt. Bei genauerer Untersuchung
der Abbildung g lässt sich nun auf die folgende Weise ein Zusammenhang
zwischen dem Vorzeichen der Abbildung g und der Struktur des residualen
Kostennetzwerkes K
f
aufdecken:
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
32
· Für alle Kanten e E mit g(e) > 0 ist nach Definition der Zirkulation
g die Ungleichung f (e) < f
(e) c(e) erfüllt. Folglich ist f nicht straff
an der oberen Kapazitätsrestriktion c, und somit enthält das residuale
Kostennetzwerk K
f
für solche Kanten e wenigstens eine Kante e
f
1
mit
gleicher Orientierung.
· Für alle Kanten e E mit g(e) < 0 ist nach Definition der Zirkulation
g die Ungleichung 0 f
(e) < f (e) erfüllt. Folglich ist f nicht straff
an der unteren Kapazitätsschranke 0, und somit enthält das residuale
Kostennetzwerk K
f
für solche Kanten e wenigstens eine Kante e
f
2
mit
entgegengesetzter Orientierung.
Die Zirkulation g induziert nun unter Berücksichtigung dieser Überlegungen
wie folgt eine Abbildung auf den Kanten E
f
des residualen Kostennetzwer-
kes K
f
:
(e
f
) :=
g(e),
falls g(e) > 0 und e
f
= e
f
1
,
-g(e), falls g(e) < 0 und e
f
= e
f
2
,
0,
sonst.
Offenbar bildet gemäß dieser Definition eine nichtnegative Zirkulation auf
dem residualen Kostennetzwerk K
f
. Dieses kann wie folgt eingesehen werden:
e
-
f
=v
(e
f
) -
e
+
f
=v
(e
f
)
=
=
e
-
f1
=v
(e
f
1
) +
e
-
f2
=v
(e
f
2
) -
e
+
f1
=v
(e
f
1
) +
e
+
f2
=v
(e
f
2
)
=
=
e
-
=v
g(e)>0
g(e) +
e
+
=v
g(e)<0
(-g(e)) -
e
+
=v
g(e)>0
g(e) +
e
-
=v
g(e)<0
(-g(e))
=
=
e
-
=v
g(e)>0
g(e) +
e
-
=v
g(e)<0
g(e) -
e
+
=v
g(e)>0
g(e) +
e
+
=v
g(e)<0
g(e)
=
=
e
-
=v
g(e) -
e
+
=v
g(e)
=
0.
Das Angebot ist somit für alle Knoten v V identisch 0 und die Nichtnega-
tivität von folgt unmittelbar aus der Definition. Nach dem Flusszerlegungs-
KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)
33
satz für nichtnegative Zirkulationen
3
existieren nun innerhalb des residualen
Kostennetzwerkes K
f
gerichtete Kreise C
1
, ..., C
r
, wobei r m = |E|, so
dass die Zirkulation durch nichtnegative Flüsse
C
1
, ...,
C
r
entlang dieser
Kreise dargestellt werden kann. Dabei sind die Flüsse
C
i
entlang der Kreise
C
i
, für i = 1, ..., r auf der Kantenmenge E
f
durch
C
i
(e
f
) :=
i
,
e
f
C
i
,
0,
e
f
E
f
\C
i
definiert, und für die Zirkulation ergibt sich somit =
r
i=1
C
i
. Die Kos-
ten der Kreise C
i
, i = 1, ..., r, die durch das Durchfließen einer Flusseinheit
verursacht werden, lassen sich durch
(C
i
) =
e
f1
C
i
(e) -
e
f2
C
i
(e) =
e
f
C
i
(e
f
).
erfassen. Nach unserer Annahme existieren innerhalb des residualen Netz-
werkes keine Kreise negativer -Länge, woraus (C
i
) 0 für alle i = 1, ..., r
folgt.
Aus diesen Überlegungen resultiert nun die folgende Gleichungskette für die
Kosten der Zirkulation g:
eE
(e)g(e)
=
=
eE
g(e)>0
(e)g(e) -
eE
g(e)<0
(e)(-g(e))
=
=
e
f1
E
f
(e
f
1
)(e
f
1
) +
e
f2
E
f
(e
f
2
)(e
f
2
)
=
=
e
f
E
f
(e
f
)(e
f
)
=
=
r
i=1
(C
i
)
C
i
0.
Schließlich ergibt sich nach Konstruktion von g für die Kosten der beiden
zulässigen Flüsse f und f
eE
(e)f (e)
eE
(e)f
(e).
3
vergleiche Jungnickel [22] S.332
Ende der Leseprobe aus 170 Seiten
- nach oben
Details
- Arbeit zitieren
- , 2004, Ein polynominaler primaler Netzwerk Simplex Algorithmus zur Berechnung von Flüssen mit minimalen Kosten, Hamburg, Bedey Media GmbH, https://www.diplom.de/document/226285
Ähnliche Arbeiten
Deutschlands größter Sharing Community
Jetzt Zusammenfassungen, Skripte und Klausuren kostenlos downloaden!
Uniturm.de
Ihre Vorteile als Autor
Geld verdienen Für jedes verkaufte Exemplar erhalten Sie Autorenhonorar - bis zu 40%.Kostenlose Buchveröffentlichung
Als eBook-Studie im Original und / oder auf Wunsch zusätzlich als hochwertiges Fachbuch in unserem renommierten Buchverlag.
Renommee als Fachbuchautor
Präsentieren Sie sich als Fachfrau oder Fachmann in Ihrem Fachgebiet und machen Sie sich bekannt.
Persönliche Betreuung
Unser Lektorat wird Sie persönlich betreuen und ist auch telefonisch unter 040-655992-14 erreichbar.
Weltweit im Buchhandel
Ihr Buch ist weltweit im Buchhandel und Online-Buchhandel wie z.B. amazon erhältlich.
Jetzt Autor werden!
Kommentare