Table of Contents

1 Grundlagen.- 1.1 Ein einführendes Beispiel.- 1.2 Grundlegende Begriffe.- 1.3 Spezielle Graphen.- 1.3.1 Wälder, Bäume und Gerüste.- 1.3.2 Kränze.- Aufgaben.- 2 Das Simplexverfahren für Flußprobleme.- 2.1 Flußprobleme.- 2.2 Zirkulationsflüsse.- 2.3 Das Simplexverfahren in Graphen.- 2.3.1 Zur Pivotspaltenwahl.- 2.3.2 Zur Pivotzeilenwahl.- 2.3.3 Der Algorithmus.- 2.3.4 Zur Interpretation des Verfahrens.- 2.3.5 Rücknahme von Voraussetzungen.- Aufgaben.- 3 Anwendungsstrategien für das Simplexverfahren.- 3.1 Zur Implementierung des Verfahrens.- 3.1.1 Zur Pivotspaltenwahl.- 3.1.2 Zur Ermittlung des Zirkulationsflusses.- 3.1.3 Zur Berechnung der—-Werte.- 3.1.4 Zusätzliche Hilfsfunktionen.- 3.1.5 Speicherplatzbedarf.- 3.2 Auffinden einer Anfangslösung.- 3.2.1 Die Zweiphasen-Methode.- 3.2.2 Verwendung von Vorgängerfunktion und Big-M-Prinzip.- 3.2.3 Pivotstrategien.- Aufgaben.- 4 Primale Flußminimierung.- 4.1 Ein Verfahren zulässiger Abstiegsrichtungen.- 4.2 Negative Kreise in Netzen.- 4.2.1 Zur Ermittlung negativer Ringe.- 4.2.2 Ein Verfahren zur Ermittlung negativer Kreise.- 4.3 Das Out-of-Kilter-Verfahren.- Aufgaben.- 5 Unzulässige Startlösungen.- 5.1 Eine Verallgemeinerung des Out-of-Kilter-Verfahrens.- 5.1.1 Reduktion des Problems.- 5.1.2 Erweiterung des Out-of-Kilter-Verfahrens.- 5.1.3 Ein Zweiphasen-Algorithmus.- 5.2 Anwendungsstrategien.- 5.2.1 Vorphasen.- 5.2.2 Ungarische Eröffnung.- 5.2.3 Die Ungarische Methode für Hitchcock- und Zuordnungsprobleme.- Aufgaben.- 6 Vermessung von Netzen.- 6.1 Minimale Distanzen.- 6.2 Kürzeste Wege und negative Kreise.- 6.3 Anwendungsstrategien.- 6.4 Flußminimierung durch Vermessung von Netzen.- Aufgaben.- 7 Netzplantechnik.- 7.1 Eine Einführung in die Zeitplanung.- 7.2 Projektplanung und -überwachung mit Netzplänen.- 7.3 Ein Verfahren der Kostenplanung.- 7.3.1 Problembeschreibung.- 7.3.2 K-Netzpläne.- 7.3.3 Ein Verfahren zur Kostenplanung.- Aufgaben.- 8 Optimale Untergraphen.- 8.1 Auswahl von Untergraphen.- 8.1.1 Kostenminimale Zuordnungen.- 8.1.2 Kostenminimale Überdeckungen.- 8.1.3 Kostenminimale Geraste.- 8.1.4 Kostenminimale Routen.- 8.2 Branch-and-Bound-Verfahren.- 8.2.1 Die Organisationsform des Verfahrens.- 8.2.2 Auswahl- und Verzweigungsregeln.- 8.3 Berechnung der Schranken.- 8.3.1 Das Verfahren von Little, Murty, Sweeney, Karel.- 8.3.2 Das Verfahren von Eastman.- 8.4 Heuristische Methoden.- 8.4.1 Sukzessive Einbeziehung von Knoten.- 8.4.2 Der k-Tausch.- Aufgaben.- 9 Optimale Touren.- 9.1 Tourenprobleme.- 9.2 Das reale k-Liefer-Problem.- 9.2.1 Verfahren der sukzessiven Einbeziehung von Knoten.- 9.2.2 Das Verfahren von Little et al..- 9.2.3 Schrankenverbesserung nach einer Idee von Held und Karp.- 9.3 Das Briefträgerproblem.- Aufgaben.- Sachwortverzeichnis.