Netzwerk Simplex Algorithmus fur

Minimum Cost Flow Probleme

Jan Burkl

13. Juni 2003

Seminar Universitat Trier

Sommersemester 2003

Prof. S. Naher, O. Zlotowski

1

Inhaltsverzeichnis

1 Einleitung 3

2 Bezeichnungen und Definitionen 3

3 Spanning Tree Solution 6

4 Beschreibung einer Spanning Tree Structure 10

5 Knotenpotentiale berechnen 12

6 Initialer Spannbaum 14

7 Simplex-Algorithmus 16

7.1 Entering Arc . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

7.1.1 Dantzig’s Pivot Regel . . . . . . . . . . . . . . . . . . . 17

7.1.2 First Eligable Arc Rule . . . . . . . . . . . . . . . . . . 17

7.1.3 Kandidaten-Liste Pivot-Regel . . . . . . . . . . . . . . 18

7.2 Leaving Arc . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

7.3 Spannbaum updaten . . . . . . . . . . . . . . . . . . . . . . . 20

7.4 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

8 Strongly Feasible Spanning Tree 25

8.1 Leaving Arc Rule . . . . . . . . . . . . . . . . . . . . . . . . . 26

2

1 Einleitung

Der Simplex-Algorithmus ist einer der machtigsten Algorithmen zum Losen

von Optimierungsproblemen. Obwohl er nicht direkt fur eine Netzwerkstruk-

tur konstruiert wurde, lasst er sich doch einfach modifizieren, um ein Mini-

mum Cost Flow Problem effizient zu losen.

Im einzelnen betrachtet diese Seminararbeit folgende Aspekte:

Es wird gezeigt, dass jedes Minimum Cost Flow Problem mindestens ei-

ne Spanning Tree Solution besitzt. Diese Spanning Tree Solutions sind die

Grundlage der Simplex-Methode, da von einer Losung zur nachsten gewech-

selt wird, bis die Optimallosung gefunden ist. Als nachstes wird beschrieben,

wie solche Spanning Trees am geschicktesten implementiert werden konnen,

damit der Algorithmus auch effizient ausgefuhrt werden kann. Bevor dann

die eigentliche Simplex-Methode erklart wird, muss vorher gezeigt werden,

wie die sogenannten Knotenpotentiale berechnet werden und ein initialer

Spannbaum konstruiert wird. Auch dieser Schritt muss genau durchdacht

sein, damit der Netzwerk-Simplex-Algorithmus effizient ausgefuhrt werden

kann. Schließlich wird eine einfache Methode beschrieben, wie der Algorith-

mus so modifiziert werden kann, dass eine Terminierung bzw. die Finitheit

garantiert ist.

2 Bezeichnungen und Definitionen

Einige grundlegende Begriffe aus der Graphentheorie werden in dieser Arbeit

vorausgesetzt. So betrachten wir ein gerichtetes Netzwerk N mit n Knoten

und m gerichteten Kanten. Die Menge der gerichteten Kanten nennen wir

E. Auf diesem Netzwerk N konnen wir ein sogenanntes Minimum Cost Flow

Problem beschreiben, dass wir mit Hilfe des Netzwerk Simplex Algorithmus

3

losen konnen:

Definition 2.1 (Min Cost Flow Problem).

Sei N ein gerichtetes Netzwerk. Jede Kante (i, j) ∈ E hat bestimmte Kosten

cij, die die Kosten pro Flusseinheit auf dieser Kante beschreiben. Außerdem

hat jede Kante (i, j) ∈ E eine obere Kapazitatsschranke uij, das die maximal

mogliche Menge von Flusseinheiten auf dieser Kante beschreibt. Mit jedem

Knoten i gibt es auch einen ganzzahligen Wert b(i), der das Angebot (b(i) >

0) bzw. die Nachfrage (b(i) < 0) des Knotens angibt. Der Fluss, der uber

eine Kante (i, j) ∈ E fließt, wird mit xij bezeichnet.

Das Min Cost Flow Problem wird jetzt wie folgt definiert:

min∑

(i,j)∈E

cijxij

s.t.

∑{j:(i,j)∈E}

xi,j −∑

{j:(j,i)∈E}

xji = b(i) ∀i ∈ N (1)

0 ≤ xij ≤ uij (i, j) ∈ E (2)

Bemerkung 1.

Wir betrachten ausschließlich Netzwerke N, deren Kantenfluss nach unten

durch 0 beschrankt ist.

Bemerkung 2.

