lineare Optimierung

Die lineare Optimierung bzw. lineare Programmierung (LP) ist der wichtigste Teilbereich des Operations Research. Im Mittelpunkt stehen LPModelle, zugehörige Lösungsverfahren, wie z.B. der Simplex-Algorithmus, und die Dualitätstheorie.

Siehe auch: lineare Programmierung

Lineare Programmierung (LP)

(lineare Planungsrechnung, lineare Programmierung) wichtige Teildisziplin der mathematischen Optimierung und Planungsmathematik des 0perations Research. Die Modelle der linearen Optimierung bestehen aus einer linearen Zielfunktion und einer Vielzahl linearer Restriktionen. Zahlreiche Unternehmungsmodelle, Absatzplanungsmodelle und Transportmodelle, Finanzplanungsmodelle und Produk- tionsplanungsmodelle sind vom Typ der linearen Optimierung. Die grösste Bedeutung hat die lineare Optimierung für die Fertigungsplanung (Input-Output-Funktion, Produktionsprogrammoptimierung, Kuppelproduktionsoptimierung, Mischungsoptimierung, Verschnittoptimierung). Das System der Restriktionen enthält m Gleichungen und m 4- n Variablen, nämlich alle yj und Xj. Wenn n Variablen gleich Null sind, lassen sich die restlichen m Variablen - von gewissen Ausnahmefällen abgesehen - bestimmen. Jede derartige "Basislösung" bildet einen Eckpunkt in der geometrischen Darstellung des Restriktionensystems. Es lässt sich zeigen, dass die optimale Lösung ebenfalls eine Basislösung ist. Es gilt also, den richtigen Satz an n Variablen gleich Null zu setzen, um die optimale Lösung zu erhalten. Auf dieser Idee baut das Simplex-Verfahren von George B. Dantzig von 1947 auf. Anfangs werden alle n Variablen Xj gleich Null gesetzt, und es ergeben sich die Werte der yj aus den bi. Die gleich Null gesetzten Variablen nennt man "Nichtbasisvariablen", die anderen "Basisvariablen". Nun wird pro Rechenschritt (Iteration) jeweils eine Nichtbasisvariable gegen eine Basisvariable ausgetauscht, wobei jeweils der Zielfunktionswert z vergrössert wird. Im Zusammenhang damit wird das System der Zielfunktion und Restriktionen nach Regeln der linearen Algebra so umgewandelt, dass die gegenwärtigen Basisvariablen nur in jeweils einer einzigen Restriktion mit dem Koeffizienten 1 erscheinen. Die Iterationen werden fortgesetzt, bis keine Verbesserung des Zielfunktionswertes mehr möglich ist, was sich an den Vorzeichen der Zielfunk- tionskoeffizienten schnell erkennen lässt. Für das Simplex-Verfahren gibt es zahlreiche leistungsfähige Standardrechenpro- gramme für EDV-Anlagen. Auf entsprechend grossen EDV-Anlagen lassen sich Modelle mit einigen tausend Restriktionen und Variablen ohne besondere Schwierigkeiten bearbeiten. Literatur: Dantzig, G. B., Lineare Programmierung und Erweiterungen, Berlin u.a. 1966. Müller-Mer- bach, H., Operations Research, 3. Aufl., München 1973. Gass, S.I., Linear Programming, 5. Aufl., New York 1984.

LP-Modelle

Vorhergehender Fachbegriff: lineare Mehrfachregression | Nächster Fachbegriff: Lineare Optimierung, -Programmierung

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : Planungsumfeld | Konstant Summen Skala | Schuldschein-Darlehen

Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

Marketing

Definition

Konditionenpolitik

Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

Investitionsrechnungen

Marktversagen

Umsatzsteuer