DIPLOMARBEIT
H
YBRIDE
A
NSÄTZE BASIEREND AUF
D
YNAMIC
P
ROGRAMMING
UND
A
NT
C
OLONY
O
PTIMIZATION ZUR MEHRKRITERIELLEN
O
PTIMIERUNG
K
ÜRZESTER
-W
EGE
-P
ROBLEME IN GERICHTETEN
G
RAPHEN AM
B
EISPIEL VON
A
NGEBOTSNETZEN IM
E
XTENDED
V
ALUE
C
HAIN
M
ANAGEMENT
eingereicht von
S
ASCHA
H
ÄCKEL
zur Erlangung des akademischen Grades
Diplom-Wirtschaftsinformatiker (Dipl.-Wirt.-Inf.)
an der
Technischen Universität Chemnitz
Fakultät für Wirtschaftswissenschaften
Professur für Produktionswirtschaft und Industriebetriebslehre
Chemnitz, den 24. August 2006
Inhaltsverzeichnis
Abbildungsverzeichnis
vii
Tabellenverzeichnis
ix
Algorithmenverzeichnis
x
Abkürzungsverzeichnis
xi
Verwendete Notationen
xiii
Symbolverzeichnis
xiv
1
Einführung
1
1.1
Gegenstand der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Dokumentstruktur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2
Theoretische Grundlagen
3
2.1
Grundlagen der Graphentheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.1
Gerichtete Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.1.2
Wichtige Eigenschaften von Graphen . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
Grundlagen der Komplexitätstheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2.1
Komplexitätsmaße . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.2
Komplexitätsklassen P und NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2.3
Problemrelationen und polynomielle Reduktion . . . . . . . . . . . . . . . . . . . .
6
2.3
Diskrete und kombinatorische Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.3.1
Problemdefinition und Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.3.2
Ausgewählte Optimierungsprobleme . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3
Optimierung bei Mehrfachzielsetzung
11
3.1
Mehrkriterielle Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.1.1
Problemstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.1.2
Zielbeziehungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.2
Optimalität bei mehrfacher Zielsetzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.2.1
Paretooptimalität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.2.2
Eigenschaften der paretooptimalen Lösungsmenge . . . . . . . . . . . . . . . . . .
14
3.2.3
Idealpunkte und Nadir-Punkt der Front . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.3
Multikriterielle kombinatorische Optimierung . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.3.1
Klassifizierung entscheidungstheoretischer Ansätze . . . . . . . . . . . . . . . . . .
16
3.3.2
A-priori-Methoden als reduktive Verfahren . . . . . . . . . . . . . . . . . . . . . . .
19
3.3.3
A-posteriori-Methoden als nicht-reduktive Verfahren . . . . . . . . . . . . . . . . .
20
iii
INHALTSVERZEICHNIS
3.4
Reduktive Entscheidungsmodelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.4.1
Lexikographische Ordnung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.4.2
Haupt- und Nebenziele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.4.3
Methode der gewichteten Summen und Produkte . . . . . . . . . . . . . . . . . . .
23
3.4.4
AHP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.4.5
Fuzzy Decision Making . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.4.6
Goal Programming und Compromise Programming . . . . . . . . . . . . . . . . . .
29
3.5
Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.5.1
Beurteilung der A-priori-Methoden . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
3.5.2
Beurteilung der A-posteriori-Methoden . . . . . . . . . . . . . . . . . . . . . . . . .
30
4
Optimierung von Angebotsnetzen im EVCM
33
4.1
Extended Value Chain Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.1.1
Phasenmodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.1.2
Prozessvariantenplan und Prozessplan . . . . . . . . . . . . . . . . . . . . . . . . .
35
4.1.3
Angebotsnetze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4.1.4
Problemstellung bei der Kompetenzzellenauswahl . . . . . . . . . . . . . . . . . .
39
4.2
Formalisierung des Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.2.1
Problemgraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
4.2.2
Restriktionssystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
4.2.3
Lösungskonstruktion und Problemstellung . . . . . . . . . . . . . . . . . . . . . . .
45
4.3
Zielsetzungen der Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4.3.1
Preis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4.3.2
Lieferwahrscheinlichkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4.3.3
Liefertermin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4.4
Angebote mit unvollständigen Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
4.4.1
Ansatz mit impliziter Behandlung von Teilmengen . . . . . . . . . . . . . . . . . .
53
4.4.2
Ansatz mit Behandlung expliziter Fehlmengen . . . . . . . . . . . . . . . . . . . . .
55
4.5
Problemkomplexität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
5
Dynamic Programming
61
5.1
Theoretische Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
5.1.1
Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
5.1.2
Problemstellung und Lösungsprinzip . . . . . . . . . . . . . . . . . . . . . . . . . .
62
5.1.3
Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
5.2
Problemspezifische Modellierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
5.2.1
Problemspezifischer Basisalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . . .
69
5.2.2
Umgang mit Divergenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
5.3
Komplexitätsbetrachtungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
5.3.1
Komplexität bei einkriteriellen Problemen mit rein konvergierenden Prozessplänen 80
5.3.2
Komplexität bei einkriteriellen Problemen mit allgemeinen Prozessplänen . . . . .
80
6
Ant Colony Optimization
83
6.1
Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
6.1.1
Einordnung des Verfahrens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
6.1.2
Naturanalogie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
6.1.3
ACO-Metaheuristik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
6.2
Verschiedene Ansätze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
6.2.1
Ant System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
iv
INHALTSVERZEICHNIS
6.2.2
Ant Colony System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
6.3
Mehrkriterielle Ameisenalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
6.3.1
Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
6.3.2
Paretooptimierung mit ACO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
6.3.3
Gewichtung bei beliebiger Zielanzahl . . . . . . . . . . . . . . . . . . . . . . . . . .
97
6.4
Problemspezifische Modellierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.4.1
Ant Family Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.4.2
Lösungskonstruktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.4.3
Heuristikwerte für das Angebotsnetz . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.4.4
Konvergenzverhalten und Pheromoninitialisierung . . . . . . . . . . . . . . . . . . 109
7
Hybride Methoden und Erweiterungen
111
7.1
Pheromonaktualisierung bei Paretooptimierung . . . . . . . . . . . . . . . . . . . . . . . . 111
7.1.1
Eigenschaften der bisherigen Strategie . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.1.2
Nadir-Punkt-Strategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
7.2
Paretooptimierung mit Auswahl nach Fuzzy Decision Making . . . . . . . . . . . . . . . . 115
7.2.1
Ausgangssituation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.2.2
Auswahlwahrscheinlichkeiten über Fuzzy Decision Making . . . . . . . . . . . . . 116
7.3
Problemreduktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.3.1
Dominanz von Teilgraphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.3.2
Algorithmisches Konzept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7.4
Die Look-Ahead-Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7.4.1
Ausgangssituation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7.4.2
Konzept der Look-Ahead-Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
8
Evaluierung
125
8.1
Evaluierung des Parallel Path Problems und des dynamischen Programms . . . . . . . . . 125
8.1.1
Verwendete Evaluierungsmaße . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
8.1.2
Abhängigkeiten zwischen Komplexität und Zielkriterien . . . . . . . . . . . . . . . 127
8.1.3
Abhängigkeiten zwischen Paretofront und Zielfunktionen . . . . . . . . . . . . . . 128
8.1.4
Komplexität von Angebotsnetzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
8.1.5
Probleme mit divergenten Prozessplänen . . . . . . . . . . . . . . . . . . . . . . . . 132
8.2
Evaluierung ACO und hybride Ansätze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
8.2.1
Verwendete Evaluierungsmaße . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
8.2.2
Problemlösungsverhalten der Ameisenalgorithmen . . . . . . . . . . . . . . . . . . 136
8.2.3
Verwendung von Routingtabellen und Tabulisten . . . . . . . . . . . . . . . . . . . 137
8.2.4
Aktualisierungsstrategien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
8.2.5
Analyse verschiedener Aggregationsmethoden . . . . . . . . . . . . . . . . . . . . 141
8.2.6
Standard-Heuristik und Look-Ahead-Heuristic . . . . . . . . . . . . . . . . . . . . 142
8.2.7
Problemreduktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
Fazit und Ausblick
149
A Ergänzungen und Detailinformationen zur Evaluierung
151
A.1 Evaluierte Problemgraphen und Prozesspläne . . . . . . . . . . . . . . . . . . . . . . . . . 151
A.1.1 Technologiegraphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
A.1.2 Problemgraphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
A.2 Verwendete Konfigurationen und Parameter von ACO . . . . . . . . . . . . . . . . . . . . 154
A.2.1 Verwendete Konfiguration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
v
INHALTSVERZEICHNIS
A.2.2 Verwendete Parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
B Beispielrechnung
157
B.1 Dynamisches Programm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
B.2 Lösungskonstruktion ACO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Literaturverzeichnis
167
Register
175
vi
Abbildungsverzeichnis
1.1
Strukturelle Abhängigkeit der Kapitel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.1
Beispielhaftes Kürzeste-Wege-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3.1
Vergleich von MODM und MADM sowie der kombinatorischen Optimierung . . . . . . .
17
3.2
Indifferenzkurven bei Verfahren mit und ohne Kompensation . . . . . . . . . . . . . . . .
18
3.3
Grafische Darstellung von Zielfunktionen der Methode der gewichteten Summe . . . . .
25
4.1
Phasenmodell des EVCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
4.2
Beispielhafter Graph eines Prozessplans für die Herstellung eines Produktes . . . . . . . .
36
4.3
Beispielhaftes Angebotsnetz für ein Produkt . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4.4
Konvergenzreihen bei der Multiplikation vieler kleiner Werte für C#-Datentypen . . . . .
48
4.5
Schematische Darstellung eines Fließkommadatentyps . . . . . . . . . . . . . . . . . . . .
49
4.6
Rucksackproblem als bikriterielles Shortest Path Problem . . . . . . . . . . . . . . . . . . .
59
5.1
Einordnung von Dynamic Programming als Verfahren . . . . . . . . . . . . . . . . . . . .
62
5.2
Schematisches Modell eines dynamischen Optimierungsproblems . . . . . . . . . . . . . .
64
5.3
Paretooptimierung bei dynamischen Programmen . . . . . . . . . . . . . . . . . . . . . . .
67
5.4
Beispielhafte Segmentierung des Angebotsnetzes in Stufen . . . . . . . . . . . . . . . . . .
70
5.5
Minimalbeispiel für die Nichteignung von Mittelwertfunktionen bei dynamischen Pro-
grammen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
5.6
Beispiel für die Verletzung der M
ARKOV
-Eigenschaft bei divergenten Prozessen . . . . . .
75
5.7
Teilproblembildung bei divergierenden Prozessen . . . . . . . . . . . . . . . . . . . . . . .
75
5.8
Komplexer Prozessplan mit exponentiellen Aufwand . . . . . . . . . . . . . . . . . . . . .
81
6.1
Einordnung von Ant Colony Optimization als heuristisches Verbesserungsverfahren . . .
84
6.2
Doppelbrückenexperiment mit argentinischen Ameisen . . . . . . . . . . . . . . . . . . . .
85
6.3
Kriteriengewichtung auf Basis des Durchmusterungsparameters . . . . . . . . . . . . .
98
6.4
Suchdurchmusterung bei drei Kriterien . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
7.1
Vergleich der mehrkriteriellen Aktualisierungsstrategien . . . . . . . . . . . . . . . . . . . 113
7.2
Problemreduktion mit dynamischer Programmierung am Beispiel . . . . . . . . . . . . . . 118
8.1
Komplexität und Anzahl der Zielkriterien . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
8.2
Konvexe Paretofront des Problems T010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
8.3
Konkave Paretofront des Problems T011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
8.4
Paretofront des Problems G036 mit typischem Verlauf für Angebotsnetze . . . . . . . . . . 130
8.5
Vergleich der Approximation der verschiedenen Algorithmenvarianten für G030 . . . . . 138
8.6
Vergleich des Diversitätsmaßes der verschiedenen Algorithmenvarianten für G030 . . . . 138
8.7
Branching-Faktor bei der Anwendung der verschiedenen Algorithmen auf G030 . . . . . 139
vii
ABBILDUNGSVERZEICHNIS
8.8
Paretofront und nichtdominierte Fronten verschiedener ACO-Läufe für G040 . . . . . . . 142
8.9
Approximation als Distanzmaß im Vergleich von Standard-Heuristik und LAH für G040
144
8.10 Diversität als Distanzmaß im Vergleich von Standard-Heuristik und LAH für G040 . . . . 144
8.11 Vergleich der nichtdominierten Fronten von LAH und Standard-Heuristik . . . . . . . . . 146
A.1 Prozesspläne der Technologiegraphen TG01 und TG01a-c . . . . . . . . . . . . . . . . . . . 152
B.1 Darstellung des Problemgraphen von B001 . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
B.2 Zugrunde liegender Prozessplan des Problems B001 . . . . . . . . . . . . . . . . . . . . . . 159
viii
Tabellenverzeichnis
3.1
(1-9)-Bewertungsskala des Analytical Hierarchy Process . . . . . . . . . . . . . . . . . . .
26
8.1
Zielfunktionen der Probleme T010, T011 und G036 . . . . . . . . . . . . . . . . . . . . . . . 128
8.2
Übersicht über die exakte Lösbarkeit beziehungsweise Nichtlösbarkeit von Problemen . . 131
8.3
Übersicht über die exakte Lösbarkeit beziehungsweise Unlösbarkeit von Problemen mit
Divergenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
8.4
Eingesetzte Parameterkonfigurationen von verschiedenen ACO-Algorithmen . . . . . . . 136
8.5
Ergebnisse der Evaluierungsläufe mit mehrkriteriellen Ameisenalgorithmen . . . . . . . . 137
8.6
Ergebnisse der Evaluierungsläufe mit und ohne Verwendung von Routing . . . . . . . . . 139
8.7
Testergebnisse bei Verwendung verschiedener Update-Strategien . . . . . . . . . . . . . . 141
8.8
Testergebnisse bei Verwendung verschiedener Aggregationsmethoden . . . . . . . . . . . 141
8.9
Approximation, Diversität und Größe der ermittelten Front im Vergleich bei Verwendung
der Standard-Heuristik und der Look-Ahead-Heuristic . . . . . . . . . . . . . . . . . . . . 143
8.10 Evaluierung der Schwellwertübertretungen der Diversität bei Verwendung der Standard-
Heuristik und der Look-Ahead-Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8.11 Testergebnisse für den Vergleich von LAH in der Best- und Worst-Case-Variante hinsicht-
lich Distanz, Diversität und Frontgröße . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
8.12 Testergebnisse für den Vergleich von LAH in der Best- und Worst-Case-Variante hinsicht-
lich der Diversität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.13 Auswirkungen der Problemreduktion auf die Eingabelänge und Lösungsraumgröße . . . 147
8.14 Testergebnisse mit den Auswirkungen der Problemreduktion auf ACS . . . . . . . . . . . 148
A.1 Übersicht über alle verwendeten Prozesspläne (Technologiegraphen) . . . . . . . . . . . . 151
A.2 Übersicht über alle verwendeten Problemgraphen . . . . . . . . . . . . . . . . . . . . . . . 153
A.3 Parameter der verwendeten Konfigurationen (1) . . . . . . . . . . . . . . . . . . . . . . . . 154
A.4 Parameter der verwendeten Konfigurationen (2) . . . . . . . . . . . . . . . . . . . . . . . . 155
A.5 Parameter der verwendeten Konfigurationen (3) . . . . . . . . . . . . . . . . . . . . . . . . 155
B.1 Zielfunktionsbeiträge der Angebote des bikriteriellen Problems B001 . . . . . . . . . . . . 157
ix
Algorithmenverzeichnis
1
Automatisierte Generierung des Restriktionssystems eines Angebotsnetzes . . . . . . . .
44
2
Testalgorithmus zur Analyse der Präzision des Datentyps double . . . . . . . . . . . . . . .
47
3
Dynamisches Programm zur Lösung rein konvergierender Parallel Path Probleme . . . .
73
4
Hilfsfunktionen für das dynamische Programm für rein konvergierende Probleme . . . .
74
5
Auflösung von Restriktion und restriktionsbehaftete Pfadkonstruktion . . . . . . . . . . .
77
6
Dominanzvergleiche bei Divergenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
7
Generierung von Lösungskombinationen bei Problemen mit Divergenzen . . . . . . . . .
79
8
Algorithmenskelett der ACO-Metaheuristik . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
9
Generierung von Routingtabellen für das Forwarding von Ameisenagenten . . . . . . . . 104
10
Lösungskonstruktion der Ameisen unter Nutzung von Routing und Restriktionen . . . . 106
11
Generierung von Tabulisten für Knoten als Agentenrestriktionen . . . . . . . . . . . . . . 107
12
Erstellen von zulässigen Auswahlmengen auf Basis von Tabulisten . . . . . . . . . . . . . 108
13
Dynamisches Programm zur Problemreduktion . . . . . . . . . . . . . . . . . . . . . . . . 119
14
Hilfsfunktionen zur Problemreduktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
15
Berechnung von Look-Ahead-Heuristic-Werten für das Parallel Path Problem . . . . . . . 123
16
Bestimmung der Lösungsraumgröße . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
x
Abkürzungsverzeichnis
ACO
Ant Colony Optimization
ACS
Ant Colony System
AFH
Ant Family Heuristic
AHP
Analytical Hierarchy Process
AS
Ant System
ATP
Aviable To Promise
CP
Compromise Programming
CTP
Capable To Promise
EAS
Elitist Ant System
EVCM
Extended Value Chain Management
FDM
Fuzzy Decision Making
GP
Goal Programming
IMK
Informationstechnischer Modellkern
LAH
Look-Ahead-Heuristic
LIFO
Last In First Out
MADM
Multi Attribute Decision Making
MODM
Multi Objective Decision Making
MMAS
MAX -MIN Ant System
MOP
Multi Objective Optimization Problem
NP
Non-deterministic [in] Polynomial Time (Komplexitätsklasse)
O.B.d.A.
Ohne Beschränkung der Allgemeinheit
P
Deterministic [in] Polynomial Time (Komplexitätsklasse)
PACO
Population-based Ant Colony Optimization
PPP
Parallel Path Problem
SAT
satisfiability, Erfüllbarkeitsproblem der Aussagenlogik
xi
ABKÜRZUNGSVERZEICHNIS
SOP
Single Objective Optimization Problem
TOPSIS
Technique for Order Preference by Similarity to Ideal Solution
UML
Unified Modelling Language
#
Anzahl
xii
Verwendete Notationen
a
b
Eine Lösung a dominiert eine Lösung b stark; a ist b vorzuziehen
a
b
Eine Lösung a dominiert eine Lösung b schwach; a ist b vorzuziehen
|A|
Länge der Menge A; entspricht der Anzahl der Elemente einer Menge A
x R
d
x
ist ein Vektor mit der Länge d; jedes x
i
mit i = {1..d} ist Element der Menge R mit der
Eigenschaft x
i
0
x
Alternative Darstellungsform eines Vektors x
a b
Vereinigung der Mengen a und b; logische OR-Verknüpfung: Entweder a oder b oder beide
a b
Durchschnitt der Mengen a und b; logische AND-Verknüpfung: Sowohl a als auch b
ab
Logische XOR-Verknüpfung; Exklusives Oder: Entweder a oder b
a 1
Zuweisungsoperation in Algorithmen; a wird der Wert 1 zugewiesen
e
ab
e
ist ein Bogen beziehungsweise eine gerichtete Kante in einem Digraphen; der Startpunkt
ist a und der Endpunkt ist b
a.b
b
ist in Algorithmen ein Attribut oder Unterobjekt von a
a
b
Allgemeiner Operator, der entsprechend der Zielfunktion angepasst wird; bei additiver Ziel-
funktion kann die Darstellung beispielsweise in a + b überführt werden, bei multiplikativer
in a · b
f : A B f
ist eine Abbildung der Menge A auf die Menge B
A B
Zeitliche oder strukturelle Ordnung der Komponenten A und B; B folgt auf A
xiii
Symbolverzeichnis
Problemrepräsentation
G
Graph
V
Knotenmenge eines Graphen
E
Kantenmenge eines Graphen
K
Kantengruppenmenge eines Graphen
S
Restriktionsmenge eines Graphen
Z
Anzahl der Zielkriterien eines MOP
z
Zielkriterium mit z {1, ..., Z}
z
Übergeordnetes (tatsächliches) Ziel des Kriteriums z
f
z
e
, f
z
v
Zielfunktionsbeiträge für Kanten e oder Knoten v des Kriteriums z
F
z
Zielfunktion des Kriteriums z eines MOP
v
i
Knoten mit v
i
V
e
ij
Gerichtete Kante von Knoten v
i
zu Knoten v
j
mit e
ij
E
k
Kantengruppe
o
Knotengruppe
q
Vorprodukt
Divergenzpunkteigenschaft eines Knotens
r
+
, r
-
Positive beziehungsweise negative elementare Restriktionsfunktionen (Attribute)
R
+
,R
-
Positive beziehungsweise negative Restriktion
R
Restriktionsvektor
v
Start
Künstlicher Startknoten mit v
Start
V
s
V
s
, E
s
Menge für Startknoten beziehungsweise -kanten
Lösungsraum
Eine Lösung
,
Paretooptimale Lösungsmenge, paretooptimale Lösung
xiv
SYMBOLVERZEICHNIS
E
, V
Kanten- beziehungsweise Knotenmenge einer Lösung
S
,C
Unaufgelöste beziehungsweise aufgelöste Restriktionen einer (Teil-)Lösung
Y
Zielraum
Y
Paretofront
y
Vektor beziehungsweise Punkt in der Paretofront mit y
Y
y
+
, y
-
Positiver beziehungsweise negativer Idealpunkt des Zielraums
y
N
Nadir-Punkt der Paretofront
Dynamische Programmierung
t
Stufe eines Teilproblems mit t n
n
Höchstmögliche Stufe eines Teilproblems
u
,u
Entscheidungsvariable beziehungsweise Entscheidungsvektor
u
, u
Optimale Entscheidung beziehungsweise Entscheidungsmenge
x, x
Zustandsvariable beziehungsweise Zustandsvektor
x
, x
Optimaler Zustand beziehungsweise Zustandsvektor
Zustandsüberführungsfunktion
F
Zielfunktion
f
t
Zielfunktionsbeitrag der Stufe t
Ant Colony Optimization
Ameise
M
Gedächtnis einer Ameise
X
, ~
X
Zustandsraum eines Problems beziehungsweise Menge aller zulässigen Zustände
x
Zustand mit x X
Bedingungen eines Problems
term
Menge von Abbruchbedingungen für die Lösungskonstruktion von
ij
Pheromonwert einer Kante e
ij
0
Initialisierungsmenge für Pheromonkonzentration
min
,
max
Pheromonunter- beziehungsweise obergrenze bei MMAS
ij
Heuristikwert einer Kante e
ij
d
ij
Entfernungswert zwischen den Knoten v
i
und v
j
, Kantengewicht der Kante e
ij
ij
Aktualisierungsmenge der Kante e
ij
p
ij
Auswahlwahrscheinlichkeit einer Kante e
ij
für eine Ameise
xv
SYMBOLVERZEICHNIS
N
i
Alternativenmenge für die Folgeentscheidung respektive Nachbarschaft einer Ameise , die
sich auf der Position des Knotens v
i
befindet
bsf
Bis zum Zeitpunkt beste ermittelte Lösung (best-so-far)
ib
Iterationsbeste Lösung (iterations-best)
Gewichtung beziehungsweise Einfluss des Pheromonwertes
Gewichtung beziehungsweise Einfluss des Heuristikwertes
Exploitationsparameter bei der Nadir-Punkt-Strategie
Binäre Funktion, die die Aktualisierungsberechtigung einer Ameise beschreibt
z
Gewichtung beziehungsweise Einfluss eines Kriteriums z
,
c
Gewichtungsvektor einer Ameise beziehungsweise einer Kolonie c
Verdunstungsparameter
q
0
Parameter zur Steuerung der Exploitation bei ACS
Glätterungsparameter bei der Verdunstung nach ACS
,
c
Durchmusterungsparameter für Ameisen beziehungsweise Kolonien
Menge von Durchmusterungsintervallen für ein Kriterium
Einzelner Gewichtungspunkt innerhalb eines Intervall mit
c
Kolonie mit c < C
C
Anzahl der Kolonien
k
Menge der zulässigen Alternativen aus einer Kantengruppe k bei der Lösungskonstruktion
mit
k
E
T
Routingtabelle mit T E
T abu
Tabuliste mit T abu E
Evaluierung
Ord
Ordnung des Lösungsraums
RCmplx
Relative Komplexität
CCmplx
Absolute Komplexität
Input
Eingabelänge des Graphen (Kanten- und Knotenanzahl)
diversity
Mittlere Distanz der Paretofront zur nichtdominierten Front
dist
Mittlere normierte Distanz einer nichtdominierten Front zur Paretofront
branching
Verzweigungsfaktor für das Parallel Path Problem
xvi
SYMBOLVERZEICHNIS
Sonstige
Nebenbedingungen
O
Komplexitätsmaß, maximaler Aufwand der Problemlösung eines Algorithmus
Komplexitätsmaß, minimaler Aufwand der Problemlösung eines Problems
C
Allgemeine Komplexitätsklasse
P, NP
Komplexitätsklassen (siehe Beschreibungen im Abkürzungsverzeichnis)
R
Menge der reellen Zahlen
Z
Mengen der ganzen Zahlen
N
Menge der natürlichen Zahlen
µ
Zugehörigkeitsfunktion in der Fuzzy Logic beziehungsweise bei Fuzzy Decision Making
U, u
Entscheidungsmenge beziehungsweise einzelne Entscheidung der Entscheidungsmenge in
der diskreten Optimierung
xvii
Kapitel 1
Einführung
»Aller Anfang ist heiter, die Schwelle ist der Platz
der Erwartung.«
Johann Wolfgang von Goethe
In einer Umwelt, die von Vernetzung und Globalisierung geprägt ist, wächst der Wettbewerbsdruck
auf die Unternehmen am Markt stetig. Die effektive Nutzung der Ressourcen einerseits und die enge
Zusammenarbeit mit Lieferanten und Kunden andererseits führen für nicht wenige Unternehmen des
industriellen Sektors zu entscheidenden Wettbewerbsvorteilen, die das Fortbestehen jener Unterneh-
men am Markt sichern. Viele Unternehmen verstehen sich aus diesem Grund als Bestandteil einer so
genannten Lieferkette (Supply Chain).
1
Die unternehmensübergreifende Steuerung und Optimierung des Wertschöpfungsprozesses stellt
ein wesentliches Problem des Supply Chain Managements dar und besitzt zur Erzielung von Wettbe-
werbsvorteilen einer Lieferkette gegenüber Konkurrenten ein sehr hohes Potential.
Ein Forschungsschwerpunkt der Professur Produktionswirtschaft und Industriebetriebslehre sowie
des Arbeitskreises Logistische Informationssysteme (LogIs) an der Technischen Universität Chemnitz sind
hierarchielose, regionale Produktionsnetzwerke.
2
Das im Rahmen dieser Forschungsarbeit entstandene
kompetenzzellenbasierte Extended Value Chain Management (EVCM)
3
generiert - vereinfacht beschrieben
- unternehmensübergreifende Angebotsnetze mit dem Ziel, eine den Präferenzen des Kunden des Un-
ternehmensnetzwerkes entsprechende Kombination von Kompetenzzellen auszuwählen, die die Durch-
führung bestimmter Prozesselemente entlang der Wertschöpfung des für den Kunden herzustellenden
Produktes übernehmen. Diese Auswahl bedarf einer übergreifenden Optimierung.
4
1.1
Gegenstand der Arbeit
Gegenstand dieser Arbeit ist das im Extended Value Chain Management bestehende Problem der Op-
timierung von Angebotsnetzen. Im Rahmen dieser Arbeit soll das bestehende Problem ausführlich be-
schrieben und analysiert werden. Eine wesentliche Kernfrage stellt die Komplexität des Problems dar,
welche sowohl in der uni- als auch in der multikriteriellen Variante betrachtet werden soll. Neben der
Vorstellung des Problems sollen Ansätze auf Basis der dynamischen Programmierung und von Ant
Colony Optimization erörtert werden, die das Problem exakt beziehungsweise näherungsweise lösen.
Darauf aufbauend soll eine Hybridisierung der beiden Lösungsansätze angestrebt werden.
Neben der problemspezifischen Modellierung sollen die entwickelten Ansätze außerdem in Hinblick
auf ihre Eignung im Rahmen der informationstechnischen Umsetzung des EVCM-Konzeptes untersucht
werden. Hierzu sollen die entwickelten Algorithmen einer Evaluierung unterzogen werden, die sowohl
die Lösungsgüte als auch den notwendigen Berechnungsaufwand einbezieht.
1
Vgl. [For06, S. 1f.].
2
Vgl. [DF06], [Log06].
3
Vgl. [Tei02].
4
Vgl. [Tei02, S. 481ff.].
1
KAPITEL 1. EINFÜHRUNG
1.2
Dokumentstruktur
Das in dieser Arbeit untersuchte Optimierungsproblem von Angebotsnetzen im EVCM stellt ein kom-
plexes graphentheoretisches Problem der kombinatorischen Optimierung dar. Zudem unterliegt das
Problem einer Mehrfachzielsetzung. Aus diesem Grund soll nach der Erläuterung einiger theoretischer
Grundlagen aus den Bereichen der Graphentheorie, der Komplexitätstheorie und der diskreten Op-
timierung in Kapitel 2 die Thematik der mehrkriteriellen Optimierung in Kapitel 3 näher untersucht
werden.
In Kapitel 4 findet anschließend eine Einführung in die Begriffswelt des Extended Value Chain Ma-
nagements, gefolgt von der detaillierten Beschreibung des Optimierungsproblems in Angebotsnetzen
statt. Anschließend wird das Problem formalisiert und bezüglich seiner Komplexität näher untersucht.
In den beiden darauf folgenden Kapiteln 5 und 6 werden mit der dynamischen Programmierung
und Ant Colony Optimization ein exaktes Verfahren und ein heuristischer Lösungsansatz einerseits
theoretisch erläutert und andererseits problemspezifisch modelliert.
Diese Lösungskonzepte werden in Kapitel 7 aufgegriffen und zu hybriden Ansätzen zur Optimie-
rung von Angebotsnetzen weiterentwickelt.
Die vorgestellten Methoden sollen in Kapitel 8 abschließend evaluiert werden. Abbildung 1.1 zeigt
die strukturellen Abhängigkeiten zwischen den einzelnen Kapiteln.
Theoretische Grund-
lagen
2
Optimierung bei
mehreren Zielen
3
Hybride Optimierung
von Angebotsnetzen
Evaluierung der vor-
gestellten Verfahren
7
8
Dynamische Pro-
grammierung
Ant Colony
Optimization
5
6
Angebotsnetze
im EVCM
4
Abbildung 1.1: Strukturelle Abhängigkeit der Kapitel
2
Kapitel 2
Theoretische Grundlagen
Bevor die eigentliche Thematik dieser Arbeit erörtert werden kann, ist die Vorstellung einiger theore-
tischer Grundlagen aus den Fachbereichen der Graphentheorie, der diskreten Optimierung sowie der
Komplexitätstheorie unabdingbar. Aufgrund dessen sollen die notwendigen Grundlagen in gebotener
Kürze vorgestellt werden.
2.1
Grundlagen der Graphentheorie
In diesem Abschnitt werden ausgewählte grundlegende Bausteine aus der Graphentheorie erläutert,
um begriffliche Verwendungen in späteren Teilen der Arbeit klarzustellen und abzugrenzen. In diesem
Zusammenhang soll zunächst der Graph als theoretisches Konstrukt und anschließend einige Eigen-
schaften dieses Konstruktes erläutert werden.
2.1.1
Gerichtete Graphen
Ein Graph G kann über das Tupel G = (V, E) definiert werden. In diesem Zusammenhang beschreibt V
eine endliche oder unendliche
1
, nichtleere Menge, deren Elemente v V als Knoten, Ecken oder Punkte
bezeichnet werden. Die Elemente e = {a, b} mit a, b V der Menge E V
2
beschreiben zweielementige
Teilmengen aus V und werden als Kanten des Graphen zwischen den Endpunkten a und b bezeichnet,
wenn a = b ist. Im Falle, dass a = b gilt, wird ein Element e Schlinge genannt. In der graphischen
Darstellung von Graphen werden Knoten als Punkte oder Kreise und Kanten als verbindende Linien
zwischen diesen Punkten dargestellt. In gerichteten Graphen, auch Digraphen
2
genannt, setzt sich die
Menge E aus geordneten Paaren (a, b) zusammen, wobei a Startpunkt oder tail und b Endpunkt oder
head heißt. Aus Gründen der Unterscheidung zu ungerichteten Graphen wird für eine gerichtete Kante
auch die Bezeichnung Bogen verwendet. Gerichtete Kanten werden in der graphischen Darstellung mit
einer Pfeilspitze in Richtung des Endpunktes gekennzeichnet. Für Elemente dieser Menge werden die
Notationen e = ab oder e = a b verwendet.
3
Zwei Knoten a und b besitzen in einem Graphen
Mehrfachkanten, falls mindestens zwei oder mehr verschiedene Elemente e
i
E mit i = {1 . . . n} und
i N existieren, welche zwei Knoten a und b miteinander verbinden. Im ungerichteten Fall werden
zwei Kanten e
1
= (a, b)
und e
2
= (b, a)
als parallel bezeichnet. Im gerichteten Fall hingegen heißen die
Bögen beziehungsweise gerichteten Kanten e
1
= a b
und e
2
= b a
antiparallel, da sie zwar die
gleichen Knoten verbinden, sich ihre Richtung aber unterscheidet.
4
1
Im Rahmen dieser Arbeit werden jedoch ausschließlich Graphen mit endlichen Mengen betrachtet.
2
Abkürzung für die engl. Bezeichnung »directed graph«.
3
In dieser Arbeit wurde die Notation abweichend in der Form e
ab
gewählt.
4
Vgl. [Die00, S. 2f. i.V.m. S.25f.] und [Jun94, S. 18f].
3
KAPITEL 2. THEORETISCHE GRUNDLAGEN
2.1.2
Wichtige Eigenschaften von Graphen
Neben der Definition sollen nachfolgend einige wesentliche Eigenschaften betrachtet werden, über wel-
che Graphen verfügen können.
Die Eigenschaft der Vollständigkeit besitzt ein Graph genau dann, wenn je zwei Knoten v
i
, v
j
V des
Graphen G mit v
i
= v
j
durch eine Kante verbunden sind. Ein Graph wird hingegen genau dann als leer
bezeichnet, wenn E = ist.
5
Eine Kantenfolge in einem gerichteten Graphen ist eine Folge aus Kanten und Knoten, wobei einem
Knoten eine Kante und einer Kante ein Knoten folgt. Sie beginnt und endet mit einem Knoten. Demnach
kann eine Kantenfolge in der Form v
0
e
01
v
1
e
12
· · · e
i-1i
v
i
e
ii+1
· · ·
e
k-1k
v
k
mit 0 < k N und i = 1, ..., k dargestellt werden, wobei die Kante e
i-1i
die Verbindung
des Knotens v
i-1
und v
i
repräsentiere, wobei v
i
der Endpunkt der Kante ist. Als Weg oder Pfad wird
eine Kantenfolge genau dann bezeichnet, wenn alle Knoten v
0
, ..., v
k
und folglich auch alle Kanten der
Folge voneinander verschieden sind. Wenn die Teilkantenfolge v
1
...v
k-1
einen Weg repräsentiert und
die Kantenfolge aufgrund von v
0
= v
k
geschlossen ist, heißt sie Kreis oder Zyklus. Graphen, die keine
Kreise besitzen, werden als zyklenfreie Graphen bezeichnet.
6
Die Eigenschaft des Zusammenhangs besitzt ein nichtleerer ungerichteter Graph genau dann, wenn
für je zwei Knoten v
i
, v
j
V des Graphen G ein Weg zwischen v
i
und v
j
existiert.
7
Ein Graph heißt gewichtet oder bewertet, wenn Kosten- oder Nutzenwerte für die einzelnen Kanten
oder Knoten des Graphen existieren, die durch Gewichte auf diesen Kanten oder Knoten repräsentiert
werden.
8
2.2
Grundlagen der Komplexitätstheorie
Während in der Praxis hauptsächlich Optimierungsprobleme gelöst werden müssen, betrachtet die
Komplexitätstheorie Entscheidungsprobleme, die aber in enger Beziehung zu den zugehörigen Opti-
mierungsproblemen stehen. Die Transformation eines Optimierungsproblems, das auf die Bestimmung
der bestmöglichen Lösung eines Problems zielt, erfolgt auf Basis einer gegebenen Lösung dieses Pro-
blems und fragt nach der Eigenschaft der Lösung, optimal zu sein. Die Antwort eines Entscheidungs-
problems kann dabei immer über einen binären Wert, das heißt mit ja beziehungsweise wahr und nein
beziehungsweise falsch, formuliert werden.
9
Ziel der Komplexitätstheorie ist es, für mit Computern berechenbare Probleme einen Minimalauf-
wand beziehungsweise -ressourcenbedarf für deren Lösung zu bestimmen. Bei der Ermittlung dieses
Minimalaufwands müssen sämtliche Algorithmen betrachtet werden, welche für die Lösung eines Pro-
blems infrage kommen. Dies stellt aufgrund der Vielzahl der möglichen Algorithmen die wesentliche
Schwierigkeit der Komplexitätstheorie dar.
10
Ein für die Praxis relevanter Untersuchungsgegenstand
der Komplexitätstheorie ist dabei die Grenze zwischen der effizienten Lösbarkeit und dem prohibi-
tiv großen und unvertretbaren Rechenaufwand für die Lösung von Problemen.
11
Aus diesem Grund
werden die Probleme, welche von der Komplexitätstheorie betrachtet werden, so genannten Komple-
xitätsklassen zugeordnet, die eine Aussage über die zu erwartende Schwierigkeit bei der Lösung des
Problems ermöglichen.
Um die Komplexitätsklassen näher erläutern zu können, werden zunächst die gängigen Komplexi-
tätsmaße vorgestellt.
5
Vgl. [Kla99, S. 40f.].
6
Vgl. [Kla99, S. 47].
7
Vgl. [Die00, S. 10f.].
8
Vgl. [BJ06, S. 6], [Dom97, S. 9f.].
9
Vgl. [Wag03, S. 138].
10
Vgl. [Weg03, S. V und S. 3f.].
11
Vgl. [Weg03, S. V und S. 3f.].
4
2.2 Grundlagen der Komplexitätstheorie
2.2.1
Komplexitätsmaße
Der Zeitbedarf, den ein Algorithmus zur Berechnung der Lösung eines Problems benötigt, hängt von
den Eingabeparametern (Problem), dem verwendeten Rechner, der Programmiersprache und der Im-
plementierung des Algorithmus ab. Der Einfluss aller Größen mit Ausnahme der Problem-Eingabepara-
meter ist jedoch entweder stark begrenzt oder statisch.
12
Um ein vergleichbares und allgemeines Kom-
plexitätsmaß zu gestalten, wird dieses in ausschließlicher Abhängigkeit vom verwendeten Algorithmus
und den Eingabeparametern definiert. Als Maß der Komplexität wird dabei die Anzahl der Operatio-
nen oder die Anzahl der Takte beziehungsweise Schritte betrachtet, die ein Algorithmus benötigt, um
das Entscheidungsproblem entweder mit positiver oder negativer Antwort zu lösen.
13
Für ein Problem können in diesem Zusammenhang mehrere Komplexitätsmaße angegeben werden.
Zunächst kann der maximale Aufwand bestimmt werden, welchen ein Algorithmus zur Lösung des
Problems benötigt. Folglich können aus diesem Komplexitätsmaß Aussagen über Algorithmen und de-
ren Effizienz abgeleitet werden. Dieses Maß wird anhand der O-Notation nach Gleichung 2.1 definiert.
14
O (f ) = {t : N - R
|c R
>
n
0
N n n
0
t (n) c · f (n)}
(2.1)
Durch O wird laut Definition die Menge aller Funktionen t beschrieben, für welche ab einem Wert n
0
kein Funktionswert von t (n) über einem Wert c·f (n) liegt, wobei c einen existierenden konstanten Wert
darstellt. Der Parameter n beschreibt die Größe des Problems hinsichtlich der Eingabeparameter, wie
beispielsweise die Anzahl von Knoten und Kanten in graphentheoretischen Problemen.
15
Die Menge O
beschränkt somit die Komplexität mit f (n) nach oben. Ein Algorithmus, welcher durch die Komplexität
O n
2
beschränkt wird, benötigt somit maximal n
2
Schritte beziehungsweise Operationen, bis er das
Problem der Eingabelänge n beantworten kann.
Entgegen dem maximalen Aufwand kann auch ein minimaler Aufwand betrachtet werden, den ein
beliebiger Algorithmus, der das Problem löst, mindestens benötigt, um eine Entscheidung zu treffen.
Dieses Komplexitätsmaß erlaubt demnach Aussagen über die Schwierigkeit des Problems, gestaltet sich
jedoch als sehr schwierig hinsichtlich der Bestimmung, da sämtliche Algorithmen betrachtet werden
müssen, die das Problem lösen. Somit kann im engeren Sinne ausschließlich eine Aussage über alle
bekannten Algorithmen, die das Problem lösen, abgeleitet werden. Dieses Maß wird anhand der -
Notation nach Gleichung 2.2 definiert.
16
(f ) = {t : N - R
|c R
>
n
0
N n n
0
c · f (n) t (n)}
(2.2)
Dieses Maß beschreibt somit mit der Menge auf Basis der Funktion f (n) den minimalen Aufwand
beziehungsweise die minimale Anzahl von Schritten, die ein Algorithmus bei einer Eingabelänge von
n
zur Problemlösung benötigt. Bei einer Komplexität von n
2
existiert kein bekannter Algorithmus,
welcher bei deterministischer Vorgehensweise in weniger als n
2
Schritten mit Sicherheit ein Problem
der Eingabelänge n entscheiden kann.
2.2.2
Komplexitätsklassen P und NP
Die Komplexitätstheorie hat Klassenkonstrukte entwickelt, welche Probleme mit ähnlichen Eigenschaf-
ten bezüglich der Schwierigkeit der Problemlösung zusammenfassen. Relevant für die Praxis sind da-
bei insbesondere die Komplexitätsklassen P und NP. Die Komplexitätsklasse P umfasst alle Probleme,
12
Vgl. [Weg03, S. 21]. Dies begründet sich auch auf der erweiterten churchschen These, welche besagt, dass alle Rechnermodelle
sich gegenseitig mit polynomiellen Aufwand simulieren können und somit Probleme unabhängig vom gewählten Rechnermodell
sind. Vgl. [Weg03, S. 22-25].
13
Vgl. [Weg03, S. 21], [Wag03, S. 138].
14
Vgl. [Wag03, S. 34].
15
Vgl. [Wag03, S. 34].
16
Vgl. [Wag03, S. 35f.].
5
KAPITEL 2. THEORETISCHE GRUNDLAGEN
für die ein bekannter deterministischer Algorithmus existiert, der nach endlich vielen Operationen be-
ziehungsweise Schritten eine Lösung für das Problem liefert, wobei die Anzahl der Schritte durch ein
Polynom p : N -N der nachfolgenden Form begrenzt ist.
17
p (n) = a
k
n
t
+ a
k-1
n
k-1
+ · · · , a
i
n
i
, · · · + a
1
n + a
0
,
a
i
, k N
Da die Komplexität des Problems somit polynomiell in Abhängigkeit von der Problemgröße beschränkt
werden kann, werden Probleme der Klasse P als effizient lösbar betrachtet.
18
Die Klasse NP kann ähnlich definiert werden und umfasst alle Probleme, für welche ein nichtdeter-
ministischer Algorithmus existiert, welcher eine polynomiell beschränkte Laufzeit besitzt. Je nach Sicht-
weise ist ein nichtdeterministischer Algorithmus entweder im Besitz der Fähigkeit, die richtigen Berech-
nungsschritte zu erraten oder sämtliche bis zu 2
p(n)
Rechenwege in maximal p(n) atomaren Schritten zu
enumerieren. Aufgrund dessen ist der nichtdeterministische Algorithmus praktisch nicht realisierbar,
sondern ausschließlich ein abstraktes Konstrukt der theoretischen Informatik.
19
Für die Komplexitäts-
klassen P und NP gilt folglich die Teilmengenbeziehung P NP, wobei die Frage nach der Echtheit der
Teilmengenbeziehung ein ungelöstes Problem der Mathematik darstellt.
20
Probleme, die in der Klasse
NP liegen und für welche nicht bekannt ist, ob sie gleichzeitig in P liegen, werden als nicht effizient
lösbar eingestuft, da bisher kein Algorithmus gefunden wurde, der das Problem sicher in polynomieller
Zeit lösen kann. Für diese Probleme sind bisher nur Algorithmen bekannt, die eine exponentielle oder
höhere Anzahl von Operationen ausführen müssen, um das Problem zu lösen.
21
2.2.3
Problemrelationen und polynomielle Reduktion
Unter der Annahme, C sei eine Komplexitätsklasse, heißt ein Problem A genau dann C-schwierig, wenn A
mindestens genauso schwierig zu lösen ist, wie jedes andere Problem B C. Die Komplexitätsklasse C
wird dabei durch die schwierigsten Probleme in C repräsentiert. A heißt C-vollständig, wenn A einerseits
C-schwierig ist und andererseits zur Komplexitätsklasse C gehört. Kann für ein Problem A nachgewiesen
werden, dass es mindestens genauso schwierig wie ein C-vollständiges Problem ist, impliziert dies, dass
A
die Eigenschaft der C-Schwierigkeit besitzt. Wird zusätzlich nachgewiesen, dass A C gilt, folgt
daraus, dass A die Eigenschaft der C-Vollständigkeit besitzt.
22
Der Nachweis, dass ein Problem A mindestens genauso schwierig wie ein Problem B ist, erfolgt im
Allgemeinen über die polynomielle Reduktion. Ein Problem B wird auf ein Problem A reduziert, indem
die Eingaben von B mit Hilfe einer Funktion in Eingaben von A transformiert werden. Alle Problem-
instanzen von B können demnach durch diese Transformation als Probleminstanzen von A abgebildet
werden. Stellt eine polynomiell berechenbare Funktion dar, ist B polynomiell auf A reduzierbar und
folglich A mindestens genauso schwierig wie B.
23
Daraus folgt, dass ein Problem NP-vollständig ist,
wenn es auf ein anderes NP-vollständiges Problem reduziert werden kann und Element der Klasse NP
ist.
Den ersten Beweis zur NP-Vollständigkeit eines Problems erbrachte der Begründer der NP-Vollstän-
digkeitstheorie S
TEPHEN
C
OOK
im Jahre 1971 für das Erfüllbarkeitsproblem (SAT).
24
Der Nachweis der
17
Wobei auch logarithmische Komplexitätsmaße aufgrund von log n n als klassenzugehörig betrachtet werden. Vgl. [Sch01,
S. 152f.].
18
Dabei sollte jedoch auch beachtet werden, dass nach dieser Definition die Komplexität O n
100
oder größer ebenfalls poly-
nomieller Natur ist, jedoch kaum als effizient lösbar betrachtet werden kann. Vgl. [Grö05, S. 264].
19
Vgl. [Weg03, S. 44f.].
20
Die Antwort auf die Frage, ob P NP und somit P = NP oder P = NP gilt, zählt zu den 7 wichtigsten ungelösten Problemen
der Mathematik, auf dessen Lösung ein Preisgeld von 1 Mio. $ ausgesetzt wurde. Vgl. [Grö05, S. 268].
21
Vgl. [Sch01, S. 153ff.].
22
Vgl. [Weg03, S. 71].
23
Vgl. [Weg03, S. 65f.].
24
Vgl. Beweis in [Coo71].
6
2.3 Diskrete und kombinatorische Optimierung
NP-Vollständigkeit aller übrigen Probleme kann, vorausgesetzt das Problem gehört zur Klasse NP, über
die polynomielle Reduktion auf SAT oder ein anderes NP-vollständiges Problem erbracht werden.
25
2.3
Diskrete und kombinatorische Optimierung
Gegenstand dieser Arbeit ist die Analyse und die exakte sowie näherungsweise Lösung eines Problems
aus der Klasse der kombinatorischen Optimierung. Aus diesem Grund und zur Begriffsabgrenzung soll
diese Problemklasse im Folgenden kurz vorgestellt werden.
2.3.1
Problemdefinition und Eigenschaften
Bei näherer Betrachtung der Strukturen von Entscheidungsmodellen stellt die diskrete Optimierung ne-
ben der stetigen Optimierung, in der sämtliche Entscheidungsvariablen durch reelle Zahlen repräsentiert
werden, und der dynamischen Optimierung, in welcher Zeitfunktionen oder Folgen von Entscheidungen
betrachtet werden, einen dritten wesentlichen Typ von Optimierungsmodellen dar.
26
Diskrete Optimierungsmodelle zeichnen sich durch die Eigenschaft aus, entweder über eine end-
lich große oder zumindest abzählbar unendlich große Entscheidungsmenge zulässiger Alternativen zu
verfügen.
27
Aufgrund dessen besteht die Möglichkeit, jeder Entscheidungsalternative eine natürliche Zahl zu-
zuordnen, wobei die resultierende Entscheidungsmenge U zumeist als Menge von binären Vektoren
U {0, 1}
n
oder als Menge von Vektoren aus natürlichen Zahlen U N
n
gegeben ist. Daher werden
diskrete Optimierungsmodelle in der Literatur auch oft als ganzzahlige Modelle bezeichnet. Ein weite-
res Synonym stellt der Begriff der kombinatorischen Optimierung dar, welcher darauf zurückzuführen ist,
dass die Ableitung der Größe der Lösungsmenge häufig durch einfache kombinatorische Überlegungen
aus den Eingabeparametern des Problems möglich ist. Alternativ kann die Menge U jedoch auch durch
ein graphentheoretisches Problem definiert werden.
28
Unter der Annahme, U sei eine endliche oder abzählbar unendlich große Menge, kann ein diskretes
Optimierungsproblem durch eine Zielfunktion F : U - R wie nach Gleichung 2.3 definiert werden.
29
F (u) max!
bzw. min!
u U
(2.3)
Da für viele ganzzahlige beziehungsweise diskrete Optimierungsprobleme exakte Methoden auf-
grund der Komplexität des Problems einen zu hohen Rechenaufwand benötigen, werden oft Heuristi-
ken zur Approximation der Lösung eingesetzt.
30
2.3.2
Ausgewählte Optimierungsprobleme
Nachfolgend werden einige ausgewählte und für diese Arbeit relevante kombinatorische Probleme vor-
gestellt. Insbesondere das Rucksackproblem und das Travelling Salesman Problem sowie das Kürzeste-
Wege-Problem sind bekannte Vertreter der diskreten Optimierung.
2.3.2.1
Das Rucksackproblem
Einem Reisenden stehe ein Rucksack zur Verfügung, welcher ein Maximalgewicht k aufnehmen kann.
Des Weiteren existieren n verschiedene Gegenstände j {1 . . . n}, welchen jeweils ein Wert p
j
und ein
25
Vgl. [Weg03, S. 82].
26
Vgl. [Kis03, S. 4ff.].
27
Vgl. u.a. [Tei02, S. 319], [Bom93, S. 431], [Kis03, S. 6].
28
Vgl. [Bom93, S. 431], [Kis03, S. 6].
29
Vgl. [Bom93, S. 432].
30
Vgl. [Kis03, S. 6ff.].
7
KAPITEL 2. THEORETISCHE GRUNDLAGEN
Gewicht w
j
zugeordnet ist. Das daraus resultierende Optimierungsproblem ergibt sich aus der Frage,
welche Gegenstände in den Rucksack eingepackt werden sollen, um den Wert des Inhaltes zu maxi-
mieren, ohne jedoch dabei die zulässige Gewichtsschranke k zu überschreiten.
31
Formal kann dieses
Problem wie folgt definiert werden.
n
j=1
p
j
u
j
max!
(2.4)
Hierbei gilt als Nebenbedingung die folgende Kapazitätsrestriktion
n
j=1
w
j
u
j
k
(2.5)
mit u
j
{0, 1} und j {1 . . . n}. Die Entscheidungsvariable u
j
nimmt den Wert 1 an, falls der Ge-
genstand j eingepackt werden soll beziehungsweise 0, falls der Gegenstand j nicht eingepackt werden
soll.
In [Kel04] wird durch die Reduktion des NP-vollständigen Subset Sum Problems auf das Rucksack-
problem (auch knapsack problem) gezeigt, dass auch dieses zur Klasse der NP-vollständigen Probleme
gehört.
32
Equality Knapsack ist eine Variante des Grundproblems, bei welchem anstatt der normalen Kapazi-
tätsrestriktion, die forderte, dass das Gewicht nicht größer als die vorhandene Kapazität sein darf, die
genaue Gleichheit zwischen Kapazität und des Gesamtgewichts aller eingepackten Gegenstände be-
dingt.
33
Formal kann diese Restriktion demnach in der Form
n
j=1
w
j
u
j
= k
(2.6)
definiert werden. Diese Variante ist aufgrund der NP-Vollständigkeit des Subset Sum Problems ebenso
wie die Basisvariante NP-vollständig.
34
2.3.2.2
Travelling Salesman Problem
Das NP-vollständige Rundreiseproblem stellt einen Reisenden oder Verkäufer vor die Aufgabe, eine
kürzeste Rundreise zwischen n Städten zu finden, ohne dabei eine Stadt mit Ausnahme jener, in welcher
die Rundreise beginnt, mehr als ein Mal zu besuchen.
35
Formal kann das Problem durch einen unge-
richteten, vollständigen und gewichteten Graphen beschrieben werden, in welchem ein so genannter
Hamiltonkreis
36
kürzester Länge bezüglich der Kantengewichte gesucht wird.
37
Zur formalen Beschreibung des Problems wird die Entscheidungsmatrix U der Größe n × n mit den
Elementen u
ij
{0, 1} mit i, j = 1, ..., n definiert, wobei U eine Rundreise und somit eine Lösung des
Problems repräsentiert. Die Elemente u
ij
U ergeben sich nach Gleichung 2.7.
38
u
ij
1
wenn die Kante e
ij
Bestandteil der Rundreise ist
0
sonst
(2.7)
31
Vgl.[Weg03, S. 17].
32
Vgl. [Kel04, S. 491].
33
Vgl. [Kel04, S. 413f.].
34
Vgl. [Kel04, S. 487ff.].
35
Vgl. [Hop00, S. 373], [Wag03, S. 90f.].
36
Ein Hamiltonkreis ist ein Kreis durch den Graphen, welcher alle Knoten des Graphen enthält. Vgl. Abschnitt 2.1.2 i.V.m.
[Die00, S. 211].
37
Vgl. [Hop00, S. 373], [Rei90, S. 247f.] sowie [Sch01, S. 165].
38
Die nachfolgenden formalen Beschreibungen entstammen [Kal97, S. 214f.].
8
2.3 Diskrete und kombinatorische Optimierung
Um sicherzustellen, dass U einen Hamiltonkreis beschreibt, gelten die folgenden Gleichungen 2.8
und 2.9 als durch die Entscheidungsmatrix U zu erfüllende Restriktionen.
n
j=1
u
ij
= 1
für i {1, 2, ..., n} , i = j
(2.8)
n
i=1
u
ij
= 1
für j {1, 2, ..., n} , i = j
(2.9)
Unter der Annahme, dass die Kantengewichte durch die Variable c
ij
beschrieben werden, kann auf
Basis der dargelegten Problemdefinition das Ziel der Optimierung wie folgt formuliert werden.
n
i=1
n
j=1
u
ij
· c
ij
min!
mit i = j
(2.10)
Das Travelling Salesman Problem ist eines der schwierigsten algorithmischen Probleme. Die NP-
Vollständigkeit dieses Problems kann durch die Technik der Reduktion auf andere NP-vollständige
Probleme bewiesen werden.
39
2.3.2.3
Kürzeste Wege durch Graphen
Eng verwandt mit dem Rundreiseproblem ist das Kürzeste-Wege-Problem. Entgegen dem Rundreise-
problem wird jedoch nicht nach einer Rundreise durch alle Städte (Knoten) eines Graphen, sondern
nach dem kürzesten Weg zwischen einem als Startpunkt und einem als Endpunkt definierten Knoten
des Graphen gesucht.
40
v
1
v
2
v
5
2
2
5
v
8
v
10
v
9
v
6
v
4
v
3
v
7
8
6
7
6
9
8
4
4
3
3
6
3
2
Abbildung 2.1: Beispielhaftes Kürzeste-Wege-Problem
Die Abbildung zeigt einen unvollständigen, ungerichteten, gewichteten Graph, in welchem der kür-
zeste Weg zwischen den Knoten v
1
und v
2
bestimmt und markiert wurde.
Dieses Problem ist jedoch, anders als TSP, effizient lösbar. D
IJKSTRA
entwickelte einen Algorithmus,
welcher das Problem mit einem Komplexitätsbedarf von O n
2
löst.
41
Der Algorithmus von F
LOYD
und
W
ARSHALL
bestimmt sogar sämtliche kürzeste Wege zwischen allen Knoten mit einer Komplexität von
O n
3
.
42
Das Problem ist demnach Element der Komplexitätsklasse P.
39
Vgl. [Wag03, S. 117], [Sch01, S. 163., S. 178f.].
40
Vgl. [Wag03, S. 117].
41
Vgl. [Dij59].
42
Vgl. [Wag03, S. 117] sowie [Flo62] und [War62].
9
KAPITEL 2. THEORETISCHE GRUNDLAGEN
10
Kapitel 3
Optimierung bei Mehrfachzielsetzung
Mehrkriterielle Probleme beschreiben die Realität meist deutlich besser als Probleme, welche das Opti-
mierungsziel ausschließlich durch eine zu minimierende Kosten- oder zu maximierende Gewinnfunk-
tion definieren. In so genannten real world problems müssen sehr oft Entscheidungen unter teilweise sehr
vielen Gesichtspunkten, mit Hilfe so genannter Kriterienbündel, getroffen werden. Neben quantifizier-
baren Größen wie Kosten, Gewinn oder Kapitalbindung sind häufig auch Ziele von Bedeutung, die nur
qualitativ artikulierbar sind. So sind beispielsweise soziale oder ökologische Aspekte nicht zu vernach-
lässigen.
1
Zahlreiche Anwendungen zur Behandlung spezieller mehrkriterieller Probleme zeigen die
Wichtigkeit dieser Thematik in der Praxis auf.
2
Ein gutes Beispiel für mehrkriterielle Probleme (mit konfliktären Zielen) stellt die Reihenfolge- be-
ziehungsweise Ablaufplanung in der betrieblichen Produktion dar, in welcher aufgrund von Bewer-
tungsproblemen eine Reduktion der Kosten- auf Zeitziele stattfindet. Ziele in der Reihenfolgeplanung
sind neben anderen die gleichzeitige Maximierung der Kapazitätsauslastung und die Minimierung der
Durchlaufzeit.
3
Weitere Ziele können beispielsweise die Vermeidung von Überstunden oder die Mini-
mierung von Terminüberschreitungskosten sein.
Da auch das im Rahmen dieser Arbeit betrachtete Optimierungsproblem zur Auswahl von Kom-
petenzzellenangeboten aus einem Angebotsnetz einer Mehrfachzielsetzung unterliegt, soll nachfolgend
eine Einführung in die multikriterielle Entscheidung und Optimierung stattfinden.
4
3.1
Mehrkriterielle Probleme
Die Definition aus Abschnitt 2.3 auf Seite 7 betrachtete ausschließlich unikriterielle Probleme (SOP
5
).
Nachfolgend soll zunächst eine formale Definition von Problemen mit mehrfacher Zielsetzung erfol-
gen. Anschließend soll auf mögliche Abhängigkeiten und Beziehungen zwischen den Zielen näher ein-
gegangen werden.
3.1.1
Problemstellung
Ein mehrkriterielles Optimierungsproblem (MOP
6
) kann als Erweiterung eines unikriteriellen Optimie-
rungsproblems definiert werden. Während in einem einkriteriellen Optimierungsproblem stets genau
1
Vgl. ähnliche Darstellungen in [Zim91, S. V], [Rot98, S. 17], [Zim91, S. V] und [Kam06, S. 20].
2
Eine gute Übersicht findet sich beispielsweise in [Bam96, S. 43].
3
Diese Problematik wird auch als Dilemma der Ablaufplanung bezeichnet. Vgl. [Käs04, S. 174].
4
Vgl. Kapitel 4.
5
Abkürzung für die engl. Bezeichnung »Single Objective Problem«.
6
Abkürzung für die engl. Bezeichnung »Multi Objective Problem«.
11
KAPITEL 3. OPTIMIERUNG BEI MEHRFACHZIELSETZUNG
eine zu minimierende oder zu maximierende Zielfunktion das Ziel des Problems beschreibt, existieren
im multikriteriellen Fall mehrere solcher Funktionen, welche jeweils ein separates Ziel repräsentieren.
Formal beschrieben sei M ein mehrkriterielles Optimierungsproblem mit Z verschiedenen Zielkri-
terien z {1, ..., Z} und den zugehörigen Zielfunktionen f
z
. Der Lösungsraum eines Problems M sei
durch das Symbol beschrieben. Die Zielfunktionen können formal wie folgt definiert werden.
f
z
: - R z = 1, ..., Z
Für repräsentiere f
z
()
den Zielfunktionswert des z-ten Optimierungskriteriums der Lösung
. In diesem Zusammenhang sei darauf hingewiesen, dass viele Verfahren fordern, dass alle Zielkrite-
rien entweder zu minimieren oder zu maximieren sind. Handelt es sich um ein Optimierungsproblem,
welches sowohl zu minimierende Zielfunktionen von Zielkriterien als auch zu maximierende enthält,
so müssen einige Zielfunktionen geeignet invertiert werden. Das Problem kann in der Form
Zielfunktion
y = F ()
=
f
1
()
f
2
()
..
.
f
z
()
..
.
f
Z
()
min! bzw. max!
Nebenbedingungen
()
= (
1
() ,
2
() , ...,
j
() , ...,
m
()) 0
(3.1)
abgebildet werden. Dabei wird als Entscheidungsvektor oder Lösung des Problems und als
Entscheidungs- oder Lösungsraum bezeichnet. Der Vektor y Y wird Zielvektor und Y Zielraum ge-
nannt. Die Nebenbedingungen bestimmen die Teilmenge des Lösungsraums, die zulässig respektive
gültig ist.
7
Diese Abbildung entspricht der Form eines Vektoroptimierungsproblems.
8
3.1.2
Zielbeziehungen
Existieren für ein Optimierungsproblem mehrere Ziele, so können diese in unabhängiger (auch neutraler),
komplementärer oder konkurrierender (auch konträrer) Beziehung zueinander stehen. Diese Zielbeziehun-
gen sollen nachfolgend näher betrachtet werden.
Stehen zwei Ziele in komplementärer Beziehung, so bewirkt eine Verbesserung des Zielfunktions-
wertes einer zugehörigen Zielfunktion ebenso eine Verbesserung des Zielfunktionswertes der Zielfunk-
tion des anderen Ziels. Analog würde eine Verschlechterung eines Zielfunktionswertes einer Funktion
genauso zu einer Verschlechterung der anderen Zielfunktion führen. Ist die Beziehung zweier Ziele kon-
kurrierend, stehen diese Ziele im Konflikt. Dies bedeutet, dass eine Verbesserung des Zielerreichungs-
grades von einem der Ziele zu einer Verschlechterung der Zielerreichung des anderen Ziels führen
würde. In einer neutralen, auch als indifferent bezeichneten Beziehung, kann keine Konkurrenz oder
Komplementarität zwischen den Zielen nachgewiesen werden.
9
Aufgrund dieser Zusammenhänge können Schlussfolgerungen über den Lösungsraum des zugrun-
de liegenden Optimierungsproblems gezogen werden. Stehen alle Ziele eines Optimierungsproblems
in komplementärer Beziehung, so existiert mindestens genau eine Lösung, welche für jedes Ziel den
optimalen Zielfunktionswert besitzt. Eine Lösung, die diese Eigenschaft aufweist, wird als perfekte Lö-
7
Vgl. [Tei01, S. 315f.].
8
Vgl. [Kle02, S. 372].
9
Vgl. [Bam96, S. 46f.], [Käs04, S. 173f.].
12
3.2 Optimalität bei mehrfacher Zielsetzung
sung bezeichnet.
10
Besteht zwischen allen Zielen eine symmetrische Komplementarität aller Ziele, kann
ein multikriterielles Optimierungsproblem auf ein einkriterielles Optimierungsproblem reduziert wer-
den.
11
Stehen hingegen mindestens zwei Ziele in Konflikt, enthält keine Lösung , die für alle Ziele
des Optimierungsproblems ein Optimum darstellt.
12
In diesem Falle kann, ebenso wie bei neutraler
Zielbeziehung, eine Reduktion eines MOP auf ein SOP nicht ohne weiteres durchgeführt werden. Aus
diesem Grund wird nachfolgend der Begriff der Optimalität bei mehrfacher Zielsetzung geklärt.
3.2
Optimalität bei mehrfacher Zielsetzung
Das Paretokriterium geht auf den Ökonomen V
ILFREDO
P
ARETO
(1848-1923) zurück und beschreibt
ein volkswirtschaftliches Konzept, das die Effizienz einer Allokation von Gütern in einer Gesellschaft
definiert. Eine Allokation gilt genau dann als effizient, wenn es durch eine Umverteilung von Gütern
auf Konsumenten nicht möglich ist, ein beliebiges Wirtschaftssubjekt besser zu stellen, ohne gleichzei-
tig mindestens ein anderes Wirtschaftssubjekt schlechter zu stellen. Ein solcher Zustand wird als effi-
ziente beziehungsweise paretooptimale Allokation bezeichnet.
13
Ausgehend von einer Gesamtmenge
an Gütern können sehr viele paretooptimale Zustände existieren, welche durch eine unterschiedliche
Verteilung der Güter auf einzelne Wirtschaftssubjekte erreichbar sind. Mit dem Paretokriterium kann
demnach keine Aussage über Fairness oder Gerechtigkeit bei der Verteilung von Gütern abgeleitet wer-
den. Welcher spezielle paretooptimale Zustand hinsichtlich einer Allokation anstrebenswert ist, obliegt
den wirtschafts- und sozialpolitischen Intentionen der zugrunde liegenden Gesellschaft.
14
Dieser volkswirtschaftliche Ansatz ist auf die Lösung multikriterieller Optimierungsprobleme über-
tragbar, wenn die Wirtschaftssubjekte den Zielkriterien und die zu verteilenden Güter den Zielerrei-
chungsgraden dieser Zielkriterien entsprechen. In diesem Zusammenhang sollen zunächst die Begriffe
der starken und schwachen Dominanz von Lösungen definiert werden, um das Konzept der Paretoop-
timalität in multikriteriellen Optimierungsproblemen zu konkretisieren.
3.2.1
Paretooptimalität
Um eine Beziehung zwischen Lösungen eines Optimierungsproblems darzustellen, werden die Begriffe
der starken und schwachen Dominanz verwendet, welche im Folgenden definiert werden.
Seien
1
und
2
gültige Lösungen des bereits in Abschnitt 3.1.1 definierten und zu minimierenden
Optimierungsproblems M . Gilt der nachfolgende Zusammenhang zwischen den Zielfunktionswerten
der Lösungen
1
und
2
, so wird die Lösung
2
von der Lösung
1
stark dominiert.
f
z
(
1
) < f
z
(
2
)
z {1, . . . , Z}
(3.2)
Dies bedeutet, dass die Kosten- beziehungsweise Zielfunktionswerte der Lösung
1
für jedes Zielkri-
terium kleiner (besser) sind als die der Lösung
2
. Eine starke Dominanz der Lösung
1
gegenüber
2
sei durch die Schreibweise
1
2
gekennzeichnet. Handelt es sich hingegen nur um eine schwache
Dominanz der Lösung
1
gegenüber
2
müssen nur die Bedingungen
f
z
(
1
)
f
z
(
2
)
z {1, . . . , Z}
f
z
(
1
)
<
f
z
(
2
)
z {1, . . . , Z}
(3.3)
10
Vgl. [Dom91, S. 45].
11
Symmetrische Komplementarität beschreibt eine wechselseitige Komplementarität zwischen mehreren Zielen. Vgl. [Bam96,
S. 47].
12
Vgl. [Dom91, S. 45].
13
Vgl. [Han02, S. 50].
14
Vgl. [Han02, S. 79].
13
KAPITEL 3. OPTIMIERUNG BEI MEHRFACHZIELSETZUNG
erfüllt sein, was bedeutet, dass sämtliche Zielfunktionswerte der Zielkriterien der Lösung
1
nicht klei-
ner (schlechter) als die der Lösung
2
sein dürfen, jedoch mindestens ein Zielfunktionswert im Vergleich
zu
2
tatsächlich kleiner (besser) sein muss.
15
Die schwache Dominanz einer Lösung
1
gegenüber
2
sei durch die Schreibweise
1
2
dargestellt. Durch die strengere Restriktion der starken Dominanz
ergibt es sich, dass jede starke Dominanz auch eine schwache Dominanz ist.
Formal kann die Paretooptimalität einer Lösung
durch die Eigenschaft definiert werden, dass
keine Lösung mit =
und
existiert. Wird demnach eine Lösung
von keiner anderen
Lösung des Optimierungsproblems schwach oder stark dominiert, heißt diese Lösung paretooptimal.
16
Wird ein Algorithmus zur Lösung des Optimierungsproblems in der Form modelliert, dass durch
ihn alle Lösungen ausgeschlossen werden, die durch eine andere Lösung in mindestens schwach do-
miniert werden, ermittelt dieser sämtliche paretooptimalen Lösungen. Die Menge aller paretooptimalen
Lösungen
konstruiert im Zielraum des Problems die so genannte Paretofront Y
.
17
3.2.2
Eigenschaften der paretooptimalen Lösungsmenge
Aus den Definitionen der Dominanz und der Eigenschaft der Paretooptimalität kann abgeleitet werden,
dass, falls die Menge aller paretooptimalen Lösungen eine Lösung enthält, welche über die Eigenschaft
der schwachen oder starken Dominanz gegenüber allen übrigen Lösungen verfügt, diese die einzige
Lösung in dieser Menge ist, da sie von keiner anderen Lösung dominiert werden kann. Gemäß der
Definition ist diese Lösung perfekt. Perfekte Lösungen sind somit ein Spezialfall der Paretooptimalität.
Unabhängig von den Zielbeziehungen können folgende Aussagen über die paretooptimale Lösungs-
menge eines multikriteriellen Optimierungsproblems getroffen werden. Einerseits kann die Menge der
paretooptimalen Lösungen genau dann nicht leer sein, wenn der Lösungsraum des Optimierungspro-
blems keine leere Menge bildet. Andererseits ergibt sich, dass die Menge der paretooptimalen Lösungen
gleich der Menge aller Lösungen ist, falls keine Lösung im Lösungsraum existiert, welche eine an-
dere Lösung zumindest schwach dominiert. Somit gilt die nachfolgende Teilmengenbeziehung.
(3.4)
Die Anzahl der paretooptimalen Lösungen kann somit nicht stärker als durch den Lösungsraum
begrenzt werden. Insbesondere bei Problemen, deren Lösungsraum exponentiell im Vergleich zur Ein-
gabegröße einer Probleminstanz wächst, kann die Enumeration aller Lösungen der Front ein nicht zu
vernachlässigendes Speicherproblem darstellen.
3.2.3
Idealpunkte und Nadir-Punkt der Front
Aufgrund der Relevanz in späteren Abschnitten und Kapiteln soll nachfolgend auf spezielle Punkte
respektive Vektoren im Zielraum, welche diesen oder die Paretofront beschränken, näher eingegangen
werden.
18
Der positive Idealpunkt, auch ideal point oder utopia point genannt, stellt einen Vektor y
+
im Z-
dimensionalen Raum dar, dessen Elemente y
+
z
den jeweiligen optimalen Zielerreichungsgrad eines Ziel-
kriteriums z beinhalten. Der Wert y
+
z
stellt den Optimalwert dar, welcher durch eine einkriterielle Opti-
mierung für das Kriterium z ermittelt werden würde. Unter der Annahme, dass alle Zielfunktionen zu
minimieren sind, kann dieser Punkt y
+
wie folgt formal definiert werden.
19
15
Vgl. [Mer02, S. 113] und [Mie99, S. 10ff.].
16
Vgl. [Mer02, S. 113] und [Mie99, S. 10ff.].
17
Vgl. [Mer02, S. 113].
18
Dieses Konstrukt wird beispielsweise im Compromise Programming (Abschnitt 3.4.6) benötigt. Auch die in Kapitel 7 entwi-
ckelten hybriden Methoden greifen teilweise auf diese Punkte zurück.
19
Vgl. [Ehr05, S. 34], [Mie99, S. 15f.].
14
3.3 Multikriterielle kombinatorische Optimierung
y
+
=
y
+
z
..
.
y
+
z
..
.
y
+
Z
mit y
+
z
= min
f
z
()
(3.5)
Der positive Idealpunkt existiert als Zielfunktionsvektor nur dann als zulässige Lösung, wenn ein Pro-
blem eine perfekte Lösung besitzt und ist bei allen übrigen Problemen nicht erreichbar.
20
Der negative Idealpunkt, auch negative ideal point oder anti-ideal point genannt, entspricht dem ge-
nauen Gegenteil und beschreibt einen Vektor y
-
, dessen Elemente y
-
z
den jeweiligen pessimalen Zieler-
reichungsgrad für das Kriterium z beinhalten. Dieser Wert könnte durch eine einkriterielle Optimierung
für das Kriterium z ermittelt werden, wenn das Ziel der Optimierung umgekehrt wird.
21
Formal ist der
Punkt y
-
wie folgt definiert.
y
-
=
y
-
z
..
.
y
-
z
..
.
y
-
Z
mit y
-
z
= max
f
z
()
(3.6)
Der negative Idealpunkt beschreibt somit das inverse Konzept des positiven Idealpunktes und be-
schränkt den Zielraum als untere Grenze. Es kann keine zulässige Lösung geben, welche von y
-
do-
miniert wird.
22
Zusätzlich ergibt sich aus dem positiven Idealpunkt der so genannte nadir point (dt. Fußpunkt). Die-
ser Nadir-Punkt y
N
ergibt sich aufgrund des Dominanzkonzeptes nach dem Paretokriterium und stellt
eine untere Beschränkung der Paretofront dar. Formal ergibt sich der Punkt nach folgender Gleichung,
wobei
die Menge der paretooptimalen Lösungen darstelle.
y
N
=
y
N
z
..
.
y
N
z
..
.
y
N
Z
mit y
N
z
= max
f
z
()
(3.7)
Der Nadir-Punkt beschreibt als Fußpunkt der Paretofront deren untere Begrenzung, wobei definitions-
gemäß keine paretooptimale Lösung
existieren kann, für welche F (
)
y
N
gilt.
23
3.3
Multikriterielle kombinatorische Optimierung
Da ausschließlich kombinatorische Optimierungsprobleme Gegenstand dieser Arbeit sind, soll die mul-
tikriterielle Optimierung im Folgenden aus deren Perspektive näher betrachtet werden. In diesem Zu-
sammenhang werden zunächst verschiedene Problemlösungsansätze und -klassen der Entscheidungs-
theorie vorgestellt und eine mögliche Einordnung kombinatorischer Probleme vorgenommen. Anschlie-
ßend werden grundsätzliche Vorgehensweisen für die mehrkriterielle kombinatorische Optimierung er-
örtert.
20
Vgl. [Ehr05, S. 34], [Mie99, S. 15f.] i.V.m. [Dom91, S. 45].
21
Vgl. [Han98, S. 20].
22
Vgl. [Han98, S. 20], angepasst für ein Minimierungsproblem.
23
Vgl. [Mie99, S. 16f.], [Yoo95, S. 38].
15
KAPITEL 3. OPTIMIERUNG BEI MEHRFACHZIELSETZUNG
3.3.1
Klassifizierung entscheidungstheoretischer Ansätze
Die Reihe der multikriteriellen Entscheidungsverfahren ist sehr groß, weshalb zunächst eine Klassifizie-
rung der verfügbaren Methoden erfolgen soll. Da sich in der Literatur keine einheitliche Klassifizierung
findet, sollen verschiedene Klassifizierungsmodelle nachvollzogen werden.
3.3.1.1
Multiattributive und multiobjektive Verfahren
Klassische multikriterielle Entscheidungsmodelle können unter dem Begriff Multi Criteria Decision Ma-
king zusammengefasst werden. Diese werden nach H
WANG
und Y
OON
in Multi Objective Decision Ma-
king (MODM) und Multi Attribute Decision Making (MADM) unterschieden.
24
Wesentliche Unterschiede
zwischen den Klassen finden sich einerseits in der Problemstruktur und andererseits in der Art der
Problemlösung. W
EBER
beschreibt den Unterschied zwischen diesen Gruppen wie folgt.
»Multiobjektive Methoden dienen zur Erarbeitung von Lösungen für Probleme mit meh-
reren, teilweise konfliktären, jedenfalls aber quantifizierbaren Zielen, die unter Einhaltung
vorgegebener Restriktionen bestmöglich zu erreichen sind. [...] Die multiattributiven Metho-
den (multiattributive methods) sind dagegen primär auf eine im voraus begrenzt festgelegte
Zahl von Attributen und deren vergleichsweise Gewichtung im Hinblick auf eine - eventuell
nur implizit erkennbare - Zielvorgabe ausgerichtet.«
25
Methoden der Gruppe MADM fordern demnach die explizite Vorgabe einer endlichen Alternativen-
menge, welche in den meisten Fällen sehr klein ist. Eine Besonderheit dieser Methoden ergibt sich auf-
grund der Eigenschaft, dass eine Ziel- beziehungsweise Attributerfüllung auf einem ordinalen Skalenni-
veau zumeist ausreichend ist. Die Problemlösung durch eine MADM-Methode besteht folglich aus der
Auswahl einer Alternative.
26
Hauptvertreter dieser Gruppe stellen Verfahren wie die Nutzwertanalyse,
AHP und die Methode der gewichteten Summierung dar.
27
Für MODM-Methoden ist die implizite Vor-
gabe der Alternativenmengen durch ein mathematisches Modell hinreichend. Die Alternativenmenge
ist in der Regel unendlich groß, wobei die Zielerfüllungsgrade der Alternativen über quantifizierba-
re Zielfunktionen beschrieben werden. Der Lösungsraum ist stetig und die Problemlösung durch ein
zur Gruppe gehöriges Verfahren erfolgt über die Berechnung einer Alternative.
28
Hauptvertreter dieser
Klasse sind abstandsorientierte Verfahren wie das Goal Programming und das Compromise Program-
ming.
29
In Abbildung 3.1
30
wird ein Überblick über diese beiden Schulen von Entscheidungsmodellen an-
hand einer Gegenüberstellung wesentlicher Unterschiede dargestellt. In diesem Zusammenhang sei er-
wähnt, dass fast alle Verfahren der Gruppe MODM - insbesondere abstandsorientierte Verfahren - auch
in Verbindung mit diskreten Lösungsräumen einsetzbar sind. Beispiele hierfür sind das Goal bezie-
hungsweise Compromise Programming oder das TOPSIS-Verfahren.
31
Es ist des Weiteren bei Verfahren
der Klasse MADM möglich, diese mit quantifizierbaren Zielerfüllungen zu nutzen.
3.3.1.2
Einordnung der kombinatorischen Optimierung
Nachfolgend soll, soweit dies möglich ist, eine Zuordnung der kombinatorischen Optimierung zu den
bereits im vorigen Abschnitt vorgestellten Modellklassen MODM und MADM erfolgen.
24
Vgl. [Hwa81, S. 2f.] sowie [Ruh04, S. 10] und [Zim91, S. 25]. Einen guten Überblick über Anwendungsmöglichkeiten und
Verfahren geben [Hwa79] für MODM und [Hwa81] für MADM.
25
[Web93, S. 11]
26
Vgl. [Zim91, S. 11 i..V.m. S. 25].
27
Vgl. [Ant94, S. 14] i.V.m. [Ruh04, S. 10].
28
Vgl. [Zim91, S. 25].
29
Vgl. [Web93, S. 15], [Zel73].
30
Angelehnt an [Ant94, S. 13].
31
Vgl. [Ruh04, S. 10f.].
16
3.3 Multikriterielle kombinatorische Optimierung
MCDM
Multi Criteria Decision Making
MADM
Multi Attribute Decision Making
Entscheidungsalternativen
explizit vorgegeben
Attributerfüllung
nicht quantifizierbar
Alternativenanzahl ist eine
endliche Menge
Auswahl anhand
interattributiver Vergleiche
MODM
Multi Objective Decision Making
Entscheidungsalternativen
nur implizit vorgegeben
Zielerfüllung
quantifizierbar
Unendliche Anzahl von Alter-
nativen (Lösungsraum stetig)
Funktionale Beziehung zwischen
Alternativen und Kriterien darstellbar
Kombina-
torisches
Multikriterielles
Optimierungs-
problem
Abbildung 3.1: Vergleich von MODM und MADM sowie der kombinatorischen Optimierung
Die Abbildung zeigt eine vergleichende Gegenüberstellung der Eigenschaften von MODM und MA-
DM als MCDM-Methoden. Des Weiteren wird eine Einordnung der mehrkriteriellen kombinatorischen
Optimierung bezüglich dieser Eigenschaften vorgenommen.
Im Rahmen dieser Arbeit wird davon ausgegangen, dass die Zielerfüllung bei kombinatorischen
Problemen auf einem hohen Skalenniveau quantifizierbar ist. Für jedes Ziel können demnach anhand
von Vergleichen der Zielfunktionswerte die Verhältnisse zwischen den Zielerreichungsgraden mehrerer
Lösungen dargestellt werden.
Die prinzipielle, praktisch allerdings kaum umsetzbare Möglichkeit, eine vollständige Enumeration
für ein diskretes Problem durchzuführen, führt einerseits zu der Eigenschaft des Lösungsraums, dass
nur eine endliche Anzahl von Alternativen existiert, verbietet jedoch andererseits hinsichtlich der Art
der Alternativenvorgabe eine Einordnung in die Gruppe der multiattributiven Methoden, da prohibitiv
viele Alternativen existieren können. Daher sollte eine Einordnung bei der nur impliziten Vorgabe der
Alternativen erfolgen, welche aus der Definition des Problems und den konkreten Informationen der
Probleminstanz folgt. Folglich ist nicht die Auswahl, sondern die Berechnung beziehungsweise Suche
einer Alternative Ziel des Verfahrens. Da kein direkter Vergleich aller Alternativen mit dem Ziel, eine
dieser Alternativen auszuwählen, vorgenommen werden kann, verbietet sich damit die Anwendung
17
KAPITEL 3. OPTIMIERUNG BEI MEHRFACHZIELSETZUNG
von MADM-Methoden. Folglich erscheint eine Zuordnung zu multiobjektiven Methoden durchaus ge-
rechtfertigt.
Verfahren der Klasse MADM können trotzdem verwendet werden, um eine Auswahlentscheidung
für eine Alternative aus der paretooptimalen Lösungsmenge zu treffen oder um konkrete Alternativen
im direkten Vergleich zu bewerten.
3.3.1.3
Klassifizierung nach der Kompensation der Zielerfüllungsgrade
Eine weitere Klassifizierungsmöglichkeit ergibt sich durch die Trennung in kompensatorische und nicht-
kompensatorische multikriterielle Entscheidungsmethoden. Kompensatorische Methoden besitzen da-
bei die Eigenschaft, dass ein schlechter Zielerfüllungsgrad eines Ziels durch einen sehr guten Zielerfül-
lungsgrad eines anderen Ziels ausgeglichen respektive kompensiert werden kann. Nichtkompensatori-
sche Methoden besitzen diese Eigenschaft nicht.
32
Z1
0%
25%
50%
75%
100%
0%
25%
50%
75%
100%
Zielerreichung von Ziel 1
0%
25%
50%
75%
100%
0%
25%
50%
75%
100%
Indifferenzkurve mit
vollständiger Kompensation
Indifferenzkurve ohne
Kompensation
Zielerr
eichungvonZiel2
Zielerreichung von Ziel 1
Zielerr
eichungvonZiel2
Bewertung
(a)
(b)
Abbildung 3.2: Indifferenzkurven bei Verfahren mit und ohne Kompensation
Die Diagramme zeigen Indifferenzkurven für Verfahren mit und ohne Kompensationsmöglichkeiten
der Zielerreichung hinsichtlich der Bewertung von Alternativen bei Anwendung auf ein bikriterielles
Problem. Das linke Diagramm zeigt dabei ein Verfahren mit vollständiger Kompensation (Methode der
gewichteten Summe), während das rechte Diagramm ein Verfahren ohne Kompensation zeigt (Fuzzy
Decision Making).
Die Eigenschaft und der Grad der Kompensation kann durch Indifferenzkurven nachvollzogen und
sichtbar gemacht werden. Dabei liegen genau die alternativen Lösungen eines Problems auf einer ge-
meinsamen Indifferenzkurve, welche durch das Verfahren hinsichtlich der Zielerreichung gleich bewer-
tet werden.
33
Abbildung 3.2 zeigt unterschiedliche Indifferenzkurven für ein Verfahren mit und für ein
Verfahren ohne die beschriebene Eigenschaft der Kompensation.
34
32
Vgl. [Hwa81, S. 24f.], [Yoo95, S. 17].
33
Vgl. [Yoo95, S. 44].
34
Vgl. Methode der gewichteten Summe in Abschnitt 3.4.3 und Fuzzy Decision Making in Abschnitt 3.4.5.
18
3.3 Multikriterielle kombinatorische Optimierung
3.3.1.4
Klassifizierung nach der Integration des Entscheidungsträgers
Sowohl für klassische multiobjektive Methoden als auch für die nicht lineare multikriterielle Optimie-
rung kann alternativ eine Klassifizierung der Verfahren aufgrund der Art und Weise der Integration des
Entscheidungsträgers erfolgen. Dabei können die folgenden vier Klassen unterschieden werden.
35
1. A-priori-Methoden
2. A-posteriori-Methoden
3. Interaktive Verfahren
4. No-Preference-Verfahren
Methoden, bei denen bereits im Vorfeld des Optimierungsprozesses eine Artikulation der Präferenzen
des Entscheidungsträgers gefordert wird, werden unter dem Begriff A-priori-Methoden zusammenge-
fasst. Wird hingegen erst nach Durchführung des Such- beziehungsweise Berechnungsprozesses eine
Präferenzangabe des Entscheidungsträgers gefordert, handelt es sich um A-posteriori-Methoden. No-
Preference-Methoden verlangen keine Angabe der Präferenzen durch den Entscheidungsträger. Inter-
aktive Verfahren treten über den gesamten Optimierungsprozess in Interaktion mit dem Entscheidungs-
träger, wobei die Informationen über die Präferenzsituation progressiv artikuliert wird.
36
Nachfolgend sollen ausschließlich die beiden erstgenannten Methoden als alternative Modelle für
die kombinatorische Optimierung tiefgehender untersucht werden. Für interaktive Methoden soll kei-
ne weitere Betrachtung stattfinden, da diese Verfahren viel Zeit für die Kooperation mit dem Entschei-
dungsträger erfordern. In Verbindung mit der ebenfalls von einem hohen Zeitbedarf geprägten kombi-
natorischen Optimierung soll im Rahmen dieser Arbeit davon ausgegangen werden, dass sie kein sinn-
volles Vorgehensmodell bereitstellen können, welches innerhalb eines angemessenen Zeitrahmens be-
wältigt werden kann. Dem entgegen können mehrere Optimierungsläufe mit einem A-priori-Verfahren
aufgrund wiederholter Präferenzänderungen ebenfalls als progressives Verfahren verstanden werden.
37
No-Preference-Methoden stellen ebenfalls keine sinnvolle Alternative dar, wenn nicht davon aus-
gegangen werden kann, dass eine für den Entscheidungsträger passende Nutzenfunktion ableitbar ist,
ohne dass Informationen über seine Präferenzen zur Verfügung gestellt werden müssen beziehungs-
weise keine Situation vorliegt, in welcher der Entscheidungsträger über keine Präferenzen bezüglich
der Zielkriterien verfügt.
38
3.3.2
A-priori-Methoden als reduktive Verfahren
Entsprechend der in Abschnitt 3.3.1.4 vorgestellten Klassifizierung besitzen A-priori-Methoden die Ei-
genschaft, dass die Informationen über die Präferenzen des Entscheidungsträgers bereits vor Durchfüh-
rung des Optimierungsprozesses vorliegen. Da diese Informationen bereits zu Beginn des Suchprozes-
ses vorhanden sind, ist es Ziel des Verfahrens, genau eine paretooptimale Lösung zu generieren, welche
den Präferenzen des Entscheidungsträgers am besten entspricht. Das gesamte Vorgehen kann demnach
in die Phasen
1. Präferenzartikulation des Entscheidungsträgers
2. Detailgetreue Suche nach einer paretooptimalen Lösung
3. Ergebnispräsentation
35
Vgl. Klassen in [Mie99, S. 63f.], auch [Zim91, S. 30f.].
36
Vgl. [Mie99, S. 63f.], [Coe02, S. 29f.].
37
Vgl. Ausführungen zu dieser Thematik in [Mie99, S. 132].
38
Vgl. [Mie99, S. 132].
19
KAPITEL 3. OPTIMIERUNG BEI MEHRFACHZIELSETZUNG
gegliedert werden.
39
Unter Betrachtung der klassischen Entscheidungsmodelle, welche in Abschnitt 3.4
vorgestellt werden, ergeben sich verschiedene Vorgehensweisen für einen Optimierungsprozess.
40
Ge-
mein ist allen Verfahren die Reduktion des mehrkriteriellen Problems auf ein oder mehrere unikriterielle
Probleme. Aus diesem Grund werden A-priori-Methoden im Folgenden auch als reduktive Methoden
beziehungsweise Verfahren bezeichnet.
3.3.2.1
Verfahren mit Ersatzzielfunktion
Die erste Gruppe dieser Verfahren bildet mit Hilfe der Präferenzangaben des Entscheidungsträgers ei-
ne Ersatzzielfunktion, welche durch das Optimierungsverfahren zur Bewertung von Alternativen ge-
nutzt wird. Diese Ersatzzielfunktion wird substituierend zu den »echten« Zielfunktionen des Problems
verwendet, sodass ein unikriterielles Optimierungsproblem resultiert.
41
Diese Vorgehensweise wird im
Wesentlichen von multiobjektiven Verfahren, wie beispielsweise dem Compromise Programming oder
dem TOPSIS-Verfahren verfolgt.
42
3.3.2.2
Verfahren mit echter Zielreduktion
Die zweite Gruppe der Verfahren reduziert die Ziele des Problems soweit, dass ein unikriterielles Op-
timierungsproblem entsteht. Das verbleibende Ziel stellt dabei ein »echtes« Ziel (hinsichtlich der Ziel-
funktion) des gegebenen Optimierungsproblems dar. Alle übrigen Ziele werden in anderer Form durch
das Verfahren beachtet. Bei der lexikographischen Ordnung werden nach der Ermittlung der Lösungs-
menge weitere Optimierungsläufe innerhalb dieser Lösungsmenge für alle übrigen Kriterien durchge-
führt, während beim Verfahren der Haupt- und Nebenziele alle übrigen Ziele ausschließlich als Restrik-
tion in das Problem einfließen.
43
3.3.3
A-posteriori-Methoden als nicht-reduktive Verfahren
Den reduktiven Verfahren gegenüber stehen die A-posteriori-Methoden, welche erst nach Abschluss
des Optimierungs- respektive Suchprozesses die Angabe der Präferenzen durch den Entscheidungs-
träger erfordern. Aus diesem Grund zielt der Suchprozess auf die Ermittlung der paretooptimalen Lö-
sungsmenge, da während und vor dem Berechnungs- beziehungsweise Suchprozess keine Informatio-
nen über die Präferenzen des Nutzers bekannt sind. Durch nachträgliche Angabe dieser Präferenzen
kann im Anschluss an den Suchprozess die Lösung aus der Menge der paretooptimalen Lösungen aus-
gewählt werden, welche am besten mit den Präferenzen des Nutzers übereinstimmt. Diese Auswahl
kann beispielsweise mit Hilfe einer geeigneten MADM-Methode, der graphischen Darstellung der Pa-
retofront oder einem progressiven Verfahren erfolgen. Das Vorgehen kann daher in die Phasen
1. Ermittlung der paretooptimalen Lösungsmenge
2. Präferenzartikulation des Entscheidungsträgers
3. Auswahl einer Lösung mit geeigneter Methode
gegliedert werden.
44
Nachfolgend werden Ansätze zur exakten Bestimmung und zur Approximation
der Paretofront als mögliche Vorgehensweisen einer nicht-reduktiven Methode vorgestellt.
39
Angelehnt an [Coe02, S. 30]. Vgl. hierzu auch [Mie99, S. 115]. G
AGNÉ
und G
RAVEL
verwenden ein solches Vorgehen beispiels-
weise in Kombination mit einem ACO-Verfahren. Vgl. [Gag04].
40
Siehe Seite 22.
41
Vgl. [Hei99, S. 60].
42
Vgl. Compromise Programming in [Zel73] sowie Abschnitt 3.4.6 und TOPSIS in [Yoo95, S.38f.].
43
Vgl. Abschnitte 3.4.1 und 3.4.2.
44
Angelehnt an [Coe02, S. 30]. Vgl. hierzu auch [Mie99, S. 77].
20
3.3 Multikriterielle kombinatorische Optimierung
3.3.3.1
Dominanztechniken
Neben der Definition des Effizienzbegriffs und somit der Optimalität bei Problemen mit mehrfacher
Zielsetzung stellt die Bestimmung der vollständigen Paretofront gleichzeitig eine Variante der multikri-
teriellen Optimierung dar. Eine mögliche Zielfunktion der Paretooptimierung kann aus dem Paretokri-
terium mit der Gleichung
F () =
1
wenn x : x
0
wenn x : x
max
(3.8)
abgeleitet werden, wobei sämtliche Lösungen bestimmt werden müssen, welche den optimalen Ziel-
funktionswert F () = 1 besitzen.
45
Nach Ermittlung der paretooptimalen Lösungsmenge kann ein
Nutzer eine seinen Präferenzen entsprechende Lösung aus dieser Menge auswählen, ohne im Vorfeld
der Optimierung eine Angabe seiner Zielpräferenzen zu vollziehen.
Da jedoch in Gleichung 3.4 auf Seite 14 festgestellt wurde, dass prinzipiell die Möglichkeit besteht,
dass
=
gelten kann, folgt, dass die Bestimmung aller paretooptimalen Lösungen zu einer voll-
ständigen Enumeration aller Lösungsmöglichkeiten führen kann. Wenn a priori keine Aussage über die
Anzahl der paretooptimalen Lösungen getroffen werden kann, ergibt sich ein deutlicher Nachteil die-
ses Verfahrens. Zusätzlich besteht, vor allem dann, wenn es sich um sehr große Paretofronten handelt,
das Problem, dass die Anzahl der ermittelten Lösungen nach dem Optimierungslauf in vielen Anwen-
dungsfällen reduziert werden muss, bevor sie einem Nutzer geeignet präsentiert werden kann. Da aus
dem Paretokriterium analog zur Allokation von Gütern im volkswirtschaftlichen Sinne keine Aussa-
ge über die Fairness beziehungsweise Gerechtigkeit bei der Verteilung abgleitet werden kann, ist es a
posteriori zudem erforderlich, dass der Nutzer eine seinen Präferenzen entsprechende Lösung aus der
ermittelten Lösungsmenge auswählt.
46
3.3.3.2
Approximation der Paretofront
Der exakten Bestimmung der paretooptimalen Lösungsmenge gegenüber besteht jedoch des Weite-
ren die Möglichkeit, mehrere parallele oder auch sequentielle Optimierungsläufe mit einem A-priori-
Verfahren durchzuführen, um die Paretofront zu approximieren. Dazu wird eine systematische Durch-
musterung von Präferenzsituationen generiert. Für alle Gewichtungsvektoren wird anschließend eine
zielgerichtete Suche durchführt. Hierzu eignen sich allerdings nicht alle beschriebenen Verfahren, son-
dern ausschließlich jene, welche eine freie Gewichtung der Zielkriterien zulassen.
47
Diese Vorausset-
zung wird beispielsweise von den folgenden und - mit Ausnahme von TOPSIS - in dieser Arbeit be-
trachteten Methoden erfüllt.
48
· Methode der gewichteten Summe / des gewichteten Produktes
· Analytical Hierarchy Process
· Gewichtetes Goal / Compromise Programming
· TOPSIS
49
· Fuzzy Decision Making
45
Vgl. Definition in Abschnitt 3.2.1.
46
Vgl. Ausführungen zu Paretokriterium in Abschnitt 3.2 auf Seite 13.
47
Vgl. [Mey04, S. 46f.].
48
Vgl. Ausführungen zu den Verfahren in Abschnitt 3.4.
49
Nähere Informationen in [Yoo95].
21
KAPITEL 3. OPTIMIERUNG BEI MEHRFACHZIELSETZUNG
Die Methode der gewichteten Summe beziehungsweise des gewichteten Produkts wurde bereits er-
folgreich in [Mer02] und [Gun04] in Kombination mit Ant Colony Optimization angewendet, um die
Paretofront näherungsweise zu ermitteln.
50
Durch die Eigenschaft fast aller Verfahren, Kompensationen zwischen Zielfunktionswerten zu er-
möglichen, ergeben sich hierbei jedoch Probleme, die dazu führen können, dass die Paretofront nicht
gleichmäßig approximiert wird.
51
3.4
Reduktive Entscheidungsmodelle
Sowohl bei reduktiven als auch bei nicht-reduktiven Methoden können klassische Entscheidungsmo-
delle als Bewertungs- oder Auswahlverfahren zum Einsatz kommen. Aufgrund dessen werden nach-
folgend ausgewählte Verfahren vorgestellt, welche zu den Klassen der MADM- und MODM-Methoden
gehören und sowohl als Bewertungs- als auch als Auswahlverfahren eingesetzt werden können.
Zunächst werden einige ausgewählte multiattributive Methoden vorgestellt und auf ihre Eignung
für kombinatorische Probleme untersucht. Die Verwendung dieser Verfahren bleibt nicht auf die Aus-
wahl einer Lösung aus der paretooptimalen Lösungsmenge beschränkt, sondern ist sogar in Form von
Ersatzzielfunktionen denkbar. Um den Einsatz in letzterer Weise zu ermöglichen, benötigen einige die-
ser Verfahren geeignete Normierungstechniken, welche die konsistente Vergleichbarkeit von Zielfunk-
tionswerten verschiedener Kriterien gewährleisten. Entsprechende Techniken werden in den jeweiligen
Ausführungen ebenfalls diskutiert. Anschließend wird das Verfahren des Goal beziehungsweise Com-
promise Programmings als Vertreter der MODM-Methoden kurz erörtert.
3.4.1
Lexikographische Ordnung
Eine erste Möglichkeit zur Rückführung mehrerer Kriterien auf eine einkriterielle Optimierung stellt die
lexikographische beziehungsweise hierarchische Anordnung der einzelnen Kriterien dar. Der Entschei-
dungsträger muss bei Verwendung der Methode eine eindeutige Präferenz hinsichtlich der subjektiven
Bedeutung zwischen den Kriterien festlegen, sodass aus den Zielen
z
mit z = 1, . . . , Z eine Ordnung
mit einer eindeutigen Reihenfolge zwischen allen Zielen konsistent in der Form
1
2
. . .
z
. . .
Z
(3.9)
für die Optimierung als Parameter abgeleitet werden kann. Anhand einer solchen Reihenfolge führt
ein Algorithmus einen Optimierungslauf durch, welcher das Problem zunächst ausschließlich für das
Kriterium
1
optimiert. Hierbei werden sämtliche Lösungen bestimmt, welche bezüglich dieses Ziels
Optimalität besitzen. Die ermittelte Teilmenge des Lösungsraums dient als bereichsbeschränkende Ein-
gabe für einen anschließenden Optimierungslauf, der nur dann sattfindet, falls mehr als eine Lösung
bestimmt wurde.
52
Innerhalb der zweiten Sequenz werden alle Lösungen bestimmt, welche innerhalb
des beschränkten Bereichs bezüglich
2
Optimalität besitzen.
53
Dieses Verfahren wird sequentiell für al-
le folgenden Kriterien solange fortgeführt, bis entweder nur noch eine gültige Lösung im beschränkten
Bereich liegt oder die Optimierung für alle Kriterien abgeschlossen wurde. Unter Anwendung dieser
Verfahrensweise ergibt es sich, dass eine Optimierung des Ziels
z
nur dann stattfindet, falls nach der
Optimierung des Ziels
z-1
mehrere Lösungen im beschränkten Bereich liegen.
54
Daraus ergibt sich
50
Vgl. [Mer02, S. 111ff.] und [Gun04, S. 118ff.].
51
Siehe beispielsweise die Probleme der Methode der gewichteten Summe in Abschnitt 3.4.3 auf der nächsten Seite.
52
Vgl. [Neu93, S. 136], [Dom91, S. 45f.].
53
Es muss hierbei darauf hingewiesen werden, dass die Optimalität bezüglich
2
nicht für das ursprüngliche Problem, sondern
ausschließlich im beschränkten Bereich gelten muss. Vgl. [Neu93, S. 136].
54
Vgl. [Neu93, S. 136].
22
0 Kommentare