Wir sprechen von einem zulassigen Fluss x, wenn die Bedingungen (1) und

(2) fur alle xij ((i, j) ∈ E) erfullt sind.

Um aus dem zulassigen Fluss einen optimalen zulassigen Fluss zu berech-

nen, benotigt der Simplex Algorithmus den Spanning Tree.

4

Definition 2.2.

Ein zusammenhangender Graph ohne Kreis ist ein Spanning Tree T von N ,

wenn alle Knoten aus N auch in T enthalten sind.

Ein Spanning Tree T von N mit zulassigem Fluss entspricht einer Ba-

sislosung des Simplex Algorithmus.

Weiterhin benotigen wir die reduzierten Kosten aller Kanten:

Definition 2.3.

cπij bezeichnet die reduzierten Kosten einer Kante (i, j) ∈ E wenn gilt:

cπij = cij − π(i) + π(j),

wobei π(i) das Knotenpotential des Knotens i ist (Das Knotenpotential eines

Knotens i entspricht in einem Spanning Tree dem negativen Distanzwert von

der Wurzel zum Knoten i).

Da wir im Simplex Algorithmus mit den reduzierten Kosten arbeiten, ist

es wichtig den Zusammenhang zwischen den Funktionswerten

z(π) :=∑

(i,j)∈E

cπijxij

und

z(0) :=∑

(i,j)∈E

cijxij

zu verstehen.

Sei zu Beginn π(0). Wir erhohen jetzt das Knotenpotential von Knoten k zu

π(k). Dadurch werden die reduzierten Kosten jeder ausgehenden Kante von

k verringert, wahrend die reduzierten Kosten der eingehenden Kanten um

π(k) erhoht werden. Somit andert sich der Zielfunktionswert um π(k)-mal

dem ausgehenden Fluss minus π(k)-mal dem eingehenden Fluss von k. Da

5

der ausgehende Fluss gleich dem eingehenden Fluss sein muss (Massenba-

lance), reduziert eine Erhohung des Potentials von Knoten k um π(k) den

Zielfunktionswert um π(k)b(k). Wiederholt man dies fur alle Knoten, erhalt

man

z(0)− z(π) =∑i∈N

π(i)b(i).

Fur ein gegebenes π ist das Ergebnis konstant und somit gilt

min z(π) ≡ min z(0).

3 Spanning Tree Solution

Definition 3.1.

Sei x eine zulassige Losung fur ein Netzwerk N, dann heißt eine Kante (i, j)

• frei, wenn 0 < xij < uij,

• beschrankt, wenn xij = 0 oder xij = uij,

wobei xij der Fluss der Kante (i, j) ist und uij die obere Flussgrenze der

Kante (i, j). Der Einfachheit halber ist die untere Flussgrenze gleich 0.

Bemerkung 3.

Auf beschrankten Kanten kann man den Fluss nur verringern (xij = uij)

oder nur erhohen (xij = 0).

Definition 3.2.

• Eine Losung eines Netzwerks N heißt Cycle Free Solution, wenn sie

keinen Kreis enthalt, der nur aus freien Kanten besteht.

6

• Eine Losung heißt Spanning Tree Solution, wenn (zu einem Span-

ning Tree aus dem gegebenen Netzwerk) jede nicht-Baum-Kante eine

beschrankte Kante ist.

Bemerkung 4.

Jede Spanning Tree Solution ist eine Cycle Free Solution. Umgekehrt gilt dies

nicht.

Eine Cycle Free Solution erhalten wir in der Simplex-Methode immer,

wenn wir den Fluss des Kreises, der durch Einfugen einer Kante in den

Spannbaum entstanden ist, maximal erhoht haben (Kapitel 7.2). Diese Cycle

Free Solution konnen wir dann ganz einfach wieder zu einer Spanning Tree

Solution umbauen. Betrachtet man nur die freien Kanten einer Cycle Free

Solution, so erhalt man einen Wald mit k Baumen (im Spezialfall k = 1 di-

rekt einen Spanning Tree), da nach Definition 3.2 jeder ursprungliche Kreis

mindestens eine beschrankte Kante enthalt. Wenn man jetzt mit k − 1 be-

schrankten Kanten alle k entstandenen Baume zusammenfugt, erhalt man

eine Spanning-Tree-Solution.

Beispiel 3.1.

Wir konnen an Beispiel aus Abbildung 3.1 erkennen, dass es moglich ist aus

einer Cycle Free Solution verschiedene Spanning Tree Solutions zu gewinnen.

Denkbar ware auch eine Losung mit den Kanten (1, 3), (3, 2), (3, 4).

