Modellierung des quadratischen Zuordnungsproblems

Inhaltsverzeichnis

1. Einführung

2. Beispiel

3. Grundmodelle des quadratischen Zuordnungsproblems
3.1. Das Koopmans-Beckmann-Modell
3.1.1. Die Annahmen des Koopmans-Beckmann-Modells
3.1.2. Mathematische Formulierung
3.2. Varianten des Grundmodells
3.2.1. Explizite Berücksichtigung der Zuordnungskosten
3.2.2. Symmetrie
3.2.3. Überzahl an Standorten
3.3 Beispiel

4. Netzwerkbasierte Ansätze
4.1. Charakteristika und Arten netzwerkbasierter Ansätze
4.2. Der „große“ netzwerkbasierte Ansatz
4.2.1. Aufbau der Linearisierung
4.2.2. Modellierung
4.2.3. Validität der Formulierung
4.2.4. Beispiel
4.3. Der „kleine“ netzwerkbasierte Ansatz
4.3.1. Aufbau der Linearisierung
4.3.2. Modellierung
4.3.3. Validität der Formulierung
4.3.4. Beispiel
4.3.5. Ergänzende Bemerkungen zur Bestimmung unterer Schranken
4.4. Beurteilung und Leistungsfähigkeit der Ansätze

5. Zusammenfassung und Ausblick

6. Literaturverzeichnis

Verzeichnis der Tabellen

Tabelle 1: Entfernungsmatrix

Tabelle 2: Transportintensitäten

Verzeichnis der Abbildungen

Abbildung 1: Grundmodell des quadratischen Zuordnungsproblems

Abbildung 2: Quadratisches Zuordnungsproblem mit Zuordnungskosten

Abbildung 3: Mathematische Formulierung des „großen“ Netzwerkes

Abbildung 4: „Großes“ Netzwerk

Abbildung 5: Mathematische Formulierung des „kleinen“ Netzwerkes

Abbildung 6: „Kleines“ Netzwerk

1. Einführung

Das Zuordnungsproblem ist ein Problem der innerbetrieblichen Standortplanung, in dem es um die (kosten-)optimale Zuordnung von Organisationseinheiten zu Standorten geht. Ein vereinfachtes Problem ist das quadratische Zuordnungsproblem mit gleicher Anzahl von Organisationseinheiten und Standorten. Aufgrund der Nichtlinearität gehört es zur Klasse np-schwerer Probleme, deren Rechenaufwand bei steigender Variablenanzahl exponentiell ansteigt. Exakte Lösungen sind nur im begrenzten Umfang möglich. Approximationen der Optimallösung umfangreicherer Probleme ergeben sich durch Eingrenzung in obere und untere Schranken. Einen Approximationsversuch durch graphentheoretische Ansätze zur Linearisierung des Problems unternehmen Ball et al. in dem dieser Arbeit zugrunde liegenden Artikel „Networked-based formulation of the quadratic assignment problem.“^[1]

Diese anwendungsorientierte Seminararbeit verdeutlicht anhand eines Beispiels die Problematik des quadratischen Zuordnungsproblems, gibt eine Übersicht über die Grundmodelle und beschäftigt sich intensiv mit der Formulierung des netzwerkbasierten Ansatzes.

2. Beispiel

Das folgende Beispiel soll zur Verdeutlichung der Zielsetzung des quadratischen Zuordnungsproblems dienen und die komplexe Formulierung der Modelle veranschaulichen.

In einem Dorf sollen eine Bäckerei, eine Mühle und ein Kornfeld aufgestellt werden. Zur Wahl stehen drei gleich große Standorte (Eins, Zwei und Drei), die jedes Gebäude aufnehmen können. Für die Errichtung der Bauwerke entstehen keine besonderen von der Lage abhängigen Kosten (z.B. für eine besondere Einebnung etc.). Tabelle 1 gibt die Entfernungen zwischen den Standorten wider.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Entfernungsmatrix^[2]

