präsentiert von
Inhaltsverzeichnis
1 Einführung
1.1 Gegenstand der Arbeit
1.2 Dokumentstruktur
2 Theoretische Grundlagen
2.1 Grundlagen der Graphentheorie
2.1.1 Gerichtete Graphen
2.1.2 Wichtige Eigenschaften von Graphen
2.2 Grundlagen der Komplexitätstheorie
2.2.1 Komplexitätsmaße
2.2.2 Komplexitätsklassen P und NP
2.2.3 Problemrelationen und polynomielle Reduktion
2.3 Diskrete und kombinatorische Optimierung
2.3.1 Problemdefinition und Eigenschaften
2.3.2 Ausgewählte Optimierungsprobleme
3 Optimierung bei Mehrfachzielsetzung
3.1 Mehrkriterielle Probleme
3.1.1 Problemstellung
3.1.2 Zielbeziehungen
3.2 Optimalität bei mehrfacher Zielsetzung
3.2.1 Paretooptimalität
3.2.2 Eigenschaften der paretooptimalen Lösungsmenge
3.2.3 Idealpunkte und Nadir-Punkt der Front
3.3 Multikriterielle kombinatorische Optimierung
3.3.1 Klassifizierung entscheidungstheoretischer Ansätze
3.3.2 A-priori-Methoden als reduktive Verfahren
3.3.3 A-posteriori-Methoden als nicht-reduktive Verfahren
3.4 Reduktive Entscheidungsmodelle
3.4.1 Lexikographische Ordnung
3.4.2 Haupt- und Nebenziele
3.4.3 Methode der gewichteten Summen und Produkte
3.4.4 AHP
3.4.5 Fuzzy Decision Making
3.4.6 Goal Programming und Compromise Programming
3.5 Fazit
3.5.1 Beurteilung der A-priori-Methoden
3.5.2 Beurteilung der A-posteriori-Methoden
4 Optimierung von Angebotsnetzen im EVCM
4.1 Extended Value Chain Management
4.1.1 Phasenmodell
4.1.2 Prozessvariantenplan und Prozessplan
4.1.3 Angebotsnetze
4.1.4 Problemstellung bei der Kompetenzzellenauswahl
4.2 Formalisierung des Problems
4.2.1 Problemgraph
4.2.2 Restriktionssystem
4.2.3 Lösungskonstruktion und Problemstellung
4.3 Zielsetzungen der Optimierung
4.3.1 Preis
4.3.2 Lieferwahrscheinlichkeit
4.3.3 Liefertermin
4.4 Angebote mit unvollständigen Mengen
4.4.1 Ansatz mit impliziter Behandlung von Teilmengen
4.4.2 Ansatz mit Behandlung expliziter Fehlmengen
4.5 Problemkomplexität
5 Dynamic Programming
5.1 Theoretische Grundlagen
5.1.1 Einführung
5.1.2 Problemstellung und Lösungsprinzip
5.1.3 Verfahren
5.2 Problemspezifische Modellierung
5.2.1 Problemspezifischer Basisalgorithmus
5.2.2 Umgang mit Divergenzen
5.3 Komplexitätsbetrachtungen
5.3.1 Komplexität bei einkriteriellen Problemen mit rein konvergierenden Prozessplänen
5.3.2 Komplexität bei einkriteriellen Problemen mit allgemeinen Prozessplänen
6 Ant Colony Optimization
6.1 Einführung
6.1.1 Einordnung des Verfahrens
6.1.2 Naturanalogie
6.1.3 ACO-Metaheuristik
6.2 Verschiedene Ansätze
6.2.1 Ant System
6.2.2 Ant Colony System
6.3 Mehrkriterielle Ameisenalgorithmen
6.3.1 Überblick
6.3.2 Paretooptimierung mit ACO
6.3.3 Gewichtung bei beliebiger Zielanzahl
6.4 Problemspezifische Modellierung
6.4.1 Ant Family Heuristic
6.4.2 Lösungskonstruktion
6.4.3 Heuristikwerte für das Angebotsnetz
6.4.4 Konvergenzverhalten und Pheromoninitialisierung
7 Hybride Methoden und Erweiterungen
7.1 Pheromonaktualisierung bei Paretooptimierung
7.1.1 Eigenschaften der bisherigen Strategie
7.1.2 Nadir-Punkt-Strategie
7.2 Paretooptimierung mit Auswahl nach Fuzzy Decision Making
7.2.1 Ausgangssituation
7.2.2 Auswahlwahrscheinlichkeiten über Fuzzy Decision Making
7.3 Problemreduktion
7.3.1 Dominanz von Teilgraphen
7.3.2 Algorithmisches Konzept
7.4 Die Look-Ahead-Heuristic
7.4.1 Ausgangssituation
7.4.2 Konzept der Look-Ahead-Heuristic
8 Evaluierung
8.1 Evaluierung des Parallel Path Problems und des dynamischen Programms
8.1.1 Verwendete Evaluierungsmaße
8.1.2 Abhängigkeiten zwischen Komplexität und Zielkriterien
8.1.3 Abhängigkeiten zwischen Paretofront und Zielfunktionen
8.1.4 Komplexität von Angebotsnetzen
8.1.5 Probleme mit divergenten Prozessplänen
8.2 Evaluierung ACO und hybride Ansätze
8.2.1 Verwendete Evaluierungsmaße
8.2.2 Problemlösungsverhalten der Ameisenalgorithmen
8.2.3 Verwendung von Routingtabellen und Tabulisten
8.2.4 Aktualisierungsstrategien
8.2.5 Analyse verschiedener Aggregationsmethoden
8.2.6 Standard-Heuristik und Look-Ahead-Heuristic
8.2.7 Problemreduktion
Fazit und Ausblick
A Ergänzungen und Detailinformationen zur Evaluierung
A.1 Evaluierte Problemgraphen und Prozesspläne
A.1.1 Technologiegraphen
A.1.2 Problemgraphen
A.2 Verwendete Konfigurationen und Parameter von ACO
A.2.1 Verwendete Konfiguration
A.2.2 Verwendete Parameter
B Beispielrechnung
B.1 Dynamisches Programm
B.2 Lösungskonstruktion ACO
Literaturverzeichnis
Register
Zielsetzung & Themen
Die Arbeit untersucht das Optimierungsproblem von Angebotsnetzen innerhalb des "Extended Value Chain Management" (EVCM). Ziel ist die Entwicklung und Evaluierung von Lösungsansätzen zur Auswahl von Kompetenzzellen in einem unternehmensübergreifenden Produktionsnetzwerk, wobei die Komplexität des Problems in uni- und multikriterieller Hinsicht analysiert wird.
- Optimierung von Angebotsnetzen mittels dynamischer Programmierung
- Einsatz von Ant Colony Optimization zur näherungsweisen Problemlösung
- Hybridisierung und Erweiterung von Lösungsalgorithmen
- Umgang mit Divergenzen in Prozessplänen und deren Komplexitätsauswirkungen
- Evaluierung der Leistungsfähigkeit der entwickelten Methoden
Auszug aus dem Buch
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, 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 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. Zwei Knoten a und b besitzen in einem Graphen Mehrfachkanten, falls mindestens zwei oder mehr verschiedene Elemente ei ∈ E mit i = {1 . . . n} und i ∈ N existieren, welche zwei Knoten a und b miteinander verbinden. Im ungerichteten Fall werden zwei Kanten e1 = (a, b) und e2 = (b, a) als parallel bezeichnet. Im gerichteten Fall hingegen heißen die Bögen beziehungsweise gerichteten Kanten e1 = a → b und e2 = b → a antiparallel, da sie zwar die gleichen Knoten verbinden, sich ihre Richtung aber unterscheidet.
Zusammenfassung der Kapitel
1 Einführung: Einleitung in die Problematik der Angebotsnetze im EVCM und Vorstellung der Forschungsfrage sowie Dokumentstruktur.
2 Theoretische Grundlagen: Erläuterung graphentheoretischer, komplexitätstheoretischer und diskreter Optimierungsgrundlagen.
3 Optimierung bei Mehrfachzielsetzung: Detaillierte Betrachtung multikriterieller Probleme, paretooptimaler Lösungen und verschiedener Entscheidungsansätze.
4 Optimierung von Angebotsnetzen im EVCM: Vorstellung des EVCM-Konzepts und Formalisierung des Optimierungsproblems.
5 Dynamic Programming: Theoretische Einführung in die dynamische Programmierung und deren Anwendung zur exakten Lösung des Parallel Path Problems.
6 Ant Colony Optimization: Vorstellung der ACO-Metaheuristik und deren Anpassung an die Anforderungen von Angebotsnetzen.
7 Hybride Methoden und Erweiterungen: Entwicklung und Analyse hybrider Algorithmen zur Verbesserung der Lösungsgüte bei komplexen Problemstellungen.
8 Evaluierung: Umfassende Untersuchung und Evaluierung der vorgestellten Methoden anhand verschiedener Problemgraphen und Leistungskennzahlen.
Schlüsselwörter
EVCM, Angebotsnetze, kombinatorische Optimierung, Parallel Path Problem, Dynamische Programmierung, Ant Colony Optimization, Paretooptimalität, Multikriterielle Optimierung, heuristische Verfahren, Look-Ahead-Heuristic, Problemkomplexität, NP-Vollständigkeit, Lieferwahrscheinlichkeit, Preis, Liefertermin.
Häufig gestellte Fragen
Worum geht es in dieser Diplomarbeit?
Die Arbeit befasst sich mit der Optimierung unternehmensübergreifender Angebotsnetze im Rahmen des sogenannten Extended Value Chain Managements (EVCM).
Welche zentralen Themenfelder werden behandelt?
Zentrale Themen sind die mathematische Modellierung von Angebotsnetzen, die Anwendung exakter Lösungsverfahren wie der dynamischen Programmierung und metaheuristischer Verfahren wie Ant Colony Optimization.
Was ist das primäre Ziel der Arbeit?
Das Hauptziel ist die Entwicklung und Evaluierung von Methoden zur Auswahl der optimalen Kombination von Kompetenzzellen, die den Kundenanforderungen an Preis, Lieferwahrscheinlichkeit und Liefertermin entsprechen.
Welche wissenschaftliche Methode kommt zum Einsatz?
Die Arbeit nutzt Methoden der Graphentheorie zur Modellierung, Techniken der diskreten und multikriteriellen kombinatorischen Optimierung sowie algorithmische Ansätze der dynamischen Programmierung und Ameisenalgorithmen (ACO).
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die theoretische Fundierung, die spezifische Modellierung der Angebotsnetze als "Parallel Path Problem" und die Erarbeitung von Lösungsverfahren, inklusive einer detaillierten Evaluierung.
Welche Schlüsselbegriffe charakterisieren die Arbeit?
Charakterisierende Begriffe sind EVCM, Angebotsnetze, Parallel Path Problem, Paretooptimalität, Multikriterielle Optimierung und Ant Colony Optimization.
Warum ist die "Look-Ahead-Heuristic" wichtig?
Diese Heuristik wurde entwickelt, um die Schwächen der Standard-Greedy-Heuristik in ACO-Algorithmen bei unterschiedlichen Pfadlängen zu beheben und somit eine realistischere Bewertung von Alternativen zu ermöglichen.
Welche Rolle spielt die Problemreduktion?
Die Problemreduktion nutzt Konzepte der dynamischen Programmierung, um den Lösungsraum vorab zu vereinfachen und die Effizienz des Ameisenalgorithmus durch Fokus auf relevante Entscheidungsbereiche zu erhöhen.
Was zeigt die Evaluierung hinsichtlich der Lösbarkeit?
Die Evaluierung demonstriert, dass exakte Lösungen mittels dynamischer Programmierung nur für kleinere und mittlere Instanzen praktikabel sind, während für größere Probleme oder Probleme mit hoher Divergenz auf ACO-basierte Näherungsverfahren zurückgegriffen werden muss.
Ende der Leseprobe aus 197 Seiten
- nach oben
- Arbeit zitieren
- Dipl.-Wirt.-Inf. Sascha Häckel (Autor:in), 2006, Hybride Ansätze zur Optimierung Kürzester-Wege-Probleme in gerichteten Graphen, München, Page::Imprint:: GRINVerlagOHG, https://www.diplomarbeiten24.de/document/90934
neugierig - aktuell - relevant
Entdecken Sie hilfreiche Tipps und Tricks rund ums Studium!
Entdecken Sie hilfreiche Tipps und Tricks rund ums Studium!
Ihre Hausarbeit / Abschlussarbeit:
- - Publikation als E-Book und Buch
- - Hohes Honorar auf die Verkäufe
- - Für Sie komplett kostenlos - mit ISBN
- - Es dauert nur 5 Minuten
- - Jede Arbeit findet Leser
- © GRIN Publishing GmbH.
- Alle Inhalte urheberrechtlich geschützt. Kopieren und verbreiten untersagt.
- info@grin.com
- AGB
- Open Publishing
Der GRIN Verlag hat sich seit 1998 auf die Veröffentlichung akademischer eBooks und Bücher spezialisiert. Der GRIN Verlag steht damit als erstes Unternehmen für User Generated Quality Content. Die Verlagsseiten GRIN.com, Hausarbeiten.de und Diplomarbeiten24 bieten für Hochschullehrer, Absolventen und Studenten die ideale Plattform, wissenschaftliche Texte wie Hausarbeiten, Referate, Bachelorarbeiten, Masterarbeiten, Diplomarbeiten, Dissertationen und wissenschaftliche Aufsätze einem breiten Publikum zu präsentieren.
Kostenfreie Veröffentlichung: Hausarbeit, Bachelorarbeit, Diplomarbeit, Dissertation, Masterarbeit, Interpretation oder Referat jetzt veröffentlichen!
Folgen Sie GRIN auf
- GRIN Verlag GmbH
-
- Nymphenburger Str. 86
- 80636
- Munich, Deutschland
- +49 89-550559-0
- +49 89-550559-10
- info@grin.com
-