Eine Spanning Tree Solution teilt die Menge der Kanten des Netzwerks

in drei Gruppen auf:

T: Alle Kanten im Spanning Tree

L: Alle nicht-Baum-Kanten mit xij = 0

U: Alle nicht-Baum-Kanten mit xij = uij

7

(a) Beispiel-Netzwerk (b) Alle freien Kanten

(c) Zwei mogliche Spanning Tree Solution

Abbildung 1: Konstruktion von Spanning Tree Solution aus einer Cycle Free

Solution

Wir nennen das Tupel (T,L,U) Spanning Tree Structure. Eine Spanning Tree

Structure heißt zulassig, wenn die zugehorige Spanning Tree Solution die

Kapazitatsschranken der Kanten erfullt.

Bemerkung 5.

Wenn jede Baumkante eine freie Kante ist, so nennt man den Spanning Tree

nichtdegenerativ, andernfalls degenerativ.

Essentiell fur die Durchfuhrung des Simplex-Algorithmus ist der folgende

Satz. Dabei betrachten wir die reduzierten Kosten

cπij = cij − π(i) + π(i),

die wir in der Simplex-Methode als Optimalitatskriterium nutzen.

8

Satz 3.1 (Min-Cost-Flow Optimalitatsbedingungen).

Eine Spanning Tree Structure (T,L,U) ist ein optimale Spanning Tree Struc-

ture, wenn die Losung zulassig ist und (fur eine Wahl des Knotenpotentials

π) die reduzierten Kosten cπij folgende Bedingungen erfullen:

a) cπij = 0, ∀(i, j) ∈ T

b) cπij ≥ 0, ∀(i, j) ∈ L

c) cπij ≤ 0, ∀(i, j) ∈ U

Beweis.

Sei x∗ die zur Spanning Tree Solution (T,L,U) zugehorige Losung. Wir wissen,

dass fur ein bestimmtes π die Bedingungen erfullt sind.

Wir mussen jetzt zeigen, dass x∗ eine optimale Losung des Min-Cost-Flow

Problems ist.

Da

cπij = cij − π(i) + π(j)

gilt nach Kapitel 2

min(∑

(i,j)∈A

cijxij) ≡ min(∑

(i,j)∈A

cπijxij)

Fur ein gegebenes π gilt weiter:

min(∑

(i,j)∈A

cπijxij)

≡ min

∑

(i,j)∈T

cπijxij︸ ︷︷ ︸

=0

+∑

(i,j)∈L cπijxij +

∑(i,j)∈U

cπij︸︷︷︸≤0

xij

︸ ︷︷ ︸≤0

≡ min

(∑(i,j)∈L cπ

ijxij −∑

(i,j)∈U |cπij|xij

)(3)

9

Da fur eine beliebige Losung x

xij ≥ x∗ij ∀(i, j) ∈ L

und

xij ≤ x∗ij ∀(i, j) ∈ U

gilt, kann (3) mit der Losung x nur großer oder gleich des Zielfunktionswertes

der Losung x∗ werden.

Bemerkung 6.

Eine Spanning Tree Structure ist optimal, wenn die zugehorige Spanning Tree

Solution eine Optimallosung des Min-Cost-Flow Problems ist.

4 Beschreibung einer Spanning Tree Structure

Damit der Simplex-Algorithmus effektiv arbeiten kann, muss der Spanning

Tree geeignet im Computer dargestellt werden. Wir stellen uns den Spanning

Tree wie folgt vor:

Von einer Wurzel (root) hangt der Baum nach unten. Um diese Struktur

darstellen zu konnen, brauchen wir drei Indizes:

Definition 4.1.

• Der Predecessor Index pred(i) bezeichnet den Knoten j, der auf dem

eindeutigen Pfad von i zur Wurzel liegt, wenn die Kante (i,j) existiert.

D.h. pred(i)=j ist der direkte Vorganger von i auf dem Weg von i zur

Wurzel.

• Der Depth Index depth(i) bezeichnet die Anzahl der Kanten des ein-

deutigen Pfades von i zur Wurzel, d.h. die Tiefe des Knotens in dem

hangenden Baum, wobei die Wurzel Tiefe 0 hat.

10

i 1 2 3 4 5 6 7 8 9 10 11

pred(i) 0 1 1 2 3 3 4 4 6 8 8

depth(i) 0 1 1 2 2 2 3 3 3 4 4

thread(i) 2 4 6 7 3 9 8 10 1 11 5

