Ein polynominaler primaler Netzwerk Simplex Algorithmus zur Berechnung von Flüssen mit minimalen Kosten

Pliefke, Timm

Ein polynominaler primaler Netzwerk Simplex Algorithmus zur Berechnung von Flüssen mit minimalen Kosten

Zusammenfassung

Inhaltsangabe:Einleitung:
Es gibt zwei Wege, die Rentabilität der Arbeit eines Geschäfts, eines Unternehmens 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 Entdeckung 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 Organisation und Planung der Produktion die erste Arbeit auf dem Gebiet der mathematischen 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 im Jahre 1947. Bis heute ist der Simplex Algorithmus eines der mächtigsten und das in der Praxis am weitesten verbreitete Verfahren zur Lösung linearer Programme. Komplexe Problemstellungen mit tausenden von Variablen und Restriktionen lassen sich mit modernen Implementierungen des Algorithmus (wie z.B. CPLEX) 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 Kommunikationsnetzen (Shortest Path Problem, SPP), die Maximierung des Verkehrsflusses auf einem vorgegebenen Straßennetz (Maximum Flow Problem, MFP), oder der kostenminimale Transport von Gütern zwischen Produzenten und Käufern (Minimum Cost Flow Problem, MCFP), weisen eine spezielle Struktur auf, welche es erlaubt, diese, selbst bei komplexen Zusammenhängen, anhand von geeigneten Graphen und Netzwerken zu modellieren. Probleme dieser Art werden in der Kategorie Netzwerkprobleme 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 Programme 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 […]

Leseprobe

Inhaltsverzeichnis

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.

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

1 Grundlagen

1.1 Graphen, Netzwerke und Flüsse . . . . . . . . . . . . . . . . .

1.2 Eigenschaften maximaler Flüsse . . . . . . . . . . . . . . . . .

2 Das Minimum Cost Flow Problem (MCFP)

2.1 Die Problemstellung . . . . . . . . . . . . . . . . . . . . . . . 17

2.2 MCFP Zulässigkeit . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3 MCFP Optimalität . . . . . . . . . . . . . . . . . . . . . . . . 29

3 Der Netzwerk Simplex Algorithmus

3.1 Baumlösungen und Baumstrukturen . . . . . . . . . . . . . . . 37

3.2 Initialisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.3 Der Netzwerk Simplex Algorithmus . . . . . . . . . . . . . . . 54

4 Der Premultiplier Algorithmus

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

INHALTSVERZEICHNIS

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

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

wie z.B. CPLEX

EINFÜHRUNG

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

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.

KAPITEL 1. GRUNDLAGEN

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

, ..., e

) eine Folge von Knoten

, ..., v

) gegeben, so dass e

= (v

i-1

, v

) oder e

= (v

, v

i-1

) erfüllt ist, so

heißt der Kantenzug (e

, ..., e

) bzw. die entsprechende Folge von Knoten

, ..., v

) ein Kreis, falls v

= v

Gültigkeit besitzt. Dabei bezeichnet man

= (v

i-1

, v

) als Vorwärtskante und e

= (v

, 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

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:

f (e) =

f (e),

für alle v V \{s, t}.

KAPITEL 1. GRUNDLAGEN

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

f (e) -

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

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.

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

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

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.

vergleiche Ahuja et al. [1] S.193

KAPITEL 1. GRUNDLAGEN

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

f (e) -

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

f (e) -

f (e)

f (e) -

f (e) +

f (e) -

f (e) =

f (e) -

f (e).

Mit Hilfe der Kapazitätsbeschränkungen lässt sich nun aus obiger Gleichungs-

kette die folgende Abschätzung herleiten:

w(f ) =

f (e) -

f (e)

c(e) -

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

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

und wie folgt definiert:

:= min{c(e) - f (e) : (e

, e

) P },

:= min{f (e) : (e

, e

) P },

· := min{

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

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

f (e) -

f (e) =

c(e) -

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

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

= (G

, r

) mit Knotenmenge V , Kantenmenge E

und Residu-

alkapazitätsfunktion r

: E

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

eine Vorwärtskante

= (e

, e

) mit gleicher Orientierung eingeführt. Die Residualkapa-

zität dieser Kante wird durch r

) := 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

eine Rückwärtskan-

te e

= (e

, e

) mit entgegengesetzter Orientierung eingeführt. Die

Residualkapazität dieser Kante ist durch r

) := 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

