Inhalt
Inhaltsübersicht.- 1. Maximale Ströme und minimale blockierende Schnitte in Netzen.- 1.1. Netze (Definition und Darstellung von Netzen in Bildern und Matrizen).- 1.2. Zur Interpretation von Netzen (Hinweise auf Transportnetze, Ausbildungsnetze, Verflechtungsnetze).- 1.3. Ströme und Schnitte in engen Netzen (Netze mit beschränkter Kapazität, minimale blockierende Schnitte als Engpässe und maximale zulässige Ströme zwischen Quellen und Mündungen als extreme Auslastung in engen Netzen).- 1.4. Sätze über Ströme und Schnitte in engen Netzen (Erweiterung eines Satzes von Ford und Fulkerson, das max-flow-min-cut-Theorem, ein neues Theorem, äquivalente Sätze über Engpässe, Sätze über Transferpfade).- 2. Die Konstruktion von maximalen zulässigen Strömen und minimalen blockierenden Schnitten in engen Netzen.- 2.1. Ein Algorithmus zum Auffinden von minimalen blockierenden Schnitten in engen Netzen (Flußdiagramm, Beispiele, Beweise).- 2.2. Ein Algorithmus zur Konstruktion eines maximalen zulässigen Stromes (Flußdiagramm, Beispiel, Beweise).- 2.3. Vergleich zwischen neuen und alten Konstruktionsverfahren (Das Enumerationsverfahren von Dulliez und Rao, ein Ansatz der Linearen Programmierung und die Konstruktion von Ford und Fulkerson im Vergleich zu den neuen Algorithmen).- 3. Zirkulationen in zweiseitig beschränkten, bewerteten Netzen.- 3.1. Zweiseitig beschränkte, bewertete Netze und zulässige, kostenminimale Zirkulationen (Netze mit begrenzter Kapazität, Mindestauslastungen und Kosten für die Ströme).- 3.2. Sätze über Zirkulationen (Das Hoffmansche Zirkulationstheorem, ein Satz über Schattenpreise).- 4. Die Konstruktion von zulässigen Zirkulationen in zweiseitig beschränkten Netzen.- 4.1. Ein Algorithmus (Flußdiagramm, Beispiel, Beweise).- 4.2.Vergleich zwischen dem neuen Algorithmus und dem Zirkulationsalgorithmus von Ford und Fulkerson (Vergleich der Konzepte und Schrittzahlen).- 5. Die Konstruktion von kostenminimalen zulässigen Zirkulationen.- 5.1. Optimalitätskriterien (Hinreichende Optimalitätsbedingungen und Schattenpreise).- 5.2. Ein Algorithmus (Flußdiagramm, Beispiele, Beweise).- 5.3. Vergleich zwischen Algorithmus 4 und dem out-of-kilter-Algorithmus von Ford und Fulkerson (Vergleich der Struktur der Algorithmen und der nicht-optimalen Zustände).- 6. Anwendungen.- 6.1. Die Ermittlung der Engpässe und die maximale Auslastung eines Transportnetzes (Transportnetze mit mehreren Quellen, Knoten- und Bogenkapazitäten).- 6.2. Ein dynamisches Transportproblem (Rückführung eines dynamischen Problems auf ein statisches).- 6.3. Konsistenztest für prognostizierte makroökonomisehe Stromgrößen (Konsistenz von oberen und unteren Schranken für die Ströme eines volkswirtschaftlichen Kreislaufs).- 6.4. Zuordnungsprobleme (Das Assignmentproblern der Linearen Programmierung).- 6.5. Der Weg des geringsten Widerstandes (Kürzeste Wege und taktische Konzepte).- 6.6. Warenhausprobleme (Das Cahnsche Problem mit Erweiterungen, Hinweis auf ein Finanzierungsproblem von gleicher Struktur).- 6.7. Kostenminimale Transporte (Verallgemeinerung des sogenannten general minimal Cost-flow problem, vermischte Probleme von der Struktur des Transshipment- und Hitchcockproblems).