Abbildung 2: Beispiel eines Netzwerks mit dazugehorigen Baumindizes

• Der Thread Index thread(i) bezeichnet den direkten Nachfolger j des

Knotens i bei der vollstandigen Traversierung des Baumes. Die Thread

Indizes definieren somit einen Weg von der Wurzel uber alle Knoten

zuruck zur Wurzel. Diese Thread Indizes sind nicht eindeutig bestimmt.

Je nach Anwendung kann man sie z.B. durch einen Preorder Traversal

erreichen.

Beispiel 4.1.

Knoten 1 ist die Wurzel.

Die gestrichelten Kanten in Abb. 2 entsprechen dem Traversierungspfad des

Netzwerks.

11

5 Knotenpotentiale berechnen

Um die im vorigen Kapitel erwahnten reduzierten Kosten ermitteln zu konnen,

mussen vorher die Potentiale aller Knoten berechnet werden. Dafur konnen

wir das Knotenpotential des Wurzelknotens beliebig setzen (hier gleich 0)

und konnen so alle anderen Potentiale berechnen.

Lemma 5.1.

Das Knotenpotential des Wurzelknotens kann π(1) = 0 gesetzt werden, ohne

dass diese Anderung Auswirkung auf die reduzierten Kosten aller Kanten

hat.

Beweis.

Addition einer Konstanten k bewirkt keine Anderung der reduzierten Kosten,

da

cπij = cij − π(i) + π(j) = cij − [π(i) + k] + [π(j) + k].

Wir nutzen jetzt die Eigenschaft aus, dass gilt:

cπij = cij − π(i) + π(j) = 0 ∀(i, j) ∈ T (4)

Somit konnen wir, wenn ein Knotenpotential der Gleichung 4 bekannt ist,

das Potential des anderen Knotens berechnen. Dabei starten wir mit dem

Wurzelknoten i = 1, da nach Lemma 5.1 π(1) = π(i) = 0 bekannt ist und

berechnen sukzessive anhand der Thread Indizes und des folgenden Algorith-

mus alle Knotenpotentiale.

Algorithmus 1.

12

procedure compute-potentials;

begin

π(1) := 0;

j := thread(1);

while j 6= 1 do

begin

i := pred(j);

if (i, j) ∈ N then π(j) := π(i)− cij;

if (j, i) ∈ N then π(j) := π(i) + cij;

j := thread(j);

end;

end;

Laufzeitanalyse:

Die Prozedur braucht O(1) Zeit fur einen Iterationsdurchlauf, der n− 1-mal

durchgefuhrt wird. Somit hat die Prozedur eine Gesamtlaufzeit von O(n).

Beispiel 5.1.

Wir verwenden den zweiten Spanning Tree aus Beispiel 3.1 c):

π(1) = 0

pred(2) = 1 ⇒ π(2) = π(1)− c12 = −5

pred(3) = 1 ⇒ π(3) = π(1)− c13 = −3

pred(4) = 2 ⇒ π(4) = π(2)− c24 = −5− 2 = −7

An diesem Beispiel kann man erkennen, dass die Knotenpotentiale nichts

anderes als die negativen Distanzwerte vom Wurzelknoten aus darstellen.

13

6 Initialer Spannbaum

Damit der Simplex Algorithmus auf jedes beliebige Netzwerk N angewendet

werden kann, muss zunachst ein initialer Spannbaum mit gultigem Fluss

aus N konstruiert werden. Der initiale Spannbaum entspricht einer gultigen

Startlosung. Um eine solche Startlosung zu erreichen, fugt man einen neuen,

kunstlichen Knoten r ein und n (Anzahl der Knoten in N) neue, kunstliche

Kanten, die wie folgt konstruiert werden:

Wir untersuchen jeden Knoten j aus N . Wenn b(j) > 0, fugen wir eine Kante

(j, r) ein, mit einem Fluss von b(j). Ist b(j) ≤ 0, so fugen wir eine Kante (r, j)

mit Fluss von −b(j) ein. Alle Kanten haben unendlich grosse Kapazitat,

ebenso setzt man ihre Kosten sehr hoch, damit es auf jeden Fall teurer ist,

wenn Fluss uber kunstliche Kanten fließt. Die Kosten der kunstlichen Kanten

konnen sich z.B. wie folgt ergeben:

crk = ckr =∑

(i,j)∈N

cij + 1 ∀k ∈ N.

Alle anderen Kanten haben zu diesem Zeitpunkt noch keinen Fluss.

