E-Book, Deutsch, 255 Seiten
ISBN: 978-3-7398-0342-5
Verlag: UVK
Format: EPUB
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
Behandelt werden zentrale Fragen und Algorithmen des Operations Research wie diskrete, lineare und ganzzahlige Optimierungsmethoden sowie Entscheidungs- und Spieltheorie. Anwendungen sind beispielsweise Netzplantechnik, Transportprobleme oder Routenplanung. Verweise auf weiterführende Themenbereiche runden die Darstellung ab.
Autoren/Hrsg.
Fachgebiete
Weitere Infos & Material
2 Optimierung in Graphen
Übersicht
Zunächst werden in Abschnitt 2.1 Graphen und – als Spezialfälle – Bäume und Netzwerke eingeführt. Viele Fragestellungen des OR lassen sich durch Graphen abbilden. Oft folgt dann die Frage nach kürzesten Wegen in diesen Konstrukten, die in Abschnitt 2.2 vgl. S. 56 gelöst wird. Beispiel für die Suche nach längsten Wegen sind Netzpläne zur Projektsteuerung, die in Abschnitt 2.3 vgl. S. 64 erklärt werden. Viele Optimierungsprobleme, die sich in Graphen abbilden lassen, sind mit der Dynamischen Optimierung zu lösen, die in Abschnitt 2.4 vgl. S. 76 angesprochen wird. 2.1 Relationen, Graphen, Bäume
Um Graphen mathematisch „erfassbar“ zu machen, benötigen wir zunächst Sprechweisen und etwas Handwerkszeug. Mathematische Begriffe zur Modellierung sind hier Objekte, Mengen und Relationen. 2.1.1 Relationen
In Modellen werden Objekte der Realwelt zur mathematischen Behandlung oft in Mengen zusammengefasst. Zur formalen Umsetzung von Beziehungen zwischen solchen Objekten einer oder mehrerer Mengen dienen Relationen. Definition 2.1 Seien A und B (nicht-leere) Mengen. Eine Teilmenge R ? A × B heißt (binäre) RELATION Glossar von A nach B Dabei ist A × B das KARTESISCHE PRODUKT Glossar der Mengen A und B, das definiert wird durch A × B = {(a, b) : a ? A, b ?B} Eine Relation beinhaltet also in der Regel nicht alle Kombinationsmöglichkeiten, sondern einen Ausschnitt davon. Dieser Ausschnitt kann durch Aufzählung oder durch irgendwelche Kriterien definiert werden. Kartesisches Produkt und Relationen lassen sich auch für mehr als zwei Mengen definieren: Ai ? , 1 = i = m, R ? A1 × · · · × Am heißt Relation zwischen A1, . . . , Am Beispiel 2.1: A = B = : R = {(x, y): x = y} ? 2 A = B = : R = {(x, y) : y = x2} ? 2 A = B = : R = {(p, q) : p | q} ? 2 A = B = : R = {(p, q) : p = q mod t} ? 2 mit t ? , t = 2. Definition 2.2 (Komposition/Inversion von Relationen) Mit Relationen lässt sich auch „rechnen“. Vorbild dabei sind die entsprechenden Operationen für Funktionen. R ? A × B und S ? B × C seien Relationen, dann heißt R º S ? A × C Komposition von R und S und ist definiert durch R º S = {(a, c) : ? b ? mit (a, b) ? R und (b, c) ? S} R ? A × B, dann ist R-1 ? B × A die inverse Relation, die definiert ist durch R-1 = {(b, a) : (a, b) ? R} Beispiel 2.2: Gegeben seien A = {1, 2, 3} B = {0, 1} C = {1, 2, 3, 4} R = {(1, 0), (2, 1), (3, 0)} ? A × B S = {(0, l), (0, 2), (l, 3), (l, 4)} ? B × C Dann gilt: R º S = {(1, 1), (1, 2), (2, 3), (2, 4), (3, 1), (3, 2)} ? A × C R-1 = {(0, 1), (1, 2), (0, 3)} ? B × A S-1 = {(1, 0), (2, 0), (3, 1), (4, 1)} ? C × B Rechenregeln R ? A × B, S ? B × C, T ? C × D =? (R º S) º T = R º ( S º T) R ? A × A, S ? A × A =? (R º S)-1 = S-1 º R-1 R ? A × B =? (R-1)-1 = R Jede binäre Relation von einer endlichen Menge A nach einer endlichen Menge B lässt sich zwanglos graphisch darstellen. Beispiel 2.3: Gegeben seien A = {1, 2, 3, 4} und B = {x, y, z}. Die Relation sei gegeben durch R = {(1, x), (1, z), (2, y), (3, y), (3, z), (4, x)} Eine mögliche grafische Darstellung zeigt Abbildung 2.1. Abbildung 2.1: Grafische Darstellung einer Relation Formalisiert wird diese Darstellung durch die folgende Begriffsbildung. 2.1.2 Graphen
GRAPHEN Glossar dienen der Darstellung von Strukturen, d.h. logischen und/oder zeitlichen Abhängigkeiten. Definition 2.3 Sei V ? eine endliche Menge („vertices“, d.h. KNOTEN Glossar) und E eine Menge zweielementiger Teilmengen von V („edges“, d.h. KANTEN Glossar). Dann wird G = (V, E) als (ungerichteter) Graph bezeichnet. Beispiel 2.4: V sei die Menge der (internationalen) Flughäfen in Deutschland. {v, w} ? E, falls zwischen v und w eine Direktverbindung besteht. Der Sachverhalt lässt sich durch ein Schaubild wie Abbildung 2.2 darstellen, das durchaus auch mal mehr als nur Knoten und Kanten enthält. (Die hier eingezeichneten Verbindungen sind nur zur Illustration gedacht und dürften mit den tatsächlichen Verbindungen vermutlich wenig zu tun haben.) Abbildung 2.2: Flugverbindungen in Deutschland Für die weitere Diskussion bauen wir uns ein übersichtliches Beispiel, in dem nur die relevanten Elemente abgebildet werden. Beispiel 2.5: V = {1, 2, 3, 4, 5, 6} E = {{1, 2}, {1, 3}, {1, 5}, {1, 6}, {2, 3}, {3, 4}, {3, 6}, {4, 5}, {5, 6}} Eine einfache Darstellung des Graphen ist in Abbildung 2.3 zu sehen. Abbildung 2.3: Beispielgraph Die Anordnung der Knoten und Kanten im Raum ist nicht eindeutig festgelegt; insofern repräsentiert auch die Abbildung 2.4 denselben Graphen. Abbildung 2.4: Beispielgraph in anderer Darstellung Wir werden üblicherweise mit schlichten Graphen arbeiten, die definiert sind durch die Festlegungen: keine Schlingen, d.h. Kanten von v nach v (v ? V ). Es gilt also immer (v, v) ? E. keine Mehrfachkanten zwischen zwei Knoten. Dies würde auf sogenannte multiple Graphen führen. Weitere Begriffe: Gegeben sei eine Kante e = {v, w} ? E, dann sagt man: „e verbindet ihre Endpunkte v und w.“ „v und w sind adjazent.“ „v und e sind inzident.“ sowie „w und e sind inzident.“ Man benötigt zur Rechnung üblicherweise nicht die grafische Darstellung eines Graphen, sondern eine algorithmisch nutzbare Form, die denselben Sachverhalt darstellt. Möglich ist die algebraische Beschreibung eines Graphen G = (V, E), V = {v1, . . . , vm} mittels der ADJAZENZMATRIX Glossar A = [aij], 1 = i, j = m, die definiert ist durch die Einträge Beispiel 2.6 (Fortsetzung von Beispiel 2.5): Dem schon bekannten Graphen in Abbildung 2.5 Abbildung 2.5: Beispielgraph entspricht die Adjazenzmatrix Bemerkungen: In ungerichteten Graphen gilt aij = aji. Deshalb reicht es natürlich, die Matrix A oberhalb oder unterhalb der Hauptdiagonalen anzugeben. Mittels der Adjazenzmatrix lassen sich die Probleme dieses Kapitels auch algebraisch beschreiben. Dies wird speziell bei Implementierung der Verfahren ausgenutzt. Die Elemente der Hauptdiagonalen sind stets 0, falls Schlingen ausgeschlossen wurden. Weitere Sprechweisen: H = (W, F) ist Teilgraph von G = (V, E), falls W ? V und F ? E. Im Falle V = W heißt H ein aufspannender Teilgraph. G = (V, E) Graph, W ? V . Die Definition E | W := {{w, w'} ? E : w, w' ? W} ergibt die Kanten, die nach Weglassen von Ecken noch Start- und Endpunkte...
