Theorie Der Linearen Dekomposition

ISBN-13: 9783540056676 / Niemiecki / Miękka / 1971 / 194 str.

Paul B. Hagelschuer

Opis

Das zentrale Interesse heutiger Forschung auf dem Gebiet der mathematischen Programmierung gilt speziellen Fragen der linearen Programmierung so wie allgemeinen Problemen der nichtlinearen Pro grammierung. Unter den speziellen Fragen der linea ren Programmierung ist der mit dem Stichwort De komposition verbundene Komplex aus verschiedenen GrUnden von besonderer Bedeutung und Aktualitat: Einerseits, weil die praktische Anwendung von linearen Programmen haufig zu derart groBen Syste men fUhrt, daB die Speicherkapazitat moderner Re chenanlagen fUr diese Systeme nicht ausreicht, so daB die Idee der Dekomposition, d. h. der Zerlegung in kleinere, voneinander unabhangig zu l6sender Teilprogramme, in diesem Zusammenhang von entschei dender Bedeutung ist; andererseits, weil sich mit Hilfe der Dekomposition interessante theoretische Zusammenhange innerhalb der mathematischen Pro grammierung aufzeigen lassen. Wenn man davon ausgeht, daB bislang keine zusammen hangende Darstellung der Satze und Verfahren der Dekomposition aus einheitlicher Sicht existiert, lag es nahe diese LUcke zu schlieBen. Hagelschuer hat mit der vorliegenden Untersuchung eine ge schlossene Darstellung der Theorie der linearen Dekomposition vorgelegt. Er hat die verschiedenar tigen Einzeldarstellungen nicht nur mit einheitli cher Symbolik zusammengetragen, sondern insbesonde re mit Hilfe des von ihm bewiesenen Zerlegungssatzes eine gemeinsame, mehrere Dekompositionsverfahren verbindende Grundlage gefunden."

Spis treści

1. Dekompositionsverfahren zur Lösung blockdiagonaler linearer Programme mit verbindenden Nebenbedingungen oder verbindenden Variablen.- 1.1. Indirekte Dekompositionsverfahren.- 1.1.1. Das Dekompositionsverfahren von DANTZIG und WOLFE.- 1.1.1.1. Der Darstellungssatz linearer Systeme und das Dekompositionsprinzip von DANTZIG und WOLFE.- 1.1.1.2. Die Beschreibung des Lösungsalgorithmus.- 1.1.2. Die Partitionsmethode von BENDERS.- 1.1.2.1. Ein Zerlegungssatz für allgemeine lineare Programme.- 1.1.2.2. Das Partitionstheorem von BENDERS.- 1.1.2.3. Die Beschreibung des Lösungsalgorithmus.- 1.2. Direkte Dekompositionsverfahren.- 1.2.1. Das Dekompositionsverfahren von ROSEN.- 1.2.1.1. Die Beschreibung des Lösungsalgorithmus.- 1.2.1.2. Der Zusammenhang des Verfahrens von ROSEN mit der parametrischen linearen Programmierung.- 1.2.2. Die Unzulässigkeitsmethode von BALAS.- 1.2.2.1. Die Beschreibung des Lösungsalgorithmus.- 1.2.2.2. Der Zusammenhang des Verfahrens von BALAS mit der Methode der zulässigen Richtungen.- 2. Dekompositionsverfahren zur Lösung blockdiagonaler linearer Programme mit verbindenden Nebenbedingungen und verbindenden Variablen.- 2.1. Die doppelte Dekompositionsmethode von KRONSJÖ.- 2.1.1. Die Beschreibung des Lösungsalgorithmus.- 2.1.2. Eine Erweiterung des Verfahrens von KRONSJÖ.- 2.2. Ein aus dem Zerlegungssatz abgeleitetes doppeltes Dekompositionsverfahren.- 2.2.1. Die Transformation des primalen und dualen blockdiagonalen linearen Programms in ein dreifaches Optimierungsproblem.- 2.2.2. Die Beschreibung des Lösungsalgorithmus.- 2.2.2.1. Die primale Schleife eines Iterationsschritts.- 2.2.2.2. Die duale Schleife eines Iterationsschritts.- 3. Dekompositionsverfahren zur Lösung allgemeiner nicht strukturierter linearer Programme.- 3.1. Das Modell der ‘Zweiebenenplanung’ von LIPTÁK.- 3.2. Ein aus dem Zerlegungssatz abgeleitetes allgemeines doppeltes Dekompositions- prinzip.- Anhang I.- Anhang II.