R3 Flussprobleme

Flussprobleme beschäftigen sich mit der Frage, wie groß der maximale Fluss von einer Quelle zu einer Senke durch ein Netzwerk ist.

Der Name Fluss rührt aus dem Bild eines Pipelinesystems, durch das eine Flüssigkeit, z.B. Wasser, fließt. Über jede Kante kann pro Zeiteinheit eine bestimmte Menge Wasser fließen. An der „Quelle“ kommt Wasser in das System, das über Leitungen mit einer bestimmten Kapazität zu einer „Senke“ transportiert wird. Die Knoten sind in dieser Analogie Verteilstationen, an denen das Wasser auf die weiterführenden Leitungen verteilt wird.

Quelle
Senke

Begrifflichkeiten und Problemformulierung

Bei Flussproblemen wird in der Regel mit gerichteten Graphen gearbeitet. Maximaler Fluss durch das Netzwerk:

Größtmöglicher Fluss, der unter Berücksichtigung aller Kantenkapazitäten durch das Netzwerk von der Quelle zum Ziel fließen kann.

Optimierungsziel ist es, den größtmöglichen Fluss zu ermitteln:

max_f

Kantenkapazität k_ij:

Maximaler Fluss, der über eine bestimmte Kante ij fließen kann. Im Laufe der Lösung des Problems verändert sich die Kantenkapazität nicht.

Fluss über eine Kante x_ij

Fluss der über eine Kante fließt. Der Fluss über eine Kante muss kleiner-gleich der Kapazität dieser Kante sein.

Im Verlauf der Lösungsfindung werden die xij verändert mit dem Ziel f zu erhöhen.

Kantenkapazitaet

Negative Flüsse sind in dem Modell nicht definiert, von daher gilt auch

nnb

Quelle A:

Knoten, im Folgenden mit A bezeichnet, an dem der Fluss f entsteht.

D.h. die Summe aller Abflüsse zu benachbarten Knoten Aj ist größer oder gleich der Summe der Zuflüsse.

Häufig wird es keine Kante die einen Zufluss zur Quelle erlaubt geben, dann vereinfacht sich die vorstehende Formel wie folgt:

gleichung_quelle

Senke Z:

Knoten, im Folgenden mit Z bezeichnet, an dem der Fluss versiegt.

gleichung_senke

Das heißt die Summe der Abflüsse ist kleiner als die Summe der Zuflüsse. Auch hier lässt sich der Term vereinfachen

Knoten außer Quelle und Senke:

In allen übrigen Knoten ist die Summe der Zuflüsse gleich der Summe der Abflüsse aus dem jeweiligen Knoten.

Flusshaltung

Das Problem wird im übernächsten Abschnitt mit einem Graphenalgorithmus gelöst. Da es sich um ein Lineares Optimierungsproblem handelt, lässt es sich auch mit dem Simplexalgorithmus lösen. Zielfunktion und Nebenbedingungen ergeben sich aus den vorstehenden Gleichungen und der Nichtnegativtätsbedingung.

Hinweis:

In vielen Darstellungen wird der Fluss f auch als Rückfluss von der Senke zur Quelle aufgefasst und entsprechend mit x_ZA bezeichnet, wobei die Rückflusskante eine unbeschränkte Kapazität hat. In dem Netzwerk fließt somit der Fluss gedanklich immer im Kreis.