0-1 QAP: Lösungsansätze und exakte Methoden
PAYBACK Punkte
0 °P sammeln!
Diplomarbeit aus dem Jahr 1998 im Fachbereich Mathematik - Angewandte Mathematik, Note: sehr gut, Technische Universität Carolo-Wilhelmina zu Braunschweig (Institut für Angewandte Mathematik Abteilung Mathematische Optimierung), 27 Quellen im Literaturverzeichnis, Sprache: Deutsch, Abstract: In dieser Arbeit beschäftigen wir uns mit dem quadratischen Zuordnungsproblem (Quadratic Assignment Problem QAP). Das QAP ist ein Problem der kombinatorischen Optimierung und zählt dort mittlerweile zu den klassischen Problemstellungen. Eine der typischen Problemstellungen, die mit Hilfe des QAPs model...
Diplomarbeit aus dem Jahr 1998 im Fachbereich Mathematik - Angewandte Mathematik, Note: sehr gut, Technische Universität Carolo-Wilhelmina zu Braunschweig (Institut für Angewandte Mathematik Abteilung Mathematische Optimierung), 27 Quellen im Literaturverzeichnis, Sprache: Deutsch, Abstract: In dieser Arbeit beschäftigen wir uns mit dem quadratischen Zuordnungsproblem (Quadratic Assignment Problem QAP). Das QAP ist ein Problem der kombinatorischen Optimierung und zählt dort mittlerweile zu den klassischen Problemstellungen. Eine der typischen Problemstellungen, die mit Hilfe des QAPs modelliert werden können, sind plänare Zuordnungsprobleme. Bei dieser Klasse von Problemen betrachtet man z.B. ein gegebenes Streckennetz der Bahn mit verschiedenen Verkehrsknoten, an denen sich verschiedene Streckenabschnitte kreuzen. An diesen Verkehrsknoten sollen verschiedene Fabriken errichtet werden, die untereinander in Geschäftsverbindung stehen und sich deswegen gegenseitig mit verschiedenen
über das Streckennetz beliefern. In einer Planungsphase zur Anordnung der Fabriken auf jeweils verschiedenen Verkehrsknoten ist bereits bekannt, wie viele Güter von einer Fabrik zu einer anderen transportiert werden. Außerdem ist bekannt, wie lang die Strecken zwischen jeweils zwei Knoten des Streckennetzes sind. An jedem Verkehrsknoten soll genau eine Fabrik errichtet werden. Das Ziel der Planung soll die Minimierung der gesamten zurückzulegenden Strecke der Güter sein. Das heißt, daß insgesamt möglichst viele Güter zwischen den verschiedenen Fabriken auf möglichst kurzen Wegen des Streckennetzes transportiert werden sollen.
Das quadratische Zuordnungsproblem wurde erstmals 1957 in ähnlicher Weise von Koopmans und Beckmann formuliert, um plänare Zuordnungsprobleme der beschriebenen Art zu losen. In dieser ersten Formulierung ging es um die Zuordnung einer Menge von Wirtschaftsresourcen auf eine Menge von Standorten. Hierbei sind dann die
über das Streckennetz beliefern. In einer Planungsphase zur Anordnung der Fabriken auf jeweils verschiedenen Verkehrsknoten ist bereits bekannt, wie viele Güter von einer Fabrik zu einer anderen transportiert werden. Außerdem ist bekannt, wie lang die Strecken zwischen jeweils zwei Knoten des Streckennetzes sind. An jedem Verkehrsknoten soll genau eine Fabrik errichtet werden. Das Ziel der Planung soll die Minimierung der gesamten zurückzulegenden Strecke der Güter sein. Das heißt, daß insgesamt möglichst viele Güter zwischen den verschiedenen Fabriken auf möglichst kurzen Wegen des Streckennetzes transportiert werden sollen.
Das quadratische Zuordnungsproblem wurde erstmals 1957 in ähnlicher Weise von Koopmans und Beckmann formuliert, um plänare Zuordnungsprobleme der beschriebenen Art zu losen. In dieser ersten Formulierung ging es um die Zuordnung einer Menge von Wirtschaftsresourcen auf eine Menge von Standorten. Hierbei sind dann die
Andere Kunden interessierten sich für
