In diesem Buch wird das in Band 1 entwickelte revidierte Simplexverfahren an die besondere Struktur von Optimierungsaufgaben angepaßt, deren Zielsetzung in der Ermittlung kostenminimaler Flüsse in gerichteten Graphen besteht. Die Implementierung des Verfahrens wird ausführlich diskutiert. Ausgehend von einer so entstehenden graphentheoretischen Version des Simplexverfahrens werden weite re kombinatorische Verfahren vorgestellt, deren Darstellung und B egründung auf ausschließlich graphentheoretischen Methoden beruht .Über ein Studium kürzester Wege in Graphen werden die Grundlagen der Terminplanung (Netzplantechnik) erarbeitet und danach die vor gestellten Methoden zu einem Verfahren der Kostenplanung (Netzpla ntechnik) zusammengefügt. Den Abschluß bilden Betrachtungen zu Re ihenfolgeproblemen.Das Buch ist methodenorientiert; es versucht exemplarisch, in die Denk- und Arbeitsweise der Optimierung in Graphen einzuführen. D abei werden die Verfahren strikt algorithmisiert; die Umsetzung d er Verfahren in ausführbare Programme ist ein richtungsgebender G esichtspunkt.
Inhaltsverzeichnis
1 Grundlagen. - 1. 1 Ein einführendes Beispiel. - 1. 2 Grundlegende Begriffe. - 1. 3 Spezielle Graphen. - Aufgaben. - 2 Das Simplexverfahren für Flußprobleme. - 2. 1 Flußprobleme. - 2. 2 Zirkulationsflüsse. - 2. 3 Das Simplexverfahren in Graphen. - Aufgaben. - 3 Anwendungsstrategien für das Simplexverfahren. - 3. 1 Zur Implementierung des Verfahrens. - 3. 2 Auffinden einer Anfangslösung. - Aufgaben. - 4 Primale Flußminimierung. - 4. 1 Ein Verfahren zulässiger Abstiegsrichtungen. - 4. 2 Negative Kreise in Netzen. - 4. 3 Das Out-of-Kilter-Verfahren. - Aufgaben. - 5 Unzulässige Startlösungen. - 5. 1 Eine Verallgemeinerung des Out-of-Kilter-Verfahrens. - 5. 2 Anwendungsstrategien. - 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. - Aufgaben. - 8 Optimale Untergraphen. - 8. 1 Auswahl von Untergraphen. - 8. 2 Branch-and-Bound-Verfahren. - 8. 3 Berechnung der Schranken. - 8. 4 Heuristische Methoden. - Aufgaben. - 9 Optimale Touren. - 9. 1 Tourenprobleme. - 9. 2 Das reale k-Liefer-Problem. - 9. 3 Das Briefträgerproblem. - Aufgaben. - Sachwortverzeichnis.
