|
|
lineare Optimierung
lineare Planungsrechnung, lineare Programmierung, linear programming.
I. Begriff: Es handelt sich um ein Teilgebiet des Operations Research (OR), das sich im wesentlichen mit dem theoretischen Hintergrund von mathematischen Optimierungssystemen der Form
mit zugehörigen Rechenverfahren sowie mit dem Einsatz derartiger Systeme zur Unterstützung ökonomischer Entscheidungsprozesse befaßt. In dem System ((1), (2), (3)), das man auch (allgemeines) lineares Optimierungssystem nennt, steht dabei i (I = 1, 2, ..., m) für eines der Restriktionszeichen "=", "", c1, c2, ... ,cn, a11, a12, ... , amn, b1, b2, ... , bm, für gewisse Konstanten und x1, x2, ..., xn für gewisse reellwertige Variablen, die stets so zu wählen sind, daß sämtliche Restriktionen von (2) erfüllt sind, d. h., das Restriktionssystem (2) beschreibt eine gewisse Lösungsmenge. - Jeder Lösung aus dieser Lösungsmenge ist durch die Funktion (1) (Zielfunktion) eine Zahl x0 (Zielwert) zugeordnet, die in Verbindung mit einer der Vorschriften von (3) (Zielvorschrift) eine Beurteilung der Güte der betreffenden Lösung erlaubt. Die Zielvorschrift x0 —> Max! (x0 —> Min!) besagt dabei, daß eine Lösung mit einem größeren (kleineren) Zielwert besser ist als jede andere Lösung mit einem kleineren (größeren) Zielwert. - Die Charakterisierung von Systemen des Typs ((1),(2),(3)) als linear erklärt sich insofern, als die Zielfunktion (1) und sämtliche Restriktionen (2) linear sind (lineare Zielfunktion, lineare Restriktion).
II. Grundlegende Fragestellungen: 1. Optimale Lösung: Im Zusammenhang mit linearen Optimierungssystemen drängt sich die Frage auf, welche Lösung von (2) den durch (1) definierten Zielwert x0 maximiert (oder minimiert) bzw. wie man ggf. erkennt, daß eine solche optimale Lösung nicht existiert. Zur Beantwortung derartiger Fragen wurden eine ganze Reihe von Verfahren (Simplexmethoden) entwickelt und in entsprechende Standardsoftware eingebettet, die geeignet ist, auch sehr große Probleme der Praxis (d. h. Probleme mit vielen Variablen und Restriktionen) zu lösen. - 2. Beim Einsatz linearer Optimierungssysteme in der Praxis besteht häufig Ungewißheit über die tatsächlichen numerischen Werte der Koeffizienten c1, ..., cn, a11, ..., amn, b1, ..., bm; z. T. ist sogar unklar, ob bestimmte Restriktionen von (2) überhaupt auftreten. Wie man im Hinblick auf derartige Situationen - ausgehend von einer ersten optimalen Lösung - auf einem möglichst einfachen Wege Alternativrechnungen (postoptimale Rechnungen) durchführen kann, ist eine weitere Problemstellung. - 3. Vor dem gleichen Hintergrund untersucht man im Rahmen von Sensitivitätsanalysen, wie sich bestimmte Koeffizienten (v. a. die Koeffizienten c1, ..., cn der Zielfunktion (1) bzw. die rechten Seiten b1, ..., bm der Restriktionen (2)) ändern dürfen, ohne daß eine gefundene optimale Lösung (bzw. eine gefundene kanonische Form des Optimierungssystems) die Eigenschaft der Optimalität verliert. - 4. Die parametrische lineare Optimierung befaßt sich mit der noch erweiterten Fragestellung, welche optimalen Lösungen sich jeweils ergeben, wenn gewisse Koeffizienten (v. a. Koeffizienten der Zielfunktion und/oder die rechten Seiten der Restriktionen) in Abhängigkeit von einem oder mehreren Parametern schwanken können. - 5. Die Dualitätstheorie der linearen Optimierung untersucht den Zusammenhang zwischen gewissen Paaren von linearen Optimierungssystemen. Ihre Erkenntnisse sind v. a. für die Entwicklung von Rechenverfahren von Bedeutung. - 6. Die bei Anwendung in der Praxis vorkommenden linearen Optimierungssysteme sind i. d. R. sehr groß (viele Variablen, viele Restriktionen), so daß die Bestimmung einer optimalen Lösung mit herkömmlichen Lösungsverfahren sehr viel Rechenzeit und Speicherplatz beanspruchen kann. Es läßt sich jedoch oft beobachten, daß die jeweiligen Koeffizientenmatrizen nur wenige von Null verschiedene Koeffizienten a11, ..., amn (mageres lineares Gleichungssystem, dünn besetzte Matrix) aufweisen. Fragen im Zusammenhang mit deren Ausnutzung stellen sich im Hinblick auf die Entwicklung schnellerer, weniger speicherplatzintensiver Lösungsverfahren.
III. Spezielle Strukturen: Optimierungssysteme der Praxis zeichnen sich i. d. R. nicht nur durch dünn besetzte Koeffizientenmatrizen aus, die von Null verschiedenen Koeffizienten sind außerdem oft nach einem gewissen Schema angeordnet. Derartige speziell strukturierte Systeme ergeben sich etwa bei der mathematischen Formulierung von Transportproblemen und Zuordnungsproblemen, von Wege- und Flußproblemen in Graphen (Netzplantechnik). Sie lassen sich mit traditionellen Simplexmethoden lösen, daneben gibt es aber Lösungsverfahren, die durch eine Ausnutzung der jeweiligen speziellen Koeffizientenstruktur erhebliche Vorteile in bezug auf Rechenzeit und Speicherbedarf erzielen.
IV. Erweiterungen: Durch bestimmte Umformungen und Techniken lassen sich die Methoden der l. O. z. T. auch zur Untersuchung von Fragen über solche Optimierungssysteme einsetzen, deren Struktur nur unvollständig mit der des Systems ((1), (2), (3)) übereinstimmt: 1. Gewisse (d. h. mindestens eine, möglicherweise aber auch alle) Variablen dürfen nur ganze Zahlen (ganzzahliges Optimierungsproblem) bzw. nur die Werte Null oder Eins annehmen (binäres Optimierungsproblem). - 2. Gewisse Probleme der nichtlinearen Optimierung (nichtlineare Optimierung) lassen sich ebenfalls mit linearen bzw. geringfügig modifizierten linearen Methoden lösen. Hierzu gehört u. a. die Bestimmung von optimalen Lösungen für quadratische Optimierungsprobleme und bestimmte separable Optimierungsprobleme. - 3. Im Rahmen der l. O. bei mehrfacher Zielsetzung stehen solche linearen Optimierungssysteme im Mittelpunkt, bei denen den Lösungen des Restriktionssystems (2) anhand verschiedener Zielfunktionen gleichzeitig mehrere Zielwerte zugeordnet sind. Nur in ganz seltenen Ausnahmefällen existiert jetzt noch eine Lösung, die im Hinblick auf alle Zielfunktionen und -vorschriften gleichzeitig optimal ist. Die für diese Optimierungssysteme entwickelten Verfahren bezwecken deshalb nicht die Ableitung einer in diesem Sinne idealen Lösung, sondern es geht vielmehr um die Ableitung von allen oder einigen effizienten Lösungen bzw. bei interaktiven Verfahren um die Ermittlung einer für den Entscheidenden akzeptablen Kompromißlösung.
V. Ökonomische Anwendung: Von allen Methoden des Operations Research haben diejenigen der l.O. (neben denen der Netzplantechnik) die weiteste Verbreitung in der ökonomischen Praxis gefunden und sich bewährt. Empirischen Untersuchungen zufolge liegen ihre Einsatzschwerpunkte in der Grundstoff-, der chemischen, der Eisen- und Stahl- sowie der Nahrungs- und Genußmittelindustrie. Bezüglich der betrieblichen Funktionsbereiche sind in erster Linie Anwendungen im Produktionsbereich (zur Lösung von Problemen der Produktionsprogrammplanung, Produktionssteuerung und Zuschnittplanung), im Absatzbereich (Transportproblem), in der Lagerhaltung (Bestimmung optimaler Lagerbestände) sowie im Beschaffungsbereich (Transportproblem, Mischungsproblem, optimale Bestellmenge) anzuführen. - In stärkerem Maße setzen sich schließlich auch integrierte Modelle zur simultanen Planung verschiedener Funktionsbereiche (v. a. des Produktions- und des Absatzbereichs) durch.
VI. Software: Die Lösung eines linearen Optimierungsproblems in der Praxis macht - wegen Größe des dabei zu behandelnden Optimierungssystems - regelmäßig den Computer-Einsatz erforderlich: 1. Für Großrechenanlagen angebotene Standardsoftware hat in der Zwischenzeit einen hohen Entwicklungsstand erreicht, der weit über das einfache Berechnen einer optimalen Lösung hinausgehend eine Vielzahl von Programmbausteinen, u. a. zur Sensitivitätsanalyse, parametrischen Optimierung, ganzzahligen und binären Optimierung sowie Lösung von Optimierungsproblemen mit spezieller Struktur umfaßt. Daneben stehen gewöhnlich Unterprogramme zur Unterstützung der Dateneingabe sowie zur Erzeugung eines standardisierten Lösungsreports zur Verfügung. Solange in den betrachteten Optimierungssystemen ausschließlich reellwertige Variable vorkommen, bleiben im Hinblick auf diese Software - zumindest bzgl. Rechengeschwindigkeit - kaum noch Wünsche offen. So lassen sich auch für Optimierungssysteme mit mehr als 10 000 Variablen/Restriktionen in annehmbarer Zeit optimale Lösungen berechnen. Vorteilhaft macht sich dabei der Umstand bemerkbar, daß bei geringfügigen Datenänderungen das Problem nicht von vorn durchgerechnet werden muß, sondern bei einer zuvor berechneten (und gespeicherten) kanonischen Form "aufgesetzt" werden kann. Als problematischer erweist sich dagegen in der Praxis z. T. die Behandlung von Optimierungssystemen mit vielen ganzzahligen oder binären Variablen. Hier kommt es vor, daß die Verfahren mit dem Erreichen einer vorgegebenen Rechenschranke abbrechen, ohne daß eine optimale Lösung gefunden bzw. nachgewiesen werden konnte. Diejenige zulässige Lösung, die den bis zu diesem Zeitpunkt günstigen Zielwert aufweist, läßt sich dann aber immer noch als eine (gewöhnlich gute) Annäherung an die gesuchte optimale Lösung interpretieren. - 2. Die Entwicklung von Software für Personalcomputer ist dagegen noch in vollem Gang. Viele der angebotenen Programmpakete sind allenfalls zu Schulungszwecken einsetzbar. Es gibt aber auch bereits PC-Software, mit der reale Optimierungsprobleme der Praxis, die mehrere tausend (reellwertige) Variablen und Restriktionen aufweisen, gelöst werden.
VII. Neuere Entwicklungen: Theoretische, am Worst-case-Verhalten von Algorithmen orientierte Überlegungen haben Zweifel an der rechentechnischen Vorteilhaftigkeit der (in der Praxis gewährten) Simplexmethoden entstehen lassen. Dieser Umstand führte zur Entwicklung des zwar theoretisch günstigeren Ellipsoid-Verfahrens, das sich bei konkreten Vergleichsrechnungen aber (mit Ausnahmen einiger künstlich konstruierter Sonderfälle) als praktisch schlechter erwies. Aufsehen erregte in jüngerer Zeit auch das Karmakar-Verfahren, dessen praktische Überlegenheit aber bisher ebenfalls nicht schlüssig aufgezeigt werden konnte. Allerdings kann wegen der kurzen Zeit, die seit dessen Veröffentlichung vergangen ist, noch kein endgültiges Urteil über dieses Verfahren getroffen werden.
Literatur: Bradley, S. P./Hax, A. C./Magnanti, T. L., Applied Mathematical Programming, Reding (Mass.) 1977; Dantzig, G. B., Lineare Programmierung und Erweiterungen, Berlin - Heidelberg 1966; Jaeger, A./Wäscher, G., Mathematische Propädeutik für Wirtschaftswissenschaftler: Lineare Algebra, München - Wien 1986; Karmakar, N., A New Polynomial-Time Algorithm for Linear Programming, in: Combinatoria 4 (1984), S. 373-396; Schmitz, P./Schönlein, A., Lineare und linearisierbare Optimierungsmodelle sowie ihre ADV-gestützte Lösung, Braunschweig 1978; Weber, H. M., Khachiyan's Algorithmus, in: Zeitschrift für Operations Research 26 (1982), B 229- B 240.
<< vorheriger Begriff |
|
nächster Begriff>> |
|
|
|
Diese Seite bookmarken :
|
|