Wir erhalten so einen Spanning Tree aus dem Orginalnetzwerk mit Wurzel r

und ausschließlich kunstlichen Kanten zu allen Knoten aus N mit zulassigem

14

Fluss, wobei die Flusseinheiten zu diesem Zeitpunkt nur von den Senken uber

den Knoten r zu den Quellen fließt.

Beispiel 6.1.

Wir nutzen das Netzwerk N aus Bsp. 3.1.

Abb. 3(a) zeigt das ursprungliche Netzwerk, in Abb. 3(b) sieht man den

konstruierten Spanning Tree mit kunstlichem Wurzelknoten und kunstlichen

Kanten. In diesem Beispiel entspricht Knoten 1 der Quelle s, Knoten 2 der

Senke t und der neue, kunstliche Knoten r ist Knoten 5.

(a) Beispiel-Netzwerk (b) Konstruierter Spanning Tree

Abbildung 3: Initialer Spannbaum

Existiert eine Losung fur das gegebene Problem, dann berechnet der Sim-

plex Algorithmus einen Fluss x, bei dem nur Kanten des Orginalnetzwerks

positive Flusswerte haben. Daher setzt man die Kosten der kunstlichen Kan-

ten so hoch, dass es auf jeden Fall gunstiger ist, Fluss uber die Kanten des

gegebenen Netzwerks fließen zu lassen, wenn das Problem losbar ist.

15

7 Simplex-Algorithmus

Sei (T, L, U) eine mogliche Spanning Tree Struktur des Min-Cost-Flow-Problems

und π die entsprechenden Knotenpotentiale. Nach Satz 3.1 ist diese Losung

optimal, wenn gilt:

∀(i, j) ∈ L : cπij ≥ 0,

∀(i, j) ∈ U : cπij ≤ 0.

Sollten die Bedingungen nicht erfullt sein, so muss eine Kante durch eine an-

dere ersetzt werden, damit der Zielfunktionswert in Richtung des optimalen

Werts verbessert wird. Dadurch andern sich bestimmte Knotenpotentiale, so-

wie reduzierte Kosten einzelner Kanten. Diese mussen angepasst werden und

die Optimalitatsbedingungen erneut uberpruft werden. Im einzelnen lautet

der Simplex -Algorithmus wie folgt:

Algorithmus 2.

algorithm network simplex

begin

konstruiere initialen Spannbaum;

solange die Optimalitatsbedingungen nicht erfullt sind tue

wahle eine einzufugende Kante, die die Optimalitatsbedingung verletzt;

fuge diese Kante ein und bestimme die wegfallende Kante;

baue den Spannbaum neu auf und passe x und π an;

end;

end;

Bemerkung 7.

Sollte noch Fluss auf den eingefugten kunstlichen Kanten fließen, obwohl alle

16

Optimalitatskriterien erfullt sind, so gibt es keine zulassige Losung fur dieses

Netzwerk.

7.1 Entering Arc

Die einzufugende Kante muss aus der Menge der Kanten stammen, die die

obigen Optimalitatsbedingungen nicht erfullen (sie kann also nur aus L oder

U stammen). Fur die Wahl dieser Kante gibt es verschiedene Pivotregeln,

drei werden an dieser Stelle vorgestellt.

7.1.1 Dantzig’s Pivot Regel

Die Regel wahlt in jeder Iteration die Kante mit der hochsten Verletzung. (Als

Verletzung einer Kante (i, j) bezeichnen wir |cπij|). Der Hintergrund zu dieser

Regel ist die großere Verringerung des Zielfunktionswertes bei einer hohen

Verletzung, wenn alle Kandidaten eine ahnlich hohe Flussanderung bewirken.

Der Algorithmus muss also alle Kanten aus L und U nach der maximalen

Verletzung durchsuchen. Da dies jedoch bei jeder Iteration gemacht werden

muss, ist diese Regel auf Grund der hohen Laufzeit fur die Praxis nicht

geeignet.

7.1.2 First Eligable Arc Rule

Bei dieser Regel werden alle Kanten durchsucht und die erste geeignete Kan-

te ausgewahlt. Eine bekannte Variante dieser Regel arbeitet nach der ’wra-

paround fashion’. Dabei wird die letzte gewahlte Kante als Startpunkt fur die

neue Suche gesetzt. Durch diese Tatsache wird schnell die neue, einzufugende

Kante gefunden. Diese hat aber in den meisten Fallen nur eine geringe Ver-

letzung und somit eine kleine Reduzierung des Zielfunktionswertes. Durch

17

