R2 Wegeprobleme
Kürzeste Wege und Lineare Optimierung
Nachdem mit dem Dijkstra-Algorithmus ein sehr leistungsfähiger Algorithmus für kürzeste Wege Probleme vorgestellt wurde, wird nun noch gezeigt, wie mithilfe Linearer Optimierung Kürzeste-Wege-Probleme gelöst werden können. Vorab sei bemerkt, dass was die Effizienz anbelangt, der Dijkstra-Algorithmus deutlich überlegen ist. Dass trotzdem in diesem Abschnitt auf die Lösungsmöglichkeit über Lineare Optimierung eingegangen wird, liegt daran, dass sich zeigen lässt, dass die Lineare Optimierung ein sehr universelles Werkzeug ist und sich Kürzeste-Wege-Probleme als Lineares Modell formulieren lassen.
Formulierung von Kürzeste-Wege-Problemen als Lineares Modell
Das Kürzeste-Wege-Problem lässt sich auch als System von linearen Gleichungen und Ungleichungen formulieren. Auch hier hilft es, das Bild des Graphen vor Augen zu haben, um die Formulierung nachzuvollziehen. Die Formulierung wird nachfolgend für einen gerichteten Graphen entwickelt. Sie kann bei gerichteten Graphen angewendet werden. Bei ungerichteten Graphen ist es zunächst notwendig, die Kanten in zwei entgegengesetzte gerichtete Kanten umzuwandeln.
Für das vorstehende Beispiel soll das Kürzeste-Wege-Problem von Knoten 1 nach 6 als Lineares Optimierungsproblem formuliert werden.
Jede Kante wird als Variable definiert, die Kante zwischen Knoten 1 und 2 wird durch die Variable x12 repräsentiert.
Es wird folgende Codierung verwendet:
xij=0 wenn die Kante von i nach j nicht auf dem benutzten Weg liegt
xij=1 wenn die Kante von i nach j auf dem benutzten Weg liegt.
Es handelt sich um eine Binärvariable, die nur die Werte 0 oder 1 annehmen darf. Aber dazu später mehr.
Die Zielfunktion lautet wie folgt:
min z= 3·x12+ 6 ·x13+ 2·x23+ 7·x24+2·x32+ 5·x35+ 3·x45+6 ·x46+ 4·x56
Für jede Kante wird die Länge multipliziert mit der Variablen. Wir eine Kante benutzt, hat sie vorstehender Codierung zu Folge den Wert 1 und die Länge der Kante geht in die Summe ein, hat die Variable den Wert 0 entfällt das Glied und die Länge der Kante geht nicht in die Summe ein.
Da der Weg möglichst kurz sein soll, handelt es sich um ein Minimierungsproblem.
Nun geht es darum, über die Nebenbedingungen zu erzwingen, dass die optimale Lösung auch wirklich einen Weg von 1 nach 6 enthält und nicht einfach alle Variablen auf null setzt. Dafür werden sogenannte Flusserhaltungsgleichungen benutzt.
Die Idee ist, sicherzustellen, dass am Anfangsknoten der Weg beginnt, dass an den Zwischenknoten der Weg durchführt und am Zielknoten der Weg endet.
Für den Anfangsknoten:
x12+ x13=1
Ausgehende Knoten werden mit positiven Vorzeichen gezählt. Damit die Bedingung erfüllt ist, muss entweder x12 oder x13 benutzt werden.
Für alle Zwischenknoten:
Knoten 2: -x12- x32 + x24+ x23=0
Knoten 3: -x13- x23 + x23+ x35=0
Knoten 4: -x24 + x45+ x46=0
Knoten 5: -x45 + x35+ x56=0
Die eingehenden Kanten werden mit negativen Vorzeichen angesetzt, die ausgehenden mit positiven. In einem Zwischenknoten führt eine benutzte Kante hinein und auch eine benutzte Kante heraus oder es führt weder eine Kante hinein noch heraus. Das heißt die Summe in obiger Gleichung muss null sein. Um einem Einwand vorzubeugen: Die einzelnen Gleichungen wären auch erfüllt, wenn z.B. zwei benutzte Kanten hinein- und wieder hinausführen. Das wird aber nicht passieren, da die Zielfunktion die Weglänge minimiert.
Für den Zielknoten:
-x46- x56=-1
In den Zielknoten führt eine benutzte Kante hinein, deswegen ist die Summe 1. Die Koeffizienten des obigen Linearen Optimierungsproblem in Matrixschreibweise:
Es zeigt sich, die Koeffizientenmatrix ist nichts anderes als die Inzidenzmatrix des Graphen.
Weiterhin sind die Nicht-Negativitätsbedingungen zu beachten. Aus der Variablendefinition geht hervor, dass auch noch Ganzzahligkeitsbedingungen zu erfüllen sind. Bei diesem besonderen Problem ist es jedoch nicht erforderlich die Einhaltung gesondert zu überwachen, die Ganzzahligkeit ergibt sich automatisch. Man spricht von natürlicher Ganzzahligkeit. Hinweis ohne weitere Erklärung: Die Koeffizientenmatrix ist unimodular.