mindestens eine Kante e

existiert, welche die beiden Knoten

KAPITEL 1. GRUNDLAGEN

Abbildung 1.1: residuales Netzwerk

verbindet. Die Orientierung der Kante(n) e

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

entspricht der von e.

Die Kante e wird also als Vorwärtskante e

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

der von e ent-

gegengesetzt. Somit wird die Kante e als Rückwärtskante e

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

werden zwei Kanten

und e

eingeführt, wobei wie zuvor die Orientierung der Kante e

mit

der Orientierung von e identisch ist, währenddessen die Orientierung von e

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

= (V, E

) für jeden Fluss f erhalten.

Durch die Residualkapazität r

einer Kante e

im Netzwerk N

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

Eine Suche nach einem augmentierenden Weg P bezüglich eines Flusses f

KAPITEL 1. GRUNDLAGEN

zwischen zwei Knoten v und w eines Netzwerkes N ist, entsprechend dieser

Überlegungen, äquivalent zur Suche eines gerichteten Weges P

von v nach

w im residualen Netzwerk N

. Existiert solch ein augmentierender Weg, so

kann f entlang P um := min{r

) : e

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

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.

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

KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)

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

s(v) = 0 erfüllt wird. Das Minimum Cost

Flow Problem ist schließlich durch

Minimiere

(e)f (e)

unter

f (e) -

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)

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

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 ) :=

(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

(e) := 0,

für alle e E

(e) := c(e) - b(e),

für alle e E

(v) := s(v) +

b(e) -

b(e),

für alle v V

auf ein Problem MCFP

, welches durch

KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)

Minimiere

(e)f

(e)

unter

(e) -

(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 :=

(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:

(v) =

(e) -

(e)

(f (e) - b(e)) -

(f (e) - b(e))

f (e) -

f (e) +

b(e) -

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)

) =

(e)f

(e) =

(e)(f (e) - b(e))

(e)f (e) -

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

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 |

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

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:

f (e) =

f (e)

f (e) =

f (e) + f ((s, v))

f (e) =

f (e) + c ((s, v))

f (e) =

f (e) + s(v)

s(v)

f (e) -

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)

f (e) =

f (e)

f (e) =

f (e) + f ((v, t))

f (e) =

f (e) + c ((v, t))

f (e) =

f (e) - s(v)

s(v)

f (e) -

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}) =

= s

V \{s}

c (e).

KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)

Für den Wert des Flusses f ergibt sich nach Konstruktion von f und Defi-

nition von c :

w(f ) =

f (e) -

f (e) =

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)

(9)

(10) if w(f ) =

vV,s(v)>0

s(v)

(11)

then f := f |

ist zulässiger Fluss für MCFP

KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)

(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

. 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

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 )

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.

vergleiche Jungnickel [22] S.206

vergleiche Jungnickel [22] S.295

KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)

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)

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

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 )

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)

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

= (G

, r

) das entsprechend Definition 1.2.7 konstruierte zugehörige

residuale Netzwerk. Definiert man auf der Kantenmenge E

des residualen

Netzwerkes N

eine Kostenfunktion durch

· (e

) = (e), wobei die Kante e

des residualen Netzwerkes N

und

die zugehörige Kante e des zugrunde liegenden Graphen G = (V, E)

gemäß Definition 1.2.7 die gleiche Orientierung haben,

· (e

) = -(e), wobei die Kante e

des residualen Netzwerkes N

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

= (G

, r

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

keine gerichteten Kreise negativer -Länge enthält.

Beweis. Sei zunächst C

ein gerichteter Kreis negativer -Länge innerhalb

des residualen Kostennetzwerkes K

und somit die Bedingung

) <

KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)

0 erfüllt. Offensichtlich ist ein gerichteter Kreis innerhalb des residualen Kos-

tennetzwerkes K

äquivalent zu einem augmentierenden Kreis im zugrunde

liegenden Netzwerk. Ist durch

:= min{r

) : e

}

das Minimum der Residualkapazitäten der auf dem Kreis C

liegenden Kan-

ten e

definiert, so lässt sich f entlang dieses Kreises wie folgt augmentieren:

f (e) :=

f (e) +

f (e) -

f (e)

sonst.

Nach Definition der Residualkapazitäten r

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

(e)

)

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

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

aufdecken:

KAPITEL 2. DAS MINIMUM COST FLOW PROBLEM (MCFP)

· 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ür solche Kanten e wenigstens eine Kante e

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ür solche Kanten e wenigstens eine Kante e

mit

entgegengesetzter Orientierung.

Die Zirkulation g induziert nun unter Berücksichtigung dieser Überlegungen

wie folgt eine Abbildung auf den Kanten E

des residualen Kostennetzwer-

kes K

) :=

g(e),

falls g(e) > 0 und e

= e

-g(e), falls g(e) < 0 und e

= e

sonst.

Offenbar bildet gemäß dieser Definition eine nichtnegative Zirkulation auf

dem residualen Kostennetzwerk K

. Dieses kann wie folgt eingesehen werden:

) -

)

) +

) -

) +

)

g(e)>0

g(e) +

g(e)<0

(-g(e)) -

g(e)>0

g(e) +

g(e)<0

(-g(e))

g(e)>0

g(e) +

g(e)<0

g(e) -

g(e)>0

g(e) +

g(e)<0

g(e)

g(e) -

g(e)

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)

satz für nichtnegative Zirkulationen

existieren nun innerhalb des residualen

Kostennetzwerkes K

gerichtete Kreise C

, ..., C

, wobei r m = |E|, so

dass die Zirkulation durch nichtnegative Flüsse

, ...,

entlang dieser

Kreise dargestellt werden kann. Dabei sind die Flüsse

entlang der Kreise

, für i = 1, ..., r auf der Kantenmenge E

durch

) :=

definiert, und für die Zirkulation ergibt sich somit =

i=1

. Die Kos-

ten der Kreise C

, i = 1, ..., r, die durch das Durchfließen einer Flusseinheit

verursacht werden, lassen sich durch

) =

(e) -

(e) =

erfassen. Nach unserer Annahme existieren innerhalb des residualen Netz-

werkes keine Kreise negativer -Länge, woraus (C

) 0 für alle i = 1, ..., r

folgt.

Aus diesen Überlegungen resultiert nun die folgende Gleichungskette für die

Kosten der Zirkulation g:

(e)g(e)

g(e)>0

(e)g(e) -

g(e)<0

(e)(-g(e))

)(e

) +

)(e

)

)(e

)

i=1

)

Schließlich ergibt sich nach Konstruktion von g für die Kosten der beiden

zulässigen Flüsse f und f

(e)f (e)

(e)f

(e).

vergleiche Jungnickel [22] S.332

Details

Seiten
Erscheinungsform: Originalausgabe
Jahr: 2004
ISBN (eBook): 9783836621120
Dateigröße: 1.3 MB
Sprache: Deutsch
Institution / Hochschule: Universität Augsburg – Mathematisch-Naturwissenschaftliche Fakultät
Erscheinungsdatum: 2014 (April)
Note: 1,0
Schlagworte: simplex algorithmus mimimal cost flow polynomialität implementierung netzwerk

Autor

Timm Pliefke (Autor:in)

Ein polynominaler primaler Netzwerk Simplex Algorithmus zur Berechnung von Flüssen mit minimalen Kosten

Zusammenfassung

Leseprobe

Inhaltsverzeichnis

Details

Autor

Timm Pliefke (Autor:in)