Zwischen den Einheiten werden Waren geliefert. Die Lieferwege und Mengen zeigt die folgende Tabelle 2.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Transportintensitäten^[3]

Gesucht ist die optimale Positionierung der Mühle, des Getreidefeldes und des Bäckers in dem Sinne, dass die Transportkosten pro Periode minimal sind.

3. Grundmodelle des quadratischen Zuordnungsproblems

3.1. Das Koopmans-Beckmann-Modell

3.1.1. Die Annahmen des Koopmans-Beckmann-Modells

Die Grundannahmen des Modells der innerbetrieblichen Standortplanung (quadratisches Zuordnungsproblem) von Koopmans / Beckmann aus dem Jahre 1957 sind die folgenden:

- Zur Anordnung von Organisationseinheiten dient ein Standortträger mit n gleich großen potentiellen Standorten.
- Die anzuordnenden Organisationseinheiten sind gleich groß. Jeder Standort kann genau eine Organisationseinheit aufnehmen.
- Die Entfernungen zwischen den Standorten sind bekannt. Bei den Distanzangaben handelt es sich um die Entfernungen zwischen den Mittelpunkten zweier Standorte.
- Zwischen den Organisationseinheiten findet ein Warenaustausch statt. Die Höhe dieses Austausches pro Periode ist bekannt.
- Die Kosten der Warentransporte verhalten sich proportional zu Entfernung und Transportmenge. Der Übersichtlichkeit halber wird der Proportionalitätsfaktor 1 verwendet, so dass die Kosten dem Produkt aus Entfernung und Transportmenge entsprechen.

Das Ziel ist die Anordnung der Organisationseinheiten auf den zur Verfügung stehenden Standorten derart, dass die Kosten für die Warentransporte pro Periode minimal werden.^[4]

3.1.2. Mathematische Formulierung

Zur mathematischen Formulierung sollen die folgenden Variablen verwendet werden

Abbildung in dieser Leseprobe nicht enthalten

Damit ergibt sich folgendes nichtlineare Optimierungsproblem

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Grundmodell des quadratischen Zuordnungsproblems

In der Zielfunktion werden alle Transportkosten summiert, die sich aus den n! möglichen Zuordnungen der Organisationseinheiten ergeben. In den n Nebenbedingungen aus (2) wird sichergestellt, dass jedem Standort p genau eine Organisationseinheit zugeordnet wird, in den n Nebenbedingungen (3) wird gesichert, dass jede Organisationseinheit genau einem Standort zugeordnet wird. Bei den n2 Entscheidungsvariabeln handelt es sich um Binärvariablen (4).

3.2. Varianten des Grundmodells

Der Vollständigkeit halber soll in einem kurzen Abriss auch auf die Varianten des Grundmodells und deren Besonderheiten hingewiesen werden.

3.2.1. Explizite Berücksichtigung der Zuordnungskosten

Berücksichtigt man die Kosten, die entstehen, wenn die Organisationseinheit i auf dem Standort p angeordnet wird, entsteht das folgende Problem. Mit den Variablen

Abbildung in dieser Leseprobe nicht enthalten

ergibt sich die folgende Problemformulierung

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Quadratisches Zuordnungsproblem mit Zuordnungskosten

Das Problem konvertiert zum Grundproblem (1)-(4), wenn direkte Zuordnungskosten cij unberücksichtigt bleiben.

3.2.2. Symmetrie

Im Falle symmetrischer Entfernungen und/oder Transportintensitäten brauchen aus den entsprechenden Matrizen lediglich die oberen Dreiecksmatrizen betrachtet zu werden.

3.2.3. Überzahl an Standorten

Stehen mehr Standorte als Organisationseinheiten zur Verfügung, ändert sich die Zielfunktion zur Summation über alle Standorte und Nebenbedingung (3) in eine ≤-Bedingung.

[...]

^[1] Ball et al. (1995)

^[2] Quelle: eigene Darstellung

^[3] Quelle: Eigene Darstellung

^[4] Vgl. Domschke / Drexl (1993) 138 f