die vielen daraus resultierenden Iterationen ist auch diese Regel nicht fur die

Praxis geeignet.

7.1.3 Kandidaten-Liste Pivot-Regel

Dieser Algorithmus ist eine Zwei-Phasen-Prozedur, bestehend aus einer Haup-

titeration und einer Nebeniteration. In der Hauptiteration werden ausgehend

von der Wurzel alle geeigneten Kanten in eine Kandidatenliste eingefugt. Das

wiederholt man fur Knoten 2, 3, ..., bis entweder alle geeigneten Kanten ein-

gefugt sind oder der fur die Liste allokierte Speicherplatz belegt ist. Die

nachste Hauptiteration beginnt an dem Knoten, an dem die vorhergehende

Iteration endete. In der Nebeniteration wird die Liste nach der Kante mit

der maximalen Verletzung durchsucht. Gleichzeitig werden alle nicht mehr

geeigneten Kanten wieder aus der Liste entfernt. Das wiederholt sich solange,

bis die Liste leer ist oder die angegebene maximale Anzahl der Iterations-

durchlaufe erreicht ist. Anschließend wird eine neue Liste in der Hauptitera-

tion aufgebaut. Man kann erkennen, dass diese Regel viele Moglichkeiten zur

Optimierung bietet und sowohl die Dantzig’s Pivot Regel als auch die First

Eligable Arc Rule Spezialfalle der Kandidaten-Liste Pivot-Regel sind(Große

der Kandidatenliste = 1 ⇒ First Eligable Arc Rule; Große der Kandidaten-

liste = ∞ ⇒ Dantzig‘s Pivot Regel).

In der Praxis hat sich diese Mischung aus den beiden anderen Pivotregeln

auf Grund ihrer schnelleren Laufzeit bewahrt.

7.2 Leaving Arc

Nachdem eine Kante eingefugt wurde, muss auch wieder eine entfernt werden,

damit die Spanning Tree Struktur wieder aufgebaut werden kann.

Sei (k, l) die eingefugte Kante. (k, l) erzeugt genau einen Kreis W (Pivot-

18

Kreis), dessen Orientierung der Richtung von (k, l) entspricht, wenn (k, l) ∈ L

und entgegengesetzt, wenn (k, l) ∈ U . So wird der Kreis W partitioniert in W

und W . Dabei enthalt W alle Vorwartskanten (entsprechend der Orientierung

des Pivot-Kreises), W alle Ruckwartskanten. Wir erhohen den Fluss (entlang

W ) jetzt um

δ = min (δij | (i, j) ∈ W ) ,

wobei

δij =

uij − xij, wenn (i, j) ∈ W

xij, wenn (i, j) ∈ W.

So erreicht mindestens eine Kante ihre obere bzw. untere Grenze. Diese Kante

(i, j) bzw. eine dieser Kanten (kann beliebig gewahlt werden) heißt blockie-

rende Kante. Diese wird aus T entfernt und in L eingefugt (wenn xij = 0)

oder in U eingefugt (wenn xij = uij).

Bemerkung 8.

Ein positiver erhohender Fluss entlang W erhoht den Fluss auf Vorwarts-

kanten, verringert ihn auf Ruckwartskanten.

Definition 7.1.

Eine Pivot-Operation heißt

• nichtdegenerative Iteration, wenn δ > 0,

• degenerative Iteration, wenn δ = 0.

Bemerkung 9.

Wenn es mehr als eine Kante gibt, die durch den erhohenden Fluss an ihre

Grenzen stoßen, so wird der nachste Spanning Tree degenerativ sein.

19

Die Schwierigkeit bei diesem Verfahren liegt in der Erkennung des Krei-

ses. Effizient losen kann man dieses Problem, wenn man den Spanning Tree

vor Einfugen der neuen Kante (k, l) betrachtet. Jetzt werden in einer Schleife

die Vorganger von k und l solange aufgerufen, bis der gemeinsame Vorganger

gefunden ist. Das konkrete Vorgehen beschreibt der nachfolgende Algorith-

mus:

Algorithmus 3.

procedure identify-cycle;

begin

i:=k und j:=l;

while i 6= j do

begin

if depth(i) > depth(j) then i:=pred(i);

else

if depth(j) > depth(i) then j:=pred(j);

else i:=pred(i) und j:=pred(j);

end;

end;

7.3 Spannbaum updaten

Wenn die wegfallende Kante (p, q) gleich der eingefugten Kante (k, l) ist

(δ = δkl = ukl), andert sich T nicht, lediglich die Kante (k, l) wechselt von L

