LP-Probleme mit spezieller Struktur
Es gibt eine Reihe von linearen Problemen, die eine spezielle Struktur aufweisen, durch die die Problemlösung
wesentlich schneller erfolgen kann als
bei Anwendung des Simplex-Algorithmus.
Gelingt es, ein lineares Problem in die Struktur eines Netzwerkflußproblems zu überführen,
dann ist es z.T. möglich, die optimale Lösung u.U. 100mal
so schnell oder noch schneller zu ermitteln als bei Anwendung des Simplex-Algorithmus.
Das allgemeine Netzwerkflußproblem
Ein Netzwerk ist eine Menge von Knoten und Kanten, die die Knoten verbinden. Ein Netzwerkflußproblem
besteht i. a. darin, die Transportmengen
(Produkt- oder Materialflüsse) von einigen Orten zu anderen Orten zu bestimmen, wobei eine bestimmte
Zielsetzung verfolgt wird und verschiedene
Bedingungen einzuhalten sind.
Symbole:
| i |
Knotenindex |
| j |
Knotenindex |
| x |
Transportmenge |
| b |
Nettobedarf eines Ortes (Knotens) |
| l |
Mindesttransportmenge über eine Strecke |
| u |
Maximale Transportmenge über eine Strecke |
Das klassische Transportproblem
Das klassische Transportproblem ist ein Netzwerkflußproblem, in dem es keine Umladeknoten gibt
und in dem die Kanten keine
Kapazitätsbeschränkungen haben. Die Summe der Angebotsmengen aller Quellen ist
gleich der Summe der Bedarfsmengen aller Senken.
Nehmen wir m Quellen und n Senken an, dann können wir schreiben:
Siehe hierzu: Günther, H.-O. und H. Tempelmeier, Produktion und Logistik, 9.Aufl., Berlin(Springer) 2012
Das lineare Zuordnungsproblem
Dies ist ein Spezialfall des klassischen Transportproblems, bei dem alle Angebotsmengen und alle Nachfragemengen
genau gleich 1 sind. Das Modell
lautet:
Das Kürzeste-Wege-Problem
Dies ist ein Spezialfall des allgemeinen Netzwerkflußproblems (Minimalkostenflußproblems),
bei dem das Nettoangebot an jedem Knoten entweder
1, 0 oder -1 ist. Außerdem haben die Pfeile keine Kapazitätsbeschränkung. Dieses Problem
ist regelmäßig in allen Routing-Programme, die man im
Internet aufrufen kann und auch in allen Navigationssystemen zu lösen.
