0-1 Qap : Loesungsansatze und exakte Methoden

Diplomarbeit aus dem Jahr 1998 im Fachbereich Mathematik - Angewandte Mathematik, Note: sehr gut, Technische Universitt Carolo-Wilhelmina zu Braunschweig (Institut fr Angewandte Mathematik Abteilung Mathematische Optimierung), 27 Quellen im Literaturverzeichnis, Sprache: Deutsch, Anmerkungen: Auszug aus der Einfhrung: In dieser Arbeit beschftigen wir uns mit dem quadratischen Zuordnungsproblem Quadratic Assignment Problem (QAP). Das QAP ist ein Problem der kombinatorischen Optimierung und zhlt dort mittlerweile zu den klassischen Problemstellungen. Eine der typischen Problemstellungen, die mit Hilfe des QAPs modelliert werden knnen, sind planare Zuordnungsprobleme. Bei dieser Klasse von Problemen betrachtet man z.B. ein gegebenes Streckennetz der Bahn mit verschiedenen [...] , Abstract: In dieser Arbeit beschftigen wir uns mit dem quadratischen Zuordnungsproblem (Quadratic Assignment Problem QAP). Das QAP ist ein Problem der kombinatorischen Optimierung und zhlt dort mittlerweile zu den klassischen Problemstellungen. Eine der typischen Problemstellungen, die mit Hilfe des QAPs modelliert werden knnen, sind plnare 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 Geschftsverbindung 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 Gter von einer Fabrik zu einer anderen transportiert werden. Auerdem 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 zurckzulegenden Strecke der Gter sein. Das heit, da