nach U oder umgekehrt. Ist (p, q) ungleich (k, l), so mussen einige Verande-

rungen vorgenommen werden. Als erstes wird (p, q) zu L hinzugefugt (wenn

xpq = 0), bzw. zu U (wenn xpq = upq) hinzugefugt. Betrachten wir jetzt den

Spannbaum ohne die Kanten (p, q) und (k, l), so erhalten wir einen Teilbaum

20

T1, der die Wurzel und entweder k oder l enthalt. Der zweite Teilbaum T2

hangt dagegen entweder am Knoten p oder q. Der entsprechend andere Kno-

ten befindet sich in T1. Damit auch im neuen Spannbaum die Bedingung

cπij = 0 gilt, mussen die Knotenpotentiale in T1 oder in T2 geandert werden:

Wenn k ∈ T1, dann mussen alle Knotenpotentiale um cπkl verringert werden,

wenn k ∈ T2, dann mussen alle Knotenpotentiale um cπkl erhoht werden. Eine

genaue Beschreibung des Spannbaum-Updates liefert der folgende Algorith-

mus.

Algorithmus 4.

procedure update-potentials;

begin

if q ∈ T2 then y := q else y := p;

if k ∈ T1 then change := −cπkl else change := cπ

kl;

π(y) := π(y) + change;

z:=thread(y);

while depth(z) > depth(y) do

begin

π(z) := π(z) + change;

z:=thread(z);

end;

end;

7.4 Beispiel

Wir nutzen erneut das bekannte Beispiel. Diesmal ist es das vollstandige

Netzwerk mit Kantenkosten, Kantenbeschrankungen und Supply/Demand.

21

Als erstes wird der kunstliche Knoten (5) eingefugt, inkl. aller kunstlichen

Kanten. Wir lassen 4 Einheiten Fluss uber die Kanten (1,5) und (5,4) fließen

und berechnen die Knotenpotentiale, wobei wir die Kosten der kunstlichen

Kanten mit∑

(i,j)∈N cij +1 = 16 Einheiten veranschlagen. Mit dieser Berech-

nung der Kantenkosten ist bei allen Min-Cost-Flow Problemen sichergestellt,

dass es auf jeden Fall teurer ist, Fluss uber die kunstlichen Kanten fließen zu

lassen.

Somit haben wir den initialen Spannbaum (durchgezogene Kanten). Da die

Kante (1,3) die hochsten reduzierten Kosten besitzt (cπ13 = −29), wahlen wir

diese als einzufugende Kante(grun). Weil δ jedoch 0 ist, kann der Fluss nicht

erhoht werden. Wir wahlen daraufhin (5,3) als blockierende Kante(rot), und

entfernen diese aus dem Spannbaum, und fugen sie in die Menge L ein.

22

Das Knotenpotential von Knoten 3(rot) inkl. der reduzierten Kosten aller

inzidenten Kanten muss jetzt erneuert werden, woraufhin Kante (3,2) mit

cπ32 = −28 als neue Baumkante gewahlt wird. Wiederum kann der Fluss

nicht erhoht werden, so wird Kante (5,2) nach L verschoben.

Nach einigen weiteren Schritten erhalten wir das linke unten stehende Bild.

23

Bis hierhin sind auch Kanten (1,3) und (2,4) aus dem Baum nach U ver-

schoben worden. Beide Kanten sind mit maximalem Fluss (x13 = x24 = 3)

entfernt worden.

Ein Update mussen hier die Knoten 2 und 3 erhalten. Kante (1,2) wird neu

eingefugt und der Fluss kann um eine Einheit erhoht werden. Kante (5,4)

muss daraufhin entfernt werden.

Nach einem Update der Knoten 2,3 und 4 sind alle Optimalitatsbedingun-

gen erfullt. Da Optimalitatsbedingungen auf allen Kanten erfullt ist und kein

Fluss auf kunstlichen Kanten fließt, ist die Losung optimal mit Flusskosten

von 26 Einheiten.

24

8 Strongly Feasible Spanning Tree

Es kann passieren, dass die Simplex-Methode nicht terminiert. Damit der

Algorithmus nicht in eine Endlosschleife gerat, wird hier das Konzept des

Strongly Feasible Spanning Tree mit einer Leaving Arc Rule vorgestellt, die

die Finitheit des Algorithmus garantiert.

Stellen wir uns nochmal den Spanning Tree (T, L, U) als hangenden Baum

vor, dann gibt es Kanten, die nach oben zeigen (upward pointing) oder die

