| |
|
|
Lineare Programmierung (LP)
Die Lineare Programmierung ist eine Technik zur Optimierung von Problemstellungen unter Zuhilfenahme mathematischer Algorithmen. Dabei müssen sich die Probleme darstellen lassen als ein System von linearen Ungleichungen (auch Nebenbedingungen genannt) und einer linearen Zielsetzung (auch Zielfunktion genannt). Synonyme Begriffe zur Linearen Programmierung sind lineare Planungsrechnung oder lineare Optimierung. Das Grund modell der LP hat die folgende Struktur Zielfunktion: n max Z L c, x, j1 Nebenbedingungen: n Z a“ x, = bj für 1,. . . . x, S 0 für1,. . ., n Die Xj stehen für die vom Algorithmus zu ermittelnden Entscheidungsvariablen. Die Zielfunktionsbeiträge der Variablen werden durch Cj dargestellt, ajj charakterisieren die Auswirkungen von Variablenwerten in bezug auf die Nebenbedingungen, die durch den konstanten Wen b, begrenzt werden. Alle Probleme, die in solchen Modell en dargestellt werden können, lassen sich mit Hilfe der SimplexMethode lösen. Diese Methode wurde von Dantzig entwickelt und in dem wohl bedeutendsten Werk der Linearen Programmierung dargelegt (G. B. Dantzig, Lineare Programmierung und Erweiterungen, deutsche Übersetzung von A. Jaeger, BerlinHeidelbergNew York 1966). Die Nebenbedingungen des LPs bilden, mathematisch gesehen, ein konvexes Polyeder, d. h. einen zusammenhängenden Bereich, in dem alle zulässigen Variablenkombinationen liegen. Dieser Bereich wird Zulässigkeitsbereich genannt. Die Schnittpunkte der Nebenbedingungen werden Ecken oder Basislösungen genannt. Die Zielfunktion, die über den Zulässigkeitsbereich maximiert oder minimiert wird, kann nur in einer Ecke ( oder in mehreren) ihren Extremwert annehmen. Diese Ecke heißt Basislösung. Die SimplexMethode geht von einer zulässigen Basislösung aus, wandert systematisch unter Berücksichtigung der Zielfunktion von einer Ecke zur anderen, bis sie durch einen weiteren Eckentausch oder Basiswechsel nicht mehr verbessert werden kann. Somit ist nach endlich vielen Basiswechseln die optimale Lösung, falls eine existiert, gef und en. Da praktische LPModelle mehrere tausend Variablen und Nebenbedingungen aufweisen können, ist es für die Zwecke der Lösbarkeit mittels EDVAnlage innerhalb vertretbarer Zeiten notwendig, die SimplexMethode abzuwandeln bzw. zu erweitern. Die Abwandlung führt zur revidierten SimplexMethode, die nicht mehr die gesamte Matrix der Koeffizienten während der Berechnung mitführt, sondern nur die zum Basiswechsel erforderlichen Koeffizienten. Erweiterungen bestehen z. B. in einer Prozedur, die eine erste zulässige Basislösung ermittelt (CrashProzedur). Außerdem besitzen die meisten Soft702 warepakete eine Reinversionsprozedur, die versucht, Rechenungenauigkeiten auszugleichen, die bei häufigem Basiswechsel auftreten. Die meisten auf dem Markt existierenden Softwaresysteme zur linearen Optimierung (MPSX von IBM, LP5000 von Siemens, FMPS von Sperry Univac) benutzen einheitlich zur Dateneingabe das MPSFormat (mathematical programming System format), bei dem Variablen und Nebenbedingungen durch ihre Namen (8 Stellen) identifiziert werden. Auch die Ausgabe der Lösung ist standardisiert. Die Lineare Programmierung kann als die wichtigste Methode innerhalb des» Operations Research angesehen werden, da viele andere Optimierungsmethoden wie nichtlineare Optimierung, ganzzahlige Optimierung, Transportproblematik, Netzplantechnik, Zuteilungsproblematik als Spezialfälle aus der Linearen Programmierung hervorgegangen sind.
Diese Seite als Bookmark speichern :
<< vorhergehender Begriff |
|
nächster Begriff >> |
|
|
|
|
|
|
|