nach unten zeigen (downward pointing).

Definition 8.1.

Ein Spannbaum T ist strongly feasible, wenn jede Baumkante ohne Fluss

nach oben zeigt und jede Baumkante deren Fluss gleich ihrer Kapazitat ist

nach unten zeigt.

Definition 8.2.

25

Ein Spannbaum ist strongly feasible, wenn es moglich ist, einen Fluss von

einem beliebigem Knoten zur Wurzel zu schicken, ohne Kapazitatsgrenzen zu

verletzen.

Bemerkung 10.

Man kann leicht zeigen, dass diese beiden Definitionen aquivalent sind.

Leider erhalten wir durch Konstruktion des initialen Spannbaums keinen

Strongly Feasible Spanning Tree. Dies kann jedoch erreicht werden, wenn die

Definition fur eine Startlosung wie folgt geandert wird:

Wir untersuchen jeden Knoten j aus N(Orginalnetzwerk). Wenn b(j) ≥

0(statt b(j > 0)) , fugen wir eine Kante (j, r) (mit r als neuem kunstli-

chem Knoten) ein, mit einem Fluss von b(j). Ist b(j) < 0(statt b(j) ≤ 0), so

fugen wir eine Kante (r, j) mit Fluss von −b(j) ein.

Jetzt ist leicht zu sehen, dass es moglich ist von jedem Knoten Fluss zur

Wurzel r zu schicken.

Da wir durch unsere Konstruktion des initialen Spannbaums immer einen

nicht-degenerativen Baum erhalten, haben wir auch automatisch zu Beginn

einen Strongly Feasible Spanning Tree. Jetzt gilt es, diese Eigenschaft im

Spanning Tree beizubehalten. Der Spannbaum kann im nachsten Schritt nur

degenerieren, wenn es mehr als eine blockierende Kante gibt, d.h. ist die

blockierende Kante eindeutig, so erhalt man auch im nachsten Schritt einen

Strongly Feasible Spanning Tree. Damit dies auch im anderen Fall passiert,

gibt es folgende Regel.

8.1 Leaving Arc Rule

Aus dem Spannbaum soll die letzte blockierende Kante, die nach Traversie-

rung (entlang der Orientierung der eingefugten Kante) des entstanden Krei-

26

ses entfernt werden. Dabei wird am Knoten w, der hochste Punkt (apex) des

Kreises im hangenden Baum, gestartet. Durch diese Regel wird der Kreis W

in W1 und W2 geteilt. W1 ist der Teil von W vom Knoten w bis zur Kante

(p, q) (entfernte Kante), W2 = W − W1 − {(p, q)}. Beide Teile haben die

gleiche Orientierung wie der Kreis W .

Satz 8.1.

a) Jeder Knoten im Segment W2 kann einen positiven Fluss zur Wurzel

schicken.

b) Jeder Knoten im Segment W1 kann einen positiven Fluss zur Wurzel

schicken.

Beweis.

a)

Da (p, q) die letzte blockierende Kante war, kann in W2 keine blockierende

Kante sein. Deshalb ist es auf jeden Fall moglich, dass jeder Knoten aus W2

noch Fluss zur Wurzel schicken kann.

b)

Fall 1:

Wenn die vorhergende Pivotoperation den Fluss entlang W1 erhoht hat und

damit eine nichtdegenerative Pivotoperation war, dann kann im nachsten

Schritt der Fluss auch wieder in die andere Richtung (zur Wurzel hin) ge-

schickt werden.

Fall 2:

Wenn in der vergangenen Pivotoperation keine Flusserhohung durchgefuhrt

wurde, muss W1 zwischen w und k liegen, da nach den Eigenschaft des Stron-

gly Feasible Trees Fluss von l zur Wurzel geschickt werden kann. Und da der

27

Fluss ja auch nicht im Segment W1 erhoht wurde, kann auch positiver Fluss

von jedem Knoten in W1 zur Wurzel geschickt werden.

Die Finitheit resultiert jetzt daraus, dass mit jeder Flusserhohung in den

Pivotoperationen der Zielfunktionswert vermindert wird. Das kann aber nur

endlich oft passieren, deswegen garantiert diese Methode die Finitheit des

Algorithmus.

Beispiel 8.1.

Abbildung 4: Strongly Feasible Spanning Tree

28

Literatur

[1] Ravindra K. Ahuja, James B. Orlin, Thomas L. Magnanti,

Network Flows: Theory, Algorithms & Applications,

Prentice Hall, 1993.

29